机器学习算法总结_K近邻

1、第一章k近邻1.1 K近邻简介k近邻（k-Nearest Neighbor , k-NN ）是一种基本的、有监督学习的分类方法，于 1968 年由Cover和Hart提出，其用于判断某个对象的类别。k近邻的输入为对象特征向量，对 应于特征空间上的点；输出为对象的类别。k近邻算法实例引入：图1.1 k近邻实例如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示， 而图正中间的那个绿色的圆所示的数据则是待分类的数据。也就是说，现在，我们不知道中 间那个绿色的数据是从属于哪一类（蓝色小正方形 or红色小三角形），下面，我们就要解决 这个问题：给这个绿色的圆分类。所谓物以类聚，人

2、以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手。要判别上图中那个绿色的圆是属于哪一类数据，只需根据它周围的邻 居即可。但一次性看多少个邻居呢？从上图中，你还能看到：如果k=3，绿色圆点的最近的3个邻居（欧式距离）是2个红色小三角形和1个蓝色 小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形 一类。如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是 少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。上面这个小例子基本上体现了 k近邻算法的三个基本要素：确定度量方式（欧式距离）、选着k值

3、（2 or 3 ）、分类决策规则（少数服从多数）下面，给出k近邻算法的数学表述：输入：训练数据集T 二（ xi, yj,区亿），川，（xn，y”）其中，xiRn为实例的特征向量，yic1）c2JH，ck为实例的类别，i =1,2，hi,n；实例特征向量x;输出：实例x所属的类。（1）根据给定的距离度量，在训练集 T中找出与x最邻近的k个点，涵盖这k个点的x的 邻域记作Nk（x）；（2 ）在Nk（x）中根据分类决策规则（如多数表决）决定 x的类别y:y 二 arg max |（ yj 二 5 ）, i 二 1,2,川，N； j = 1,2, |卄，K（ 1-1）Cj xi ENk（x）其中，I为

4、指示函数，即当 y - cj时I为1,否则I为0。k近邻的特殊情况是k=1的情形，称为最近邻算法，对于输入的对象（特征向量）x，最近邻法将训练数据集中于x最近邻点所属的类作为x的类。1.2 K近邻模型建立建立数学模型的过程实质就是确定三个基本要素的过程。1.2.1距离度量方式的确定样本空间（特征空间）中两个对象的距离是它们相似程度的量化反映。k近邻模型的特征空间可被抽象为n维的向量空间R，现在两个对象之间的距离就可转化为两个向量之间 的距离，这样研究起来就方便多了。在k近邻模型中，计算向量之间距离的公式列举如下：（1） 欧式距离：d（X ,Y）以 - y2（ 1-2）n（2） 曼哈顿距离：d（

