《数据挖掘层次聚类算法研究综述》由会员分享，可在线阅读，更多相关《数据挖掘层次聚类算法研究综述（4页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘层次聚类算法研究综述摘 要 聚类问题是数据挖掘中的重要问题2，是一种非监督的学习方法。分层聚类技 术在图像处理、入侵检测和生物信息学等方面有着极为重要的应用，是数据挖掘领域的研究 热点木文总结了分层聚类算法技术的研究现状，分析算法性能的主要差异，并指岀其 今后的发展趋势。关键词 层次聚类，数据挖掘，聚类算法Review of hierarchical clustering algorithm in Data MiningAbstract Clustering problem of data mining is one of important issues, it is a kind
2、of unsupervised learning methods. Stratified cluster tech no logy in image processi ng, intrusion detection and bioinformatics has extremely important application and is data mining area of research one of the hotspots. This paper summarizes the layered clustering algorithm technology research, anal
3、yzes the main difference arithmetic performance, and pointed out the future development trendKeywords Hierarchical clustering, Data mining, Clustering algorithm1引言随着计算机技术的发展，信息数据越来越多，如何从海量数据中提取对人们有价值的 信息已经成为一个非常迫切的问题。由此产生了数据挖掘技术，它是一门新兴的交叉学科， 汇集了来自机器学习、模式识别、数据库、统计学、人工智能等备领域的研究成果。聚类分 析是数据挖掘中的一个重要研究领域。
4、它在图像处理、入侵检测和生物信息学等方面有着极 为重要的应用。数据挖掘是从大量数据中提取出可信、新颖、有效并能被人理解的模式的 高级处理过稈。其日标是从数据库中发现隐含的、有意义的知识。聚类分析作为一个独立 的工具來获得数据分布的情况，是数据挖掘的一个重要研究分支。在数据挖掘领域，研究工作己经集中在为大型数据库的有效和实际的聚类分析寻找适 当的方法。活跃的主题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有 效性，高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。迄今为 止，人们己经提出了很多聚类算法，它们可以分为如下几类：划分方法、层次方法、基 于密度的方法、基
5、于网格的方法和基于模型的方法，这些算法对于不同的研究对象各有优 缺点。在聚类算法当中，划分方法和层次方法是最常见的两类聚类技术，其中划分方法具 有较高的执行效率，而层次方法在算法上比较符合数据的特性，所以相对于划分方法聚类的 效果比较好。111层次聚类算法和基于划分的K-Means聚类算法是实际应用中聚类分析的支柱，算法简 单、快速而且能有效地处理大数据集。层次聚类方法是通过将数据纽织为若干纽并形成一个 相应的树来进行聚类的。根据层是|底而上还是El顶而下形成。一个完全层次聚类的质量由 于无法对己经做的合并或分解进行调報而受到煤响。但是层次聚类算法没有使用准则函数， 它所潜含的对数据结构的假设
6、更少，所以它的通用性更强。2基于层次的聚类算法2.1凝聚的和分裂的层次聚类层次聚类是聚类问题研究中一个重要的纽成部分。分层聚类的基本原则可以表述为：如 果输入n个数据点(或数集)，我们定义n个数簇，其中每个簇含一个数据。确定距离(簇与 簇Z间的距离可以通过很多的方法来定义，最常用的是单连接度量。其定义两个簇Z间的距 离为一个簇中所有成员与另一簇中所有成员Z间的最短距离。)层次化聚类算法可以进一步地分为两类：凝聚和分裂。凝聚算法：在毎层选择两个最相似的簇被合并，合并示的簇在更高层参与类似的合并。分裂算法：它首先把敕个数据集看成一个簇，然后依据数据集的特性在每一层分成越来 越小的簇。非层次化方法的
7、聚类算法也有很多，其中，K-Means算法是最经典的，还有 K-Means的变种。层次化聚类算法就是将数据对象组成一棵聚类的树。根据层次分解是自底向上生成还是 顶向下生成，层次的聚类方法可以细分为凝聚的和分裂的层次聚类。凝聚的层次聚类：凝聚的层次聚类是白底向上的策略。首先将每个对象作为一个类，然 麻合并这些原子类为越来越大的类，氏到所有的对彖都在一个类中，或者某个终结条件被满 足。分裂的层次聚类是种自顶向下的策略与凝聚的层次聚类相反，它首先将所有对象置于一 个类中，然后逐渐细分为越來越小的类，直到每个对彖自成一类，或者达到了某个终结条件, 例如达到了某个希望的类数目，或者两个最近的类Z间的距离
8、超过了某个闽值。绝大多数聚 类方法属于这一类，它们只是在簇间相似度的定义有所不同。分裂的层次聚类：这种白顶向下的策略与凝聚的层次聚类相反，它首先将所有对象置于 一个簇中，然示逐渐细分为越來越小的簇，直到每个对彖自成一簇，或者达到了某个终止条 件，例如达到了某个希望的簇数目，或者两个最近的簇Z间的距离超过了某个阀值。层次化 聚类方法尽管简单，但如何恰当地选择合并或分裂点，是个很困难的工作，这样的选择是非 常关键的，因为一旦一组对象被合并或者分裂，下一步的处理将在新生成的簇上进行。已做 的处理不能被撤消，聚类之间也不能交换对象。如果在某一步没有很好的选择合并或者分裂 的决定，可能会导致低质量的聚类
9、结果。而且，这种聚类方法不具行很好的可伸缩性，因为 合并或者分裂的决定需耍检查和估算大量的对象或簇。2.2改进的层次聚类算法基本思想按照原层次聚类算法，当依照最小距离d (i, j)合并了第i和第j簇后，必须重新计算 新合并的簇d (i, j)和原有簇的距离,按照最小距离的计算方法,d(k), (r, s)=mind(k), (r), d(k), (s),其中d(k),(!)与d(k), (s)来源于初始化的距离矩阵,也就是说d(k), (r, s)的值必然也就是初始化距离矩阵中的某个值，同理，当合并了一个簇示，新的距离矩阵 里的所有值也就都是来源于初始化的距离矩阵，当然新的距离矩阵内的最小值
10、也来源于初始 化的距离矩阵。层次聚类算法是按照最短距离法来进行层次聚类的，当第一次合并了其中最小的一个 d(i, j)示，产生了新的距离矩阵，由于新的距离矩阵中的所有值均来源于初始化的距离矩阵, 再从新的距离矩阵中取最小值，那么这个最小值必定是除了第一次合并后的最小值外，初始 化距离矩阵中的次小值。也就是说，假定我们合并掉了初始化距离矩阵中的最小值后，下一 个要合并的必定就是初始化距离矩阵中的次小值，依次递推下去，直到所有的簇都被合并完 为止。2.3改进的层次聚类算法改进层次算法的聚类质最的一个主要方向是将层次聚类和莫他的聚类技术进行集成，形 成多阶段聚类，许多学者在基于多阶段聚类方法的思想Z
11、上提出了几种经典的层次聚类方法 的改进算法。这里主要讲BIRCH算法，它首先用树结构对对象进行层次划分，然后采用其 他的聚类算法对聚类结果进行求精。4BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法是一个集成的层 次聚类方法。它包含两个重要概念：聚类特征(CF)和聚类特征树(CF tree),它们用于概括聚类描述。这些结构辅助聚类方法在人型数据库中取得更快的速度和可伸缩性。BIRCH算法 对增量或动态聚类也非常有效。一个聚类特征CF是一个三元组，给出了对象子聚类的信息 的汇总描述。假设某个了聚类中有N个d
12、维数据或对彖。则该子聚类的CF=(N, LS, SS) 其中，N为该了聚类所含对象个数；LS为这N个点的和，SS为数据点的平方和。聚类特征基木上就是对给定了聚类统计信息的总结。它包含了聚类计算和空间存储利用 所需要的关键信息。如图2.1所示，一个CF树是高度平衡的树，它存储了层次聚类的聚类特征。树中的非 叶子节点有后代或“孩子”，它们存储了其孩子的CF的总和，即汇总了关于其孩子的聚类 信息。一个CF树有两个参数：分支因了 B和阈值T。分支因了定义了每个非叶了节点孩了 的最大数目，而阈值参数给出了存储在树的叶了节点中的了聚类的最大肓径。这两个参数直 接煤响了结果树的大小。根第一层图2. 1 CF
13、树示意图BIRCH方法工作主要包括两个阶段：阶段一：BIRCH扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的 多层压缩，试图保留数据内在的聚类结构。阶段二：BIRCH采用某个聚类算法对CF树的叶了节点进行聚类。在阶段一，随着对彖 被插入，CF树被动态地构造。所以这个方法支持增量聚类。一个对彖被插入到最近的叶了 条目(了聚类)。如果在插入后存储在叶子节点中的子聚类的直径大于阈值。那么该叶子节点 (及可能有其他节点)被分裂。新对象插入后，关于该对象的信息向着树根传递。通过修改阈 值，CF树的大小可以改变。如果存储CF树需要的内存大于主存的大小，可以定义一个较 小的阈值，并重建CF树
14、。重建过程从旧树的叶了节点建造一个新树。这样，重建树的过稈 不需要重读所有的对彖。因此，为了建树，貝需读一次数据。BIRCH采用一些启发式的规 则和方法，通过额外的数据扫描来处理孤立点和改进CF树的质量。CF树建好后，可以在 阶段二被用于任何聚类算法。BIRCH试图利用可用的资源來生成最好的聚类结果。给定有限的主存，一个重要的考 虑是最小的I/O时间。BIRCH采用了一种多阶段聚类技术：数据集合的单遍扫描产生了一个 基木的聚类，一遍或多遍的额外扫描可以进一步地改进聚类质星。这个算法的计算复杂性是 0(n),这里的n是对象的数目。3总结现有聚类算法的分类研究还需要继续深入，在数据挖掘的理论及应用
15、实践小，人们己经 提出了许多聚类算法，但到H前为止仍没冇普遍适川的聚类算法，每种方法在具有某种优点 的同时也存在着某些不足，可能适合于处理某些问题却无法处理另一类情况。这就给人们的 选择使用带来了不便，往往会出现血对浩瀚的聚类算法，却不知道哪个可用的困境。因此, 需要对现有聚类算法木身进行分类处理为用户的选择使川提供理论指导，这也许比单纯的提 出聚类新算法更有现实意义。参考文献1 王里.并行层次聚类技术研究,硕士学位论文.湖南大学.2006. 122 赵法信，王国业.数据挖掘中聚类分析算法研究通化师范学院学报，2005 (26)3 段明秀.层次聚类算法的研究与应用,硕士学位论文.中南大学.2009. 54 汤效琴，戴汝源.数据挖掘中聚类分析的技术方法.微计算机信息，2003 (19)5 李潮健.一种并行分层聚类算法的研究和实现，硕士学位论文.湘潭大学.2007. 11
