基于密度敏感的改进自适应谱聚类算法

针对谱聚类算法在构造相似矩阵时对尺度参数敏感以及对多尺度数据集聚类效果不太理想的问题,提出了基于密度敏感的改进自适应谱聚类算法.首先利用密度差来调整簇类样本点之间的相似度构造新的相似矩阵函数,然后利用新的相似矩阵构造拉氏矩阵,选取拉氏矩阵的前k个最大特征值对应的特征向量组成新的向量空间,新的向量空间中的点与原始数据一一对应,最后引入K-means聚类算法对数据点进行聚类.该算法在降低对尺度参数敏感性的同时又改善了对多尺度数据集的处理.通过在人工数据集以及UCI数据集仿真实验结果表明,本文提出的算法具有较优的聚类效果.     

基于信息熵属性赋权的谱聚类算法研究

针对谱聚类算法在处理较大规模的样本时,在存储空间和计算时间上都存在瓶颈问题,文章分析了目前常见的两种解决方式,即基于稀疏化t近邻的谱聚类和基于Nystr9m矩阵低秩逼近的谱聚类方法.为了进一步提高这两种谱聚类算法的准确度,提出了采取基于信息熵属性赋权的欧式距离来计算样本间的相似度的方法.首先,计算样本各属性的权重;然后,计算样本间的相似度矩阵并应用到稀疏化t近邻的谱聚类和Nystr9m矩阵低秩逼近的谱聚类方法中;最后,在多个数据集上进行了验证.实验结果表明该方法在一些数据集上的聚类精确度要比原来谱聚类算法高,尤其在Pendigits数据集上,基于信息熵赋权的稀疏化t近邻谱聚类比稀疏化t近邻谱聚类方法精确度提高15.11%.     

一种基于余弦函数和矩阵变换的谱聚类算法

为了实现快速谱聚类分析,设计了一种基于余弦函数和矩阵变换的谱聚类算法(CMTSC).CMTSC将余弦函数和矩阵变换技术融入到了谱聚类算法之中.利用余弦函数构造了相似度矩阵W,跳过了传统谱聚类算法中设置尺度因子的过程,随后利用矩阵变换技术实现了矩阵W的特征值分解,降低了分解的计算复杂度.在UCI数据库中部分数据集上的聚类实验和Berkeley图像库中部分图像上的分割实验,验证了CMTSC的有效性和高效性.     

基于快速谱聚类的图像分割算法

设计了一种基于快速谱聚类的图像分割算法,该算法利用余弦相似度构造相似度矩阵,避免了传统谱聚类算法中尺度因子的精确设置问题,提高了算法效率.在谱映射的过程中,该算法采用了Nystrm逼近策略,降低了谱聚类算法的复杂度和内存消耗.在Berkeley图像库上的图像分割实验证明了算法的有效性.     

基于多层次聚类的纹理图像分割算法

提出了一种基于多层次聚类的算法,此算法相对传统算法降低了空间和时间复杂度,并减少了对参数的敏感度,适合处理大规模数据集.该算法包括粗分、代表点聚类和细分三个阶段.首先,利用亲和传播聚类(AP)算法对所有数据进行粗分,为了节省空间和时间,仅考虑每个点和离自己最近的t个近邻之间的相似度,所以构造的相似度矩阵远远小于原始AP算法所构造的相似度矩阵;其次,为了进一步提高效率和性能,在第二阶段采用密度峰值算法(FDP)对上一阶段所得结果进行再划分;最后,结合两个阶段划分的结果得到所有数据的划分.实验表明:所提算法可以快速准确地进行图像分割,和经典聚类算法FCM(模糊C均值)、Kmeans以及SOM(自组织映射)的对比实验也证明了所提算法的有效性.     

基于类内和类间距离的粗粒度并行AP聚类算法

近邻传播(Affinity Propagation,AP)聚类是基于数据点间消息传递的算法,主要通过数据间的相似度实现聚类.与传统的聚类方法相比,AP聚类无需事先给定聚类数目就可实现聚类,因此具有快速高效的优点,然而在处理高维复杂数据集时存在随着聚类效率提升而准确度不高的问题.为改善AP聚类算法的效率和精度,提出基于类内和类间距离的粗粒度并行AP聚类算法——IOCAP.首先引入粒度思想将初始数据集划分成多个子集;其次对各子集结合类内和类间距离进行相似度矩阵的改进计算,最后基于MapReduce模型实现改进后的并行AP聚类.在真实数据集上的实验表明,IOCAP算法在大数据集上有较好的适应性,能在保持AP聚类效果的同时有效地提升算法精度.     

基于局部线性嵌入的半监督仿射传播聚类算法

