模式识别 最近邻法和k近邻法MATLAB实现.docx

模式识别 最近邻法和k近邻法MATLAB实现.docx

《模式识别 最近邻法和k近邻法MATLAB实现.docx》由会员分享，可在线阅读，更多相关《模式识别 最近邻法和k近邻法MATLAB实现.docx（15页珍藏版）》请在冰点文库上搜索。

模式识别最近邻法和k近邻法MATLAB实现

最近邻法和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;

forii=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

forx=1:

u

fory=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;

ifInd（1,1）<=25

class1=class1+1;

elseifInd（1,1）>25&&Ind（1,1）<=50

class2=class2+1;

else

class3=class3+1;

end

ifclass1>class2&&class1>class3

m=1;

ty='Iris-setosa';

elseifclass2>class1&&class2>class3

m=2;

ty='Iris-versicolor';

elseifclass3>class1&&class3>class2

m=3;

ty='Iris-virginica';

else

m=0;

ty='none';

end

ifx<=25&&m>0

disp（sprintf（'第%d组数据分类后为%s类',rbow1（:

x+25）,ty））;

elseifx<=25&&m==0

disp（sprintf（'第%d组数据分类后为%s类',rbow1（:

x+25）,'none'））;

end

ifx>25&&x<=50&&m>0

disp（sprintf（'第%d组数据分类后为%s类',50+rbow2（:

x）,ty））;

elseifx>25&&x<=50&&m==0

disp（sprintf（'第%d组数据分类后为%s类',50+rbow2（:

x）,'none'））;

end

ifx>50&&x<=75&&m>0

disp（sprintf（'第%d组数据分类后为%s类',100+rbow3（:

x-25）,ty））;

elseifx>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;

forii=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

forx=1:

u

fory=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;

class2=0;

class3=0;

forn=1:

k

ifInd（1,n）<=30

class1=class1+1;

elseifInd（1,n）>30&&Ind（1,n）<=65

class2=class2+1;

else

class3=class3+1;

end

end

ifclass1>=class2&&class1>=class3

m=1;

elseifclass2>=class1&&class2>=class3

m=2;

elseifclass3>=class1&&class3>=class2

m=3;

end

ifx<=29

disp（sprintf（'第%d组数据分类后为第%d类',rbow1（:

30+x）,m））;

elseifx>29&&x<=65

disp（sprintf（'第%d组数据分类后为第%d类',59+rbow2（:

x+6）,m））;

elseifx>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近邻法，比如，快速搜索近邻法、剪切近邻法、压缩近邻法等，但就个人能力而言，上述优化的算法不太容易编程实现。

在日后的学习中，自己也要加强优化算法的能力。