【免费】初始中心优化的K_Means聚类算法1资源-CSDN文库

需积分: 0 84 浏览量 2022-08-03 21:18:14 上传评论收藏 264KB PDF 举报

资源详情

资源评论

资源推荐

计算机科

学

20 0 2

V ol

.

9 2

塑

·

7

初

始

中

心

优

化的

K

一

M

a e

n s聚类

算法

`

’

K

一

M

a e

n

s

C l

u s

t

e r

i

n

g

A l

g

o l r

t

h m i w

t

h R

e

fi

n

e

d

I

n

i

t

i

a

l C

en

t

e r

李

飞

薛彬黄亚楼

(

南

开

大学计算机

科

学与技术

系天

津

30 0 0 7

) 1

A b

s

t

a r e

t

A

so

n

eo

f

t

h

e

m

o s

t

p

o

p

u

l

a r e

l

u s

t

e r

i

n

g

t

e e

h

n

i q

u s e

,

K

一

M

e a

n

s a

l

g

o r l

t

h m

u s u a

l l

y

o

b

t

a

i

n

s

l

o e a

l l

y

o

p

t

im

a

l

s o

l

u

-

t

i

o

n

s

d

u e

t o

i

t

s s e

n

s

i

t

i

v

i

t

y

t

o

i

n

i

t

i

a

l

s

t

a r

t

i

n

g

e e

n t

e r

.

T

o o v e r e o

m

e

t

h

i

s

p

r o

b l

e

m

,

a

g

e n e

t

i

e a

l

g

o r

i

t

h m 1

5

u

s e

d

t

o s e a r e

h

t

h

e

i

n

i

t

i

a

l

e e

n t

e r

f

o

r

K

一

M

e a n s a

l

g

o r

i

t

h m

.

A

e o

n

e e

p

t o

f

“

G

e

n

e

d if f

e r e

n

e e ”

1

5

i

n t

r

o

d

u e e

d

t o

e

o n t

r o

l

t

h

e e r o s s o v e r o

p

e r a

-

t o

r a

n

d m

u

t

a

t

i

o n o

p

e r a

t

o r

i

n

g

e

n

e

t

i

e a

l

g

o r

i

t

h m

.

E

x

p

e r

i m

e

n t

s o

n

s

t

a

n

d

a r

d d

a

t

a

b

a s e o

f U C I

s

h

o

w

t

h

a

t t

h

e

p

r o

p

o s e

d

m

e

t

h

o

d

e a

n

e

f f i

e

i

e

n t

l

y i

m

P

r

o

v e

t

h

e e

l

u s

t

e r

i

n

g

r e s u

l

t

.

K

e

y w

o r

d

s

K

一

M

e a

n

s a

l

g

o r

i

t

h m

,

G

e n e

t

i

e a

l

g

o r

i

t

h m

,

G

e n e

d

i

f f

e r e

n

e e

引言

聚类

分析

(c l

us

t

er

in

g

)

是人

工

智

能研

究的

重要

领域

。

聚

类

方

法

被广

泛

研究并

应用于

机

器学习

、

统计

分

析

、

模

式识别以及

数据库数据

挖

掘与

知识

发

现

等

不

同

的

领域

。

各种

聚类方法

中

,

基于目

标

函数的

K

一

M ea

n

s

聚

类

方法应

用极

为广

泛

,

根据

聚

类结果

的表

达方式

又可分

为

硬

K

一

M ae ns

( H C

M

)

算

法

、

模糊

K

一

M

e a

n

s

算

法

(

F

C

M

)

和

概率

K

一

M

e a

n

s

算

法

(

P

C

M 户

〕

。

各种

K

一

M ae

n

s

算法都

以

确定

的目

标

函

数来

测

度

聚类的效果

,

最

佳

的聚

类效

果

对应

于目

标

函

数

的

极值

点

。

由于

目

标

函

数

局部

极小值

点的

存

在

川

以及

算

法的贪心

性

,

导致聚

类结果对初始中心敏

感

,

往往达不到全局最优

。

针对

K

一

M

e

an

s

算法

对初始聚

类中

心的敏

感

问

题

,

可以选

取

不同的初始

值

多次

执行该算法

,

然后选取

最好

的

结

果

。

显

然

,

如果初始

中

心选

取

次数

较

少不能

保

证得到最

优解

,

选

取

次

数较多

则会

大

大增加

计算

量

.

因此

,

许

多

峨

究

者针对

这个问

题

提

出了

改

进的

算法

。

P

.

5

.

Br

ad

l

ey

等

人提出一

种

从聚

类数据

集

随机

选取

多个子

样本集

的

方

法

川

,

对

所

选取的子

样本集

重

复执行

K

一

M ea

n

s

算

法得到优化的初始聚

类中

心

,

然后再

对

整

个

聚

类数据集采

用

K

一

M ae ns 方法聚

类

。

但是

,

这

种算

法得到

的

只

是

一

种

“

次优

”

的

聚

类结果

,

而且

受子样本集选取方式

的

影

响

。

其他

研

究者把随机算法

的思

想引

入到初始聚

类中

心

的

选取中

,

如

C L A R A N S

算法

[’]

.

随

机搜索多

个初

始

聚

类中

心

对

应

的

局

部极小值

,

比

较得

到

全

局

最优解

;

最近

,

有

学

者将

全

局

优化方

法

中

的

模

拟退火

技术

应用于聚

类

分

析

,

提出一

种

基

于

模

拟

退

火

算

法的动态聚

类算

法

比

目

。

遗传算

法是一种高效

率

的随机全局

优化搜索算

法

,

广

泛

应

用于

各种优化

问

题

的

求解

,

包括

应

用于聚

类分析

v.[

`

