硕士学位论文开题报告 姓名 类别 研究方向 论文题目 杨海斌 专业名称 □教育硕士 计算机软件与理论 学 号 2008200860 ■国任 □高校教师 □中职教师 □公共管理硕士 □在职申请 入学年月 2008 年 9 月 算法设计与分析 指导老师 赵学锋 一种新的层次聚类算法的研究及应用 记录人 许岩 开题组成员名单： 开题组意见： 研究生修改情况： 学院意见 组长签字： 导师签字： 注：1.开题后，修改的正式开题报告连同此表由学院保存备案，并将电子文档交存研究生学院培养部。 2.无正式开题报告及表中不填注各项意见者不得参加论文答辩。 主管学院领导签字： （盖章） 

学位论文题目：一种新的层次聚类算法的研究及应用 一、 选题背景及研究意义 数据挖掘是从海量数据中以高度精确和高度可靠的手段挖掘和产生新的知识，这 些新的知识将为决策者提供有力的科学决策依据。数据挖掘涉及多学科技术，包括数 据库、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检 索、图像与信号处理和空间数据分析等，已在医学、电信、零售业等科学或商业领域 得到了成功的应用。 数据挖掘的效率主要依赖于挖掘的方法，而数据挖掘的方法涉及到数理统计、 神经网络和人工智能等多种技术，技术含量比较高，实现难度比较大。随着数据挖掘 技术的不断发展，数据挖掘方法的研究和应用受到了国内外学术界、企业界和政府部 门越来越多的重视。目前，国外在数据挖掘方面的研究主要是对数据挖掘方法的进一 步研究和开发应用。 聚类算法是数据挖掘中的一个重要研究课题，属于无指导的学习过程，其目标是 将具有相似特征的数据划分在同一类或簇内，而将不相似的数据划分在不同的类或簇 中。同一个类中的数据彼此相似，而与其它类中的数据相异。聚类算法己被广泛应用 于统计学、机器学习、空间数据库、生物学以及市场营销等领域，还可以作为独立的 数据挖掘工具来了解数据的分布，或者作为其他数据挖掘算法（如关联规则、分类等） 的预处理步骤。聚类算法可以分为基于划分的方法、基于层次的方法、基于密度的方 法、基于网格的方法和基于模型的方法。 二、国内外研究现状 国外很多计算机公司非常重视数据挖掘方法的开发应用，IBM 和微软都成立了 相应的研究中心。国内从事数据挖掘方法研究的人员主要在大学，也有部分在研究所 或公司。所涉及的研究领域很多，一般集中于算法的研究、数据挖掘方法的实际应用 以及有关数据挖掘理论方面的研究。在所有聚类算法中，层次聚类是应用最为广泛的 一类，层次聚类算法又称为树聚类算法，其主要有凝聚式与分裂式两种：凝聚式层次 聚类采用自底向上的聚类过程，以一定的凝聚策略逐层合并数据(类)，最终形成层次 聚类树；与此相反，分裂式则是一个自顶向下地构造层次聚类树的过程。 层次聚类算法在实际应用中占主导地位。不但在各种软件包中都能找到它的身 1 

影，而且使用简单。但层次聚类算法存在高计算性以及对数据的输入顺序敏感等缺点。 目前已经提出了多种层次聚类算法，比如 BIRCH, CURE, Chameleon 等。这些算法在 减少时间复杂度，发现任意形状的聚类，消除噪音的影响等方面做出了卓有成效的工 作，但并没有考虑如何为使用者提供一个可以逐层分析，由粗到细的分析方法。当使 用者面对海量数据时，仍然无法清楚地了解聚类结果所代表的含义。 BIRCH 算法是一种分层聚类算法。它用聚类中心和半径来代表聚类，首先定义 了聚类特征(cluster feature)的概念，然后通过动态地构造一棵类似 B+树的聚类特征树 来实现聚类。BIRCH 算法不要求用户输入任何参数，具有一定处理噪音的能力。而 且它是一种增量聚类方法，不要求所有数据一次性读入内存，所以空间复杂度很低。 此外它的计算复杂度也只有 O(n)。BIRCH 的缺点主要是无法发现任意形状和大小的 聚类。另外当数据量非常大的时候，为了使有限的内存能够容纳聚类特征树，聚类半 径会比较大，从而导致聚类质量比较差。 CURE 算法也是一种分层聚类算法。不过它不是用聚类中心和半径来代表聚类， 而是用固定数目具有代表性的数据点来表示一个聚类。所以，可以发现具有任意大小 和形状的聚类。同时，在选择一个聚类的代表点时，通过向中心“收缩”的方式，可以 排除“噪音”。CURE 算法的缺点之一是要求用户提供聚类个数作为参数。另外它的空 问复杂度是 O(n)，所以必须采用抽样技术来减少数据量。CURE 算法在最坏的情况下， 时间复杂度会达到 O(n2logn)。如果数据的维数较低，时间复杂度可以达到 O(n2)。 Chameleon 是一个在层次聚类中采用动态模型的聚类算法。在聚类过程中，它先 为所有数据点构造一个 K-最近邻居图，然后将此图划分为许多小的子集，再用一个 凝聚的层次聚类算法通过反复地合并子类，来找到真正的结果簇。因为用具体的一簇 点来代表聚类，所以可以发现任意形状和大小的聚类。同时它在聚合子集时，既考虑 了互联性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇，这 样大大减少了“噪音”的影响，得到质量很高的聚类结果。但此算法的空间复杂度为 O(n)，计算复杂度会达到 O(n2)，所以面对大规模数据库，其实用性受到怀疑。 三、论文创新工作 Chameleon 算法由 Karypis G 在 1999 年提出，本文对 Chameleon 算法从理论上 进行了分析和讨论，作为一个探索动态模型的层次聚类算法，被认为是目前较好的层 次聚类算法，具有发现任意形状簇的能力，但其主要缺点如下：(1)K-最近邻居图中 K 值的确定需要人工进行；(2)最小二等分的选取困难；(3)相似度函数的阈值需要人 2 

