机器学习算法总结K近邻.docx

机器学习算法总结K近邻.docx

《机器学习算法总结K近邻.docx》由会员分享，可在线阅读，更多相关《机器学习算法总结K近邻.docx（18页珍藏版）》请在冰点文库上搜索。

机器学习算法总结K近邻

第一章k近邻

1.1K近邻简介

k近邻（k-NearestNeighbor，k-NN）是一种基本的、有监督学习的分类方法，于1968年由Cover和Hart提出，其用于判断某个对象的类别。

k近邻的输入为对象特征向量，对应于特征空间上的点；输出为对象的类别。

k近邻算法实例引入：

图1.1k近邻实例

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所示的数据则是待分类的数据。

也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：

给这个绿色的圆分类。

所谓物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手。

要判别上图中那个绿色的圆是属于哪一类数据，只需根据它周围的邻居即可。

但一次性看多少个邻居呢？

从上图中，你还能看到：

如果k=3，绿色圆点的最近的3个邻居（欧式距离）是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

上面这个小例子基本上体现了k近邻算法的三个基本要素：

确定度量方式（欧式距离）、选着k值（2or3）、分类决策规则（少数服从多数）。

下面，给出k近邻算法的数学表述：

输入：

训练数据集

其中，

为实例的特征向量，

为实例的类别，

;实例特征向量

;

输出：

实例

所属的类。

（1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作

；

（2）在

中根据分类决策规则（如多数表决）决定x的类别y：

（1-1）

其中，

为指示函数，即当

时

为1,否则

为0。

k近邻的特殊情况是k=1的情形，称为最近邻算法，对于输入的对象（特征向量）x，最近邻法将训练数据集中于x最近邻点所属的类作为x的类。

1.2K近邻模型建立

建立数学模型的过程实质就是确定三个基本要素的过程。

1.2.1距离度量方式的确定

样本空间（特征空间）中两个对象的距离是它们相似程度的量化反映。

k近邻模型的特征空间可被抽象为n维的向量空间R，现在两个对象之间的距离就可转化为两个向量之间的距离，这样研究起来就方便多了。

在k近邻模型中，计算向量之间距离的公式列举如下：

（1）欧式距离：

（1-2）

（2）曼哈顿距离：

（1-3）

（3）切比雪夫距离：

（1-4）

（4）闵可夫斯基距离：

（1-5）

特点：

为综合性的公式。

（5）马氏距离：

　　（1-6）

特点：

可排除对象间的相关性。

（6）相关距离：

（1-7）

（7）夹角余弦距离和Tonimoto系数：

（I）夹角余弦距离：

（1-8）

（II）Tonimoto系数（夹角余弦的改进）：

（1-9）

下面给出计算欧式距离的C/C++代码：

//计算欧氏距离

doubleeuclideanDistance（constvector&v1,constvector&v2）

{

assert（v1.size（）==v2.size（））;

doubleret=0.0;

for（vector:

:

size_typei=0;i!

=v1.size（）;++i）

{

ret+=（v1[i]-v2[i]）*（v1[i]-v2[i]）;

}

returnsqrt（ret）;

}

1.2.2K值的选择

选择较小的K值，近似误差会减小，估计误差会增大，意味着整体模型变得复杂，容易发生过拟合；

选择较大的K值，减少估计误差，近似误差会增大，K值的增大就意味着整体的模型变得简单。

 在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（一部分样本做训练集，一部分做测试集）来选择最优的K值。

1.2.3分类决策规则

（1）多数表决

k近邻法中的分类决策规则往往是多数表决，即由输入对象的k个邻近中的多数类决定输入对象的类，通俗点就是“少数服从多数”。

（2）误分类率

误分类率即对输入对象出现错误分类的概率。

其数学表示如下：

对给定的实例

，其最近邻的k个训练实例点构成集合

.如果涵盖

的区域的类别是

，那么误分类率是

（1-10）

要使误分类率最小即经验风险最小，就要使

最大，所以多数表决规则等价于经验风险最小化.

1.3k近邻算法的实现

在实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻捜索。

k近邻法最简单的实现方法是线性扫描法（linearscan）。

即计算输入对象与每一个训练对象之间的距离，然而当训练集很大时，计算非常耗时，这种方法是不可行的.

为了提高k近邻搜索的效率，我们可以构建数据的索引（因为实际数据一般都会呈现簇状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配）。

索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。

根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。

前者划分空间没有重叠，其代表就是kd树；后者划分空间相互有交叠，其代表为R树。

下面主要介绍其中的kd树（kdtree）方法。

1.3.1kd树的构建

该方法来自斯坦福大学的JonLouisBentley在ACM杂志上发表的一篇论文：

Multidi-mensionalBinarySearchTreesUsedforAssociativeSearching，这篇论文中正式提出kd树，并阐述的了kd树的构建等（此时的k与kNN中的k含义是不同的）。

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

