加权PageRank改进地标表示的自编码谱聚类算法

针对传统谱聚类算法在处理大规模数据集时,聚类精度低并且存在相似度矩阵存储开销大和拉普拉斯矩阵特征分解计算复杂度高的问题。提出了一种加权PageRank改进地标表示的自编码谱聚类算法,首先选取数据亲和图中权重最高的节点作为地标点,以选定的地标点与其他数据点之间的相似关系来逼近相似度矩阵作为叠加自动编码器的输入。然后利用聚类损失同时更新自动编码器和聚类中心的参数,从而实现可扩展和精确的聚类。实验表明,在几种典型的数据集上,所提算法与地标点谱聚类算法和深度谱聚类算法相比具有更好的聚类性能。     

基于局部和全局信息的改进聚类算法

传统K-means算法在随机选取初始聚类中心时,容易导致结果不稳定,谱聚类算法直接在相似矩阵上进行分割,对结果的准确性影响较大,而局部和全局正则化聚类算法未考虑数据空间分布对结果的影响。为此,引入离散度矩阵对局部和全局正则化聚类算法进行改进。改进算法考虑数据的分布信息,通过在局部信息目标函数中引入离散度矩阵,结合全局信息的目标函数,将目标函数最小化问题转换为分解稀疏矩阵特征的问题。在UCI机器学习数据集和公共数据挖掘数据集上的实验结果表明,与K-means及标准谱聚类算法相比,该算法的预测精度更高。     

自适应Rulkov神经元聚类算法

针对类间间距较小、可分性较差的样本数据聚类问题,文中提出自适应Rulkov神经元聚类算法.首先,构建基于自适应距离和共享近邻的相似度矩阵,将样本构成的无向图的最优分割问题转化为拉普拉斯矩阵的谱分解问题,并按特征值大小选取拉普拉斯矩阵的特征向量作为新的样本特征,增大样本类间间距,减小类内间距.然后,将样本根据新特征映射为神经元,样本特征距离决定神经元之间的耦合权值,通过耦合强度自学习进一步提升样本可分性.最后,通过强连通分量实现样本聚类.在多个合成数据集和真实数据集上的实验表明文中算法获得较优的聚类效果.     

结合共享近邻和流形距离的自适应谱聚类算法

谱聚类算法是建立在图论的基础上,将聚类问题转化为图的划分问题,能识别任意形状的类簇且易于实现,因此比传统聚类算法具有更强的适应性。然而,该算法中常用的距离度量不能同时考虑全局和局部一致性,且易受到噪声影响;聚类结果依赖由输入数据构造的相似度矩阵,且通过特征分解得到松弛划分矩阵和离散化过程的两步独立策略难以得到一个共同最优解。因此,提出一种结合共享近邻和流形距离的自适应谱聚类算法(SNN-MSC),引入一种新的具有指数项和比例因子的流形距离,可以灵活调整同一流形内数据的相似度和不同流形之间数据的相似度之比,并将密度因子纳入流形距离度量中,以消除噪声影响;采用共享近邻重新定义相似度度量,能挖掘数据点之间的空间结构和局部关系;同时,对拉普拉斯矩阵施加秩约束,使相似度矩阵中的连通分量完全等于簇个数,能够在优化求解过程中自适应优化数据相似度矩阵和聚类结构,无须再进行离散化操作。在人工数据集和UCI真实数据集上的对比实验显示,所提算法在多个聚类有效性指标上能体现出更好的性能。     

一种基于模糊核聚类的谱聚类算法

谱聚类是对样本拉普拉斯矩阵的特征向量进行聚类,不局限于原始数据的分布形状,可收敛于全局最优解,但不能准确反映样本间的实际关系,而模糊核聚类可利用模糊数学理论确定样本间的模糊关系。为此,在调整相似度度量函数和距离度量函数的基础上,将模糊核聚类融合到谱聚类算法中,提出SC-KFCM算法,利用模糊划分改进谱聚类中的硬划分,根据特征向量间的相似性和关联程度建立模糊隶属关系并对样本进行聚类,从而弥补谱聚类中硬划分部分对聚类结果造成的影响。实验结果表明,SC-KFCM算法在不同分布特点及维数的数据集上均取得了较稳定的聚类结果和较高的聚类精度。     

一种基于数据垂直划分的分布式密度聚类算法

聚类分析是数据挖掘领域的一项重要研究课题,对大数据集的聚类更以其数据量大、噪声数据多等而成为一个难点.针对数据垂直划分的情况,提出连通点集及局部噪声点集等概念.在分析局部噪声点集与全局噪声点集以及局部连通点集与全局连通点集关系的基础上,对全局噪声点进行有效过滤,进一步设计闭三角链表结构存储各个结点的聚类中间结果,提出了基于密度的分布式聚类算法DDBSCAN.理论分析和实验结果表明,算法可以有效解决垂直划分的大数据集聚类问题,算法是有效可行的.     

