K邻近算法

1 算法介绍

1.1 什么是K-NN

K-NN（K Near Neighbor）：k个最近的邻居，即每个样本都可以用它最接近的k个邻居来代表。K-NN算法属于监督学习方式的分类算法，即计算某给点到每个点的距离作为相似度的反馈。简单来讲，KNN就是“近朱者赤，近墨者黑”的一种分类算法。

1.2 K-NN的算法思想

k-NN算法的基本思想是：给定一个待分类样本，找出与其距离最近的k个训练样本（邻居），然后通过这k个邻居的类别来决定待分类样本的类别，即这K个样本的多数属于某个类，就把该输入样本分类到这个类中。（这就类似于现实生活中少数服从多数的思想）。在回归任务中，则通过这k个邻居的值来预测待测样本的值，即通过这k个邻居的目标变量值的平均值来预测待测样本的目标变量值。

【案例1】如下图：有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。我们的目标是对于这个新的数据点，确定它的类别是什么？

使用k近邻的思想来给绿色圆点进行分类：

（1）如果K=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

（2）如果K=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

【案例2】

假设我们对男性身高的判断为：矮【150.154.158】，中【170，175，178】，高【180.185，188】，而小明的身高为152，我们人类一眼就可以判断出小明的身高属于矮，因为152离150和154最近。这是我们人为的判断，而knn算法呢，就是通过一些算法告诉计算机，让计算机来判断小明的身高属于哪个级别。

1.3 k-近邻算法三要素

k-近邻算法三要素：距离度量、k值选择和分类决策规则。

1、选择参数k：选择一个正整数k，表示选择k个邻居。K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。

在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。

2、计算距离：对待预测样本和训练样本中的每一个样本计算距离。常用的距离度量方法有欧氏距离（Euclidean distance）、曼哈顿距离（Manhattan distance）等。

（1）欧氏距离

欧式距离是最常用的距离度量方法，适用于多维空间中的点。对于两个点_a_(_x_11,_x_12,…,x_1_n) 和 b(_x_21,_x_22,…,x_2_n)，欧式距离定义为：

（2）曼哈顿距离在每个维度上计算绝对差值之和，适用于需要考虑方向但不考虑对角线距离的情况。对于两个点 a 和 b，曼哈顿距离定义为：

3、选择k个最近的邻居：从训练样本中选出与待预测样本距离最近的k个样本。

4、计算预测值：在分类任务中，通过投票法决定待分类样本的类别，即选择k个邻居中出现最多的类别作为结果。在回归任务中，通过取k个邻居的平均值作为预测结果。

2 算法实现

2.1 算法步骤

【案例1】给定一个点的坐标，判断该点是红点还是蓝点。

【分析】

（1）获取训练数据

训练数据格式：((x,y),label)即(位置,标签)

（2）给定一个点，如：((0.145211188,0.548882643),?)

计算该点到所有点的距离，然后对距离排序，取K个最近距离的点。再根据多数原则，得出该点的分类（标签）。

根据上例，K邻近算法的步骤：

（1）计算测试数据与各个训练数据之间的距离；

（2）按照距离的递增关系进行排序；

（3）选取距离最小的K个点；

（4）确定前K个点所在类别的出现频率；

（5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

2.2 算法实现

1、案例1代码实现

public static void main(String[] args) throws IOException {

    // 1 创建训练集// 1.1 获取训练集数据: 0.559159703 0.098352957    0String filePath = "d:\\user\\input\\train.txt";List<String> lines = FileUtils.readLines(new File(filePath));// 2.2 将训练数据转换成元组:((0.559159703,0.098352957),0)List<Tuple2<Double[],Object>> trains = new ArrayList<>();for(String line : lines){String[] split = line.split("(\\s+|\t)");// 分割数据Double[] coordinate = {Double.valueOf(split[0]),Double.valueOf(split[1])};Tuple2 train = Tuple2.of(coordinate,split[2]);trains.add(train);}// 2 训练// 2.1 获取测试数据Double[] center = {0.160564179,0.427239984};// 2.2 预测String label = Knn.predic(trains,center);System.out.println(Arrays.asList(center) + "\t" + label);    }

2、创建Knn类

（1）计算测试数据与各个训练数据之间的距离

 /*** 计算欧式距离* @param a 中心点* @param b 测试点* @return*/public static Double euclidDistance(Double[] a, Double[] b){double result = 0;double tmp = 0;for (int i = 0; i < a.length ; i++) {tmp = tmp + Math.pow(a[i]-b[i],2);}result = Math.sqrt(tmp);return result;}

（2）按照距离的递增关系进行排序

 /*** 按照距离的递增关系进行排序* @param tmpList 距离集合*/public static void sort(List<Tuple2<Object,Double>> tmpList) {Collections.sort(tmpList, new Comparator<Tuple2< Object, Double>>() {@Overridepublic int compare(Tuple2< Object, Double> o1, Tuple2< Object, Double> o2) {if(o1.f1 > o2.f1){return 1;}else if(o1.f1 < o2.f1){return -1;}else {return 0;}}});}

（3）选取距离最小的K个点

/**

 * 选取最近的k个点（特征集合）* @param tmpList 距离集合* @param k* @return*/public static List<Tuple2< Object,Double>> setK(List<Tuple2< Object,Double>> tmpList,int k) {List<Tuple2< Object,Double>> labels = tmpList.subList(0, k);return labels;}

（4）确定前K个点所在类别的出现频率

  /*** 确定前K个点所在类别的出现频率* @param labels 特征集合* @return*/public static Map<String,Integer> count(List<Tuple2< Object,Double>>  labels) {// 计算每个分类包含的点的个数Map<String,Integer> rates = new HashMap<>();for (Tuple2< Object,Double> t : labels) {String type = (String)t.f0;// 当key存在时，old+value,否则key的值为1rates.merge(type,1,Integer::sum);}return rates;}

（5）返回前K个点中出现频率最高的类别作为测试数据的预测分类

/**

 * 返回前K个点中出现频率最高的类别作为测试数据的预测分类* @param rates* @return*/public static String result(Map<String,Integer> rates) {// 找出最大频率double value = 0.0;String type = "";for (Map.Entry<String, Integer> entry : rates.entrySet()) {if (entry.getValue() > value) {type = entry.getKey();value = entry.getValue();}}return type;}

（6）算法步骤封装

/**

 * 预测结果* @param trains* @param tests* @return*/public static String predic(List<Tuple2<Double[],Object>> trains,Double[] tests){// 1 计算测试数据与各个训练数据之间的距离，并将距离封装到元组(标签，距离)List<Tuple2< Object,Double>> tmpList = new ArrayList<>();for(Tuple2<Double[],Object> train:trains){Double d = Knn.euclidDistance(tests, train.f0);Tuple2 t = Tuple2.of(train.f1,d);tmpList.add(t);}// 2 按照距离的递增关系进行排序Knn.sort(tmpList);// 3 选取最近的k个点List<Tuple2< Object,Double>> labels = Knn.setK(tmpList, 7);// 4 确定前K个点所在类别的出现频率Map<String, Integer> rates = Knn.count(labels);// 5 返回前K个点中出现频率最高的类别作为测试数据的预测分类return  Knn.result(rates);}