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

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

基于Hadoop MapReduce并行近似谱聚类算法研究与实现

随着信息时代的来临,互联网产生的大规模高维数据呈现几何级数增长,对其进行谱聚类在计算时间和内存使用上都存在瓶颈问题,尤其是求Laplacian矩阵特征向量分解。鉴于Hadoop MapReduce并行编程模型对密集型数据处理的优势,基于t最近邻稀疏化近似相似Laplacian矩阵,设计Hadoop MapReduce并行近似谱聚类算法,以期解决上述瓶颈问题。实验使用UCI Bag of Words数据集验证所设计算法的正确性和有效性,结果显示该并行设计在谱聚类质量和性能方面达到了一定的预期效果。     

多尺度的谱聚类算法

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

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

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

一种基于加速迭代的大数据集谱聚类方法

传统谱聚类算法的诸多优点只适合小数据集。根据Laplacian矩阵的特点重新构造新的Gram矩阵,输入新构造矩阵的若干列,然后利用加速迭代法解决大数据集的谱聚类特征提取问题,使得在大数据集条件下,谱聚类算法只需要很小的空间复杂度就可达到非常快的计算速度。     

融合局部结构学习的大规模子空间聚类算法

常规的大规模子空间聚类算法在计算锚点亲和矩阵时忽略了数据之间普遍存在的局部结构，且在计算拉普拉斯（Laplacian）矩阵的近似特征向量时存在较大误差，不利于数据聚类。针对上述问题，提出一种融合局部结构学习的大规模子空间聚类算法（LLSC）。所提算法将局部结构学习嵌入锚点亲和矩阵的学习，从而能够综合利用全局和局部信息挖掘数据的子空间结构；此外，受非负矩阵分解（NMF）的启发，设计一种迭代优化方法以简化锚点亲和矩阵的求解过程；其次，根据Nystr?m近似方法建立锚点亲和矩阵与Laplacian矩阵的数学联系，并改进Laplacian矩阵特征向量的计算方法以提升聚类性能。相较于LMVSC(Large-scale Multi-View Subspace Clustering)、SLSR(Scalable Least Square Regression)、LSC-k(Landmark-based Spectral Clustering using k-means)和k-FSC(k-Factorization Subspace Clustering),LLSC在4个广泛使用的大规模数据集上显示出...     

基于均值的谱聚类特征向量选择算法

在数据聚类当中,谱聚类是最流行的方法之一,其性能取决于所选取相关图的拉普拉斯(Laplacian)矩阵的特征向量。对于一个K类问题,Ng-Jordan-Weiss(NJW)谱聚类算法通常采用Laplacian矩阵的前K个最大特征值对应的特征向量作为数据的一种表示。然而,对于某些分类问题,这K个特征向量不一定能够很好地体现原始数据的信息。本文提出一种基于均值的谱聚类特征向量选择算法。该算法首先得出图的Laplacian矩阵的前3K个最大特征值的均值,然后选取K个离均值最近的特征值所对应的特征向量。相比传统谱聚类算法,该算法在UCI数据集上获得了较好的聚类性能。     

基于密度调整的改进自适应谱聚类算法

针对谱聚类存在构造相似度矩阵时对尺度参数敏感以及处理多重尺度数据集效果不理想的缺陷, 提出一种基于密度调整的改进自适应谱聚类算法. 该算法将样本点所处领域的密度引入谱聚类, 利用密度差来调整样本点之间的相似度, 使其更符合实际簇类中样本点间的内在关系, 在一定程度上解决了多尺度聚类问题; 同时, 通过样本点的近邻距离自适应得到尺度参数, 使算法对尺度参数相对不敏感. 仿真实验验证了所提出算法的有效性和优越性.

     

基于半监督自动谱聚类算法的网络故障检测

针对网络故障检测中利用先验知识不足和多数谱聚类算法需事先确定聚类数的问题,提出一种新的基于成对约束信息传播与自动确定聚类数相结合的半监督自动谱聚类算法。通过学习一种新的相似性测度函数来满足约束条件,改进NJW聚类算法,对非规范化的Laplacian矩阵特征向量进行自动谱聚类,从而提高聚类性能。在UCI标准数据集和网络实测数据上的实验表明,该算法较相关比对算法聚类准确率更高,可满足网络故障检测的实际需要。     

融入局部几何特征的流形谱聚类图像分割

为了改善谱聚类图像分割的精准性和时效性,文中提出融入局部几何特征的流形谱聚类图像分割算法.首先,考虑图像数据的流形结构,在数据点的K近邻域内执行局部PCA,得到数据间本征维数的关系.然后,引入流形学习中的局部线性重构技术,通过混合线性分析器得到数据间局部切空间的相似性,结合二者构造含有局部几何特征的相似性矩阵.再利用Nystr m技术逼近待分割图像的特征向量,对构造的k个主特征向量执行谱聚类.最后,在Berkeley数据集上的对比实验验证文中算法的准确性和时效性优势.     

