解决文本聚类集成问题的两个谱算法

聚类集成中的关键问题是如何根据不同的聚类器组合为最终的更好的聚类结果. 本文引入谱聚类思想解决文本聚类集成问题, 然而谱聚类算法需要计算大规模矩阵的特征值分解问题来获得文本的低维嵌入, 并用于后续聚类. 本文首先提出了一个集成算法, 该算法使用代数变换将大规模矩阵的特征值分解问题转化为等价的奇异值分解问题, 并继续转化为规模更小的特征值分解问题; 然后进一步研究了谱聚类算法的特性, 提出了另一个集成算法, 该算法通过求解超边的低维嵌入, 间接得到文本的低维嵌入. 在TREC和Reuters文本数据集上的实验结果表明, 本文提出的两个谱聚类算法比其他基于图划分的集成算法鲁棒, 是解决文本聚类集成问题行之有效的方法.     

文本聚类集成问题中的谱算法

聚类集成中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果.引入谱聚类算法解决该问题,提出了基于相似度矩阵的谱算法(SMSA),但该算法高昂的计算代价使其不适合大规模文本集.进一步研究了谱聚类算法的特性,对超边的相似度矩阵进行谱分析.提出了基于超边相似度矩阵的元聚类算法(HSM-MCLA).真实文本数据集的实验结果表明:SMSA和HSM-MCLA比其他基于图划分的集成算法更优越;HSM-MCLA可获得与SMSA相当的结果,而计算需求却明显低于SMSA.     

一种基于二部图谱划分的聚类集成方法

将二部图模型引入聚类集成问题中,使用二部图模型同时建模对象集和超边集,充分挖掘潜藏在对象之间的相似度信息和超边提供的属性信息.设计正则化谱聚类算法解决二部图划分问题,在低维嵌入空间运行K-means++算法划分对象集,获得最终的聚类结果.在多组基准数据集上进行实验,实验结果表明所提出方法不仅能获得优越的结果,而且具有较高的运行效率.     

改进的判别割及其在图像分割中的应用

谱聚类算法能在任意形状的样本空间上聚类且收敛于全局最优解,但判别割(Dcut)算法在计算正则化相似度矩阵及其特征向量时比较耗时,而基于子空间的Dcut(SDcut)算法则不稳定,为此,提出基于主成分分析(PCA)的Dcut算法(PCA-Dcut)。PCA-Dcut算法采用PCA算法计算相似度矩阵的前m个大的特征值对应的特征向量构造一个新的矩阵,然后采用构造的矩阵与相似度矩阵和拉普拉斯矩阵分别进行矩阵运算;接着通过计算获得一个m阶正则化相似度矩阵,并计算该矩阵的k个最大特征向量;最后使用构造的矩阵与这k个特征向量相乘获得最终用于分类的特征向量。PCA-Dcut算法能降低Dcut算法的计算复杂度。通过对人工合成数据集、UCI数据集和真实图像的仿真实验表明,PCA-Dcut算法的聚类准确率与Dcut等谱聚类算法相当,同时在分割图像时的运算速度约为Dcut的5.4倍,并具有比SDcut更快的速度和更好的性能。     

基于地标表示的联合谱嵌入和谱旋转的谱聚类算法

经典的谱聚类算法包含两个步骤.(1)谱嵌入过程:求解Laplacian矩阵的特征值分解,得到分类指示矩阵的连续松弛解.(2)后处理过程:对谱嵌入连续松弛矩阵应用k-means或者谱旋转,得到最终的二值指示矩阵.由于有用信息的丢失,这种单独求解步骤不能保证最佳聚类结果.同时,谱聚类算法在处理大规模数据集时,存在聚类精度低、数据相似度矩阵存储开销大和Laplacian矩阵特征值分解计算复杂度高的问题.已有的联合谱聚类算法使用标准正交矩阵逼近非标准正交簇指示矩阵,这会导致较大的逼近误差.为了克服这一缺点,提出用一个改进的标准正交簇指示矩阵代替非正交指示矩阵,得到一个新的联合谱嵌入和谱旋转的谱聚类算法.因为两个标准正交矩阵更容易最小化,所以提出的算法可以取得更好的性能.进一步通过地标点方法对原始数据集进行稀疏特征表示,提出一种基于地标表示的联合谱嵌入和谱旋转算法(LJSESR),解决了大规模数据谱聚类的高效求解问题.实验结果表明,提出的LJSESR算法具有可行性和有效性.     

