蔡程宇，婁淵勝

(河海大學(xué)，南京210000)

聚類(lèi)分析[1－5]的重要性及涉及各個(gè)領(lǐng)域的研究已經(jīng)深入人心.而聚類(lèi)算法的研究在各個(gè)領(lǐng)域已經(jīng)被廣泛應(yīng)用并且不斷的提高，它也是數(shù)據(jù)挖掘[6]技術(shù)的最重要組成部分，能將隱藏在底層的未知的數(shù)據(jù)得以被發(fā)現(xiàn)，目前已經(jīng)廣泛應(yīng)用于模式識(shí)別中的一些圖像處理[7－8]，數(shù)據(jù)分析等其他領(lǐng)域的許多方面.因此它的重要特征是在某一類(lèi)中，所有的對(duì)象在一定程度上有相似點(diǎn)，同類(lèi)數(shù)據(jù)之間的相似性越小越好，不同類(lèi)數(shù)據(jù)之間的相似性越大越好.

1 聚類(lèi)

1.1 聚類(lèi)概念

這里給出關(guān)于聚類(lèi)所下的定義:一個(gè)簇內(nèi)的實(shí)體應(yīng)該是盡可能的相似，而不同簇內(nèi)的實(shí)體應(yīng)該是盡可能的不相似;在同一個(gè)類(lèi)內(nèi)，空間中的數(shù)據(jù)對(duì)象的匯集是通過(guò)距離測(cè)量得到的，在同一類(lèi)內(nèi)的任意兩個(gè)點(diǎn)間的距離必須要小于不同類(lèi)簇的任意兩個(gè)點(diǎn)間的距離;類(lèi)是一個(gè)密度較高的點(diǎn)的集合的多維空間而形成的一個(gè)連通區(qū)域[9－11]，通過(guò)相對(duì)密度較低的點(diǎn)集來(lái)區(qū)分不同的類(lèi).

設(shè)給定一個(gè)輸入模式的集合Z={X1，X2，X3…，Xn}，Xi表示集合 Z 中的第i個(gè)模式 i={1，2，3…，n};因此我們要把n個(gè)模式硬劃分為K類(lèi)，即C={C1，C2…，Ck}(K≤N)，這 K 個(gè)劃分滿足一下幾個(gè)條件:

1)Ci≠φ，i=1，2，…K

2)∪ki=1Ci=Z 且對(duì)?ci，cj?z ci∩cj= φ，ci≠cj，i，j=1，2…K 且 i≠j

1.2 聚類(lèi)準(zhǔn)則

1.2.1 離差平方和準(zhǔn)則(最小方差分割)

假設(shè)n個(gè)樣本分成了K類(lèi)，Xj∈Z對(duì)i=1，2，…k和 j=1，2，…n，定義如下;mij=1，表示第i類(lèi)中含有第j個(gè)樣本則mij標(biāo)注為1

令ni表示第i類(lèi)中所包含的樣本個(gè)數(shù)，

設(shè)Pi∈z表示第i類(lèi)的中心，則

1.2.2 離散度準(zhǔn)則

第1類(lèi)內(nèi)離散度矩陣，首先得到第i類(lèi)的離散度矩陣，假設(shè)mi是第i類(lèi)的中心，則第i類(lèi)中所有樣本相對(duì)該類(lèi)中心的離散程度為:

則總的內(nèi)離散度矩陣的和為:

第2類(lèi)間離散度矩陣，每一類(lèi)的中心相對(duì)總的中心的離散程度和為:

SB，m 是所有樣本中心第3總離散度矩陣，所有樣本相對(duì)總的中心的離散程度:－m)]T=↑SB+SW.ST在這里面是不變量，即為常數(shù)，SB，SW隨樣本劃分的改變而改變，因此與樣本劃分有關(guān)，而SB，SW，都是矩陣，通過(guò)定準(zhǔn)則比大小.

若k=n，則一個(gè)點(diǎn)成一個(gè)類(lèi)，那么這樣的聚類(lèi)顯然是沒(méi)有意義的，且離差平方和準(zhǔn)則達(dá)到最大，所以系數(shù)k的確立是對(duì)整個(gè)離差平方和準(zhǔn)則有著重大影響并對(duì)J的影響也不容忽視.

2 傳統(tǒng)聚類(lèi)算法分類(lèi)圖

