Abstract: Coarsening phase is the most critical step among procedures in multilevel clustering algorithm. Some classical multilevel clustering algorithms, such as METIS (multilevel scheme for partitioning irregular graphs) and Graclus, use some criterions of vertex and edge weights to capture the collapsing of the vertex and edges and realize coarsening procedure. But there is the disadvantage that the coarsest dataset can not formulate the global information and structure of original dataset correctly. This paper proposes a core-sets coarsening method, which defines multilevel core-sets to retain global information of layered dataset in perspective. Meanwhile, as the coarsest dataset has the same number as clustering, and each core point corresponds to a single class, the partitioning procedure need not be considered. Some numerical experiments verify the superiority and availability of the proposed algorithm.

Key words: multilevel, coarsening, core-sets, clustering

摘要： 粗化是多层聚类算法中的关键步骤。经典的多层聚类算法，如METIS（multilevel scheme for partitioning irregular graphs）、Graclus等，利用顶点和边权的若干准则合并顶点和边，实现粗化，其缺点是粗化之后的小规模数据集无法准确表述原数据集的全局信息和结构。提出了核心集粗化（core-sets coarsening）的方法，通过定义“多层核心集”，逐层保留数据集的全局信息。同时，顶层核心点的个数与聚类个数相同，其每个核心点对应一个单独的类，因此不需要一般多层聚类中的划分过程。实验结果表明了该算法的有效性。

关键词: 多层, 粗化, 核心集, 聚类