一种基于粗糙集理论的谱聚类算法

谱聚类算法利用特征向量构造简化的数据空间,在降低数据维数的同时,使得数据在子空间中的分布结构更加明显.现有谱聚类算法的聚类结果多为精确集,而真实数据集中重叠现象广泛存在.基于粗糙集理论提出了一种新的谱聚类算法,其主要思想是对谱聚类算法进行粗糙集扩展,使得聚类结果成为具有下近似和上近似定义的、类与类之间存在重叠区域的结构.实验表明,该算法与现有的谱聚类算法相比,稳定性和准确率都有一定的提高.     

基于改进SimRank的产品特征聚类研究

针对在线用户评论中产品特征的提取和聚类问题进行了研究,提出一种改进的SimRank算法,将情感词-特征对放入二分网中,在二分网中使用改进后的SimRank算法计算特征词之间的相似度;再通过谱聚类算法对特征相似度进行聚类,提取网络产品的特征集合。以某电脑评论为例,从中提取情感词-特征对进行研究,实验结果显示,改进后的算法准确率更高。改进后的特征相似度检测方法可以作为检测特征相似度的有效方法。实验采用在线产品的评论语料,实验结果表明使用改进后的SinRank相似度对特征词进行聚类提取出特征更加准确。     

基于黎曼流形的多视角谱聚类算法

现有的多视角谱聚类算法大多只线性结合了各视角的基拉普拉斯矩阵,未考虑不同视角数据的差异性对最优拉普拉斯矩阵的影响,存在聚类性能受限的问题。提出一种基于黎曼几何均值与高阶拉普拉斯矩阵的谱聚类算法(RMMSC),挖掘多视角数据中的高阶连接信息与流形信息,提高最优拉普拉斯矩阵对各视角的信息利用率。按一定的权重线性结合数据单一视角的各阶拉普拉斯矩阵,得到每个视角的基拉普拉斯矩阵,通过低阶与高阶连接信息的结合使用,充分体现多视角数据集的全局结构。在此基础上,计算各视角基拉普拉斯矩阵的黎曼几何均值,将其作为最优拉普拉斯矩阵输入谱聚类算法,得到聚类结果。相比于传统矩阵算数均值的计算,基于黎曼流形的黎曼几何均值能够更好地恢复互补层数据的流形信息。实验结果表明,RMMSC在多组标准数据集上聚类效果优于ONMSC、MLAN、AMGL等算法。其中,在Flower17数据集上,精确度较基准算法ONMSC提高了2.14%,纯度提高了1.7%,且收敛性较好。     

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

谱聚类的现状及其在社会网络中的应用

近年来,凭借其重要的研究意义,采用数据聚类去分析社会网络已成为时下最热门的话题之一。这些研究最直接应用的是防止恐怖袭击和社区通过检测疾病的传播。此外,由于社会网络是动态的,而社会关系的变化是可以通过数据聚类方法预测的。从而使得清楚了解社会网络结构将有助于促进社会发展和社会成员间的合作。从数据挖掘角度来看,社交网络是一种不完全的,庞大的,复杂的,动态的网络。而这些特性使得传统的数据聚类方法并不能成功应用在社会网络中。相反,作为一个最流行的现代数据的聚类算法,谱聚类在对社交网络的问题提供了一种系统的,灵活实用的解决方案。理论和实验证明,谱聚类在寻找全局最优解和处理大型数据集方面的性能优于传统聚类算法。一方面审视讨论当今谱聚类的理论和算法,及其优于传统聚类算法的特点。另一方面,也涵盖了社会网络的基本知识及两个典型的谱聚类在社会网络中的应用。     

改进的基于谱聚类的子空间聚类模型

子空间聚类的目的是将来自不同子空间的数据分割到其本质上所属的低维子空间。现有的基于数据的自我表示和谱聚类的子空间聚类算法将该问题分为两个连续的阶段：首先从高维数据中学习数据的相似性矩阵,然后通过将谱聚类应用于所学相似性矩阵来推断数据的聚类隶属。通过定义一种新的数据自适应稀疏正则项,并将其与结构稀疏子空间聚类（SSSC）模型和改进的稀疏谱聚类（SSpeC）模型相结合,给出了一个新的统一优化模型。新模型利用数据的相似度和聚类指标的相互引导克服了SSpeC稀疏性惩罚的盲目性,并使得相似度具有了判别性,这有利于将不同子空间的数据分为不同类,弥补了SSSC模型只强制来自相同子空间的数据具有相同标签的缺陷。常用数据集上的实验结果表明,所提模型增强了聚类判别的能力,优于一些经典的两阶段法和SSSC模型。     

基于用户谱聚类的协同过滤推荐算法

针对电子商务系统中传统协同过滤推荐算法面临的稀疏性、准确性、实时性等问题,提出了一种基于用户谱聚类的协同过滤推荐算法。首先利用非负矩阵分解的方法对原始稀疏评分矩阵进行平滑处理,然后利用改进相似度的谱聚类方法将用户聚类,最后在用户所属类中寻找最近邻并产生推荐。用户谱聚类过程可离线完成,加快了在线推荐速度。在数据集MovieLens上的实验结果表明,该算法在平均绝对偏差、召回率、准确率等方面都有了较大改善,提高了推荐质量。     

