基于Canopy聚类的谱聚类算法

传统的谱聚类算法对初始化敏感,针对这个缺陷,引入Canopy算法对样本进行“粗”聚类得到初始聚类中心点,将结果作为K-Means算法的输入,提出了一种基于Canopy和谱聚类融合的聚类算法（Canopy-SC）,减少了传统谱聚类算法选择初始中心点的盲目性,并将其用于人脸图像聚类。与传统的谱聚类算法相比,Canopy-SC算法能够得到较好的聚类中心和聚类结果,同时具有更高的聚类精确度。实验结果表明了该算法的有效性和可行性。     

基于矩阵谱分析的文本聚类集成算法

聚类集成技术可有效提高单聚类算法的精度和稳定性,其中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果.文中引入谱聚类算法解决文本聚类集成问题,设计基于正则化拉普拉斯矩阵的谱算法(NLM-SA).该算法基于代数变换,通过求解小规模矩阵的特征值和特征向量间接获得正则化拉普拉斯矩阵的特征向量,并用于后续聚类.进一步研究谱聚类算法的关键思想,设计基于超边转移概率矩阵的谱算法(HTMSA).该算法通过求解超边的低维嵌入间接获得文本的低维嵌入,并用于后续K均值算法.在TREC和Reuters文本集上的实验结果验证NLMSA和HTMSA的有效性,它们都获得比其它基于图划分的集成算法更为优越的结果.HTMSA获得的结果比NLMSA略差,而时间和空间需求则比NLMSA低得多.     

基于免疫谱聚类的图像分割

提出了一种基于免疫谱聚类的图像分割方法.利用谱聚类的维数缩减特性获得数据在映射空间的分布,在此基础上构造一种新的免疫克隆聚类,用于在映射空间中对样本进行聚类.该方法通过谱映射为后续的免疫克隆聚类提供低维而紧致的输入.而免疫克隆聚类算法具有快速收敛到全局最优并且对初始化不敏感的特性,从而可以获得良好的聚类结果.在将其用于图像分割时,采用了Nystr?m逼近策略来降低算法复杂度.合成纹理图像和SAR图像的分割结果验证了免疫谱聚类算法用于图像分割的有效性.     

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

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

基于共享近邻的自适应谱聚类

谱聚类是一种极具竞争力的聚类算法.相似度定义对谱聚类算法的性能有至关重要的影响.本文用两点的共享近邻数目表征局部密度,从而获知隐含的簇结构信息.将这一信息与自调节的高斯核函数结合,提出了基于共享近邻的自适应相似度及相应的谱聚类算法.它满足聚类假设的要求,具有局部密度的自适应性,能有效识别数据点之间的内在联系.典型人工和真实数据集上的实验结果证明了算法的有效性.     

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

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

一种高效的双边聚类集成算法

谱聚类可以任意形状的数据进行聚类,在聚类集成中能够有效的提高基聚类的质量.以往的聚类集成算法中,聚类集成得到的结果并不是最终聚类结果,还需要利用聚类算法来获得最终聚类结果,在整个过程中会使得解由离散-连续-离散的转变.提出了一种基于谱聚类的双边聚类集成算法.算法首先在生成阶段使用谱聚类算法来获得基聚类,通过标准互信息来选取基聚类.将选出来基聚类和样本作为图的顶点,并对构建的图利用双边聚类算法对基聚类和样本同时聚类直接得到最终聚类结果.在实验中,将所提方法与一些聚类集成算法进行了比较,取得了较好的结果.     

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

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

基于模糊K-harmonic means的谱聚类算法

谱聚类作为一种有效的方法广泛应用于机器学习。通过分析谱聚类初始化敏感的实质,引入对初值不敏感的模糊K-harmonic means算法来克服这一缺点,提出一种基于模糊K-harmonic means的谱聚类算法（FKHM-SC）。与传统谱聚类算法以及对初值敏感的K-means、FCM算法相比,改进算法不仅可以识别有挑战性的人工数据,并且可以得到稳定的聚类中心和聚类结果,同时提高了聚类的精确度。实验结果表明了该算法的有效性和可行性。     

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

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

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

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

半监督谱聚类特征向量选择算法

对于一个K类问题,Ng-Jordan-Weiss(NJW)谱聚类算法通常采用数据规范化亲和度矩阵的前K个最大特征值对应的特征向量作为数据的一种表示。然而,对于某些模式识别问题,这K个特征向量不一定能够体现原始数据的结构。文中提出一种半监督谱聚类特征向量选择算法。该算法利用一定量的监督信息寻找能够体现数据结构的特征向量组合,进而获得优于传统谱聚类算法的聚类性能。UCI标准数据集和MNIST手写体数据集上的仿真实验验证该算法的有效性和鲁棒性。     

Spectral clustering with eigenvector selection

