k-近邻算法（KNN）原理与代码实现_python的k近邻分析是什么距离

作者：羊村懒王 | 2024-06-11 12:09:03

踩

python的k近邻分析是什么距离

1. 概述

k-近邻算法（k-Nearest Neighbor，KNN）是一种比较常用的机器学习分类算法，在进行有标签的分类任务表现还不错，一般采用的分类方式为： 测量不同特征值之间的距离方法进行分类，因此没有显式的训练过程。

距离度量一般采用 Lp 距离，当p=1时，即为曼哈顿距离，也称城市街区距离（1范数）；

$L_{1} (x_{i},x_{j})= \left ( \sum_{l=1}^{n} \left | x_{i}^{(l)}-x_{j}^{(l)} \right |\right )$

当p=2时，即为欧氏距离（2范数），为两点间的距离；

$L_{2} (x_{i},x_{j})= \left ( \sum_{l=1}^{n} \left | x_{i}^{(l)}-x_{j}^{(l)} \right |^{2}\right )^{\frac{1}{2}}$

大于2的时，即为切比雪夫距离，也称棋盘距离。

$L_{\infty }(x_{i},x_{j})=\left ( \sum_{l=1}^{n} \left | x_{i}^{(l)}-x_{j}^{(l)} \right |^{p}\right )^{\frac{1}{p}}$

在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

其中，k-近邻算法的K 值的选择会对算法的结果产生重大影响：

（1） K值较小，就相当于用较小的邻域中的训练实例进行预测，学习的近似误差会减小，只有与输入实例较近的训练实例才会起到预测作用，但是估计的误差会增大，预测的结果对近邻的实例点非常敏感，若紧邻点恰好是噪声点，则预测结果将可能发生更多的错误，并且较小的k值意味着整体的模型变得更加复杂，因此更容易出现过拟合的现象；

（2）如果 K 值较大（意味着整体的模型较为简单），优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。

在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。

2. 实现案例

在一般的案例中，具体实现步骤可以描述为：

(1) 计算已知类别数据集中的点与当前点之间的距离；

(2) 按照距离递增次序排序；

(3) 选取与当前点距离最小的k个点；

(4) 确定前k个点所在类别的出现频率；

(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

另附python实现的KNN算法算法代码：


def classify_KNN(test_X, train_set, labels, K):
    rows = train_set.shape[0]
    diff = tile(test_X, (rows, 1)) - train_set
    # 这一行利用tile函数将输入样本实例转化为与训练集同尺寸的矩阵
    # 便之后的矩阵减法运算
    
    sqDistance = (diff ** 2).sum(axis=1)  
    Distance = sqDistance ** 0.5
    sorted_Distance = Distance.argsort()
    # 对每个训练样本与输入的测试样本求欧几里得距离，即点之间的范数
    # 随后按距离由小到大进行排序
    
    classCount = {}
    for i in range(K):
        vote_label = labels[sorted_Distance[i]]
        classCount[vote_label] = classCount.get(vote_label, 0) + 1
    #记录距离最小的前K个类，并存放入列表。KEY对应标签，VALUE对应计数
    
    sortedClassCount = sorted(classCount.items(), 
                              key = operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】