无需特征分解的快速谱聚类算法

为了解决样本数较大时,传统谱聚类算法执行特征分解消耗时间过大的问题,提出了一种无需特征分解的快速谱聚类算法,通过乘法更新迭代来降低时间开销。首先,利用Nyström方法进行随机采样,建立了采样矩阵和原始矩阵之间的关系;其次,基于乘法更新原理实现矩阵指示器矩阵的迭代更新;最后,在理论上对所设计算法进行了正确性和收敛性分析。在广泛使用的五个真实数据集和三个人工合成数据集上进行测试。实验结果表明,在真实数据集上,所提算法的标准互信息（NMI）平均值为0.45,与k-means聚类算法相比提高了12.50%;运行时间为61.73 s,与传统谱聚类算法相比减少了61.13%;而且表现性能优于层次聚类算法,验证了该算法的有效性。     

局部相似性优化的p-谱聚类算法

通过引入p-Laplacian算子,谱聚类算法得以获得较好的图切判据。但算法中的相似矩阵未能充分挖掘数据样本的局部结构信息,同时相似性的计算与数据样本的聚类是在两个不同的步骤中实现的,故得到的相似矩阵并不一定是最适合此聚类方法的,从而得不到最优的聚类结果。因此,提出了基于局部相似性优化的p-谱聚类算法。该算法通过数据样本的自适应和最优近邻之间的局部距离来优化相似性测度的方法,同时通过p-Laplacian矩阵的秩约束,可以得到对应无向图中连通分量的数目等于聚类数目。实验表明,基于局部相似性优化的p-谱聚类算法可以获得更好的聚类效果。     

无需特征分解的快速谱聚类算法

为了解决样本数较大时，传统谱聚类算法执行特征分解消耗时间过大的问题，提出了一种无需特征分解的快速谱聚类算法，通过乘法更新迭代来降低时间开销。首先，利用Nyström方法进行随机采样，建立了采样矩阵和原始矩阵之间的关系；其次，基于乘法更新原理实现矩阵指示器矩阵的迭代更新；最后，在理论上对所设计算法进行了正确性和收敛性分析。在广泛使用的五个真实数据集和三个人工合成数据集上进行测试。实验结果表明，在真实数据集上，所提算法的标准互信息（NMI）平均值为0.45，与k-means聚类算法相比提高了12.50%；运行时间为61.73 s，与传统谱聚类算法相比减少了61.13%；而且表现性能优于层次聚类算法，验证了该算法的有效性。     

基于局部协方差矩阵的谱聚类算法

针对传统谱聚类算法没有解决簇划分过程中,簇间交叉区域样本点对聚类效果有影响这个问题,提出一种基于局部协方差矩阵的谱聚类算法,主要介绍了一种新的计算样本之间相似度亲和矩阵的方法,即通过计算样本点之间的欧氏距离划分出小子集,计算小子集的协方差,通过设定阈值剔除交叉点,由剩下的点构造相似矩阵,对相似矩阵进行特征值分解,用经典的[k]-means算法对由特征向量组成的矩阵聚类。通过在Control等真实数据集上的实验结果表明,该算法在聚类准确率、标准互信息等指标上比较对比算法获得更优秀的效果。     

面向多视图聚类的低秩张量表示学习

针对现有鲁棒图学习忽略多视图间的互补信息和高阶相关性问题,提出一种面向多视图聚类的低秩张量表示学习（LRTRL-MVC）算法。利用鲁棒主成分分析的思想,在去除噪声的干净数据上计算各视图的鲁棒图和转移概率矩阵,然后构建一个包含各视图马尔可夫转移概率矩阵的张量,采用基于张量奇异值分解的核范数来确保目标张量的低秩性质。利用迭代最优化算法求解,将求得的低秩张量作为马尔可夫谱聚类算法的输入得到最终聚类结果。在4个不同类型的公开标准数据集BBCSport、NGs、Yale和MSRCv1上进行实验并与相关的最好多视图聚类算法进行对比,结果表明在3个聚类度量标准下,所提算法的聚类结果均高于其他对比算法。     

Non-negative Matrix Factorization with Symmetric Manifold Regularization

