基于Kd樹改進的高效K—means聚類算法

高亮謝健曹天澤

摘要：針對經(jīng)典的Kmeans算法在多維數(shù)據(jù)聚類效率上還有待提高的問題，本文提出一種稱為CKmeans的改進聚類算法。該算法在kmeans算法的基礎(chǔ)上，通過引入Kd樹空間數(shù)據(jù)結(jié)構(gòu)，初始聚類中心從多維數(shù)據(jù)某一維的區(qū)間等間隔集中選取，以及在數(shù)據(jù)對象分配過程中采用剪枝策略來提高算法的運行效率。實驗結(jié)果表明，CKmeans聚類算法較經(jīng)典的kmeans聚類算法運行效率更高。

關(guān)鍵詞：kmeans算法；簇心；kd樹；剪枝策略；CKmeans算法

中圖分類號：TN914文獻標(biāo)識碼：A

1引言

數(shù)據(jù)挖掘是一種經(jīng)典有效的數(shù)據(jù)分析方法，聚類分析是數(shù)據(jù)挖掘中的重要研究內(nèi)容。數(shù)據(jù)對象通過聚類分析，可以形成簇或者類內(nèi)部數(shù)據(jù)對象相似度高且不同簇之間的數(shù)據(jù)對象相似度低的簇組。目前主要的聚類方法有：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法[1]。kmeans算法是一種傳統(tǒng)的聚類算法，其算法易于實現(xiàn)、時間復(fù)雜度小和可以處理大型數(shù)據(jù)集等優(yōu)勢明顯。

Kmeans算法作為一種常用的聚類算法，在處理多維和海量數(shù)據(jù)時，由于需要提前給定簇的個數(shù)，聚類結(jié)果隨初始質(zhì)心變化的波動大，重新計算質(zhì)心時受到孤立點影響，而且僅適用于類簇之間區(qū)別較大的情況，同時聚類過程時間消耗過長，因此提高該算法的執(zhí)行效率。

在文獻[2]中，李濤等提出了一種引入競爭策略的聚類算法。受文獻[2]、[3]的影響，本文提出一種kmeans算法的改進算法稱為Ckmeans算法。該算法從多維數(shù)據(jù)中隨機選取某一維數(shù)值并均分為k個數(shù)值域。初始聚類中心從k個數(shù)值域中選取，以減少迭代次數(shù)來提高算法效率。引入了K-d樹，對樣本點的數(shù)據(jù)結(jié)構(gòu)進行標(biāo)準(zhǔn)化，從而便于節(jié)點的遍歷和查詢。同時，該算法采用了剪枝的策略，減少參與計算節(jié)點和候選聚類簇心之間歐式距離的計算量，從而能夠明顯地降低算法時間復(fù)雜度。在剪枝時，計算最小距離時利用k-d樹最近鄰查詢算法，計算最大距離時利用數(shù)據(jù)節(jié)點代表的空間范圍最大值，從而大大提高了剪枝策略的有效性。通過對傳統(tǒng)的kmeans聚類算法進行此方法的改進，進而提高了算法的運行效率。

2Kmeans 算法

2.1Kmeans 算法簡介

Kmeans算法是一種基于劃分的傳統(tǒng)聚類方法，該算法的基本思想是：在n個數(shù)據(jù)對象中，首先隨機初始化k個簇心，每個點分派給最近的簇心，分派到同一個簇心的所有數(shù)據(jù)對象的集合構(gòu)成一個簇，接著根據(jù)分派到簇的點，更新每個簇的簇心，重復(fù)分派和更新簇心過程，直到簇的簇心不發(fā)生變化，最終得到目標(biāo)函數(shù)最小的k個類。

計算技術(shù)與自動化2015年12月

第34卷第4期高亮等：基于Kd樹改進的高效Kmeans聚類算法

2.2Kmeans 算法的優(yōu)勢

Kmeans算法是一種高效的聚類算法，在科學(xué)研究和工程應(yīng)用中得到了應(yīng)用和推廣，它的算法流程比較簡單，并且收斂速度很快，對于大數(shù)據(jù)集也有較好的分類效果，其時間復(fù)雜度為O（tkdn）， t是迭代次數(shù)，k是簇類的個數(shù)，d是數(shù)據(jù)集的維數(shù)，n是樣本點數(shù)。在對大型數(shù)據(jù)集聚類時，Kmeans算法比層次聚類算法快得多[4]。

2.3Kmeans 算法的不足

1）必須提前給定要形成的聚類個數(shù)k。

