模式识别结题论文-基于聚类算法和线性判决器的模式分类问题分析.doc

基于聚类算法和线性判决器的模式分类问题分析一、模式分类概述一个典型的模式识别系统如图1所示，由数据获取、预处理、特征提取、分类决策及分类器设计五部分组成。一般分为上下两部分：上部分完成未知类别模式的分类；下半部分属于分类器设计的训练过程，利用样品进行训练，确定分类器的具体参数，完成分类器的设计。而分类决策在识别过程中起作用，对待识别的样品进行分类决策。数据获取预处理特征提取分类决策分类结果未知类别模式的分类图1 模式识别系统及识别过程训练样本输入预处理特征选择确定判别函数改进判别函数分类器设计误差检验模式识别系统组成单元功能如下：（1）数据获取用计算机可以运算的符号来表示所研究的对象，一般获取的数据类型有一下几种。二维图像：文字、指纹、地图、照片等。一维波形：脑电图、心电图、季节震动波形等。物理参量和逻辑值：体温、化验数据、参量正常与否的描述。（2）预处理对输入测量仪器或其他因素所造成的退化现象进行复原、去噪声，提取有用信息。（3）特征提取和选择对原始数据进行变换，得到最能反映分类本质的特征。将维数较高的测量空间（原始数据组成的空间）转变为维数较低的特征空间（分类识别赖以进行的空间）。（4）分类决策在特征空间中用模式识别方法把被识别对象归为某一类别。（5）分类器设计基本做法是在样品训练基础上确定判别函数，改进判别函数和误差检验。二、具体分类方法概述2.1 聚类聚类分析是将数据分类到不同的类或者簇的过程，聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。 本课题中主要讨论层次聚类和c均值聚类方法。2.1.1 层次聚类在描述基本思想之前，假设 是将要聚类的l维向量集。层次聚类算法产生一个嵌套聚类的层次。更具体地说，这些算法包含n步，与数据向量的数量一样多。在第t步，要在前t-1步的聚类基础上生成新聚类。有两种不同的算法：合并和分裂层次算法。合并算法中，初始聚类 由n个聚类组成，每个聚类仅包含x中的一个元素。第一步生成聚类 ，它包含n-1个集合，如 。重复此过程直到产生最后一个聚类 ，它只包含一个单个的聚类集合，即数据集x。因而得到聚类的层次为分裂算法与合并算法的思路恰好相反。在这种算法中，初始聚类 仅包括一个集合x。第一步产生聚类 ，它由 个集合组成，如 。重复此过程直到产生最后一个聚类 ，它包含n个集合，每个集合仅包含x中的一个元素，在这种情况下可得本课题中采用合并算法中的最短距离法。层次聚类算法原理为：n个初始模式样本自成一类，即建立n类，之后按照以下步骤运算：step1：计算各类之间（即各样本间）的距离，得一个维数为nn的距离矩阵d(0)。“0”表示初始状态。step2：假设已求得距离矩阵d(n)（n为逐次聚类合并的次数），找出d(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：step3：计算合并后所得到的新类别之间的距离，得d(n+1)。step4：跳至第2步，重复计算及合并。直到满足下列条件时即可停止计算：取距离阈值t，当d(n)的最小分量超过给定值 t 时，算法停止。所得即为聚类结果。或不设阈值t，一直到将全部样本聚成一类为止，输出聚类的分级树。 2.1.2 c均值算法c均值算法首先取定c个类别数量并对这c个类别数量选取c个聚类中心，按最小距离原则将各模式分配到c类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其对应的判属类别中心的距离平方之和最小。上述算法也可以先初始化聚类中心，然后再执行迭代过程。算法性能依赖于初始聚类中心。2.2 线性判决器在特征空间中，通过学习，不同的类别可以得到不同的判别函数，比较不同类别的判别函数值大小，就可以进行分类。统计模式识别方法把特征空间划分为决策区对模式进行分类。一个模式类同一个或几个决策区相对应。每个决策区对应一个判别函数。对于特征空间中的每个特征向量x,可以计算相应于各个决策区的判别函数gi(x),i=1,2,c。用判别函数进行分类的方法就是：若对所有的i均有gi(x)gi(x),则把x分为第j类,记成r(x)=j。本课题中选用最小欧式距离判别准则设计线性分类器：； ；判别函数： ；三、实验部分3.1 实验一 区分图片中的汽车与背景首先，对样本进行解释：每个样本的特征有252个，其中前12个为第四层高频系数，中间48个是第三层高频系数，后192个是第二层高频系数。所以可以考虑从252维特征中选取不同的多个特征，分析其各自的分类效果，进行比较。3.1.1 基于线性分类器的仿真结果利用合适的特征设计分类器区分汽车和背景两类数据，并分析结果。进行训练样本集和测试样本集的划分:将所给的n个样本随机的分成两个子集，每个子集有n/2个样本。利用其中的一个子集作为训练样本集设计分类器，然后用另一个子集进行测试，计算错误率。随机选取多次，求出平均错误率，作为性能指标。 说明：程序首先调用自己编写的randq子程区分训练样本和测试样本，通过得到相关参数，设计最小欧式距离判别器，再用来检测所有的测试样本，最后分别得到每次的错误率：err_vg（将汽车误判为背景时的错判率）；err_gv(将背景误判为汽车时的错判率)；由于特定每次得到的错误率和数据样本的分布有关，所以要估计整个分类器的错误率，所以本子程设定循环抽样十次分别求取得到不同的单次抽样率，求得错误率的平均值： err_vg（将汽车误判为背景时的错判率）；err_gv(将背景误判为汽车时的错判率)；此外，本程序设置了两个变量：k_s ，k_d 用来灵活的设定所选择的特征。k_s标识选择的特征起始标号，k_d表示选择的特征结束标号，通过选定不同的特征，得到不同的错误率进行比较，得到最有区分度的特征。结果分析:通过选定指定的特征，选取10次训练和测试样本集的不同划分，求取平均错误辨识率，得到平均错误率，该错误率基本减小了样本分布的差异。选取不同的k_s, k_d值得到不同的特征选择，进行训练，判别，得到对应不同的错误率，进行比较分析。选取1：252维所有特征时：err_vg = 0.0348； err_gv = 0.0392；选取1：12维所有第四层高频系数作为特征时：err_vg = 0.2792； err_gv = 0.1620；选取13：60维所有第三层高频系数作为特征时：err_vg = 0.0448； err_gv = 0.0196；选取61：252维所有第二层高频系数作为特征时：err_vg = 0.0688； err_gv = 0.0512；选取13：252维所有第二层和第三层高频系数作为特征时：err_vg = 0.0316； err_gv = 0.0184；结论：通过数据分析，可以得到：针对最小欧式距离判决准则的线性分类器，当它选取不同的特征进行训练，判决时，得到的错误率还是有比较大的差别，尤其是仅选取小波变换后得到的第四层系数时，得到的错误率比较大，此后错误率大小依次是第二层，第三层。而若将第二层和第三层的特征结合起来考虑，得到的错误率最小，甚至比选取所有维的特征都小。由于我们是随机选取的训练样本和测试样本，并求取最后的平均错误率，所以基本可以得出结论：在本问题中，若使用基于最小欧式距离的线性判决器，则选取其小波变化后的第三和第二层系数作为特征，其最终的判决结果较好。3.1.2 基于层次聚类的仿真结果程序说明：首先用pdist函数算出对象两两之间的距离，然后利用linkage函数建立层次化的结构树。通过比较分类结果，选择适合本类样本特点的类内平方距离最小误差算法。最后调用cluster函数，对于结构树进行聚类，确定最终的类别。 结果分析：通过聚类，得到背景误判概率（样本为背景，错判为其它类）err_bg0.0420；汽车误判概率（样本为汽车，错判为其它类）err_car0.0400；行人误判概率（样本为行人，错判为其它类）err_hm=0.002;其中数组class_1，class_2，class_3各自存储着该类数据对应的样本在总样本集中的下标值。从中我们可以得到哪些样本得到了正确的划分，哪些被错分到了不同类。比较最远距离聚类算法得到的结果，该种算法得到的结果是非常好的，错误率比较低，最高不超过5。也就是说500个样本数据，仅有25个错误数据，效果还是不错的。 总结：无标签分层聚类算法：因为是无标签学习，所以没有学习训练过程，直接根据数据样本在所处的特征空间的位置进行聚类，所以选用适合样本分布特点的聚类算法是至关重要的，它决定了最终的分类效果。3.2 实验二 根据身高体重特征区分男女生用a.txt、b.txt和/或c.txt的数据作为本次实验使用的样本集，其中存放身高体重数据，利用c均值聚类法和层次聚类法对样本集进行聚类分析，对结果进行分析，从而加深对所学内容的理解和感性认识。3.2.1 基于c均值方法的仿真结果 3.2.2 基于层次算法的仿真结果 通过两种方法的分类可以看出，在当前样本的情况下，c均值方法100组数据分错五组，错误率5%，层次方法100组数据分错6组，错误率6%，结果受样本选取的影响比较大，再加上样本选取的范围比较小，故错误率比较高。应该再多选取几组数据进行试验，这样才能比较出两种方法的优缺点。四、源程序代码4.1 实验一 区分图片中的汽车与背景函数介绍：1 pdist函数 调用格式：y=pdist(x,metric)说明：用 metric指定的方法计算 x 数据矩阵中对象之间的距离。 x：一个mn的矩阵，它是由m个对象组成的数据集，每个对象的大小为n。metric取值如下：euclidean：欧氏距离（默认）；seuclidean：标准化欧氏距离；mahalanobis：马氏距离；cityblock：布洛克距离；minkowski：明可夫斯基距离；2. linkage函数 调用格式：z=linkage(y,method) 输入值说明：y为pdist函数返回的m*(m-1)/2个元素的行向量，用method参数指定的算法计算系统聚类树。method：可取值如下：single：最短距离法（默认）；complete：最长距离法；average：未加权平均距离法； weighted： 加权平均法；centroid：质心距离法；median：加权质心距离法；ward：内平方距离法（最小方差算法）返回值说明：z为一个包含聚类树信息的（m-1）3的矩阵，其中前两列为索引标识，表示哪两个序号的样本可以聚为同一类，第三列为这两个样本之间的距离。另外，除了m个样本以外，对于每次新产生的类，依次用m+1、m+2、来标识。为了表示z矩阵，我们可以用更直观的聚类数来展示，方法为：dendrogram(z), 产生的聚类数是一个n型树，最下边表示样本，然后一级一级往上聚类，最终成为最顶端的一类。纵轴高度代表距离列。另外，还可以设置聚类数最下端的样本数，默认为30，可以根据修改dendrogram(z,n)参数n来实现，1n=0.5) if (j250) for a=1:252 test(k,a)=x(i,a); end k=k+1; else for a=1:252 tr(j,a)=x(i,a); end j=j+1; end else if(k250) for a=1:252 tr(j,a)=x(i,a); end j=j+1; else for a=1:252 test(k,a)=x(i,a); end k=k+1; end end endname_tr=tr;name_test=test;设计线性分类器把汽车和背景两类数据区分：根据最小欧式距离判别准则设计线性分类器load vehicle;load background;for j=1:10k_s=1;k_d=252;vec_tr(250,252)=0;vec_test(250,252)=0;vec_tr,vec_test=randq(vehicle);randq(background);bg_tr(250,252)=0;bg_test(250,252)=0;bg_tr,bg_test=randq(background);m_vec=vec_tr(1,k_s:k_d);for i=2:250m_vec=m_vec+(vec_tr(i,k_s:k_d);endm_vec=m_vec/250;m_bg=bg_tr(1,k_s:k_d);for i=2:250m_bg=m_bg+(bg_tr(i,k_s:k_d);endm_bg=m_bg/250;d_vec=(m_vec*m_vec)/2;d_bg=(m_bg*m_bg)/2; 求取分类器对应的各参数flag_vec(250)=0;flag_bg(250)=0;dk_vec=0;dk_bg=0;for i=1:250dk_vec=vec_test(i,k_s:k_d)*m_vec-d_vec; 设计线性分类器 dk_bg=vec_test(i,k_s:k_d)*m_bg-d_bg; if(dk_vec=dk_bg) flag_vec(i)=1; else flag_vec(i)=0; endends1_vec=sum(flag_vec);for i=1:250 dk_vec=bg_test(i,k_s:k_d)*m_vec-d_vec; dk_bg=bg_test(i,k_s:k_d)*m_bg-d_bg; if(dk_bg=dk_vec) flag_bg(i)=1; else flag_bg(i)=0; endends1_bg=sum(flag_bg);err_vg(j)=(250-s1_vec)/500;err_gv(j)=(250-s1_bg)/500;enderr_vg=0;err_gv=0;for i=1:10 err_vg=err_vg+err_vg(i); err_gv=err_gv+err_gv(i);enderr_vg=err_vg/10err_gv=err_gv/104.1.2 层次聚类程序load feature_table;w=feature_table;dist=pdist(w); 计算两两对象之间的距离tree=linkage(dist,ward); 建立层次化的结构树（类内平方距离最小误差）class=cluster(tree,3); 聚类class_1=find(class=1); 第一类class_2=find(class=2); 第二类class_3=find(class=3); 第三类n1=size(class_1);n2=size(class_2);n3=size(class_3);a1=0;a2=0;a3=0;for i=1:n1(1) if(1000=class_1(i)1500) a1=a1+1; endendfor i=1:n2(1) if(500=class_2(i)1000) a2=a2+1; endendfor i=1:n3(1) if(0=class_3(i)500) a3=a3+1; endend err_bg=abs