李順勇 張鈺嘉 彭曉慶 曹付元 劉恩乾

1(山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院 山西 太原 030006) 2(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006) 3(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室 山西 太原 030006)

0 引 言

聚類分析是一種無監(jiān)督算法，其目標(biāo)是按照某種相似性度量將數(shù)據(jù)集中相似度較大的數(shù)據(jù)分到同一個(gè)簇，盡可能使簇內(nèi)的數(shù)據(jù)相似性較大、簇間數(shù)據(jù)相似性較小[1-2]。聚類算法多種多樣，可以從不同角度對(duì)算法進(jìn)行分類，如根據(jù)層次、劃分、密度等角度對(duì)其分類。如今處于大數(shù)據(jù)時(shí)代，數(shù)據(jù)量的增加以及數(shù)據(jù)本身的復(fù)雜化給聚類分析帶來了不小的難度，一些面向于大型數(shù)據(jù)分類的算法被提出，本文針對(duì)各種算法可處理的原數(shù)據(jù)類型對(duì)其進(jìn)行分類，如圖1所示。

圖1 聚類分類

傳統(tǒng)方法中具有代表性的方法如K-means[3]、K-modes[4]、K-prototypes[5]、CURE[6]和DBSCAN[7]等。文獻(xiàn)[3]提出了K-means算法，其距離度量函數(shù)面向的是數(shù)值型數(shù)據(jù)，所以在數(shù)據(jù)集比較復(fù)雜并且含有分類型數(shù)據(jù)時(shí)該算法存在一些不足。文獻(xiàn)[4]提出了K-modes算法，該算法用modes代替means，在處理分類型數(shù)據(jù)時(shí)有較好效果。文獻(xiàn)[5]提出了K-prototypes算法，利用簡單匹配差異度來度量分類型數(shù)據(jù)距離，并且引入?yún)?shù)來刻畫兩種屬性數(shù)據(jù)在距離度量時(shí)所占的權(quán)重。文獻(xiàn)[6]提出的CURE算法可以識(shí)別一些形狀比較復(fù)雜的簇，并且可以檢測(cè)出數(shù)據(jù)中的一些異常點(diǎn)，但是該算法得到的結(jié)果不夠穩(wěn)定。文獻(xiàn)[7]提出了基于密度劃分的算法，提出了Density-reachability和Density-connectivity，該算法可以處理不同形狀的簇，并且算法性能較好。文獻(xiàn)[8]提出了一種智能聚類算法，該算法不需要計(jì)算結(jié)構(gòu)化單分類器中的二次錐規(guī)劃，只需要計(jì)算一個(gè)線性規(guī)劃問題即可，從而節(jié)省了運(yùn)算時(shí)間。文獻(xiàn)[9]提出的算法降低了聚類運(yùn)行時(shí)間，但是在處理分類型數(shù)據(jù)時(shí)該算法運(yùn)行結(jié)果較差。文獻(xiàn)[10]提出了一種高效率的處理大型數(shù)據(jù)的DBDC算法，該算法基本思想和DBSCAN算法相同，區(qū)別是DBDC算法是一種并行算法，效率遠(yuǎn)高于DBSCAN算法。文獻(xiàn)[11]提出了一種基于稀疏編碼的算法，該算法抽取一些數(shù)據(jù)點(diǎn)來逼近相似度矩陣，但是該方法得到的結(jié)果不穩(wěn)定。文獻(xiàn)[12]提出了一種并行算法，去掉了一些影響聚類質(zhì)量的因素，如在輸入數(shù)據(jù)時(shí)順序的影響，并取得較好效果，其不足是不能處理混合數(shù)據(jù)。文獻(xiàn)[13]提出了一種快速聚類算法，該算法結(jié)合了MapReduce分布并行計(jì)算框架，得到的結(jié)果較為穩(wěn)定并且性能較好。

上述方法在處理大規(guī)模數(shù)據(jù)時(shí)會(huì)出現(xiàn)算法迭代時(shí)間長、聚類精度低等問題。為了在不影響聚類精度的前提下對(duì)數(shù)據(jù)進(jìn)行快速有效的劃分，本文提出了一種基于分層抽樣的大數(shù)據(jù)快速聚類算法。該算法大致分3個(gè)步驟進(jìn)行：(1)隨機(jī)抽取μk個(gè)點(diǎn)(k為數(shù)據(jù)集簇?cái)?shù)，μ為正數(shù))，隨后在原始數(shù)據(jù)集上根據(jù)距離最小原則將剩余未抽到的數(shù)據(jù)劃分到μk個(gè)點(diǎn)附近，得到μk個(gè)層，這樣在進(jìn)行抽樣時(shí)可以覆蓋數(shù)據(jù)的全局信息，降低初始點(diǎn)選取時(shí)的敏感性；(2)根據(jù)本文提出的抽樣方案進(jìn)行分層抽樣，得到樣本集；(3)用K-means算法對(duì)抽取的樣本數(shù)據(jù)集進(jìn)行聚類，得到劃分結(jié)果。

