Ｋ－ｍｅａｎｓ算法的初始点优化研究.docVIP

Ｋ－ｍｅａｎｓ算法的初始点优化研究 　　摘要：为了克服经典K-means算法对初始聚类中心过分依赖的缺点，该文提出采用竞争神经网络和密度思想对经典k-means算法进行预处理，从而改变经典K-means算法对初始聚类中心的随机选择。实验结果表明，这两种方法是有效的。 　　关键词：聚类；k-means；算法；实验 　　中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)32-1176-02 　　Study on the Initial Centrists of K-means Algorithm 　　MOU Ying1, QUAN Tai-feng2 　　(1.College of Physics and Information Technology, Chongqing Normal University, Chongqing 400047,China;2.Chongqing Communication Institute, Chongqing 400035, China) 　　Abstract: In order to conquer the problem that k-means algorithm depends on initial cluster centrists, so this paper discusses use competition neural network and the mind of density to improve the classic k-means algorithm. The two methods are able to improve the random choice of the initial centrists in the classic k-means algorithm. Experimental results show that the two algorithms are effective. 　　Key words: clustering; K-means; algorithm; experiment 　　 　　1 引言 　　 　　聚类是将数据对象分组成为多个类或簇，在同一个簇中对象之间具有较高的相似度，而不同簇中的对象之间差别较大[1]。在聚类算法中，K-means算法是其中一种最常用最知名的划分方法[2]，它根据事先确定的K值，把样本分为K类，使所有样本到聚类中心的距离平方和最小。现在K-means算法已经应用到各种领域，包括图像和语音数据压缩，用径向基函数网络进行系统建模的数据处理等[3]，但经典K-means算法在运行初期随机产生聚类初始点；如果初始聚类点离数据本身中心较近，则算法运行效率较高否则反之。 　　本文将竞争神经网络和经典K-means算法相结合，提出一种基于竞争神经网络的K-means算法。另外还采用基于密度的思想进行寻找初始聚类中心，从而改变经典K-means算法对初始聚类中心的随机选择。实验结果表明，这两种方法有效的克服了K-means对初始聚类中心的依赖性。 　　 　　2 经典K-means算法 　　 　　经典K-means算法的基本思想是：给定一个包含n个数据对象的数据库，以及要生成的簇的数目k，随机选取k个对象作为初始的聚类中心，然后计算剩余各个样本到每一个聚类中心的距离，把该样本归到离它最近的那个聚类中心所在的类，直到调整结束且聚类平均误差准则函数E已经收敛。 　　K-means算法的具体描述如下： 　　1）任选k个对象特征矢量作为初始聚类中心：z1(0),z2(0)…zk(0)，令t=0 　　2）将待分类的对象特征矢量集{xi}中的对象逐个按最小距离原则分配给k类中的某一类，即 　　如果 　　 　　i=1,2,…N(1) 　　则判xi∈wi(t+1)。 　　其中dij(t)表示xi和wj(t)的中心zj(t)的距离，上角标表示迭代次数。于是产生新的聚类wj(t+1)(j=1,2,…,k)。 　　3）计算重新分类后的各类心 　　 　　式中nj(t+1)为wj(t+1)类中所含对象的个数。 　　因为这一步采取平均的方法计算调整后各类的中心，且定为k类，故称K－均值法。 　　4）如果Zj(t+1)=Zj(t)(j=1,2,…,k)，则结束；否则，t=t+1，转至（2） 　　经典K－means算法的计算复杂度为O(nkt)，其中，n为对象个数，k为聚类个数，t为循环次数。由于它要求用户输入希望产生聚类的数目,而实际中的k值也很难被精确的确定，往往表现为一个模糊的取值区间[4]。并且在经典K-means算法中，首先需要根据初始聚类中心来确定一