KNN算法

KNN算法

If you can dream it, you can do it.

K最近邻(kNN,k-NearestNeighbor)分类算法

我们的目的是要预测某个学生在数学课上的成绩。。。 
先来说明几个基本概念:图中每个点代表一个样本(在这里是指一个学生),横纵坐标代表了特征(到课率,作业质量),不同的形状代表了类别(即:红色代表A(优秀),绿色代表D(不及格))。

我们现在看(10,20)这个点,它就代表着:在数学课上,某个学生到课率是10%,交作业质量是20分,最终导致了他期末考试得了D等级(不佳)。同理,这6个点也就代表了6个往届学生的平时状态和最终成绩,称之为训练样本。。。。

现在要来实现我们的预测目的了,想象一下现在一学期快过完了,张三同学马上要考试了,他想知道自己能考的怎么样,他在数学老师那里查到了自己的到课率85%,作业质量是90,那么怎么实现预测呢?

张三可以看做是(85,90)这个点–也被称之为测试样本,首先,我们计算张三到其他6位同学(训练样本)的距离,点到点的距离相信我们初中就学了吧(一般用的欧氏距离)。

再选取前K个最近的距离,例如我们选择k=3,那么我们就找出距离最近的三个样本分别属于哪个类别,此例中,自然三个都是A等,所以可预测出张三的数学期末成绩可能是A等(优秀)。倘若李四现在也想进行预测,据他较近的3个中两个D,一个A,那么李四的数学期末成绩被预测为D。这也就是最开始所说的:在前k个样本中选择频率最高的类别作为预测类别。。。

总结其计算步骤如下:

好了,经过上诉过程,你是否对KNN算法基本思想有了一定了解。

原理就说到这吧。。。2  K-近邻的优缺点

KNN算法的优点:

1)简单、有效。 

2)重新训练的代价较低(类别体系的变化和训练集的变化,在Web环境和电子商务应用中是很常见的)。 

3)计算时间和空间线性于训练集的规模(在一些场合不算太大)。 

4)由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。 

5)该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。

KNN算法缺点:

1)KNN算法是懒散学习方法(lazy learning,基本上不学习),一些积极学习的算法要快很多。 

2)类别评分不是规格化的(不像概率评分)。 

3)输出的可解释性不强,例如决策树的可解释性较强。 

4)该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。

该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。 

5)计算量较大。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。

代码实现步骤:

KNN基本思想:物以类聚,人以群分

首先提取新数据的特征并与原数据集中的每一个数据特征进行比较;然后从数据集中提取K个最邻近(最相似)的数据特征标签,统计这K个最邻近数据中出现次数最多的分类,将其作为新的数据类别。

在KNN学习中,首先计算待分类数据特征与训练数据特征之间的距离并排序,取出距离最近的K个训练数据特征;然后根据这K个相近训练数据特征所属类别来判定新样本类别:如果它们都属于一类,那么新的样本也属于这个类;否则,对每个候选类别进行评分,按照某种规则确定新的样本的类别。笔者借用下面这个图来做更形象的解释:

  • 看离圆形最近(K=1)的那个类型是什么,由图可知,离圆形最近的是三角形,故将新数据判定为属于三角形这个类别。
  • 看离圆形最近的3个数据(K=3)的类型是什么,由图可知离圆形最近的三个中间有两个是矩形,一个是三角形,故将新数据判定为属于矩形这个类别。
  • 看离圆形最近的9个数据(K=9)的类型是什么,由图可知离圆形最近的9个数据中间,有五个是三角形,四个是矩形,故新数据判定为属于三角形这个类别。

上面所说的三种情况也可以说成是1-近邻方法、3-近邻方法、9-近邻方法。当然,K还可以取更大的值,当样本足够多,且样本类别的分布足够好的话,那么K值越大,划分的类别就越正确。而KNN中的K表示的就是划分数据时,所取相似样本的个数。

我们都知道,当K=1时,其抗干扰能力就较差,因为假如样本中出现了某种偶然的类别,那么新的数据很有可能被分错。为了增加分类的可靠性,可以考察待测数据的K个最近邻样本 ,统计这K个近邻样本中属于哪一类别的样本最多,就将样本X判属于该类。

当然,如果在样本有限的情况下,KNN算法的误判概率和距离的具体测度方法就有了直接关系。即用何种方式判定哪些数据与新数据近邻。不同的样本选择不同的距离测量函数,这能够提高分类的正确率。通常情况下,KNN可以采用Euclidean(欧几里得)、Manhattan(曼哈顿)、Mahalanobis(马氏距离)等距离用于计算。

KNN的不足

1、加入某些类别的样本容量很大,而其他类样本容量很小,即已知的样本数量不均衡,有可能当输入一个和小容量类相同的的新样本时,该样本的K个近邻中,大容量类的样本占多数,从而导致误分类。
针对此种情况可以采用加权的方法,即和该样本距离小的近邻所对应的权值越大,将权值纳入分类的参考依据。

