面向大文本数据集的间接谱聚类  

Indirect spectral clustering towards large text datasets

作　　者：侯海霞[1] 原民民[2] 刘春霞[3] 

机构地区：[1]太原大学计算机工程系,太原030032 [2]山西水利职业技术学院信息工程系,山西运城044000 [3]太原科技大学计算机科学与技术学院,太原030024

出　　处：《计算机应用》2012年第12期3274-3277,共4页journal of Computer Applications

基　　金：山西省青年科技研究基金资助项目(2011021014-3)

摘　　要：针对谱聚类存在计算瓶颈的问题,提出了一种快速的集成算法,称为间接谱聚类。它首先运用K-Means算法对数据集进行过分聚类,然后把每个过分簇看成一个基本对象,最后在过分簇的级别上利用标准谱聚类来完成总体的聚类。将该思想应用于大文本数据集的聚类问题后,过分簇中心之间的相似性度度量方法可以采用常用的余弦距离法。在20-Newgroups文本数据上的实验结果表明:间接谱聚类算法在聚类准确性上比K-Means算法平均高出14.72%;比规范割谱聚类仅低0.88%,但算法所需的计算时间平均不到规范割谱聚类的1/16,且随着数据集的增大当规范割谱聚类遭遇计算瓶颈时,提出的算法却能快速地给出次优解。To alleviate the computational bottleneck of spectral clustering,in this paper a general ensemble algorithm,called indirect spectral clustering,was developed.The algorithm first grouped a given large dataset into many over-clusters and then regarded each obtained over-cluster as a basic object.And then the standard spectral clustering ran at this object level.By convention,when applying this new idea to large text datasets,the cosine distance would be the appropriate manner in measuring the similarities between over-clusters.The empirical studies on 20-Newgroups dataset show that the proposed algorithm has a 14.72% higher accuracy on average than the K-Means algorithm and has a 0.88% lower accuracy than the normalized-cut spectral clustering.However,the proposed algorithm saves 16.8 times computation time compared to the normalized-cut spectral clustering.In conclusion,with the increase of data size,the computation time of the normalized-cut spectral clustering might become unacceptable;however,the proposed algorithm might efficiently give the near-optimal solutions.

关 键 词：谱聚类 文本聚类 大数据集 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]