kNN（k-Nearest Neighbors，k近邻）是机器学习中非常基础的一种算法，算法原理简单而且容易实现，结果精度高，无需估计参数，无需训练模型，而且不仅可以用于分类任务，还可以应用到回归问题。作为开始学习机器学习的入门是一个很好的选择。
俗话说：近朱者赤，近墨者黑，物以类聚，人以群分。KNN算法就是这样。它使相同类别的样本在特征空间中聚集在一起。
分类时一般采用多数表决投票法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。
简单来说就是计算输入数据D与所有样本点的距离，然后取最小的前k个样本的标签的统计即可。
如下图，现在有三种颜色的点分布在二维空间中，对应了分类任务中的训练样点的三个类别。现在我们希望推测图中黄色圆的那个点是属于那个类别，那么knn算法将计算该点与所有训练样点之间的距离，并且挑选出距离最小的k个样点（此处k=4，根据实际需要自定义），那么黄色点的类别将通过图中连接的4个点来判断。很明显，这4个点均为红色类别，那么黄色点被推测为红色类别。
同理，再看下图所示，此时这4个样本点包含了2个类别，针对这样的情况，knn算法通常采用投票法来进行类别推测，即找出k个样本点中类别出现次数最多的那个类别，因此黄色点的类型被推测为蓝色类别。
KNN算法的主要实现步骤：
计算测试数据与各训练数据之间的距离。按照距离的大小进行排序。选择其中距离最小的k个样本点。确定K个样本点所在类别的出现频率。返回K个样本点中出现频率最高的类别作为最终的预测分类。python代码实现
import numpy as npimport operatordef knnClassify(inputX, data, labels, k): # 1.计算测试数据与各训练数据之间的距离。 dataSize = data.shape[0] x = np.tile(inputX, (dataSize, 1)) - data xPositive = x ** 2 xDistances = xPositive.sum(axis=1) distances = np.sqrt(xDistances) # 2.按照距离的大小进行排序。 sortDisIndex = distances.argsort() # 3.选择其中距离最小的k个样本点。4.确定K个样本点所在类别的出现频率。 classCount = {} # 创建字典：label为键，频数为值 for i in range(k): getLabel = labels[sortDisIndex[i]] classCount[getLabel] = classCount.get(getLabel, 0) + 1 # 5.返回K个样本点中出现频率最高的类别作为最终的预测分类。 sortClass = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) print(sortClass[0][0]) return sortClass[0][0]if __name__ == '__main__': # 测试数据 inputX = np.array([2, 2.2, 1.9]) # 训练数据 data = np.array([[1, 0.9, 1], [0.8, 0.9, 0.7], [1.3, 1, 1.2], [1.2, 0.9, 1], [2, 2.2, 2.1], [2.3, 2.2, 2], [2, 2.2, 1.9], [1.9, 2.2, 2.1], [3.1, 3.1, 3], [2.8, 2.9, 3.1], [2.9, 3, 3.2], [3.1, 3, 3.1]]) # 训练数据标签 labels = np.array([1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]) k = 4 knnClassify(inputX, data, labels, k)