一种新的层次聚类算法的研究及应用

论文摘要

聚类分析是数据挖掘中的一个重要研究领域,是一种数据划分的方法,在数据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等领域有着广泛的应用。聚类算法可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。本文重点对层次聚类算法进行了分析和研究,并给出了层次聚类算法存在的缺陷,在分析Chameleon聚类算法的基础上,提出了一种基于动态近邻选择模型的Chameleon算法。社团结构是许多实际复杂网络中的一个重要特征。寻找和分析社团结构有助于更好地了解网络的内部结构,分析网络的性质。目前,人们已经提出了很多算法用于寻找复杂网络中存在的社团结构,本文将改进的层次聚类算法应用到复杂网络社团发现。论文的主要工作如下:（1）分析了现有的层次聚类算法,并着重介绍了BIRCH算法、CURE算法、ROCK算法和Chameleon算法,并比较了这些算法的优缺点。（2）在分析Chameleon聚类算法的基础上,提出了一种基于动态近邻选择模型的Chameleon算法。新的算法考虑了回溯机制,有利于合并之后的分解。在标准数据集Wine和Iris上的实验表明,DNMC算法的fa指标优于M-Chameleon算法。通过计算各个属性的差异度,显示出一些属性的存在对于聚类结果影响很小,删除这些属性列可以降低时间复杂度。（3）简单介绍了复杂网络社团发现的主要算法,将改进的层次聚类算法应用于社团发现,取得了良好的效果。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.3 论文创新工作
• 1.4 本文的目标与组织结构
• 第二章 聚类算法研究
• 2.1 聚类分析概述
• 2.2 聚类算法的分类
• 2.2.1 基于划分的方法（Partitioning Method）
• 2.2.2 基于层次的方法（Hierarchical Method）
• 2.2.3 基于密度的方法（Density-based Method）
• 2.2.4 基于网格的方法（Grid-based Method）
• 2.2.5 基于模型的方法（Model-based Method）
• 2.3 聚类分析中的数据类型
• 2.3.1 区间标度变量
• 2.3.2 二元变量
• 2.3.3 标称型、序数型和比例标度型变量
• 2.3.4 混合类型的变量
• 2.3.5 向量对象
• 2.4 孤立点分析
• 2.5 聚类算法的质量评价标准
• 2.6 本章小结
• 第三章 层次聚类方法及其改进
• 3.1 层次方法概述
• 3.1.1 凝聚的和分裂层次聚类
• 3.1.2 簇间距离度量方法
• 3.1.3 主要的几种层次聚类方法
• 3.2 层次聚类方法存在的不足
• 3.3 Chameleon 算法及其改进
• 3.3.1 Chameleon 算法
• 3.3.2 改进的Chameleon 算法
• 3.4 试验结果与分析
• 3.4.1 试验结果
• 3.4.2 聚类效果分析
• 3.5 本章小结
• 第四章 基于层次聚类算法的复杂网络社团发现
• 4.1 引言
• 4.1.1 复杂网络的发展及研究概况
• 4.1.2 复杂网络研究中存在的问题
• 4.2 社团结构的定义
• 4.3 复杂网络中划分社团结构的一般方法
• 4.3.1 Kernighan-Lin 算法
• 4.3.2 基于Laplace 矩阵特征值的谱平分法
• 4.3.3 分裂算法
• 4.3.4 凝聚算法
• 4.4 基于层次聚类的社团发现算法
• 4.4.1 相关概念
• 4.4.2 算法步骤
• 4.4.3 应用实例分析
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 附录：攻读硕士学位期间学术成果