K近邻分类的算法实现

1、K近邻分类的算法实现K近邻（KNN ）法的输入为实例的特征向量，对应于特征空间的点；输入 为实例的类别，可以取多类。K近邻法假设给定一个训练数据集，其中的实例类 别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数 表决等方式进行预测。因此K近邻不具有显式的学习过程。K近邻法实际上是利 用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。1.1选题背景现如今，数据的爆炸式增长、广泛可用和巨大数量使得我们的时代成为 真正的数据时代。急需功能强大和通用的工具，以便从这些海量数据中发现有价 值的信息，把这些数据转化成有组织的知识。这种需求导致了数据挖掘的诞生。 这个领域是年

2、轻的、动态变化的、生机勃勃的。数据挖掘已经并且将继续在我们 从数据时代大步跨入信息时代的历程中作出贡献。K近邻方法是20世纪50年代早期首次引进的。当给定大量数据集时， 该方法是计算密集的，直到20世纪60年代计算能力大大增强之后才流行起来。 此后它广泛用于模式识别领域。K近邻分类法是基于类比学习，即通过将给定的检验元组与它相似的训练元 组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点。 这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，k近 邻分类法搜索模式空间，找出最接近元组的k个训练元组。这k个训练元组即为 该元组的k个“最近邻”。1.2研究现状国内

3、外学者为此算法在实际生活中更好地应用做出了许多努力。例如对k近 邻方法的不足做出的一些改进如文献2，7，8，9，10等等。在其他领 域的应用如文献5将K近邻算法改进为非线性分类算法，以达到分类动态心电 图波形的目的。文献6在KNN算法的基础上提出了图像自动分类模型。在生物 学上，K近邻方法也得到了广泛地应用，有文献利用蛋白质相互作用网络，提出 了一种基于K近邻的蛋白质功能的注释方法，该方法使得蛋白质的功能能够得到 更有效的预测4。还有很多其他领域的一些应用，显示了机器学习在21世纪越 来越重要的作用。本论文主要研究实现K近邻分类算法，体会在如今大数据时代机器学习的意 义，为今后进一步学习数据挖

4、掘打下基础。第二章k近邻模型和算法2.1 K近邻模型K近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素 一-距离度量、k值得选择和分类规则决定。2.1.1模型K近邻法中，当训练集、距离度量（如欧式距离）、k值及分类决策规则（如 多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。这相当 于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所述的 类。这一事实从最近邻算法中可以看得很清楚。特征空间中，对每个实例点土，距离该点比其他店更近的所有点组成一个区 域，叫做单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特 征空间的一个划分。最近邻法将实例

