近鄰?fù)骄垲惸Ｐ团c指數(shù)衰減加權(quán)同步聚類模型的比較與分析

陳新泉,周靈晶，戴家樹，周 祺

(1.安徽工程大學(xué) 計算機與信息學(xué)院，安徽 蕪湖 241000；2.安徽工程大學(xué) 教育工會，安徽 蕪湖 241000)

作為統(tǒng)計學(xué)中多元統(tǒng)計分析方法的一種重要技術(shù)，聚類分析試圖發(fā)現(xiàn)未知數(shù)據(jù)中的內(nèi)在結(jié)構(gòu)或分布規(guī)律。在機器學(xué)習(xí)中，聚類被稱為無監(jiān)督學(xué)習(xí)，指的是試圖發(fā)現(xiàn)無標(biāo)記數(shù)據(jù)中的內(nèi)在分布結(jié)構(gòu)，讓劃分后的簇表現(xiàn)出數(shù)據(jù)的自然結(jié)構(gòu)特點。聚類可以讓缺乏先驗信息的數(shù)據(jù)集獲得其內(nèi)在的分布結(jié)構(gòu)(聚類的數(shù)目、大小、分布位置及空間結(jié)構(gòu)等信息)，進而為半監(jiān)督學(xué)習(xí)、監(jiān)督學(xué)習(xí)、數(shù)據(jù)壓縮等一些后續(xù)操作提供一定的輔助信息。通常，同一聚類中的數(shù)據(jù)應(yīng)該比不同聚類間的數(shù)據(jù)更為相似，不同聚類間的數(shù)據(jù)應(yīng)該具有較大的差異。聚類在許多領(lǐng)域都有應(yīng)用，如：心理學(xué)和其他社會科學(xué)、生物學(xué)、統(tǒng)計學(xué)、模式識別、信息檢索、機器學(xué)習(xí)和數(shù)據(jù)挖掘。

聚類分析屬于一個交叉研究領(lǐng)域，它融合了多個學(xué)科的方法和技術(shù)。Qlan Wei-ning等從多個角度分析了現(xiàn)有的許多聚類算法，給出了一些優(yōu)缺點比較分析結(jié)果。Johannes Grabmeier等從數(shù)據(jù)挖掘的角度(如相似度的定義、相關(guān)的優(yōu)化標(biāo)準(zhǔn)等)分析了許多聚類算法。Arabie和Hubert的專著是早期聚類分析領(lǐng)域的一本很有價值的參考文獻。Jain等對一些經(jīng)典聚類算法進行了很好地比較與分析，這是聚類分析領(lǐng)域早期一篇經(jīng)典的綜述文獻。2000年后，Rui Xu等和Anil K.Jain對聚類算法分別做了較為全新的綜述分析。

傳統(tǒng)的聚類算法一般可分為基于劃分的聚類方法、層次聚類方法、密度聚類方法、網(wǎng)格聚類方法、模型聚類方法、圖聚類方法等。近年來，量子聚類方法、譜聚類方法、粒度聚類方法、概率圖聚類方法、同步聚類方法等也流行起來。

B?hm等于2010年第一次將自然界中普通存在的同步現(xiàn)象引入聚類分析領(lǐng)域，在國際頂級會議KDD(Knowledge Discovery and Data Mining)上發(fā)表了第一篇同步聚類算法論文。這篇開拓性論文首先將Kuramoto模型進行了適當(dāng)?shù)赝茝V，得到可應(yīng)用于聚類算法中的擴展Kuramoto模型，提出了(Synchronization clustering，Sync)聚類算法。接著作者還將最小描述長度原理應(yīng)用于Sync算法中，提出了一種參數(shù)的自動優(yōu)化方法?；谕侥Ｐ偷木垲愃惴梢跃徑饩垲惙治龊驮肼暀z測在傳統(tǒng)數(shù)據(jù)上的某些難題，它具有動態(tài)性、局部性及多尺度分析等特性，可以在一定程度上解決大規(guī)模數(shù)據(jù)的聚類分析所面臨的困難。自此之后，新型的基于同步模型的聚類算法形成了一個研究熱潮。