見(jiàn)圖1.

圖1 聚類(lèi)算法分類(lèi)

3 聚類(lèi)算法比較分析

3.1 基于劃分的聚類(lèi)算法

3.1.1 k－means算法

k－means是聚類(lèi)算法中最簡(jiǎn)單的一種了，但是它的算法思想?yún)s非比尋常，在聚類(lèi)問(wèn)題中，我們可以假設(shè)樣本{x(1)，x(2)，x(3)，…x(n)}∈Z，k －means算法是將n個(gè)樣本聚類(lèi)成k個(gè)簇，具體算法描述:

1)隨機(jī)選取 k 個(gè)聚類(lèi)質(zhì)點(diǎn)為 v1，v2，v3…，vk∈Z.

2)Repeat{

對(duì)于每一個(gè)樣例i，計(jì)算其應(yīng)該屬于的類(lèi)

c(i):=argmin‖x(i)－vj‖2

對(duì)于每一個(gè)類(lèi)j，重新計(jì)算類(lèi)的質(zhì)心

}直到收斂為止，算法結(jié)束

k是一個(gè)常量，c(i)代表第i個(gè)數(shù)據(jù)對(duì)象與k個(gè)類(lèi)中質(zhì)點(diǎn)距離最近的值，質(zhì)心vj代表同一個(gè)類(lèi)的樣本中心.

3.1.2 PAM、CLARANS 算法

在PAM算法中假設(shè)非代表對(duì)象Oh替換當(dāng)前代表對(duì)象Oi的總代價(jià)為Uih，非代表對(duì)象Oh替換當(dāng)前代表對(duì)象Oi所產(chǎn)生的對(duì)于非代表對(duì)象Oj的代價(jià)為Ujih.則對(duì)每個(gè)非代表對(duì)象Oi，計(jì)算Ujih有以下四種情況:

1)Oj∈Oi，對(duì)任意代表數(shù)據(jù)對(duì)象 Om，若 Oi被Oh替換，d(Oj，Om)min，則 Oj∈Om，Ujih=d(Oj，Om)－ d(Oj，Oi).

2)Oj∈Oi，對(duì)任意代表數(shù)據(jù)對(duì)象 Om，若 Oi被Oh替換，d(Oj，Oh)min，則 Oj∈Oh，Ujih=d(Oj，Oh)－ d(Oj，Oi).

3)Oj∈Om，對(duì)任意代表數(shù)據(jù)對(duì)象 Om，若 Oi被Oh替換，d(Oj，Om)min，則，Oj∈Om，Ujih=0.

4)Oj∈Om，對(duì)任意代表數(shù)據(jù)對(duì)象Om，若Oi被Oh替換，d(Oj，Oh)min，則 Oj∈Oh，Ujih=d(Oj，Oh)－ d(Oj，Om).

因此Uth=Σijih為Oi替換對(duì)所有的非代表對(duì)象Oj的總代價(jià).如果Uih＜0則Oh替換Oi，進(jìn)入循環(huán)迭代操作，否則質(zhì)心不變.

在CLARANS算法中首先假設(shè)幾個(gè)參數(shù):numlocal和maxneighbor分別表示抽樣次數(shù)和任意一個(gè)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)比較數(shù)目，i用來(lái)表示已選樣的次數(shù)，mincost為最小代價(jià)，current為當(dāng)前節(jié)點(diǎn)，j表示已經(jīng)與當(dāng)前節(jié)點(diǎn)進(jìn)行比較的鄰居個(gè)數(shù).PAM和CLARANS的算法流程圖見(jiàn)圖2、3.

3.2 基于層次的聚類(lèi)算法

