集X = {x1，x2，，xi，，xn}，设定初始聚类个数k1，初始化聚类目标函数J (0) =，聚类迭代次数t初始化为1，首先随机选择k1个聚类中心。
步骤2 衡量每个样本xi (i = 1，2，，n)与每个类中心cj ( j = 1，2，，k)之间的距离，并将xi归为与其最相似的类中心所属的类，并计算当前聚类后的类测度函数值J (1) 。
步骤3 进行更细层次的聚类，具体步骤如下： 步骤 根据式（5）选择类半径最大的类及其类心ci ：ri = max ||xj - ci||，j = 1，2，，ni且xj属于Xj（5） 步骤 根据距离公式（1）选择该类中距离类ci最远的样本点xi1，然后选择该类中距离xi1最远的样本点xi2。 步骤 以这两个点和其他聚类中心作为初始聚类中心重新做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－均值聚类算法。该方法
相关推荐：
loading