Kmeans算法必須提前給定要形成的聚類個數(shù)k，聚類的結(jié)果對此有很大的依賴性，然而通常最恰當(dāng)劃分?jǐn)?shù)據(jù)集的聚類的個數(shù)并不是事先可知的，一般需要通過多次反復(fù)試驗才能得到該聚類個數(shù)，因此在算法的開始就指定聚類個數(shù)會影響聚類過程和結(jié)果是很明顯的。

2）聚類結(jié)果隨初始聚類中心變化的波動大。

Kmeans算法隨機指定初始聚類中心，這給聚類結(jié)果帶來很大影響，聚類結(jié)果變得不穩(wěn)定，有可能導(dǎo)致局部最優(yōu)。

3）重新計算質(zhì)心時受到孤立點影響。

在聚類的迭代過程中，要重新計算以形成新的質(zhì)心，但是與類簇距離明顯的孤立點導(dǎo)致計算的質(zhì)心也偏離真正的數(shù)據(jù)密集區(qū)，質(zhì)心的代表性下降，新的聚類過程受到孤立點的影響大。

4）僅適用于類簇之間區(qū)別較大的情況。

由于Kmeans算法根據(jù)歐式距離度量各個點之間的距離，并且聚類準(zhǔn)則函數(shù)使用偏差和準(zhǔn)則函數(shù)，聚類過程參考該準(zhǔn)則函數(shù)。只有當(dāng)類簇之間區(qū)別明顯是，聚類才會有效，否則可能導(dǎo)致聚類的過程反復(fù)不定，不斷將形成的類簇分割的情況。

5）聚類過程時間消耗。

Kmeans算法的聚類是一個不斷的迭代的過程。一旦形成類簇，就重新計算質(zhì)心，然后重新計算距離并指派，當(dāng)解決大數(shù)據(jù)量的問題時，算法的聚類過程會消耗大量的時間。

本文針對Kmeans算法對海量數(shù)據(jù)和多維數(shù)據(jù)運算速度慢，時間消耗大的缺陷，提出改進算法CKmeans，以期提高算法的運算效率。

3KD樹

Kd樹（多維二叉搜索樹）是由Bentley于1975年提出[5]，k是空間數(shù)據(jù)對象的維度數(shù)，在多維的空間數(shù)據(jù)結(jié)構(gòu)中，Kd樹常用來數(shù)據(jù)索引和數(shù)據(jù)查詢。kd樹通過把一個空間劃分成多個不相交的子空間來進行高效的組織k維空間中點的集合。kd樹中內(nèi)部節(jié)點對象包含有某一維的區(qū)分值，其中小于或等于區(qū)分值的點劃分到左子樹，大于區(qū)分值的點劃分到右子樹。Kd樹本質(zhì)上是一種二元搜索樹，它用超平面把一個空間劃分成若干子空間來對數(shù)據(jù)搜索，可以快速而準(zhǔn)確地找到某一點的最近鄰。

3.1Kd樹構(gòu)造算法

Kd樹的構(gòu)造是多次使用垂直于坐標(biāo)軸的超平面分割k維空間實現(xiàn)的，所有的對象都組織到樹中，其中根節(jié)點代表所有的對象。

在Kd樹的構(gòu)造中，一方面考慮在數(shù)據(jù)對象維度進行分割時，選擇基于順序循環(huán)分割或者基于維的長度優(yōu)先分割；另一方面考慮分割點的判斷，選擇基于中點的方法或者基于中值點的方法。在文獻[6]中的研究表明，這兩個因素的選擇分別為從最長的維度開始分割和選擇中點的方法較好，本文采用上述方法。Kd樹構(gòu)造是多次遞歸地調(diào)用Kd樹構(gòu)造函數(shù)實現(xiàn)的，Kd樹構(gòu)造算法的時間復(fù)雜是O（nlogn）。

Kd樹的構(gòu)造算法[7]如下：

輸入：維度為d的數(shù)據(jù)對象集合X和Kd樹的深度Depth；

輸出：包含所有數(shù)據(jù)對象的Kd樹根節(jié)點KD。

1）若數(shù)據(jù)對象集合X為空，返回空Kd樹；

2）調(diào)取節(jié)點判斷的函數(shù)，

（1）計算數(shù)據(jù)對象每一維數(shù)值的方差值，分割維Split的順序按方差大小來判斷，

（2）取每一維的中點值作為分割點MidPoint；