The task of discovering natural groupings of input patterns, or clustering, is an important aspect of machine learning and pattern analysis. In this paper, we study the widely used spectral clustering algorithm which clusters data using eigenvectors of a similarity/affinity matrix derived from a data set. In particular, we aim to solve two critical issues in spectral clustering: (1) how to automatically determine the number of clusters, and (2) how to perform effective clustering given noisy and sparse data. An analysis of the characteristics of eigenspace is carried out which shows that (a) not every eigenvectors of a data affinity matrix is informative and relevant for clustering; (b) eigenvector selection is critical because using uninformative/irrelevant eigenvectors could lead to poor clustering results; and (c) the corresponding eigenvalues cannot be used for relevant eigenvector selection given a realistic data set. Motivated by the analysis, a novel spectral clustering algorithm is proposed which differs from previous approaches in that only informative/relevant eigenvectors are employed for determining the number of clusters and performing clustering. The key element of the proposed algorithm is a simple but effective relevance learning method which measures the relevance of an eigenvector according to how well it can separate the data set into different clusters. Our algorithm was evaluated using synthetic data sets as well as real-world data sets generated from two challenging visual learning problems. The results demonstrated that our algorithm is able to estimate the cluster number correctly and reveal natural grouping of the input data/patterns even given sparse and noisy data.     

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

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

四元数矩阵正交特征向量系的求解方法及其在彩色人脸识别中的应用

针对四元数矩阵正交特征矢量系求解困难的缺点, 本文提出一种获取四元数矩阵正交特征矢量集等效、便捷的方法, 其基本思路为: 首先, 构造四元数矩阵定义于复数域的导出阵, 并利用该导出阵特征矢量空间的一种特殊的等价空间间接获取相应特征值所对应的特征矢量. 然后, 将复数矢量转换为四元数矢量, 按如此方式获取的对应所有特征值的非零特征矢量则构成原始四元数矩阵的正交特征矢量系. 同时, 本文将定义于实数域的主成分分析方法 (Principal component algorithm, PCA) 向四元数体作合理的推广, 给出详细的数学推导过程, 证明该方法的合理性及其在统计模式识别领域得以应用的可能性. 最后, 作者将彩色图像像素的R、G、B三分量作为四元数的三个虚数部分, 首次在人脸识别中引入基于四元数的彩色人脸识别方法. 较传统的基于灰度图像的识别方法, 本文方法不仅利用了人脸图像灰度值的空间分布信息, 而且充分利用不同人脸之间的色彩差异, 从而得到更多的鉴别信息.在四川大学人工智能研究所的彩色人脸库上进行的实验表明, 所提出的基于四元数的识别方法不仅大幅度提高了识别率, 而且具有较高的鲁棒性.     

Spectral clustering based on matrix perturbation theory

This paper exposes some intrinsic characteristics of the spectral clustering method by using the tools from the matrix perturbation theory. We construct a weight ma- trix of a graph and study its eigenvalues and eigenvectors. It shows that the num- ber of clusters is equal to the number of eigenvalues that are larger than 1, and the number of points in each of the clusters can be approximated by the associated eigenvalue. It also shows that the eigenvector of the weight matrix can be used directly to perform clustering; that is, the directional angle between the two-row vectors of the matrix derived from the eigenvectors is a suitable distance measure for clustering. As a result, an unsupervised spectral clustering algorithm based on weight matrix (USCAWM) is developed. The experimental results on a number of artificial and real-world data sets show the correctness of the theoretical analysis.     

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.     

联合结构化图学习与l1范数谱嵌入的鲁棒聚类算法

谱聚类算法存在两个不足:a)将图的构造与谱分解割裂成两个独立的阶段,导致了结果的次优性;b)常用的基于l₂范数度量谱特征向量的相似性具有噪声敏感性。为了克服上述两点不足,提出基于联合结构化图学习与l₁范数谱嵌入的鲁棒聚类算法(记为CLRL1)。在该算法框架下,一方面图的学习过程与聚类过程可以有效结合起来进行协同优化,另一方面l₁范数的使用可以很好地约束谱特征向量的相似性以提升算法的鲁棒性。在多个常用数据集上进行的实验结果表明,改进算法聚类性能得到了明显提升。     

基于堆和邻域共存信息的KNN相似图算法

在谱聚类算法中,相似图的构造至关重要,对整个算法的聚类结果和运行效率都有着巨大影响。为了加快谱聚类的运算速度和通过近邻截断提高其性能,通常选择K近邻(KNN)方法来构造稀疏的相似图,而K近邻图对离群点非常敏感,这种噪声边会严重影响聚类算法的性能。文中提出了一种新的高效稀疏亲和图构造方法HCKNN,其中基于堆的K近邻搜索比基于排序的近邻选择在效率方面提升了log(n),基于邻域共存累计的阈值化来进行邻域约减不仅能够去除噪声边以提高聚类性能,还能进一步稀疏化相似矩阵,从而加速谱聚类中的特征分解。