可間斷運行的Ｋ－ｍｅａｎｓ聚類算法

摘 要：引入事務的恢復機制改進K-means算法，改進后的算法允許在運行過程中的任何時刻停機，重新啟動后可在停機前運算成果的基礎上繼續運算，直至算法結束。改進后的算法使得普通機器條件下針對大數據集運用K-means算法成為可能。改進后的算法在長達400 h的聚類運算中得到了檢驗。

關鍵詞：K-means算法; 聚類；恢復機制

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695(2009)06-2053-03

doi:10.3969/j.issn.1001-3695.2009.06.016

Recoverable implementation of K-means clustering algorithm

HUANG Zhi-hua1，2a，WEN Bu-ying2b ，WANG Guo-qian3

(1.School of Information Science Technology， Xiamen University， Xiamen Fujian 361005， China; 2.a.College of Mathematics Computer Science， b.College of Electrical Engineering Automation， Fuzhou University， Fuzhou 350108， China;3.Computing Center of Fujian Pro-vince， Fuzhou 350003， China)

Abstract:This paper improved K-means clustering algorithm by using transaction recovery mechanism.The new algorithm was able to resume itself without loss of computing time after the computer running， it was shut down on purpose or by chance at any time， so that it could achieve its goal in big data sets on ordinary computers. It was verified in a clustering task which spent as long as 400 hours.

Key words:K-means algorithm; clustering; recovery mechanism

1 聚類算法的研究與應用

聚類分析有著幾十年的研究歷史，眾多聚類算法相繼被提出。聚類已成為模式識別、數據挖掘等研究方向的重要研究內容，在識別數據的內在結構方面具有極其重要的作用。聚類分析在眾多應用領域發揮了重要作用。例如，在圖像處理中，聚類可被用于圖像分割，同時也是圖像特征提取的重要手段；聚類經常在各種應用領域中被用做數據壓縮或數據降維的手段。聚類還應用于統計科學，對生物學、心理學、考古學、地質學、地理學、市場營銷等研究都有重要作用^[1]。

文獻[1]把聚類算法分為層次聚類算法、劃分式聚類算法、基于密度和網格的聚類算法，以及其他聚類算法四種類型。層次聚類算法又稱為樹聚類算法，它使用數據的聯結規則，透過一種層次構架方式，反復將數據進行分裂和聚合，以形成一個層次序列的聚類問題解。劃分式聚類算法需要預先指定聚類數目或聚類中心，通過反復迭代運算，逐步降低目標函數的誤差值，當目標函數值收斂時，得到最終聚類結果，K-means聚類算法就是該類型中最具代表性的算法。基于網格和密度的聚類算法在以空間信息處理為代表的眾多領域中有著廣泛應用，它們通過數據密度，或使用網格，或兩者結合使用來發現類簇。其他聚類算法指近年來研究者提出的新穎的聚類算法，如采用具有不同偏好的蟻群系統來解決數據分類的問題。

聚類算法在得到廣泛應用的同時也面臨著一些問題。大多數聚類算法都需要預先給定參數，如果沒有相關知識和經驗，合理給出聚類算法的參數是不可能的。對于層次聚類算法，如何找到聚合或分裂過程的有效終止條件仍然是一個開問題。對于劃分式聚類算法，如何快速找到類的合理個數和較好的初始類中心點集仍然是很有價值的研究課題。聚類算法的聚類結果有一定的不可預見性，同一算法對不同的數據集聚類效果有差異，不同算法對同一數據集聚類效果也存在差異，即使同一聚類算法在同一數據集上也會因為相似性度量方式不同而產生

不同的聚類結果。

2 K-means聚類算法的問題

K-means聚類算法是一種劃分式聚類算法，由MacQueen于1967年首次提出。該算法是一個非常經典且被廣泛應用的聚類方法。其思想如下：在d維歐式空間中給定n個數據點組成的集合P，指定一個整數k，要求在d維空間中找到一個由k個點組成的集合，稱為centers，使得P中的每個點到離它最近的center之間的歐式距離的均值最小^[2]。解決K-means問題是非常困難的，針對該問題，目前未見有效的解決方案被提出。Lloyd的算法就是一個解決K-means問題的近似方法，通常所說的K-means聚類算法指的就是Lloyd的算法。該算法可描述如下：

a)隨機指定k個聚類中心C(c1，c2，…，ck);

b)對P中的每個點xi，找到離它最近的聚類中心cr，并將其分配到cr標注的類中，同時計算D=1/nni=1(minr=1，…，kd(xi，cr))，如果D值收斂，轉步驟e）；

c)將每個cr(r=1，2，…，k)更新為它所標注的類的中心；

d)轉步驟b）；

e)返回c1，c2，…，ck并終止本算法。

該算法描述簡單，易于實現，是最為廣泛應用的聚類算法之一。但是，該算法仍然存在三個較為突出的問題有待進一步研究改進。第一，對于一個給定的集合P，整數k指定為多少才是合理的；第二，該算法可能終止于D的一個局部極小值，而不是D的最小值；第三，該算法的計算代價非常大，需要耗費很長的計算時間，往往不可能在大數據集上運用該算法。針對第一個問題，文獻[3]進行了有益的研究，提出一種基于層次思想的計算方法。它首先掃描數據集獲得統計值，然后自底向上地生成不同層次的數據劃分，增量地構建一條關于不同層次劃分的聚類質量曲線，曲線極值點所對應的劃分用于估計最佳劃分數。

針對第二個問題，文獻[2，4]分別從不同的角度進行了研究。文獻[2]以交換centers為基礎提出了不同于Lloyd算法的求解K-means問題的近似算法；文獻[4]通過改變K-means聚類算法的步驟a），在該步驟中計算得到一個優質的聚類中心點集，以此點集作為初始中心點集啟動K-means聚類算法，從而使得K-means聚類算法能夠收斂到一個較好的局部極值。

針對第三個問題，文獻[5]提出了一種能夠降低計算代價的方法。K-means聚類算法的計算代價主要集中在步驟b）。文獻[5]提出了一種稱為k-d樹的數據結構來組織集合P，使得K-means聚類算法每次執行步驟b）時，不用計算P中每個點和centers中每個點的距離，減少了計算距離的計算量。文獻[6]對文獻[5]的方法進行了細小的改進，并通過深入分析和大量的實驗說明了該方法確實在一定的條件下能夠提高K-means聚類算法的運行效率。

K-d樹是一個二叉樹。該樹的根節點關聯著一個超立方體，該超立方體是能夠包含P中所有點的最小超立方體。K-d樹的每個非根節點也關聯著一個超立方體，該超立方體是其父節點所關聯的超立方體被一個超平面分割得到的，其父節點所關聯的超立方體被一個超平面分割成兩部分，一部分被左孩子節點繼承，另一部分被右孩子節點繼承。分割超平面可以由不同的方法來產生，一個簡單可行的方法是選擇與超立方體中所有點跨度最大的坐標軸正交且通過所有點在該坐標軸的中值的超平面。K-d樹的葉節點關聯的超立方體所包含的點數小于等于一個規定值，該規定值最小為1。K-d樹在每次聚類前被構建，聚類過程中沒有變化。這里將文獻[5，6]中的算法稱為高效K-means聚類算法。

高效K-means聚類算法如下：

a)隨機指定k個聚類中心C(c1，c2，…，ck)，針對集合P構建k-d樹，根節點為R;

b)調用filter(R，C)，同時計算D=1/nni=1(minr=1，…，kd(xi，cr))，如果D值收斂，轉步驟e）；

c)將每個cr(r=1，2，…，k)更新為它所標注的類的中心；

d)轉步驟b）;

e)返回c1，c2，…，ck并終止本算法。

其中:filter(R，C)是一個遞歸函數。先根遍歷R所標示的k-d樹，遍歷過程中把根節點與C關聯，其他節點首先從父節點繼承聚類中心集；然后根據該節點所關聯超立方體的幾何特性過濾掉部分聚類中心，剩下的聚類中心構成的集合就是此節點關聯的聚類中心集合。遍歷過程遇到葉節點或節點關聯的聚類中心集合僅包含一個聚類中心時，計算該節點所關聯超立方體中每個點與該節點所關聯聚類中心集合中每個聚類中心的距離，對于每個點都找到離它最近的聚類中心cr，并將其分配到cr標注的類中。Filter(R，C)的詳細表述參見文獻[6]。在為每個點尋找最近的聚類中心時，filter(R，C)避免了計算每個點與所有聚類中心間的距離，而只是計算每個點與可能的聚類中心間的距離，從而減少了計算距離的量。其代價是在聚類前需要構建k-d樹，在每次迭代時需要遍歷k-d樹并在遍歷的過程中過濾無關的聚類中心。總體而言，高效K-means聚類算法降低了K-means聚類的計算代價^[6]。

針對第三個問題，本文從另一個角度尋求解決方法。由于有時待聚類的數據集非常大，即使高效K-means聚類算法也要運行很長時間。普通的PC機通常難以承受過長時間的連續運行負載。當在普通的PC機上針對大數據集進行K-means聚類時經常會遇到死機、意外關機或因故需要關機等情況。當需要的運算時間很長時，幾乎每次啟動K-means聚類算法都會遇到這樣的情況。在這樣的背景下，K-means聚類算法在事實上是不可行的。本文引入事務的恢復機制改進K-means聚類算法，使得它在運行過程的任何時刻都可以停機，系統重啟后，可在停機前運算成果的基礎上繼續運行。改進后的算法不要求一次性完成K-means聚類計算，允許很長的聚類運算間斷地在普通的PC機上完成。