3）在Split維時分割點MidPoint劃分?jǐn)?shù)據(jù)集合，得到子集合X1和X2，X1：在Split維的數(shù)據(jù)對象都小于或等于MidPoint，X2：在Split維的數(shù)據(jù)對象都大于MidPoint；

4）Lchild為KD的左子節(jié)點，Rchild為KD的右子節(jié)點，Lchild=KdConstruct（X1，Depth+1），Rchild=KdConstruct（X2， Depth +1），遞歸地調(diào)用直到子節(jié)點為葉子節(jié)點；

5）把Lchild和Rchild 合并為Node，返回Node。

3.2Kd樹上的最鄰近查找算法

Kd樹是一種很好尋找最近鄰問題的數(shù)據(jù)結(jié)構(gòu)，Kd樹的查找有最近鄰搜索和范圍搜索兩種基本方式。Kd樹上的最鄰近查找算法即在Kd樹中檢索與某一查詢點歐式距離最近的數(shù)據(jù)點[8-9]。kd樹最近鄰查找算法描述如下：

輸入：Kd樹類型的KD和查找對象Object；

輸出：最近鄰數(shù)據(jù)點。

1）若數(shù)據(jù)KD為Null，返回；

2）從根節(jié)點遞歸地向下搜索，進行二叉搜索；

3）搜索到葉子節(jié)點，記為當(dāng)前最近鄰Nearest；

4）回溯搜索：

if 超球與父節(jié)點超平面相交，進入相反的空間搜索，更新Nearest，else繼續(xù)向上回溯，父節(jié)點相反的空間不查找；

5）回溯到根節(jié)點，結(jié)束并返回最近鄰。

4Ckmeans算法

本節(jié)內(nèi)容為Ckmeans算法的詳細(xì)設(shè)計描述。

4.1Ckmeans 算法設(shè)計

在改進Kmeans算法過程中，通過對Kmeans算法運行時間進行分析來提出改進，提高算法的運行效率。設(shè)初始簇心時間為Tinit，分派樣本點時間Tassign，重新計算簇心時間為Tagain，Kmeans算法迭代次數(shù)為t，Kmeans算法的運行時間Tsum。則有以下算法的運行公式：

Tsum=Tinit+tx（Tassign+Tagain）…（1）

由公式（1）可知，若要提高算法的運行效率，可以通過減少算法的迭代次數(shù)和指派時間來實現(xiàn)。

對于d維數(shù)據(jù)集X，在d維選取其中的一維數(shù)值，對該維數(shù)值進行排序，則存在一個對應(yīng)的區(qū)間[m，n]，給定一個整數(shù)常量k，把區(qū)間[m，n]分成k個子區(qū)間，子區(qū)間長度是相同的，則規(guī)定C={C1，C2，...，Ck-1}為區(qū)間等間隔集，當(dāng)i=1時，C1=（m-n）/k；當(dāng)i=2，3，…，k-1時，Ci=Ci-1+C1。pkmeans算法的k個初始簇心分別從C（k等分）的每一個子區(qū)間中選取。通過對kmeans算法選取初始簇心的隨機性進行改進，達到減少迭代次數(shù)來提高Ckmeans算法運行效率的目的。

在Kmeans算法分配數(shù)據(jù)樣本點的過程中，需要保證數(shù)據(jù)集X中的樣本點被指派給最近的簇心，當(dāng)所有樣本點分配結(jié)束之后，重新計算簇心。Kmeans算法對于X中的樣本點，需要計算其與所有簇心的距離，然后找到最近距離的簇心。

在Ckmeans算法中，通過引入Kd樹，使得樣本點數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)化，便于遍歷和查詢。通過采用剪枝策略，減少了要參與計算的點和候選簇心的歐式距離計算量，可以顯著的減少算法的時間復(fù)雜性。剪枝策略：首先搜索候選簇心集中的每個簇心到該節(jié)點對象所代表的空間區(qū)域的最近鄰距離MinDis，最小距離采用Kd樹最近鄰查詢算法獲取，然后把該節(jié)點對象所代表的空間區(qū)域的最大距離記作MaxDis，最大距離采用節(jié)點所代表的空間范圍的最大值，最后把最近鄰距離大于最大距離的最小者的簇心剪去。

