第 23 卷 第 4 期
2003 年 12 月
南 京 邮 电 学 院 学 报
Journal of Nanjing University of Posts and Telecommunications
Vol. 23 No. 4
Dec. 2003
文章编号: 1000- 1972( 2003) 04- 0006- 06
收稿日期: 2003-04-23
基金项目: 国家重点基础研究发展规划 973( G 1999032701) 和国
家自然科学基金( 60273037) 资助项目
数据挖掘中基于密度的聚类结构及算法设计
洪 龙
1, 2
, 陈燕俐
1
, 王建东
2
, 朱梧木贾
2
1 南京邮电学院 计算机科学与技术系, 江苏 南京 210003
2 南京航空航天大学 信息科学与技术学院, 江苏 南京 210016
摘 要: 聚类分析是数据挖掘的主要技术之一。其中基于密度的聚类可以得到任意 形状的聚类结果, 从
而可以观察到一 个并发的、完整的聚类结构。对聚类、数据对象、簇的 密度、基 于密度的方 法和 OP-
TICS 中的基本概念进行了描 述, 在 此基 础上, 明确 定义 了簇的 密度, 建 立了 关于 ζ的 基于 密度 的
簇、密度度量函数等概念, 并设计了获得聚类结构的相应算法且对其进行了复杂性分析。
关键词: 数据挖掘; 聚类; 距离; 簇的密度 ; 基于密度的簇; 聚类结构
中图分类号: TP31113 文献标识码: A
1 引 言
数据挖掘能自动地发现隐藏在数据库、数据仓
库或海量信息存储中的知识模式, 因此数据挖掘又
称作数据库中的知识发现。聚类分析是数据挖掘的
主要方法之一, 由于其简单、有效, 它已成为数据挖
掘研究领域中一个非常活跃的研究方向。
在聚类中, 两个 m 维的数据对象 i = ( x
i 1
, x
i 2
,
, xim ) 与 j = ( xj 1, xj2, , xjm ) 的闵氏距离( Minkows-
ki distance)
d ( i, j ) =
m
k= 1
| x
ik
- x
jk
|
q
1/ q
其中 d( i, j ) 一般要求满足条件:
( 1) d( i, j ) = 0
i= j ;
( 2) i j ( d ( i , j ) 0) ;
( 3) i j ( d ( i , j ) = d( j , i ) ) ;
( 4) i j k( d( i , j ) d ( i , k) + d( k , j ) )
当 q = 2 时, d ( i, j ) 称作欧氏距离( Euclidean dis-
tance) 。
聚类分析本是多元统计分析中的一种方法, 在
机器学习领域, 聚类被认为是无指导学习。实现聚
类有多种方法, 绝大多数方法是以数据对象之间的
距离划分簇, 这样只能发现球状簇。
基于密度的方法是把具有足够高密度的区域划
为簇, 因而可以得到任意形状的聚类结果。
OPT ICS( Ordering Pointers To Identify the Clustering
Structure) 是基于密度进行聚类的一种方法, 它通过
对给定的数据对象集合中的元素进行排序来识别聚
类结构, 次序是根据密度的高低来确定的, 因此 OP-
TICS 可同时得到多个聚类结果。文献[ 1] 对 OPTICS
的思想方法进行了简单的介绍, 并说 已经提出了一
个算法。
本文对簇、聚类、基于密度的方法和 OPT ICS 中
的基本概念进行了描述, 在此基础上, 明确定义了簇
的密度, 建立了关于 ζ的基于密度的簇、密度度量函
数等概念, 并设计了获得聚类结构的相应算法且对
其进行了复杂性分析。
2 基于密度聚类的基本概念
2. 1 聚 类
定义 1 数据对象的聚合称作簇( cluster) 。
其中聚合是指由两个或更多个数据对象所构成
的有目的的集合。聚合形象地说明了簇的特征, 即
同一簇中的数据对象相似, 不同簇中的数据对象相
异。
定义 2 把一个数据对象集合分成多个簇称作
类分析( cluster analysis) 。
把这些簇分别记作 C
1
, C
2
, , C
n
, 则应有