基于改进的最小生成树聚类算法研究

论文摘要

数据挖掘指的是从大量数据中提取隐含的、事先未知的、并且潜在有用的知识的技术,是目前国际上数据库和信息决策领域最前沿的领域之一。聚类分析就是其中一个重要的研究方向,对它进行深入研究在理论和应用上都有重要价值。目前,很多学者都在尝试用不同的方法来处理聚类问题。但是由于聚类问题属于非监督模式识别问题,现有的方法还存在不足,这就要求对现有聚类技术进行改进,提出新的聚类理论和方法以适应新的应用。本文通过研究,借鉴传统的最小生成树(minimum spanning tree,MST)聚类算法的先进思想,并分析该方法在聚类算法在时间复杂度和聚类效果上的不足,提出一种新的应用于一般问题的改进最小生成树(improved minimum spanning tree,IMST)的聚类算法,该算法首先通过对数据集、中间集的处理,使用一种新的方法构造最小生成树,提高了构造生成树的效率;然后,通过清除最长边后,对初步划分的生成树用矩阵表示,以度最大的结点作为聚类中心,再根据中心点算法完成聚类,解决了以往最小生成树算法无法解决的多个簇用短边或长度相同的边相连无法分类的问题,从而提高了聚类速度,改善了聚类的质量;最后,通过对多维数据进行分析,通过计算各个属性的差异度,能够得出结论,一些属性的存在对于构造生成树有很小的影响或没有影响,删除这些属性列也可以提高效率,达到减少计算复杂性的目的。本文提出的方法解决了传统MST聚类算法存在的问题,并使用降低数据维数的方法,进一步提高了效率,实例验证,该方法具有理论和现实双重意义。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 数据挖掘概述
• 1.1.1 数据挖掘的任务和基本方法介绍
• 1.1.2 数据挖掘的过程
• 1.1.3 数据挖掘的应用和发展
• 1.2 数据挖掘的工具
• 1.2.1 SAS 的数据挖掘工具
• 1.2.2 IBM 的数据挖掘工具——QUEST 系统
• 1.2.3 SPSS（Statistical Program for Social Sciences）Clementine
• 1.3 目前研究的热点与难点
• 1.4 本文研究的内容和意义
• 1.4.1 课题来源
• 1.4.2 本文研究的意义
• 1.4.3 本文研究的内容
• 第2章 数据挖掘中的聚类分析
• 2.1 聚类分析的概念、形式化描述及研究内容
• 2.2 聚类分析算法的典型要求
• 2.3 聚类分析的研究过程、方法及现状
• 2.3.1 划分方法（partitioning method）
• 2.3.2 层次方法（hierarchical method）
• 2.3.3 基于密度的方法（density-based method）
• 2.3.4 基于网格的方法（grid-based method）
• 2.3.5 基于模型的方法（model-based method）
• 2.4 本章小结
• 第3章 基于划分的聚类算法
• 3.1 引言
• 3.2 基于划分的聚类算法
• 3.2.1 主要思想
• 3.2.2 k-平均算法
• 3.2.3 PAM
• 3.2.4 其他方法
• 3.3 本章小结
• 第4章 基于改进最小生成树聚类算法的描述
• 4.1 引言
• 4.2 基因表示的最小生成树聚类算法
• 4.2.1 基因的生成树表示
• 4.2.2 清除最长 MST 边的聚类法
• 4.2.3 重复聚类算法
• 4.2.4 改进的重复聚类法
• 4.3 IMST 聚类算法
• 4.3.1 数据集初分方案
• 4.3.2 算法的基本思想
• 4.4 本章小结
• 第5章 算法实现及实例分析
• 5.1 引言
• 5.2 算法实现步骤描述
• 0是最小生成树'>5.3 证明该算法得到的树T₀是最小生成树
• 5.4 算法效率分析
• 5.5 具有一般问题的实例分析
• 5.6 本章小结
• 第6章 IMST 聚类算法的多维分析
• 6.1 引言
• 6.2 高维数据的实例
• 6.2.1 购物篮数据
• 6.2.2 用户评分数据
• 6.2.3 多媒体数据
• 6.2.4 Web 使用数据
• 6.2.5 时间序列数据
• 6.2.6 基因表达数据
• 6.3 通常处理高维数据聚类的方法
• 6.4 分析随维数提高对IMST 算法的影响
• 6.5 降低数据维数的实例分析
• 6.6 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