面向高维数据的PCA-Hub聚类方法研究

摘要

传统的聚类分析算法往往可以在低维数据空间中取得不错的聚类效果，然而在高维数据空间中却表现很差，这主要是由高维数据空间中的维数灾难所引起的。维数灾难造成的影响之一是距离集中，Hinneburg和 Aggarwal等人已经对高维数据中的距离集中和无意义的最近邻作了深入的研究。维数灾难造成的另一方面影响是hubness现象，本文将会从这个新的方向进行深入分析。Hubness这一概念最初是在2010年由Milos Radovanovic等人提出的，hubness描述的是这样一种现象：在 k近邻列表中某些对象趋向于高频率地出现在其它对象的最近邻居列表中。Milos Radovanovic等人利用这一属性提出了四种hub聚类分析算法。Hub聚类算法虽然可以在高维数据空间中进行聚类分析，但是它却忽略了高维数据空间中的冗余和噪声数据，从而无法获得更优的簇结构以及更快的聚类收敛速度。
　　本文针对hub聚类分析算法的上述问题，提出了一种基于逆近邻数偏度降维的PCA-Hub聚类分析算法，此算法可以解决高维数据空间中的冗余和噪声数据，并且能够获得更好的簇结构和更快的聚类收敛速度。实验结果表明，PCA-Hub聚类算法相比之前的聚类算法在轮廓系数上平均提高了15％；当数据集的维数或者逆近邻数的偏度较高时，PCA-Hub聚类算法对近邻数k的选择未表现出强烈的相关性；在实验环境和聚类参数一致的情况下，PCA-Hub聚类算法的结果在很大程度上具有一致性。
　　PCA-Hub聚类算法虽然可以很好地解决高维数据空间中的冗余和噪声特征，然而随着数据集样本数和数据集维数的不断增加，PCA-Hub聚类算法的时间复杂度将会变得越来越严重甚至不可接受。因此，本文提出了一种Quick PCA-Hub聚类分析算法从快速搜索前k个理想的主成分来加快PCA-Hub算法的聚类分析速度。实验结果表明，Quick PCA-Hub聚类算法相比之前的聚类算法在轮廓系数上平均提高了8%；Quick PCA-Hub在高维数据空间中搜索理想的前k个主成分时表现出了巨大的优势。
　　最后，本文提出的PCA-Hub方法可以解决hub聚类算法无法处理高维数据空间中冗余和噪声特征的问题，并且从多方面的实验证实了该算法的有效性。针对PCA-Hub聚类算法搜索前k个主成分时间复杂度过高的问题，Quick PCA-Hub聚类算法通过快速搜索前k个主成分解决了该问题，实验结果表明该算法在高维数据空间上具有较好的表现性。

目录

1 绪 论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文研究的主要内容

1.4 论文的章节排版

2 聚类分析概述

2.1 聚类分析的定义

2.2 常用的聚类分析算法

2.3 Hub聚类算法分析

2.4 聚类分析的评价标准

2.5 聚类分析的评估检验

2.6 本章小结

3 PCA-Hub 聚类算法

3.1 维数灾难

3.2 基于逆近邻数偏度的降维方法

3.3 PCA-Hub聚类算法

3.4 实验结果及其分析

3.5 本章小结

4 Quick PCA-Hub聚类算法

4.1 快速搜索前k个主成分

4.2 算法思想

4.3 实验结果及其分析

4.4 本章小结

5 总结与展望

5.1 总结

5.2 展望

致谢

参考文献

附录

A.作者在攻读硕士学位期间撰写的论文目录