目录

前提

核心原理

代码

算法改进

前提

我们前面讲感知机模型的时候，是建立在数据集是线性可分的且只需要分两类的基础上的。但现实中大部分的数据集都是线性不可分的而且类别也不止两类。那我们该怎么分类呢。这个时候我们就可以用K邻近模型。

要学习K邻近模型我们要先来了解一下几个距离。

1	欧氏距离（Euclidean Distance）		平面 / 空间中两点间的 “直线距离”，最符合日常对 “距离” 的直观认知
2	曼哈顿距离（Manhattan Distance）		像在城市网格中走路，只能沿坐标轴方向移动，距离是 “各维度差值的绝对值之和”
3	切比雪夫距离（Chebyshev Distance）		两点在 “各维度上差值最大的那个维度” 的距离（可理解为 “最远距离维度决定总距离”）

以上三种距离都属于闵可夫斯基距离(Minkowski distance)

取1或2时的闵氏距离是最为常用的=2即为欧氏距离，=1时则为曼哈顿距离。 当。  取无穷时的极限情况下，可以得到切比雪夫距离。在我们上一节感知机算法中提到的距离是欧式距离，在这一节中k邻近算法我们的距离也是欧式距离。

上一节感知机算法是根据线性可分的数据集来划分超平面然后对待预测的样本在哪个区域进行分类，而在在k邻近算法中我们通过待预测样本周围最近的k个训练样本的类别，来判断该样本的类别。核心思想是“物以类聚，人以群分”。

核心原理

第一步，确定一种距离度量（这里我们用的欧氏距离），计算待预测样本与所有训练样本之间的距离。

第二步，将所有距离按从小到大排序，选取距离最近的前k个训练样本。

第三部，对k个样本的类别进行排序，出现次数最多的类别即为待预测样本的类别。

代码

def classify0(inX, dataSet, labels, k):
    """
    K近邻(KNN)算法

    参数:
        inX (array-like): 需要进行分类预测的输入样本向量，与训练集特征维度一致
        dataSet (numpy.ndarray): 训练数据集，二维数组，每行代表一个样本，每列代表一个特征
        labels (array-like): 训练数据集对应的标签列表，长度与训练样本数量一致
        k (int): 选取的近邻样本数量，必须为正整数

    返回:
        any: 输入样本inX的预测类别，与labels中的元素类型一致
    """
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

算法改进

看了核心原理是不是觉得k邻近算法很简单，但是该算法有很多要注意的地方，比如k值的选择，若k值选的太小了，那么将会出现过拟合现象；k值选大了就偏离了算法的“邻近”思想，预测会偏向数据集中的多数类，也就是我们的欠拟合现象。

同时我们发现如果数据集相当大，那我们第一步中计算所有训练样本与待预测样本之间的距离的计算量会非常大，算法运行速度慢。我们可以用一些方法来提升算法速度，比如kd树等方法。