《模式识别与智能信息处理实践》实验报告.doc

模式识别与智能信息处理实践实验报告书专业： 学号： 姓名： 计算机科学与工程学院2011.6.20实验一 聚类分析一、实验目的通过聚类分析实验，加深对聚类分析基本思想、方法的理解和掌握。二、实验内容了解动态、静态聚类算法的特点；熟练掌握k-均值算法或层次聚类算法；编写能对实际模式样本正确分类的算法程序。掌握动态聚类算法的基本思想；认识类别数、初始类心的选择对k-均值算法聚类结果的影响；编写能对实际模式样本正确分类的k-均值算法程序。三、方法手段设类别数为k，选取k个初始聚类中心，按最小距离原则将各模式分配到k类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所属类别中心的距离平方之和最小 。四、k-均值算法（1）从d中随机取k个元素，作为k个簇的各自的中心。（2）分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。（3）根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。（4）将d中全部元素按照新的中心重新聚类。（5）重复第4步，直到聚类结果不再变化。五、k-均值程序运行结果（1）改变初始类心，观察对聚类结果的影响若选初始类心是1 2 3时的结果为其分为1类共39个，分为2类共61个，分为3类共50个，其中被分为第1类的样本为51 53 78 101 103 104 105 106 108 109 110 111 112 113 116 117 118 119 121 123 125 126 129 130 131 132 133 135 136 137 138 140 141 142 144 145 146 148 149，被分为第2类的样本为52 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 102 107 114 115 120 122 124 127 128 134 139 143 147 150，被分为第3类的样本为1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50。若选初始类心是2 4 5时其聚类结果为其分为1类共96个，分为2类共22个，分为3类共个32，其中被分为第1类的样本为51 52 53 54 55 56 57 59 60 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 95 96 97 98 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150，被分为第2类的样本为 2 3 4 7 9 10 13 14 25 26 30 31 35 39 42 43 46 48 58 61 94 99，被分为第3类的样本为1 5 6 8 11 12 15 16 17 18 19 20 21 22 23 24 27 28 29 32 33 34 36 37 38 40 41 44 45 47 49 50。可见，初始类心的选择对于k均值算法的影响较大。（2）改变类别数k，比较其对类内距离平方和的大小的影响若k=3且选初始类心是1 2 3时，其最终各类中心的距离为1.1657 0.8230 4.0783，若k=4且选初始类心是1 2 3 4时，其最终各类中心的距离为1.3049 0.4917 4.0783 1.3928，可见，改变类别数k，其对类内距离平方和的大小有直接的影响，且k越大, 其类内距离平方和距离越小。六、实验总结影响k-均值算法结果的因素有:初始类心的选择以及k值的选择，且k-均值算法适用于k值已知的情况，即类别号已知的情况。七、kmeans程序function y=my_kmeans(k,mid)k=3;%类数mid=1 2 3; %随便给三个聚类中心%从文本文件读入数据放入x中x=load(iris.txt,height,weight);num=size(x,1);%获得x维数大小for i=1:k z(i,:)=x(mid(i),:);%获取k个聚类中心的初始坐标 end%计算新的聚类中心，k-均值算法的核心部分temp=;while(isequal(z,temp) %聚类中心是否变化,若不变化则停止循环 temp=z; class=cell(k,1);%初始化类样本class value=cell(k,1);%初始化类样本的坐标value for j=1:num for t=1:k d(t)=dist(x(j,:),z(t,:);%计算每个样本到类中心的距离 minu,index=min(d);%求出离聚类中心最小的一个样本 end classindex=cat(1,classindex,j);%将该样本归于一类 valueindex=cat(1,valueindex,x(j,:);%存放该类样本的坐标 end for i=1:k z(i,:)=mean(valuei);%计算k类样本的均值，更新聚类中心 endendcelldisp(class);%显示kmeans聚类结果d %显示最终类间距离实验二 判别域代数界面方程法一、实验目的通过实验加深对判别域代数界面方程法基本思想、方法的认识，了解线性判别函数的分类能力，熟练掌握感知器算法，或h-k算法，或累积势函数分类法，以及它们各自的适用条件，加深对有监督训练、线性可分、解空间、权空间等概念的理解，编写能对实际模式样本正确分类的算法程序。二、实验内容编写能对实际模式样本正确分类的感知器算法，或h-k算法，或累积势函数分类法的算法程序，能对实际模式样本进行正确分类。三、方法手段：设已知类别模式特征矢量集为x1,x2,xn，类别数为c。感知器算法是基于一次准则函数的梯度下降法。从任意初始解矢量w0出发，利用产生错分的样本对解矢量进行迭代校正：wk=wk-1+rxi，i=1,2,c，k=0,1,2，r=常数，从而解得线性判决函数d(x)=wx的解矢量w.四、感知器算法1、算法思想任选一初始增广权矢量用训练样本检验用分类正确否对进行校正对所有训练样本都能正确分类？endyesyesnono校正方法实际上是最优化技术中的负梯度下降法。该算法也是人工神经网络理论中的线性阈值神经元的学习算法。2、算法原理步骤设给定一个增广的训练模式集，其中每个模式类别已知，它们分属类和类。 置步数，令增量某正的常数，分别赋给增广权矢量初值的各分量较小的任意值。 输入训练模式。 计算判别函数值。 调整增广权矢量，规则是 如果和，则；(偏小，故加) 如果和，则；(偏大，故减) 如果和，或和，则。（分类正确，不校正） 令。如果，返至。如果，检验判别函数对是否都能正确分类。若是，结束；若不是，令，返至。如果训练模式已经符号规范化，即已乘以1（包括增广分量1），则校正权矢量的规则可统一为 在用全部模式训练完一轮后只要还有模式被判错，则需要进行第二轮迭代，用全部训练模式再训练一次，建立新的权矢量。如果对训练模式还有错分的，则进行第三轮迭代，余类推，直至对所有训练模式均能正确分类为止，此时的即为所求的权矢量。五、感知器算法实验结果（1）改变权矢量初值，观察对算法的影响已知w1:x1=(0 0),x2=(1 0),x3=(1 1),x4=(1 2)；w2:x5=(1 3),x6=(2 3),x7=(3 2),x8=(3 3)，若步长因子r=1不变，权初始值取w=0 0 0,则需迭代eth0=15步，若权初始值取w=1 1 1，则需迭代eth0=18步，可见，权初始值选取的不同，将直接导致算法的收敛速度不同。（2）改变步长因子r，观察对算法的影响若权初始值取w=0 0 0不变，取步长因子r=1，则需迭代eth0=15步，若取步长因子r=0.1，则需迭代eth0=16步，可见，步长因子r选取的不同，也将直接导致算法的收敛速度不同。（3）算法的适用性若已知w1:x1=(1 3),x2=(2 3),x3=(1 1),x4=(1 2)；w2:x5=(0 0),x6=(1 0),x7=(3 2),x8=(3 3)，则导致该程序死循环，可见，感知器算法只适用两类样本线性可分的条件下（图1），若希望在两类样本线性不可分的条件下，构造一判决平面，则可考虑使用势函数。图1 感知器算法分类结果图2 线性不可分的情况六、实验程序function y=my_preception(w1,w2)%感知器算法，对两类问题生成线性判别函数%注意：前提是两类可线性判别，否则将死循环%w1=0 0;1 0;1 1;1 2;%w1类中的样本w2=1 3;2 3;3 2;3 3;%w2类中的样本%初始化w=0 0 0; %任取w初值c=1; %任取校正增量系数c=1；%感知器算法部分%增广样本w1和w2乘(-1)m,n=size(w1);for i=1:m w1(:,n+1)=1;%w1增广endm,n=size(w2);for i=1:m w2(:,n+1)=1;%w2增广endw2=-w2;%取反%将增广向量转换成元组，便于处理m=ones(1,m);w1=mat2cell(w1,m,n+1);w2=mat2cell(w2,m,n+1);x=cat(1,w1,w2);%合并两类增广样本%eth0=0; %迭代次数%感知器算法核心部分m,n=size(x);temp1=;temp2=1;%随意两个赋不等的值while(isequal(temp1,temp2) %判断权值是否变换化，若不变化，则终止循环 eth0=eth0+1; temp2=temp1; clear temp1;%不清除此变量不行啊！ for i=1:m temp1i,1=w; if(w*xipwx(2) w(j,1)=s; disp(正常人) else w(j,2)=s; disp(感染病人) end pause;enddisp(=)disp(正常人 感染病人)w%最小风险贝叶斯n=20; % 样本数figureplot(1:n,a,rx)xlabel(样本数);ylabel(生化化验值);title(样本数据：生化化验值);pause;% 先验概率p=0.9 0.1;% 作类条件概率密度曲线p(x|wi)x=-0.9:0.01:1.3;px(1,:)=(1/(sqrt(2*pi)*0.3)*exp(-0.5*(x/0.3).2);px(2,:)=(1/(sqrt(2*pi)*0.1)*exp(-0.5*(x-1)/0.1).2);figure;plot(x,px(1,:),b,x,px(2,:),r-);xlabel(生化化验值);ylabel(概率密度);title(类条件概率密度曲线)axis tight;pause;% 作后验概率曲线for i=1:2 pwx(i,:)=px(i,:)*p(i)./(px(1,:)*p(1)+px(2,:)*p(2);endfigure;plot(x,pwx(1,:),b,x,pwx(2,:),r-);xlabel(生化化验值);ylabel(后验概率);title(后验概率曲线)axis tight;pause;% 损失函数r=0 1000 0;200 0 0;%作条件风险曲线for i=1:2 r(i,:)=r(i,1)*pwx(1,:)+r(i,2)*pwx(2,:);endfigure;plot(x,r(1,:),b,x,r(2,:),r-);xlabel(生化化验值);ylabel(条件风险);title(条件风险曲线)axis tight;pause;% 计算给定生化化验值的条件风险for j=1:n s=a(j); pxw1=spline(x,px(1,:),s); pxw2=spline(x,px(2,:),s); pxw=pxw1,pxw2; disp(样本) s %计算后验概率 for i=1:2 pwx(i)=pxw(i)*p(i)/(pxw(1)*p(1)+pxw(2)*p(2); end %计算条件风险,判断输出 for i=1:2 rx(i,:)=r(i,1)*pwx(1)+r(i,2)*pwx(2);% end disp(条件风险 r(ai|x)=) rx plot(x,r(1,:),b,x,r(2,:),r-); xlabel(生化化验值); ylabel(条件风险); title(条件风险曲线) hold on plot(s,rx(1),or,s,rx(2),ob); axis tight; hold off if rx(1)rx(2) w(j,1)=s; disp(正常人) else w(j,2)=s; disp(感染病人) end pause;enddisp(=)disp(正常人 感染病人)w实验四 特征提取与选择一、实验目的通过实验加深对特征提取与选择原理、方法的认识，编写基于离散k-l变换的特征提取程序，或分支定界特征挑选算法程序，掌握离散k-l变换原理、特点。编写基于离散k-l变换的特征提取程序。二、实验内容 编写基于离散k-l变换的特征提取程序，主要使用主成分分析法（pca）进行图像识别。三、方法手段：设n维特征矢量x=(x1,x2,xn)，其均值矢量m=ex，协方差矩阵c=e(x-m)(x-m)，设l1l2ln是c的本征值， ti是li对应的本征矢量，i=1,2,n. x经标准正交矩阵t=(t1,t2,tn)正交变换后成为矢量y=(y1,y2,yn)，即，y = tx。这种正交变换称为离散k-l变换（间记为dklt）。dklt的性质：（1）变换后y各分量正交或不相关；（2）变换后y各分量的方差更趋于不均匀，可分性强于x；（3）最佳逼近性，即，若用y的前dn个分量近似x，误差最小。当n较大时，由dklt的性质（2），可以用y的前dn个分量作为特征。四、k-l算法原理特征脸方法是基于k-l变换的人脸识别方法，k-l变换是图像压缩的一种最优正交变换。高维的图像空间经过k-l变换后得到一组新的正交基，保留其中重要的正交基，由这些基可以张成低维线性空间。如果假设人脸在这些低维线性空间的投影具有可分性，就可以将这些投影用作识别的特征矢量，这就是特征脸方法用于人脸识别的基本思想。在人脸识别中，可以用离散k-l变换对人脸图像的原始空间进行转换，即构造人脸图像数据集的协方差矩阵，对之进行正交变换，求出协方差矩阵的特征向量，再依据特征值的大小对这些特征向量进行排序，每一个向量表示人脸图像中一个不同数量的变量，这些特征向量表示特征的一个集合，它们共同表示一个人脸图像。在人脸识别领域，人们常称这些特征向量为特征脸。每一个体人脸图像都可以确切地表示为一组特征脸的线性组合。这样我们首先通过有指导的训练（给定训练样本集已知分类）得到样本集在特征脸空间中的坐标。训练完成后，输入待辨识图像，求得在特征脸空间的坐标，采用最近邻法，就可以实现人脸识别。一般说k-l变换是均方差意义下的最佳变换，理论推导如下。假设任何信号x都可以被表示为：，其中 (1.1)k-l变换是一种正交变换，即将一个向量x，在某一种坐标系统中得描述，转换成用另一种基向量组成的坐标系表示。这组基向量是正交的，其中每个坐标基向量用ui表示，ci为其分量数值，变换的目的是如何将(1.1)表示的无限多维基向量系统改成有限d维坐标系近似。如x的近似值或者估计量表示为： (1.2)要使向量x的估计量误差小，即使引起的均方误差 (1.3)为最小，而k-l变换就实现了这个目的，下面详细证明。求某一个数据x的相应的ci值，可以通过x与对应某个基ui的点积来计算。由于不同的基之间是相互正交的，这个点积值就是ci的值，即，如果我们要求一组系数ci,并将其表示成一个向量形式,则我们可以得： (1.4)则u就是一个变换矩阵，其中每一行是某一个正交基向量的转置，由x计算c称为对x的分解。反过来，如果我们希望用c重构信号x，则根据(1.2)，它是各个成分之和。如果我们将重构信号表示为，则 (1.5)我们称为残差，带进(1.3)中我们可以得到：另外：，故：欲使该均方误差为最小，就变成在保证正交变换的条件下，使最小的问题，设一函数： ，并对其进行求导可得： (1.6)可见向量ui应是矩阵的特征值的特征向量，而此时截断误差为，如将按其大小顺序排列，即，则取前d项特征值对应的特征向量组成的坐标系，可使向量的均方误差为最小。满足上述条件的变换就是k-l变换。五，k-l变换人脸识别实验结果分析1.数据准备本实验数据是orl标准人脸数据库数据1）给定样本集，在这里样本集的大小为400，一共是40人，每人10张图片。我选取每人5张图片一共200张作为训练集，训练集的大小是可选的，它的大小将直接影响到识别的正确率，在后面我对采用不同大小的训练集进行识别的正确率进行了统计。2）确定采用何种产生矩阵，有总体散布矩阵和类间散布矩阵，后面的例子程序中分别采用了这两种产生矩阵，并进行了识别正确率的比较。3）根据产生矩阵计算出特征脸，这里要用到奇异值分解，其基本原理就是通过计算较低维数矩阵的特征值与特征向量而间接求出较高维数矩阵的特征向量（特征脸），从而达到简化计算的目的。4）分别求得训练集中各图像在特征脸空间中的坐标。2.识别过程首先求得待辨识图像相对于训练集平均脸的差值图像，然后求得该图像在特征脸空间中的坐标，最后采用最近邻法对图像进行归类。3.实验结果1）训练样本的过程中生成的一些特征脸（图1）。图1 训练样本的过程中生成的一些特征脸2）识别的正确率统计训练集中每个人图片数123456789识别正确率0.8250.82140.81250.82500.84380.88330.90.950.9889表1以类间散布矩阵为产生矩阵的k-l变换进行人脸识别正确率训练集中每个人图片数123456789识别正确率0.72190.83590.86670.90.90630.93330.96250.97501表2 以总体散布矩阵为产生矩阵的k-l变换进行人脸识别正确率图2 基于两种产生矩阵的识别正确率统计4.实验结论通过对分别采用类间散布矩阵和总体散布矩阵为产生矩阵的k-l变换进行人脸识别的正确率的统计可以看出，应用总体散布矩阵作为产生矩阵的k-l变换进行人脸识别的正确率明显要高。我想主要是因为类间散布矩阵采用每个人的平均图像向量组成训练集，来生成特征脸空间，计算量较之采用总体散布矩阵作为产生矩阵的k-l变换计算量又进一步减少，但是它忽略了每个人的图像的多样性，造成识别率低。以总体散布矩阵作为产生矩阵的k-l变换进行人脸识别的计算量较之采用类间散布矩阵作为产生矩阵的k-l变换要大一些，但是它充分考虑了每个人图像的多样性，使得识别率相对较高。六，实验程序function y=mypca()%pca算法对人脸图像处理提取主成分程序path = d:pca; % d:pcaorl%读取图像numimage=400; %40*10=400张人脸imagepath=path orlorl001 .bmp; %第一张人脸文件的路径及文件名：d:pcaorlorl001.bmpimmatrix=imread(imagepath); % 读入第一张人脸文件，构成矩阵immatrixm,n=size(immatrix); % 计算矩阵immatrix的行数m、列数ndata = uint8 (rand(m*n, numimage); %随机生成m*n行、numimage列的矩阵，并取uint8for i=1:numimage s1=floor(i/100); % 取整,求第3位 tem=rem(i,100); % i除以100的余数，取后两位 s2=floor(tem/10); % 取第2位 s3=rem(tem,10); % 取第1位 imagepath=path orlorl int2str(s1) int2str(s2) int2str(s3) .bmp; % 构成图像文件的路径即文件名 immatrix=imread(imagepath); % 读入每一张人脸文件，构成矩阵immatrix imvector=reshape(immatrix,m*n,1); % 将矩阵immatrix转化为一个列向量，长度为m*n data(:,i)=