自Sync算法發(fā)表后，吸引了一些研究人員的注意。近幾年，邵俊明等從多個角度研究基于同步模型的數(shù)據(jù)挖掘方法，發(fā)表了多篇高水平論文。例如，文獻[10]提出了一種新穎的孤立點檢測算法。文獻[11]提出了一種新穎有效的高效子空間聚類算法(arbitrarily ORiented Synchronized Clusters，ORSC)。文獻[12]提出了一種基于同步模型和最小描述長度原理的新穎的動態(tài)層次聚類算法(hierarchical Synchronization clustering，hSync)，文獻[13]提出了一種可以發(fā)現(xiàn)復(fù)雜圖的內(nèi)在模式的新穎的圖聚類算法(Robust Synchronization-based Graph Clustering，RSGC)。文獻[14]提出了一種用于檢測概念漂移的基于原型學(xué)習(xí)的數(shù)據(jù)流挖掘算法。黃健斌等在文獻[8]的基礎(chǔ)上，提出了一種層次型的同步聚類算法(Synchronization-based Hierarchical Clustering，SHC)。2017年，陳新泉找到了另外一種更為有效的同步聚類模型—Vicsek模型的線性版本。在將這種Vicsek模型的線性版本應(yīng)用到聚類中后，發(fā)表了基于該模型的ESynC(Effective Synchronization Clustering)算法。杭文龍等基于重力學(xué)中的中心力優(yōu)化方法，提出了一種局部同步聚類算法(Gravitational Synchronization clustering，G-Sync)。陳新泉在文獻[8]的基礎(chǔ)上，提出了基于三種空間索引結(jié)構(gòu)的快速同步聚類算法(Fast Synchronization Clustering，F(xiàn)SynC)。FSynC算法中的兩種參數(shù)型方法在某些情況下可得到O(dnlogn)的時間代價。這幾篇較新的同步聚類論文分別從不同的角度拓展了同步聚類算法的研究。

1 基本概念

設(shè)數(shù)據(jù)集

S

={

x

,

x

,…,

x

()}分布在

d

維有序?qū)傩钥臻g(

A

×

A

×…×

A

)的某個有限區(qū)域內(nèi)。為更好地描述研究算法，先給出幾個基本定義。

定義

1

數(shù)據(jù)集

S

中的點

x

()(

i

=1,…,

n

)的

δ

近鄰點集

δ

(

x

())定義為：

δ

(

x

())={

x

|0<

dis

(

x

,

x

())≤

δ

,

x

∈

S

,

x

≠

x

()}。

(1)

式中，

dis

(

x

,

x

())為

S

中的兩個不同點

x

和

x

()的相異性度量，

δ

是一個預(yù)先設(shè)定的閾值參數(shù)。定義1的實質(zhì)意義是：

δ

(

x

())是從中選取與點

x

()相距不超過

δ

“距離”的其他點所構(gòu)成的集合。

定義

2應(yīng)用到聚類中的擴展的Kuramoto模型定義為：

(2)

定義

316應(yīng)用到聚類中的

Vicsek

簡化模型定義為：

(3)

式中，

x

()(

t

+1)表示點

x

()在第

t

個同步后的更新位置；

v

(

t

)表示第

t

個同步時的移動速度；

v

(

t

)·

Δt

表示第

t

個同步的移動路徑長度。在一些基于Vicsek模型的多agent系統(tǒng)中，

v

(

t

)是個常量。通過一些仿真實驗的觀察，當(dāng)

v

(

t

)是常量時，基于式(3)的Vicsek模型的原始版本不能很好地應(yīng)用到聚類中，所以將Vicsek模型的另外一種有效版本應(yīng)用到聚類中。

(4)

式中，

x

()(

t

+1)表示點

x

()在第

t

個同步后的更新位置。式(4)與Mean Shift聚類算法中的下一個搜索位置的計算公式相似。從中我們可以看出，點

x

()的更新位置就是點

x

()及它的

δ

近鄰點集

δ

(

x

())的均值位置。式(4)還可以被改寫為：

(5)

式(5)與式(2)在外形方面有點相似，但它們有著本質(zhì)的區(qū)別。我們可以看到，式(2)所表示的更新模型是非線性的，而式(4)與式(5)的更新模型是線性的。

基于萬有引力定律和物理學(xué)中普遍存在的指數(shù)衰減規(guī)律，我們提出下面的三種指數(shù)衰減加權(quán)同步模型。前兩種模型是在全局范圍內(nèi)進行迭代計算，后一種是在

δ

近鄰范圍內(nèi)進行迭代計算。

定義

5

應(yīng)用到聚類中的第一種指數(shù)衰減加權(quán)同步模型定義為：

(6)

定義

6

應(yīng)用到聚類中的第二種指數(shù)衰減加權(quán)同步模型定義為：

