模式识别课程报告

1、模式识别实验报告学生姓名：班学号：指导老师：机械与电子信息学院2014年6月基于K-means算法的改进算法方法一：层次K均值聚类算法在聚类之前，传统的K均值算法需要指定聚类的样本数，由于样本初始分布 不一致，有的聚类样本可能含有很多数据，但数据分布相对集中，而有的样本集却 含有较少数据，但数据分布相对分散。因此，即使是根据样本数目选择聚类个数， 依然可能导致聚类结果中同一类样本差异过大或者不同类样本差异过小的问题，无 法得到满意的聚类结果。结合空间中的层次结构而提出的一种改进的层次K均值聚 类算法。该方法通过初步聚类，判断是否达到理想结果，从而决定是否继续进行更 细层次的聚类，如此迭代执行，

2、生成一棵层次型K均值聚类树，在该树形结构上可 以自动地选择聚类的个数。标准数据集上的实验结果表明，与传统的K均值聚类方 法相比，提出的改进的层次聚类方法的确能够取得较优秀的聚类效果。设X = x1，x2，xi，xn 为n个Rd空间的数据。改进的层次结构 的K均值聚类方法(Hierarchical K means)通过动态地判断样本集X当前聚类是 否合适，从而决定是否进行下一更细层次上的聚类，这样得到的最终聚类个数一定 可以保证聚类测度函数保持一个较小的值。具体的基于层次结构的K均值算法：步骤1选择包含n个数据对象的样本集X = xl, x2,，xi,，xn，设 定初始聚类个数k1，初始化聚类目

3、标函数J （0） =0.01，聚类迭代次数t初始化为 1，首先随机选择k1个聚类中心。步骤2衡量每个样本xi （i = 1，2，n）与每个类中心 （ j = 1， 2,，k）之间的距离，并将xi归为与其最相似的类中心所属的类，并计算当前聚 类后的类测度函数值J （1）。步骤3进行更细层次的聚类，具体步骤如下：步骤3. 1根据式（5）选择类半径最大的类及其类心ci : ri = max |xj - ci|， j = 1，2，ni 且 xj 属于 Xj（5）步骤3.2根据距离公式（1）选择该类中距离类ci最远的样本点xi1，然后 选择该类中距离xi1最远的样本点xi2。步骤3.3以这两个点和其他聚

4、类中心作为初始聚类中心重新做k均值聚类。步骤4设e = J （t） - J （t - 1）/J （t - 1），若e ，则返回步骤3 继续迭代执行；否则算法结束，输出聚类结果X ?X1，X2，Xk。实验结果及分析文中作者为比较层次K均值聚类算法中类个数选择方法与传统基于随机选择 聚类个数的K均值算法的有效性，在四个标准数据集上（见表1）进行了实验，并 与传统的经典随机选择初始聚类中心的K-means方法作了比较。表I实弱数据集数据集训练集个数数据维数ASL25022Banana5 5002Breast _ca.ncer2 0009Spambase1 73157由图1可以看出，采用传统的K均值聚

5、类方法，数据集ASL在聚类达到25类 后，聚类衡量函数值的减小变得平缓，因此，该数据集聚为25类是比较合适的同 理，对于数据集Banana、Breast_cancer、Spambase来说，最佳聚类个数分别为 20、25、30。由于采用传统K均值聚类方法开始无法得到最优的聚类个数，但 是，采用本文提出的方法可以自动地获取聚类的个数，最终在四个数据集上到的聚 类个数分别为28、22、24、31，与传统K均值方法多次实验比较得到的最优聚类个数是一致的。0.80,1!11ASL -k），聚类中心初始化完毕转到步骤；（选择其他聚类中心）利用公式（5）找到最小点xi为新的聚类中心， q=q+1，转到步骤

6、；K-Mean聚类）利用已经获得聚类中心m1， m2，mk，进行K-Means 聚类。实验结果及分析为了证明DWKM算法有效性，作者对K-Means和DWKM算法做对比实验对K- Means聚类算法和DWKM算法的结果，可以看出DWKM算法不仅很好地解决了 K- Means的随机性，而且从总体精度Pc和运行时间上看，降低了错误率，提高了算 法的效率。为了证明加权对聚类结果的影响，分别取不同的加权系数，通过测试数 据Iris，说明加权能够得到更好的聚类结果。从表可以看出，通过加权系数可以得到比较好的聚类结果，并且从MSE 上可 以出，当MSE小的时候其总分类精度Pc不是最优解，因此算法准则函数M

