模式识别报告.pdf

《模式识别报告.pdf》由会员分享，可在线阅读，更多相关《模式识别报告.pdf（23页珍藏版）》请在三一文库上搜索。

1、1 Harbin Institute of Technology 模式识别报告模式识别报告 课程名称： 模式识别 院 系： 信号与信息处理 班 级： 电子 2 班 姓 名： 赵德华 学 号： 11S005019 教 师： 宿富林 哈尔滨工业大学 2 目录目录 Harbin Institute of Technology . 1 目录 . 2 实验一 C-均值算法与模糊 C 均值聚类的比较 . 3 实验要求 . 3 实验原理 . 3 实验结果与分析 . 6 C 均值法 . 6 模糊 C 均值法 . 7 试验程序 . 7 C 均值法 . 7 模糊 C 均值法 . 10 实验二 SVM 用于模式识别

2、 . 14 实验要求 . 14 实验原理 . 14 实验结果与分析 . 16 试验程序 . 19 Fisher 线性分类器及感知器 . 20 实验要求 . 20 实验结果 . 20 试验程序 . 21 Fisher 分类 . 21 感知器分类 . 22 样本产生函数 . 23 3 实验一实验一 C-均值算法与模糊均值算法与模糊 C 均值聚类的比较均值聚类的比较 实验要求实验要求 表 1 用于 C-均值算法与模糊 C 均值聚类的比较实验的数据(X1、X2、X3 是样本的特征) 样本 1 2 3 4 5 6 7 8 9 10 X1 -7.82 -6.68 4.36 6.72 -8.64 -6.87

3、 4.47 6.73 -7.71 -6.91 X2 -4.58 3.16 -2.19 0.88 3.06 0.57 -2.62 -2.01 2.34 -0.49 X3 -3.97 2.71 2.09 2.80 3.50 -5.45 5.76 4.18 -6.33 -5.68 样本 11 12 13 14 15 16 17 18 19 20 X1 6.18 6.72 -6.25 -6.94 8.09 6.81 -5.19 -6.38 4.08 6.27 X2 2.81 -0.93 -0.26 -1.22 0.20 0.17 4.24 -1.74 1.30 0.93 X3 5.82 -4.04 0

4、.56 1.13 2.25 -4.15 4.04 1.43 5.33 -2.78 利用表 1 数据完成下面的实验： (1) 编写 C-均值算法，并用上表数据按下列条件分别测试。 （a） c=2(类别数)；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1) （b） c=2(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)。将得到的结果与（a） 中结果比较，并解释差别，包括迭代次数的差别。 （c） c=3(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2) （d） c=3( 类 别

5、 数 ) ； 初 始 聚 类 的 均 值 ： m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1) ， m3(0)=(-0.1,-0.1,0.1)。将得到的结果与（a）与（c）中结果比较，并解释差别，包括 迭代次数的差别。 (2) 重做（1） ，但利用模糊 C 均值聚类，并设置:b=2。并与 C-均值算法比较 实验原理实验原理 C 均值算法是一种动态聚类方法，依据最小误差平方和准则，通过迭代计算可以得到较 好的聚类结果。 该算法主要有 3 个步骤： （1） 选择代表点 初始代表点的选择往往会影响迭代的结果，如果代表点选择的不好得到的可能不是全 局最优解而是局部最优解。因此

6、代表点的选择也很重要。 通常代表点的选择又有以下几种方法： (a)，凭经验选择代表点 根据问题的性质， 用经验的办法确定类别数， 从数据中找出从直观上看来是比较合适的 代表点 (b), 将全部数据随机的分为 c 类 计算各类重心，将这些重心作为每类的代表点 4 (c), 用前 c 个样本作为代表点 这里的“密度”是具有统计性质的样本密度。一种求法是，以每个样本点为球心，用某个 正数为半径作一个球形邻域，落在该球内的样本数则称为该点的“密度”。在计算了全部样 本点的“密度”后，首先选择“密度”大最大的样本点作为第一个代表点。它对应样本分布的一 个最高的峰值点。在选第二个代表点时，可以人为地规定一

