模式识别实验指导书2014

实验一、基于感知函数准则线性分类器设计1.1实验类型：设计型：线性分类器设计（感知函数准则）1.2实验目的：本实验旨在让同学理解感知准则函数的原理，通过软件编程模拟线性分类器，理解感知函数准则的确定过程，掌握梯度下降算法求增广权向量，进一步深刻认识线性分类器。1.3实验条件：matlab软件1.4实验原理：感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。感知准则函数利用梯度下降算法求增广权向量的做法，可简单叙述为：任意给定一向量初始值)1(a，第k+1次迭代时的权向量)1(ka等于第k次的权向量)(ka加上被错分类的所有样本之和与k的乘积。可以证明，对于线性可分的样本集，经过有限次修正，一定可以找到一个解向量a，即算法能在有限步内收敛。其收敛速度的快慢取决于初始权向量)1(a和系数k。1.5实验内容已知有两个样本空间w1和w2，这些点对应的横纵坐标的分布情况是：x1=[1,2,4,1,5];y1=[2,1,-1,-3,-3];x2=[-2.5,-2.5,-1.5,-4,-5,-3];y2=[1,-1,5,1,-4,0];在二维空间样本分布图形如下所示：（plot(x1,y1,x2,y2)）-6-4-20246-6-4-20246w1w21.6实验任务：1、用matlab完成感知准则函数确定程序的设计。2、请确定sample=[(0,-3),(1,3),(-1,5),(-1,1),(0.5,6),(-3,-1),(2,-1),(0,1),(1,1),(-0.5,-0.5),(0.5,-0.5)];属于哪个样本空间,根据数据画出分类的结果。3、请分析一下k和)1(a对于感知函数准则确定的影响，并确定当k=1/2/3时，相应的k的值，以及)1(a不同时，k值得变化情况。4、根据实验结果请说明感知准则函数是否是唯一的，为什么？实验二、基于Fisher准则线性分类器设计2.1实验类型：设计型：线性分类器设计（Fisher准则）2.2实验目的：本实验旨在让同学进一步了解分类器的设计概念，能够根据自己的设计对线性分类器有更深刻地认识，理解Fisher准则方法确定最佳线性分界面方法的原理，以及Lagrande乘子求解的原理。2.3实验条件：matlab软件2.4实验原理：线性判别函数的一般形式可表示成0)(wXWXgT其中dxxX1d21根据Fisher选择投影方向W的原则，即使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，用以评价投影方向W的函数为：2221221~~)~~()(SSmmWJF)(211*mmSWW上面的公式是使用Fisher准则求最佳法线向量的解，该式比较重要。另外，该式这种形式的运算，我们称为线性变换，其中21mm式一个向量，1WS是WS的逆矩阵，如21mm是d维，WS和1WS都是d×d维，得到的*W也是一个d维的向量。向量*W就是使Fisher准则函数)(WJF达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向，该向量*W的各分量值是对原d维特征向量求加权和的权值。以上讨论了线性判别函数加权向量W的确定方法，并讨论了使Fisher准则函数极大的d维向量*W的计算方法，但是判别函数中的另一项0W尚未确定，一般可采用以下几种方法确定0W如2~~210mmW或者mNNmNmNW~~~2122110或当1)(p与2)(p已知时可用2)(/)(ln2~~2121210NNppmmW……当W0确定之后，则可按以下规则分类，2010XwXWXwXWTT使用Fisher准则方法确定最佳线性分界面的方法是一个著名的方法，尽管提出该方法的时间比较早，仍见有人使用。2.5实验内容：已知有两类数据1和2二者的概率已知1)(p=0.6，2)(p=0.4。1中数据点的坐标对应一一如下：数据：x=0.23311.52070.64990.77571.05241.19740.29080.25180.66820.56220.90230.1333-0.54310.9407-0.21260.0507-0.08100.73150.33451.0650-0.02470.10430.31220.66550.58381.16531.26530.8137-0.33990.51520.7226-0.20150.4070-0.1717-1.0573-0.2099y=2.33852.19461.67301.63651.78442.01552.06812.12132.47971.51181.96921.83401.87042.29481.77142.39391.56481.93292.20272.45681.75231.69912.48831.72592.04662.02262.37571.79872.08282.07981.94492.38012.23732.16141.92352.2604z=0.53380.85141.08310.41641.11760.55360.60710.44390.49280.59011.09271.07561.00720.42720.43530.98690.48411.09921.02990.71271.01240.45760.85441.12750.77050.41291.00850.76760.84180.87840.97510.78400.41581.03150.75330.95482数据点的对应的三维坐标为x2=1.40101.23012.08141.16551.37401.18291.76321.97392.41522.58902.84721.95391.25001.28641.26142.00712.18311.79091.33221.14661.70871.59202.93531.46642.93131.83491.83402.50962.71982.31482.03532.60301.23272.14651.56732.9414y2=1.02980.96110.91541.49010.82000.93991.14051.06780.80501.28891.46011.43340.70911.29421.37440.93871.22661.18330.87980.55920.51500.99830.91200.71261.28331.10291.26800.71401.24461.33921.18080.55031.47081.14350.76791.1288z2=0.62101.36560.54980.67080.89321.43420.95080.73240.57841.49431.09150.76441.21591.30491.14080.93980.61970.66031.39281.40840.69090.84000.53811.37290.77310.73191.34390.81420.95860.73790.75480.73930.67390.86511.36991.1458数据的样本点分布如下图：-2-101230.511.522.500.511.522.6实验要求：1)请把数据作为样本，根据Fisher选择投影方向W的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，求出评价投影方向W的函数，并在图形表示出来。并在实验报告中表示出来，并求使)(wJF取极大值的*w。用matlab完成Fisher线性分类器的设计，程序的语句要求有注释。2)根据上述的结果并判断（1，1.5，0.6）(1.2，1.0，0.55)，(2.0，0.9，0.68)，(1.2，1.5，0.89)，（0.23，2.33，1.43），属于哪个类别，并画出数据分类相应的结果图，要求画出其在W上的投影。3)回答如下问题，分析一下W的比例因子对于Fisher判别函数没有影响的原因。实验三、K均值聚类算法－动态聚类3.1实验类型：设计型：K均值/C-均值动态聚类算法3.2实验目的：本实验旨在让同学理解动态聚类算法的原理，掌握K均值/C-均值算法，并能利用K均值/C-均值算法解决实际的分类问题。3.3实验条件：matlab软件3.4实验原理：动态聚类方法的任务是将数据集划分成一定数量的子集，例如将一个数据集划分成三个子集，四个子集等。因此要划分成多少个子集往往要预先确定，或大致确定，当然这个子集数目在理想情况现能体现数据集比较合理的划分。这里要解决的问题是:1．怎样才能知道该数据集应该划分的子集数目2．如果划分数目已定，则又如何找到最佳划分。因为数据集可以有许多种不同的划分方法，需要对不同的划分作出评价，并找到优化的划分结果。由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。我们先讨论在子集数目已定条件下的聚类方法，然后在讨论如何确定合理的子集数目。一个动态聚类算法需要有以下几个要点：1.选定某种距离度量作为样本间的相似性度量；2.确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。3.确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。这是一个动态聚类方法的三个要素，其中初始划分只是为了使划分能从某个初始点开始，。而相似度量计算方法对解决实际问题很重要，我们先从最简单的度量——数据之间的欧氏距离开始，然后再提到其它相似性度量方法。第三个要素，即使用准则函数作为优化的评价是动态聚类方法的核心。动态聚类算法原理上就是通过迭代求函数极值的方法要解决的问题是数据的聚类，也就是将现有的数据集进行划分。因此要构造一个函数，这个函数的值与数据划分有关，从而调整数据的划分使该函数达到极值。K均值/C-均值算法1.准则函数—误差平方和准则K均值/c-均值算法的准则函数表示了相似度量是以数据到数据子集均值的模的平方来度量，这是用欧氏距离的度量方法。这个准则函数是以计算各类均值im，与计算各类样本到其所属类均值点误差平方和为准则，若各类均值表示成iyiiyNm1其中第i类集合为i，其样本数目为iN是样本特征向量。此时误差平方和准则可表示成21ciyicimyJ其含义是各类样本与其所属样本均值间误差平方之总和。对于样本集的不同分类，导致不同的样本子集i及其均值im，从而得到不同的cJ值，而最佳的聚类是使cJ为最小的分类。这种类型的聚类通常称为最小方差划分。C—均值算法可归纳成：(1)选择某种方法把N个样本分成C个聚类的初始划分，计算每个聚类的均值cmmm,,21和cJ(2)选择一个备选样本y，设其在i中(3)若1iN，则转(2)，否则继续(4)计算ijmyNNijmyNNejjjjjjj,1,122(5)对于所有的j，若jiee，则将y从i移到j中。(6)重新计算im和jm的值，并修改cJ。(7)若连续迭代N次(即所有样本都运算过)不变，则停止，否则转到2。上述C—均值算法都是在类别c已知条件下进行的，在类别数未知情况下使用C—均值算法时，可以假设类别数是逐步增加的，例如对c＝1，2，3，…分别使用该算法。准则函数cJ是随c的增加而单调地减少的。3.5实验内容：已知有样本点的横纵坐标分别如下：x1=0.56600.62940.53150.58600.51290.50170.78540.60110.65050.79380.99770.68020.40880.08490.29120.01470.07730.1329y1=0.57691.22091.26491