knn算法简单易懂介绍(机器学习-KNNk-nearestneighbor)

1、什么是KNN

k近邻法(k-nearest neighbor, kNN)是一种基本分类与回归方法,其基本做法是:给定测试实例,基于某种距离度量找出训练集中与其最靠近的k个实例点,然后基于这k个最近邻的信息来进行预测。

通常,在分类任务中可使用“投票法”,即选择这k个实例中出现最多的标记类别作为预测结果;在回归任务中可使用“平均法”,即将这k个实例的实值输出标记的平均值作为预测结果;还可基于距离远近进行加权平均或加权投票,距离越近的实例权重越大。

k近邻法不具有显式的学习过程,事实上,它是懒惰学习(lazy learning)的著名代表,此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为零,待收到测试样本后再进行处理。

本文只讨论分类问题中的k近邻法,下一篇文章将会介绍KNN分类的实际案例。

knn算法简单易懂介绍(机器学习-KNNk-nearestneighbor)(1)

2、KNN的算思想

KNN(k-NearestNeighbor)又被称为近邻算法,它的核心思想是:物以类聚,人以群分

假设一个未知样本数据x需要归类,总共有ABC三个类别,那么离x距离最近的有k个邻居,这k个邻居里有k1个邻居属于A类,k2个邻居属于B类,k3个邻居属于C类,如果k1>k2>k3,那么x就属于A类,也就是说x的类别完全由邻居来推断出来。

所以我们可以总结出其算法步骤为:

  • 计算测试对象到训练集中每个对象的距离
  • 按照距离的远近排序
  • 选取与当前测试对象最近的k的训练对象,作为该测试对象的邻居
  • 统计这k个邻居的类别频率
  • k个邻居里频率最高的类别,即为测试对象的类别

我们可以简化为:找邻居 投票决定

3、KNN的优点与缺点

优点

  • 非常简单的分类算法没有之一,人性化,易于理解,易于实现
  • 适合处理多分类问题,比如推荐用户

缺点

  • 属于懒惰算法,时间复杂度较高,因为需要计算未知样本到所有已知样本的距离
  • 样本平衡度依赖高,当出现极端情况样本不平衡时,分类绝对会出现偏差
  • 可解释性差,无法给出类似决策树那样的规则
4、KNN的应用范围

由KNN的自身属性所决定的,基于现有类别计算距离投票选择,所以不能发现新的类别,但对于固定类别,KNN的简单易用的特性就完全的显示出来了,在某些分类上,比SVM,决策树等有着并不逊色的性能。在进行固定类别分类的时候,模型选择的时可以以KNN作为基础标准进行模型选择,说不定会有意外的惊喜。目前KNN应用比较成熟的方向主要有,内容的推荐,文本的识别等。

5、KNN参数详解

KNN算法在实际应用时,最主要的参数主要有三个:距离算法的选择、K值的选择、投票时的权重计算

5.1距离算法的选择

目前主流的距离计算的算法主要有以下几种:

  • 欧式距离:是应用最多的距离计算算法
  • 曼哈顿距离:应用相对较少,可在交叉验证中选择查看
  • 余弦距离:两个向量之间的夹角大小,主要用来计算文本相似性

knn算法简单易懂介绍(机器学习-KNNk-nearestneighbor)(2)

5.2K值的选择

K值指的是,在进行分类投票时,选择多少距离最小的类别进行投票,K值的大小会对分类器的结果产生直接的影响,这个可以通过交叉验证确定最佳K值。

5.3投票时的权重计算

k近邻默认的投票方法是分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类,决定输入实例的类。即在取出的K个分类中,出现最多的分类及分类的结果。

同时也可采用对K个临近的记录不同的距离进行加权,距离近的权重高,距离远的权重低来进行投票。常用的距离加权函数为高斯函数。

knn算法简单易懂介绍(机器学习-KNNk-nearestneighbor)(3)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页