1 K-means算法[3]

設(shè)一數(shù)據(jù)集為X={X1,X2,…,XN}，X中共有N個(gè)數(shù)據(jù)，每個(gè)Xi有m個(gè)屬性，即Xi={xi1,xi2,…,xim}，設(shè)初始原型集合V={V1,V2,…,Vk}，經(jīng)過K-means算法得到的k個(gè)簇為C={C1,C2,…,Ck}，其中C1∪C2∪…∪Ck=C且Ci∩Cj=?。該算法的分類標(biāo)準(zhǔn)如定義1所示。

定義1[3]數(shù)據(jù)的分類標(biāo)準(zhǔn)為：

(1)

具體過程如算法1所示。

算法1[3]K-means算法

輸入：原型k，數(shù)據(jù)集X。

輸出：劃分結(jié)果。

Step1選擇k個(gè)原型V；

Step2根據(jù)式(1)將數(shù)據(jù)集中的各個(gè)樣本分到各自所屬的簇中，更新簇中心；

Step3計(jì)算原數(shù)據(jù)集中的數(shù)據(jù)和Step2中得到的簇中心的距離，根據(jù)式(1)對(duì)數(shù)據(jù)重新進(jìn)行劃分，并得出新的簇中心；

Step4重復(fù)Step2和Step3直到簇中心不再變化為止。

K-means算法由于其計(jì)算復(fù)雜度較小并且實(shí)現(xiàn)方便而得到廣泛應(yīng)用，但是K-means算法也存在一些不足之處：(1)在選取初始原型時(shí)采用的是隨機(jī)選取原則，這樣會(huì)造成算法結(jié)果不穩(wěn)定，易受到初始原型選擇的影響；(2)迭代次數(shù)較多，在處理數(shù)據(jù)量較大或者數(shù)據(jù)維數(shù)較高的數(shù)據(jù)時(shí)算法運(yùn)行時(shí)間較長。

2 算法設(shè)計(jì)

基于上述K-means算法存在的一些不足，本文提出了FCASS算法。該算法將分層抽樣與K-means算法結(jié)合，使其能在較短時(shí)間內(nèi)輸出正確率較高并且較穩(wěn)定的劃分結(jié)果。

為了使抽取出來的樣本數(shù)據(jù)集有較好的代表性，確定抽取樣本大小以及抽樣方法尤為重要。基于此，本文還提出了一種分層抽樣算法。

2.1 分 層

