收稿日期

:

2007

-

07

-

12

基金项目

:

国家自然科学基金资助

(

50474033

)

作者简介

:

冯少荣

(

1964

-)

,

男

,

副教授

,

华南理工大学博士研究生

,

E

-

mail

:

s

haorong

@

xmu

.

edu

.

cn

.

一种提高

DBSCAN

聚类算法质量的新方法

冯

少

荣

1

,

2

,

肖

文

俊

1

(

1

.

华南理工大学

计算机科学与

工程学院

,

广东

广州

510640

;

2

.

厦门大学

信息科学与技术学院

,

福建

厦门

361005

)

摘要

:

针

对基于密度带有

“

噪声

”

的空间聚类应用

(

DBSCAN

)

聚类算法存

在的

3

个

主要问题

:

输入

参数

敏感

、

对内存要求高

、

数据分布不均匀时影响聚类效果

,

提出了

一种基于遗传方法的

DBSCA

N

算法

改进

方案数据分区中

使

用遗

传

思

想的

DBSCAN

算

法

(

D

PDG

A

)

来

提

高

聚类

质

量

.

利

用

遗

传

算法

改

进

K

-

means

算法来获取初始聚类中心

;

对数据

进行划

分

,

在

此基础

上对划

分的每

一部

分使用

DBSCA

N

算

法

进行聚类

;

合并聚类的结果

.

仿真实验表明

,

新方法较

好解决

了传统

DBSCA

N

聚

类算法

存在的

问题

,

在

聚类效率和聚类效果方面均优于传统

DBSCA

N

聚类算法

.

关键词

:

聚类算法

;

遗传算法

;

数据划分

;

密度

中图分类号

:

T

P301

.

6

文献标识码

:

A

文章编号

:

1001

-

2400

(

2008

)

03

-

0523

-

07

New

method

to

improve

DBS

CAN

clustering

algorithm

quality

FE

NG

Shao

-

rong

1

,

2

,

X

I

AO

Wen

-

jun

1

(

1

.

School

of

Computer

Science

and

Engineering

,

South

China

U

niversity

of

Technology

,

Guangzhou

510640

,

China

;

2

.

College

of

Information

Science

and

Techno

logy

,

Xiamen

U

niv

.

,

Xiamen

361005

,

China

)

A

bstract

:

T

here

are

three

pro

blems

along

with

the

Density

Based

Spatial

Clustering

of

Applications

with

Noise

(

DBSCA

N

)

Clustering

A

lg

o

rithm

:

input

sensitivity

,

desire

fo

r

to

o

much

memo

ry

space

and

the

effect

of

nonunifo

rm

da

ta

.

T

o

so

lve

these

problems

,

a

fa

st

Da

ta

P

ar

titio

n

DBSCA

N

using

Genetic

Algo

rithm

(

DPDG

A

)

A

lgo

rithm

is

develo

ped

w

hich

considerably

improv

es

the

cluste

r

quality

.

Fir

st

,

the

G

ene

tic

Algo

rithm

is

used

to

impr

ove

the

K

-

means

A

lg

orithm

to

g

et

the

initial

clustering

center

.

Second

,

data

is

par

titio

ned

and

the

DBSCA

N

A

lg

o

rithm

is

applied

to

cluster

pa

rtitions

.

Finally

,

all

clustered

result

sets

are

merg

ed

.

Simulatio

n

e

xperiments

indicate

tha

t

the

DPDG

A

A

lg

orithm

w

orks

w

ell

to

solv

e

these

problems

and

tha

t

both

the

efficiency

and

the

cluster

quality

are

better

than

tho

se

of

the

original

DBSCA

N

A

lgo

rithm

.

Key

Words

:

clustering

alg

orithm

;

g

enetic

;

da

ta

par

titio

n

;

density

带有

“

噪声

”

的空间聚类应用

(

DBSCAN

)

算法

[

1

,

2

]

是基于密度的聚类方法

,

它要求聚类空间中一定区域

(

半径

ε

)

内所包含对象的数目不小于某一给定的阈值

M

(

最小数目

)

.

并且将密度足够大的那部分记录组成

类

,

它的显著优点是聚类速度快并可以在带有

“

噪声

”

的空间数据库中发现任意形状的聚类

.

但这个算法使

用了

ε

和

M

两个全局变量

,

需要由用户主观来选择它们

,

从而影响了最终的聚类结果

.

另外

,

该算法需要把

所有数据载入内存

,

当数据量很庞大时对主存要求较高

.

针对

DBSCAN

算法存在的不足

,

已有一些改进方

法

[

2

～

5

]

,

但效果并不理想

.

笔者利

用了遗传

思想

,

提

出了一

种基于

遗传方

法的

DBSCAN

算

法改进

方案

(

DPDGA

)

来提高聚类质量

.

1

DPDGA

算法的基本思想

1

.

1

DPDGA

算法构造需要考虑的问题

DPDGA

算法的构造应考虑如下

3

个方面的问题

.

2008

年

6

月

第

35

卷

第

3

期

西安电子科技大学学报

(

自然科学版

)

JOUR

NAL

OF

XIDI

AN

UNIV

ER

SI

TY

Jun

.

2008

Vol

.

35

No

.