3 改進的K-means聚類算法

3.1 事務的恢復機制

事務是交給計算機的一組不可分割的操作序列，該組操作序列要么全部完成，要么全部沒有做。事務的概念出現在計算機的各個領域。例如，在數據庫領域，事務是數據庫系統處理數據的基本單位，操作系統通常用事務的方式實現刪除文件、移動文件等操作，較好的軟件安裝工具把軟件安裝過程組織成事務。事務的不可分割性也常被稱為原子性，是靠恢復機制來實現的。事務的恢復機制可簡單地概括為回滾和重做，如果系統在某一時刻崩潰，有的已完成事務的處理結果可能丟失，正在運行的事務只有部分操作被完成，系統重啟后，要重做那些丟失了結果的已完成事務，回滾當時正在運行的事務。重做和回滾都是依據日志來完成的，日志記錄著事務的每個操作信息，日志中的信息在每個事務的每個操作執行前被記入。

3.2 K-means聚類算法的恢復機制

為了讓K-means聚類算法可以間斷地運行，需要為K-means聚類算法建立一套恢復機制。無論K-means還是高效K-means聚類算法，都是迭代算法，每次迭代過程僅依賴于上一次迭代的結果。它們在運行過程的任何時刻停機，只要把停機時刻的上一次迭代結果作為聚類中心C的初值重新運行即可。參照事務的恢復機制，為K-means聚類算法增加一個運行日志文件，專門記錄以前迭代的結果。當K-means聚類算法在運行過程中停機后，可從日志文件中讀出上一次迭代的結果，以此作為聚類中心C的初值重新啟動K-means聚類算法。這樣，K-means聚類算法實際上就是在停機前運算成果的基礎上繼續運行。如果把每次迭代過程看成一個事務，上述效果相當于重做了已完成事務回滾的未完成事務。

為實現以上機制，K-means聚類算法的運行日志文件應能夠可靠地提供當前運行時刻的上一次迭代結果。在日志文件中保存以前每次迭代的結果可以達到此目標，但是，很顯然，保存以前每次迭代的結果沒有必要。在日志文件中僅保存上一次迭代結果不能確保可靠地提供當前運行時刻的上一次迭代結果。因為在這樣的情況下，每次向日志文件寫入上一次迭代結果必然覆蓋再上一次的迭代結果，該覆蓋也是一個需要經歷一定時間的過程，如果停機恰恰發生在這個過程中，日志中的信息將是混亂的，既不是上次迭代的結果也不是再上一次的迭代結果，這樣的信息對于恢復K-means聚類算法的運行是沒有意義的。

本文采用的方法是讓日志文件保存最近兩次的迭代結果，當向日志文件寫入新的迭代結果時覆蓋日志文件中較早的那次迭代結果。如果停機發生在覆蓋的過程中，當前迭代并未完成，日志中出現混亂的部分是較早的那次迭代結果，恢復運算所需要的較新的那一次迭代結果是完好的。日志文件的結構如圖1所示。其中：finish是一個長整數，記錄當前已完成的迭代次數，其初值為0；C1和C2用于保存最近兩次的迭代結果，其結構與聚類中心C(c1，c2，…，ck)一致，對于一個具體的聚類任務，C1和C2的結構及其大小都是固定不變的。

寫日志的過程可表述如下：

a)讀finish到cur；

b)i＝cur％2＋1；

c)將當前迭代得到的聚類中心集合C寫入Ci；

d)cur=cur+1；

e)將cur寫入finish，結束。

當需要依據日志恢復時，首先讀取finish，如果finish等于0，表明停機前并未成功完成一次迭代，不必恢復，直接重新啟動算法；否則，判斷finish為奇數還是偶數。若為奇數，讀取C1；若為偶數，讀取C2，將讀取的內容作為聚類中心集合C的初值來啟動算法，從而達到恢復運行的目的。

3.3 改進后的算法

本文將引入恢復機制的K-means聚類算法稱為可間斷運行的K-means聚類算法，它可被表述如下：

a)若為非恢復模式，隨機指定k個聚類中心C(c1，c2，…，ck)，并創建日志文件，賦值給finish為0，轉步驟d)，否則轉步驟b）;

b)若為恢復模式且finish為0，隨機指定k個聚類中心C(c1，c2，…，ck)，轉步驟d），否則轉步驟c）；

c)判斷finish為奇數還是偶數，若為奇數，讀取C1，若為偶數，讀取C2，將讀取的內容賦值給聚類中心C(c1，c2，…，ck)；

d)對P中的每個點xi，找到離它最近的聚類中心cr，并將其分配到cr標注的類中，同時計算D=1/nni=1(minr=1，…，kd(xi，cr))，如果D值收斂，轉步驟g），否則轉步驟e）；