Non-negative matrix factorization (NMF) is becoming an important tool for information retrieval and pattern recognition. However, in the applications of image decomposition, it is not enough to discover the intrinsic geometrical structure of the observation samples by only considering the similarity of different images. In this paper, symmetric manifold regularized objective functions are proposed to develop NMF based learning algorithms (called SMNMF), which explore both the global and local features of the manifold structures for image clustering and at the same time improve the convergence of the graph regularized NMF algorithms. For different initializations, simulations are utilized to confirm the theoretical results obtained in the convergence analysis of the new algorithms. Experimental results on COIL20, ORL, and JAFFE data sets demonstrate the clustering effectiveness of the proposed algorithms by comparing with the state-of-the-art algorithms.

     

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

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

图优化的低秩双随机分解聚类

低秩双随机矩阵分解聚类(low-rank doubly stochastic matrix decomposition for cluster analysis，DCD)是最近由Yang等人[16]提出的一种图聚类方法，它通过最小化KL(Kullback-Leibler)散度准则：KL(A，S)，从图关联矩阵S中获得一个非负低秩双随机矩阵分解：A=UUT(U(0)，并以U作为类标签矩阵进行聚类。在DCD方法中，因矩阵S是固定不可变的，故S初始取值选取的好坏对聚类结果有极大影响，这导致了它缺乏稳定性。针对这一问题，提出了一种基于图优化的DCD方法，将图关联矩阵S和DCD的优化集成在统一框架中，这改进和拓展了原始的DCD方法。实验结果表明，与DCD方法相比，图优化的DCD方法具有更好的聚类精确度和稳定性。     

基于约束优化传播的改进大规模数据半监督式谱聚类算法

针对传统谱聚类算法在聚类过程中所出现的高计算复杂度、噪声敏感,以及聚类簇形态偏斜等问题,结合当前大规模数据聚类的特点与需求,本文建立基于约束优化传播的改进大规模数据半监督式谱聚类模型。该模型首先利用先验成对点约束信息构建微型相似性矩阵,在此基础上采用Gabow算法提取该微型相似性矩阵所对应连通图的各强连通分支,继而提出面向各强连通分支的新型约束优化传播算法以获取整个数据集的点对相似度,最后通过奇异值分解并运用加速k-means算法获得大规模数据的聚类结果。在多个标准测试数据集上的实验表明,相比于该领域其它前期研究成果,本文所提聚类模型具有更高的聚类准确率和更低的计算复杂度,更适合大规模数据的聚类应用。     

基于奇异值分解的新闻标题聚类研究

和导航中应用广泛。文本聚类作为一种无监督学习算法,其依据是聚类假设:同类的文档相似程度大,不同类的文档相似程度小。文中主要研究汉语文本聚类算法在新闻标题类文本中的应用。首先对采集到的若干条新闻标题进行分词和特征提取,将分词后的文本转化为词条矩阵;然后使用TF-IDF技术处理词条矩阵,得到基于分词权重的新的词条矩阵,对新的词条矩阵进行奇异值分解,得到主成分得分矩阵,提取主成分分析文本特征并根据主成分得分矩阵进行K-均值和分层聚类分析;最后将聚类结果用词云图的形式展示出来并评价聚类效果的好坏。实证显示,对词条矩阵的奇异值分解能降低向量空间的维数,提高聚类的精度和运算速度。     

基于主元的多元时间序列聚类分析方法研究

为提高多元时间序列聚类算法的效率,采用基于主元分析的多元时间序列聚类方法,将原始多元时间序列元素划分成一系列互不相关的簇,根据各簇的代表元素和剩余元素的主元素之间的扩展欧几里德范数对多元时间序列进行聚类分析.理论分析和实验结果表明该算法聚类质量结果和运行时间明显优于直接利用K-means法时的聚类结果.     

Manifold-ranking based retrieval using k-regular nearest neighbor graph

Manifold-ranking is a powerful method in semi-supervised learning, and its performance heavily depends on the quality of the constructed graph. In this paper, we propose a novel graph structure named k-regular nearest neighbor (k-RNN) graph as well as its constructing algorithm, and apply the new graph structure in the framework of manifold-ranking based retrieval. We show that the manifold-ranking algorithm based on our proposed graph structure performs better than that of the existing graph structures such as k-nearest neighbor (k-NN) graph and connected graph in image retrieval, 2D data clustering as well as 3D model retrieval. In addition, the automatic sample reweighting and graph updating algorithms are presented for the relevance feedback of our algorithm. Experiments demonstrate that the proposed algorithm outperforms the state-of-the-art algorithms.     

Connected graph decomposition for spectral clustering

Multimedia Tools and Applications - This paper proposes a new spectral clustering method based on local Principal Component Analysis (PCA) and connected graph decomposition. Specifically, our...     

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

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