(7)

定義

7

應(yīng)用到聚類中的

δ

近鄰指數(shù)衰減加權(quán)同步模型定義為：

(8)

定義

8 數(shù)據(jù)集

S

={

x

,

x

,…,

x

()}在經(jīng)歷了

T

步的同步聚類后穩(wěn)定下來，表示為

S

(

T

)={

x

(

T

),…,

x

()(

T

)}。設(shè)從

S

(

T

)可獲得

K

個聚類和

K

個孤立點，

K

=

K

+

K

。

S

(

T

)的聚類穩(wěn)定點集記為

C

={

c

,…,

c

()}，其中

c

()是第

j

個聚類區(qū)域的穩(wěn)定標(biāo)記位置。如果

x

()(

T

)滿足式(9)，則點

x

()判為屬于第

j

個聚類區(qū)域。

dis

(

c

(),

x

()(

T

))<

ε

。

(9)

式(9)中的參數(shù)

ε

與算法中的迭代退出閾值參數(shù)

ε

相同，是一個非常小的實數(shù)。如果第

j

個聚類區(qū)域包含了

n

個數(shù)據(jù)點，則這

n

個數(shù)據(jù)點在原始數(shù)據(jù)集

S

={

x

,…,

x

()}中的均值位置

m

()與第

j

個聚類穩(wěn)定點位置

c

()之間的距離表示為

dis

(

c

(),

m

())，則

K

個聚類區(qū)域的穩(wěn)定位置與

K

個聚類區(qū)域的均值位置差異值定義為：

(10)

顯然，式(10)所表示的這個指標(biāo)可度量同步聚類后聚類區(qū)域的穩(wěn)定位置與均值位置的平均差異。

定義

9

互信息(Mutual Information,MI)。根據(jù)香農(nóng)信息論，兩個離散隨機變量

X

和

Y

的互信息定義為：

(11)

式中，

p

(

x

,

y

)是兩個隨機變量

X

和

Y

的聯(lián)合概率密度分布函數(shù)，

p

(

x

)是隨機變量

X

的邊緣概率密度分布函數(shù)，

p

(

y

)亦然。

定義

10 正規(guī)化互信息(Normalized Mutual Information,NMI)。兩個聚類結(jié)果

X

和

Y

的正規(guī)化互信息定義為：

(12)

式中，

MI

(

X

,

Y

)是兩個聚類結(jié)果

X

和

Y

的互信息，

H

(

X

)是聚類結(jié)果

X

的信息熵，

H

(

Y

)亦然。

定義

11

調(diào)整互信息(Adjusted Mutual Information,AMI)。兩個聚類結(jié)果

X

和

Y

的調(diào)整互信息定義為：

(13)

式中，

MI

(

X

,

Y

)，

H

(

X

)，

H

(

Y

)的含義與上面相同，

E

{

MI

(

X

,

Y

)}是兩個聚類結(jié)果

X

和

Y

的互信息的數(shù)學(xué)期望。

定義

12

調(diào)整變信息(Adjusted Variation Information,AVI)。兩個聚類結(jié)果

X

和

Y

的調(diào)整變信息定義為：

(14)

式中，

MI

(

X

,

Y

)，

H

(

X

)，

H

(

Y

)，

E

{

MI

(

X

,

Y

)}的含義與上面相同。當(dāng)聚類結(jié)果

X

和

Y

完全一致時，

NMI

，

AMI

和

AVI

取值為1。當(dāng)聚類結(jié)果

X

和

Y

的互信息等于它們的期望時，

AMI

和

AVI

取值為0；當(dāng)聚類結(jié)果

X

和

Y

的分布相互獨立時，

NMI

取值為0。

2 基于同步模型的聚類算法

B?hm等提出的Sync算法，Chen提出的ESynC算法是2.1節(jié)中基于近鄰?fù)侥Ｐ偷木垲愃惴ǖ膬蓚€典型代表，基于指數(shù)衰減加權(quán)同步模型的聚類算法將在2.2節(jié)中予以介紹。

2.1 基于近鄰?fù)侥Ｐ偷木垲愃惴?/h3>基于近鄰?fù)侥Ｐ偷木垲愃惴ㄊ且环N在

δ

近鄰范圍內(nèi)進行動態(tài)同步迭代的聚類算法框架，具體表述如下：

算法1:基于近鄰?fù)侥Ｐ偷木垲愃惴?/p>輸入：數(shù)據(jù)點集

