最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • KNN最近邻算法

    KNN简介

    KNN(K-NearestNeighbor)是机器学习入门级的分类算法,非常简单。它实现将距离近的样本点划为同一类别;KNN中的K指的是近邻个数,也就是最近的K个点 ;根据它距离最近的K个点是什么类别来判断属于哪个类别。

    KNN算法步骤

    我们有一堆样本点,类别已知,如下图左,蓝色为一类,黄色为另一类。现在有个新样本点,也就是图中黑色的叉叉,需要判断它属于哪一类。

    KNN做的就是选出距离目标点黑叉叉距离最近的k个点,看这k个点的大多数颜色是什么颜色。这里的距离用欧氏距离来度量。

    给定两个样本 和 ,其中n表示特征数 ,X和Y两个向量间的欧氏距离(Euclidean Distance)表示为:

    当我们设定k=1时,距离目标点最近的点是黄色,就认为目标点属于黄色那类。当k设为3时,我们可以看到距离最近的三个点,有两个是蓝色,一个是黄色,因此认为目标点属于蓝色的一类。

    所以,K的选择不同,得到的结果也会不同。

    K值选择

    KNN的决策边界一般不是线性的,也就是说KNN是一种非线性分类器,如下图。

    K越小越容易过拟合,当K=1时,这时只根据单个近邻进行预测,如果离目标点最近的一个点是噪声,就会出错,此时模型复杂度高,稳健性低,决策边界崎岖

    但是如果K取的过大,这时与目标点较远的样本点也会对预测起作用,就会导致欠拟合,此时模型变得简单,决策边界变平滑

    寻找最合适的K值,比较经典的方法是N折交叉验证

    上图展示的是5折交叉验证,也就是将已知样本集等分为5份,其中4份作为训练集,1份为验证集,做出5个模型

    具体过程

    将样本数据按照一定比例,拆分出训练用的数据和验证用的数据,比如6:4拆分出部分训练数据和验证数据,从选取一个较小的K值开始,不断增加K的值,然后计算验证集合的方差,最终找到一个比较合适的K值。

    通过交叉验证计算方差后你大致会得到下面这样的图:

    由上图可知,当你增大k的时候,一般错误率会先降低,因为有周围更多的样本可以借鉴了,分类效果会变好。但注意,和K-means不一样,当K值更大的时候,错误率会更高。这也很好理解,比如说你一共就35个样本,当你K增大到30的时候,KNN基本上就没意义了。

    所以选择K点的时候可以选择一个较大的临界K点,当它继续增大或减小的时候,错误率都会上升,比如图中的K=10。

    PS:处理数据要先对其进行标准化;也可以采用标准差标准化

    KNN优缺点

    KNN的优点在于原理简单,容易实现,对于边界不规则数据的分类效果好于线性分类器。

    缺点:

    • 要保存全部数据集,需要大量的存储空间;
    • 需要计算每个未知点到全部已知点的距离,非常耗时;
    • 对于不平衡数据效果不好,需要进行改进;
    • 不适用于特征空间维度高的情况。

    代码实现

    伪代码

    具体实现

    https://github.com/GreedyAIAcademy/Machine-Learning/tree/master/2.KNN

    参考文章

    https://www.cnblogs.com/listenfwind/p/10311496.html

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » KNN最近邻算法

    发表评论

    • 52会员总数(位)
    • 320资源总数(个)
    • 25本周发布(个)
    • 3 今日发布(个)
    • 333稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情