一種基于分層抽樣的大數據快速聚類算法

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

1(山西大學數學科學學院 山西 太原 030006) 2(山西大學計算機與信息技術學院 山西 太原 030006) 3(計算智能與中文信息處理教育部重點實驗室 山西 太原 030006)

0 引 言

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

圖1 聚類分類

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

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

1 K-means算法[3]

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

定義1[3]數據的分類標準為：

(1)

具體過程如算法1所示。

算法1[3]K-means算法

輸入：原型k，數據集X。

輸出：劃分結果。

Step1選擇k個原型V；

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

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

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

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

2 算法設計

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

為了使抽取出來的樣本數據集有較好的代表性，確定抽取樣本大小以及抽樣方法尤為重要?；诖?，本文還提出了一種分層抽樣算法。

2.1 分 層

分層即將原始數據及分成不同層，使得同一個層內的數據相似度較大，不同層的數據相似度較小。K-means根據式(1)將數據分到距離其最小的k個初始點中，并且一直迭代，直到簇中心不變為止。首先選取h(h=μk，h

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

2.2 總樣本量的確定

本文采用文獻[14]中的方法來得出合適的總樣本數n：

(2)

式中：S2為總體方差；Nh為第h層數據總數；Sh為第h層標準差。

2.3 各層樣本量的分配

(3)

(4)

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

證畢。

(5)

由定義2可知：

(6)

(7)

(8)

證畢。

定義4抽取樣本的時間函數為：

(9)

(10)

(11)

根據Cauchy-Schwarz不等式，對于任意ah≥0,bh≥0，有：

(12)

(13)

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

(14)

(15)

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

(16)

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

算法2FCASS算法

輸入：原始數據集X，k個初始點。

輸出：最終分類結果。

Step1選取h個初始原點，根據式(1)將數據集X分為h層；

Step2根據式(2)計算要抽取的合理樣本個數n；

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

Step4對每層進行抽樣，得到樣本集L={n1,n2,…,nh}；

Step5對抽取的樣本運行K-means算法，得到劃分結果。

3 仿真實驗

3.1 數據集的選擇及評價標準

本文選取UCI數據庫[15]的4個數據集以及8個人工數據集對算法性能以及運行速度進行評測，數據集形式如表1所示，其中：h表示屬性數；class表示分類個數，即模k；instance表示樣本個數。

表1 數據集信息

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

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

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

3.2 參數μ的確定

確定參數μ的算法的具體過程見算法3。

算法3確定參數μ算法

輸入：原始數據集X，初始點k。

輸出：劃分錯誤率。

Step1令μ=1，選取h=μk個初始點，根據式(1)將數據集X分為h層；

Step2根據式(2)計算要抽取的合理樣本個數；

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

Step4對每層進行抽樣，得到樣本集L={n1,n2,…,nh}；

Step5對抽取的樣本運行K-means算法，得到劃分結果，并計算AC和ARI值；

Step6令μ=2,3,…，重復上述步驟，并計算AC和ARI值。

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

圖2 Transfusion數據集不同μ值結果對比

圖3 Banknote數據集不同μ值結果對比

圖4 HTRU2數據集不同μ值結果對比

由圖2可知，當μ=3時，在Transfusion數據集上AC和ARI值最大，故在該數據集上μ取3較為合適。

由圖3可知，當μ=4時，在Banknote數據集上AC值最大，ARI值也最大，因此在Banknote數據集上μ取4較為合適。

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

3.3 算法比較

3.3.1真實數據集實驗

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

表2 真實數據集結果對比

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

3.3.2人工數據集實驗

本節選取表1中的8個Artificial data進行實驗，實驗對比結果如表3所示。

表3 Artificial data實驗結果對比

可以看出，在8個Artificial data上本文算法的AC值與K-means算法相差不大，這是因為本文抽取的樣本具有較好的代表性。在8個Artificial data數據集上本文算法運行的時間均少于K-means算法，Artificial data中instance越多，本文算法運行速度的優越性體現得越明顯，并且在數據集h增高時，本文算法運行時間遠快于K-means算法。

結合表2和表3中的數據對比，本文算法在較高維度數據集以及大樣本數據集上聚類效果優良并且算法運行時間較短。

4 結 語

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