对聚类及聚类评价若干问题的研究.pdf

南京航空航天大学
博士学位论文
对聚类及聚类评价若干问题的研究
姓名:吕宗磊
申请学位级别:博士
专业:计算机应用技术
指导教师:王建东
20090401
摘要
聚类是数据挖掘中的一项重要任务,在很多应用中起着重要的作用。现在已经有很多成熟
的聚类方法,每种方法的适用范围不尽相同。对于同样的数据,不同聚类方法得到的结果也不
尽相同。为了在具体的应用中选择最恰当的聚类方法,人们从不同的角度提出了一些聚类评价
方法。然而不同的评价方法对于同一结果的评价并不完全一致,每种评价方法都有自己的适用
范围。超出了方法本身的适用范围将会导致方法的失效。如何保证聚类及聚类评价的有效性成
为聚类应用的一个关键问题。本文从聚类的基本概念出发对聚类及聚类评价中的相关问题进行
了系统的研究,主要包括以下几方面内容:
一、提出了聚类相似性的一般形式。根据聚类的概念,聚类是一个依据给定相似性对数据
集合进行划分的过程。相似性是聚类的关键所在。距离、密度等许多种模型都可以用来表示相
似性,但是这些模型所刻画的并不是相似性的本质。为了准确反映聚类的本质,本文首先对相
似性的形式进行讨论;而后,从相似性的直观含义出发,只保留那些直观的、明确的性质,得
出相似性的一般形式。
二、构造了聚类假设空间。假设空间是机器学习的重要理论基础。为了进一步研究聚类相
关问题,本文在聚类相似性一般形式基础上构造了聚类的假设空间。并利用聚类假设空间分析
了导致聚类及聚类评价方法失效的主要原因。
三、建立了聚类的模态逻辑表示方法。聚类相似性、数据集合、簇指派是聚类的三个重要
组成部分。本文在聚类相似性一般形式基础上将聚类对应于模态逻辑中 Kripke 语义结构,进而
通过模态逻辑公式对聚类的结果进行表示,为深入分析聚类及聚类相关问题建立了理论基础。
四、提出了具有通用性的聚类评价方法。本文采用模态逻辑公式对聚类结果中各个数据所
反映的信息进行刻画,根据数据反映的不同信息,本文提出了一种基于模态逻辑的聚类代表点
方法。在此基础上,本文进一步提出了基于代表点的聚类评价方法,这种方法不受相似性计算
方式的限制,具有较强的通用性。此外,代表点本身除了可对聚类结果进行定量的评判外,还
可以给出有关聚类结果的定性分析。
五、提出了增量聚类的风险理论及评价方法。聚类可以看作是归纳学习,而归纳有“失
真”的风险。本文提出并证明了归纳应该就近进行的原则。聚类的模态逻辑表示方法不但有助
于常规聚类的评价,还可以用于对增量聚类的评价。不同增量数据中所反映的不同逻辑公式表
明了该数据进行归纳的风险。通过降低归纳风险可以得到较好的增量聚类结果;而通过计算增
量聚类结果的归纳风险则可以对增量聚类的结果进行评价。
最后,本文通过具体的应用实例进一步验证了以上内容。其中合并小样本的应用中分别验
证了聚类假设空间的可行性及在此基础上构造的聚类评价方法;航班延误定级应用验证了基于
代表点的聚类评价方法的可行性,以及该方法所得到的定量与定性双重结果在实际工程中的应
用价值。
关键字:机器学习;聚类;假设空间;模态逻辑;代表点;增量聚类
iv
Abstract
Clustering plays an important role in many engineering applications, such as data mining and so
on. There are many mature methods to do clustering. The scope of application of different methods
may be not same with others. For the same data set, different clustering methods may get different
clusters. To choose the suitable clustering methods, some clustering validity indexes have been
presented. However, different indexes may lead different conclusions. Each method has its own
application scope. When the application exceeds the scope, the method may be invalid. It is very
important to ensure the validity of both