一種快速山峰聚類算法

摘 要：山峰聚類既可以對數(shù)據(jù)集進(jìn)行近似聚類，又可以為其他聚類方法提供聚類所需的初始聚類中心。減法聚類是山峰聚類的改進(jìn)，它避免了山峰聚類中出現(xiàn)的計(jì)算量隨樣本維數(shù)增加呈指數(shù)增長的情況。但減法聚類對處理大樣本集也力不從心。引入了Ptree數(shù)據(jù)結(jié)構(gòu)，對高維大樣本集進(jìn)行分解，然后用減法聚類對子樣本集進(jìn)行聚類。此算法既避免了山峰聚類的維數(shù)災(zāi)難問題，也解決了減法聚類中樣本數(shù)太大的問題。實(shí)驗(yàn)結(jié)果證明，該算法有效地減少了運(yùn)算量，提高了聚類的速度。

關(guān)鍵詞：聚類分析； 山峰聚類法； 減法聚類； Ptree； 無監(jiān)督學(xué)習(xí)

中圖分類號：TP391．4 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)07-2043-03



Quick mountain clustering algorithm

CHEN Xiaoyun1，MIN Yufang1，ZHENG Liangren1，YANG Li2

(1.College of Information Science Engineering， Lanzhou University， Lanzhou 730000， China;2.Xinjiang Vocational University， Urumchi 830011， China)Abstract:A new clustering technique is described， which is an improvement on the mountain method (MM) of clustering originally.For higher dimensional data sets， the MM approach becomes computationally unattractive or even infeasible.Subtractive clustering method is an improvement on the mountain method. But for large data sets the SCM can still be computationally intensive. This paper used Ptree data structure to decomposing the higher dimensional and large data sets， then clustered the small data sets using SCM.The method not only avoids the question of higher dimensional， but also solves the shortage of large data sets of SCM. 

Key words:clustering analysis；mountain clustering method；subtractive clustering method(SCM)；Ptree；unsupervised learning 

0 引言

聚類分析是將特性相似的樣本進(jìn)行劃分歸類的過程。聚類分析既是從大量樣本中獲取知識的重要手段，也是數(shù)據(jù)挖掘中的常用方法^[1，2]。根據(jù)聚類準(zhǔn)則的不同，有多種不同的聚類算法^[3]，但大多數(shù)聚類算法都存在兩個(gè)問題：a)需要事先人為地給定一些參數(shù)如聚類個(gè)數(shù)、初始聚類中心等，而在沒有先驗(yàn)知識的情況下，人為確定這些參數(shù)既是非常主觀的，也是十分困難的；b)對于大樣本集或高維樣本集，聚類分析的時(shí)空效率難以保證。山峰聚類法是由Yager等人^[4，5]提出的，是依據(jù)樣本密度計(jì)算聚類中心的簡捷有效的聚類方法。這種方法既可以對數(shù)據(jù)集進(jìn)行近似聚類，又可以為其他聚類方法提供聚類所需的初始聚類中心。不過該方法的計(jì)算量隨樣本的維數(shù)增加呈指數(shù)級增長。為此，Chiu^[6]對山峰聚類作了改進(jìn)，提出了減法聚類（SCM），使得計(jì)算量由樣本數(shù)目決定并且不會隨樣本維數(shù)增加呈指數(shù)增長。但是對于大樣本集SCM方法同樣由于計(jì)算量太大而顯得力不從心。其后，Pal等人^[7]對Chiu提出的減法聚類模型進(jìn)行了改進(jìn)，但是時(shí)間效率并沒有得到很大的提高。

Ptree^[8]（Peano count tree）是一種空間數(shù)據(jù)基于象限的無損失的樹表示。它主要用于高維空間數(shù)據(jù)的存儲，為空間數(shù)據(jù)挖掘做準(zhǔn)備。它的思想是遞歸地劃分高維的樣本集。為了降低在處理高維樣本集和大樣本集時(shí)的時(shí)間復(fù)雜度，本文將Ptree引進(jìn)到山峰聚類算法，在聚類前先將大樣本集用Ptree數(shù)據(jù)結(jié)構(gòu)分解成2n個(gè)小樣本集；然后用改進(jìn)的減法聚類計(jì)算每個(gè)小樣本集的聚類中心，作為整個(gè)聚類的候選聚類中心。用此算法既避免了原山峰聚類算法中隨樣本維數(shù)增加而呈指數(shù)增長的時(shí)間復(fù)雜度，也避免了減法聚類在面對大樣本集時(shí)效率低下。