Ckmean算法的基本思想是：將數(shù)據(jù)集初始成Kd樹，從d維數(shù)據(jù)集X中選取一維數(shù)值，排序后形成區(qū)間等間隔集，得到算法的初始簇心集。從初始化后的Kd樹的根節(jié)點對象開始，根據(jù)最小距離最大距離原則剪枝，根節(jié)點對象于全部候選簇心集計算歐式距離，而子節(jié)點只從父節(jié)點的候選簇心集剪枝。分配數(shù)據(jù)對象后，再次計算簇心，直到目標(biāo)函數(shù)值收斂。如圖1所示，Ckmeans算法可以描述：

輸入：聚類個數(shù)k以及包含d維的n個數(shù)據(jù)對象數(shù)據(jù)集X；

輸出：滿足目標(biāo)函數(shù)值QUOTE最小的k個聚類。

1）將樣本集合X構(gòu)造Kd樹；

2）簇心初始化，在數(shù)據(jù)集d維中取一維排序成區(qū)間等間隔集，取k個初始簇心；

3）修剪節(jié)點對象的候選簇心集；

4）計算節(jié)點對象到修剪后的候選簇心的距離并當(dāng)距離最小時把對象Xi分配給簇Cj；

5）重新計算：重新計算與簇心；

6）重復(fù)步驟3）和4），直到值收斂。

4.2Ckmeans 算法中剪枝策略

剪枝原則如下：首先搜索候選簇心集中的每個質(zhì)心到該節(jié)點對象所代表的空間區(qū)域的最近鄰距離MinDis，然后把該節(jié)點對象所代表的空間區(qū)域的最大距離記作MaxDis（在構(gòu)造kd樹的過程中形成的數(shù)據(jù)結(jié)構(gòu)），最后把最近鄰距離大于最大距離的最小者的質(zhì)心剪去。

具體的剪枝策略如下：假設(shè)存在一個數(shù)據(jù)集合X，數(shù)據(jù)集X為{（3.5，4），（1.5，5.5），（5.5，2），（1，3），（2.5，7），（4.5，0.5），（6.5，7.5），（2，2.5），（8.5，5）}，對該數(shù)據(jù)集構(gòu)建K-d樹結(jié)構(gòu)如圖2所示：

已經(jīng)選擇的候選簇心集為：{（9.5，9.5），（9.7，1.5），（4，5.5），（1.5，9.5），（2，4）}，根節(jié)點為O1（3.5，4.0），候選簇心集為{ X1，X2，X3，X4，X5}，該點被指派給質(zhì)心：X3；根節(jié)點的左葉子節(jié)點O2（1.5，5.5），所代表的空間范圍為（1，2.5）和（3.5，7）所包圍的矩形，父節(jié)點的候選簇心的個數(shù)為：5，即{ X1，X2，X3，X4，X5}，針對5個候選簇心有如表1的計算結(jié)果。

如表所示，其中最大距離中的最小者為6.3246。將最近鄰距離大于最大距離的最小者的質(zhì)心剪去后，只剩下3個質(zhì)心，即{X3，X4，X5}。則針對左葉子節(jié)點O2（1.5，5.5）的候選簇心集為：{X3，X4，X5}，該點被指派給質(zhì)心：X5。對于各個候選簇心與該節(jié)點對象的最近距離與最遠(yuǎn)距離表示如圖3所示。以此類推，對節(jié)點O2（1.5，5.5）的左葉子節(jié)點O8（2，2.5）也進行剪枝，其中參與剪枝的候選簇心集合只從其父節(jié)點的候選簇心集合中選取，結(jié)果是{X3，X4，X5}，在剪枝工作之后的候選簇心集合是{X3，X5}。對于其他的節(jié)點對象也采取相同的操作策略，對數(shù)據(jù)集合所構(gòu)建的k-d樹的左子樹上的各個節(jié)點，在采取了剪枝操作之后，相應(yīng)的候選簇心情況如圖4所示。

從圖4中我們可以看到，在經(jīng)過了剪枝操作之后，每個節(jié)點都擁有相應(yīng)的候選簇心集合，并且這個候選簇心集合中質(zhì)心的個數(shù)明顯少于初始的整體簇心集合，如此就能減少節(jié)點與質(zhì)心之間歐式距離的計算量，從而有效地減少運算時間，提高了運算的效率。

5實驗結(jié)果及分析

在試驗中，算法的程序用Java語言實現(xiàn)，編譯環(huán)境為Eclipse。實驗的計算機環(huán)境為： Intel（R） Core（TM） i3-2120 CPU，3.30 GHz，2.85G內(nèi)存，操作系統(tǒng)為windows XP Sp3。

