模式识别-最近邻法及k近邻法MATLAB实现.doc

最近邻法和k-近邻法
学号：02105120 姓名：吴林
一.基本概念：
最近邻法：对于未知样本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=data101: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+(testsample(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
class1=class1+1;
elseif Ind(1,1)>25&&Ind(1,1)<=50
class2=class2+1;
else
class3=class3+1;
end
if class1>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 x<=25&&m>0
disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),ty));
elseif x<=25&&m==0
disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),'none'));
end
if x>25&&x<=50&&m>0
disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),ty));
elseif x>25&&x<=50&&m==0
disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),'none'));
end
if x>50&&x<75&&m>0
disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),ty));
elseif x>50&&x<=75&&m==0
disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),'none'));

end

if (x<=25&&m==1)||(x>25&&x<=50&&m==2)||(x>50&&x<=75&&m==3)
sum=sum+1;
end

end
disp(sprintf('第%d次分类识别率为%4.2f',ii,sum/75));
totalsum=totalsum+(sum/75);
end
disp(sprintf('10次分类平均识别率为%4.2f',totalsum/10));

测试结果：
第3组数据分类后为Iris-setosa类
第5组数据分类后为Iris-setosa类
第6组数据分类后为Iris-setosa类
第7组数据分类后为Iris-setosa类
第10组数据分类后为Iris-setosa类
第11组数据分类后为Iris-setosa类
第12组数据分类后为Iris-setosa类
第14组数据分类后为Iris-setosa类
第16组数据分类后为Iris-setosa类
第18组数据分类后为Iris-setosa类
第19组数据分类后为Iris-setosa类
第20组数据分类后为Iris-setosa类
第23组数据分类后为Iris-setosa类
第24组数据分类后为Iris-setosa类
第26组数据分类后为Iris-setosa类
第28组数据分类后为Iris-setosa类
第30组数据分类后为Iris-setosa类
第31组数据分类后为Iris-setosa类
第34组数据分类后为Iris-setosa类
第37组数据分类后为Iris-setosa类
第39组数据分类后为Iris-setosa类
第41组数据分类后为Iris-setosa类
第44组数据分类后为Iris-setosa类
第45组数据分类后为Iris-setosa类
第49组数据分类后为Iris-setosa类
第51组数据分类后为Iris-versicolor类
第53组数据分类后为Iris-versicolor类
第54组数据分类后为Iris-versicolor类
第55组数据分类后为Iris-versicolor类
第57组数据分类后为Iris-versicolor类
第58组数据分类后为Iris-versicolor类
第59组数据分类后为Iris-versicolor类
第60组数据分类后为Iris-versicolor类
第61组数据分类后为Iris-versicolor类
第62组数据分类后为Iris-versicolor类
第68组数据分类后为Iris-versicolor类
第70组数据分类后为Iris-versicolor类
第71组数据分类后为Iris-virginica类
第74组数据分类后为Iris-versicolor类
第75组数据分类后为Iris-versicolor类
第77组数据分类后为Iris-versicolor类
第79组数据分类后为Iris-versicolor类
第80组数据分类后为Iris-versicolor类
第84组数据分类后为Iris-virginica类
第85组数据分类后为Iris-versicolor类
第92组数据分类后为Iris-versicolor类
第95组数据分类后为Iris-versicolor类
第97组数据分类后为Iris-versicolor类
第98组数据分类后为Iris-versicolor类
第99组数据分类后为Iris-versicolor类
第102组数据分类后为Iris-virginica类
第103组数据分类后为Iris-virginica类
第105组数据分类后为Iris-virginica类

