模式识别大作业

模式识别大作业             1.最近邻/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类 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类 2.Fisher线性判别法 Fisher线性判别是统计模式识别的基本之一。它简单，容易实现，且计算量和存储量小，是实际应用中最常用的方法之一。Fisher判别法Fisher在1936年发的中首次提出的线性判别法。Fisher判别法的基本思想是寻找一个最好的投影，当特征向量x从d维空间映射到这个方向时，两类能最好的分开。这个方法实际上涉及到特征维数的压缩问题。 一维空间的Fisher线性判别函数为：         （1）                               =,i=1,2                        （2）               （3） 其中，和是两个样本的均值，，分别为各类样本的的类内离散度。投影方向为：                                                         （4）                                                                 （5） 在Fisher判决函数中，分子反应了映射后两类中心的距离平方，该值越大，类间可分性越好；分母反应了两类的类内的离散度，其值越小越好；从总体上讲，的值越大越好，在这种可分性评价下，使达到最大值的即为最佳投影方向。 2.1 实验原理 1．线性投影与Fisher准则函数     各类在维特征空间里的样本均值向量： ，                    (4.5-2) 通过变换映射到一维特征空间后，各类的平均值为： ，                    (4.5-3) 映射后，各类样本“类内离散度”定义为： ，              (4.5-4) 显然，我们希望在映射之后，两类的平均值之间的距离越大越好，而各类的样本类内离散度越小越好。因此，定义Fisher准则函数：                       (4.5-5) 使最大的解就是最佳解向量，也就是Fisher的线性判别式。 2．求解 从的表达式可知，它并非的显函数，必须进一步变换。 已知：，, 依次代入(4.5-1)和(4.5-2)，有： ，      (4.5-6) 所以：                     (4.5-7) 其中：                    (4.5-8) 是原维特征空间里的样本类内离散度矩阵，表示两类均值向量之间的离散度大小，因此，越大越容易区分。 将(4.5-6)和(4.5-2)代入(4.5-4)式中：                             (4.5-9) 其中：，            (4.5-10) 因此：              (4.5-11) 显然：                            (4.5-12) 称为原维特征空间里，样本“类内离散度”矩阵。 是样本“类内总离散度”矩阵。 为了便于分类，显然越小越好，也就是越小越好。 将上述的所有推导结果代入表达式： 可以得到： 其中，是一个比例因子，不影响的方向，可以删除，从而得到最后解：                         (4.5-18) 就使取得最大值，可使样本由维空间向一维空间映射，其投影方向最好。是一个Fisher线性判断式。       这个向量指出了相对于Fisher准则函数最好的投影线方向。 3. Fisher算法步骤 由Fisher线性判别式求解向量的步骤： ① 把来自两类的训练样本集分成和两个子集和。 ② 由，，计算。 ③ 由计算各类的类内离散度矩阵，。 ④ 计算类内总离散度矩阵。 ⑤ 计算的逆矩阵。 ⑥ 由求解。 4．算法优缺点分析 优点：（1）一般对于线性可分的样本，总能找到一个投影方向，使得降维后样本仍然线性可分，而且可分性更好即不同类别的样本之间的距离尽可能远，同一类别的样本尽可能集中分布。 （2）Fisher方法可直接求解权向量； （3）Fisher的线性判别式不仅适用于确定性模式分类器的训练，而且对于随机模式也是适用的，Fisher还可以进一步推广到多类问题中去 缺点： （1）如果，，则样本线性不可分； ，未必线性可分； 不可逆，未必不可分。 （2）对线性不可分的情况，Fisher方法无法确定分类 2.1 Fisher线性判别实验流程图 N 三、matlab代码及实验结果分析 （1）训练样本程序确定投影方向 clear % w1类训练样本，10组，每组为行向量。 w1=[-0.4,0.58,0.089;-0.31,0.27,-0.04;-0.38,0.055,-0.035;-0.15,0.53,0.011;-0.35,0.47,0.034;...        0.17,0.69,0.1;-0.011,0.55,-0.18;-0.27,0.61,0.12;-0.065,0.49,0.0012;-0.12,0.054,-0.063]; % w2类训练样本，10组，每组为行向量。 w2=[0.83,1.6,-0.014;1.1,1.6,0.48;-0.44,-0.41,0.32;0.047,-0.45,1.4;0.28,0.35,3.1;...     -0.39,-0.48,0.11;0.34,-0.079,0.14;-0.3,-0.22,2.2;1.1,1.2,-0.46;0.18,-0.11,-0.49]; %w1=load('xxx1.txt'); %w2=load('xxx2.txt'); xx1=[-0.7,0.58,0.089]';  % 测试数据xx1，为列向量。 xx2=[0.047,-0.4,1.04]';  % 测试数据xx2，为列向量。     m1=mean(w1,1)';  % w1类样本均值向量，为列向量     sw1=cov(w1,1);  % w1类样本类内离散度矩阵     m2=mean(w2,1)';  % w2类样本均值向量，为列向量     sw2=cov(w2,1);  % w2类样本类内离散度矩阵       sw=sw1+sw2;      % 总类内离散度矩阵 w= inv(sw)*(m1-m2);  % 投影方向 y0=(w'*m1+w'*m2)/2;  % 阈值y0 figure(1) for i=1:10     plot3(w1(i,1),w1(i,2),w1(i,3),'g+')     hold on     plot3(w2(i,1),w2(i,2),w2(i,3),'ro') end xlabel('x轴'); ylabel('y轴'); title('原始训练数据w1,w2三维分布图');   z1=w'*w1'; z2=w'*w2'; figure(2) for i=1:10     plot3(z1(i)*w(1),z1(i)*w(2),z1(i)*w(3),'g+')     hold on     plot3(z2(i)*w(1),z2(i)*w(2),z2(i)*w(3),'ro') end xlabel('x轴'); ylabel('y轴'); title('训练数据w1,w2线性分类效果图'); hold off y1=w'*xx1; if y1>y0     fprintf('测试数据xx1属于w1类\n'); else     fprintf('测试数据xx1属于w2类\n'); end y2=w'*xx2; if y2>y0     fprintf('测试数据xx2属于w1类\n'); else     fprintf('测试数据xx2属于w2类\n'); end 结果如下： 测试数据xx1属于w1类 测试数据xx2属于w2类 （2）对样本数据w3中的10个样本数据进行fisher判别法分类（程序及结果） 程序如下： clear % w1类训练样本，10组，每组为行向量。 w1=[-0.4,0.58,0.089;-0.31,0.27,-0.04;-0.38,0.055,-0.035;-0.15,0.53,0.011;-0.35,0.47,0.034;..     0.17,0.69,0.1;-0.011,0.55,-0.18;-0.27,0.61,0.12;-0.065,0.49,0.0012;-0.12,0.054,-0.063]; % w2类训练样本，10组，每组为行向量。 w2=[0.83,1.6,-0.014;1.1,1.6,0.48;-0.44,-0.41,0.32;0.047,-0.45,1.4;0.28,0.35,3.1;...     -0.39,-0.48,0.11;0.34,-0.079,0.14;-0.3,-0.22,2.2;1.1,1.2,-0.46;0.18,-0.11,-0.49]; % w3为待分类样本数据，10组，每组为列向量。 w3=[1.58,2.32,-5.8;0.67,1.58,-4.78;1.04,1.01,-3.63;-1.49,2.18,-3.39;-0.41,1.21,-4.73;...     1.39,3.61,2.87;1.2,1.4,-1.89;-0.92,1.44,-3.22;0.45,1.33,-4.38;-0.76,0.84,-1.96]';     m1=mean(w1,1)';  % w1类样本均值向量，为列向量     sw1=cov(w1,1);  % w1类样本类内离散度矩阵     m2=mean(w2,1)';  % w2类样本均值向量，为列向量     sw2=cov(w2,1);  % w2类样本类内离散度矩阵       sw=sw1+sw2;      % 总类内离散度矩阵 w= inv(sw)*(m1-m2);  % 投影方向 y0=(w'*m1+w'*m2)/2  % 阈值y0 % w1,w2,w3原始数据三维分布图 figure(3) for i=1:10     plot3(w1(i,1),w1(i,2),w1(i,3),'g+')     hold on     plot3(w2(i,1),w2(i,2),w2(i,3),'ro')     hold on     plot3(w3(1,i),w3(2,i),w3(3,i),'bp') end xlabel('x轴'); ylabel('y轴'); title('训练w1,w2/样本w3原始数据三维分布图'); % w1,w2,w3数据线性投影分类效果图 z1=w'*w1'; z2=w'*w2'; z3=w'*w3; figure(4) for i=1:10     plot3(z1(i)*w(1),z1(i)*w(2),z1(i)*w(3),'g+')     hold on     plot3(z2(i)*w(1),z2(i)*w(2),z2(i)*w(3),'ro')     hold on     plot3(z3(i)*w(1),z3(i)*w(2),z3(i)*w(3),'bp') end xlabel('x轴'); ylabel('y轴'); title('训练w1,w2/样本w3数据线性投影分类效果图'); hold off for i=1:10   y(i)=w'*w3(:,i);     if y(i)>y0         fprintf('样本数据%d属于w1类\n',i);     else         fprintf('样本数据%d属于w2类\n',i);     end end 3．实验及小结 比较两类的分类结果可以得出：用fisher线性判别分析方法得到的识别率分别是80%和84%；而用近邻法得到的识别率分别为96%和88%。因此近邻法的识别率要高于fisher线性判别，主要原因是这两种类型的点相对集中，有一定的规律，但是线性不可分，存在交叠的情况。 在这个分类实验中近邻法有着较高的识别率，但是如果对样本数目少或规律比较复杂的样本，选择近邻法得到的结果可能会大打折扣。因此要根据具体的应用场合来选择合适的分类方法。     书本上有好多模式识别方法法，比如，最近邻方法，fisher线性判别法，快速搜索近邻法、剪切近邻法、压缩近邻法等，但就个人能力而言，上述优化的算法不太容易编程实现。在日后的学习中，自己也要加强优化算法的能力。