5、七的类作为其单元中所有点的类标记。这 样，每个单元的实例点的类别时确定的。下图是二维特征空间划分的一个例子。2.1.2距离度量特征空间中两个实例点的距离是两个点相似程度的反映。K近邻模型的特征 空间一般是n维实数向量空间Rn。使用的距离是欧式距离，但也可以是其他距 离，如更一般的Lp或闽科夫斯基距离。设特征空间穴是n维实数向量空间Rn，七，X f X = (X，X，一咋心，X = (x,X (2),X()T, x x的L距离定义为j j jj i j 的 PL (x ,x ) = XX，-xi p pP i j I j ) l=1/这里p 2 L当P = 2时，称为欧式距离，即X1 - x 1

6、, j 7Xl - X l当P二1时，称为曼哈顿距离，即L(x,x)=乎当P =8时，它是各个距离坐标的最大值，即L (x , x ) = max xi 一 xi8 i j l i J2.1.3 K值的选择k值的选择会对k近邻法的结果产生重大影响。如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学 习”的近似误差会减小，只有与输入实例较近的(相似的)训练实例才会对预测 结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点 非常敏感。如果近邻的实例点恰巧是噪声，预测就会出错。换句话说，k值得减 小就意味着整体模型变得复杂，容易发生过拟合。如果选择较大的k值，就相

7、当于用较大邻域中的训练实例进行预测。其优点 是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例 较远的(不相似的)训练实例也会对预测起作用，是预测发生错误。K值得增大 就意味着整体的模型变得简单。如果k=N，那么无论输入实例是什么，都将简单的预测它属于在训练实例中 最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可 取的。2.1.4分类决策规则K近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训 练实例中的多数类决定输入实例的类。多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数 为f : Rn c , c , , c 1

8、2 k那么误分类的概率是P(Y 力 f (X) = 1 - P(Y = f (X)对给定的实例x 5，其最近邻的k个训练实例点构成集合N (x)。如果涵盖nk (x)的区域的类别是C那么误分类概率是1 i (七。)=1 -1 i (七 *.)x eN (x)x eN (x)；i Ki K 7E i(, *)要使误分类概率最小即经验风险最小，就要使X 4 (x)最大，所以多数 表决规则等价于经验风险最小化。2.2 K近邻算法输入：训练数据集T = (x , y ),(x , y )，(x , y )1122N N甘击 x & x uR斗由店ng杜；工右且 y e y = c ,c，c 斗由的其中

9、，i 一为头1列的勺特征向量，i 12 k为头1列的勺类力别，i=1,2, . ,N;实例特征向量x； 输出：实例x所属的类y。根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这 k个点的x邻域记作Nk (x)；在Nk(x)中根据分类决策规则(如多数表决)决定x的类别y：y = arg max EI(y = c ), i = 1,2, . N; j = 1,2, . ., Kc jj Xj eNk (X)该式中，I为指示函数，即当yi =Cj时I为1，否则I为0。当k取1的特殊情况时，k近邻算法即为最近邻算法。对于输入的实例点或 是特征向量x，其分类由其最邻近的点的分类决定。第三章

10、数据模拟和实例分析3.1数据模拟用MATLAB随机生成150组数据，类别为三类，编程如下 #程序1：A1=rand(50,2);hold onplot(A1(:,1),A1(:,2),.)A2=rand(50,2)+0.75;hold onplot(A2(:,1),A2(:,2),.) hold on A3=rand(50,2)+1.5;plot(A3(:,1),A3(:,2),.)得到如图所示图像图1模拟数据在坐标系中的分布再用k近邻分类算法对这150组数据进行分类，取k=15近邻，程序如下#程序2：clear allclcy=importdata(C:UsersadmDesktoptest

11、.txt);p=y(:,2:3);P=P;Add=zeros(150,1);Add(1:50,:)=ones(50,1);Add(51:100,:)=2*ones(50,1);Add(101:150,:)=3*ones(50,1);figure (1) ,plot(y(:,1),Add,g.);hold ongrid on;count=0;for i=1:3for j=1:50for k=1:150distance(k)=mse(p(:,k)-p(:,(i-1)*50+j);% 保存每个向量与所有训 练样本之间的距离endd1 index1=sort(distance);%对距离distanc

12、e向量进行从小到大的排序 num=0 0 0;for m=1:20 % 考察num，存放的是排序后distance前20个属于每一 类别的个数if index1(m)=50num(1)=num(1)+1;elseif index1(m)=100num(2)=num(2)+1;elsenum(3)=num(3)+1;endendd2 class=max(num);%属于哪类的个数最多，就属于哪类，class即 就是该向量所属的类别if i=classcount=count+1;endA(i-1)*50+j)=class;%存放判断的结果endendcountrate=count/150figur

13、e(2),plot(y(:,1),A,r.);grid on;%画图分类程序运行后得到count =143 rate =0.9533图一模拟数据原始分类图2K近邻方法得到的分类实验结果分析从图像和运行结果均可以看出，对上述模拟数据用取k=15的k近邻算法作 出的分类正确率为95.33%，分类效果不错，符合预期。改变k值，分别取k=1,5,10,15,20,30,40,60做测试，发现k取1的取值对分 类结果没有明显的规律，当k=1时，即为最近邻的特殊情况，此时分类和原分类 吻合，当k从1开始逐渐增大时，分类效果呈现起伏，这说明k值得选取对分类 结果有一定的影响，程序执行如下表。表2 Iris数

14、据集分类效果K值正确率错误110596%4%1094.67%5.33%1595.33%4.67%2096.67%3.33%3096%4%4095.33%4.67%6094.67%5.33%3.2实例分析本文选取了著名的Iris数据集，Iris数据集共150组，有四个特征，分别是 花萼和花瓣的长度和宽度，类别也是三类，取k=20，对前文程序代码稍作修改如 下。#程序3：clear allclcy=importdata(C:UsersadmDesktoptest.txt);p=y(:,2:5);p=p;Add=zeros(150,1);Add(1:50,:)=ones(50,1);Add(51:1

15、00,:)=2*ones(50,1);Add(101:150,:)=3*ones(50,1);figure (1) ,plot(y(:,1),Add,g.);hold ongrid on;count=0;for i=1:3for j=1:50for k=1:150distance(k)=mse(p(:,k)-p(:,(i-1)*50+j);% 保存每个向量与所有训 练样本之间的距离endd1 index1=sort(distance);%对距离distance向量进行从小到大的排序 num=0 0 0;for m=1:20% 考察num，存放的是排序后distance前20个属于每一类别的个数

16、if index1(m)=50num(1)=num(1)+1;elseif index1(m)=100num(2)=num(2)+1;elsenum(3)=num(3)+1;endendd2 class=max(num);% 属于哪类的个数最多，就属于哪类，class即 就是该向量所属的类别if i=classcount=count+1;endA(i-1)*50+j)=class;%存放判断的结果endendcountrate=count/150figure(2),plot(y(:,1),A,r.)； grid on;%画图分类程序执行后得到以下结果： count =147 rate =0.9

17、800050100150图3原始数据的分类图像图4 K近邻分类算法所得到的分类图像实验结果分析上述程序运行后的结果表明k取20时对Iris数据集具有较好的分类效果， 从某种意义上说，k近邻算法对花的分类可以给出一定的借鉴意义。改变 k 值后，分别取 k=4,6,8,10,12,14,16，18,20,22,24,30 时，发现对于 Iris 数据集k取8-22之间的值最为合适，分类正确率稳定，当k小于8或是大于22 时，分类效果下降。执行程序得到的结果如下表。表2 分类正确率K值正确率错误率496%4%697.33%2.67%898%2%1098%2%1298%2%1498%2%1698%2%

18、1898%2%2098%2%2298%2%2497.33%2.67%3095.33%4.67%结语通过在MATLAB软件上编写和运行K近邻算法的过程中，我们了解到K近邻 法是有监督的学习方法，在分类阶段，k是一个用户定义的常数。一个没有类 别标签的向量（查询或测试点）将被归类为最接近该点的k个样本点中最频 繁使用的一类。该算法的优点是精度高、对异常值不敏感、无数据输入假定。然 而该方法由于其计算量较大，对每一个待分类的文本都要计算它到全体已知样本 的距离，才能求得它的K个最近邻点，在计算速度上有待改进，但也正因为如此 它只是适用于一些样本容量比较大的类域的自动分类，而那些样本容量较小的类 域采

19、用这种算法则容易产生误分k-近邻算法的另一个缺陷是它无法给出任何数 据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么 特征。附录Iris数据集包含150个样本，都属于鸢尾属下的三个亚属，分别是山鸢尾、变色 鸢尾和维吉尼亚鸢尾，有四个特征被用作样本的定量分析，它们第一列和第二列 是花萼的长度和宽度，第二列是花瓣的长度和宽度。K值花萼长花萼宽花瓣长花瓣宽类别15.13.51.40.2124.931.40.2134.73.21.30.2144.63.11.50.21553.61.40.2165.43.91.70.4174.63.41.40.31853.41.50.2194.42

20、.91.40.21104.93.11.50.11115.43.71.50.21124.83.41.60.21134.831.40.11144.331.10.11155.841.20.21495884763434542141212563453258382732213814165.74.175.43.185.13.195.73.205.13.215.43.225.13.234.63.245.13.254.83.2652753.285.23.295.23.304.73.314.83.325.43.335.24.345.54.354.93.3653.375.53.384.93.394.4405.13.

21、4153.424.52.434.43.4453.455.13.464.8475.13.484.63.495.33.5053.5173.526.43.536.93.545.52.556.52.第1.50.411.30.411.40.311.70.311.50.311.70.211.50.4110.211.70.511.90.211.60.211.60.411.50.211.40.211.60.211.60.211.50.411.50.111.40.211.50.211.20.211.30.211.40.111.30.211.50.211.30.311.30.311.30.211.60.611.9

22、0.411.40.311.60.211.40.211.50.211.40.214.71.424.51.524.91.5241.324.61.52834972329913725285893839644773413356363715565.72.576.33.584.92.596.62.605.22.615625.96362.646.12.655.62.666.73.675.6685.82.696.22.705.62.715.93.726.12.736.32.746.12.756.42.766.6776.82.786.77962.805.72.815.52.825.52.835.82.8462.8

23、55.48663.876.73.886.32.895.6905.52.915.52.926.1935.82.9452.955.62.第4.51.324.71.623.3124.61.323.91.423.5124.21.524124.71.423.61.324.41.424.51.524.1124.51.523.91.124.81.8241.324.91.524.71.224.31.324.41.424.81.4251.724.51.523.5123.81.123.7123.91.225.11.624.51.524.51.624.71.524.41.324.11.3241.324.41.224.61.4241.223.3124.21.3296979899100101102103104105106107108