针对运用半监督仿射传播聚类算法处理高维数据时聚类精度低和计算量大的问题,提出一种基于局部线性嵌入的半监督仿射传播聚类算法.该算法首先通过LLE算法将高维输入数据集映射到低维空间得到低维数据集,计算低维数据集的相似度矩阵,再用半监督算法调整相似度矩阵,最后用仿射传播聚类算法对低维数据进行聚类分析.仿真结果表明,本文提出的算法与半监督仿射传播聚类算法相比,在处理高维数据时聚类效果更好,精度更高,迭代次数更少.     

一种基于流形距离核的谱聚类和量子聚类融合算法

谱聚类是一种基于图谱划分理论的聚类算法,本质上是将聚类问题转化为图的最优划分问题;量子聚类可以充分挖掘数据样本的内在信息,是一种基于划分的无监督聚类算法.为了充分发挥谱聚类算法和量子聚类算法的优势,本文提出了一种基于流形距离核的谱聚类和量子聚类融合算法(MFD-NJW-QC).首先,计算数据集的流形距离核矩阵,构造相应的拉普拉斯矩阵;其次,根据拉普拉斯矩阵的若干最大特征值对应的特征向量构造新数据集,并使用量子聚类算法对新构造的数据集进行聚类,从而得到原始数据的类标签;最后,基于7个人工数据集和5个UCI数据集验证MFD-NJW-QC算法的聚类性能.结果显示,MFD-NJW-QC算法能够明显提高聚类性能,尤其对于具有流形结构,且类簇大小不平衡、密度分布不均匀的数据集优势更为突出.     

基于二次分水岭和近邻传播聚类的彩色图像分割算法研究与实现

利用特征散度普适能力强的优势,提出了基于二次分水岭和近邻传播聚类的彩色图像分割算法.算法通过二次分水岭算法预分割,提取区域中色彩向量数据点,利用特征散度构造相似度矩阵,运用近邻传播数据聚类,实现图像的分割.实验证明,算法较好地避免了聚类算法对初始条件的依赖性,降低了彩色图像大样本数据的运算量,与人的主观视觉感知具有良好的一致性.     

基于三种近邻网络的聚类算法研究

根据K近邻、共享K近邻和互K近邻三种近邻算法的思想分别构造复杂网络,然后通过复杂网络的社团发现算法来实现对样本的聚类.最后,将三种方法分别在人工构造的非凸类簇数据集和UCI数据集上进行仿真实验,结果表明三种方法都是可行的,且互K近邻网络聚类方法还具有识别一定数量孤立点功能.     

基于自适应图的降维方法

为了构建能反映高维数据本质结构的高质量图,提出了一种新颖的降维方法———基于自适应图的降维方法( DＲAG: Dimensionality Ｒeduction based on Adaptive Graphs) 。与其他传统的基于图的降维方法相比,提出的DＲAG 避免了传统k 近邻或ε 球准则构图策略中的参数选择问题,考虑了数据的局部信息和噪声,能自适应地构建稀疏的最优图结构,并将其结合在经典的LPP( Locality Preserving Projection) 模型中,学习能有效刻画高维数据本征结构的投影矩阵,从而实现降维的目的。为了评估算法的有效性和可行性,在4 个标准的图像数据库( CMU PIE,Extended YaleB,OＲL 和COIL 20) 分别进行了分类与聚类实验,实验结果表明,所提出的方法在分类识别率和聚类准确率上都优于其他对比方法。     

一种改进的稀疏子空间聚类算法

在现有的稀疏子空间聚类算法基础上提出了一个改进的稀疏子空间聚类算法。首先,利用高维数据可以通过同一子空间的低维数据稀疏地表示这一理论,建立一个稀疏最优化模型,获得稀疏矩阵。然后把稀疏矩阵应用到一个正则化谱聚类算法中,从而有效地把数据聚类到子空间中。最后,该算法应用到一个视频序列中,对每个视频帧里的运动物体进行识别,并与现有的子空间聚类算法相比较。实验结果表明,该算法能够有效地识别运动物体,具有良好的实时性和有效性。     

Game Theoretical Approach for Non-Overlapping Community Detection

Graph clustering, i.e., partitioning nodes or data points into non-overlapping clusters, can be beneficial in a large varieties of computer vision and machine learning applications. However, main graph clustering schemes, such as spectral clustering, cannot be applied to a large network due to prohibitive computational complexity required.While there exist methods applicable to large networks, these methods do not offer convincing comparisons against known ground truth. For the first time, this work conducts clustering algorithm performance evaluations on large networks(consisting of one million nodes) with ground truth information. Ideas and concepts from game theory are applied towards graph clustering to formulate a new proposed algorithm, Game Theoretical Approach for Clustering(GTAC). This theoretical framework is shown to be a generalization of both the Label Propagation and Louvain methods, offering an additional means of derivation and analysis. GTAC introduces a tuning parameter which allows variable algorithm performance in accordance with application needs. Experimentation shows that these GTAC algorithms offer scalability and tunability towards big data applications.     

