文档介绍：Nanjing University of Aeronautics and Astronautics
The Graduate School
College of Science
Multilevel Core-sets based Aggregation
Clustering Algorithm
A Thesis in
Mathematics
by
Wang Xiuli
Advised by
Prof. Ma Runing
Submitted in Partial Fulfillment
of the Requirements
for the Degree of
Master of Science
December, 2012
承诺书
本人声明所呈交的硕士学位论文是本人在导师指导下进
谢的地方外,论文中不包含其他人已经发表或撰写过的研究成
果,也不包含为获得南京航空航天大学或其他教育机构的学位
或证书而使用过的材料.
本人授权南京航空航天大学可以将学位论文的全部或部
分内容编入有关数据库进行检索,可以采用影印、缩印或扫描
等复制手段保存、汇编学位论文.
(保密的学位论文在解密后适用本承诺书)
作者签名:
日期:
南京航空航天大学硕士学位论文
摘要
聚类分析是无监督模式分类的一个重要组成部分,也成为现代数据分析中越来越重要的一
个工具。初始条件、相似性准则和聚类准则的不同产生的聚类算法也不尽相同。因此,聚类算
法是一个内容庞杂的大家族。至今,众研究学者也提出了多种多样的聚类算法。
许多经典的聚类算法,如平均链接、K-means、K-medoids、Clara、Clarans 等,都是利用单
一的聚类中心进行聚类。为克服单一聚类中心只能描述凸状聚类的缺陷,CURE、DBSCAN 等
算法使用多个代表点(或稠密点)表述任意形状的聚类结构,但仍难以聚类重叠和噪声数据。
为此,本文提出一种新的基于多层“聚类中心”(称为“核心集”)的凝聚聚类算法(MulCA)。
该算法创新性地使用了“多层核心集”表述聚类结构,使得每一层数据集向其“核心集”凝聚,
同时上层的“核心集”自动成为下层的数据集,随着每层核心集规模按α比例迅速减少,控制
了凝聚过程的迭代次数。
由于现代社会的快速发展,大规模数据已经成为需要处理数据的主要成员,为此,本文引
入了基于随机采样计算ε-核心集(RBC)的技巧,将 MulCA 算法应用于大规模数据集。并做
了实验证明了算法对大规模数据的有效性。
在人工和实际数据集上大量的数值试验充分验证了 MulCA 算法的有效性,以及相比于其
他算法的优越性。
关键词:多层,核心集,凝聚聚类,大规模
I
基于多层核心集的凝聚聚类算法
Abstract
As an ponent of unsupervised pattern classification, clustering analysis has e
an more and more important tool in modern data analysis. Different starting conditions and similarity
criterion and clustering criterion usually generate different clustering algorithms. Therefore, clustering
algorithm is a vast and diverse algorithm family. So far, many researchers has put forward various
clustering algorithms.
Many classical clustering algorithms like average-link, K-means, K-medoids, Clarans, Clara and so
on are all based on a single cluster-center and only apt to discover convex-structured clusters. Other
methods, ., CURE and DBSCAN, use more than one point