K均值聚类算法优缺点.doc

(3-1)其中,是类中数据对象的均值,即,(j=1,2,…,n),是K个聚类中心,分别代表K个类。K-means算法的工作原理:算法首先随机从数据集中选取K个点作为初始聚类中心,然后计算各个样本到聚类中的距离,把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心,如果相邻两次的聚类中心没有任何变化,说明样本调整结束,聚类准则函数已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确,就要调整,在全部样本调整完后,再修改聚类中心,进入下一次迭代。如果在一次迭代算法中,所有的样本被正确分类,则不会有调整,聚类中心也不会有任何变化,这标志着已经收敛,因此算法结束。算法描述如下:算法:K-means。划分的K-means算法基于类中对象的平均值。输入:类的数目K和包含N个对象的数据库。方法:①对于数据对象集,任意选取K个对象作为初始的类中心;②根据类中对象的平均值,将每个对象重新赋给最相似的类;③更新类的平均值,即计算每个类中对象的平均值;④Repeat②③;⑤直到不再发生变化。其中,初始聚类中心的选择对聚类结果的影响是很大的,,图a是三个类的实际分布,图b是选取了好的初始聚类中心(+字标记的数据对象)得到的结果。图c是选取不好的初始聚类中心得到的结果,从中可以看到,选择初始聚类中心是很关键的。 a b -means算法的一组对象的聚类算法的数据描述为:把n个向量(j=1,2,…,n)分成c个类(i=1,2,…,c),并求每类的聚类中心,使得非相似性(或距离)指标的目标函数达到最小。当选择第i类中向量与相应聚类中心间的度量为欧几里德距离时,目标函数可以定义为:(3-2)其中是类的目标函数。J值依赖于的几何形状和的位置。可以看出J是样本和聚类中心的函数,样本集X给定的情况下J的值取决于K个聚类中心。J描述n个样本聚类成K个类时所产生的总的误差平方和。显然,若J值越大,说明误差越大,聚类结果越不好。因此,应该寻求使J最小的聚类结果,即在误差平方和准则下的最优结果。这种聚类通常也称为最小方差划分。-means算法的特点——采用两阶段反复循环过程算法,结束的条件是不再有数据元素被重新分配:①指定聚类,即指定数据到某一个聚类,使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。②修改聚类中心。优点:本算法确定的K个划分到达平方误差最小。当聚类是密集的,且类与类之间区别明显时,效果较好。对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为O(NKt),其中N是数据对象的数目,t是迭代的次数。一般来说,K<<N,t<<N。缺点主要有三个:①在K-means算法中K是事先给定的,这个K值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是K-means算法的一个不足。有的算法是通过类的自动合并和分裂,得到较为合理的类型数目K,例如ISODATA算法。关于K-means算法中聚类数目K值的确定在文献[23]中,是根据方差分析理论,应用混合F统计量来确定最佳分类数,并应用了模糊划分熵来验证最佳分类数的正确性