基于谱聚类的词和文档的联合聚类

文档聚类和词聚类都是重要且被充分研究的问题.大多数现有的聚类算法针对文档和词是分别聚类,不是同时的.本文提出文档集作为文档和词间的一个二部图的模型思想,使用这个思想,联合聚类问题可以被看成二部图的分割问题.为了解决图的分割问题,使用一个新的联合谱聚类算法,即使用适度规模的词-文档矩阵的奇异向量产生好的分割结果.谱算法得到一些最佳的性能,表明奇异向量通过连续放松解决图划分的NP难问题.最后通过实验结果验证联合聚类算法在实践中非常有效.     

大规模数据集聚类的K邻近均匀抽样数据预处理算法

为解决基于密度的聚类算法处理大规模数据集效率低和存储开销大的问题, 提出一种分片的基于K邻近关系的空间均匀抽样算法作为聚类应用的数据预处理过程, 将数据集分片,按密度降序方式去除数据集中部分样本的K邻居, 将剩余样本作为抽样样本, 在保证精度的同时, 可以降低数据规模, 提升计算效率. 实验结果表明, 在数据规模较大且保证聚类结果准确性的前提下, 通过降低聚类数据规模, 可以有效提升聚类效率.     

利用测地线距离的改进谱聚类算法

针对往复式压缩机故障数据空间分布复杂、常规算法不能有效聚类的问题,提出了一种改进的谱聚类算法.该算法使用新的相似度矩阵计算方式,根据故障数据流形分布的特点引入测地线距离取代欧氏距离作为数据间的关系度量;通过计算各数据点的邻域密度因子有效地识别和剔除了噪声点;利用基于密度的局部欧氏距离调整方法对流形间隙过小的区域进行了处理.在几个人工数据集和往复式压缩机故障数据集上的测试结果表明,改进谱聚类算法对于具有流形分布、多尺度、有噪声、流形间隙过小甚至交叉等特点的数据具有很好的聚类能力,聚类准确率比常规的k-均值和MSCA谱聚类算法分别提高了50.86%和8.6%.     

基于DCBM的马尔可夫谱聚类社区发现算法

谱聚类划分算法是经典社区发现算法之一,由于目前构造的相似图承载的社区结构信息较少,导致聚类效果与理想效果具有较大差距,因此,提出了基于DCBM的马尔可夫谱聚类社区发现算法MSCD.首先,基于DCBM模型提出了以节点间连接概率为元素的概率矩阵,并建立了概率矩阵与相似矩阵之间的映射关系;其次,利用马尔可夫链重构了谱聚类的相似图;最后,使用重构的相似图对网络进行社区划分.在人工合成网络和真实网络上与SC,MRW-KNN和FluidC三种典型算法进行了对比实验.实验结果表明,MSCD算法具有更加高效的聚类性能,能够揭示更加清晰的社区结构.     

基于中心自动融合的多尺度可能性聚类算法

针对可能性聚类对初始化参数设置依赖性较强的问题, 提出一种基于中心自动融合的可能性聚类算法, 并证明了算法中尺度因子的多尺度性质. 该算法通过建立中心的相关性判定准则, 根据数据自身分布特点动态调整聚类数目与结构, 通过引入尺度参数实现对数据的多分辨率分析. 与传统的模糊和可能性聚类算法相比, 该算法摆
脱了对聚类数目及初始化中心或隶属度矩阵设置的依赖性, 易于控制. 人造数据和真实数据实验结果表明, 该算法能自动确定数据中不同尺度下的聚类结构, 具有识别不同大小聚类结构的能力.     

一种基于密度的网格动态聚类算法的研究

聚类算法是数据挖掘领域中一个非常重要的研究方向.至今为止人们已经提出了许多适用于大规模的、高维的数据库的聚类算法.基于密度的聚类算法是其中一个比较典型的研究方向,文中以DBSCAN为基础,提出一种基于密度的网格动态聚类算法.新算法将网格的原理运用到基于密度的聚类算法中,并采用了动态的参数法,能自动根据数据的分布情况进行必要的参数更改,有效减少DBSCAN对初始参数的敏感度,从而提高了聚类的效率和效果,降低了算法I/O的开销.算法不仅能挖掘出各种形状的聚类,并能准确的挖掘出数据集中突出的聚类.