结合K均值与Laplacian的聚类集成算法

聚类集成可以有效提高传统聚类算法的精度,其关键问题在于如何根据聚类成员提供的信息获得更加优越的聚类结果.设计一种聚类集成算法,它结合K均值算法与基于拉普拉斯矩阵的谱聚类算法,充分利用聚类成员提供的属性信息与关系信息.为了降低算法计算复杂度,通过代数变换方法有效避免了大规模矩阵的特征值分解问题.在多组真实数据集上的实验结果表明,提出的算法优于其他聚类集成算法.     

文本聚类集成问题中的谱算法

聚类集成中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果．引入谱聚类算法解决该问题,提出了基于相似度矩阵的谱算法（ＳＭＳＡ）,但该算法高昂的计算代价使其不适合大规模文本集．进一步研究了谱聚类算法的特性,对超边的相似度矩阵进行谱分析,提出了基于超边相似度矩阵的元聚类算法（ＨＳＭ-ＭＣＬＡ）．真实文本数据集的实验结果表明：ＳＭＳＡ 和ＨＳＭ-ＭＣＬＡ 比其他基于图划分的集成算法更优越;ＨＳＭ-ＭＣＬＡ 可获得与ＳＭＳＡ 相当的结果,而计算需求却明显低于ＳＭＳＡ．

     

利用广义信息熵谱选择的图像分割

谱聚类算法中图上拉普拉斯矩阵的特征向量(谱)决定聚类结果,如何选择谱至关重要.为了解决这一问题,基于广义信息熵,定义谱的区分性、谱的区分有效性和谱的区分度这3个指标.谱的区分性指标用于衡量谱所含聚类信息的显著程度;谱的区分有效性指标用于剔除聚类结果无效的谱;谱的区分度指标用于构建基于贡献力的选择性聚类集成方案.进而提出基于谱选择的谱聚类算法.各种自然图像分割实验表明文中算法简单有效.     

一种深度自监督聚类集成算法

针对聚类集成中一致性函数设计问题,本文提出一种深度自监督聚类集成算法。该算法首先根据基聚类划分结果采用加权连通三元组算法计算样本之间的相似度矩阵,基于相似度矩阵表达邻接关系,将基聚类由特征空间中的数据表示变换至图数据表示;在此基础上,基聚类的一致性集成问题被转化为对基聚类图数据表示的图聚类问题。为此,本文利用图神经网络构造自监督聚类集成模型,一方面采用图自动编码器学习图的低维嵌入,依据低维嵌入似然分布估计聚类集成的目标分布;另一方面利用聚类集成目标对低维嵌入过程进行指导,确保模型获得的图低维嵌入与聚类集成结果是一致最优的。在大量数据集上进行了仿真实验,结果表明本文算法相比HGPA、CSPA和MCLA等算法可以进一步提高聚类集成结果的准确性。     

联合Laplacian正则项和特征自适应的数据聚类算法

在信息爆炸时代,大数据处理已成为当前国内外热点研究方向之一.谱分析型算法因其特有的性能而获得了广泛的应用,然而受维数灾难影响,主流的谱分析法对高维数据的处理仍是一个极具挑战的问题.提出一种兼顾维数特征优选和图Laplacian约束的聚类模型,即联合拉普拉斯正则项和自适应特征学习（joint Laplacian regularization and adaptive feature learning,简称LRAFL）的数据聚类算法.基于自适应近邻进行图拉普拉斯学习,并将低维嵌入、特征选择和子空间聚类纳入同一框架,替换传统谱聚类算法先图Laplacian构建、后谱分析求解的两级操作.通过添加非负加和约束以及低秩约束,LRAFL能获得稀疏的特征权值向量并具有块对角结构的Laplacian矩阵.此外,提出一种有效的求解方法用于模型参数优化,并对算法的收敛性、复杂度以及平衡参数设定进行了理论分析.在合成数据和多个公开数据集上的实验结果表明,LRAFL在效果效率及实现便捷性等指标上均优于现有的其他数据聚类算法.     