BIRCH在層次聚類(lèi)算法中屬于至關(guān)重要的算法之一，即平衡迭代削減聚類(lèi).其中涉及到聚類(lèi)特征(CF)和聚類(lèi)特征樹(shù)(CF Tree)兩個(gè)概念，主要思想是通過(guò)掃描數(shù)據(jù)庫(kù)，建立一個(gè)初始存放于內(nèi)存中的聚類(lèi)特征樹(shù)，然后對(duì)聚類(lèi)特征樹(shù)的葉結(jié)點(diǎn)進(jìn)行聚類(lèi).它的核心是聚CF和CF Tree.CF是指三元組CF=(N，LS，SS)，用來(lái)概括子簇信息.其中:N為簇中d維點(diǎn)的數(shù)目;LS為N個(gè)點(diǎn)的線性和;SS為N個(gè)點(diǎn)的平方和.CF樹(shù)是一棵具有兩個(gè)參數(shù)的高度平衡樹(shù)，用來(lái)存儲(chǔ)層次聚類(lèi)的聚類(lèi)特征.它涉及到兩個(gè)參數(shù)分支因子和閾值.CF樹(shù)的構(gòu)造過(guò)程實(shí)際上是一個(gè)數(shù)據(jù)點(diǎn)的插入過(guò)程，其步驟見(jiàn)圖4.

圖2 PAM算法流程

圖3 CLARANS算法流程

圖4 BIRCH算法流程

3.3 基于密度的聚類(lèi)算法

DBSCAN算法是基于密度的聚類(lèi)算法，它有著顯著的不同，它是將高密度的點(diǎn)相互連接起來(lái)的一個(gè)最大集合并能快速找到不規(guī)則形狀的聚類(lèi).

DBSCAN算法描述:

在DBSCAN算法中要設(shè)法找到一個(gè)類(lèi)，首先要假設(shè)兩個(gè)參數(shù)，eps及MinPts分別代表半徑和最小數(shù)目，然后從數(shù)據(jù)庫(kù)中隨機(jī)取得一個(gè)數(shù)據(jù)對(duì)象Z，并計(jì)算與該對(duì)象Z以半徑eps為閾值范圍的所有對(duì)象的個(gè)數(shù)，如果個(gè)數(shù)大于等于MinPts，則對(duì)象Z為核心對(duì)象，即可找到關(guān)于這兩個(gè)參數(shù)的一個(gè)類(lèi).如果對(duì)象Z為一個(gè)臨界點(diǎn)，即不滿足MinPts，因此Z對(duì)象被標(biāo)記為噪聲點(diǎn)，依次循環(huán)處理下一個(gè)未被標(biāo)記的數(shù)據(jù)對(duì)象來(lái)對(duì)聚類(lèi)進(jìn)行拓?fù)?見(jiàn)圖5.

圖5 DBSCAN算法算法描述

上述DBSCAN流程圖中所定義到的eps及MinPts參數(shù)對(duì)整個(gè)結(jié)果影響是非常大的，而對(duì)于用戶的選擇來(lái)說(shuō)是隨機(jī)不定的，因此這也是我們應(yīng)該要解決的問(wèn)題.

計(jì)算與對(duì)象Z以半徑eps為閾值范圍的所有對(duì)象個(gè)數(shù)的過(guò)程需要不斷執(zhí)行區(qū)域查詢(xún)來(lái)實(shí)現(xiàn)，并把查詢(xún)的結(jié)果反饋回來(lái)，這種有效的查詢(xún)是通過(guò)使用空間查詢(xún)R－樹(shù)結(jié)構(gòu)，首先，必須建立R*樹(shù)，第二步，對(duì)于參數(shù)的選擇，在這里又引入了k－dist圖，是計(jì)算所有對(duì)象與它的第k個(gè)最近的對(duì)象之間的距離，對(duì)計(jì)算的結(jié)果進(jìn)行從小到大的排序并繪k－dist圖.橫坐標(biāo)表示任意對(duì)象與第k個(gè)最近數(shù)據(jù)對(duì)象之間的距離，而縱坐標(biāo)表示相同距離值的數(shù)據(jù)對(duì)象的個(gè)數(shù).雖然工序復(fù)雜，但是k－dist圖可以為eps取值帶來(lái)很好的效果.

3.4 基于密度和網(wǎng)格的聚類(lèi)算法

CLIQUE算法是基于密度同時(shí)基于網(wǎng)格的聚類(lèi)算法.主要用于找出在高維數(shù)據(jù)空間中存在的低維聚類(lèi)，采用了子空間的概念來(lái)進(jìn)行聚類(lèi)，因此它適合處理解決高維數(shù)據(jù).CLIQUE聚類(lèi)算法空間劃分和密集單元:

設(shè) A={C1，C2，C3，……，Cn}是個(gè)有界的定義子空間，則S=C1×C2×C3×……×Cn就是一個(gè)n維的數(shù)據(jù)空間，將 C1，C2，C3，……，Cn看作 S 的屬性或者字段.

