最近邻法和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+(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类