本文用到的測試數(shù)據(jù)集來源于文獻[10]中，并沒有數(shù)據(jù)集進行任何特殊的優(yōu)化。為了體現(xiàn)算法對不同數(shù)據(jù)規(guī)模體現(xiàn)的效率，選用2個測試數(shù)據(jù)集對Kmeans和Ckmeans進行實驗，分別是data[1024，2]和data[1024，10]。data[1024，2]數(shù)據(jù)集表示由1024個數(shù)據(jù)點和2維屬性構(gòu)成，data[1024，10]類同。在這2個數(shù)據(jù)集上對k=20、30、40、50、60、70、80、90分別進行測試。針對每種情況進行20次試驗。

實驗結(jié)果如下圖5和圖6所示。由實驗結(jié)果分析可知：與Kmeans算法相比，Ckmeans算法在精度上與其近似，但是Ckmeans算法在運行效率上明顯優(yōu)于Kmeans算法。

1）在運行效率上，Ckmeans算法優(yōu)于Kmeans算法，隨著數(shù)據(jù)集維度增加和聚類個數(shù)的增加，Ckmeans算法的優(yōu)勢更加明顯。當(dāng)數(shù)據(jù)集維度為10時，Ckmeans算法的運行時間相對于Kmeans算法的節(jié)省了2～3倍。

2）當(dāng)數(shù)據(jù)集維度為2時，Ckmeans算法的運行效率優(yōu)勢比較微弱，但在此數(shù)據(jù)規(guī)模下當(dāng)聚類個數(shù)不斷增加，Pkmeans算法的運行效率優(yōu)勢顯示出來。

6結(jié)論

通過對經(jīng)典Kmeans的分析和研究，為了提高算法的運行效率，對Kmeans算法進行改進。改進的算法優(yōu)化了傳統(tǒng)隨機選取簇心的初始化方法，提出了基于Kd樹和剪枝策略的Ckmeans算法。經(jīng)過實驗結(jié)果比較，改進后的算法與原有算法具有相似的精度，但是改進后的算法的運行效率明顯提高，尤其是對于高維數(shù)據(jù)效果更明顯。把它應(yīng)用在農(nóng)業(yè)氣象災(zāi)害區(qū)劃系統(tǒng)之中，對于提高氣候區(qū)劃的精度，以及系統(tǒng)的反應(yīng)速度都有著比較好的參考價值和意義，同時對滿足其他科學(xué)的研究和工程應(yīng)用需求也提供了非常良好的借鑒作用。然而，這僅僅是在數(shù)值計算領(lǐng)域得到了驗證，如何將其應(yīng)用于非數(shù)值數(shù)據(jù)的聚類分析與計算中，仍然是今后的研究方向。

參考文獻

[1]WANG Qian，WANG Cheng.Review of Kmeans clustering algorithm[J].Electronic Design Engineering，2012.

[2]Tao Li，Shuren Bai，Jinyang Ning.An improved Kmeans Algorithm Based on Competitive Strategy[J].In： International Conference on Information and Multimedia Technology.Hong Kong：IEEE Computer Society，2010，2：76-80

[3]ZHAI Dong-hai，YU Jiang，GAO Fei.K-means text clustering algorithm based on initial cluster centers selection according to maximum distance[J].Application Research of Computers.2014.

[4]HUANG Z.A fast clustering algorithm to cluster very large categorical data sets in data mining. In： Tucson： the SIGMOD Workshop on Research Issues on Data Mining and knowledge Discovery.Tuncson， 1997， 146～151

[5]BENTLEY J.Multidimensional binary search trees used for associative searching[J].Journal of Communications of the ACM， Vol.18， No.9： 509- 517，1975.

[6]Jiang Xiaoping，Li chenghua.Parallel implementing kmeans clustering algorithm using MapReaduce programming mode[J].J.Huazhong Univ.of.Sci&Tech.（Matural Science Edition）.2011

[7]Chen Xiaokang，Liu Zhusong.K Nearest Neighbor Query Based on Improved KdTree Construction Algorithm[J].Journal of Guangdong University of Technology.2014

[8]MOORE A W. An introductory tutorial on kdtrees[D]. Extract from Andrew Moore's PhD Thesis： Efficient Memorybased Learning for Robot Control Technical Report No. 209.1991

[9]STEPHEN J.Redmond，Conor Heneghan.Method for Initializing the Kmeans Clustering Algorithm Using Kdtrees[J]. Pattern Recognition Letters， 2007，28（8）：965-973.

[10]HAN Lingbo.A new method of determining optimal number of clusters Kmeans[J].Modern Compute.2013，20：46-50.