美文网首页机器学习KNN
“k 近邻算法”综述

“k 近邻算法”综述

作者: 李威威 | 来源:发表于2018-11-18 14:39 被阅读1次

    “k 近邻算法”综述

    本来题目想叫“白话 k 近邻算法”,后来想想,“k 近邻算法” 的描述几乎就是“白话”,所以就不故弄玄虚了,接下来的就是一篇笔记呀。

    image

    图片来自周志华《机器学习》第 10 章第 1 节。

    想说一说“k 近邻算法”在机器学习中的地位

    “k 近邻算法” 可以说是最容易理解的机器学习算法,所以可以用“k 近邻算法”来作为入门机器学习算法的基本流程的最好材料,因为我们在理解算法上不须要花太多时间。

    下面简单说说,“k 近邻算法” 给我们带来了什么。

    • 超参数:k 就是一个超参数,这是我们得根据经验,在算法运行之前指定的;
    • 数据集分离:我们不能使用所有的样本训练数据,我们还要评估算法的性能,即使是同一个算法,不同的超参数还须要评估好坏,因此,必须从数据集中分离出一部分数据,进行算法好坏,超参数选择的验证;
    • 评估算法好坏的准则:k 近邻算法用于分类问题,一个最容易理解的评价指标就是准确率(或者错误率,因为错误率=1-准确率);
    • 交叉验证:交叉验证用于选择超参数,比起简单地那一部分数据作为测试数据集要靠谱,因为分离数据集带有一定随机性;
    • 网格搜索:其实就是暴力搜索,把我们认为可能合理的超参数和超参数的组合输入算法,而在其中评估算法好坏,超参数的选择也用到了交叉验证的过程;
    • 数据标准化:这一步是一开始学习机器学习算法的时候经常被忽略的,后面我们可以看到数据标准化在梯度下降中也发挥很大的作用;
    • 模型复杂度:理解下面这句话 k 的值越小,模型越复杂,k 的值越大,模型越简单,因为 k 如果和训练数据集一样大的话,其实我们每个预测数据都只能预测为一个类别,即训练数据集中数量最多的那个类别;
    • 决策边界:这是分类问题的一个重要且简单的概念。

    k 近邻算法的核心思想

    • 物以类聚,人以群分;
    • 未标记样本的类别由距离其最近的 k 个邻居投票来决定。

    k 近邻算法的三要素

    1、超参数:k

    2、距离的定义(例如:欧氏距离);

    3、决策的规则(例如:投票表决,或者加权投票)。

    算法执行的步骤:

    1、选择 k 和距离的度量;
    2、计算待标记的数据样本和数据集中每个样本的距离,取距离最近的 k 个样本。待标记的数据样本所属的类别,就由这 k 个距离最近的样本投票产生。

    理解 k 近邻算法的部分核心代码

    distances = [np.linalg.norm(point - X) for point in X_train]
    print("打印每个点距离待测点的距离:")
    for index, distance in enumerate(distances):
        print("[{}] {}".format(index, np.round(distance, 2)))
    
    sorted_index = np.argsort(distances)
    print(y_train[sorted_index])
    
    k = 6
    topK = y_train[sorted_index][:k]
    print(topK)
    
    from collections import Counter
    
    votes = Counter(topK)
    mc = votes.most_common(n=1)
    print(mc)
    print("根据投票得出的点 X 的标签为:", mc[0][0])
    

    k 近邻算法的训练过程,即是利用训练数据集,对特征向量空间进行划分

    李航《统计学习方法》P37

    说明:从这张图中,你可以看到决策边界。

    • k 近邻算法是一个懒惰学习的算法,没有显式的学习过程,即没有它没有训练的步骤,是一个基于记忆的学习算法;
    • “多数表决”规则等价于“经验风险最小化”(我们的算法在训练数据集上“风险”最小);
    • k 近邻算法的优化实现:kd 树,即是给训练数据建立树结构一样的索引,期望快速找到 k 个邻居,以防止线性扫描。

    k 近邻算法的应用领域

    文本分类、模式识别、聚类分析,多分类领域。

    要注意的地方

    • 使用距离作为度量时,要保证所有特征在数值上是一个数量级上,以免距离的计算被数量级大的特征所主导。例如《机器学习实战》提供的这个例子:
    image
    • <b><font size='3' color='ff0000'>在数据标准化这件事上,还要注意一点,训练数据集和测试数据集一定要使用同一标准的标准化,看下面的公式。</font></b>

    标准化的训练数据集 = \cfrac{原始训练数据集数据-训练数据集的平均值}{训练数据集的标准差}

    标准化的测试数据集 = \cfrac{原始训练测试集数据-训练数据集的平均值}{训练数据集的标准差}

    <b><font size='3' color='ff0000'>测试数据集在标准化的时候,一定也要使用“训练数据集的平均值”和“训练数据集的标准差”,而不能使用测试数据集的。</font></b>

    原因其实很简单:

    1、标准化其实可以视为算法的一部分,既然数据集都减去了一个数,然后除以一个数,这两个数对于所有的数据来说,就要一视同仁;
    2、训练数据集其实很少,在预测新样本的时候,新样本就更少得可怜,如果新样本就一个数据,它的均值就是它自己,标准差是 0 ,这根本就不合理。

    k 近邻算法的优点

    • k 近邻算法是一种在线技术,新数据可以直接加入数据集而不必进行重新训练;
    • k 近邻算法理论简单,容易实现;
    • 准确性高:对异常值和噪声有较高的容忍度;
    • k 近邻算法天生就支持多分类,区别与感知机、逻辑回归、SVM。

    k 近邻算法的缺点

    • 基本的 k 近邻算法每预测一个“点”的分类都会重新进行一次全局运算,对于样本容量大的数据集计算量比较大;

    • 维度灾难:在高维空间中计算距离的时候,就会变得非常远;

    • 样本不平衡时,预测偏差比较大,例如:某一类的样本比较少,而其它类样本比较多;

    • k 值大小的选择得依靠经验或者交叉验证得到。

    • k 的选择可以使用交叉验证,也可以使用网格搜索(其实是一件事情,网格搜索里面其实就是用的交叉验证);

    • k 的值越大,模型的偏差越大,对噪声数据越不敏感,当 k 的值很大的时候,可能造成模型欠拟合;k 的值越小,模型的方差就会越大,当 k 的值很小的时候,就会造成模型的过拟合。

    k 近邻算法说开

    • 增加邻居的权重,距离越近,权重越高,参数:weights;

    维基百科最近邻居法词条中是这样介绍的:

    无论是分类还是回归,衡量邻居的权重都非常有用,使较近邻居的权重比较远邻居的权重大。例如,一种常见的加权方案是给每个邻居权重赋值为 \cfrac{1}{d},其中 d 是到邻居的距离。

    • 使用一定半径内的点,当数据采样不均匀的时候,该算法可以取得更好的性能:from sklearn.neighbors import RadiusNeighborsClassifier

    • k 近邻算法还可以用于回归,找最近的邻居,计算它们的平均值就可以了。

    扩展

    参考资料

    • 李航《统计学习方法》第 3 章:k 近邻法
      说明:介绍 kd 树,并给出了例子。

    相关文章

      网友评论

        本文标题:“k 近邻算法”综述

        本文链接:https://www.haomeiwen.com/subject/tyvdgftx.html