1 山峰聚類

山峰聚類法是由Yager和Filev在1994年提出的一種大致估計(jì)聚類中心的有效的聚類方法。它的思想是將數(shù)據(jù)樣本空間劃分成有限的網(wǎng)格，并將所有網(wǎng)格的交叉點(diǎn)作為聚類中心的候選中心點(diǎn)，為每個(gè)交叉點(diǎn)構(gòu)造山峰函數(shù)及計(jì)算其值；然后不斷地修改山峰函數(shù)獲取函數(shù)值最大的網(wǎng)格交叉點(diǎn)作為聚類中心。其算法步驟如下：

a）根據(jù)樣本的密度分布，在數(shù)據(jù)樣本空間構(gòu)造網(wǎng)格。其網(wǎng)格的交叉點(diǎn)vj(j=1，2，…，m，m為網(wǎng)格交叉點(diǎn)數(shù)）既是山峰函數(shù)的計(jì)算點(diǎn)，也是聚類中心的候選集，記為vj∈V。V是由網(wǎng)格點(diǎn)構(gòu)成的集合。網(wǎng)格劃分越細(xì)

，不僅潛在地增加了聚類中心的數(shù)目，而且也增大了所需的計(jì)算量。

b）構(gòu)造表示密度指標(biāo)的高斯型山峰函數(shù)，點(diǎn)vj∈V處山峰函數(shù)的高度等于：

m(vj)=Ni=1exp(-‖vj-xi‖2/2σ2)(1)

其中：N為數(shù)據(jù)樣本數(shù)；vj為待計(jì)算的第j個(gè)網(wǎng)格交叉點(diǎn)；xi為第i個(gè)樣本點(diǎn)；影響因子σ是個(gè)重要的參數(shù)，它顯示了數(shù)據(jù)的抱團(tuán)特性，隨著σ值的不斷減小，聚類的抱團(tuán)性質(zhì)減弱。比較極端的情況；當(dāng)σ→0時(shí)，每個(gè)數(shù)據(jù)點(diǎn)自成一類，當(dāng)σ→∞時(shí)，全體數(shù)據(jù)點(diǎn)聚成一類。式（1）表明每個(gè)數(shù)據(jù)點(diǎn)xi對m(C1)=max(m(vj))處山峰函數(shù)高度的貢獻(xiàn)，且貢獻(xiàn)的大小與xi和vj間的距離成反比。當(dāng)分布于聚類中心附近的數(shù)據(jù)增加時(shí)，山峰函數(shù)值趨向于更高；如果中心附近的數(shù)據(jù)點(diǎn)較少，則其值趨向于更小。

c）通過順序地削去山峰函數(shù)來選擇聚類中心。首先，在聚類中心候選集V中選取山峰函數(shù)值最大的點(diǎn)為第一個(gè)聚類中心（如果存在多個(gè)最大值點(diǎn)，任選其一作為第一個(gè)聚類中心），即

m(c1)=max(m(vj))(2)

下一個(gè)聚類中心的獲取需要消除已經(jīng)辨識過的聚類中心的影響。可以通過修改山峰函數(shù)來實(shí)現(xiàn)上述要求，即減去中心在c1處的比例高斯函數(shù)可構(gòu)成新的山峰函數(shù)。

相減后，再選擇V中具有最大新山峰函數(shù)值的點(diǎn)為第二個(gè)聚類中心。這樣不斷地重復(fù)削去山峰函數(shù)和求下一個(gè)聚類中心的過程，直至得到足夠多的聚類中心。圖1就是山峰聚類過程的一個(gè)實(shí)例。圖1（a）中顯示了每個(gè)網(wǎng)格交叉點(diǎn)的山峰函數(shù)值，（b）~（d）是不斷修改山峰函數(shù)，求取聚類中心的示意圖。

由以上計(jì)算過程可見，計(jì)算網(wǎng)格越密，計(jì)算過程越準(zhǔn)確，計(jì)算工作量隨樣本空間維數(shù)的增加呈指數(shù)增長，即存在維數(shù)災(zāi)難問題。一個(gè)解決的辦法就是以樣本點(diǎn)作為計(jì)算點(diǎn)，從而減少計(jì)算工作量，這就是Chiu提出的減法聚類。

減法聚類是用樣本點(diǎn)來代替網(wǎng)格交叉點(diǎn)作為聚類的候選聚類中心，計(jì)算每個(gè)樣本點(diǎn)的山峰函數(shù)值，然后通過順序地削去山峰函數(shù)來選擇聚類中心。減法聚類的時(shí)間復(fù)雜度與樣本的個(gè)數(shù)相關(guān)，當(dāng)出現(xiàn)大樣本集時(shí)，減法聚類的計(jì)算量也是非常巨大的。面對高維大樣本集，要減少計(jì)算工作量，提高計(jì)算效率，本文提出一種新的聚類方法：首先將大樣本集劃分成小樣本集；然后計(jì)算每個(gè)小樣本集的聚類中心，作為整個(gè)聚類的候選聚類中心點(diǎn)。這樣既避免了山峰聚類的維數(shù)災(zāi)難問題，也解決了減法聚類中樣本數(shù)太大的問題。

在樣本集的劃分中，本文采用Ptree數(shù)據(jù)結(jié)構(gòu)來進(jìn)行劃分。

2 Ptree數(shù)據(jù)結(jié)構(gòu)

現(xiàn)存的數(shù)據(jù)挖掘算法一般在時(shí)空上無法滿足處理高維海量數(shù)據(jù)的要求。Ptree數(shù)據(jù)結(jié)構(gòu)是一種空間數(shù)據(jù)基于象限的無損失的樹表示。它可以用于高維空間數(shù)據(jù)的存儲，為空間數(shù)據(jù)挖掘做準(zhǔn)備。其思想是遞歸地劃分高維的樣本集，每個(gè)小樣本集中的樣本數(shù)是近似相同的。Ptree有多種劃分規(guī)則，本文中采用Wolberg^[9]提出的迭代劃分方法。

深度為h的Ptree數(shù)據(jù)結(jié)構(gòu)是將樣本集X所在的超矩形區(qū)域H層次劃分為2h個(gè)相鄰的超矩形區(qū)域{H1，H2，…，H2h}，每個(gè)區(qū)域內(nèi)的樣本點(diǎn)數(shù)是近似相等的。Ptree的根節(jié)點(diǎn)是樣本集X本身，構(gòu)造樹的過程就是遞歸地將樹上的每個(gè)節(jié)點(diǎn)劃分為兩個(gè)子節(jié)點(diǎn)，直到滿足結(jié)束條件的過程。其中每個(gè)子節(jié)點(diǎn)中包含父節(jié)點(diǎn)樣本集中的一半樣本點(diǎn)（如果父節(jié)點(diǎn)包含奇數(shù)個(gè)樣本點(diǎn)，那么其中一個(gè)子節(jié)點(diǎn)比另一個(gè)子節(jié)點(diǎn)中多包含一個(gè)樣本）。Ptree結(jié)構(gòu)是一個(gè)滿二叉樹結(jié)構(gòu)，樹的第k層有2k個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)又是（k+1）層節(jié)點(diǎn)的父節(jié)點(diǎn)。如果樹的深度為h，那么樹的葉子節(jié)點(diǎn)有2h個(gè)，樣本集X被劃分為2h個(gè)小樣本集，每個(gè)小樣本集中包含了大約N/(2h)個(gè)樣本點(diǎn)。

