java 实现 数据挖掘_数据挖掘(二)——Knn算法的java实现
1、K-近邻算法(Knn)
其基本原理是在给定的样本空间内，在已有类别标记训练集的基础上，在遇到一个待分类测试样本时，则通过查询与该测试样本距离最近的前k个训练样本来确定其类别归属
举例如下：爱情影片与动作影片，在这两类电影中均包含有吻戏和动作元素。对于一个待分类的新影片，在建立了一个基于吻戏数量与动作数量所构成之坐标系的基础上进行分析后，则会通过寻找距离待分类影片特征点最近的k个已知类别影片来推断其类别定位。
2、算法实现步骤
(1)计算所有点距离未知点的欧式距离
(2)对所有点进行排序
(3)找到距离未知点最近的k个点
(4)计算这k个点所在分类出现的频率
(5)选择频率最大的分类即为未知点的分类
3、java实现
Point类
public classPoint {private longid;private doublex;private doubley;privateString type;public Point(long id,double x, doubley) {this.x =x;this.y =y;this.id =id;
Point构造函数接收四个参数：长整数值id、双精度浮点数x坐标值、双精度浮点数y坐标值以及字符串类型的类型描述
}
//get、set方法省略}
Distance类
public class Distance {
// 已知点id
private long id;
// 未知点id
private long nid;
// 二者之间的距离
private double disatance;
public Distance(long id, long nid, double disatance) {
this.id = id;
this.nid = nid;
this.disatance = disatance;
}
//get、set方法省略
}
比较器CompareClass类
import java.util.Comparator;
//比较器类
public class CompareClass implements Comparator{
public int compare(Distance d1, Distance d2) {
return d1.getDisatance()>d2.getDisatance()?20 : -1;
}
}
KNN主类
/***
1、输入所有已知点
2、输入未知点
3、计算所有已知点到未知点的欧式距离
4、根据距离对所有已知点排序
5、选出距离未知点最近的k个点
6、计算k个点所在分类出现的频率
7、选择频率最大的类别即为未知点的类别
*@authorfzj
**/
public classKNN {public static voidmain(String[] args) {//一、输入所有已知点
List dataList =creatDataSet();//二、输入未知点
Point x = new Point(5, 1.2, 1.2);// 三；计算各已知点与未知点之间的欧氏距离；并按计算出的距离对各已知点进行排序
CompareClass compare = newCompareClass();
Set distanceSet = new TreeSet(compare);for(Point point : dataList) {
distanceSet.add(newDistance(point.getId(), x.getId(), oudistance(point,
x)));
}//四、选取最近的k个点
double k = 5;/*** 五、计算k个点所在分类出现的频率*/
//1、计算每个分类所包含的点的个数
List distanceList= new ArrayList(distanceSet);
Map map =getNumberOfType(distanceList, dataList, k);//2、计算频率
Map p =computeP(map, k);
x.setType(maxP(p));
System.out.println("未知点的类型为："+x.getType());
}//欧式距离计算
public static double EuclideanDistance(Point p1, Point p2) {double temp = Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2);return Math.sqrt(temp);}
}//找出最大频率
public static String maxP(Mapmap) {
String key = null; double value = 0.0; for (Map.Entry entry : map.entrySet()) { if ((Double) entry.getValue().compareTo(value) > 0) { } }
key=entry.getKey();
value=entry.getValue();
}
}returnkey;
}//计算频率
public static Map computeP(Mapmap,doublek) {
Map p = new HashMap();for (Map.Entryentry : map.entrySet()) {
p.put(entry.getKey(), entry.getValue()/k);
}returnp;
}//计算每个分类包含的点的个数
public static MapgetNumberOfType(
List listDistance, List listPoint, doublek) {
Map map = new HashMap();int i = 0;
System.out.println("选择k个点，并按从近到远的顺序排列这些点：");for(Distance dist : listDistance){}
System.out.println("id为" + distance.getId() + ",距离为："
+distance.computeDistance());long identifier = distance.getId();//通过获取标识符来确定所属类别，并将信息存储在HashMap中。
for(Point point : listPoint) {if (point.getId() ==id) {if (map.get(point.getType()) != null)
map.put(point.getType(), map.get(point.getType())+ 1);else{
map.put(point.getType(),1);
}
}
}
i++;if (i >=k)break;
}returnmap;
}public static ArrayListcreatDataSet(){
Point point1= new Point(1, 1.0, 1.1, "A");
Point point2= new Point(2, 1.0, 1.0, "A");
Point point3= new Point(3, 1.0, 1.2, "A");
Point point4= new Point(4, 0, 0, "B");
Point point5= new Point(5, 0, 0.1, "B");
Point point6= new Point(6, 0, 0.2, "B");
ArrayList dataList = new ArrayList();
dataList.add(point1);
dataList.add(point2);
dataList.add(point3);
dataList.add(point4);
dataList.add(point5);
dataList.add(point6);returndataList;
}
}
4、运行结果
参考
[1] 《机器学习实战》