基于传递距离的谱聚类算法

谱聚类算法受到度量中尺度因子的影响,同时传统谱聚类算法通过欧氏距离度量样本间相似性也不准确。针对上述问题,提出一种基于传递距离的谱聚类算法。算法首先通过改进传统谱聚类中的度量方式,用基于传递距离的度量方式度量样本间相似性,并构建传递矩阵,接着用传递矩阵做相似度变换构建拉普拉斯矩阵,最终通过求特征值和特征向量完成聚类。基于传递距离的谱聚类算法在人工数据集及UCI数据集上均取得了良好的聚类结果,具有较好的鲁棒性和有效性。     

自适应谱聚类算法并行实现及优化

谱聚类算法是基于谱图分割理论的聚类方法,其对高维、非凸数据分布问题有很好的聚类效果。但对大规模数据问题的聚类,该方法存在着计算时间和存储空间等方面的瓶颈。本文给出了一个自适应的谱聚类并行算法,通过局部计算和异步循环通信并行方法,最大限度减少了并行谱聚类中数据通信次数,并通过计算与通信重叠策略,进一步降低了并行算法的通信开销。在并行算法实现中,将自主开发的最优预条件共轭梯度法并行求解器 PLOBPCG 用于谱聚类的特征降维。在中科院的“元”超级计算机上,通过对两类大规模数据聚类的测试表明,在 2048 核上的加速比接近线性加速,并行效率达到96%以上。     

Hearing the clusters of a graph: A distributed algorithm

We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue/eigenvector computations. We prove that, by propagating waves through the graph, a local fast Fourier transform yields the local component of every eigenvector of the Laplacian matrix, thus providing clustering information. For large graphs, the proposed algorithm is orders of magnitude faster than random walk based approaches. We prove the equivalence of the proposed algorithm to spectral clustering and derive convergence rates. We demonstrate the benefit of using this decentralized clustering algorithm for community detection in social graphs, accelerating distributed estimation in sensor networks and efficient computation of distributed multi-agent search strategies.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

Local density adaptive similarity measurement for spectral clustering

Similarity measurement is crucial to the performance of spectral clustering. The Gaussian kernel function is usually adopted as the similarity measure. However, with a fixed kernel parameter, the similarity between two data points is only determined by their Euclidean distance, and is not adaptive to their surroundings. In this paper, a local density adaptive similarity measure is proposed, which uses the local density between two data points to scale the Gaussian kernel function. The proposed similarity measure satisfies the clustering assumption and has an effect of amplifying intra-cluster similarity, thus making the affinity matrix clearly block diagonal. Experimental results on both synthetic and real world data sets show that the spectral clustering algorithm with our local density adaptive similarity measure outperforms the traditional spectral clustering algorithm, the path-based spectral clustering algorithm and the self-tuning spectral clustering algorithm.     

Fast density-weighted low-rank approximation spectral clustering

While spectral clustering can produce high-quality clusterings on small data sets, computational cost makes it infeasible for large data sets. Affinity Propagation (AP) has a limitation that it is hard to determine the value of parameter ‘preference’ which can lead to an optimal clustering solution. These problems limit the scope of application of the two methods. In this paper, we develop a novel fast two-stage spectral clustering framework with local and global consistency. Under this framework, we propose a Fast density-Weighted low-rank Approximation Spectral Clustering (FWASC) algorithm to address the above issues. The proposed algorithm is a high-quality graph partitioning method, and simultaneously considers both the local and global structure information contained in the data sets. Specifically, we first present a new Fast Two-Stage AP (FTSAP) algorithm to coarsen the input sparse graph and produce a small number of final representative exemplars, which is a simple and efficient sampling scheme. Then we present a density-weighted low-rank approximation spectral clustering algorithm to operate those representative exemplars on the global underlying structure of data manifold. Experimental results show that our algorithm outperforms the state-of-the-art spectral clustering and original AP algorithms in terms of speed, memory usage, and quality.     

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

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

拉普拉斯正则化双曲正切低秩子空间聚类算法

传统的低秩表示模型LRR对高维数据聚类精确度低,针对这一情况提出一种基于拉普拉斯正则化双曲正切函数低秩子空间聚类算法(LRHT-LRSC).该算法利用双曲正切函数代替核范数以便更紧凑地逼近秩函数,并利用拉普拉斯正则项刻画数据本身的几何结构,提高了数据聚类的准确率;然后构建数据样本的系数矩阵和相似矩阵;最后利用谱聚类方法得到最终的聚类结果.在合成数据集、真实数据集ExtendedYaleB和Hopkins155上的对比实验结果表明,LRHT-LRSC能够提高聚类的准确率和鲁棒性.