clique算法的輸入對(duì)象是一個(gè)n維空間中的數(shù)據(jù)對(duì)象點(diǎn)集，設(shè)為 u={u1，u2，u3，……，un}，其中 ui={ui1，ui2，ui3，……，uin}，ui的第個(gè) j分量 uij∈Cj.

算法中，輸入一個(gè)參數(shù)a，可以將空間S的每一維分成相同的a個(gè)區(qū)間，從而將整個(gè)空間分成有限(an)個(gè)互不相交的矩形單元格，每一個(gè)這樣的矩形單元格可以描述為{v1，v2，……，vn}，其中vi=[li，hi)，均為一個(gè)前閉后開(kāi)的區(qū)間.

通常說(shuō)一個(gè)數(shù)據(jù)對(duì)象 u={u1，u2，u3，……，un}落入一個(gè)單元格v={v1，v2，……，vn}當(dāng)且僅當(dāng)對(duì)于每一個(gè)vi都有l(wèi)i≤ ui＜hi成立.

一個(gè)單元的選擇率s(v)為s(v)=單元格中的點(diǎn)數(shù)/總的點(diǎn)數(shù)，設(shè)定一個(gè)密度閾值w，稱(chēng)數(shù)據(jù)單元u是稠密的，當(dāng)s(v)＞w.

Clique利用的一個(gè)性質(zhì):如果一個(gè)k維單元是密集的，那么他在k－1維空間上的投影也是密集的.也就是說(shuō)，給定一個(gè)k維的候選密集單元，如果檢查它的k－1維投影單元，發(fā)現(xiàn)任何一個(gè)不是密集的，那么就知道第k維的單元也不可能是密集的.因此可以從k－1維空間中發(fā)現(xiàn)的密集單元來(lái)推測(cè)k維空間中潛在的或候選的密集單元.(類(lèi)似于Aprior性質(zhì))

4 聚類(lèi)算法性能比較

見(jiàn)表1.

表1 多種算法的性能比較

5 結(jié)語(yǔ)

聚類(lèi)算法目前仍然是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)熱點(diǎn)，并且在好多領(lǐng)域得到廣泛的應(yīng)用，如:機(jī)器學(xué)習(xí)，模式識(shí)別，天文物理等各個(gè)研究領(lǐng)域，在本文中也例出了幾個(gè)經(jīng)典的聚類(lèi)算法，并對(duì)其思想，性能和優(yōu)缺點(diǎn)進(jìn)行了深度分析，因此聚類(lèi)不僅是過(guò)去，現(xiàn)在，乃至將來(lái)都是一個(gè)具有不可取代地位的一門(mén)學(xué)科.

[1]JAIN A K，DUIN R P W，MAO J C.Statistical pattern recogni-tion:A review.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2000，22(1):4－37.

[2]李明華.數(shù)據(jù)挖掘中聚類(lèi)算法的新發(fā)展[D].蘇州:蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，2008.

[3]朱 強(qiáng).粒度計(jì)算在聚類(lèi)分析中的應(yīng)用[D].合肥:安徽大學(xué)，2007.

[4]張建華，江 賀，張憲超.蟻群聚類(lèi)算法綜述[D].阜陽(yáng):大連理工大學(xué)軟件學(xué)院，2006.

[5]HAN J，KAMBER M.Data Mining:Concepts and Techniques[M].San Francisco:Morgan Kaufmann，2006.

[6]韓彥芳，施鵬飛.基于蟻群算法的圖像分割方法[J].計(jì)算機(jī)工程與用，2004，40(18):5－7.

[7]HAN J W，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社，2001.

[8]郭 里.并行層次聚類(lèi)技術(shù)研究[D].長(zhǎng)沙:湖南大學(xué)，2007.

[9]楊彥侃.并行的聚類(lèi)算法研究[D].包頭:內(nèi)蒙古科技大學(xué)，2010.

[10]錢(qián)彥江.大規(guī)模數(shù)據(jù)聚類(lèi)技術(shù)與實(shí)現(xiàn)[D].成都:成都電子科技大學(xué)，2009.

[11]周慶欣，吳玉東，范紅霞，等.加權(quán)Markov鏈權(quán)重計(jì)算及其應(yīng)用[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2014，30(6):740－743.