聚類算法在數(shù)據(jù)挖掘領(lǐng)域的研究

蔡程宇，婁淵勝

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

聚類分析[1－5]的重要性及涉及各個(gè)領(lǐng)域的研究已經(jīng)深入人心.而聚類算法的研究在各個(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)域的許多方面.因此它的重要特征是在某一類中，所有的對(duì)象在一定程度上有相似點(diǎn)，同類數(shù)據(jù)之間的相似性越小越好，不同類數(shù)據(jù)之間的相似性越大越好.

1 聚類

1.1 聚類概念

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

設(shè)給定一個(gè)輸入模式的集合Z={X1，X2，X3…，Xn}，Xi表示集合 Z 中的第i個(gè)模式 i={1，2，3…，n};因此我們要把n個(gè)模式硬劃分為K類，即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 聚類準(zhǔn)則

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

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

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

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

1.2.2 離散度準(zhǔn)則

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

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

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

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

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

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

見圖1.

圖1 聚類算法分類

3 聚類算法比較分析

3.1 基于劃分的聚類算法

3.1.1 k－means算法

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

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

2)Repeat{

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

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

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

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

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

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用來表示已選樣的次數(shù)，mincost為最小代價(jià)，current為當(dāng)前節(jié)點(diǎn)，j表示已經(jīng)與當(dāng)前節(jié)點(diǎn)進(jìn)行比較的鄰居個(gè)數(shù).PAM和CLARANS的算法流程圖見圖2、3.

3.2 基于層次的聚類算法

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

圖2 PAM算法流程

圖3 CLARANS算法流程

圖4 BIRCH算法流程

3.3 基于密度的聚類算法

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

DBSCAN算法描述:

在DBSCAN算法中要設(shè)法找到一個(gè)類，首先要假設(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è)類.如果對(duì)象Z為一個(gè)臨界點(diǎn)，即不滿足MinPts，因此Z對(duì)象被標(biāo)記為噪聲點(diǎn)，依次循環(huán)處理下一個(gè)未被標(biāo)記的數(shù)據(jù)對(duì)象來對(duì)聚類進(jìn)行拓?fù)?見圖5.

圖5 DBSCAN算法算法描述

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

計(jì)算與對(duì)象Z以半徑eps為閾值范圍的所有對(duì)象個(gè)數(shù)的過程需要不斷執(zhí)行區(qū)域查詢來實(shí)現(xiàn)，并把查詢的結(jié)果反饋回來，這種有效的查詢是通過使用空間查詢R－樹結(jié)構(gòu)，首先，必須建立R*樹，第二步，對(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取值帶來很好的效果.

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

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

設(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è)前閉后開的區(qū)間.

通常說一個(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，稱數(shù)據(jù)單元u是稠密的，當(dāng)s(v)＞w.

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

4 聚類算法性能比較

見表1.

表1 多種算法的性能比較

5 結(jié)語

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

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

[4]張建華，江 賀，張憲超.蟻群聚類算法綜述[D].阜陽:大連理工大學(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]郭 里.并行層次聚類技術(shù)研究[D].長(zhǎng)沙:湖南大學(xué)，2007.

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

[10]錢彥江.大規(guī)模數(shù)據(jù)聚類技術(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.