kd树是二叉树，表示对k维空间的一个划分（partition）。

构造k树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。

kd树的每个结点对应于一个k维超矩形区域。

构造kd树的方法如下：

构造根结点，使根结点对应于k维空间中包含所有对象点的超矩形区域；通过下面的递归方法，不断地对k维空间进行切分，生成子结点。

在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面经过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）：

这时，对象被分到两个子区域。

重复这个过程直到子区域内没有对象时终止（终止时的结点为叶结点）。

在此过程中，将所有对象保存在相应的结点上。

对于三维的情形，kd树对空间的划分，如下图所示：

图1.2三维kd树

通常，依次选择坐标轴对空间切分，选择训练对象点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。

在确定坐标轴时，选着当前方差最大的效果较好，因为此时区分度最大。

注意，平衡的树搜索时的效率未必是最优的。

下面给出构造以树的算法（见图1.3）：

算法1.1（构造平衡kd树）

输入：

k维空间数据集

，

其中

输出：

kd树。

（1）开始：

构造根结点，根结点对应于包含T的k维空间的超矩形区域.

选择

为坐标轴，以T中所有实例的坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域.切分由通过切分点并与坐标轴

垂直的超平面实现.

由根结点生成深度为1的左、右子结点：

左子结点对应坐标

小于切分点的子区域，右子结点对应于坐标

大于切分点的子区域.

将落在切分超平面上的对象点保存在根结点.

（2）重复：

对深度为j的结点，选择

为切分的坐标轴，

，以该结点的区域中所有实例的

坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域.切分由通过切分点井与坐标轴

垂直的超平面实现.

由该结点生成深度为j+1的左、右子结点：

左子结点对应坐标

小于切分点的子区域，右子结点对应坐标

大于切分点的子区域.

将落在切分超平面上的对象点保存在该结点.

（3）直到两个子区域没有实例存在时停止.从而形成kd树的区域划分.

例1.1给定一个二维空间的数据集：

T={（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}

构造一个平衡kd树.

解：

根结点对应包含数据集T的矩形，选择轴，6个数据点的坐标的中位数是7,以平面将空间分为左、右两个子矩形（子结点）；接着，左矩形以分为两个子矩形，右矩形以分为两个子矩形，如此递归，最后得到如图3.3所示的特征空间划分和如图3.4所示的kd树。

图1.3构造平衡kd树算法

图1.4特征空间划分图1.5kd树示例

1.3.2kd树的最近邻搜索算法：

（1）基本思想：

给定一个目标点，搜索其最近邻。

首先找到包含目标点的叶结点；然后从该叶节点出发，依次回退到父结点，当确定不可能存在更近的结点时终止；

包含目标点的叶结点对应包含目标点的最小超矩形区域，以此点的实例点作为当前最近点，目标点的最近邻一定在以目标点为中心并通过最近点的超球体的内部。

然后返回当前结点的父结点，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。

如果存在这样的点，将此点作为新的当前最近点，算法转到更上一级的父结点，继续上述过程。

如果父结点的另一子结点的超矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。

详细的最近邻搜索算法如下：

算法1.2（见图1.6）：

输入：

已构造的kd树；目标点x；

输出：

x的最近邻。

（1）在kd树中找出包含目标点x的叶结点：

从根结点出发，递归地向下访问kd树。

若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点.直到子结点为叶结点为止。

（2）以此叶结点为“当前最近点”。

（3）递归地向上回退，在每个结点进行以下操作：

（a）如果该结点保存的实例点（即当前父节点）比当前最近点距离目标点更近，则以该实例点为“当前最近点”。

（b）检查该子结点的父结点的另一子结点对应的区域是否有更近的点。

具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。

如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，作为当前父节点。

接着，递归地进行最近邻搜索，递归到叶子结点为止（从上到下）；

如果不相交，向上回退，退回到上上层父节点。

（4）当回退到根结点时，搜索结束。

最后的“当前最近点”即为x的最近邻点。

注意：

上面这种方式只是一种近似计算方法，因为它只考虑了kd树的一边（左或右子树），而没有遍历另一边。

该算法的时间复杂度是

，其中N是训练实例数。

树更适用于训练实例数远大于空间维数时的k近邻搜索。

当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

图1.6查找K近邻算法

例1.2给定一个如图所示的kd树，根结点为A，其子结点为B，C等，树上共存储7个实例点；另有一个输入目标实例点S，求S的最近邻。

图1.7通过kd树搜索示意图图1.8生成的kd树

解：

首先在kd树中找到包含点S的叶结点D（图中的右下区域），以点D作为近似最近邻。

真正最近邻一定在以点S为中心通过点D的圆的内部。

然后返回结点D的父结点B，在结点B的另一子结点F的区域内搜索最近邻。

结点F的区域与圆不相交，不可能有最近邻点.继续返回上一级父结点A，在结点A的另一子结点C的区域内搜索最近邻。