分層即將原始數(shù)據(jù)及分成不同層，使得同一個(gè)層內(nèi)的數(shù)據(jù)相似度較大，不同層的數(shù)據(jù)相似度較小。K-means根據(jù)式(1)將數(shù)據(jù)分到距離其最小的k個(gè)初始點(diǎn)中，并且一直迭代，直到簇中心不變?yōu)橹埂Ｊ紫冗x取h(h=μk，h

該分層技術(shù)優(yōu)點(diǎn)較明顯：(1)選取的初始點(diǎn)個(gè)數(shù)大于k，這樣會(huì)降低分層時(shí)受初始點(diǎn)隨機(jī)選擇的影響；(2)只需要計(jì)算一次初始點(diǎn)和原始數(shù)據(jù)集中其他數(shù)據(jù)之間的距離，計(jì)算量小，節(jié)省時(shí)間。μ的具體取值會(huì)在仿真實(shí)驗(yàn)中求出。

2.2 總樣本量的確定

本文采用文獻(xiàn)[14]中的方法來得出合適的總樣本數(shù)n：

(2)

式中：S2為總體方差；Nh為第h層數(shù)據(jù)總數(shù)；Sh為第h層標(biāo)準(zhǔn)差。

2.3 各層樣本量的分配

(3)

(4)

引進(jìn)隨機(jī)變量ai(i=1,2,…,N)，若Yi被抽中,ai=1；反之，ai=0。

證畢。

(5)

由定義2可知：

(6)

(7)

(8)

證畢。

定義4抽取樣本的時(shí)間函數(shù)為：

(9)

(10)

(11)

根據(jù)Cauchy-Schwarz不等式，對(duì)于任意ah≥0,bh≥0，有：

(12)

(13)

式(13)中等號(hào)成立的條件是：

(14)

(15)

假定各層的單位抽樣時(shí)間相等，即th=t，得到每層抽取的樣本數(shù)，計(jì)算公式如下：

(16)

從式(16)可以看出，有較大WhSh的層會(huì)抽取較多的樣本。Wh較大，意味著該層有較多的數(shù)據(jù)，所以應(yīng)從該層抽取較多的樣本；Sh較大，意味著該層數(shù)據(jù)分布較為分散，為了使抽到的樣本能代表該層，故抽取的樣本數(shù)也較多。

算法2FCASS算法

輸入：原始數(shù)據(jù)集X，k個(gè)初始點(diǎn)。

輸出：最終分類結(jié)果。

Step1選取h個(gè)初始原點(diǎn)，根據(jù)式(1)將數(shù)據(jù)集X分為h層；

Step2根據(jù)式(2)計(jì)算要抽取的合理樣本個(gè)數(shù)n；

Step3根據(jù)式(15)計(jì)算出每層抽取的nh；

Step4對(duì)每層進(jìn)行抽樣，得到樣本集L={n1,n2,…,nh}；

Step5對(duì)抽取的樣本運(yùn)行K-means算法，得到劃分結(jié)果。

3 仿真實(shí)驗(yàn)

3.1 數(shù)據(jù)集的選擇及評(píng)價(jià)標(biāo)準(zhǔn)

本文選取UCI數(shù)據(jù)庫[15]的4個(gè)數(shù)據(jù)集以及8個(gè)人工數(shù)據(jù)集對(duì)算法性能以及運(yùn)行速度進(jìn)行評(píng)測(cè)，數(shù)據(jù)集形式如表1所示，其中：h表示屬性數(shù)；class表示分類個(gè)數(shù)，即模k；instance表示樣本個(gè)數(shù)。

表1 數(shù)據(jù)集信息

可以看出，Transfusion、Banknote、HTRU2以及Activity Recognition 4個(gè)數(shù)據(jù)集的instance相差較大，并且HTRU2和Activity Recognition數(shù)據(jù)集的h為9，維數(shù)較高，這樣選取的數(shù)據(jù)集代表性較好，能較好體現(xiàn)算法在處理不同維度以及不同樣本數(shù)的數(shù)據(jù)集時(shí)的性能。因此，本文生成的Artificial data也盡量增大數(shù)據(jù)集之間的差異性，如Artificial data 1到Artificial data 4數(shù)據(jù)集的h=3，但instance相差較大，并且與Artificial data 5到Artificial data 8的h相差較大，這樣可以較全面地對(duì)算法性能進(jìn)行測(cè)試。

本文選取AC、ARI[16]以及算法運(yùn)行時(shí)間T作為評(píng)價(jià)指標(biāo)。對(duì)數(shù)據(jù)集X={X1,X2,…,Xn}，通過聚類劃分得到的簇和在原始數(shù)據(jù)集中已有類標(biāo)簽劃分得到的簇分別為C={C1,C2,…,Ck-1,Ck}和P={P1,P2,…,Pk′}，定義AC和ARI計(jì)算公式如下：

式中：nCi和nPj分別是Ci和Pj中對(duì)象的個(gè)數(shù)，nij=|Ci∩Pj|。經(jīng)過計(jì)算可知，0≤AC≤1,0≤ARI≤1，且AC、ARI值越接近1，劃分效果越好。

3.2 參數(shù)μ的確定

確定參數(shù)μ的算法的具體過程見算法3。

算法3確定參數(shù)μ算法

輸入：原始數(shù)據(jù)集X，初始點(diǎn)k。

輸出：劃分錯(cuò)誤率。

Step1令μ=1，選取h=μk個(gè)初始點(diǎn)，根據(jù)式(1)將數(shù)據(jù)集X分為h層；

Step2根據(jù)式(2)計(jì)算要抽取的合理樣本個(gè)數(shù)；

Step3根據(jù)式(16)計(jì)算出每層抽取的nh；

Step4對(duì)每層進(jìn)行抽樣，得到樣本集L={n1,n2,…,nh}；

Step5對(duì)抽取的樣本運(yùn)行K-means算法，得到劃分結(jié)果，并計(jì)算AC和ARI值；

Step6令μ=2,3,…，重復(fù)上述步驟，并計(jì)算AC和ARI值。

選取表1中的Transfusion、Banknote和HTRU2 3個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，Transfusion數(shù)據(jù)集中有748個(gè)樣本，Banknote數(shù)據(jù)集中有1 372個(gè)樣本，HTRU2數(shù)據(jù)集中有17 898個(gè)樣本，每個(gè)數(shù)據(jù)集的樣本個(gè)數(shù)相差較大，這樣可以使得出的結(jié)論更加可信。在三個(gè)數(shù)據(jù)集上運(yùn)行算法3共10次，計(jì)算出AC和ARI值，實(shí)驗(yàn)結(jié)果如圖2-圖4所示。圖中橫軸表示的是μ的值，縱軸表示的是AC和ARI值，其值越大說明算法效果越好。

圖2 Transfusion數(shù)據(jù)集不同μ值結(jié)果對(duì)比

圖3 Banknote數(shù)據(jù)集不同μ值結(jié)果對(duì)比

圖4 HTRU2數(shù)據(jù)集不同μ值結(jié)果對(duì)比

由圖2可知，當(dāng)μ=3時(shí)，在Transfusion數(shù)據(jù)集上AC和ARI值最大，故在該數(shù)據(jù)集上μ取3較為合適。

由圖3可知，當(dāng)μ=4時(shí)，在Banknote數(shù)據(jù)集上AC值最大，ARI值也最大，因此在Banknote數(shù)據(jù)集上μ取4較為合適。

由圖4可知，當(dāng)μ=5時(shí)，在HTRU2數(shù)據(jù)集上AC值最大，但是ARI值較??；μ=4時(shí)算法3輸出的ARI值最高，AC值也較大。因此，考慮到算法運(yùn)行時(shí)間以及AC值和ARI值，認(rèn)為在HTRU2數(shù)據(jù)集上μ取4較為合適。綜上，本文將μ定為4。

3.3 算法比較

3.3.1真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)選取表1中的Transfusion、Banknote、HTRU2以及Activity Recognition四個(gè)數(shù)據(jù)集，為了方便，本文將上述4個(gè)數(shù)據(jù)集的名稱簡寫為TF、BK、HT2和AR。將本文算法的聚類結(jié)果與K-means算法結(jié)果作對(duì)比。上述4個(gè)數(shù)據(jù)集的h、class以及instance均相差較大，這樣的實(shí)驗(yàn)結(jié)果具有較好的對(duì)比性，結(jié)果如表2所示。