e）將每個cr(r=1，2，…，k)更新為它所標注的類的中心，調用寫日志過程；

f)轉步驟d);

g)返回c1，c2，…，ck并終止本算法。

可間斷運行的K-means聚類算法有兩種運行模式，即非恢復模式和恢復模式。非恢復模式指該算法第一次運行一個聚類任務；恢復模式指該算法已運行過此聚類任務，此次運行是在上次運行的基礎上恢復運行，此次運行的模式作為該算法的參數由調用者指定。

高效K-means聚類算法也被改進為可恢復的形式，本文稱之為可間斷運行的高效K-means聚類算法。它可被表述如下:

a)若為非恢復模式，隨機指定k個聚類中心C(c1，c2，…，ck)，針對集合P構建k-d樹，根節點為R，并創建日志文件，賦值給finish為0，轉步驟d），否則轉步驟b）;

b)若為恢復模式且finish為0，隨機指定k個聚類中心C(c1，c2，…，ck)，轉步驟d），否則轉步驟c）；

c)判斷finish為奇數還是偶數，若為奇數，讀取C1，若為偶數，讀取C2，將讀取的內容賦值給聚類中心C(c1，c2，…，ck)；

d)調用filter(R，C)，同時計算D=1/nni=1(minr=1，…，kd(xi，cr))，如果D值收斂，轉步驟g），否則轉步驟e）；

e）將每個cr(r=1，2，…，k)更新為它所標注的類的中心，調用寫日志過程；

f)轉步驟d）;

g)返回c1，c2，…，ck并終止本算法。

4 實驗

可間斷運行K-means聚類算法在每次遇到停機時會丟失當前迭代運算的成果，恢復后以最近完成的迭代結果為基礎繼續運行，所以，該算法間斷運行完成所花費的總時間應比一次性完成所花費的時間多一點，但兩者的差別很小。本文的實驗為驗證這一點而設計。實驗在一臺普通的PC機上進行，該PC機的CPU為Intel Pentium D 2.66 GHz，內存為1 GB，運行的操作系統為Windows XP。在Visual Studio.NET 2003上用C++編程實現可間斷運行的K-means聚類算法。實現的程序針對三個不同的數據集分別以一次性完成和間斷運行完成兩種方式完成聚類任務，運行的情況如表1~3所示。表1~3所展現的實驗結果完全符合預期。

k個聚類中心C(c1，c2，…，ck)指定與一次性完成一樣的初值

間斷的情況運行過程中強行關機然后恢復運行6次，意外關機然后恢復運行1次程序在計算機上運行的總時間24.21 h間斷的情況運行過程中強行關機然后恢復運行3次，意外關機然后恢復運行4次程序在計算機上運行的總時間103.79 h

表4所展現的是可間斷運行K-means聚類算法在一個大數據集上運行的情況。該數據集較大，需要的計算時間很長，超過了普通PC機承受連續運算的能力，因此沒有一次性完成的情況。由于dataSet1~4是從相同的視頻流采集來的，只是數據的維數不同而已，根據dataSet1~3的運行情況，可以粗略地估計出可間斷運行K-means聚類算法在dataSet4上運算的時間為400多個小時。表4展現的情況與估計大體一致。可間斷運行K-means聚類算法在dataSet4上最終完成聚類運算，說明它的目標已完全達到。

算機上運行的總時間427.39 h

5 結束語

本文以聚類算法的研究與應用為背景，分析研究了K-means聚類算法的問題并將該算法的問題歸納為三個方面。針對第三方面的問題提出了自己的解決方案，即引入事務的恢復機制改進K-means聚類算法。改進后的算法在實驗中的運行情況完全符合預期，改進后的算法在總運行時間400多個小時的聚類任務中經受了考驗，使得在普通PC機上針對大數據集運用K-means聚類算法成為可能。

參考文獻：

［1］孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學報，2008，19(1):48-61.

［2］KANUNGO T，MOUNT D M，NETANYAHU N S，et al.A local search approximation algorithm for K-means clustering[J].Computational Geometry，2004，28(2-3):89-112.

［3］陳黎飛，姜青山，王聲瑞.基于層次劃分的最佳聚類數確定方法［J］.軟件學報，2008，19(1):62-72.

［4］BRADLEY P S，FAYYAD U M.Refining initial points for K-means clustering[C]//Proc of the 15th International Conference on Machine Learning.San Francisco:Morgan Kaufmann， 1998:91-99.

［5］ALSABTI K，RANKA S，SINGH V.An efficient K-means clustering algorithm[C]//Proc of the 1st Workshop on High Performance Data Mining.1998.

［6］KANUNGO T，MOUNT D M，NETANYAHU N S，et al.An efficient K-means clustering algorithm:analysis and implementation[J].IEEE Trans on Pattern Analysis and Machine Intelligence， 2002，24(7):881-892.