论文摘要
聚类分析技术作为一种有效的工具,在数据挖掘和机器学习相关领域有关广泛的研究和应用。目前,存在大量的成熟的有效的聚类算法,其中，谱聚类算法由于它的深厚的数学理论基础和广泛的应用性,近年来得到了越来越多研究者的关注。谱聚类算法最大的优势在于它的简单,易懂。通过特征空间的映射,将原空间中有挑战性的聚类问题转化为更为直观的容易解决的形式。利用目前已经存在的成熟的特征分解的库,很容易能够实现谱聚类算法。并且,关于谱聚类算法的性能分析有很多有影响力的研究成果。但是,谱聚类算法本身过高的空间(相似度矩阵的存储)和时间(特征分解的计算)复杂度极大的限制了在解决大规模数据集上的可行性。为了降低谱聚类算法在大规模数据集上的复杂度,经常会使用一些低秩逼近去近似一个矩阵。Nystrom方法是一种有效的产生地址逼近矩阵的方法。并且,抽样点的算则是最重要的一个方面。已经存在对于当前存在的几种抽样方法在一些机器学习领域中的误差的理论上的分析。本文中,我们首先简单的总结和概括了关于谱聚类算法的当前的研究现状。并重点介绍和总结了关于Nystrom扩展在谱聚类算法上的应用技术,特别是当前已有的比较成功的抽样算法。但是,目前由于还没有关于矩阵逼近误差对于谱聚类性能分析的研究,在本文中,我们首先使用了可聚类能力的概念来分析Nystrom扩展方法的性能,然后进一步分析了矩阵逼近误差对于谱聚类算法性能的影响。我们的分析结果给出了一种增量的Nystrom扩展的抽样方法。实验结果进一步验证了我们提出的算法的有效性,该算法在一系列聚类任务上都给出了优于已经存在的抽样算法。并且它的时间复杂度并没有大幅度的增加。