表2 真實(shí)數(shù)據(jù)集結(jié)果對(duì)比

可以看出，在4個(gè)數(shù)據(jù)集上本文算法的AC值與K-means算法相差不大，HT2數(shù)據(jù)集和AR數(shù)據(jù)集上本文算法的AC值甚至略高于K-means算法，說明本文算法劃分效果較好；在Transfusion和Banknote數(shù)據(jù)集上本文算法運(yùn)行時(shí)間略長于K-means算法，但在HTRU2和Activity Recognition數(shù)據(jù)集上本文算法運(yùn)行較快，結(jié)合表1中各個(gè)數(shù)據(jù)集的信息可以發(fā)現(xiàn)，當(dāng)數(shù)據(jù)集的h較高以及instance較多時(shí)，本文算法運(yùn)行速度較快。

3.3.2人工數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)選取表1中的8個(gè)Artificial data進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)對(duì)比結(jié)果如表3所示。

表3 Artificial data實(shí)驗(yàn)結(jié)果對(duì)比

可以看出，在8個(gè)Artificial data上本文算法的AC值與K-means算法相差不大，這是因?yàn)楸疚某槿〉臉颖揪哂休^好的代表性。在8個(gè)Artificial data數(shù)據(jù)集上本文算法運(yùn)行的時(shí)間均少于K-means算法，Artificial data中instance越多，本文算法運(yùn)行速度的優(yōu)越性體現(xiàn)得越明顯，并且在數(shù)據(jù)集h增高時(shí)，本文算法運(yùn)行時(shí)間遠(yuǎn)快于K-means算法。

結(jié)合表2和表3中的數(shù)據(jù)對(duì)比，本文算法在較高維度數(shù)據(jù)集以及大樣本數(shù)據(jù)集上聚類效果優(yōu)良并且算法運(yùn)行時(shí)間較短。

4 結(jié) 語

本文提出了一種基于分層抽樣的大數(shù)據(jù)快速聚類集成算法，該算法能夠快速地處理較高維度以及大樣本數(shù)據(jù)集，并且能夠得到較高的聚類精度。本文算法的核心是分層抽樣技術(shù)，其保證所抽取的樣本具有較好的代表性。最后在4個(gè)UCI數(shù)據(jù)集以及8個(gè)人工數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明在數(shù)據(jù)規(guī)模比較大時(shí)，本文算法有較高的聚類精度以及較短的運(yùn)行時(shí)間，驗(yàn)證了本文算法的有效性。