模式识别实验指导书.doc

信 息 工 程 学 院模式识别实 验 指 导 书王文华，徐蔚然编著2007年3月目 录实验课概况1实验一、Bayes分类器设计2实验二、基于Fisher准则线性分类器设计5实验三、基于感知函数准则线性分类器设计10实验四、近邻法分类器设计12实验五、动态聚类21实验课概况课程名称：模式识别适应专业：信息工程、自动化、信息安全、信息科学、数字媒体艺术实验学时：8开科学期：5学期一、 实验的性质、任务和基本要求（一） 实验课的性质模式识别实验课是一门非独立的实验课，是同学对模式识别理论内容进行充分的理解的基础上，根据相应的原理，设计实验内容，完成实验任务，是理论知识实践化的方式，利于学生更好的吸收，领悟模式识别的原理与应用，培养学生的动手实践的能力。（二） 实验课的基本要求1、 理解模式识别的基本概念2、 掌握各种算法的流程，以及相应的优缺点。3、 会使用相应的模式识别分类器等算法处理实验问题。二、 实验的分配情况序号实验内容学时选作1Bayes分类器算法2必做2Fisher线性分类器设计， 2二选一3感知器设计24近邻法4二选一5动态聚类4实验一、Bayes分类器设计1.1实验类型：基础型：Bayes分类器设计1.2实验目的：本实验旨在让同学对模式识别有一个初步的理解，能够根据自己的设计对贝叶斯决策理论算法有一个深刻地认识，理解二类分类器的设计原理。1.3实验条件：matlab软件1.4实验原理： 最小风险贝叶斯决策可按下列步骤进行：(1)在已知，i=1,，c及给出待识别的的情况下，根据贝叶斯公式计算出后验概率：j=1,，x (2)利用计算出的后验概率及决策表，按下面的公式计算出采取,i=1,，a的条件风险,i=1,2,a(3)对(2)中得到的a个条件风险值,i=1,，a进行比较，找出使其条件风险最小的决策，即则就是最小风险贝叶斯决策。1.5实验内容：假定某个局部区域细胞识别中正常（）和非正常（）两类先验概率分别为正常状态：P（）=0.9；异常状态：P（）=0.1。现有一系列待观察的细胞，其观察值为：-3.9847 -3.5549 -1.2401 -0.9780 -0.7932 -2.8531 -2.7605 -3.7287 -3.5414 -2.2692 -3.4549 -3.0752 -3.9934 2.8792 -0.9780 0.7932 1.1882 3.0682-1.5799 -1.4885 -0.7431 -0.4221 -1.1186 4.2532 已知先验概率是的曲线如下图：类条件概率分布正态分布分别为（-2，0.25）（2,4）试对观察的结果进行分类。1.6 实验要求：1) 用matlab完成分类器的设计，要求程序相应语句有说明文字，要求有子程序的调用过程。2) 根据例子画出后验概率的分布曲线以及分类的结果示意图。3) 如果是最小风险贝叶斯决策，决策表如下：最小风险贝叶斯决策表：状态决策106210请重新设计程序，画出相应的后验概率的分布曲线和分类结果,并比较两个结果。实验二、基于Fisher准则线性分类器设计2.1实验类型：设计型：线性分类器设计（Fisher准则）2.2实验目的：本实验旨在让同学进一步了解分类器的设计概念，能够根据自己的设计对线性分类器有更深刻地认识，理解Fisher准则方法确定最佳线性分界面方法的原理，以及Lagrande乘子求解的原理。2.3实验条件：matlab软件2.4实验原理：线性判别函数的一般形式可表示成 其中 根据Fisher选择投影方向W的原则，即使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，用以评价投影方向W的函数为： 上面的公式是使用Fisher准则求最佳法线向量的解，该式比较重要。另外，该式这种形式的运算，我们称为线性变换，其中式一个向量，是的逆矩阵，如是d维，和都是dd维，得到的也是一个d维的向量。向量就是使Fisher准则函数达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向，该向量的各分量值是对原d维特征向量求加权和的权值。以上讨论了线性判别函数加权向量W的确定方法，并讨论了使Fisher准则函数极大的d维向量 的计算方法，但是判别函数中的另一项尚未确定，一般可采用以下几种方法确定如或者 或当与已知时可用当W0确定之后，则可按以下规则分类，使用Fisher准则方法确定最佳线性分界面的方法是一个著名的方法，尽管提出该方法的时间比较早，仍见有人使用。2.5实验内容：已知有两类数据和二者的概率已知=0.6， =0.4。中数据点的坐标对应一一如下： 数据：x = 0.2331 1.5207 0.6499 0.7757 1.0524 1.1974 0.2908 0.2518 0.6682 0.5622 0.9023 0.1333 -0.5431 0.9407 -0.2126 0.0507 -0.0810 0.7315 0.3345 1.0650 -0.0247 0.1043 0.3122 0.6655 0.5838 1.1653 1.2653 0.8137 -0.3399 0.5152 0.7226 -0.2015 0.4070 -0.1717 -1.0573 -0.2099y = 2.3385 2.1946 1.6730 1.6365 1.7844 2.0155 2.0681 2.1213 2.4797 1.5118 1.9692 1.8340 1.8704 2.2948 1.7714 2.3939 1.5648 1.9329 2.2027 2.4568 1.7523 1.6991 2.4883 1.7259 2.0466 2.0226 2.3757 1.7987 2.0828 2.0798 1.9449 2.3801 2.2373 2.1614 1.9235 2.2604z = 0.5338 0.8514 1.0831 0.4164 1.1176 0.5536 0.6071 0.4439 0.4928 0.5901 1.0927 1.0756 1.0072 0.4272 0.4353 0.9869 0.4841 1.0992 1.0299 0.7127 1.0124 0.4576 0.8544 1.1275 0.7705 0.4129 1.0085 0.7676 0.8418 0.8784 0.9751 0.7840 0.4158 1.0315 0.7533 0.9548数据点的对应的三维坐标为x2 = 1.4010 1.2301 2.0814 1.1655 1.3740 1.1829 1.7632 1.9739 2.4152 2.5890 2.8472 1.9539 1.2500 1.2864 1.2614 2.0071 2.1831 1.7909 1.3322 1.1466 1.7087 1.5920 2.9353 1.4664 2.9313 1.8349 1.8340 2.5096 2.7198 2.3148 2.0353 2.6030 1.2327 2.1465 1.5673 2.9414y2 = 1.0298 0.9611 0.9154 1.4901 0.8200 0.9399 1.1405 1.0678 0.8050 1.2889 1.4601 1.4334 0.7091 1.2942 1.3744 0.9387 1.2266 1.1833 0.8798 0.5592 0.5150 0.9983 0.9120 0.7126 1.2833 1.1029 1.2680 0.7140 1.2446 1.3392 1.1808 0.5503 1.4708 1.1435 0.7679 1.1288z2 = 0.6210 1.3656 0.5498 0.6708 0.8932 1.4342 0.9508 0.7324 0.5784 1.4943 1.0915 0.7644 1.2159 1.3049 1.1408 0.9398 0.6197 0.6603 1.3928 1.4084 0.6909 0.8400 0.5381 1.3729 0.7731 0.7319 1.3439 0.8142 0.9586 0.7379 0.7548 0.7393 0.6739 0.8651 1.3699 1.1458数据的样本点分布如下图：2.6实验要求：1) 请把数据作为样本，根据Fisher选择投影方向的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，求出评价投影方向的函数，并在图形表示出来。并在实验报告中表示出来，并求使取极大值的。用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），属于哪个类别，并画出数据分类相应的结果图，要求画出其在上的投影。3) 回答如下问题，分析一下的比例因子对于Fisher判别函数没有影响的原因。实验三、基于感知函数准则线性分类器设计3.1 实验类型：设计型：线性分类器设计（感知函数准则）3.2 实验目的：本实验旨在让同学理解感知准则函数的原理，通过软件编程模拟线性分类器，理解感知函数准则的确定过程，掌握梯度下降算法求增广权向量，进一步深刻认识线性分类器。3.3 实验条件：matlab软件3.4 实验原理：感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。感知准则函数利用梯度下降算法求增广权向量的做法，可简单叙述为： 任意给定一向量初始值，第k+1次迭代时的权向量等于第k次的权向量加上被错分类的所有样本之和与的乘积。可以证明，对于线性可分的样本集，经过有限次修正，一定可以找到一个解向量，即算法能在有限步内收敛。其收敛速度的快慢取决于初始权向量和系数。3.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)）3.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、 请分析一下和对于感知函数准则确定的影响，并确定当=1/2/3时，相应的k的值，以及不同时，k值得变化情况。4、 根据实验结果请说明感知准则函数是否是唯一的，为什么？实验四、近邻法分类器设计4.1 实验类型：设计型：近邻法分类器设计4.2 实验目的：本实验旨在让同学理解近邻法的原理，通过软件编程分段线性分类器的极端情况，理解k-近邻法和剪辑近邻的设计过程，掌握影响k-近邻法错误率的估算因素等。4.3 实验条件：matlab软件4.4 实验原理：最近邻法可以扩展成找测试样本的k个最近样本作决策依据的方法。其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成,则决策规划是：如果则决策X (3-63)k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。剪辑近邻法的基本思想是从这样一个现象出发的，即当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。下面以两类别问题为例说明这种方法的原理。假设现有一个样本集N，样本数量为N。我们将此样本集分成两个互相独立的样本子集。一个被当作考试集，另一个作为参考集，数量分别为与，+N。将中的样本表示成，而在中的样本表示为。将一个样本集分成两个相互独立的样本子集是指，分完以后的两个子集具有相同的分布例如将一个样本集分成两个相互独立的对等子集，则在每个特征空间的子区域，两个子集都有相同的比例，或说各类数量近似相等。要注意指出的是每个子区域(从大空间到小空间)实际做时要用从总的集合中随机抽取的方式进行。剪辑的过程是： 首先对中每一个Xi在中找到其最近邻的样本Yi(Xi)，用Yi(Xi)表示Yi是Xi的最近邻参考样本。如果Yi与Xi不属于同一类别，则将Xi从中删除，最后从中得到一个经过剪辑的样本集，称为剪辑样本集。可用来取代原样本集，作为参考样本集对待识别样本进行分类。经过剪辑后，要作为新的训练样本集，则是对其性能进行测试的样本，如发现中的某个训练样本对分类不利，就要把它剪辑掉。实际上剪辑样本的过程也可以用k-近邻法进行，即对中的每个样本Xi，找到在中的k个近邻，用k-近邻法判断Xi是否被错分类。从而决定其取舍，其它过程与前述方法完全一样。剪辑近邻法也可用到多类别情况。剪辑过程也可不止一次。重复多次的称为重复剪辑近邻法。4.5 实验内容如下面的matlab程序阐述的一样，有两个类别，x，y，样本的分布规律服从正态分布，其均值和方差分别为（2，2），（2，4），每个类别里面分别有样本100个，如下面的数据所列（第一行为横坐标，相应的下一行对应的是纵坐标），图形所示clear allclose allx = 2 + sqrt(2) * randn(2,100)y = -2 + sqrt(4) * randn(2,100) plot(x(1,:),x(2,:),ro);hold on plot(y(1,:),y(2,:),b*);grid onx1 = 1 + sqrt(2) * randn(2,2)y1 = -1 + sqrt(4) * randn(2,3) plot(x1(1,:),x1(2,:),gs);hold on plot(y1(1,:),y1(2,:),gd);x = Columns 1 through 8 2.3393 3.0777 1.8737 2.7339 2.3723 2.0607 2.7958 1.1613 4.0497 2.7254 2.9687 1.2959 0.4281 2.7207 1.9812 2.2180 Columns 9 through 16 1.5151 2.8422 0.6955 1.9956 -1.4693 3.1027 2.0873 1.5888 1.3233 1.8781 4.1631 1.6972 0.4532 0.6957 4.4584 2.4472 Columns 17 through 24 1.2210 2.7702 5.3554 2.5755 3.1579 1.4299 2.6070 0.5714 5.0188 1.7864 1.2680 1.4595 1.4049 2.2075 2.9997 2.4271 Columns 25 through 32 1.6260 2.3400 0.7291 1.4722 2.7524 3.1380 3.7800 0.9639 2.4397 2.5036 -0.1208 1.6814 0.1167 0.9358 0.9934 1.0406 Columns 33 through 40 1.6377 0.6335 0.5944 0.6900 2.7269 0.7390 -0.9497 2.2660 1.1267 0.9308 -0.2890 5.5362 1.9855 2.0577 0.2602 -2.1053 Columns 41 through 48 0.7235 0.8765 1.2597 -0.1537 5.8664 1.4564 0.8619 1.2108 1.8883 2.6320 1.5465 0.4295 4.6099 2.7126 0.8788 3.3248 Columns 49 through 56 1.7689 3.9543 2.1305 3.5910 3.4501 2.8476 2.2794 1.7877 1.2711 1.4769 0.6973 2.7846 2.4393 2.0672 3.1551 1.4484 Columns 57 through 64 3.9710 1.9122 3.8749 3.1035 2.1726 1.0068 3.2602 3.4937 -0.2553 3.2665 3.2834 1.1804 3.9009 4.2703 2.6435 3.7896 Columns 65 through 72 1.8904 0.9381 2.6499 1.1209 -0.7602 0.9878 3.3209 2.6825 2.2168 1.6666 0.6734 -0.2885 3.4517 -0.8319 3.5121 1.2336 Columns 73 through 80 1.3980 1.7750 3.0315 4.3814 0.0746 1.0233 0.7370 2.3106 2.8502 2.4497 2.4605 2.5328 1.8479 1.9284 1.9925 2.9242 Columns 81 through 88 1.6755 2.5795 2.0735 1.2835 4.4952 2.1099 1.5293 4.2977 1.6345 4.2585 4.4371 3.7047 3.7777 2.2204 1.7801 2.4882 Columns 89 through 96 0.5578 2.3503 1.9332 2.8394 1.9185 1.1366 2.6934 3.6876 2.7108 2.2008 3.1586 1.0979 2.2828 1.1050 0.7363 6.0314 Columns 97 through 100 0.8630 4.8719 0.7702 1.1824 2.5452 0.9279 2.4000 2.9063y = Columns 1 through 8 -4.0741 -2.2019 0.2772 2.5119 -2.6005 -2.7258 -0.9535 -2.6182 -3.6242 1.8317 -0.3543 -1.3855 -1.0020 -2.2239 -0.4317 -2.0749 Columns 9 through 16 1.1157 -2.9820 -0.7157 -4.8064 -2.1368 0.0204 -4.6403 -1.4024 -1.1429 -1.9817 -1.0701 3.5301 -0.3107 -2.6776 -3.6135 -3.0649 Columns 17 through 24 1.0383 0.0278 -3.8224 -1.7426 -0.8970 -3.1769 -2.6497 -1.0395 -2.4134 -3.3121 -3.0811 -2.6541 -0.7125 -3.1175 -1.9918 -2.0607 Columns 25 through 32 -2.9279 -5.6277 -3.2913 -0.3836 -6.5657 -6.9075 -4.9407 -2.4313 -3.3265 -2.0005 -1.7682 -2.1453 -0.7046 -3.2416 0.6713 -1.8313 Columns 33 through 40 1.1533 0.0380 -0.9046 0.4450 2.1135 -0.9418 -0.3634 0.2072 -0.2502 -1.9232 -1.7691 -3.5266 -1.1793 -2.3955 -1.7491 -2.2116 Columns 41 through 48 -2.7789 -0.4264 -1.5418 -4.5961 -3.1488 -3.2813 0.1521 0.3201 -2.8753 -3.1971 -5.1734 -1.7970 -1.2165 1.0112 1.8658 0.6457 Columns 49 through 56 1.7258 2.4568 1.0064 -2.8329 -2.2510 -2.2932 -0.4625 -2.1996 -3.2806 -1.3224 -1.5015 -3.4684 -3.3073 -1.0344 1.3012 -4.8685 Columns 57 through 64 -0.3933 -4.4781 -0.8298 -2.7694 -4.4012 -2.3012 -2.7238 4.4696 -1.9525 -3.9448 -4.2802 -2.8949 -7.0979 -1.7046 -2.1852 -2.5313 Columns 65 through 72 -0.2649 -0.5083 1.2236 -4.0723 -2.7961 -3.8391 -6.0491 -1.2649 0.8744 -3.6436 -1.7198 -1.0935 -1.5580 -0.2845 -1.1005 -7.1413 Columns 73 through 80 -0.7904 -4.9162 -0.8173 -3.0191 -1.5423 -3.4648 -3.9127 -1.0085 -0.1674 -1.8316 -1.9920 -6.5079 -1.1666 -3.2242 -2.6278 -1.7200 Columns 81 through 88 -3.0868 -2.2972 -3.3748 -1.1780 -3.1821 -3.7845 -1.4982 -1.7623 -0.3149 -4.3529 -1.3920 -1.1284 -0.0297 -5.7240 -2.0337 -2.7306 Columns 89 through 96 -2.0356 -3.1204 -1.6235 -1.6992 -4.8063 -2.9712 -5.5903 -3.5470 -2.3859 -0.1046 -0.6685 -3.2670 -0.1880 1.7160 -4.2020 -3.9663 Columns 97 through 100 -1.6145 2.1930 -2.3963 -5.2112 -0.5505 -5.9320 1.6841 -3.7229请使用k-近邻法判断下列sample中样本的分类情况（-0.7303，2.1624），（1.4445，-0.1649），（-1.2587，0.9187），（1.2617，-0.2086），（0.7302，1.6587） 4.6 实验要求：1、 要求用matlab编程，来确定分类的情况，并以图形的方式表示出来。2、 分析k值的不同对分类的情况是否有影响，并把结果用图形的方式表示出来。3、 回答下列问题设在一个二维空间，A类有三个训练样本，图中用红点表示，B类四个样本，图中用蓝点表示。 试问：（1） 按近邻法分类，这两类最多有多少个分界面（2） 画出实际用到的分界面（3） A1与B4之间的分界面没有用到4、 请根据剪辑方法近邻的原理，对样本的空间进行剪辑，再确定上述样本点的分类情况。并对两种分类结果进行分析（选作）。实验五、动态聚类5.1 实验类型：设计型：C-均值动态聚类算法5.2 实验目的：本实验旨在让同学理解动态聚类算法的原理，掌握C-均值算法，并能利用C-均值算法解决实际的分类问题。5.3 实验条件：matlab软件5.4 实验原理：动态聚类方法的任务是将数据集划分成一定数量的子集，例如将一个数据集划分成三个子集，四个子集等。因此要划分成多少个子集往往要预先确定，或大致确定，当然这个子集数目在理想情况现能体现数据集比较合理的划分。这里要解决的问题是:1 怎样才能知道该数据集应该划分的子集数目2 如果划分数目已定，则又如何找到最佳划分。因为数据集可以有许多种不同的划分方法，需要对不同的划分作出评价，并找到优化的划分结果。由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。我们先讨论在子集数目已定条件下的聚类方法，然后在讨论如何确定合理的子集数目。一个动态聚类算法需要有以下几个要点：1.选定某种距离度量作为样本间的相似性度量；2.确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。3.确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。这