第106组数据分类后为Iris-virginica类
第107组数据分类后为Iris-versicolor类
第108组数据分类后为Iris-virginica类
第114组数据分类后为Iris-virginica类
第118组数据分类后为Iris-virginica类
第119组数据分类后为Iris-virginica类
第124组数据分类后为Iris-virginica类
第125组数据分类后为Iris-virginica类
第126组数据分类后为Iris-virginica类
第127组数据分类后为Iris-virginica类
第128组数据分类后为Iris-virginica类
第129组数据分类后为Iris-virginica类
第130组数据分类后为Iris-virginica类
第133组数据分类后为Iris-virginica类
第135组数据分类后为Iris-virginica类
第137组数据分类后为Iris-virginica类
第138组数据分类后为Iris-virginica类
第142组数据分类后为Iris-virginica类
第144组数据分类后为Iris-virginica类
第148组数据分类后为Iris-virginica类
第149组数据分类后为Iris-virginica类
第150组数据分类后为Iris-virginica类

k近邻法对wine分类：
clc;
otalsum=0;
for ii=1:10 %循环测试10次
data=load('wine.txt');%导入wine数据
data1=data(1:59,1:13);%任取第一类数据的30组
rbow1=randperm(59);
trainsample1=data1(sort(rbow1(:,1:30)),1:13);
rbow1(:,31:59)=sort(rbow1(:,31:59)); %剩余的29组按行下标大小顺序排列
testsample1=data1(rbow1(:,31:59),1:13);
data2=data(60:130,1:13);%任取第二类数据的35组
rbow2=randperm(71);
trainsample2=data2(sort(rbow2(:,1:35)),1:13);
rbow2(:,36:71)=sort(rbow2(:,36:71));
testsample2=data2(rbow2(:,36:71),1:13);
data3=data(131:178,1:13);%任取第三类数据的24组
rbow3=randperm(48);
trainsample3=data3(sort(rbow3(:,1:24)),1:13);
rbow3(:,25:48)=sort(rbow3(:,25:48));
testsample3=data3(rbow3(:,25:48),1:13);
train_sample=cat(1,trainsample1,trainsample2,trainsample3);%包含89组数据的样本集
test_sample=cat(1,testsample1,testsample2,testsample3);
k=19;%19近邻法
newchar=zeros(1,89);
sum=0;
[i,j]=size(train_sample);%i=89,j=13
[u,v]=size(test_sample);%u=89,v=13

for x=1:u
for y=1:i
result=sqrt((test_sample(x,1)-train_sample(y,1))^2+(test_sample(x,2)-train_sample(y,2))^2+(test_sample(x,3)-train_sample(y,3))^2+(test_sample(x,4)-train_sample(y,4))^2+(test_sample(x,5)-train_sample(y,5))^2+(test_sample(x,6)-train_sample(y,6))^2+(test_sample(x,7)-train_sample(y,7))^2+(test_sample(x,8)-train_sample(y,8))^2+(test_sample(x,9)-train_sample(y,9))^2+(test_sample(x,10)-train_sample(y,10))^2+(test_sample(x,11)-train_sample(y,11))^2+(test_sample(x,12)-train_sample(y,12))^2+(test_sample(x,13)-train_sample(y,13))^2); %欧式距离
newchar(1,y)=result;
end;
[new,Ind]=sort(newchar);
class1=0;
class 2=0;
class 3=0;
for n=1:k
if Ind(1,n)<=30
class 1= class 1+1;
elseif Ind(1,n)>30&&Ind(1,n)<=65
class 2= class 2+1;
else
class 3= class3+1
end
end
if class 1>= class 2&& class1>= class3
m=1;
elseif class2>= class1&& class2>= class3
m=2;
elseif class3>= class1&& class3>= class2
m=3;
end
if x<=29
disp(sprintf('第%d组数据分类后为第%d类',rbow1(:,30+x),m));
elseif x>29&&x<=65
disp(sprintf('第%d组数据分类后为第%d类',59+rbow2(:,x+6),m));
elseif x>65&&x<=89
disp(sprintf('第%d组数据分类后为第%d类',130+rbow3(:,x-41),m));
end

if (x<=29&&m==1)||(x>29&&x<=65&&m==2)||(x>65&&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类
第16组数据分类后为第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类
第102组数据分类后为第2类
第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近邻法，比如，快速搜索近邻法、剪切近邻法、压缩近邻法等，但就个人能力而言，上述优化的算法不太容易编程实现。在日后的学习中，自己也要加强优化算法的能力。