2005
年
3
月
第
29
卷第
2
期
安徽大学学报(自然科学版)
J0umal
of
Anhui
University
Natural
Science
Edition
覆盖聚类算法
赵妹,张燕平,张铃,张妓,陈传明
(安徽大学计算智能与信号处理教育部重点实验室,安徽合肥
230039)
March
2005
Vo
l.
29
No.2
摘
要:首先比较几类主要的聚类算法,给出每类算法的基本概念、原理、每类的代表性算法,
及这些算法的主要特征。在此分析基础上,提出一种新的聚类算法一一覆盖聚类算法,该算法采
用覆盖的概念将比较集中的样本聚合在一起,从而发现隐含在样本集中的类,对于周围稀疏的样
本结合最短距离法,获得聚类效果,并用实验数据对分层聚类方法、
LBG
方法与覆盖聚类算法进行
比较,证明了覆盖聚类算法的可行性和有效性。最后给出了算法的研究方向。
关键词:聚类算法;覆盖聚类:分层聚类
中图分类号
:T
自
11
文献标识码
:A
文章编号
:10
∞
-2162(2
∞
5)02
-∞
28
-05
近几年来,聚类问题变得越来越重要,在很多领域都有广泛的应用,像模式识别
[1]
、数据挖掘
[2]
、
图像分割
[3
-4]
等,但它也是一个相当难的问题。聚类的目的就是把大量的
d
维数据样本
(n
个)聚集
成
k
类
(k<
<n)
,使同一类内样本的相似性最大,而不同类内样本的相似性最小。聚类技术要求在
样本间定义一个相似度,这在事先不知道样本的分布形状及结构的情况下,并不是一件容易的事情。
目前存在许多聚类算法,但没有一个算法能够完全处理好各种形状和结构的样本。
笔者在下面一节中比较了几类主要的聚类算法,给出了每类算法的基本概念、原理及每类的代表
性算法,及这些算法的主要特征;第二节主要提出一个新的聚类方法一一覆盖聚类算法,并对两种已
经存在聚类方法一一分层聚类算法、
LBG
方法和该算法用实验的方式进行比较,证明了覆盖聚类算
法的可行性和有效性;最后给出本文的总结及近来算法存在的重要问题和新的发展方向。
1
聚类方法简介
聚类属于非监督模式识别问题,聚类的过程完全依赖于样本之间的特征差别。目前用于数据挖
掘的聚类算法,大致分为如下几类
[5]
(1)划分聚类
(Partitional
Clustering)
。这类算法直接将样本集分解成一组没有交集的类。更确切
地说,是确定一个划分的整数以优化一特定的准则函数。这个准则函数可能是样本的局部或全局结构,
作为样本间的相似度,它的优化过程是一个迭代过程。代表算法有
K-
均值算法、
K
-modes
等。
(2)
分层聚类(
Hierarchical
Clustering)
。这类算法连续的要么将相似的类别合并成一个大类,要
么将一个大类分裂成若干个小类。算法的结果是一棵聚类树,它表明了类之间的相互关系。在合适
的尺度下通过分解该聚类树,就得到了相应样本的无交集的聚类结果。该类算法不必事先输入聚类
数,但对样本的输人次序敏感。分层聚类方法主要是将距离函数作为类间的相似度。一些新的方法
像
BIRCH
和
CURE
尝试着去解决样本集大小可变的问题并努力提高聚类质量。
(3)
基于密度的聚类
(Density
- based
Clustering)
。其主要思想是通过密度条件将样本集合中邻
收稿日期
:2
∞
4
-01
-15
基金项目:国家自然科学基金资助项目
(ω135010
、
60175018)
;安徽省教育厅自然科学研究基金资助项目
(2
∞
3kj007
)
作者简介:赵
妹
(1979-)
,女,安徽巢湖人,安徽大学博士研究生;
张燕平(1
962-)
,女,安徽巢湖人,安徽大学教授,硕士生导
JF;
张
铃(1
937-)
,男,福建福清人,安徽大学教授,博士生导师.