〕

.

本文

应

用

遗传算

法的全局高效搜

索能

力

来解

决

K

一

M ae

n

s

聚

类算

法对

初

始中

心的敏

感性

问题

。

同

时

,

针

对

标

准的遗

传算

法

本身

的早

熟

收敛

、

误差平

分等

缺

陷

0[J

,

根据

所要

解

决问

题

的先

验

知

识

,

引进

基因差异

度

对

标

准遗

传算

法的交叉

、

变

异

算

子

进行修

正

,

限

制适

应

度差的

个

体

的

生成

,

以期

提高算法

的寻

优能力

.

“

无

监

督学习

”

算法

。

指

定类别数为

C

,

对样本集合进行

聚

类

,

聚类的结果由

C

个聚

类中

心

来表达

。

基于

给定

的聚类目

标

函

数

(

或

者

说是

聚类效果判

别准

则

)

,

算法采

用

迭代更新

的

方法

,

每

一次迭

代

过程都是

向

目

标

函

数值减少

的

方

向

进行

,

最终的

聚类结果

使

目

标

函

数值取

得

极小值

,

达

到

较优

的聚

类效

果

。

设聚

类

的样

本集

为

:

X ~

{

x

,

}

x

,

任

R

户

,

i

一

1

,

2

,

…

,

N }

,

得

到的

c

个

聚

类中

心

为

二 ,

,

2 2

,

…

,

各

。

令 wj

(j

~ 1

,

2

,

二

`

,

c )

表

示

聚

类

的

C

个类别

,

则

:

z

,

一

吝

E

二

` v J 二

`

灼

( 1 )

定

义目

标

函

数

:

J 一

习习

试

,

(

二

, ,

二

,

)

( 2 )

2

.

优化算

祛

原理

传统的

K

一

M ae

n

s

聚

类算

法

,

是

一

种

己知聚

类类别数

的

其中

n `

表

示

街类包

含

的样本

个

数

,

一

般采

用

欧

氏

距离 dt,

(

x

, ,

二

`

) 一

了

(x

,

一

二

,

)

了

(

x

,

一

二

`

)

作

为

样本

间的距

离

。

欧氏

距离

适

合

于

类内样本

数

据

为

超球

形

分布

的

情

况

。

目

标

函

数

J 为

每

个样

本数据

点到

相应

聚

类中

心的距

离平方

和

,

即聚

类

的最

小

均方

误

差

。

传统的

K

一

M ea

n

s

聚

类算法

( H C

M

算法

)

流

程如下

:

(

1

)

随机指

定

C

个样

本点

z ,

(

1

)

,

z :

(

1 )

,

…

,

z

。

(

1

)

为

初

始

聚

类中

心

;

(

2)

按

照距

离

最

近的

原则

,

对样本集合

聚

类

,

确定每

个

样

本

的

类

属关系

;

(

3

)

使

用公

式

( 1 )

,

计算新

的聚

类中

心

z ,

(

k

)

,

z :

(

k

)

.

…

,

z

。

快

) (

k

表

示迭

代

次

数

)

;

(4

)

重复执行

(2

)

一

(4

)

,

直

到聚

类中

心稳定为止

。

显然

,

算法受初始值

的影响

很大

,

聚

类

的

结果

往往只是局

部

最

优

。

即

使对

不

同

的初

始值多次执行该算法

,

也

只

是在

庞

大

的初

值

空间

里简单地进行

搜

索

,

其

结

果也很难达

到

全

局最优

。

解决算

法

对

于初始

值

的

敏感性

问

题

,

相

当于一个

全

局

优

化

搜

索

问

题

。

基于

遗传算法的高效全

局

优化搜索能力

以及

内

在的随

机

性和

隐

含的

并行性

,

本文提

出

使

用

遗传算

法

来优化

K

一

M ea

n

s

聚

类算

法的初

始

聚

类中

心

.

算法流程改变

了

传统

K

-

M ea

n

s

算

法随

机选取中

心的

方法

,

即修改

了上

述

K

一

M ea

n

s

算

法流

程的

第

( 1)

步

,

采

用

遗传算法来选

择

初

始的聚

类中

心

。

朴

)

本文

得到天

律

市自然

科

学基金项目资助

(

。。

3 6

。。

3 1 1 )

.

李飞博

士

研

究

生

,

研究方向为智能信息

处

理

、

数据挖掘

和

数据

仓

库技术

。

黄亚楼

教

授

,

博士

生导

师

,

主要

研

究

方

向为智能

机

器人

,

智

能

信息处理

,

数据挖

掘

。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

内容反馈

白羊的羊

粉丝: 35
资源: 281

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip