kNN（k-Nearest Neighbors，k近邻）是机器学习中非常基础的一种算法，算法原理简单而且容易实现，结果精度高，无需估计参数，无需训练模型，而且不仅可以用于分类任务，还可以应用到回归问题。作为开始学习机器学习的入门是一个很好的选择。

      俗话说：近朱者赤，近墨者黑，物以类聚，人以群分。KNN算法就是这样。它使相同类别的样本在特征空间中聚集在一起。

      分类时一般采用多数表决投票法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。

简单来说就是计算输入数据D与所有样本点的距离，然后取最小的前k个样本的标签的统计即可。

      如下图，现在有三种颜色的点分布在二维空间中，对应了分类任务中的训练样点的三个类别。现在我们希望推测图中黄色圆的那个点是属于那个类别，那么knn算法将计算该点与所有训练样点之间的距离，并且挑选出距离最小的k个样点（此处k=4，根据实际需要自定义），那么黄色点的类别将通过图中连接的4个点来判断。很明显，这4个点均为红色类别，那么黄色点被推测为红色类别。

       同理，再看下图所示，此时这4个样本点包含了2个类别，针对这样的情况，knn算法通常采用投票法来进行类别推测，即找出k个样本点中类别出现次数最多的那个类别，因此黄色点的类型被推测为蓝色类别。

KNN算法的主要实现步骤：

1. 计算测试数据与各训练数据之间的距离。
2. 按照距离的大小进行排序。
3. 选择其中距离最小的k个样本点。
4. 确定K个样本点所在类别的出现频率。
5. 返回K个样本点中出现频率最高的类别作为最终的预测分类。

python代码实现 

import numpy as np
import operator


def 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)