對于有N個(gè)樣本點(diǎn)的s維樣本集X，在進(jìn)行層次分解時(shí)，先對具有最大數(shù)據(jù)間距的維進(jìn)行排序;然后將X劃分為兩個(gè)子集{X11，X12}，X的前一半樣本點(diǎn)屬于X11，后一半屬于X12。如果N是奇數(shù)，那么將中間的樣本歸入任意子集。依次迭代劃分每個(gè)子集，在第k次劃分時(shí)，如果k≤s≤h時(shí)，尋找沒有排過序且數(shù)據(jù)間距最大的維進(jìn)行排序，將樣本集分成兩個(gè)子樣本集；如果s＜k≤h時(shí)，所有的維都已排序，這時(shí)尋找具有最大標(biāo)準(zhǔn)數(shù)據(jù)間距的維（所謂最大標(biāo)準(zhǔn)數(shù)據(jù)間距就是在第k次劃分時(shí)某一子集某一維的數(shù)據(jù)間距與樣本集X中這一維的數(shù)據(jù)間距之間的比值）。以此維為準(zhǔn)，將樣本集劃分為樣本點(diǎn)數(shù)大概相同的兩個(gè)子集。

以下為樣本集X劃分為子樣本集{Xh1，Xh2，Xh3，…，Xh2h}的算法。

