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

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