Abstract: 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.

Key words: spectral clustering, text clustering, large datasets

摘要： 针对谱聚类存在计算瓶颈的问题，提出了一种快速的集成算法，称为间接谱聚类。它首先运用K-Means算法对数据集进行过分聚类，然后把每个过分簇看成一个基本对象，最后在过分簇的级别上利用标准谱聚类来完成总体的聚类。将该思想应用于大文本数据集的聚类问题后，过分簇中心之间的相似性度度量方法可以采用常用的余弦距离法。在20-Newgroups文本数据上的实验结果表明：间接谱聚类算法在聚类准确性上比K-Means算法平均高出14.72%;比规范割谱聚类仅低0.88%，但算法所需的计算时间平均不到规范割谱聚类的1/16,且随着数据集的增大当规范割谱聚类遭遇计算瓶颈时，提出的算法却能快速地给出次优解。

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