一种改进的k-均值聚类算法

针对k-均值(k-means)聚类算法中随机选取初始聚类中心的缺陷,提出了一种新的基于数据样本分布选取初始聚类中心的方法.实验结果表明,改进后的算法能改善其聚类性能,并能取得较高的分类准确率.     

一种改进的Nystrom谱聚类图像分割算法

基于图论的图像谱分割是近年来研究热点。本文针对在高分辨率图像的分割中,相似度矩阵和拉普拉斯矩阵的构造数据量大,比较耗时的缺点,提出用基于方差增量的Nystrom方法有效减少矩阵规模,并且采用基于余弦相似度构造权值矩阵,避免了传统的利用高斯公式需人工选择尺度参数。最后,通过在Berkeley图像库上的图像分割实验表明了本算法的可行性和有效性。     

基于SimRank全局矩阵平滑收敛的网络社区发现

SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法(SimRank global smooth convergence,SGSC).首先,该算法通过经典...     

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.     

Fuzzy spectral clustering with robust spatial information for image segmentation

In recent years, spectral clustering has become one of the most popular clustering algorithms in areas of pattern analysis and recognition. This algorithm uses the eigenvalues and eigenvectors of a normalized similarity matrix to partition the data, and is simple to implement. However, when the image is corrupted by noise, spectral clustering cannot obtain satisfying segmentation performance. In order to overcome the noise sensitivity of the standard spectral clustering algorithm, a novel fuzzy spectral clustering algorithm with robust spatial information for image segmentation (FSC_RS) is proposed in this paper. Firstly, a non-local-weighted sum image of the original image is generated by utilizing the pixels with a similar configuration of each pixel. Then a robust gray-based fuzzy similarity measure is defined by using the fuzzy membership values among gray values in the new generated image. Thus, the similarity matrix obtained by this measure is only dependent on the number of the gray-levels and can be easily stored. Finally, the spectral graph partitioning method can be applied to this similarity matrix to group the gray values of the new generated image and then the corresponding pixels in the image are reclassified to obtain the final segmentation result. Some segmentation experiments on synthetic and real images show that the proposed method outperforms traditional spectral clustering methods and spatial fuzzy clustering in efficiency and robustness.     

基于网格Laplace的三维几何模型分割

模型分割是模型分析的重要方法和手段.针对已有网格分割算法对姿态敏感和计算速度慢的问题,提出了一种基于网格Laplace和k-means聚类的三维几何模型分割算法.通过网格Laplace将三维模型从空域嵌入到谱空间中进行分析,得到了模型的归一化形式,克服了姿态变化对分割结果的影响,并极大地减少了计算时间,获得了视觉上有意义的分割结果.实验结果表明,本算法能快速有效地实现网格模型的正确分割,并对模型姿态的变化有较好的鲁棒性.     

K-means ■隐私保护聚类算法

针对异常离群点对k-means ■算法的聚类精确度影响较大且在确定中心点过程中会泄露聚类数据隐私的问题,提出DPk-means ■算法。标记离群点,降低离群点对k-means ■算法聚类精确度的影响,将差分隐私应用于k-means ■聚类算法中保护聚类数据隐私。在选择聚类初始中心点和迭代求取均值中心点的过程中,应用拉普拉斯机制注入噪声,解决数据隐私泄露的问题。通过隐私预算动态变化对聚类结果准确性的影响及同类算法对比实验分析验证,DPk-means ■算法能够提供更高的隐私保护水平且保证聚类结果的准确性。     

基于全序列比对相似度的用户会话自动谱聚类

针对现有个性化推荐服务系统中用户会话聚类算法存在相似性度量准确性低和需要事先确定聚类数目的问题,对序化的用户访问页面和对应的访问时间信息进行整合,提出一种基于动态规划算法的全序列比对方法来度量用户会话的相似性。在此基础上,运用改进的NJ W谱聚类算法对用户会话进行自动谱聚类。实验结果表明,算法充分考虑了用户会话的整体特征和局部信息,较相关比对算法具有更高的聚类性能,可以提高网站个性化推荐服务的效率。     

谱聚类算法研究及其在图像分割中的应用

提出了一种改进谱聚类的算法。首先介绍了谱聚类和基于路径的思想;然后为了改善传统谱聚类算法对GAUSS函数中尺度参数的敏感性,提出了一种新算法,并将其扩展到半监督的情况;最后将其应用在图像分割实验中,证明了该算法的有效性。     

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

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

一种基于空间邻接关系的k-means聚类改进算法

空间对象不仅具有非空间的属性特征，而且具有与空间位置、拓扑结构相关的空间特征。利用传统的聚类方法对空间对象进行聚类时，由于没有考虑空间关系，同一类的对象可能出现在空间不相邻的位置。基于空间邻接关系的k-means改进算法将相邻对象的空间邻接关系作为约束条件加以考虑，使聚类结果既反映了属性特征的相似程度，又反映了对象的空间相邻状态，从而可以揭示不同类别对象的空间分布格局，因此其比传统的k-means方法更适合于空间对象的聚类分析。