基于谱聚类的聚类集成算法

谱聚类是近年来出现的一类性能优越的聚类算法,能对任意形状的数据进行聚类, 但算法对尺度参数比较敏感,利用聚类集成良好的鲁棒性和泛化能力,本文提出了基于谱聚类的聚类集成算法.该算法首先利用谱聚类算法的内在特性构造多样性的聚类成员; 然后,采用连接三元组算法计算相似度矩阵,扩充了数据点之间的相似性信息;最后,对相似度矩阵使用谱聚类算法得到最终的集成结果. 为了使算法能扩展到大规模应用,利用Nystrm采样算法只计算随机采样数据点之间以及随机采样数据点与剩余数据点之间的相似度矩阵,从而有效降低了算法的计算复杂度. 本文算法既利用了谱聚类算法的优越性能,同时又避免了精确选择尺度参数的问题.实验结果表明:较之其他常见的聚类集成算法,本文算法更优越、更有效,能较好地解决数据聚类、图像分割等问题.     

一种基于SimRank得分的谱聚类算法

传统的谱聚类算法在建立相似度矩阵时仅考虑数据点与点的距离,忽略了数据点之间隐含的内在联系。针对这一问题,提出了一种基于SimRank的谱聚类算法。该算法首先用无向图数据建立邻接矩阵,并计算出基于SimRank的相似度矩阵;然后根据相似度矩阵建立拉普拉斯矩阵表达式,对其进行归一化后再进行谱分解;最后对分解得到的特征向量进行k-means聚类。在Zoo等UCI标准数据集上的实验结果表明,所提算法在聚类精确度、标准互信息和纯度3个评价指标上均优于现有的LRR(Low Rank Rrepresentation)等基于距离相似度的谱聚类算法。     

多尺度的谱聚类算法

提出了一种多尺度的谱聚类算法。与传统谱聚类算法不同,多尺度谱聚类算法用改进的k-means算法对未经规范的Laplacian矩阵的特征向量进行聚类。与传统k-means算法不同,改进的k-means算法提出一种新颖的划分数据点到聚类中心的方法,通过比较聚类中心与原点的距离和引入尺度参数来计算数据点与聚类中心的距离。实验表明,改进算法在人工数据集上取得令人满意的结果,在真实数据集上聚类结果较优。     

基于广义积分平方误差谱选择的图像分割

谱聚类算法中并不是所有的顶层谱都含有聚类信息,对于实际含噪声数据的聚类,由于谱数据分布复杂,谱的选择是必要的。文中推广积分平方误差散度,验证所提出的广义积分平方误差散度可用来估计数据分布的模态,以及度量谱所含的聚类信息量,并提出一种基于谱选择的谱聚类算法。自然图像分割实验结果表明,提出的算法比以往的谱聚类算法更为简单有效。     

基于加权集成Nyström采样的谱聚类算法

针对Nyström方法在谱聚类应用中存在聚类效果不稳定、样本代表性较弱的问题,提出基于加权集成Nyström采样的谱聚类算法.首先利用统计杠杆分数区别数据间的重要程度,对数据进行加权.然后基于权重采用加权K-means中心点采样,得到多组采样点.再引入集成框架,利用集群并行运行Nyström方法构建近似核矩阵.最后利用岭回归方法组合各个近似核矩阵,产生比标准Nyström方法更准确的低秩近似.在UCI数据集上的测试实验表明,文中算法取得较理想的聚类结果.     

The latest research progress on spectral clustering

Spectral clustering is a clustering method based on algebraic graph theory. It has aroused extensive attention of academia in recent years, due to its solid theoretical foundation, as well as the good performance of clustering. This paper introduces the basic concepts of graph theory and reviews main matrix representations of the graph, then compares the objective functions of typical graph cut methods and explores the nature of spectral clustering algorithm. We also summarize the latest research achievements of spectral clustering and discuss several key issues in spectral clustering, such as how to construct similarity matrix and Laplacian matrix, how to select eigenvectors, how to determine cluster number, and the applications of spectral clustering. At last, we propose several valuable research directions in light of the deficiencies of spectral clustering algorithms.