面向高维数据的子空间聚类算法研究

摘要

聚类是数据挖掘的重要研究内容,其中对大规模、高维数据库的聚类分析是研究的热点和难点问题.由于高维数据的稀疏性、空空间现象及维数灾难的影响,高维数据不可能在全维空间密集,于是传统聚类方法不能获得理想效果.针对高维数据聚类方法存在的问题,本文的主要工作如下: 分析了传统聚类算法在处理大规模、高维数据集时遇到的困难和问题.比较了各种降维处理方法的优劣,从原理上论证了子空间聚类算法处理大规模、高维数据集的优势. 在此基础上,进一步对已有子空间聚类算法进行分析,基于Aporiori算法思想的子空间聚类算法在应用中存在一些问题:首先在确定簇的相关维时需要多遍扫描数据库,降低了聚类的时间效率;其次,这些算法都只能对单一数据类型进行处理.关联规则挖掘中频繁模式的发现与簇相关维的确定具有很大的相似性.因此本文提出了一种基于模式树的子空间聚类算法PSC,仅需扫描数据库一遍,大大提高了子空间聚类算法的效率.同时通过扩展簇的定义,将对符号型和数值型数据的聚类整合到一个统一的框架中. 目前大多数聚类算法都是用对象在属性集上的距离来衡量对象相似度.然而距离函数并不总能有效的发现对象之间的联系.事实上距离很远但属性值具有相似变化模式的对象也可能属于一类.基于模式相似度的聚类算法是子空间聚类算法的一种,它能有效发现这一类的簇.但是已有的方法在高维大规模数据库中效率不高,并且对聚类所得的簇质量没有评价.为此本文提出了一个新的算法,该方法应用新的簇质量评价标准来挖掘最优的簇,从而聚类的结果更加有意义,同时应用基于模式树发现簇的相关维方法也有效地提高了算法效率.

目录

文摘

英文文摘

论文说明：图表清单

独创性声明及学位论文版权使用授权书

致谢

第一章绪论

1.1数据库知识发现

1.1.1 KDD的定义

1.1.2 KDD的处理过程

1.2数据挖掘

1.2.1数据挖掘的功能

1.2.2数据挖掘的研究热点

1.2.3数据挖掘面临的挑战

1.3聚类分析

1.3.1聚类的相关概念

1.3.2聚类算法分类

1.3.3聚类算法性能评价

1.4本文的主要内容与结构安排

第二章高维聚类问题

2.1高维数据聚类概述

2.1.1高维数据的特点

2.1.2高维数据对传统聚类算法的影响

2.2属性约简

2.2.1特征选择

2.2.2特征变换

2.3子空间聚类

2.3.1子空间聚类的必要性

2.3.2子空间聚类算法概述

2.3.3常用子空间聚类算法及其存在的问题

2.4本章小结

第三章基于模式树的子空间聚类

3.1频繁模式的挖掘

3.1.1关联规则挖掘

3.1.2 P-tree的结构定义

3.2基于P-tree的子空间聚类算法(PSC)

3.2.1簇的扩展定义

3.2.2 PSC算法

3.3算法性能测试

3.3.1实验结果

3.3.2性能分析

3.4本章小结

第四章基于模式相似的子空间聚类

4.1引言

4.1.1问题引入

4.1.2研究现状

4.2基于模式相似的簇的概念

4.2.1一致模式的定义

4.2.2基于相似模式的簇的定义

4.3基于模式相似的子空间聚类算法(PPSC)

4.4实验结果及性能分析

4.4.1实验结果

4.4.2性能分析

4.5本章小结

第五章总结和展望

5.1本文总结

5.2下一步工作

参考文献

研究生期间主要科研工作及成果