5、X,Y）八”区-丫门（1-3）(3 )切比雪夫距离:闵可夫斯基距离：d (X ,Y) = (a |Xi - yi |p) p 特点：为综合性的公式。(5)马氏距离:d(X, Y) = (X - Y八 (X Y)特点：可排除对象间的相关性。(6)相关距离：DXy = 1 - ;Y(7 )夹角余弦距离和Tonimoto系数:(I)夹角余弦距离:s(X,Y)二X YXY(1-4)(1-5)(1-6)(1-7)(1-8)(II) Tonimoto系数(夹角余弦的改进):T(X,Y)(1-9)-X Y下面给出计算欧式距离的C/C+代码：/计算欧氏距离double euclidea nDista nce(

6、c onst vector& v1, const vector& v2)assert(v1.size() = v2.size();double ret = 0.0;for (vector:size_type i = 0; i != v1.size(); +i)ret += (v1i - v2i) * (v1i - v2i);return sqrt(ret);1.2.2 K值的选择选择较小的K值，近似误差会减小，估计误差会增大，意味着整体模型变得复杂，容易发生过拟合；选择较大的K值，减少估计误差，近似误差会增大，K值的增大就意味着整体的模型变得简单。在实际应用中，K值一般取一个比较小的数值，例如

7、采用交叉验证法(一部分样本做训练集，一部分做测试集)来选择最优的 K值1.2.3分类决策规则(1 )多数表决k近邻法中的分类决策规则往往是 多数表决，即由输入对象的k个邻近中的多数类决定 输入对象的类，通俗点就是“少数服从多数”。(2 )误分类率误分类率即对输入对象出现错误分类的概率。其数学表示如下：对给定的实例X，其最近邻的k个训练实例点构成集合Nk(x).如果涵盖Nk(x)的区域 的类别是C，那么误分类率是1 1 |卽=q) = iI (yi - c)( 1-10)K X -Nk(x)K Xi :二Nk(x)要使误分类率最小即经验风险最小，就要使I(yi二Cj )最大，所以多数表决规则Xj

8、 mk(x)等价于经验风险最小化.1.3 k近邻算法的实现在实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻捜索。k近邻法最简单的实现方法是线性扫描法(linear scan)。即计算输入对象与每一个训练 对象之间的距离，然而当训练集很大时，计算非常耗时，这种方法是不可行的为了提高k近邻搜索的效率，我们可以构建数据的索引(因为实际数据一般都会呈现簇 状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配)。索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为 Clipping和Overlapping两种。前者划分空间没有重叠，其代表就

9、是kd树；后者划分空间相互有交叠，其代表为R树。下面主要介绍其中的kd树(kd tree)方法。1.3.1 kd树的构建该方法来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文：Multidimensional Bi nary Search Trees Used for Associative Search ing，这篇论文中正式提出 kd树，并阐述的了 kd树的构建等（此时的k与kNN中的k含义是不同的）。kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形 数据结构。 kd树是二叉树，表示对k维空间的一个划分（partition）。构造k树相当于不

10、断地用垂直于 坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于 一个k维超矩形区域。构造kd树的方法如下：构造根结点，使根结点对应于 k维空间中包含所有对象点的超 矩形区域；通过下面的递归方法，不断地对 k维空间进行切分，生成子结 点。在超矩形区 域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面 经过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结 点）：这时，对象被分到两个子区域。重复这个过程直到子区域内没有对象时终止（终止时 的结点为叶结点）。在此过程中，将所有对象保存在相应的结点上。对于三维的情形

11、，kd树对空间的划分，如下图所示：图1.2三维kd树通常，依次选择坐标轴对空间切分，选择训练对象点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。在确定坐标轴时，选着当前方差最大的效果较好，因为此 时区分度最大。注意，平衡的树搜索时的效率未必是最优的。下面给出构造以树的算法（见图1.3）:算法1.1 （构造平衡kd树）输入：k维空间数据集T二xX2，川，Xn,其中 Xi 二(x(1),x(2) JH，x(k)T, i 二 1,2, III, N;输出：kd树。(1) 开始：构造根结点，根结点对应于包含T的k维空间的超矩形区域.选择X为坐标轴，以T中所有实例的坐标的中位数为切分点，将根

12、结点对应的超矩形区 域切分为两个子区域切分由通过切分点并与坐标轴X垂直的超平面实现.由根结点生成深度为1的左、右子结点：左子结点对应坐标 X小于切分点的子区域，右 子结点对应于坐标X大于切分点的子区域将落在切分超平面上的对象点保存在根结点(2) 重复：对深度为j的结点，选择x(l)为切分的坐标轴，I j (mod k) 1，以该结点 的区域中所有实例的x(l)坐标的中位数为切分点，将该结点对应的超 矩形区域切分为两个子 区域.切分由通过切分点井与坐标轴x(l)垂直的超平面实现.由该结点生成深度为j+ 1的左、右子结点：左子结点对应坐标 X(l)小于切分点的子区域， 右子结点对应坐标X(l)大于

13、切分点的子区域将落在切分超平面上的对象点保存在该结点(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,7）1*.直】）1化3)图1.4特征空间划分图1.5 kd

14、树示例1.3.2 kd树的最近邻搜索算法: （1 ）基本思想：给定一个目标点，搜索其最近邻。首先找到包含目标点的叶结点；然后从该叶节点 出发，依次回退到父结点，当确定不可能存在更近的结点时终止；包含目标点的叶结点对应包含目标点的最小超矩形区域，以此点的实例点作为当前最 近点，目标点的最近邻一定在以目标点为中心并通过最近点的超球体的内部。然后返回当前 结点的父结点，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交的区域内 寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点，算法转到更 上一级的父结点，继续上述过程。如果父结点的另一子结点的超矩形区域与超球体不相交， 或

15、不存在比当前最近点更近的点，则停止搜索。详细的最近邻搜索算法如下：算法1.2 (见图 1.6)：输入：已构造的 kd 树；目标点 x；输出： x 的最近邻。(1)在 kd 树中找出包含目标点 x 的叶结点：从根结点出发，递归地向下访问 kd 树。若目标点x当前维的坐标小于切分点的坐标，贝能动到左子结点，否则移动到右子结点.直到子结点为叶结点为止。(2) 以此叶结点为“当前最近点” 。(3) 递归地向上回退，在每个结点进行以下操作：(a) 如果该结点保存的实例点(即 当前父节点 )比当前最近点距离目标点更近，则以该实例点为“当前最近点” 。(b) 检查该子结点的父结点的另一子结点对应的区域是否有

16、更近的点。具体 地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点” 间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距 目标点更近的点，移动到另一个子结点，作为 当前父节点 。接着，递归地进行最近邻 搜索，递归到叶子结点为止(从上到下) ； 如果不相交，向上回退，退回到 上上层父节点 。(4) 当回退到根结点时，搜索结束。最后的“当前最近点”即为x 的最近邻点。注意：上面这种方式只是一种 近似计算方法 ，因为它只考虑了 kd 树的一边(左或右子树)，而没有遍历另一边。该算法的时间复杂度是Olog N)，其中N是训练实例数。树更适用于训练实例数远大

17、于空间维数时的 k 近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。图1.6查找K近邻算法例1.2给定一个如图所示的kd树，根结点为A，其子结点为B, C等，树上共存储7个实例点；另有一个输入目标实例点 S，求S的最近邻A J/II ff fIF ) D ) i G ) ( Ef/I,fl/图1.8生成的kd树解：首先在kd树中找到包含点S的叶结点D(图中的右下区域)，以点D作为近似最近 邻。真正最近邻一定在以点 S为中心通过点D的圆的内部。然后返回结点 D的父结点B， 在结点B的另一子结点F的区域内搜索最近邻。结点F的区域 与圆不相交，不可能有最近 邻点.继续返回

18、上一级父结点A，在结点A的另一子结 点C的区域内搜索最近邻。结点 C的 区域与圆相交；该区域在圆内的实例点有点 E，点E比点D更近，成为新的最近邻。最后 得到点E是点S的最近邻。1.4应用实战1.4.1 python基本介绍python安装1. python不向下兼容，最好安装python 2.7 ；2. 两个第三方库：NumPy,Matplotlib。注意：在安装 Matplotlib时，需要按装三个插件：dateutil， pyparsing和six，其中six安装要在cmd 中,执行安装命令，如下图：图1.9安装six插件python入门介绍及需注意的问题1. 在编译运行时，注意把原来编

19、译的pyc删除掉；注意对修改后的py文件保存后，在编译；有的时候甚至要关掉python 2.7.5 shell才能运行。2. 在python中注释汉字时，要在首行加入# coding=utf-s ;因为它为非 ASCII码。3. python是动态类型的语言，不需要声明变量类型。(python 2.7版)4. python中没有大括号，利用代码段的缩进对齐表达代码的逻辑，所以多一个空格少一个空格，影响可能会很大。5. range(): integer型数据；len()：可为任意数据；for循环的初始值默认为 0;6. python中定义的函数的参数都是“引用类型”；1.4.2 k近邻算法的py

20、thon实现代码如下：def classify0(i nX, dataSet, labels, k):dataSetSize = dataSet.shape0diffMat = tile(inX, (dataSetSize,1) - dataSetsqDiffMat = diffMat*2sqDista nces = sqDifMat.sum(axis=1)dista nces = sqDista nces*0.5sortedDist In dicies = dista nces.argsort()classCo un t=for i in ran ge(k):voteIlabel = lab

21、elssortedDistI ndiciesiclassCo un tvotellabel = classCo un t.get(votellabel,0) + 1 sortedClassCo unt = sorted(classCo un t.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCou nt00说明：1. 实现的是 线性扫描法的k近邻算法，没有涉及kd树的构建和基于kd树的最近邻搜索。2. inX是输入向量(目标点)，dataset是训练样本集，labels是标签(实例类别)，k是选

22、择最近邻的数 目。1.4.3示例1:改进约会网站配对效果实现步骤a.将txt文件数据转换为 NumPy可处理的数据;b. 分析数据特点，利用Matplotlib 作图c. 数据归一化，映射到0,1;d. 编写分类器，并利用测试样本测试错误率；e.得到预测函数，作为实际应用。关键代码分析a将txt文件数据转换为 NumPy可处理的数据def file2matrix(filename): fr = open(filename) numberOfLines = len(fr.readlines() #get the number of lines in the file returnMat = ze

23、ros(numberOfLines,3) #prepare matrix to return classLabelVector = #prepare labels returnfr = open(filename) index = 0 for line in fr.readlines(): line = line.strip() listFromLine = line.split(t) returnMatindex,: = listFromLine0:3 classLabelVector.append(int(listFromLine-1) index += 1return returnMat

24、,classLabelVectorb.分析数据特点，利用Matplotlib作图；15.0*array(datingLabels),from numpy import * import kNN import matplotlib import matplotlib.pyplot as plt fig = plt.figure() ax = fig.add_subplot(111) datingDataMat,datingLabels = kNN.file2matrix(datingTestSet2.txt) #ax.scatter(datingDataMat:,1, datingDataMat

25、:,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)#ax.axis(-2,25,-0.2,2.0) #ax.axis(-2,100000,-0.2,25) ax.legend(Did,Small,Large) plt.xlabel(Percentage of Time Spent Playing Vid

26、eo Games) plt.ylabel(Liters of Ice Cream Consumed Per Week) plt.show()运行结果展示部分运行结果如下：00200004000G6000G30000Percentage erf Time Spent Haying Video (janws5土aMMud poEnlrlLJo7 3=|一10000G图1.10带有样本分类标签的约会数据散点图elMJiner mEH backWlEh)with itht tbetKi reilnrwranClBIJlfactC-ttM11cltfiirxftr宦4Mwl 耳 H ic.he1nrw*x9cbt*1X1therrt 14mvviCMbuckVltfeT3rrealanrMvridl9checlassir&erback肌therealJlI9thecla3 3.f ierc-Kcebaiclctereal