文档介绍：各种聚类算法及改进算法的研究作者:王安志李明东李超时间: 2009-3-3 10:59:00 来源: 论文天下论文网论文关键词:数据挖掘;聚类算法;聚类分析论文摘要: 该文详细阐述了数据挖掘领域的常用聚类算法及改进算法, 并比较分析了其优缺点, 提出了数据挖掘对聚类的典型要求, 指出各自的特点, 以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展, 各行各业积累的数据量急剧增长, 如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程, 即把数据对象分成多个类或簇,在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类,能够识别密集和稀疏的区域,发现全局的分布模式, 以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法, 一般可分为基于层次的, 基于划分的, 基于密度的,基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1) 可兼容性:要求聚类算法能够适应并处理属性不同类型的数据。(2) 可伸缩性:要求聚类算法对大型数据集和小数据集都适用。(3) 对用户专业知识要求最小化。(4) 对数据类别簇的包容性: 即聚类算法不仅能在用基本几何形式表达的数据上运行得很好, 还要在以其他更高维度形式表现的数据上同样也能实现。(5) 能有效识别并处理数据库的大量数据中普遍包含的异常值,空缺值或错误的不符合现实的数据。(6) 聚类结果既要满足特定约束条件, 又要具有良好聚类特性,且不丢失数据的真实信息。(7) 可读性和可视性:能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8) 处理噪声数据的能力。(9) 算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解, 各种聚类算法的改进算法也相继提出, 很多新算法在前人提出的算法中做了某些方面的提高和改进, 且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性, 但对其它类型的数据或在其他领域应用中则不一定还有优势。所以, 我们必须清楚地了解各种算法的优缺点和应用范围,根据实际问题选择合适的算法。 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解,可分为凝聚算法和分裂算法。(1) 自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类,然后将这些原子类进行聚合。逐步聚合成越来越大的类,直到满足终止条件。凝聚算法的过程为:在初始时, 每一个成员都组成一个单独的簇, 在以后的迭代过程中, 再把那些相互邻近的簇合并成一个簇, 直到所有的成员组成一个簇为止。其时间和空间复杂性均为 O(n2) 。通过凝聚式的方法将两簇合并后, 无法再将其分离到之前的状态。在凝聚聚类时, 选择合适的类的个数和画出原始数据的图像很重要。(2) 自顶向下分裂聚类方法。与凝聚法相反,该法先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇, 直到每个对象自成一簇, 或者达到了某个终结条件。其主要思想是将那些成员之