模式识别实验报告
学生姓名：
班 学 号：
指导老师：
机械与电子信息学院
2014年 6月
基于K-means 算法的改进算法
方法一：层次K 均值聚类算法
在聚类之前，传统的K 均值算法需要指定聚类的样本数，由于样本初始分布不一致，有的聚类样本可能含有很多数据，但数据分布相对集中，而有的样本集却含有较少数据，但数据分布相对分散。因此，即使是根据样本数目选择聚类个数，依然可能导致聚类结果中同一类样本差异过大或者不同类样本差异过小的问题，无法得到满意的聚类结果。结合空间中的层次结构而提出的一种改进的层次K 均值聚类算法。该方法通过初步聚类，判断是否达到理想结果，从而决定是否继续进行更细层次的聚类，如此迭代执行，生成一棵层次型K 均值聚类树，在该树形结构上可以自动地选择聚类的个数。标准数据集上的实验结果表明，与传统的K 均值聚类方法相比，提出的改进的层次聚类方法的确能够取得较优秀的聚类效果。
设X = {x1，x2，„，xi ，„，xn }为n 个Rd 空间的数据。改进的层次结构的K 均值聚类方法（Hierarchical K means ）通过动态地判断样本集X 当前聚类是否合适，从而决定是否进行下一更细层次上的聚类，这样得到的最终聚类个数一定可以保证聚类测度函数保持一个较小的值。具体的基于层次结构的K 均值算法： 步骤1 选择包含n 个数据对象的样本集X = {x1，x2，„，xi ，„，xn}，设定初始聚类个数k1，初始化聚类目标函数J (0) =0.01，聚类迭代次数t 初始化为1，首先随机选择k1个聚类中心。
步骤2 衡量每个样本xi (i = 1，2，„，n) 与每个类中心cj ( 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 以这两个点和其他聚类中心作为初始聚类中心重新做k 均值聚类。
步骤4 设ε = J (t) - J (t - 1)/J (t - 1) ，若ε > Δ，则返回步骤3继续迭代执行；否则算法结束，输出聚类结果X {X1，X2，„，Xk}。
实验结果及分析
文中作者为比较层次K 均值聚类算法中类个数选择方法与传统基于随机选择聚类个数的K 均值算法的有效性，在四个标准数据集上（见表1）进行了实验，并与传统的经典随机选择初始聚类中心的K-means 方法作了比较。
由图1可以看出，采用传统的K 均值聚类方法，数据集ASL 在聚类达到25类后，聚类衡量函数值的减小变得平缓，因此，该数据集聚为25类是比较合适的同理，对于数据集Banana 、Breast_cancer、Spambase 来说，最佳聚类个数分别为20、25、30。由于采用传统K 均值聚类方法开始无法得到最优的聚类个数，但是，采用本文提出的方法可以自动地获取聚类的个数，最终在四个数据集上到的聚类个数分别为28、22、24、31，与传统K 均值方法多次实验比较得 到的最优聚类个数是一致的。
方法二：基于密度的加权K-Means 算法
K-Means 算法存在需要输入聚类数目以及对初始聚类中心敏感等缺陷，本文提出了一种基于密度的加权K-Means 聚类算法来初始化聚类中心。该算法定了点的密度函数和聚类中心函数，通过一定评价函数获取聚类中心。该方法获取聚类中心不仅周围密度比较大，而且各个聚类中心之间相关性比较小，从而有效的减少了聚类时间，提高算法效率。称其为基于密度的加权K-Means( Density Weight K-Means，DWKM) 。
原理为：设模式向量样本{ X} = { X1，X2，„，Xn} ，且模式样本集被分为Sc 类，即S1，S2，„，Sc ，Mj 为Sj 均值向量，即
其中Nj 为Sj 的样本数目，则可以定义其准则函数：
而Min( MSE) 为DWKM 算法终止条件，其中‖X －Mj ‖为欧式距离。为了
更好体现每个点密度，定义一个vi 密度函数：
其中dij 为
（4）式中p 为X 的属性数目，kr 为各个属性的权重；显然当vi 很小时，说
明其周围点的密度相对比较大，这样Min(vi)就是一个较好的初始中心。然后假设已经找到q( q＜k) 个聚类中心m1，m2，„，mq ，为了保证剩下聚类中心与已有聚类中心的聚类距离较远，并且周围密度比较大，定义一个聚类中心引力函数fi ：
计算q 个聚类中心对第i 个点的引力，引力越小说明和已经找到的聚类中心关系越小，因此取n 个中引力最小的一个点为下一个聚类中心mq+1，即Min( fi)，i = 1，2，„，n ( 6)通过上述算法可以精确找到Sc 个初始聚类中心，在此基础上进行K-Means 聚类。
具体步骤如下：
①（第一点选择）计算每两个点之间欧式距离，然后按密度函数( 式( 3) ) 计算每个点的密度，选择密度最大的一个点最为第一个聚类中心，设q=1； ②（结束条件）if(q＞k) ，聚类中心初始化完毕转到步骤④；
③（选择其他聚类中心）利用公式( 5) 找到最小点xi 为新的聚类中心，q=q+1，转到步骤②；
④（K-Mean 聚类）利用已经获得聚类中心m1，m2，„，mk ，进行K-Means 聚类。
实验结果及分析
为了证明DWKM 算法有效性，作者对K-Means 和DWKM 算法做对比实验对K-Means 聚类算法和DWKM 算法的结果，可以看出DWKM 算法不仅很好地解决了K-Means 的随机性，而且从总体精度Pc 和运行时间上看，降低了错误率，提高了算法的效率。为了证明加权对聚类结果的影响，分别取不同的加权系数，通过测试数据Iris ，说明加权能够得到更好的聚类结果。
从表可以看出，通过加权系数可以得到比较好的聚类结果，并且从MSE 上可以出，当MSE 小的时候其总分类精度Pc 不是最优解，因此算法准则函数MSE 有待改进。
方法三：基于集对分析的遥感图像K －均值聚类算法
基于欧式距离的K －均值聚类算法是一种硬分类( 把每个待辨识的对象严格地划分到某个类中) 方法，面对具有不确定性和混合像元特征的遥感图像数据，传统K － 均值聚类算法很难得到满意的分类结果。为解决这一难题，将集对分析( set pair analysis，SPA) 理论推广到遥感图像聚类算法，通过引入一个能统一描述同一性、差异性和对立性的同异反( identical discrepancy contrary， IDC) 联系度，提出了基于IDC 联系度的改进的K －均值聚类算法。该方法克服了传统K －均值算法硬分类的缺陷，可以有效地提高遥感图像聚类精度。对Landsat5 TM卫星数据的聚类分析实验表明，在含有混合像元的遥感图像地物覆盖分类中，改进的K －均值聚类方法的分类效果要优于传统K －均值聚类方法。
该算法的具体实现步骤如下:
设定输入数据集X = { x1，x2，„，x n} ，聚类簇个数K ，差异度系数i ，最大循环次数I; 输出为满足“误差平方和最小”标准的K 个聚类Ck 。
步骤一 初始化。令I=1，随机选取K 个初始类簇中心mk （1），k = 1，2，„K ； 步骤二 计算IDC 联系度。计算待分类样本xl 与聚类中心mk 的IDC 联系度μlk ； 步骤三 分配xl 。计算样本点xl 与这K 个簇中心之间的IDC 距离Dlk ，如果满足Dlk = min { Dlk，k = 1，2，„，K } ，则xl ∈Ck ；
步骤四 修正簇中心Ck 。令I = I + 1，重新分配K 个新的聚类中心，即
步骤五 计算误差平方和J ，即
步骤六 收敛判断。如果J 值收敛，则返回mk( I) ，k = 1，2，…，K; 算法结束; 否则，返回步骤二。
实验结果及分析
为了评价改进算法的聚类性能，选取一景多光谱遥感图像作为实验数据，并与传统K －均值算法进行比较。通过作者的对比我发现，与传统K －均值聚类方法相比，利用基于SPA 改进的K －均值聚类方法对含混合地物的土地覆盖能得
到更精确的划分。
根据表2及表3，发现对于建筑用地、植被稀疏地、草地和林地的错分、漏分误差，基于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】王晓丹，高晓峰，姚旭等，ＳＶＭ 集成研究与应用［Ｊ］，空军工程大学学报：自然科学版，2012-2-13
【5】武佳薇，李雄飞，孙涛等，邻域平衡密度聚类算法[J]，计算机研究与发展，2010
心得体会
学习了模式识别这门课程，我学会了利用Matlab 软件对遥感图像进行简单的处理，可为遥感影像的判读提供良好的条件，从而提高判读精度，还学会了使用软件ENVI ，对遥感图像进行数据处理、图像分类等等，学会了通过K-means 算法对遥感图像进行分类，但是过程中遇到了不少问题，比如程序运行的速度过慢等等。由于自身能力的不足，前三次实验在自己的努力和同学的帮助下，我还是圆满的完成了，但是第四次实验对于我来说难度偏大，虽然理解了算法思想但是无法实现。总的来说学习了模式识别，让我对ENVI 产生了兴趣，并且充分认识到了自己的不足，今后我会专心研读书籍资料，不懂的地方向同学学习，增强自己的编程能力。
模式识别实验报告
学生姓名：
班 学 号：
指导老师：
机械与电子信息学院
2014年 6月
基于K-means 算法的改进算法
方法一：层次K 均值聚类算法
在聚类之前，传统的K 均值算法需要指定聚类的样本数，由于样本初始分布不一致，有的聚类样本可能含有很多数据，但数据分布相对集中，而有的样本集却含有较少数据，但数据分布相对分散。因此，即使是根据样本数目选择聚类个数，依然可能导致聚类结果中同一类样本差异过大或者不同类样本差异过小的问题，无法得到满意的聚类结果。结合空间中的层次结构而提出的一种改进的层次K 均值聚类算法。该方法通过初步聚类，判断是否达到理想结果，从而决定是否继续进行更细层次的聚类，如此迭代执行，生成一棵层次型K 均值聚类树，在该树形结构上可以自动地选择聚类的个数。标准数据集上的实验结果表明，与传统的K 均值聚类方法相比，提出的改进的层次聚类方法的确能够取得较优秀的聚类效果。
设X = {x1，x2，„，xi ，„，xn }为n 个Rd 空间的数据。改进的层次结构的K 均值聚类方法（Hierarchical K means ）通过动态地判断样本集X 当前聚类是否合适，从而决定是否进行下一更细层次上的聚类，这样得到的最终聚类个数一定可以保证聚类测度函数保持一个较小的值。具体的基于层次结构的K 均值算法： 步骤1 选择包含n 个数据对象的样本集X = {x1，x2，„，xi ，„，xn}，设定初始聚类个数k1，初始化聚类目标函数J (0) =0.01，聚类迭代次数t 初始化为1，首先随机选择k1个聚类中心。
步骤2 衡量每个样本xi (i = 1，2，„，n) 与每个类中心cj ( 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 以这两个点和其他聚类中心作为初始聚类中心重新做k 均值聚类。
步骤4 设ε = J (t) - J (t - 1)/J (t - 1) ，若ε > Δ，则返回步骤3继续迭代执行；否则算法结束，输出聚类结果X {X1，X2，„，Xk}。
实验结果及分析
文中作者为比较层次K 均值聚类算法中类个数选择方法与传统基于随机选择聚类个数的K 均值算法的有效性，在四个标准数据集上（见表1）进行了实验，并与传统的经典随机选择初始聚类中心的K-means 方法作了比较。
由图1可以看出，采用传统的K 均值聚类方法，数据集ASL 在聚类达到25类后，聚类衡量函数值的减小变得平缓，因此，该数据集聚为25类是比较合适的同理，对于数据集Banana 、Breast_cancer、Spambase 来说，最佳聚类个数分别为20、25、30。由于采用传统K 均值聚类方法开始无法得到最优的聚类个数，但是，采用本文提出的方法可以自动地获取聚类的个数，最终在四个数据集上到的聚类个数分别为28、22、24、31，与传统K 均值方法多次实验比较得 到的最优聚类个数是一致的。
方法二：基于密度的加权K-Means 算法
K-Means 算法存在需要输入聚类数目以及对初始聚类中心敏感等缺陷，本文提出了一种基于密度的加权K-Means 聚类算法来初始化聚类中心。该算法定了点的密度函数和聚类中心函数，通过一定评价函数获取聚类中心。该方法获取聚类中心不仅周围密度比较大，而且各个聚类中心之间相关性比较小，从而有效的减少了聚类时间，提高算法效率。称其为基于密度的加权K-Means( Density Weight K-Means，DWKM) 。
原理为：设模式向量样本{ X} = { X1，X2，„，Xn} ，且模式样本集被分为Sc 类，即S1，S2，„，Sc ，Mj 为Sj 均值向量，即
其中Nj 为Sj 的样本数目，则可以定义其准则函数：
而Min( MSE) 为DWKM 算法终止条件，其中‖X －Mj ‖为欧式距离。为了
更好体现每个点密度，定义一个vi 密度函数：
其中dij 为
（4）式中p 为X 的属性数目，kr 为各个属性的权重；显然当vi 很小时，说
明其周围点的密度相对比较大，这样Min(vi)就是一个较好的初始中心。然后假设已经找到q( q＜k) 个聚类中心m1，m2，„，mq ，为了保证剩下聚类中心与已有聚类中心的聚类距离较远，并且周围密度比较大，定义一个聚类中心引力函数fi ：
计算q 个聚类中心对第i 个点的引力，引力越小说明和已经找到的聚类中心关系越小，因此取n 个中引力最小的一个点为下一个聚类中心mq+1，即Min( fi)，i = 1，2，„，n ( 6)通过上述算法可以精确找到Sc 个初始聚类中心，在此基础上进行K-Means 聚类。
具体步骤如下：
①（第一点选择）计算每两个点之间欧式距离，然后按密度函数( 式( 3) ) 计算每个点的密度，选择密度最大的一个点最为第一个聚类中心，设q=1； ②（结束条件）if(q＞k) ，聚类中心初始化完毕转到步骤④；
③（选择其他聚类中心）利用公式( 5) 找到最小点xi 为新的聚类中心，q=q+1，转到步骤②；
④（K-Mean 聚类）利用已经获得聚类中心m1，m2，„，mk ，进行K-Means 聚类。
实验结果及分析
为了证明DWKM 算法有效性，作者对K-Means 和DWKM 算法做对比实验对K-Means 聚类算法和DWKM 算法的结果，可以看出DWKM 算法不仅很好地解决了K-Means 的随机性，而且从总体精度Pc 和运行时间上看，降低了错误率，提高了算法的效率。为了证明加权对聚类结果的影响，分别取不同的加权系数，通过测试数据Iris ，说明加权能够得到更好的聚类结果。
从表可以看出，通过加权系数可以得到比较好的聚类结果，并且从MSE 上可以出，当MSE 小的时候其总分类精度Pc 不是最优解，因此算法准则函数MSE 有待改进。
方法三：基于集对分析的遥感图像K －均值聚类算法
基于欧式距离的K －均值聚类算法是一种硬分类( 把每个待辨识的对象严格地划分到某个类中) 方法，面对具有不确定性和混合像元特征的遥感图像数据，传统K － 均值聚类算法很难得到满意的分类结果。为解决这一难题，将集对分析( set pair analysis，SPA) 理论推广到遥感图像聚类算法，通过引入一个能统一描述同一性、差异性和对立性的同异反( identical discrepancy contrary， IDC) 联系度，提出了基于IDC 联系度的改进的K －均值聚类算法。该方法克服了传统K －均值算法硬分类的缺陷，可以有效地提高遥感图像聚类精度。对Landsat5 TM卫星数据的聚类分析实验表明，在含有混合像元的遥感图像地物覆盖分类中，改进的K －均值聚类方法的分类效果要优于传统K －均值聚类方法。
该算法的具体实现步骤如下:
设定输入数据集X = { x1，x2，„，x n} ，聚类簇个数K ，差异度系数i ，最大循环次数I; 输出为满足“误差平方和最小”标准的K 个聚类Ck 。
步骤一 初始化。令I=1，随机选取K 个初始类簇中心mk （1），k = 1，2，„K ； 步骤二 计算IDC 联系度。计算待分类样本xl 与聚类中心mk 的IDC 联系度μlk ； 步骤三 分配xl 。计算样本点xl 与这K 个簇中心之间的IDC 距离Dlk ，如果满足Dlk = min { Dlk，k = 1，2，„，K } ，则xl ∈Ck ；
步骤四 修正簇中心Ck 。令I = I + 1，重新分配K 个新的聚类中心，即
步骤五 计算误差平方和J ，即
步骤六 收敛判断。如果J 值收敛，则返回mk( I) ，k = 1，2，…，K; 算法结束; 否则，返回步骤二。
实验结果及分析
为了评价改进算法的聚类性能，选取一景多光谱遥感图像作为实验数据，并与传统K －均值算法进行比较。通过作者的对比我发现，与传统K －均值聚类方法相比，利用基于SPA 改进的K －均值聚类方法对含混合地物的土地覆盖能得
到更精确的划分。
根据表2及表3，发现对于建筑用地、植被稀疏地、草地和林地的错分、漏分误差，基于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】王晓丹，高晓峰，姚旭等，ＳＶＭ 集成研究与应用［Ｊ］，空军工程大学学报：自然科学版，2012-2-13
【5】武佳薇，李雄飞，孙涛等，邻域平衡密度聚类算法[J]，计算机研究与发展，2010
心得体会
学习了模式识别这门课程，我学会了利用Matlab 软件对遥感图像进行简单的处理，可为遥感影像的判读提供良好的条件，从而提高判读精度，还学会了使用软件ENVI ，对遥感图像进行数据处理、图像分类等等，学会了通过K-means 算法对遥感图像进行分类，但是过程中遇到了不少问题，比如程序运行的速度过慢等等。由于自身能力的不足，前三次实验在自己的努力和同学的帮助下，我还是圆满的完成了，但是第四次实验对于我来说难度偏大，虽然理解了算法思想但是无法实现。总的来说学习了模式识别，让我对ENVI 产生了兴趣，并且充分认识到了自己的不足，今后我会专心研读书籍资料，不懂的地方向同学学习，增强自己的编程能力。