最近邻法和k-近邻法汇总.docx

最近邻法和k-近邻法 最近邻法和k-近邻法 一.基本概念： 最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x 与距离它最近的样本同类 K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类K取奇数，为了是避免k1=k2的情况 二.问题分析： 要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类 可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2） 三.算法分析： 该算法中任取每类样本的一半作为训练样本，其余作为测试样本例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类测试10次，取10次分类正确率的平均值来检验算法的性能 四.MATLAB代码： 最近邻算实现对Iris分类 clc; totalsum=0; for ii=1:10 data=load('iris.txt'); data1=data(1:50,1:4);%任取Iris-setosa数据的25组 rbow1=randperm(50); trainsample1=data1(rbow1(:,1:25),1:4); rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列 testsample1=data1(rbow1(:,26:50),1:4); data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4); rbow2(:,26:50)=sort(rbow2(:,26:50)); testsample2=data2(rbow2(:,26:50),1:4); data3=data(101:150,1:4);%任取Iris-virginica数据的25组 rbow3=randperm(50); trainsample3=data3(rbow3(:,1:25),1:4); rbow3(:,26:50)=sort(rbow3(:,26:50)); testsample3=data3(rbow3(:,26:50),1:4); trainsample=cat(1,trainsample1,trainsample2,trainsample3);%包含75组数据的样本集testsample=cat(1,testsample1,testsample2,testsample3); newchar=zeros(1,75);sum=0; [i,j]=size(trainsample);%i=60,j=4 [u,v]=size(testsample);%u=90,v=4 for x=1:u for y=1:i result=sqrt((testsample(x,1)-trainsample(y,1))^2+(testsample(x,2)-trainsample(y,2))^2+(testsampl e(x,3)-trainsample(y,3))^2+(testsample(x,4)-trainsample(y,4))^2); %欧式距离 newchar(1,y)=result; end; [new,Ind]=sort(newchar); class1=0; class2=0; class3=0; if Ind(1,1)25&&Ind(1,1)class2&&class1>class3 m=1; ty='Iris-setosa'; elseif class2>class1&&class2>class3 m=2; ty='Iris-versicolor'; elseif class3>class1&&class3>class2 m=3; ty='Iris-virginica'; else m=0; ty='none'; end if x0 disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),ty)); elseif x25&&x0 disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),ty)); elseif x>25&&x50&&x0 disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),ty)); elseif x>50&&x30&&Ind(1,n)= class 2&& class1>= class3 m=1; elseif class2>= class1&& class2>= class3 m=2; elseif class3>= class1&& class3>= class2 m=3; end if x29&&x65&&x<=89 disp(sprintf('第%d组数据分类后为第%d类',130+rbow3(:,x-41),m)); end if (x29&&x65&&x<=89&&m==3) sum=sum+1; end end disp(sprintf('第%d次分类识别率为%4.2f',ii,sum/89)); totalsum=totalsum+(sum/89); end disp(sprintf('10次分类平均识别率为%4.2f',totalsum/10)); 第2组数据分类后为第1类 第4组数据分类后为第1类 第5组数据分类后为第3类 第6组数据分类后为第1类 第8组数据分类后为第1类 第10组数据分类后为第1类 第11组数据分类后为第1类 第14组数据分类后为第1类 第19组数据分类后为第1类第20组数据分类后为第3类第21组数据分类后为第3类第22组数据分类后为第3类第26组数据分类后为第3类第27组数据分类后为第1类第28组数据分类后为第1类第30组数据分类后为第1类第33组数据分类后为第1类第36组数据分类后为第1类第37组数据分类后为第1类第43组数据分类后为第1类第44组数据分类后为第3类第45组数据分类后为第1类第46组数据分类后为第1类第49组数据分类后为第1类第52组数据分类后为第1类第54组数据分类后为第1类第56组数据分类后为第1类第57组数据分类后为第1类第60组数据分类后为第2类第61组数据分类后为第3类第63组数据分类后为第3类第65组数据分类后为第2类第66组数据分类后为第3类第67组数据分类后为第2类第71组数据分类后为第1类第72组数据分类后为第2类第74组数据分类后为第1类第76组数据分类后为第2类第77组数据分类后为第2类第79组数据分类后为第3类第81组数据分类后为第2类第82组数据分类后为第3类第83组数据分类后为第3类第84组数据分类后为第2类第86组数据分类后为第2类第87组数据分类后为第2类第88组数据分类后为第2类第93组数据分类后为第2类第96组数据分类后为第1类第98组数据分类后为第2类第99组数据分类后为第3类 第104组数据分类后为第2类第105组数据分类后为第3类第106组数据分类后为第2类第110组数据分类后为第3类第113组数据分类后为第3类第114组数据分类后为第2类第115组数据分类后为第2类第116组数据分类后为第2类第118组数据分类后为第2类第122组数据分类后为第2类第123组数据分类后为第2类第124组数据分类后为第2类第133组数据分类后为第3类第134组数据分类后为第3类第135组数据分类后为第2类第136组数据分类后为第3类第139组数据分类后为第3类第140组数据分类后为第3类第142组数据分类后为第3类第144组数据分类后为第2类第145组数据分类后为第1类第146组数据分类后为第3类第148组数据分类后为第3类第149组数据分类后为第2类第152组数据分类后为第2类第157组数据分类后为第2类第159组数据分类后为第3类第161组数据分类后为第2类第162组数据分类后为第3类第163组数据分类后为第3类第164组数据分类后为第3类第165组数据分类后为第3类第167组数据分类后为第3类第168组数据分类后为第3类第173组数据分类后为第3类第174组数据分类后为第3类 五：问题和收获： 该算法的优缺点总结为： 优点：算法简单且识别率较高； 缺点：算法需要计算未知样本x与周围每个样本的距离，然后排序选择最近的k个近邻，计算量和时间复杂度高。

书本上有好多优化的k近邻法，比如，快速搜索近邻法、剪切近邻法、压缩近邻法等，但就个人能力而言，上述优化的算法不太容易编程实现在日后的学习中，自己也要加强优化算法的能力。