K-近邻算法（KNN）

╰+攻爆jí腚メ 2022-02-21 02:18 290阅读 0赞

*  **K-近邻算法（Knn）**  
    其原理为在一个样本空间中，有一些已知分类的样本，当出现一个未知分类的样本，则根据距离这个未知 样本最近的k个样本来决定。  
    举例：爱情电影和动作电影，它们中都存在吻戏和动作，出现一个未知分类的电影，将根据以吻戏数量和动作数量建立的坐标系中距离未知分类所在点的最近的k个点来决定。
 *  **算法实现步骤**
    
     *  计算所有点距离未知点的欧式距离
     *  对所有点进行排序
     *  找到距离未知点最近的k个点
     *  计算这k个点所在分类出现的频率
     *  选择频率最大的分类即为未知点的分类
 *  **实现代码**  
    Point类

package cn.demo.myfriend.knndemo;
    
    import java.io.Serializable;
    
    public class Point implements Serializable{
    	//标识编码
        private String no;
        //X坐标
        private double x;
        //y坐标
        private double y;
        //类型
        private String type;
        
        public Point(String no,double x, double y) {
            this.x = x;
            this.y = y;
            this.no = no;
        }
    
        public Point(String no,double x, double y, String type) {
            this.x = x;
            this.y = y;
            this.type = type;
            this.no = no;
        }
    
    	public String getNo() {
    		return no;
    	}
    
    	public void setNo(String no) {
    		this.no = no;
    	}
    
    	public double getX() {
    		return x;
    	}
    
    	public void setX(double x) {
    		this.x = x;
    	}
    
    	public double getY() {
    		return y;
    	}
    
    	public void setY(double y) {
    		this.y = y;
    	}
    
    	public String getType() {
    		return type;
    	}
    
    	public void setType(String type) {
    		this.type = type;
    	}
        
        
    }

Distance类

package cn.demo.myfriend.knndemo;
    
    import java.io.Serializable;
    
    /**
     * 点信息
     * 
     * @author zhongyulin
     *
     */
    public class Distance implements Serializable {
    	// 已知点id
    	private String no;
    	// 未知点id
    	private String nid;
    	// 二者之间的距离
    	private double disatance;
    
    	public Distance(String no, String nid, double disatance) {
    		this.no = no;
    		this.nid = nid;
    		this.disatance = disatance;
    	}
    
    	public String getNo() {
    		return no;
    	}
    
    	public void setNo(String no) {
    		this.no = no;
    	}
    
    	public String getNid() {
    		return nid;
    	}
    
    	public void setNid(String nid) {
    		this.nid = nid;
    	}
    
    	public double getDisatance() {
    		return disatance;
    	}
    
    	public void setDisatance(double disatance) {
    		this.disatance = disatance;
    	}
    
    }

CompareClass类

package cn.demo.myfriend.knndemo;
    
    import java.util.Comparator;
    
    /**
     * 比较器类
     * @author zhongyulin
     *
     */
    public class CompareClass implements Comparator<Distance>{
       
    	/**
    	 * 比较二者之间的距离
    	 */
      public int compare(Distance d1, Distance d2) {
          return d1.getDisatance()>d2.getDisatance()?20 : -1;
      }
    
    }

KnnUtil 类