7、个数值0，在离开第一个代 表点距离以外选择次大的“密度”点作为第二个代表点， 这样就可以避免代表点可能集中在 一起的问题。其余代表点的选择可以类似地进行。 （2） 以代表点为基准进行初始分类 选定代表点后可以有不同的初始分类方法。 其实也可以省略掉上一步， 可以直接用样 本进行初始分类。下面给出几种确定初始分类的方法： (a),选择一批代表点后， 其余的点离哪个代表点最近就归入那一类。 从而得到初始分类。 (b),选择一批代表点后，每个代表点自成一类，将样本依顺序归入与其距离最近的代 表点的那一类，并立即重心计算该类的中心以代替原来的代表点。然后在计算下一个样本 的归类，直至所有的样本都归到相

8、应的类中为止。 (c),规定一个正数，选择 11 y，计算样本 2 y与 1 y间的距离 21 ,yy，如果小 于，则将 2 y归入 1 ，否则建立新类 22 y。当某一步轮到 l y归入时，假如当时已 形成了 K 类即 12 , k ，而每个类第一个归入的样本记作 111 12 , k y yy。若 1 ,1, 2, li y yiK，则将 l y建立为新的第 K+1 类， 即 1Kl y 。否则将 l y归 入与 111 12 , k y yy距离为最近的那一类。 (d),先将数据标准化，用 ij y表示标准化后第 i 个样本的第 j 个坐标。令 1 ( ) d ij j SUM iy (

9、1) max( ) i MASUM i (2) min( ) i MISUM i (3) 若欲将样本划分为 c 类，则对每个 i 计算 (1)( ) 1 () cSUM iMI MAMI (4) 假设与这个计算值最接近的整数为 K，则将 l y归入第 K 类。 （3） 用 c 均值法迭代修正，直到误差不变为止 有了初始分类之后， 我们分析一下把聚类 k 中的一个样本 y 从 k 移入 j 对误差平方 5 和所带来的影响。设从 k 中移出 y 后的集合是k，它相应的均值是 km，显然 1 1 k kk k mmmy N (5) 式中的 k m和 k N是 k 的样本均值和样本数。 设 j 接受

10、y 后的集合是j，它相应的均值是 jm， 1 1 j jj j mmym N (6) 式中的 j m和 j N是 j 中的样本均值和样本数。 由于 y 的移动只影响 k 和 j 两类， 而对其 它的类是无任何影响的，因此我们只需计算这两类的新的误差平方和 kJ和jJ。 2 k J 1 k kk k N Jym N (7) 2 j J = 1 j jj j N Jym N (8) 假使 2 2 11 j k jk jk N N ymym NN (9) 则把样本 y 从 k 移入到 j 就会使误差平方和减少。只有当 y 离 j m的距离比离 k m的 距离更近时才满足上述不等式。 依据上述准则进行

11、 c 均值法的迭代步骤： 选择某种方法把样本分成 C 个聚类的初始划分，计算每个聚类的均值 m1,mc 和 Jc 选择一个备选样本 y，设其在 i w 中 若 i N=1，则转(2)，否则继续 计算 2 2 , 1 , 1 j j j j j j j N ymji N e N ymji N (10) 对于所有的 j，若 kj ee，则将 y 从 i e 移到 k e中。 6 重新计算 i m和 k m，并修改 Jc 若连续迭代 N 次(即所有样本都运算过)不变，则停止，否则转到 实验结果与分析实验结果与分析 C 均值法均值法 本 c 均值法代表点的选择方法为根据经验选择代表点， 初始聚类的方法

12、采用第一种方法 即选择一批代表点后，其余的点离哪个代表点最近就归入那一类。从而得到初始分类。 (a)当类别数当类别数 c=2；初始聚类的均值：；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1)时的实验结果为时的实验结果为: 初始分类之后的 2 个聚类为: 3,4,7,8,11,12,15,16,19,20和1,2,5,6,9,10,13,14,17,18 误差 平方和为 410.1070 C均值法之后的2个聚类为: 3,4,7,8,11,12,15,16,19,20和1,2,5,6,9,10,13,14,17,18误差平 方和也为 410.1070 迭代次数为 20

13、C 均值法前后聚类没有变化，表明初始的聚类均值比较好,在初始分类之后就是最优的 结果。迭代次数为 20 也表明在 c 均值算法中没有发生交换数据。该结果表明一组好的代表 点的选择可以最大化的减少交换数据的次数，提高算法效率。 (b)当类别数当类别数 c=2；初始聚类的均值：；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)时的实验结果为时的实验结果为: 初始分类之后的 2 个聚类为: 1,2,3,5,6,7,8,9,10,13,14,17,18,19和4,11,12,15,16,20 误差 平方和为 832.8288 C 均值法之后的 2 个聚类为：1,2,5,6,9,

