K近邻分类的算法实现K近邻（KNN）法的输入为实例的特征向量，对应于特征空间的点；输入为实例的类别，可以取多类。

K近邻法假设给定一个训练数据集，其中的实例类别已定。

分类时，对新的实例，根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。

因此K近邻不具有显式的学习过程。

K近邻法实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

1.1 选题背景现如今，数据的爆炸式增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代。

急需功能强大和通用的工具，以便从这些海量数据中发现有价值的信息，把这些数据转化成有组织的知识。

这种需求导致了数据挖掘的诞生。

这个领域是年轻的、动态变化的、生机勃勃的。

数据挖掘已经并且将继续在我们从数据时代大步跨入信息时代的历程中作出贡献。

K近邻方法是20世纪50年代早期首次引进的。

当给定大量数据集时，该方法是计算密集的，直到20世纪60年代计算能力大大增强之后才流行起来。

此后它广泛用于模式识别领域。

K近邻分类法是基于类比学习，即通过将给定的检验元组与它相似的训练元组进行比较来学习。

训练元组用n个属性描述。

每个元组代表n维空间的一个点。

这样，所有的训练元组都存放在n维模式空间中。

当给定一个未知元组时，k近邻分类法搜索模式空间，找出最接近元组的k个训练元组。

这k个训练元组即为该元组的k个“最近邻”。

1.2 研究现状国内外学者为此算法在实际生活中更好地应用做出了许多努力。

例如对k近邻方法的不足做出的一些改进如文献[2]，[7]，[8]，[9]，[10]等等。

在其他领域的应用如文献[5]将K近邻算法改进为非线性分类算法，以达到分类动态心电图波形的目的。

文献[6]在KNN算法的基础上提出了图像自动分类模型。

在生物学上，K近邻方法也得到了广泛地应用，有文献利用蛋白质相互作用网络,提出了一种基于K 近邻的蛋白质功能的注释方法，该方法使得蛋白质的功能能够得到更有效的预测[4]。

还有很多其他领域的一些应用，显示了机器学习在21世纪越来越重要的作用。

本论文主要研究实现K 近邻分类算法，体会在如今大数据时代机器学习的意义，为今后进一步学习数据挖掘打下基础。

第二章 k 近邻模型和算法2.1 K 近邻模型K 近邻法使用的模型实际上对应于对特征空间的划分。

模型由三个基本要素—-距离度量、k 值得选择和分类规则决定。

2.1.1 模型K 近邻法中，当训练集、距离度量（如欧式距离）、k 值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。

这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所述的类。

这一事实从最近邻算法中可以看得很清楚。

特征空间中，对每个实例点i x,距离该点比其他店更近的所有点组成一个区域，叫做单元。

每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

最近邻法将实例i x 的类i y作为其单元中所有点的类标记。

这样，每个单元的实例点的类别时确定的。

下图是二维特征空间划分的一个例子。

2.1.2 距离度量特征空间中两个实例点的距离是两个点相似程度的反映。

K 近邻模型的特征空间一般是n 维实数向量空间Rn 。

使用的距离是欧式距离，但也可以是其他距离，如更一般的Lp 或闽科夫斯基距离。

