3种聚类算法性能比较分析

1、 收稿日期20090319作者简介张丽芳(1981,女,2003年大学毕业,硕士,助教,现主要从事数据分析方面的研究工作。3种聚类算法性能比较分析张丽芳(长江大学信息与数学学院数学系,湖北荆州434023摘要对3种著名的聚类算法进行了对比分析,在多类高维UCI 数据集上进行了试验,最后对试验结果进行了分析。关键词聚类;K 2M EANS 算法;COBWEB 算法;DENCL U E 算法中图分类号TP311文献标识码A 文章编号16731409(200902N2500213种算法简介聚类算法众多,其中著名的算法有K 2M EANS 算法、COBWEB 算法和D ENCL U E 算法。K 2M

2、 EANS 算法最早由MacQueen 提出来的。在这个算法中,每个类用该类中现有对象的平均值表示。K 2M EANS 算法非常简单,在解决一些实际问题时,也很容易完成。该算法在处理致密型和超球体型的聚类中效果很好。由于其时间复杂度是O (N kt (其中,N 为样本数;k 为聚类数;t 为迭代次数,因此对处理大型数据集也是相对可伸缩和高效率的1。COBWEB 算法是一个通用且简单的增量式的概念聚类算法。COBWEB 算法用分类树的形式来表现层次聚类。为了利用分类树来对一个对象进行分类,需要利用一个匹配函数来寻找“最佳的路径”,COBWEB 算法用了一种启发式的评估衡量标准,将分类效用CU (

3、category utility 来指导树的建立过程。该算法能够自动调整类的数目的大小,而不像其他算法那样自己设定类的个数,但COBWEB 算法中的2种操作对于记录的顺序很敏感,为了降低这种敏感性,该算法引入2个附加操作:合并和分解。可以根据CU 值来确定合并和分解操作,从而达到双向搜索的目的。COBWEB 算法的缺点是:它假设每个属性上的概率分布是彼此独立的,由于属性间经常是相关的,这个假设并不总是成立。这给该方法带来一定的局限性。聚类的概率分布表示更新和存储聚类相当繁复,因为时间和空间复杂度不只依赖于属性的数目,还取决于每个属性的值的数目,所以当属性有大量的取值时情况变得很复杂。分类树对于

4、偏斜的输入数据不是高度平衡的,它可能导致时间和空间复杂性的剧烈变化2。DENCLU E (Density 2based Clustering 算法是一个基于一组密度分布函数的聚类算法。DENCLU E 算法的优点是:它有一个坚实的数学基础,概括了其他的聚类方法,包括基于分割的、层次的以及基于位置的方法。对于有大量“噪声”的数据集合,它有良好的聚类特性。对高维数据集合的任意形状的聚类,它给出了简洁的数学描述。它使用了网格单元,只保存实际包含数据点的网格单元的信息。它以一个基于树的存取结构来管理这些单元,因此比其他算法(如DBSCAN 算法等的速度要快。DENCL U E 算法的缺点是:要求对密度

5、参数和噪声阈值进行仔细的选择,因为这样的参数选择可能明显地影响聚类结果的质量,即对参数比较敏感3。23种算法试验211试验数据表1数据集G lass 的描述表数据集样本总数类别数属性数G lass21469本试验所使用的数据集Glass 从UCI 数据库(国际通用机器学习训练数据库中获得,该数据集的详细描述见表1。从表1中可看出,该数据集是多类高维数据。052长江大学学报(自然科学版2009年6月第6卷第2期:理工Journal of Yangtze U niversity (N at Sci EditJ un 12009,Vol 16No 12:Sci &Eng 212试验结果说明表

6、2G lass 的聚类效果比较表所用算法聚错的样本数平均准确度K 2MEANS 750159262COBWEB 1130160626DENCL U E830153228如表2所示,聚错的样本数指总的聚错的样本数,即各类中聚错的样本数的和。平均准确度的计算方法如下:设原数据集有k 个类,用C i 表示第i 类,n i 为C i 这类中样本的个数,m i 为C i 中聚类正确的个数,则m i /n i 为类C i 中的精度(i =1,k 。设平均准确度为P ,那么P 由如下公式给出:P =1k6ki =1m i /n i (1213试验结果分析K 2M EANS 算法难以消除噪声的影响。另外,该算

7、法初始聚类中心的随机选取,可能会陷入局部最优解,而难以获得全局最优解。诸多的因素导致了K 2M EANS 算法的聚类效果不很理想。COBWEB 算法假设每个属性上的概率分布是彼此独立的,由于属性间经常是相关的,这个假设并不总是成立的,这给该方法带来一定局限性。这个试验中的数据维数是9维,COBWEB 算法的这一缺点或多或少地影响了聚类的准确度。DENCL U E 算法对于有大量“噪声”的数据集合,有良好的聚类特性。该算法处理高维数据集合的能力比较高。但是DENCL U E 算法对参数比较敏感,这可能是出现聚类精度不高的原因。214性能比较3种算法的性能比较见表3。表33种算法性能比较表算法类型

8、算法效率可伸缩性适合的数据类型发现的聚类形状对领域知识的依赖性对噪声的敏感程度对输入数据顺序的敏感性处理高维数据的能力K 2MEANS 基于函数最优O (kN t 较高数值型凸状、球状类大敏感敏感较低COBWEB 基于模型与概率分布有关低任意任意小一般一般低D ENCL U E基于密度较快一般数值型凸状、球状类大不敏感一般高3结语笔者对3种聚类方法进行了简单的介绍,然后针对3种算法在相同的数据上进行了试验,最后根据试验结果比较了这3种方法的优劣。在表3中可以看出3种算法在各个性能上有较大差异。有关聚类算法及其应用还有许多未解之处,有待进一步研究和探索。参考文献1MacQueen J 1Some met hods For classification and analysis of multivariate observations J 1Proc 5t h Berkeley Symp Mat h Statist ,Prob ,1967,(1:28129712Jiawei H ,Michelin K 1Data mining :Concept s and techniques M 1Beijing :Beijing Higher Education Press ,200113Berry M ,Linoff G