S

={

x

,…,

x

()}，距離相異性度量

dis

(·,·)，近鄰閾值參數(shù)

δ

，迭代退出閾值參數(shù)

ε

；輸出：數(shù)據(jù)點集

S

的聚類結(jié)果，可以采用數(shù)據(jù)點的聚類歸屬標(biāo)記數(shù)組

FinCluResult

[1…

n

]；1:迭代步

t

初始化為0，即：

t

←0；2:for

i

=1,2,…,

n

do;3:

x

()(

t

)←

x

()

4:end for

5:while(

S

(

t

)={

x

(

t

),

x

(

t

),…,

x

()(

t

)}仍在同步移動中)do6: for

i

=1,2,…,

n

do7: 根據(jù)式(1)為數(shù)據(jù)點

x

()構(gòu)造它的

δ

近鄰點集

δ

(

x

())；8: 根據(jù)定義2，或定義3，或定義4，或定義7計算

x

()(

t

)同步后的更新值

x

()(

t

+1)；

9: end for

11: if(

mse

(

S

(

t

),

S

(

t

+1))<

ε

)then

12: 這個動態(tài)的同步聚類過程收斂了，可以從while循環(huán)中退出來；

13: else

14: 迭代步

t

增加一步，即：

t

++，然后進入下一次while循環(huán)；

15: end if

16:end while

17:將退出while循環(huán)的

t

值賦給同步總次數(shù)

T

，此時可得到數(shù)據(jù)點集

S

同步后的收斂結(jié)果集

S

(

T

)={

x

(

T

),

x

(

T

),…,

x

()(

T

)}；18:在

S

(

T

)中，那些代表一些數(shù)據(jù)點的穩(wěn)定位置可看作是聚類中心，那些只代表一個或幾個點的穩(wěn)定位置可看作是孤立點的最終同步位置。根據(jù)

S

(

T

)={

x

(

T

),

x

(

T

),…,

x

()(

T

)}很容易得到一個由若干個穩(wěn)定點或孤立點構(gòu)成的自然聚類簇，從而構(gòu)造出

FinCluResult

[1..

n

]。備注：在算法1的第8步中，如果采用定義2來計算

x

()(

t

)同步后的更新值

x

()(

t

+1)，就是B?hm等提出的Sync算法；如果采用定義4來計算

x

()(

t

)同步后的更新值

x

()(

t

+1)，就是Chen提出的ESynC算法；定義3的同步模型在文獻[16]中已有幾個對照實驗；如果采用定義7來計算

x

()(

t

)同步后的更新值

x

()(

t

+1)，則會得到一種同步聚類算法。

2.2 基于指數(shù)衰減加權(quán)同步模型的聚類算法

基于指數(shù)衰減加權(quán)同步模型是一種在全局范圍內(nèi)進行動態(tài)同步迭代的聚類算法框架，具體表述如下：

算法2:基于指數(shù)衰減加權(quán)同步模型的聚類算法

輸入：數(shù)據(jù)點集

S

={

x

,…,

x

()}，距離相異性度量

dis

(·,·)，迭代退出閾值參數(shù)

ε

；輸出：數(shù)據(jù)點集

S

的聚類結(jié)果，可以采用數(shù)據(jù)點的聚類歸屬標(biāo)記數(shù)組

FinCluResult

[1..

n

]；1:迭代步

t

初始化為0，即：

t

←0；2:for

i

=1,2,…,

n

do3:

x

()(

t

)←

x

();

4:end for

5:while(

S

(

t

)={

x

(

t

),

x

(

t

),…,

x

()(

t

)}仍在同步移動中)do6: for

i

=1,2,…,

n

do7: 根據(jù)定義5，或定義6計算

x

()(

t

)同步后的更新值

x

()(

t

+1)；

8: end for

10: if(

mse

(

S

(

t

),

S

(

t

+1))<

ε

)then

11: 這個動態(tài)的同步聚類過程收斂了，可以從while循環(huán)中退出來；

12:

else

13: 迭代步

t

增加一步，即：

t

++，然后進入下一次while循環(huán)；

14: end if

15:end while

16:將退出while循環(huán)的

t

值賦給同步總次數(shù)

T

，此時可得到數(shù)據(jù)點集

S

同步后的收斂結(jié)果集

S

(

T

)={

x

(

T

),

x

(

T

),…,

x

()(

T

)}；17:在

S