结点C的区域与圆相交;；该区域在圆内的实例点有点E，点E比点D更近，成为新的最近邻。

最后得到点E是点S的最近邻。

1.4应用实战

1.4.1python基本介绍

python安装

1.python不向下兼容，最好安装python2.7；

2.两个第三方库：

NumPy,Matplotlib。

注意：

在安装Matplotlib时，需要按装三个插件：

dateutil，pyparsing和six，其中six安装要在cmd中，执行安装命令，如下图：

图1.9安装six插件

python入门介绍及需注意的问题

1.在编译运行时，注意把原来编译的pyc删除掉；注意对修改后的py文件保存后，在编译；有的时候甚至要关掉python2.7.5shell才能运行。

2.在python中注释汉字时，要在首行加入#coding=utf-s；因为它为非ASCII码。

3.python是动态类型的语言，不需要声明变量类型。

（python2.7版）

4.python中没有大括号，利用代码段的缩进对齐表达代码的逻辑，所以多一个空格少一个空格，影响可能会很大。

5.range（）：

integer型数据；len（）：

可为任意数据；for循环的初始值默认为0；

6.python中定义的函数的参数都是“引用类型”；

1.4.2k近邻算法的python实现

代码如下：

defclassify0（inX,dataSet,labels,k）:

dataSetSize=dataSet.shape[0]

diffMat=tile（inX,（dataSetSize,1））-dataSet

sqDiffMat=diffMat**2

sqDistances=sqDiffMat.sum（axis=1）

distances=sqDistances**0.5

sortedDistIndicies=distances.argsort（）

classCount={}

foriinrange（k）:

voteIlabel=labels[sortedDistIndicies[i]]

classCount[voteIlabel]=classCount.get（voteIlabel,0）+1

sortedClassCount=sorted（classCount.iteritems（）,key=operator.itemgetter

（1）,reverse=True）

returnsortedClassCount[0][0]

说明：

1.实现的是线性扫描法的k近邻算法，没有涉及kd树的构建和基于kd树的最近邻搜索。

2.inX是输入向量（目标点），dataset是训练样本集，labels是标签（实例类别），k是选择最近邻的数目。

1.4.3示例1：

改进约会网站配对效果

实现步骤

a.将txt文件数据转换为NumPy可处理的数据；

b.分析数据特点，利用Matplotlib作图

c.数据归一化，映射到[0,1]；

d.编写分类器，并利用测试样本测试错误率；

e.得到预测函数，作为实际应用。

关键代码分析

a.将txt文件数据转换为NumPy可处理的数据

deffile2matrix（filename）:

fr=open（filename）

numberOfLines=len（fr.readlines（））#getthenumberoflinesinthefile

returnMat=zeros（（numberOfLines,3））#preparematrixtoreturn

classLabelVector=[]#preparelabelsreturn

fr=open（filename）

index=0

forlineinfr.readlines（）:

line=line.strip（）

listFromLine=line.split（'\t'）

returnMat[index,:

]=listFromLine[0:

3]

classLabelVector.append（int（listFromLine[-1]））

index+=1

returnreturnMat,classLabelVector

b.分析数据特点，利用Matplotlib作图；

fromnumpyimport*

importkNN

importmatplotlib

importmatplotlib.pyplotasplt

fig=plt.figure（）

ax=fig.add_subplot（111）

datingDataMat,datingLabels=kNN.file2matrix（'datingTestSet2.txt'）

#ax.scatter（datingDataMat[:

1],datingDataMat[:

2]）

#ax.scatter（datingDataMat[:

1],

datingDataMat[:

2],15.0*array（datingLabels）,15.0*array（datingLabels））

ax.scatter（datingDataMat[:

0],datingDataMat[:

1],15.0*array（datingLabels）,15.0*array（datingLabels））

#ax.axis（[-2,25,-0.2,2.0]）

#ax.axis（[-2,100000,-0.2,25]）

ax.legend（'Did','Small','Large'）

plt.xlabel（'PercentageofTimeSpentPlayingVideoGames'）

plt.ylabel（'LitersofIceCreamConsumedPerWeek'）

plt.show（）

运行结果展示

部分运行结果如下：

图1.10带有样本分类标签的约会数据散点图

图1.11利用分类器处理约会数据集的运行结果

1.4.4示例2：

手写识别系统

实现步骤

1.图像转换为NumPy可处理的样本向量

2.利用分类器识别手写数字

*此步因数据量较大，1934个训练数据,946个测试数据，为了节省时间，将训练数据改为了20个，测试数据给为了10个（但此时错误率较高）

关键代码分析

将图像数据转换为NumPy可处理的样本向量：

defimg2vector（filename）:

returnVect=zeros（（1,1024））

fr=open（filename）

foriinrange（32）:

lineStr=fr.readline（）

forjinrange（32）:

returnVect[0,32*i+j]=int（lineStr[j]）

returnreturnVect