14、10,13,14,17,18和3,4, 7,8,11,12,15,16, 19,20 误 差平方和为 410.1070 迭代次数为 57 与（a）中相比初始聚类后的误差平方和非常大，而且这次 c 均值算法前后聚类发生了 变化,并且 c 均值法之后得聚类结果（a）中相同,表明在这两组不同的初始分类条件下将得到 相同的聚类效果。迭代次数为 57，表明代表点的选择对聚类的效果有很大的影响。 (c)当类别数当类别数 c=3；初始聚类的均值：；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)时的实时的实 验结果为验结果为: 初始分类之后的 3 个聚类为

15、: 1,6,9,10、3,4,7,8,11,12,15,16,19,20和2,5,13,14,17,18 误 差平方和为 263.6711 C 均值法之后的 3 个聚类为： 1,6,9,10、 3,4,7,8,11,12,15,16,19,20和2,5,13,14,17,18 误 差平方和为 263.6711 迭代次数为 20 可以看出 c 均值法前后聚类没有变化，说明初始均值选取的非常好。 (d) 当 类 别 数当 类 别 数c=3 ； 初 始 聚 类 的 均 值 ：； 初 始 聚 类 的 均 值 ： m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1) ， m3(0)

16、=(-0.1,-0.1,0.1)时的实验结果为时的实验结果为: 初始分类之后的 3 个聚类为: 2,5,6,9,17 、 3,4,7,8,11,12,15,16,19,20和1,10,13,14,18 误 差平方和为 360.6290 C 均值法之后的 3 个聚类为： 2,5,17、 3,4,7,8,11,12,15,16,19,20 和1,6,9,10,13,14,18 误 差平方和为 295.6191 迭代次数为 35 与（a）中相比误差平方和变小了，表明合理的选择聚类数能减少聚类之后得误差平方 和。迭代次数比（a）中稍大。 7 与（c）中相比结果也不一样，误差平方和比（c）中大，而且聚类

17、结果也不一样，迭代 数也比（c）中的大，再一次表明了初始聚类带标点的选择对结果有很大的影响。 模糊模糊 C 均值法均值法 (a),当类别数当类别数 c=2；初始聚类的均值：；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1)时的实验结果为时的实验结果为: 模糊 C 均值法之后的 2 个聚类为: 3,4,7,8,11,12,15,16,19,20和1,2,5,6,9,10,13,14,17,18 聚类损失为 360.4373 迭代次数为 16 （注：以两次迭代的均值之差的范数小于 1e-8 时停止迭代，并且以样本 属于隶属度大的那一类去模糊） 最后的聚类结果和 c 均值算

18、法的一样，但是聚类损失稍小（但聚类损失定义的不一样） (b),当类别数当类别数 c=2；初始聚类的均值：；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)时的实验结果为时的实验结果为: 模糊 C 均值法之后的 2 个聚类为： 1,2,5,6,9,10,13,14,17,18和3,4, 7,8,11,12,15,16, 19,20 聚类损失为 360.4373 迭代次数为 18 与 c 均值算法的聚类结果一样 (c),当类别数当类别数 c=3；初始聚类的均值：；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)时的实时的实

19、 验结果为验结果为: 模糊C均值法之后的3个聚类为： 1,6,9,10、 3,4,7,8,11,12,15,16,19,20和2,5,13,14,17,18 误差平方和为 211.8825 迭代次数为 30 与 c 均值算法结果一样，误差稍小。 (d), 当 类 别 数当 类 别 数 c=3 ； 初 始 聚 类 的 均 值 ：； 初 始 聚 类 的 均 值 ： m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1) ， m3(0)=(-0.1,-0.1,0.1)时的实验结果为时的实验结果为: 模糊C均值法之后的3个聚类为： 2,5,13,14,17,18、 3,4,7,8,

20、11,12,15,16,19,20 和1,6,9,10 误差平方和为 211.8825 迭代次数为 37 与 c 均值算法聚类结果不一样，且聚类误差减小了。 试验程序试验程序 C 均值法均值法 %C-均值算法 3个聚类 clear clc load data2012_5_1 % data2012_5_1内存有表1的数据 N(1)=0; N(2)=0; N(3)=0; m1=-0.1 0 0.1; %初始聚类均值 m2=0 -0.1 0.1; m3=-0.1 -0.1 0.1 ; % 初始分类 for i=1:20 tmp=x1(i),x2(i),x3(i); %读入一个数据存在tmp中 8 d

