Java實現的KNN算法示例

2024-07-14 08:41:19

字體：大中小

來源：轉載

供稿：網友

本文實例講述了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語言實現：

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算法

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");      }    }  }}

主函數

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);    }  }}

測試的結果：