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

高亮謝健曹天澤

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

關鍵詞：kmeans算法；簇心；kd樹；剪枝策略；CKmeans算法

中圖分類號：TN914文獻標識碼：A

1引言

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

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

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

2Kmeans 算法

2.1Kmeans 算法簡介

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

計算技術與自動化2015年12月

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

2.2Kmeans 算法的優勢

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

2.3Kmeans 算法的不足

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

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

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

Kmeans算法隨機指定初始聚類中心，這給聚類結果帶來很大影響，聚類結果變得不穩定，有可能導致局部最優。

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

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

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

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

5）聚類過程時間消耗。

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

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

3KD樹

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

3.1Kd樹構造算法

Kd樹的構造是多次使用垂直于坐標軸的超平面分割k維空間實現的，所有的對象都組織到樹中，其中根節點代表所有的對象。

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

Kd樹的構造算法[7]如下：

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

輸出：包含所有數據對象的Kd樹根節點KD。

1）若數據對象集合X為空，返回空Kd樹；

2）調取節點判斷的函數，

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

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

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

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

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

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

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

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

輸出：最近鄰數據點。

1）若數據KD為Null，返回；

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

3）搜索到葉子節點，記為當前最近鄰Nearest；

4）回溯搜索：

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

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

4Ckmeans算法

本節內容為Ckmeans算法的詳細設計描述。

4.1Ckmeans 算法設計

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

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

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

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

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

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

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

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

輸出：滿足目標函數值QUOTE最小的k個聚類。

1）將樣本集合X構造Kd樹；

2）簇心初始化，在數據集d維中取一維排序成區間等間隔集，取k個初始簇心；

3）修剪節點對象的候選簇心集；

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

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

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

4.2Ckmeans 算法中剪枝策略

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

具體的剪枝策略如下：假設存在一個數據集合X，數據集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）}，對該數據集構建K-d樹結構如圖2所示：

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

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

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

5實驗結果及分析

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

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

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

1）在運行效率上，Ckmeans算法優于Kmeans算法，隨著數據集維度增加和聚類個數的增加，Ckmeans算法的優勢更加明顯。當數據集維度為10時，Ckmeans算法的運行時間相對于Kmeans算法的節省了2～3倍。

2）當數據集維度為2時，Ckmeans算法的運行效率優勢比較微弱，但在此數據規模下當聚類個數不斷增加，Pkmeans算法的運行效率優勢顯示出來。

6結論

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

參考文獻

[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.