设特征空间χ是n 维实数向量空间n R ，i x ，,),,,(,)()2()1(Tn i i i i j x x x x x =∈χ ,),,,()()2()1(T n j j j j x x x x =ji x x ,的距离定义为P Lpnl pl j li j i p x x x x L 11),(⎪⎭⎫ ⎝⎛-=∑=这里1≥p 。

当2=p 时，称为欧式距离，即21122,⎪⎭⎫⎝⎛-=∑=nl l jl i j i x x x x L ）（当时，称为曼哈顿距离，即∑=-=nl lj li j i x x x x L 11,）（1=p当∞=p 时，它是各个距离坐标的最大值，即l jl i lj i x x x x L -=∞max ),(2.1.3 K 值的选择k 值的选择会对k 近邻法的结果产生重大影响。

如果选择较小的k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。

但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。

如果近邻的实例点恰巧是噪声，预测就会出错。

换句话说，k 值得减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的k 值，就相当于用较大邻域中的训练实例进行预测。

其优点是可以减少学习的估计误差。

但缺点是学习的近似误差会增大。

这时与输入实例较远的（不相似的）训练实例也会对预测起作用，是预测发生错误。

K 值得增大就意味着整体的模型变得简单。

如果k=N ，那么无论输入实例是什么，都将简单的预测它属于在训练实例中最多的类。

这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。

2.1.4 分类决策规则K 近邻法中的分类决策规则往往是多数表决，即由输入实例的k 个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数为},,,{:21k n c c c R f →那么误分类的概率是))((1))((X f Y P X f Y P =-=≠对给定的实例χ∈x ，其最近邻的k 个训练实例点构成集合)(x N K 。

如果涵盖)(x N K 的区域的类别是jc 那么误分类概率是∑∑∈∈=-=≠)()()(11)(1x N x j i x N x j i K i K i c y I k c y I k要使误分类概率最小即经验风险最小，就要使∑∈=)()(x N x j iK i c yI 最大，所以多数表决规则等价于经验风险最小化。

2.2 K 近邻算法输入：训练数据集)},(,),,(),,{(2211N N y x y x y x T =其中，ni R x ⊆∈χ为实例的特征向量，},,{y 21k i c c c y =∈为实例的类别，i=1,2, ,N;实例特征向量x ； 输出：实例x 所属的类y 。

(1)根据给定的距离度量，在训练集T 中找出与x 最邻近的k 个点，涵盖这k 个点的x 邻域记作)(x N K ；(2)在)(x N K 中根据分类决策规则（如多数表决）决定x 的类别y ：Kj N i c yI x N x j ic k i j,,2,1;,2,1,)(maxarg y )( ====∑∈该式中，I 为指示函数，即当ji c y =时I 为1，否则I 为0。

当k 取1的特殊情况时，k 近邻算法即为最近邻算法。

对于输入的实例点或是特征向量x ，其分类由其最邻近的点的分类决定。

第三章数据模拟和实例分析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 onA3=rand(50,2)+1.5;plot(A3(:,1),A3(:,2),'.')再用k近邻分类算法对这150组数据进行分类，取k=15近邻，程序如下# 程序 2：clear allclcy=importdata('C:\Users\adm\Desktop\test.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));%保存每个向量与所有训练样本之间的距离end[d1 index1]=sort(distance);%对距离distance向量进行从小到大的排序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;endend[d2 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 =143 rate =0.9533图一模拟数据原始分类图2 K近邻方法得到的分类实验结果分析从图像和运行结果均可以看出，对上述模拟数据用取k=15的k近邻算法作出的分类正确率为95.33%，分类效果不错，符合预期。

改变k值，分别取k=1,5,10,15,20,30,40,60做测试，发现k取1的取值对分类结果没有明显的规律，当k=1时，即为最近邻的特殊情况，此时分类和原分类吻合，当k从1开始逐渐增大时，分类效果呈现起伏，这说明k值得选取对分类结果有一定的影响，程序执行如下表。

表2 Iris数据集分类效果K值正确率错误1 1 05 96% 4%10 94.67% 5.33%15 95.33% 4.67%20 96.67% 3.33%30 96% 4%40 95.33% 4.67%60 94.67% 5.33%3.2 实例分析本文选取了著名的Iris数据集，Iris数据集共150组，有四个特征，分别是花萼和花瓣的长度和宽度，类别也是三类，取k=20,对前文程序代码稍作修改如下。

# 程序 3：clear allclcy=importdata('C:\Users\adm\Desktop\test.txt');p=y(:,2:5);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));%保存每个向量与所有训练样本之间的距离end[d1 index1]=sort(distance);%对距离distance向量进行从小到大的排序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;endend[d2 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.9800图3 原始数据的分类图像图4 K近邻分类算法所得到的分类图像实验结果分析上述程序运行后的结果表明k取20时对Iris数据集具有较好的分类效果，从某种意义上说，k近邻算法对花的分类可以给出一定的借鉴意义。