(

T

)中，那些代表一些數(shù)據(jù)點的穩(wěn)定位置可看作是聚類中心，那些只代表一個或幾個點的穩(wěn)定位置可看作是孤立點的最終同步位置。根據(jù)

S

(

T

)={

x

(

T

),

x

(

T

),…,

x

()(

T

)}很容易得到一個由若干個穩(wěn)定點或孤立點構(gòu)成的自然聚類簇，從而構(gòu)造出

FinCluResult

[1..

n

]。備注：在算法2的第7步中，如果采用定義5來計算

x

()(

t

)同步后的更新值

x

()(

t

+1)，會得到一種同步聚類算法；如果采用定義6來計算

x

()(

t

)同步后的更新值

x

()(

t

+1)，則會得到另外一種同步聚類算法。

2.3 算法的復(fù)雜度分析

(1)算法1的復(fù)雜度分析。在算法1中，步1只需要

O

(1)的時間代價，步2到步4需要

O

(

n

)的時間代價。步5需要

O

(

T

)的時間代價。在步7中，如果采用簡單的全范圍蠻力判斷方法，為數(shù)據(jù)點

x

()(

i

=1,…,

n

)構(gòu)造它的

δ

近鄰點集

δ

(

x

())需要

Time

=

O

(

dn

)。當(dāng)數(shù)據(jù)集的維數(shù)較小時，通過為數(shù)據(jù)點集構(gòu)造空間索引結(jié)構(gòu)的方法，可以取得

O

(

d

log

n

)的時間代價。在步8中，計算

x

()(

t

)(

i

=1,…,

n

)同步后的更新值

x

()(

t

+1)需要

Time

=

O

(

d

·|

δ

(

x

())|)。所以步6到步10最多需要

O

(

dn

)的時間代價。步10需要

O

(

dn

)的時間代價。步11到步15只需要

O

(1)的時間代價。步17只需要

O

(1)的時間代價。步18需要

O

(

dnK

)的時間代價，其中

K

是聚類數(shù)和孤立點數(shù)之和，一般有

K

?

n

。根據(jù)B?hm等和我們的分析，算法1未采用空間索引結(jié)構(gòu)時的時間代價為

Time

=

O

(

Tdn

)；算法1在低維數(shù)據(jù)集中，采用有效的空間索引結(jié)構(gòu)時的時間代價為

Time

=

O

(

Tdn

log

n

)。(2)算法2的復(fù)雜度分析。算法2中的步1，步2到步4，步5的時間代價與算法1相同。在步6到步8中，使用定義5來計算

w

()(

t

)(

i

,

j

=1,…,

n

)需要

Time

=

O

(

d

)，計算

x

()(

t

)(

i

=1,…,

n

)同步后的更新值

x

()(

t

+1)需要

Time

=

O

(

dn

)；使用定義6來計算

w

()(

t

)(

i

,

j

=1,…,

n

;

k

=1,…,

d

)需要

Time

=

O

(1)，計算

x

()(

t

)(

i

=1,…,

n

;

k

=1,…,

d

)同步后的更新值

x

()(

t

+1)需要

Time

=

O

(

n

)。所以步6到步8需要

O

(

dn

)的時間代價。步9需要

O

(

dn

)的時間代價。步10到步14只需要

O

(1)的時間代價。步16只需要

O

(1)的時間代價。步17需要

O

(

dnK

)的時間代價，其中

K

是聚類數(shù)和孤立點數(shù)之和，一般有

K

?

n

。根據(jù)上面的分析，算法2的時間代價為

Time

=

O

(

Tdn

)。

2.4 參數(shù)的優(yōu)化確定

算法1和算法2中的迭代退出閾值參數(shù)

ε

僅影響著同步迭代的次數(shù)及聚類精度，一般可設(shè)置在[0.01,0.000 001]范圍內(nèi)。在所有實驗中，均設(shè)置為

ε

=0.000 01。算法1的近鄰閾值參數(shù)

δ

可以影響數(shù)據(jù)集的聚類結(jié)果。參數(shù)

δ

的優(yōu)化設(shè)置原則是：如果兩個數(shù)據(jù)點的相異性度量小于

δ

，那么可以認(rèn)為這兩個點應(yīng)該在同一個聚類中。在文獻[8]中，參數(shù)

δ

可以通過MDL原理來優(yōu)化確定。根據(jù)文獻[16]中的定理1和性質(zhì)1，很容易選擇確定參數(shù)

δ

的一個合適值。驗中的參數(shù)

δ