輸入：樣本集X，劃分層次h

輸出：子樣本集{Xh1，Xh2，Xh3，…，Xh2h}

a)k=0，X01=X。

b)k=k+1，當(dāng)k≤h時(shí)，對于每個(gè)Xk(2j-1)；j=1，…，2k-1，確定具有最大數(shù)據(jù)間距且沒有排過序的維rk-1j，并以此維為準(zhǔn)對樣本點(diǎn)進(jìn)行升序排列。將樣本點(diǎn)的前一半歸入Xk-1j的子節(jié)點(diǎn)Xk(2j-1)，后一半歸入另一子節(jié)點(diǎn)Xk2j。如果Xk-1j有奇數(shù)個(gè)樣本點(diǎn)，則將中間的一個(gè)樣本點(diǎn)歸入任意子節(jié)點(diǎn)。

c)重復(fù)步驟b），直到k=min(s，h)。如果k=h，跳到e）。

d)K=k+1，當(dāng)s＜k≤h時(shí)，確定具有最大標(biāo)準(zhǔn)數(shù)據(jù)間距的維rk-1j，并以此維為準(zhǔn)對樣本點(diǎn)進(jìn)行升序排列。將樣本點(diǎn)的前一半歸入Xk-1j的子節(jié)點(diǎn)Xk(2j-1)，后一半歸入另一子節(jié)點(diǎn)Xk2j。如果Xk-1j有奇數(shù)個(gè)樣本點(diǎn)，則將中間的一個(gè)樣本點(diǎn)歸入任意子節(jié)點(diǎn)。

e)輸出{Xh1，Xh2，Xh3，…，Xh2h}，劃分算法結(jié)束。

3 算法描述與性能分析

將Ptree數(shù)據(jù)結(jié)構(gòu)引入山峰聚類，首先將樣本集劃分成2h個(gè)小樣本集；然后對每一個(gè)小樣本集用減法聚類，求出其聚類中心，形成聚類中心的候選集合；再對聚類中心候選集合用減法聚類求出其聚類中心，作為整個(gè)樣本集的聚類中心。第2章描述了樣本集的劃分算法，在此基礎(chǔ)上給出了改進(jìn)后算法的整體步驟描述。

輸入：樣本集X，參數(shù)σ，劃分的層次h

輸出：聚類中心或聚類中心候選集

a) 將樣本集X劃分為子樣本集的集合{Xh1，Xh2，Xh3，…，Xh2h}。

b)對于每個(gè)子樣本集Xhj；j=1，…，2h，用改進(jìn)的減法聚類進(jìn)行聚類，求出聚類中心。

c)將所有聚類中心{c1，c2，…，cn}作為聚類中心的候選集輸出，或?qū)蜻x聚類中心{c1，c2，…，cn}用改進(jìn)的減法聚類繼續(xù)進(jìn)行聚類，求出最終的聚類中心集合。

分析算法的時(shí)間復(fù)雜度：a）中劃分?jǐn)?shù)據(jù)集，主要的計(jì)算集中在大樣本集的第一次排序，本文采用快排，時(shí)間復(fù)雜度為O(n lg n)；b）中每個(gè)子集計(jì)算聚類中心的時(shí)間復(fù)雜度為O(n2/2(2h))，那么2h個(gè)子集總共的時(shí)間復(fù)雜度為O(n2/2(2h-1))；c）的時(shí)間復(fù)雜度為O(2(2h))。此算法總的時(shí)間復(fù)雜度為O(n lg n)+O(n2/2(2h-1))，小于原減法聚類的O(n2)，與數(shù)據(jù)集的維數(shù)無關(guān)。

4 實(shí)驗(yàn)結(jié)果與分析

本章展示實(shí)驗(yàn)結(jié)果，算法采用MATLAB編寫，機(jī)器配置為Pentium 4 2.80 GHz CPU，512 MB內(nèi)存，80 GB硬盤。

