【摘要】 谱聚类是利用样本数据集的相似性矩阵中特征向量的性质对样本数据集进行聚类.而随着数据规模的增加,谱聚类算法所耗时间会因为大规模的特征分解而明显增大.采用抽样方法可以有效降低算法所耗时间,但是简单随机抽样子集之间关联性太弱,通常无法准确反映数据集的分布特征.基于此,设计了一种新的抽样策略,利用该方法进行多次抽样,生成多个既具有关联性又具有差异性的数据子集.在每个数据子集上分别利用NJW算法(由Ng A Y、Jordom M I和Weiss Y提出)进行谱聚类,并根据最近邻原则将聚类结果映射到全体数据集,生成若干基聚类,最后,将聚类结果集成,得到最终的聚类划分.实验证明,该方法与传统NJW算法以及简单抽样集成算法相比,算法的效率及有效性有了一定的提高.更多还原

【Abstract】 Spectral clustering algorithm is an important one among clustering algorithms,and it uses the feature vectors of the similarity matrix calculated from the sample data set to cluster the sample data.However,the computational complexity and time consumption will increase markedly because of the large-scale calculation of eigen-decomposition when the spectral clustering is applied to large scale data sets.The use of sampling methods can effectively reduce the time consumed by the spectral clustering algorithm,but the relationship between the data subsets extracted by simple randomly sampling is too weak,which usually cannot reflect the distribution characteristics of the sample data sets accurately.Based on this and aimed at the computing characteristics of spectral clustering algorithm,a new sampling strategy different from the simple random sampling is designed and multiply used to generate multiple data subsets that can reflect the distribution characteristics of the sample data sets more accurately because of theircoexisting relevance and otherness.Then each data subset is spectral clustered by NJW algorithm(the most classical spectral clustering algorithm,proposed by Ng A Y,Jordom M I and Weiss Y)and every clustering results can be mapped to the whole sample data set according to the nearest neighbor principle,generating a number of component clusters which both have relevance and otherness.Finally,the clustering results of the whole sample data set are integrated to get the final unified clustering partition.Experimental results show that applying the proposed sampling method to the spectral clustering algorithm is effective compared with the traditional NJW algorithm and efficient compared with the ensemble algorithm of spectral clustering based on simple sampling.更多还原