就是根據(jù)這個方法確定的。通過大量的仿真實驗發(fā)現(xiàn)，在多數(shù)具有明顯聚類結(jié)構(gòu)的數(shù)據(jù)集中，參數(shù)

δ

都具有一個比較寬泛的有效值范圍。在文獻[23]中，給出了如下兩種估計參數(shù)

δ

有效值的方法。(1)第一種估計參數(shù)

δ

有效值的方法由式(15)表示：

MstEdgeInCluster

≤

δ

<

DisDifferentClusters

。

(15)

式(15)中，

MstEdgeInCluster

是聚類簇的所有最小生成樹(每個聚類有一個將該聚類所有點連接在一起的最小生成樹)中的最大邊;

DisDifferentClusters

是不同聚類中的兩個點的最小相異性度量。(2)第二種估計參數(shù)

δ

有效值的方法是一個基于數(shù)據(jù)集

S

(或它的一個樣本)的最小生成樹而設(shè)計的一個算法。具體步驟如下：①首先從數(shù)據(jù)集

S

中構(gòu)造出一個最小生成樹

MST

。②接著對該

MST

的所有邊進行升序排列。設(shè)排序后的邊集表示為

ES

(

MST

(

S

))={

e

,

e

,…,

e

-1},這里

e

≤

e

≤…≤

e

-1。③在

ES

(

MST

(

S

))中，搜索具有最大差值的兩個相鄰邊。這樣，估計參數(shù)

δ

有效值的另外一個公式可表示為：

(16)

式(16)中，

e

和

e

+1是

ES

(

MST

(

S

))中具有最大差值的兩個相鄰邊。

3 仿真實驗

3.1 仿真實驗設(shè)計

表1 仿真實驗數(shù)據(jù)集的描述(a 4類2維實值型人工數(shù)據(jù)集的描述)

表1 仿真實驗數(shù)據(jù)集的描述(b 8個UCI數(shù)據(jù)集的描述[24])

相關(guān)實驗均在Intel(R)Celeron(R)CPU 3855U 1.6 GHz上進行，配備8 G內(nèi)存，在Windows 7的Visual C++6.0開發(fā)環(huán)境下采用C語言和C++語言混合編程進行仿真實驗驗證。

為比較這些同步聚類模型的聚類結(jié)果和時間效率的差異，采用表1中描述的4類人工數(shù)據(jù)集和8個UCI數(shù)據(jù)集做一些仿真實驗。表1a給出了4類人工數(shù)據(jù)集的基本描述信息，它們是由兩個函數(shù)根據(jù)設(shè)定的參數(shù)在區(qū)域[0,600]×[0,600]內(nèi)生成的2維數(shù)據(jù)。這兩個函數(shù)的C語言代碼在文獻[16]的附加材料附錄2中給出。表1b是8個UCI數(shù)據(jù)集的簡單描述。

這里采用多個不同類型的數(shù)據(jù)集對基于六種同步模型的聚類算法(分別基于定義2、定義3、定義4、定義5、定義6和定義7構(gòu)造的同步聚類算法)在時間代價(單位為s)、同步迭代次數(shù)、聚類區(qū)域的穩(wěn)定位置與均值位置的差異值和聚類質(zhì)量(采用3個基于信息論的度量指標(biāo)AMI/AVI/NMI)上進行適當(dāng)?shù)谋容^，觀察分析這六種同步聚類模型的聚類有效性差異。同步聚類算法中的迭代退出閾值參數(shù)ε均設(shè)置為0.000 01。在算法1中，基于定義2、定義3、定義4和定義7的同步聚類模型,根據(jù)文獻[16]的方法為近鄰閾值參數(shù)δ選擇一個合適值。

3.2 六種同步模型的動態(tài)聚類過程示例與比較

圖1采用的數(shù)據(jù)集選自表1a中的DS1類，數(shù)據(jù)點數(shù)目為400，具有5個比較明顯的聚類區(qū)域。在幾個同步聚類模型的算法中，參數(shù)

δ

設(shè)置為30，參數(shù)

ε

設(shè)置為0.000 01，最大迭代次數(shù)設(shè)置為50，定義3中的

v

(

t

)·

Δt

設(shè)置為0.1。圖1a～圖1e給出了六種同步聚類模型在這個數(shù)據(jù)集上的同步聚類過程演變軌跡，用NC(Number of Clusters)記錄著聚類數(shù)目，

t

記錄著迭代的輪次。

