本文实例讲述了java实现的knn算法。分享给大家供大家参考，具体如下：
提起knn算法大家应该都不会陌生，对于数据挖掘来说算是十大经典算法之一。
算法的思想是：对于训练数据集中已经归类的分组，来对于未知的数据进行分组归类。其中是根据该未知点与其训练数据中的点计算距离，求出距离最短的点，并将其归入该点的那一类。
看看算法的工程吧：
1. 准备数据，对数据进行预处理
2. 选用合适的数据结构存储训练数据和测试元组
3. 设定参数，如k
4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列
5. 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离l 与优先级队列中的最大距离lmax
6. 进行比较。若l>=lmax，则舍弃该元组，遍历下一个元组。若l < lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队 列。
7. 遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。
8. 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。
根据算法的过程我们进行java语言实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
package knn;/** * 点的坐标 x 、y * @author administrator * */public class pointbean {int x;int y;public int getx() { return x;}public void setx(int x) { this.x = x;}public int gety() { return y;}public void sety(int y) { this.y = y;}public pointbean(int x, int y) { super(); this.x = x; this.y = y;}public pointbean() { super();}@overridepublic string tostring() { return "pointbean [x=" + x + ", y=" + y + "]";}} |
knn算法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
package knn;import java.util.arraylist;/** * knn实现的方法 * @author administrator * */public class knnmain { public double getpointlength(arraylist<pointbean> list,pointbean bb){ int b_x=bb.getx(); int b_y=bb.gety(); double temp=(b_x -list.get(0).getx())*(b_x -list.get(0).getx())+ (b_y -list.get(0).gety())*(b_y -list.get(0).gety()); // 找出最小的距离 for(int i=1;i<list.size();i++){ if(temp<((b_x -list.get(i).getx())*(b_x -list.get(i).getx())+ (b_y -list.get(i).gety())*(b_y -list.get(i).gety()))){ temp=(b_x -list.get(i).getx())*(b_x -list.get(i).getx())+ (b_y -list.get(i).gety())*(b_y -list.get(i).gety()); } } return math.sqrt(temp); } /** * 获取长度，找出最小的一个进行归类 * @param list1 * @param list2 * @param list3 * @param bb */ public void getcontent(arraylist<pointbean> list1,arraylist<pointbean> list2, arraylist<pointbean> list3,pointbean bb){ double a=getpointlength(list1,bb); double b=getpointlength(list2,bb); double c=getpointlength(list3,bb); //做出比较 if(a>b){ if(b>c){ system.out.println("这个点:"+bb.getx()+" , "+bb.gety()+" " +"属于c"); }else { system.out.println("这个点:"+bb.getx()+" , "+bb.gety()+" " +"属于b"); } }else { if(a>c){ system.out.println("这个点:"+bb.getx()+" , "+bb.gety()+" " +"属于c"); }else { system.out.println("这个点:"+bb.getx()+" , "+bb.gety()+" " +"属于a"); } } }} |
主函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
package knn;import java.util.arraylist;/* * 主函数 knn */public class testjava { static arraylist< pointbean> lista; static arraylist< pointbean> listb; static arraylist< pointbean> listc; static arraylist< pointbean> listd; public static void main(string[] args) { //创佳arraylist lista=new arraylist<pointbean>(); listb=new arraylist<pointbean>(); listc=new arraylist<pointbean>(); listd=new arraylist<pointbean>(); //写入数据 setdate(); gettestresult(); } /** * 得到结果 */ private static void gettestresult() { //创建对象 knnmain km=new knnmain(); for(int i=0;i<listd.size();i++){ km.getcontent(lista, listb, listc, listd.get(i)); } } /** * 写入数据 */ private static void setdate() { //a的坐标点 int a_x[]={1,1,2,2,1}; int a_y[]={0,1,1,0,2}; //b的坐标点 int b_x[]={2,3,3,3,4}; int b_y[]={4,4,3,2,3}; //c的坐标点 int c_x[]={4,5,5,6,6}; int c_y[]={1,2,0,2,1}; // 测试数据 //b的坐标点 int d_x[]={3,3,3,0,5}; int d_y[]={0,1,5,0,1}; // pointbean ba; for(int i=0;i<5;i++){ ba=new pointbean(a_x[i], a_y[i]); lista.add(ba); } // pointbean bb ; for(int i=0;i<5;i++){ bb=new pointbean(b_x[i], b_y[i]); listb.add(bb); } // pointbean bc ; for(int i=0;i<5;i++){ bc=new pointbean(c_x[i], c_y[i]); listc.add(bc); } // pointbean bd ; for(int i=0;i<5;i++){ bd=new pointbean(d_x[i], d_y[i]); listd.add(bd); } }} |
测试的结果：
这个点:3 , 1 属于a
这个点:3 , 5 属于b
这个点:0 , 0 属于a
这个点:5 , 1 属于c
到此简单的knn算法已经实现对于未知点的划分，有助于大家对于knn算法的理解。对于改进knn的一些算法java实现会在后面进行贴出。共同学习共同进步！
希望本文所述对大家java程序设计有所帮助。
原文链接：https://blog.csdn.net/u011015260/article/details/53392194