為了測試改進(jìn)的算法的正確性和高效性，筆者作了兩個(gè)實(shí)驗(yàn)：

a）對同一數(shù)據(jù)集用原山峰聚類方法和改進(jìn)的山峰聚類方法作聚類，找出聚類中心。所用的測試數(shù)據(jù)集是基于Pelleg 和Moore人工合成的高斯數(shù)據(jù)集（2000）^[10]。圖2是實(shí)驗(yàn)結(jié)果展示。圖中藍(lán)色的點(diǎn)是數(shù)據(jù)，紅色的點(diǎn)是找出的聚類中心。其中圖2（a）是原山峰聚類算法找出的聚類中心；（b）（c）中，用改進(jìn)的山峰聚類算法找出聚類中心的候選集。當(dāng)劃分層次值h不同時(shí)，所找出的候選聚類中心的個(gè)數(shù)是不同的。但可以看出，聚類中心是包含在聚類中心候選集中的，當(dāng)對聚類中心候選集再一次聚類時(shí)，一定能找到聚類中心，并且與原山峰聚類算法的效果一樣。

b）測試了改進(jìn)的山峰聚類算法的時(shí)間效率。圖3是基于數(shù)據(jù)集KDD Cup 1998 data (95 413×56)^[11]實(shí)現(xiàn)的，將數(shù)據(jù)集逐次均勻地降維，每次降5維（除了第一次6維），這樣總共產(chǎn)生11個(gè)數(shù)據(jù)集。將每個(gè)數(shù)據(jù)集用新算法各運(yùn)行10次，最后時(shí)間取平均值。可以看出，對于大數(shù)據(jù)集，當(dāng)維數(shù)增高時(shí)，算法的時(shí)間復(fù)雜度呈線性增長。在數(shù)據(jù)挖掘及其應(yīng)用領(lǐng)域中處理高維的大數(shù)據(jù)集時(shí)，新算法則更有優(yōu)越性，在不降低聚類效果的同時(shí)，大大降低了算法的運(yùn)行時(shí)間。

5 結(jié)束語

山峰聚類是一種新型的聚類方法，它能夠處理任意形狀的聚類，具有良好抗噪聲等能力。減法聚類是山峰聚類的改進(jìn)，它有效地控制了計(jì)算量。但減法聚類對處理大樣本集也力不從心。本文引入了Ptree數(shù)據(jù)結(jié)構(gòu)。但是，劃分層次h及影響因子σ的確定還不具備自適應(yīng)性，仍需通過實(shí)驗(yàn)來選取。如何找到自適應(yīng)的方法對該算法進(jìn)行完善，是接下來要進(jìn)行的工作。

參考文獻(xiàn)：

［1］HAND D，MANNILA H，SMYTH P.Principles of data mining[M].Cambridge MA:MIT Press，2001.

[2]JAIN A K，DUBES R C.Algorithms for clustering data[M].Englewood Cliffs:Prentice Hall，1988.

[3]行小帥， 焦李成.數(shù)據(jù)挖掘的聚類方法[J].電路與系統(tǒng)學(xué)報(bào)，2003，8(1): 59-67.

[4]YAGER R R，F(xiàn)ILEV D P.Generation of fuzzy rules by mountain clustering[J].Journal of Intelligent and Fuzzy Systems，1994，2(3):209 219.

[5]YAGER R R，F(xiàn)ILEV D P.Approximate clustering via the mountain method[J].IEEE Trans on Systems，Man， and Cybernetics，1994，24(8):1279-1284.

[6]CHIU S L.Fuzzy model identification based on cluster estimation[J].Journal of Intelligent and Fuzzy Systems，1994，2(3):267-278.

[7]PAL N R，CHAKRABORTY D.Mountain and subtractive clustering method: improvements and generalizations[J].International Journal of Intelligent Systems，2000，15(4):329-341.

[8]SAMET H.The design and analysis of spatial data structures[M].Reading，MA:Addison Wesley Longman，1990.

[9]WOLBERG J R.Expert trading systems[M].New York:John Wiley.2000.

[10][EB/OL].http://cs.cmu.edu/~dpelleg.

[11][EB/OL].http://www.cs.ucsd.edu/users/elkan/fastkmeans.html.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”