7、SE有待 改进。表3 TAVKM加权系数不同对比加权系致垃代次数聚秃间 距离i聚髡内部距禺1 S1.0,1.s1. fl278. P4O85 7H2132600. SS67o L。一 LU.2rU. 65B5.391 I5.4W499 25030. % 670. 1 ,0. 1,2r(L 14B5.39115.409499. 25030.0. 1.0. 1,0.2rI. 8586. 30705.44166幻】0.听000. L,0. 1,0,2rW4瓯 A0705.441666710, 96000. L,0. 1,t).孔o. a4S5. 48$05.373299. 143130的财0. 1,

8、0. 1 r().3r.s485. 4KS05. J782yg. 20. %(110. 1.0. 1,0,c. 52财.13015.4637就 73640.9533方法三：基于集对分析的遥感图像K 一均值聚类算法基于欧式距离的K 均值聚类算法是一种硬分类(把每个待辨识的对象严格 地划分到某个类中)方法，面对具有不确定性和混合像元特征的遥感图像数据，传 统K 一均值聚类算法很难得到满意的分类结果。为解决这一难题，将集对分析 (set pair analysis， SPA)理论推广到遥感图像聚类算法，通过引入一个能统一 描述同一性、差异性和对立性的同异反(identical discrepancy

9、 contrary， IDC) 联系度，提出了基于IDC联系度的改进的K 均值聚类算法。该方法克服了传统K 一均值算法硬分类的缺陷，可以有效地提高遥感图像聚类精度。对Landsat5 TM卫 星数据的聚类分析实验表明，在含有混合像元的遥感图像地物覆盖分类中，改进的 K均值聚类方法的分类效果要优于传统K 均值聚类方法。该算法的具体实现步骤如下：设定输入数据集X = ( x1，x2，x n，聚类簇个数K，差异度系数i， 最大循环次数I；输出为满足“误差平方和最小”标准的K个聚类Ck。1，步骤一初始化。令1=1,随机选取K个初始类簇中心mk (1), k =2,K；步骤二 计算IDC联系度。计算待分

10、类样本xl与聚类中心mk的IDC联系度 ulk；步骤三 分配xl。计算样本点xl与这K个簇中心之间的IDC距离Dlk，如果 满足 Dlk = min ( Dlk, k = 1,2，K ，则 xleCk；步骤四 修正簇中心Ck。令I=I + 1,重新分配K个新的聚类中心，即叫)=十M叫=1注，m k = 2步骤五计算误差平方和J,即J-1 (8)jfc M 1 J Cg.步骤六收敛判断。如果J值收敛，则返回mk( I) , k = 1,2，K;算法 结束；否则，返回步骤二。实验结果及分析为了评价改进算法的聚类性能，选取一景多光谱遥感图像作为实验数据，并 与传统K 均值算法进行比较。通过作者的对比

11、我发现，与传统K均值聚类方法 相比，利用基于SPA改进的K 均值聚类方法对含混合地物的土地覆盖能得到更精 确的划分。善2 却境埃ti 遥亲条站累Clirlcm? n| inidilnul K -mrarp h勒rMhinttti息UMHEK耳如1响SiCccd1 0B43. 11g7k5i0(iK44|项1Dl75lii. WtWTtIIKKA2. H企g7.71iw1a2.v4. hitt*o424a.1：MS5. nnt10732?3.HHlVIfiE 旬III?131 151辟1 E1 M221911 g4. ,骤1别MM2.44.Mfl.Z2 4根据表2及表3,发现对于建筑用地、植被稀

12、疏地、草地和林地的错分、漏 分误差，基于SPA的改进算法要低于传统K 均值算法；对于总体分类精度和 Kappa系数，基于SPA的改进算法明显高于传统K均值算法。改进的K 均值聚类方法利用同异反（IDC）联系度来度量样本间的相似性， 尝试解决传统K 均值算法在含有混合像元的遥感图像地物覆盖分类中由硬分类 造成分类精度不高的问题。实验结果显示，在传统K均值聚类算法面对具复杂特 征的遥感图像数据无法获得较好聚类效果时，基于SPA改进的K均值聚类算法仍 然能够获得较好的聚类效果。参考文献【1】胡伟，改进的层次K均值聚类算法，计算机工程与应用，2011-10-24【2】万广通；王行风，基于密度的加权K-Means算法，测绘科学，2013-07- 20【3】谢相建；赵俊三；陈学辉，袁思，基于集对分析的遥感图像K 均值聚 类算法，国土资源遥感，2012-12-15【4】王晓丹，高晓峰，姚旭等，SVM集成研究与应用J,空军工程 大学学报：自然科学版，2012-2-13【5】武佳薇，李雄飞，孙涛等，邻域平衡密度聚类算法J,计算机研究与 发展，2010心得体会学习了模式识别这门课程，我学会了利用Matlab软件对遥感图像进行简单的 处理，可为遥感影像的判读提供良好的条件，从而提高判读精度，还学会了使用软 件ENVI，对遥感图像进行数据处理、图像分类等