package cn.demo.myfriend.knndemo;
    
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    
    /**
     * KNN算法实现工具类
     * @author zhongyulin
     *
     */
    public class KnnUtil {
    	   // 欧式距离计算
    	   public static double oudistance(Point point1, Point point2) {
    	       // pow() 方法可返回 x 的 y 次幂的值
    		   //Math.pow(x,y) 
    	       double temp = Math.pow(point1.getX() - point2.getX(), 2)
    	               + Math.pow(point1.getY() - point2.getY(), 2);
    	       //Math.sqrt() 返回一个正的平方跟
    	       return Math.sqrt(temp);
    	   }
    	   
    	   // 找出最大频率
    	   public static String maxP(Map<String, Double> map) {
    	       String key = null;
    	       double value = 0.0;
    	       for (Map.Entry<String, Double> entry : map.entrySet()) {
    	           if (entry.getValue() > value) {
    	               key = entry.getKey();
    	               value = entry.getValue();
    	           }
    	       }
    	       return key;
    	   }
    	   
    	   // 计算频率
    	   public static Map<String, Double> computeP(Map<String, Integer> map,
    	           double k) {
    	       Map<String, Double> p = new HashMap<String, Double>();
    	       for (Map.Entry<String, Integer> entry : map.entrySet()) {
    	           p.put(entry.getKey(), entry.getValue() / k);
    	       }
    	       return p;
    	    }
    	   
    	   // 计算每个分类包含的点的个数
    	   public static Map<String, Integer> getNumberOfType(List<Distance> listDistance, List<Point> listPoint, double k){
    		   Map<String, Integer> map = new HashMap<String, Integer>();
    		   int i = 0;
    	       System.out.println("选取的k个点，由近及远依次为：");
    	       for (Distance distance : listDistance) {
    	    	   System.out.println("id为" + distance.getNo() + ",距离为："
    	                   + distance.getDisatance());
    	    	   String no=distance.getNo();
    	    	   // 通过no找到所属类型,并存储到HashMap中
    	    	   for (Point point : listPoint) {
    				   if(no.equals(point.getNo())) {
    					   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;
    		   }
    		   return map;
    	   }
    }

KnnMain类

package cn.demo.myfriend.knndemo;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    import java.util.TreeSet;
    
    
    
    /**
     * KNN算法入口
     * @author zhongyulin
     *
     */
    public class KnnMain {
    	
    
       // 测试数据
       public static ArrayList<Point> creatDataSet(){
    	   Point point1 = new Point("A", 3, 104, "Romance");
           Point point2 = new Point("B", 2, 100, "Romance");
           Point point3 = new Point("C", 30, 81, "Romance");
           Point point4 = new Point("D", 101, 10, "Action");
           Point point5 = new Point("E", 99, 5, "Action");
           Point point6 = new Point("F", 98, 2, "Action");
           Point point7 = new Point("G", 70, 98, "Unknown");
           
           ArrayList<Point> dataList = new ArrayList<Point>();
           dataList.add(point1);
           dataList.add(point2);
           dataList.add(point3);
           dataList.add(point4);
           dataList.add(point5);
           dataList.add(point6);
           
           return dataList;
       }
       /**
        * 1、输入所有已知点 
          2、输入未知点 
          3、计算所有已知点到未知点的欧式距离 
          4、根据距离对所有已知点排序 
          5、选出距离未知点最近的k个点 
          6、计算k个点所在分类出现的频率 
          7、选择频率最大的类别即为未知点的类别
        * @param args
        */
       public static void main(String[] args) {
    	   // 一、输入所有已知点
           List<Point> dataList = creatDataSet();
           // 二、输入未知点
           Point x = new Point("M", 60, 79);
           // 三、计算所有已知点到未知点的欧式距离，并根据距离对所有已知点排序
           CompareClass compare = new CompareClass();
           Set<Distance> distanceSet = new TreeSet<Distance>(compare);
           for (Point point : dataList) {
               distanceSet.add(new Distance(point.getNo(), x.getNo(), KnnUtil.oudistance(point,
                       x)));
           }
           // 四、选取最近的k个点
           double k = 3;
           /**
           * 五、计算k个点所在分类出现的频率
           */
           // 1、计算每个分类所包含的点的个数
           List<Distance> distanceList= new ArrayList<Distance>(distanceSet);
           Map<String, Integer> map = KnnUtil.getNumberOfType(distanceList, dataList, k);
           
          // 2、计算频率
           Map<String, Double> p = KnnUtil.computeP(map, k);
           
           x.setType(KnnUtil.maxP(p));
           System.out.println("未知点的类型为："+x.getType());
       }
    }