模式识别课程报告.docx

模式识别实验报告学生姓名：班 学 号：指导老师：机械与电子信息学院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个中引力最小的一