对层次聚类算法的改进.pdfVIP

第 21 卷第2 期 湖南理工学院学报(自然科学版) VoL21 No.2 Joumal of Hunan Institute of Science and TechnoloJ1: Y (Natural Sciences) Jun.2008 2∞8 年6 月 对层次聚类算法的改进 段明秀1 ， 2，杨路明1 (1.中南大学信息科学与工程学院，长沙 41ω83; 2.宵酋大学数学与计算机科学学院，湖南省酋 41仰∞) 摘 哥哥:介绍了层次聚类算法的基本思想，在fi..算法的基础上，通过对类问距离进行锁排序从而造免合并类时才在新计算 类问距离，该算法降低了计算的复杂皮.实验表明，改进后的算法在与原算法聚类效果相同的情况下运行速度明显提高 关键诩t 层次聚类算法;预排序;类间距离 中团分类号: TP39 文献标识码:A 文章编号: 1672附5298(2∞8)02幡∞28-02 Improving Hierarchical Clustering Algorithm DUAN Ming-xiu1 YANG Lu-ming l 气 (1.College of Infonnation Science and Engineering ,Central South University ,Changsha 41∞83 ,China; 2. College of Mathematics and Computer Science ,Jishou University ,Jishou 416α泊， China) Ab拙act: The agglomerative hierarchical clustering algorithm is introduced in this paper based on the standard algorithm. Through sorting the distance between clusters to avoid recomputing the distance between cluster咀 we proposed the improved algorithm,which decreases the complexity.Aωording to 伽e experiment. 由e improved algorithm has 伽e same c1ustering results as the standard agglomerative hierarchical clustering algorithm.but the speed is higher. Key words: hierarchical cJustering algorithm; sort; distance between ciuster 引言 数据挖掘是从存储在大型数据库、数据仓库及其他大础信息存储介质中的海最数据中提取人们感兴 趣的知识，这些知识是隐含的、有效的、新颖的、潜在有用的以及最终可以理解的模式的高级过程11J 数 据挖掘中…个非常活胀的研究领域是聚类分析.男起类就是按照事物的某些华属性. j巴事物聚集成类，使樊间 的相似性尽可能小，类内相似性尽可能大[2J 聚类分析有许多算法，屁次聚类分析由于其强壮性和对于输 入记录的顺序不敏感及简单易用而成为聚类分析中的一个广泛应用的算法. 1 层次聚类算法 1. 1 展次赢提常用算法 根据层次分解是自底向上还是自顶向下形成，层次聚类方法可进一步分为凝聚的和分裂的层次聚类. 凝聚的应次聚樊方怯应用得更多，该方法采用自戚向上的策略，首先将每个对象