工给定。龙真真等在 2009 年针对其缺点提出了 M-Chameleon 算法。 M-Chameleon 算法作为一种层次聚类算法，最主要的一个缺陷就是进行分解或合 并之后，无法回溯。本文提出了一种基于动态近邻选择模型的 Chameleon 算法(A Chameleon Algorithm based on Dynamic Nearest Neighbors Selection Model, DNMC)，有效的克服了这一缺点，并且聚类的效果有了明显的改进。 对于高维数据， 如果它们的某一维或几维属性内部值之间相差不大， 即在该维 上差异度的值很小， 那么在计算距离的过程中， 它们对最终距离的计算结果不会产 生很大的影响， 即可以将其忽略掉。因此不需要在该维数据上花费时间计算，从而 了减少计算次数，降低了时间复杂度。 对于高维数据， 如果它们的某一维或几维属性内部值之间相差不大， 即在该维 上差异度的值很小， 那么在计算距离的过程中， 它们对最终距离的计算结果不会产 生很大的影响， 即可以将其忽略掉。因此不需要在该维数据上花费时间计算，从而 了减少计算次数，降低了时间复杂度。 四、论文结构安排 第一章 阐述本课题的研究意义，提出本课题的研究背景和主要研究内容。 第二章 论述数据挖掘中的聚类算法，讨论聚类算法的分类，重点分析了层次聚 类算法。 第三章 详细阐述 Chameleon 算法和其改进算法 M-Chameleon 算法，在此基础上 提出了新的算法。 第四章 本章主要探讨改进的层次聚类算法在复杂网络社团发现中的应用。 第五章 对本课题的研究工作进行总结，提出有待进一步研究的问题。 五、写作计划 第一阶段: 收集资料,掌握前人的研究成果； 第二阶段: 阅读文献,启发思路； 第三阶段: 整理思路，做出结果； 第四阶段: 开始论文写作, 完成初稿； 第五阶段: 初稿的修改,整理； 第六阶段: 定稿. 六、主要参考文献 3 

[1] 金阳,左万利.一种基于动态近邻选择模型的聚类算法[J]. 计算机学报, 2007, 30(5): 756-762. [2] Marques JP, Written; Wu YF, Trans. Pattern Recognition Concepts, Methods and Applications[M]. Beijing:Tsinghua University Press, 2002. 51-74 (in Chinese). [3] Fred ALN, Leitão JMN. Partitional vs hierarchical clustering using a minimum grammar complexity approach.In:Proc.of the SSPR&SPR 2000. LNCS 1876, 2000.193−202.http://www.sigmod.org/dblp/db/conf/sspr/sspr2000.html. [4] 孙吉贵,刘杰,赵连宇. 聚类算法研究[J]. 软件学报,2008,19(1):48-61. [5] Zhang Tian,Ramakrishnan R,Livny M. BIRCH:An Efficient Data Clustering Method for Very Large Databases[Cl//Proceedings of the ACM SIGMOD Conference on Management of Data.Montreal, Canada:[s.n.],1996:103-114. [6] Guha U,Rastogi R，Shim K. CURE:An Efficient Clustering Algorithm for Large Databases[J]. Pergamon Information Systems, 2001,26(1):35-58. [7] Karypis G, Eui-Hong Han, Kumar V. Chameleon: A Hierarchical Clustering Algorithm Using Dynamic Modeling[J]. Computer, 1999,32(8): 68-75. [8] 周兵,王和兴,王翠荣. 一种基于GiST的层次聚类算法[J]. 计算机工, 2008, 34(9): 58-60. [9] 龙真真,张策,刘飞裔,张正文. 一种改进的Chameleon算法[J]. 计算机工程, 2009,35(20):189-191. [10] Newman M E J.Analysis of Weighted Networks[J]. hys.Rev.E,2004,70(5): 1-9. [11] Sebastiani F. A Tutorial on automated text categorisation//Proceedings of the 1st Argentinean Symposium on Artificial Intelligence(ASAI’99). Buenos A [12] Anil K.Jain,Richard C.Dubes. Algorithms for Clustering Data．Prentice Hall,1988,1-334 [13] Pang Ning Tan,Michael Steinbach,Vipin Kumar. Introduction to Data Mimng. Posts&Telecom Press,2004,132-212 [14] C.M.Bishop and M.E.Tipping. A Hierarchical Latent Variable Model for Data Visualisation. IEEE TPAMI3,1998(20):281-293 4