您好,登錄后才能下訂單哦!
本文實(shí)例講述了Java實(shí)現(xiàn)的KNN算法。分享給大家供大家參考,具體如下:
提起KNN算法大家應(yīng)該都不會(huì)陌生,對(duì)于數(shù)據(jù)挖掘來說算是十大經(jīng)典算法之一。
算法的思想是:對(duì)于訓(xùn)練數(shù)據(jù)集中已經(jīng)歸類的分組,來對(duì)于未知的數(shù)據(jù)進(jìn)行分組歸類。其中是根據(jù)該未知點(diǎn)與其訓(xùn)練數(shù)據(jù)中的點(diǎn)計(jì)算距離,求出距離最短的點(diǎn),并將其歸入該點(diǎn)的那一類。
看看算法的工程吧:
1. 準(zhǔn)備數(shù)據(jù),對(duì)數(shù)據(jù)進(jìn)行預(yù)處理
2. 選用合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)和測(cè)試元組
3. 設(shè)定參數(shù),如k
4.維護(hù)一個(gè)大小為k的的按距離由大到小的優(yōu)先級(jí)隊(duì)列,用于存儲(chǔ)最近鄰訓(xùn)練元組。隨機(jī)從訓(xùn)練元組中選取k個(gè)元組作為初始的最近鄰元組,分別計(jì)算測(cè)試元組到這k個(gè)元組的距離,將訓(xùn)練元組標(biāo)號(hào)和距離存入優(yōu)先級(jí)隊(duì)列
5. 遍歷訓(xùn)練元組集,計(jì)算當(dāng)前訓(xùn)練元組與測(cè)試元組的距離,將所得距離L 與優(yōu)先級(jí)隊(duì)列中的最大距離Lmax
6. 進(jìn)行比較。若L>=Lmax,則舍棄該元組,遍歷下一個(gè)元組。若L < Lmax,刪除優(yōu)先級(jí)隊(duì)列中最大距離的元組,將當(dāng)前訓(xùn)練元組存入優(yōu)先級(jí)隊(duì) 列。
7. 遍歷完畢,計(jì)算優(yōu)先級(jí)隊(duì)列中k 個(gè)元組的多數(shù)類,并將其作為測(cè)試元組的類別。
8. 測(cè)試元組集測(cè)試完畢后計(jì)算誤差率,繼續(xù)設(shè)定不同的k值重新進(jìn)行訓(xùn)練,最后取誤差率最小的k 值。
根據(jù)算法的過程我們進(jìn)行java語言實(shí)現(xiàn):
package KNN; /** * 點(diǎn)的坐標(biāo) 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(); } @Override public String toString() { return "PointBean [x=" + x + ", y=" + y + "]"; } }
KNN算法
package KNN; import java.util.ArrayList; /** * KNN實(shí)現(xiàn)的方法 * @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); } /** * 獲取長(zhǎng)度,找出最小的一個(gè)進(jìn)行歸類 * @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("這個(gè)點(diǎn):"+bb.getX()+" , "+bb.getY()+" " +"屬于C"); }else { System.out.println("這個(gè)點(diǎn):"+bb.getX()+" , "+bb.getY()+" " +"屬于B"); } }else { if(A>C){ System.out.println("這個(gè)點(diǎn):"+bb.getX()+" , "+bb.getY()+" " +"屬于C"); }else { System.out.println("這個(gè)點(diǎn):"+bb.getX()+" , "+bb.getY()+" " +"屬于A"); } } } }
主函數(shù)
package KNN; import java.util.ArrayList; /* * 主函數(shù) 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) { //創(chuàng)佳Arraylist listA=new ArrayList<PointBean>(); listB=new ArrayList<PointBean>(); listC=new ArrayList<PointBean>(); listD=new ArrayList<PointBean>(); //寫入數(shù)據(jù) setDate(); getTestResult(); } /** * 得到結(jié)果 */ private static void getTestResult() { //創(chuàng)建對(duì)象 KnnMain km=new KnnMain(); for(int i=0;i<listD.size();i++){ km.getContent(listA, listB, listC, listD.get(i)); } } /** * 寫入數(shù)據(jù) */ private static void setDate() { //A的坐標(biāo)點(diǎn) int A_x[]={1,1,2,2,1}; int A_y[]={0,1,1,0,2}; //B的坐標(biāo)點(diǎn) int B_x[]={2,3,3,3,4}; int B_y[]={4,4,3,2,3}; //C的坐標(biāo)點(diǎn) int C_x[]={4,5,5,6,6}; int C_y[]={1,2,0,2,1}; // 測(cè)試數(shù)據(jù) //B的坐標(biāo)點(diǎn) 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); } } }
測(cè)試的結(jié)果:
這個(gè)點(diǎn):3 , 1 屬于A
這個(gè)點(diǎn):3 , 5 屬于B
這個(gè)點(diǎn):0 , 0 屬于A
這個(gè)點(diǎn):5 , 1 屬于C
到此簡(jiǎn)單的KNN算法已經(jīng)實(shí)現(xiàn)對(duì)于未知點(diǎn)的劃分,有助于大家對(duì)于KNN算法的理解。對(duì)于改進(jìn)KNN的一些算法JAVA實(shí)現(xiàn)會(huì)在后面進(jìn)行貼出。共同學(xué)習(xí)共同進(jìn)步!
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。