2、分类时需要先计算待分类样本和全体已知样本的距离,才能求得所需的K近邻点,计算量较大,尤其是样本数量较多时。
针对这种情况可以事先对已知样本点进行剪辑,去除对分类作用不大的样本,这一处理步骤仅适用于样本容量较大的情况,如果在原始样本数量较少时采用这种处理,反而会增加误分类的概率。

改进的KNN算法

KNN学习容易受噪声影响,尤其是样本中的孤立点对分类或回归处理有很大的影响。因此通常也对已知样本进行滤波和筛选,去除对分类有干扰的样本。

K值得选取也会影响分类结果,因此需根据每类样本的数目和分散程度选取合理的K值,并且对不同的应用也要考虑K值得选择。

基于组合分类器的KNN改进算法

常用的组合分类器方法有投票法、非投票法、动态法和静态法等,比如简单的投票法中所有的基分类器对分类采取相同的权值;权值投票法中每个基分类器具有相关的动态权重,该权重可以随时间变化。

首先随机选择属性子集,构建多个K近邻分类器;然后对未分类元组进行分类;最后把分类器的分类结果按照投票法进行组合,将得票最多的分类器作为最终组合近邻分类器的输出。

基于核映射的KNN改进算法

将原空间Rn中的样本x映射到一个高维的核空间F中,突出不同类别样本之间的特征差异出,使得样本在核空间中变得线性可分或者近似线性可分,其流程如下所示:

KNN算法描述:

就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

1)计算测试数据与各个训练数据之间的距离;

2)按照距离的递增关系进行排序;

3)选取距离最小的K个点;

4)确定前K个点所在类别的出现频率;

5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

一个简单的KNN分类的MATLAB实践代码:
main.m文件

KNN文件

Eucdist.m文件

一些问题:

  1. 距离或相似度的衡量
    什么是合适的距离衡量?距离越近应该意味着这两个点属于一个分类的可能性越大。
    觉的距离衡量包括欧式距离、夹角余弦等。
    对于文本分类来说,使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。
  2. 类别的判定
    投票决定:少数服从多数,近邻中哪个类别的点最多就分为该类。
    加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大(权重为距离平方的倒数)
  3. 优点
    简单,易于理解,易于实现,无需估计参数,无需训练
    适合对稀有事件进行分类(例如当流失率很低时,比如低于0.5%,构造流失预测模型)
    特别适合于多分类问题(multi-modal,对象具有多个类别标签),例如根据基因特征来判断其功能分类,kNN比SVM的表现要好
  4. 缺点
    懒惰算法,对测试样本分类时的计算量大,内存开销大,评分慢
    可解释性较差,无法给出决策树那样的规则。
  5. 常见问题
    1、k值设定为多大?
    k太小,分类结果易受噪声点影响;k太大,近邻中又可能包含太多的其它类别的点。(对距离加权,可以降低k值设定的影响)
    k值通常是采用交叉检验来确定(以k=1为基准)
    经验规则:k一般低于训练样本数的平方根 2、类别如何判定最合适?
    投票法没有考虑近邻的距离的远近,距离更近的近邻也许更应该决定最终的分类,所以加权投票法更恰当一些。 3、如何选择合适的距离衡量?
    高维度对距离衡量的影响:众所周知当变量数越多,欧式距离的区分能力就越差。
    变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。 4、训练样本是否要一视同仁?
    在训练集中,有些样本可能是更值得依赖的。
    可以给不同的样本施加不同的权重,加强依赖样本的权重,降低不可信赖样本的影响。 5、性能问题?
    kNN是一种懒惰算法,平时不好好学习,考试(对测试样本分类)时才临阵磨枪(临时去找k个近邻)。
    懒惰的后果:构造模型很简单,但在对测试样本分类地的系统开销大,因为要扫描全部训练样本并计算距离。
    已经有一些方法提高计算的效率,例如压缩训练样本量等。 6、能否大幅减少训练样本量,同时又保持分类精度?
    浓缩技术(condensing)
    编辑技术(editing)

作者:五秋木
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 若有侵权行为,请及时留言删除。

Comments ( 20 )

  1. Replytjmc
    。。。。。
  2. Reply小鹿乱撞
    这篇文章不错。看的很明白,继续加油(ง •̀_•́)ง
  3. Reply纯种猪
    。。。。。
  4. Replycmy123
    嘿嘿(º﹃º )
  5. Replyjsz
    哈哈(ಡωಡ)hiahiahia,可以呀,加油学习
    1+
    1+
    • ReplyFdf
      你是🐷吗
  6. Replylzp
    加油😊,好好学习
  7. Replylsd
    。。。。。。
    • Reply小白哒
      嘿嘿嘿
      • Replylsd180
        what⁉️
  8. Replymsg
    简单的算法你搞得一套一套的,我写的肯定比你好

Leave a reply

Your email address will not be published.

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>