21、ist(1)=norm(m1-tmp); %分别计算该数据与三个均值的距离 dist(2)=norm(m2-tmp); dist(3)=norm(m3-tmp); distmin=find(min(dist)=dist); %找出dist最小值的下标 1 or 2 or 3 N(distmin)=N(distmin)+1; if distmin=1 cluster1(N(distmin)=i; elseif distmin=2 cluster2(N(distmin)=i; else cluster3(N(distmin)=i; end end %循环结束后N(1)存的是第一聚类的元素数，同理N

22、(2)、N(3) mean1=mean(x1(cluster1),mean(x2(cluster1),mean(x3(cluster1); %每个聚类的均值 mean2=mean(x1(cluster2),mean(x2(cluster2),mean(x3(cluster2); mean3=mean(x1(cluster3),mean(x2(cluster3),mean(x3(cluster3); J1=0; %计算误差平方和 J2=0; J3=0; for i=1:N(1) y=x1(cluster1(i),x2(cluster1(i),x3(cluster1(i); J1=J1+norm(

23、y-mean1)2; end for i=1:N(2) y=x1(cluster2(i),x2(cluster2(i),x3(cluster2(i); J2=J2+norm(y-mean2)2; end for i=1:N(3) y=x1(cluster3(i),x2(cluster3(i),x3(cluster3(i); J3=J3+norm(y-mean3)2; end Je=J1+J2+J3; before1=cluster1; %把当前的聚类情况存储下来，待会与c均值法后的结果比较 before2=cluster2; before3=cluster3; % % C均值法 % times

24、=0; %记录循环次数的变量 changed=0; %标志位 用来判断循环中是否有改变 i=1; while i21 times=times+1; %每次循环times都加1 y=x1(i),x2(i),x3(i); if ismember(i,cluster1) % 如果i在第一聚类里 9 rou1=N(1)/(N(1)-1)*norm(y-mean1)2; rou2=N(2)/(N(2)+1)*norm(y-mean2)2; rou3=N(3)/(N(3)+1)*norm(y-mean3)2; if rou2=min(rou1 rou2 rou3) % 如果rou2小于rou1 和rou3

25、就把该元素扔到第二聚 类里 N(2)=N(2)+1; cluster2(N(2)=i; %把i添加到第二聚类 N(1)=N(1)-1; cluster1(find(i=cluster1)=; %把i从第一聚类删除 changed=1; elseif rou3=min(rou1 rou2 rou3) % 如果rou3小于rou1 和rou2就把该元素扔到第三聚类里 N(3)=N(3)+1; cluster3(N(3)=i; %把i添加到第二聚类 N(1)=N(1)-1; cluster1(find(i=cluster1)=; %把i从第一聚类删除 changed=1; end elseif is

26、member(i,cluster2) %如果i在第二聚类里 rou1=N(1)/(N(1)+1)*norm(y-mean1)2; rou2=N(2)/(N(2)-1)*norm(y-mean2)2; rou3=N(3)/(N(3)+1)*norm(y-mean3)2; if rou1=min(rou1 rou2 rou3) % 如果rou1小于rou2和rou3 就把该元素扔 到第一聚类里 N(1)=N(1)+1; cluster1(N(1)=i; %把i添加到第一聚类 N(2)=N(2)-1; cluster2(find(i=cluster2)=; %把i从第二聚类删除 changed=1;

27、 elseif rou3=min(rou1 rou2 rou3) % 如果rou3小于rou2和rou1 就把该元素扔到第三聚 类里 N(3)=N(3)+1; cluster3(N(3)=i; %把i添加到第三聚类 N(2)=N(2)-1; cluster2(find(i=cluster2)=; %把i从第二聚类删除 changed=1; end else %如果i在第三聚类里 rou1=N(1)/(N(1)+1)*norm(y-mean1)2; rou2=N(2)/(N(2)+1)*norm(y-mean2)2; rou3=N(3)/(N(3)-1)*norm(y-mean3)2; if r

28、ou1=min(rou1 rou2 rou3) % 如果rou1小于rou2和rou3 就把该元素扔到第一 聚类里 N(1)=N(1)+1; cluster1(N(1)=i; %把i添加到第一聚类 10 N(3)=N(3)-1; cluster3(find(i=cluster3)=; %把i从第三聚类删除 changed=1; elseif rou2=min(rou1 rou2 rou3) % 如果rou2小于rou1和rou3 就把该元素扔到第二聚类里 N(2)=N(2)+1; cluster2(N(2)=i; %把i添加到第三聚类 N(3)=N(3)-1; cluster3(find(i=

29、cluster3)=; %把i从第二聚类删除 changed=1; end end i=i+1; if changed %如果本次循环发生改变 mean1=mean(x1(cluster1),mean(x2(cluster1),mean(x3(cluster1); %重新计算聚类的均值 mean2=mean(x1(cluster2),mean(x2(cluster2),mean(x3(cluster2); mean3=mean(x1(cluster3),mean(x2(cluster3),mean(x3(cluster3); i=1; %重置循环指示变量，即只要发生改变就从i=1开始重新循环

30、changed=0; %重置改变指示 end end J1a=0; %计算c均值法后的误差平方和 J2a=0; J3a=0; for i=1:N(1) y=x1(cluster1(i),x2(cluster1(i),x3(cluster1(i); J1a=J1a+norm(y-mean1)2; end for i=1:N(2) y=x1(cluster2(i),x2(cluster2(i),x3(cluster2(i); J2a=J2a+norm(y-mean2)2; end for i=1:N(3) y=x1(cluster3(i),x2(cluster3(i),x3(cluster3(i)

31、; J3a=J3a+norm(y-mean3)2; end Jea=J1a+J2a+J3a; 模糊模糊 C 均值法均值法 %模糊 C-均值算法 3 个聚类 clear clc load data2012_5_1 % data2012_5_1内存有表1的数据 11 b=2; N(1)=0; N(2)=0; N(3)=0; m1=0 0 0; %初始聚类均值 m2=1 1 1; m3=-1 0 2 ; % 初始分类 for i=1:20 tmp=x1(i),x2(i),x3(i); %读入一个数据存在 tmp 中 dist(1)=norm(m1-tmp); %分别计算该数据与三个均值的距离 dis

32、t(2)=norm(m2-tmp); dist(3)=norm(m3-tmp); distmin=find(min(dist)=dist); %找出 dist 最小值的下标 1 or 2 or 3 N(distmin)=N(distmin)+1; if distmin=1 cluster1(N(distmin)=i; elseif distmin=2 cluster2(N(distmin)=i; else cluster3(N(distmin)=i; end end %循环结束后 N(1)存的是第一聚类的元素数，同理 N(2)、N(3) mean1=mean(x1(cluster1),mean

33、(x2(cluster1),mean(x3(cluster1); %每个聚类的均值 mean2=mean(x1(cluster2),mean(x2(cluster2),mean(x3(cluster2); mean3=mean(x1(cluster3),mean(x2(cluster3),mean(x3(cluster3); % 模糊 c 均值法 changed=1; times=0; while(changed) times=times+1; old1=mean1; %记录当前均值 old2=mean2; old3=mean3; % 计算隶属度函数 for i=1:20 x=x1(i),x2

34、(i),x3(i); deno=1/norm(x-mean1)2+1/norm(x-mean2)2+1/norm(x-mean3)2; %分母 miu1(i)=(1/norm(x-mean1)2)/deno; miu2(i)=(1/norm(x-mean2)2)/deno; miu3(i)=(1/norm(x-mean3)2)/deno; end 12 %用当前隶属度函数更新各类聚类中心 numer=0 0 0; deno=sum(miu1.2); %计算 mean1 的分母 for i=1:20 %计算 mean1 的分子 x=x1(i),x2(i),x3(i); numer=(miu1(i

35、)2)*x+numer; end mean1=numer/deno; numer=0 0 0; deno=sum(miu2.2); %计算 mean2 的分母 for i=1:20 %计算 mean2 的分子 x=x1(i),x2(i),x3(i); numer=(miu2(i)2)*x+numer; end mean2=numer/deno; numer=0 0 0; deno=sum(miu3.2); %计算 mean3 的分母 for i=1:20 %计算 mean3 的分子 x=x1(i),x2(i),x3(i); numer=(miu3(i)2)*x+numer; end mean3=numer/deno; if (norm(old1-mean1)1e-8) count=count+1; else while a*M(:,i)length(X1)+length(X2) %连续N次为做出修正， 表明现分类面对所有样本正确， 置1flag flag=1; end end i=min(X1 X2):0.01:max(X1 X2); U=-a(1)/a(3)-a(2)/a(3).*i; plot(X1,Y1,.,X2,Y2,r*,i,U,k) 23 legend(W1,W2,Perceptron) 样本产生函数样本产生