基于判别信息和几何信息的聚类方法研究

摘要

我们现在处于大数据时代，微信、微博等新媒体迅猛发展，我们不仅是数据的接收者，更是数据的发布者。图片、视频、音频、文字等信息遍布网络，大数据成为网络时代的资产。大数据本身既不是科学也不是技术，大数据的特点是数据数量巨大，价值密度低，实时在线，多源异构，我们希望从庞大的数据中获取有价值的信息，聚类是挖掘大数据资产价值的第一步，大数据突破点在于聚类。现有的机器学习聚类算法如谱聚类、双图聚类、特征选择聚类算法等都存在一定的局限性，传统的谱聚类算法忽略了数据集的判别信息，双图聚类算法没有考虑特征空间的几何信息，特征选择算法忽略了数据本身的自相似性等，聚类的准确率有待提高。因此，我们以聚类为主题，通过挖掘数据本身固有的结构如局部几何结构、全部判别结构，特征空间几何信息等信息对数据聚类。本论文的主要工作如下：
　　1）谱聚类算法建立在图论中的谱图理论基础上，将聚类问题转化为图的最优划分问题。已有学者证明在一定的条件下，谱聚类算法和非负矩阵分解（NMF）等价。在此基础上，已有的非负谱聚类算法NSC-Ncut、NSC-Rcut、NSSC-Ncut和NSSC-Rcut都没有考虑数据集的全局判别信息。基于谱聚类与NMF的等价关系，考虑到数据集的全局判别信息，我们提出了新的谱聚类算法，即基于全局判别的非负谱聚类算法（GDBNSC-Ncut和GDBNSC-Rcut）。新的谱聚类算法保留了数据集的全局几何结构和全局判别结构，获取了数据的内在几何结构，且有更强的判别能力，提高了聚类的质量。实验结果表明，该算法能获得数据集的全局判别信息，具有更好的聚类效果。
　　2）特征选择算法剔除了不相关和冗余的特征，保留最有代表性的特征，不仅能降低数据维数，还能提高算法的质量。现有的特征选择算法大都是在数据空间进行，本文提出了一种新的特征选择算法，即基于自表示的双图正则特征选择聚类算法（DFSC），运用数据可以由自身表示的特性，我们同时保留数据空间和特征空间的局部几何信息。通过对数据空间的自表示系数矩阵加以l2,1范数约束，DFSC算法可以有效地选择最具代表性的特征。实验结果表明，由于考虑了特征空间的信息，DFSC算法的聚类质量优于一些其他的特征选择算法。此外，DFSC算法和一些双图聚类算法相比，多了一个选择的过程，对比试验结果表明DFSC算法的聚类质量更高，选择判别性的特征有利于提高聚类质量。
　　3）特征选择算法被广泛用于高维数据的降维，考虑到高维数据的自表示特征，受流形学习思想的启发，我们提出了一种新的特征选择聚类算法，即基于自表示和局部保留的无监督特征选择聚类算法（SRLP-FS）。我们运用了高维数据可以由自身表示的特性，即每个特征属性可由相关特征属性的线性组合来表示的特性。自表示的系数矩阵可以用来保留特征空间的局部几何信息，我们对自表示的系数矩阵加以l2,1范数约束，SRLP-FS算法可以有效地选择最具代表性的特征。实验结果表明，由于考虑了数据集特征空间的局部几何信息，且运用了高维数据的自表示特性，SRLP-FS算法的聚类质量优于其他一些特征选择算法。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1聚类问题简介

1.2聚类算法的研究现状

1.3聚类算法的发展趋势

第二章 基于全局判别的非负谱聚类算法

2.1引言

2.2相关工作

2.3基于全局判别的非负谱聚类算法（GDBNSC）

2.4实验结果及其分析

2.5总结与展望

第三章 基于自表示的双图正则特征选择聚类算法

3.1引言

3.2相关工作

3.3双图特征选择聚类算法

3.4实验结果及其分析

3.5算法有效性

3.6总结

第四章 基于自表示和局部保留的无监督特征选择聚类算法

4.1引言

4.2基于自表示和局部保留的无监督特征选择聚类算法

4.3求解算法

4.4算法收敛性分析

4.5实验结果及分析

4.6总结

第五章 总结与展望

5.1本文总结

5.2进一步工作

参考文献

致谢

作者简介