kNN算法及其示例
- 格式：docx
- 大小：97.62 KB
- 文档页数：8
1
KNN算法及其示例
一、KNN算法概述
KNN可以说是最简单的分类算法之一，同时，它也是最常用的分类算法之一，注意KNN算法是有监督学习中的分类算法，它看起来和另一个机器学习算法Kmeans有点像（Kmeans是无监督学习算法），但却是有本质区别的。那么什么是KNN算法呢，接下来我们就来介绍介绍吧。
二、KNN算法介绍
KNN的全称是K Nearest Neighbors，意思是K个最近的邻居，从这个名字我们就能看出一些KNN算法的蛛丝马迹了。K个最近邻居，毫无疑问，K的取值肯定是至关重要的。那么最近的邻居又是怎么回事呢？其实啊，KNN的原理就是当预测一个新的值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。听起来有点绕，还是看看图吧。
图中绿色的点就是我们要预测的那个点，假设K=3。那么KNN算法就会找到与它距离最近的三个点（这里用圆圈把它圈起来2
了），看看哪种类别多一些，比如这个例子中是蓝色三角形多一些，新来的绿色点就归类到蓝三角了。
但是，当K=5的时候，判定就变成不一样了。这次变成红圆多一些，所以新来的绿点被归类成红圆。从这个例子中，我们就能看得出K的取值是很重要的。
明白了大概原理后，我们就来说一说细节的东西吧，主要有两个，K值的选取和点距离的计算。
2.1距离计算
要度量空间中点距离的话，有好几种度量方式，比如常见的曼哈顿距离计算，欧式距离计算等等。不过通常KNN算法中使用的是欧式距离，这里只是简单说一下，拿二维平面为例，，二维空间两个点的欧式距离计算公式如下：
ρ=√(𝑥2−𝑥1)2+(𝑦2−𝑦1)2
这个高中应该就有接触到的了，其实就是计算（x1,y1）和（x2,y2）的距离。拓展到多维空间，则公式变成这样：
𝑑(𝑥,𝑦)=√(𝑥1−𝑦1)2+(𝑥2−𝑦2)2+⋯+(𝑥𝑛−𝑦𝑛)2
这样我们就明白了如何计算距离，KNN算法最简单粗暴的就3
是将预测点与所有点距离进行计算，然后保存并排序，选出前面K个值看看哪些类别比较多。但其实也可以通过一些数据结构来辅助，比如最大堆，这里就不多做介绍，有兴趣可以百度最大堆相关数据结构的知识。
2.2 K值选择
通过上面那张图我们知道K的取值比较重要，那么该如何确定K取多少值好呢？答案是通过交叉验证（将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如6：4拆分出部分训练数据和验证数据），从选取一个较小的K值开始，不断增加K的值，然后计算验证集合的方差，最终找到一个比较合适的K值。
通过交叉验证计算方差后你大致会得到下面这样的图：
这个图其实很好理解，当你增大k的时候，一般错误率会先降低，因为有周围更多的样本可以借鉴了，分类效果会变好。但注意，当K值更大的时候，错误率会更高。这也很好理解，比如说你一共就35个样本，当你K增大到30的时候，KNN基本上就4
没意义了。
所以选择K点的时候可以选择一个较大的临界K点，当它继续增大或减小的时候，错误率都会上升，比如图中的K=10。
以Iris数据集为例。Iris数据集主要包含了鸢尾花的花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性（特征），以及鸢尾花卉属于Setosa，Versicolour，Virginica三个种类中的哪一类。
在使用KNN算法之前，我们要先决定K的值是多少，要选出最优的K值，可以使用交叉验证方法，我们可以得到下面这样的图：
有了这张图，我们就能明显看出K值取多少的时候误差最小，这里明显是K=11最好。当然在实际问题中，如果数据集比较大，那为减少训练时间，K的取值范围可以缩小。
2.3 KD树
实现k近邻法时，主要考虑的问题是如何对训练数据进5
行快速k近邻搜索，这点在特征空间的维数大以及训练数据容量大时尤其重要。k近邻法的最简单实现是线性扫描，这时要计算输入实例与每一个训练实例的距离，当训练集很大时，计算非常耗时，这种方法是不可行的。为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。具体方法有很多，这里常用的有kd树方法。
kd树是一种对k维空间中的实例点进行存储以便对其进行快速搜索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间进行切分，构成一系列的k维超矩形区域。kd树的每一个节点对应于一个k维超矩形区域。k-d树是一个二叉树，每个节点表示一个空间范围。
三、KNN算法的特点
KNN是一种非参的，惰性的算法模型。什么是非参，什么是惰性呢？
非参的意思并不是说这个算法不需要参数，而是意味着这个模型不会对数据做出任何的假设，与之相对的是线性回归（我们总会假设线性回归是一条直线）。也就是说KNN建立的模型结构是根据数据来决定的，这也比较符合现实的情况，毕竟在现实中的情况往往与理论上的假设是不相符的。
惰性又是什么意思呢？想想看，同样是分类算法，逻辑回归需要先对数据进行大量训练（tranning），最后才会得到一个算法6
模型。而KNN算法却不需要，它没有明确的训练数据的过程，或者说这个过程很快。
3.1 KNN算法优点
1.简单易用，相比其他算法，KNN算是比较简洁明了的算法。即使没有很高的数学基础也能搞清楚它的原理。
2.模型训练时间快，上面说到KNN算法是惰性的，这里也就不再过多讲述。
3.预测效果好。
4.对异常值不敏感
3.2 KNN算法缺点
1.对内存要求较高，因为该算法存储了所有训练数据
2.预测阶段可能很慢
3.对不相关的功能和数据规模敏感
简单得说，当需要使用分类算法，且数据比较大的时候就可以尝试使用KNN算法进行分类了。
四、KNN算法示例
假设你是某视频网站的程序员，要判断一部新上映电影《唐人街探案》到底是动作片、爱情片还是喜剧片，这时候已经知道这三种类别的电影的特征。我们都知道动作片无非是打斗多一点，而爱情片最常出现的场景就是拥抱，喜剧片应该有大量的搞笑镜头，那么我们可以统计一下这些电影中打斗次数、拥抱次数和搞笑次数。 7
序号 电影名称 搞笑
镜头 拥抱
镜头 打头
镜头 电影
类型 距离 K=5时
1 功夫熊猫 39 0 31 喜剧片 21.47 √
2 叶问3 3 2 64 动作片 51.09
3 伦敦陷落 2 3 55 动作片 43.42
4 代理情人 9 38 2 爱情片 40.57
5 新步步惊心 8 34 17 爱情片 34.44 √
6 谍影重重 5 2 57 动作片 43.87
7 功夫熊猫 39 0 31 喜剧片 21.47 √
8 美人鱼 21 17 5 喜剧片 18.55 √
9 宝贝当家 45 2 9 喜剧片 23.43 √
10 唐人街探案 23 3 17 ?
我们来计算一下《唐人街探案》这部电影与其他影片的距离。例如，《唐人街探案》与《功夫熊猫》的距离为：
D=√(39−23)2+(0−3)2+(31−17)2=21.47
同理，可以计算出《唐人街探案》与其他影片的距离。如上表所示。当k=5时，距离最小的五部影片中，有4部是喜剧片，有1部是爱情片，所以我们判断，《唐人街探案》是一部喜剧片。
五、软件实现：
Weka的IBk函数实现了上面的算法。IBk还允许用户从多种距离加权方法里进行选择，并且提供了一个选项以借助交叉验证来自动确定k值。
以Iris为例。我们使用IB1算法来分类Iris数据集，IB1是指IBk算法中的k=1的情况。分类的结果非常好。
第二个例子使用Ionosphere数据集。运用IB1算法，在原始数据集上得到了86.3%准确率，而仅用前9个属性的情8
况下却得到了89.4%的准确率。再进一步，利用交叉验证选择2－最近邻（k=2）的分类器可以获得90.8%的精度。