通過比較定義2、定義3、定義4、定義5、定義6和定義7可以看出，除了定義2是非線性的同步聚類模型，其他幾個定義都是線性的同步聚類模型。從圖1中可知，除了基于定義4的同步聚類模型外，其他幾個同步聚類模型都不能獲得良好的局部聚類效果。

3.3 人工數(shù)據(jù)集的仿真實驗結(jié)果

表2是基于六種同步模型的聚類算法在4個人工數(shù)據(jù)集(表1a中的4類人工數(shù)據(jù)集，數(shù)據(jù)點數(shù)目設(shè)置為1 000。第1個數(shù)據(jù)集具有5個比較明顯的聚類區(qū)域，無噪聲點；第2個數(shù)據(jù)集具有4個比較明顯的聚類區(qū)域，含3個噪聲點；第3個數(shù)據(jù)集具有6個比較明顯的聚類區(qū)域，無噪聲點；第4個數(shù)據(jù)集具有5個比較明顯的聚類區(qū)域，含15個噪聲點)上的實驗結(jié)果比較。在表2中，數(shù)據(jù)點數(shù)目n及算法所需設(shè)置的參數(shù)δ的具體值附在數(shù)據(jù)集后的括號內(nèi)。表2的實驗不設(shè)置最大迭代次數(shù)，參數(shù)

ε

設(shè)置為0.000 01，定義3中的

v

(

t

)·

Δt

設(shè)置為0.1。3個指標(biāo)AMI/AVI/NMI的取值基本上可以反映出聚類質(zhì)量(采用人工觀察到的聚類區(qū)域或孤立點來設(shè)置基準(zhǔn)聚類標(biāo)號)的好壞。式(10)所表示的差異值指標(biāo)反映出同步聚類后聚類區(qū)域的穩(wěn)定點集與平均點集之間的平均差異。時間和迭代次數(shù)反映出聚類速度。

3.4 UCI數(shù)據(jù)集的仿真實驗結(jié)果

基于六種同步模型的聚類算法在8個UCI數(shù)據(jù)集上的實驗結(jié)果比較如表3所示。由表3可見，算法所需設(shè)置的參數(shù)

δ

的具體值附在數(shù)據(jù)集后的括號內(nèi)。表3的實驗不設(shè)置最大迭代次數(shù)，參數(shù)

ε

設(shè)置為0.000 01，定義3中的

v

(

t

)·

Δt

設(shè)置為0.1。3個指標(biāo)AMI/AVI/NMI的取值基本上可以反映出聚類純度(采用數(shù)據(jù)集本身的類別號來設(shè)置基準(zhǔn)聚類標(biāo)號)的好壞。式(10)所表示的差異值指標(biāo)反映出同步聚類后聚類區(qū)域的穩(wěn)定點集與平均點集之間的平均差異。時間和迭代次數(shù)反映出聚類速度。

圖1 基于定義2、定義3、定義4、定義5、定義6和定義7的同步聚類模型的動態(tài)聚類過程比較

表2 人工數(shù)據(jù)集的實驗結(jié)果

續(xù)表2

3.5 實驗結(jié)果分析及結(jié)論

從圖1的實驗結(jié)果可以看出，基于定義4的同步聚類算法的聚類效果最好，其他幾種同步聚類模型雖然具有一定的同步效果，但它們的聚類結(jié)果不能很好地反映出數(shù)據(jù)集的聚類結(jié)構(gòu)。從表2的實驗結(jié)果可以看出，基于定義4的同步聚類算法的聚類質(zhì)量總體上最優(yōu)，聚類速度最快。從表3的實驗結(jié)果可以看出，基于定義4的同步聚類算法的聚類質(zhì)量總體上最優(yōu)。通過比較表2和表3還可以看出，有的UCI數(shù)據(jù)集使用幾個同步聚類模型進行聚類時，或者運行時間過長，難以在有效時間范圍內(nèi)達到迭代的終止條件，或者只經(jīng)歷一次迭代就滿足迭代終止條件而退出循環(huán)。基于定義5的同步聚類算法的差異值指標(biāo)通常都取得了最小值，但最終的聚類數(shù)目和AMI/AVI/NMI值并不理想，這是因為這個模型的同步幅度小，未獲得良好的聚類效果?；诙x2和定義3的同步聚類算法在多數(shù)情況下長時間都不能正常地迭代退出同步聚類過程，說明相鄰兩次迭代的均方誤差一直都較大，不能進入同步穩(wěn)定階段。

