k-近邻算法的原理和步骤

化学心情下 浏览:68 0

什么是k-近邻

k-近邻(K-Nearest Neighbor)是机器学习中常用的一种监督学习算法,可以用于回归和分类任务。它的工作机制非常简单:给定测试样本,基于某种距离度量找出训练集中与其最近的k个训练样本,然后通过这k个训练样本进行预测。在分类任务中可以使用“投票法”(选择这k个样本中出现最多的类别标记作为预测结果);在回归任务中可以使用“平均法”(选择这k个样本的实值得平均值作为预测结果);还可以基于距离远近进行加权平均或加权投票,距离越近的样本权重越大。

k-近邻用于分类

k-近邻算法的原理和步骤

如图所示,正方形和三角形是已知的样本数据,绿色的圆圈是待分类的样本数据;当k=3时,将以1:2的投票结果分类于红色;而k=5时,将以3:2的投票结果分类于蓝色。

k-近邻分类算法的计算过程

  1. 计算待分类点与已知类别的点之间的距离
  2. 按照距离递增次序排序
  3. 选取与待分类点距离最小的k个点
  4. 确定前k个点所在类别的出现次数
  5. 返回前k个点出现次数最高的类别作为待分类点的预测分类

k-近邻用于回归

k-近邻算法的原理和步骤

如图,x轴是一个特征,y是该特征得到的值,红色点是已知点,要预测第一个点的位置,则计算离它最近的三个点的平均值,得出第一个绿色点,依次类推,就得到了绿色的线。

 k值的选择

由于KNN算法中几乎所有的计算都发生在分类阶段,而且分类效果很大程度上依赖于k值的选取,k值的选择很重要。k值选择过小,得到的近邻数过少,会降低分类精度,体现不出来分类的特点,同时也会放大噪声数据的干扰,而如果k值选择过大,并且待分类样本属于训练集中包含数据数较少的类,那么在选择k个近邻的时候,实际上并不相似的数据亦被包含进来,造成噪声增加而导致分类效果的降低。经验规则告诉我们:k一般低于训练样本数的平方根。

距离选择

高维度对距离衡量的影响:众所周知当变量数越多,欧式距离的区分能力就越差。变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。比较常用的是选用欧式距离,但是还是需要根据实际情况选择最佳的度量方法。

算法优缺点

优点

  1. 易于实现,无需估计参数,无需训练
  2. 分类模型简单有效
  3. 特别适合于多分类问题

缺点

  1. 分类速度慢。
  2. 属性等同权重影响了准确率。
  3. 样本库容量依懒性较强。
  4. K值的确定

参考资料

  1. 黄娟娟. 基于KNN的文本分类特征选择与分类算法的研究与改进[D]. 厦门大学, 2014.
  2. 闭小梅, 闭瑞华. KNN算法综述[J]. 科技创新导报, 2009(14):31-31.

发表评论 取消回复
表情 图片 链接 代码

分享