基于图聚类的多维数据和软件聚类研究

摘要

聚类作为一种无监督的模式分类方法，在语音识别、字符识别以及数据挖掘（多关系数据挖掘）、时空数据库应用(GIS等)、序列数据分析等领域具有广阔的应用前景。聚类研究按照数据建模方式可分为多维空间上的聚类以及图聚类（又称为图上社团发现）两个主要方向。随着各类数据规模持续增长，如何对海量的数据进行高效和有效的聚类分析是成为对多维数据的聚类研究一个巨大挑战。而对于图上的聚类而言，图聚类的特定的应用背景以及其可视化的过程需求的多样性是当前图聚类在实际应用中的主要挑战之一。
　　针对上述挑战，本文研究了在多维数值型向量数据和软件模块图数据上运用图上聚类技术实现高效和高质量聚类的聚类算法。主要工作分为两大块。
　　首先对多维空间上聚类所面临的处理海量数据的挑战，本文中提出了基于K-Means的KBAC算法，该算法采用K-Means算法作为预聚类过程，能够自适应确定最佳聚类核数目并进行聚类。其核心思想是将样本空间聚类问题转换为图上社团发现问题。并进一步研究了该算法在云平台上进行实现和优化方案。理论和实验证明，通过在云计算框架下优化实现K-Means预聚类过程的并行化，KBAC算法能够高效地对大规模数据进行自适应聚类，并获得高质量的聚类结果。
　　另一方面，针对图聚类在不同应用背景下问题的多样性，本文探索了软件聚类这一领域内的图聚类。在本文中提出了基于入口和PageRank的两阶段层次聚类算法和对软件聚类输出的模块的命名算法，并探索了对软件聚类结果进行粒度可调节的动态可视化的实现。并基于上述算法的设计，开发了软件聚类工具原型SCuV。该工具从软件源代码中提取出软件模块间的调用图，采用提出的算法进行聚类并实现可视化。案例分析表明该工具的聚类效率较高，能够给出具有一定语义的软件模块层次并实现了粒度可调的可视化，具有较好的应用前景。

目录

声明

摘要

第一章 引言

§1．1 研究背景及意义

§1．2 内容安排

第二章 聚类问题的相关工作

§2．1 多维数据聚类的相关工作

§2．1．1 基于K-Means多维数据聚类的相关工作

§2．2 图上聚类问题及其相关工作

§2．2．1 图的基本概念

§2．2．2 LPA标号传播图聚类算法

第三章 KBAC自适应聚类

§3．1 基于K-Means的自适应聚类

§3．1．1 算法主要思想：从样本空间聚类到图社团发现

§3．1．2 概念及定义

§3．1．3 KBAC算法框架描述

§3．1．4 算法复杂度分析

§3．2 KBAC聚类算法在云平台上的实现优化

§3．2．1 MapReduce云计算框架简介

§3．2．2 基于R-tree对K-Means在MapReduce下的优化

§3．3 实验分析

§3．3．1 实验数据

§3．3．2 聚类结果的参数敏感性评估

§3．3．3 KBAC在hadoop云平台下聚类的可伸缩性和准确性评估

§3．4 本章小结

第四章 软件模块的聚类

§4．1 软件聚类简介

§4．1．1 软件聚类相关工作

§4．1．2 软件聚类面临的挑战

§4．1．3 本工作的主要贡献

§4．2 两阶段软件聚类算法

§4．2．1 概念以及定义

§4．2．2 软件源码的分析

§4．2．3 软件模块的层次聚类

§4．3 聚类结果的命名

§4．3．1 模块命名算法

§4．4 聚类结果的可视化

§4．4．1 聚类结果可视化的实现

§4．4．2 对聚类结果的动态展示

§4．4．3 对聚类结果的操作

§4．5 案例分析

§4．5．1 分析项目Weka简介

§4．5．2 Weka项目的软件聚类过程

§4．5．3 Weka项目聚类结果的可视化

§4．5．4 聚类结果的合理性评估

§4．5．5 该软件聚类工具的试用反馈

§4．6 本章小结

第五章 总结与展望

§5．1 论文总结

§5．2 展望

参考文献

硕士期间发表的论文

致谢