基于定義4的同步聚類算法在迭代次數(shù)、聚類效果方面總體上表現(xiàn)最好。這種基于近鄰范圍內(nèi)的均值位置更新式(即基于定義4)的迭代同步模型在聚類分析領(lǐng)域非常有效，其聚類效果遠(yuǎn)優(yōu)于基于定義2的同步聚類模型(即文獻[8]首次提出的擴展Kuramoto同步聚類模型)、基于定義3的同步聚類模型和研究提出的另外三種同步聚類模型(分別基于定義5、定義6和定義7)。研究提出的三種同步聚類模型雖然是基于萬有引力定律和指數(shù)衰減規(guī)律而提出來的，但在聚類上的應(yīng)用效果總體上不如基于Vicsek模型的線性版本(即基于定義4)。

另外，我們還觀察到，AMI和AVI指標(biāo)能較好地度量聚類質(zhì)量，而NMI指標(biāo)有時偏好于聚類結(jié)果中簇數(shù)目較多的情況。具體來說就是，當(dāng)聚類結(jié)果與基準(zhǔn)聚類不一致時，簇數(shù)目較多的聚類結(jié)果的NMI值遠(yuǎn)遠(yuǎn)大于簇數(shù)目較少的聚類結(jié)果。例如，Glass數(shù)據(jù)集有210個數(shù)據(jù)點，當(dāng)把每個點當(dāng)作一個單聚類(即孤立點)時，其NMI值為0.530 6，大于對應(yīng)6個聚類和29個孤立點時的NMI值0.454 0。

表3 8個UCI數(shù)據(jù)集的實驗結(jié)果(a 前4個UCI數(shù)據(jù)集的實驗結(jié)果)

續(xù)表3a

表3 8個UCI數(shù)據(jù)集的實驗結(jié)果(b 后4個UCI數(shù)據(jù)集的實驗結(jié)果)

4 結(jié)束語

在聚類分析領(lǐng)域，常見的同步模型有擴展的Kuramoto模型，基于Vicsek模型的線性版本，基于第二個線性版本的Vicsek模型，萬有引力同步模型等。擴展的Kuramoto模型采用一種非線性的動態(tài)同步迭代公式來計算每一個迭代步驟的新位置，而基于Vicsek模型的線性版本采用一種線性的動態(tài)同步迭代公式來計算每一個迭代步驟的新位置，基于第二個線性版本的Vicsek模型采用一種加權(quán)的線性同步迭代公式來計算每一個迭代步驟的新位置。從研究及文獻[16]和文獻[25]的一些仿真實驗可以看出，后兩種同步模型更適合應(yīng)用到聚類分析中。

KMeans和FCM(Fussy C-Means)等基于劃分的聚類算法速度快、應(yīng)用廣，但需要事先設(shè)定正確的聚類數(shù)目，而且多適合于球狀類聚類結(jié)構(gòu)的數(shù)據(jù)集。同步聚類算法具有在多個尺度、多個層次上探測出數(shù)據(jù)集的聚類結(jié)構(gòu)，易于發(fā)現(xiàn)孤立點等優(yōu)點。在Sync算法、ESynC算法和SSynC(Shrinking Synchronization Clustering)算法中，參數(shù)δ的有效取值范圍一般都比較寬泛。但沒有使用空間索引結(jié)構(gòu)的同步聚類算法需要O(Tdn2)的時間復(fù)雜度。近年來流行的譜聚類算法是一種建立在譜圖理論上，將聚類問題轉(zhuǎn)化為圖的最優(yōu)分割問題，可以在特征空間上進行聚類的方法。但譜聚類算法仍難以避免如下幾個缺點，如聚類結(jié)果的好壞依賴于數(shù)據(jù)集相似度矩陣的構(gòu)造，聚類數(shù)目需要人工設(shè)定，最大特征向量集的選擇影響著最終的聚類結(jié)果，需要

O

(

n

)的時間和空間復(fù)雜度等。

下一步，我們將對譜聚類算法與同步聚類算法做一些比較分析研究，嘗試綜合它們的優(yōu)點設(shè)計出更為優(yōu)秀的聚類算法。還可以采用MapReduce框架來實現(xiàn)并行版本的MLSynC方法，并將該方法應(yīng)用到位置數(shù)據(jù)的時空分析中。最后，從理論上證明這些同步聚類模型的迭代收斂性，并將ESynC算法應(yīng)用到文本聚類和Web日志分析中也是未來可以嘗試的工作。