本文實例講述了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
