K-means聚類算法研究綜述

王 千， 王 成， 馮振元，葉金鳳

（1.69026部隊 新疆 烏魯木齊 830002；2.西安交通大學(xué) 航天航空學(xué)院，陜西 西安 710049；3.中國建設(shè)銀行 蘇州常熟支行，江蘇 常熟 215500）

K-means聚類算法是由Steinhaus 1955年、Lloyd 1957年、Ball&Hall 1965年、McQueen 1967年分別在各自的不同的科學(xué)研究領(lǐng)域獨立的提出。K-means聚類算法被提出來后，在不同的學(xué)科領(lǐng)域被廣泛研究和應(yīng)用，并發(fā)展出大量不同的改進算法。雖然K-means聚類算法被提出已經(jīng)超過50年了，但目前仍然是應(yīng)用最廣泛的劃分聚類算法之一[1]。容易實施、簡單、高效、成功的應(yīng)用案例和經(jīng)驗是其仍然流行的主要原因。

文中總結(jié)評述了K-means聚類算法的研究現(xiàn)狀，指出K-means聚類算法是一個NP難優(yōu)化問題，無法獲得全局最優(yōu)。介紹了K-means聚類算法的目標(biāo)函數(shù)、算法流程，并列舉了一個實例，指出了數(shù)據(jù)子集的數(shù)目K、初始聚類中心選取、相似性度量和距離矩陣為K-means聚類算法的3個基本參數(shù)?？偨Y(jié)了K-means聚類算法存在的問題及其改進算法，指出了K-means聚類的進一步研究方向。

1 經(jīng)典K-means 聚類算法簡介

1.1 K-Means聚類算法的目標(biāo)函數(shù)

對于給定的一個包含 n個d維數(shù)據(jù)點的數(shù)據(jù)集X={x1，x2，…，xi，…，xn}，其中 xi∈Rd，以及要生成的數(shù)據(jù)子集的數(shù)目K，K-Means聚類算法將數(shù)據(jù)對象組織為K個劃分C={ck，i=1，2，…K}。每個劃分代表一個類ck，每個類ck有一個類別中心μi。選取歐氏距離作為相似性和距離判斷準(zhǔn)則，計算該類內(nèi)各點到聚類中心μi的距離平方和

顯然，根據(jù)最小二乘法和拉格朗日原理，聚類中心μk應(yīng)該取為類別ck類各數(shù)據(jù)點的平均值。

K-means聚類算法從一個初始的K類別劃分開始，然后將各數(shù)據(jù)點指派到各個類別中，以減小總的距離平方和。因為K-means聚類算法中總的距離平方和隨著類別個數(shù)K的增加而趨向于減?。ó?dāng) K=n時，J（C）=0）。因此，總的距離平方和只能在某個確定的類別個數(shù)K下，取得最小值。

1.2 K-means算法的算法流程

K-means算法是一個反復(fù)迭代過程，目的是使聚類域中所有的樣品到聚類中心距離的平方和J（C）最小，算法流程包括4個步驟[1]，具體流程圖如圖1所示。

圖1 K-means聚類算法流程圖Fig.1 Steps of K-means clustering algorithm

1.3 K-means聚類算法實例

圖2顯示的是K-means算法將一個2維數(shù)據(jù)集聚成3類的過程示意圖。

2 K-means聚類算法是一個NP難優(yōu)化問題

K-means聚類算法是一個NP難優(yōu)化問題嗎?在某個確定的類別個數(shù)K下，在多項式時間內(nèi)，最小的總距離平方和J（C）值和對應(yīng)的聚類劃分能否得到？目前，不同的學(xué)者有不同的答案。

Aristidis Likas等人[2]認為在多項式時間內(nèi)最小的值和對應(yīng)的聚類劃分能夠得到，并于2002年提出了全局最優(yōu)的K-means聚類算法。但給出的 “The global k-means clustering algorithm”只有初始聚類中心選取的算法步驟，而缺乏理論證明。 很快，pierre Hansen等人[3]就提出“The global k-means clustering algorithm”不過是一個啟發(fā)式增量算法，并不能保證得到全局最優(yōu)，文章最后還給出了反例。

圖2 K-means算法示意圖Fig.2 Illustration of K-means algorithm

很多學(xué)者指出，如果數(shù)據(jù)點的維數(shù)d=1，最小的總距離平方和J（C）值和對應(yīng)的聚類劃分能夠在O（Kn）2時間內(nèi)使用動態(tài)規(guī)劃獲得，例如Bellman and Dreyfus[4]。Pierre Hansen等人[3]認為，K-means聚類算法時間復(fù)雜度未知。

但是，更多的學(xué)者認為，對于一般的數(shù)據(jù)維數(shù)d和類別個數(shù)K，K-means聚類算法是一個NP難優(yōu)化問題[5]。Sanjoy Dasgupta等人認為即使在類別個數(shù)K=2的情況下，K-means聚類算法也是一個NP難優(yōu)化問題。Meena Mahajan等人[6]認為即使在數(shù)據(jù)點的維數(shù)d=2下，對于平面的K-means聚類問題，也是NP難的。本研究也認為，對于一般的數(shù)據(jù)維數(shù)d和類別個數(shù)K，K-means聚類算法是一個NP難優(yōu)化問題。K-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)，而不可能獲得全局最優(yōu)。

3 K-means聚類算法的參數(shù)及其改進

K-means聚類算法需要用戶指定3個參數(shù)：類別個數(shù)K，初始聚類中心、相似性和距離度量。針對這3個參數(shù)，K-means聚類算法出現(xiàn)了不同的改進和變種。

3.1 類別個數(shù)K

K-means聚類算法最被人所詬病的是類別個數(shù)K的選擇。因為缺少嚴(yán)格的數(shù)學(xué)準(zhǔn)則，學(xué)者們提出了大量的啟發(fā)式和貪婪準(zhǔn)則來選擇類別個數(shù)K。最有代表性的是，令K逐漸增加，如K=1，2，…，因為K-Means聚類算法中總的距離平方和J隨著類別個數(shù)K的增加而單調(diào)減少。最初由于K較小，類型的分裂（增加）會使J值迅速減小，但當(dāng)K增加到一定數(shù)值時，J值減小速度會減慢，直到當(dāng)K等于總樣本數(shù)N時，J=0，這時意味著每類樣本自成一類，每個樣本就是聚類中心。如圖3所示，曲線的拐點A對應(yīng)著接近最優(yōu)的K值，最優(yōu)K值是對J值減小量、計算量以及分類效果等進行權(quán)衡得出的結(jié)果。而在實際應(yīng)用中，經(jīng)常對同一數(shù)據(jù)集，取不同的K值，獨立運行K-means聚類算法，然后由領(lǐng)域?qū)＜疫x取最有意義的聚類劃分結(jié)果。

圖3 J-K關(guān)系曲線Fig.3 Relationship curve between J and K

并非所有的情況都容易找到J-K關(guān)系曲線的拐點，此時K值將無法確定。 對類別個數(shù)K的選擇改進的算法是Ball&Hall[7]于1965年提出的迭代自組織的數(shù)據(jù)分析算法（Iterative Self-organizing Data Analysis Techniques Algorithm，ISODATA），該算法在運算的過程中聚類中心的數(shù)目不是固定不變的，而是反復(fù)進行修改，以得到較合理的類別數(shù)K，這種修改通過模式類的合并和分裂來實現(xiàn)，合并與分裂在一組預(yù)先選定的參數(shù)指導(dǎo)下進行。

3.2 初始聚類中心的選取

越來越對的學(xué)者傾向于認為最小化總距離平方和J（C）值和對應(yīng)的聚類劃分是一個NP難優(yōu)化問題。因此，K-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)。而不同的初始聚類中心選取方法得到的最終局部最優(yōu)結(jié)果不同。因此，大量的初始聚類中心選取方案被提出。

經(jīng)典的K-means聚類算法的初始聚類中心是隨機選取的。Selim S Z，Al-Sultan K S于1991年提出的隨機重啟動K-means聚類算法是目前工程中應(yīng)用最廣泛的初始聚類中心選取方法，其過程如圖4所示。王成等人提出使用最大最小原則來選取初始聚類中心[8]，與其它方法不同的是，該過程是一個確定性過程。模擬退火、生物遺傳等優(yōu)化搜索算法也被用于K-means聚類算法初始聚類中心的選取。四種初始聚類中心選取方法的比較可見文獻[9]。自從Aristidis Likas等人[2]提出“The global k-means clustering algorithm”，對其的批評[3]、討論和改進就沒有停止過[10]。

圖4 多次重啟動K-means聚類算法流程圖Fig.4 Steps of multiple restarts K-means clustering algorithm

3.3 相似性度量和距離矩陣

K-means聚類算法使用歐式距離作為相似性度量和距離矩陣，計算各數(shù)據(jù)點到其類別中心的距離平方和。因此，K-means聚類算法劃分出來的類別都是類球形的。實際上，歐式距離是Minkowski距離在m=2時的特例，即L2距離。在采用Lm距離進行K-means聚類時，最終類中心應(yīng)是每一類的m中心向量。Kashima等人于2008年使用L1距離，最終聚類中心使每一類的中位向量。 對于一維數(shù)據(jù)集 X={x1，x2，…，xi，…，xn}而言，中位數(shù)M比均值xˉ對異常數(shù)據(jù)有較強的抗干擾性，聚類結(jié)果受數(shù)據(jù)中異常值的影響較小。Mao&Jain[11]于1996年提出使用Mahalanobis距離，但計算代價太大。在應(yīng)用中，Linde等.于 1980年提出使用Itakura-Saito距離。Banerjee等人2004年提出，如果使用Bregman差異作為距離度量，有許多突出優(yōu)點，如克服局部最優(yōu)、類別之間的線性分離、線性時間復(fù)雜度等。

4 K-means聚類算法的其他改進

在K-means聚類算法中，每個數(shù)據(jù)點都被唯一的劃分到一個類別中，這被稱為硬聚類算法，它不易處理聚類不是致密而是殼形的情形。模糊聚類算法能擺脫這些限制，這些方法是過去20年間集中研究的課題。在模糊方法中，數(shù)據(jù)點可以同時屬于多個聚類，Dunn等人[12]于1973年提出了模糊K-means聚類算法。

5 結(jié)束語

筆者也相信K-means聚類是一個NP難優(yōu)化問題，但這需要更加嚴(yán)格的數(shù)學(xué)理論證明。因此，K-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)，對K-means聚類算法的研究也將繼續(xù)。但是對K-means聚類算法的研究和改進應(yīng)注意以下幾點：

1）筆者感興趣的是現(xiàn)實世界問題的實際解決方案，模式分析算法必須能處理非常大的數(shù)據(jù)集。所以，只在小規(guī)模的例子上運行良好是不夠的；我們要求他的性能按比例延伸到大的數(shù)據(jù)集上，也就是高效算法（efficient algorithm）。

2）在現(xiàn)實生活應(yīng)用中數(shù)據(jù)里經(jīng)?；煊杏捎谌藶檎`差而引起的噪聲。我們要求算法能夠處理混有噪聲的數(shù)據(jù)，并識別近似模式。只要噪聲不過多地影響輸出，這些算法應(yīng)能容忍少量的噪聲，稱為算法的健壯性（robust）。相對于L2距離，L1距離有較強的健壯性。但相似性度量和距離矩陣的選取，不是一個理論問題，而是一個應(yīng)用問題，需要根據(jù)問題和應(yīng)用需要需求，假定合適的模型。例如，采用不同Lm的距離，K-means聚類的結(jié)果一般是不同的。

3）統(tǒng)計穩(wěn)定性即算法識別的模式確實是數(shù)據(jù)源的真實模式，而不只是出現(xiàn)在有限訓(xùn)練集內(nèi)的偶然關(guān)系。如果我們在來自同一數(shù)據(jù)源的新樣本上重新運行算法，它應(yīng)該識別出相似的模式，從這個意義上講，可以把這個性質(zhì)看作輸出在統(tǒng)計上的健壯性。樣本讀入次序不同，一些聚類算法獲得的模式完全不同，而另一些聚類算法對樣本讀入次序不敏感。從這個角度來講，最大最小原則比隨機重啟動、模擬退火、生物遺傳在初始聚類中心選取上要好。

4）K-means聚類算法的很多變種引入了許多由用戶指定的新參數(shù)，對這些參數(shù)又如何自動尋優(yōu)確定，是一個不斷深入和發(fā)展的過程。

5）K-means還存在一個類別自動合并問題[1]，在聚類過程中產(chǎn)生某一類中無對象的情況，使得得到的類別數(shù)少于用戶指定的類別數(shù)，從而產(chǎn)生錯誤，能影響分類結(jié)果。其原因需要在理論上深入探討，但這方面的論文和研究很少。聚類的意義，這也是所有的聚類算法都面臨的問題，需要在數(shù)學(xué)理論和應(yīng)用兩方面開展研究。

[1]Anil K J.Data clustering:50 years beyond K-Means[J].Pattern Recognition Letters，2010，31（8）：651-666.

[2]Likas A，Vlassis M，Verbeek J.The global K-means clustering algorithm[J].Pattern Recognition，2003，36（2）:451-461.

[3]Selim S Z，Al-Sultan K S.Analysis of global K-means，an incremental heuristic for minimum sum-of-squares clustering[J].Journal of Classification，2005（22）:287-310.

[4]Bellman R，Dreyfus S.Applied dynamic programming[M].New Jersey：Princeton University Press，1962.

[5]Aloise D，Deshpande A，Hansen P，et al.NP-hardness of euclidean sum-of-squares clustering[J].Machine Learning，2009，75（2）：245-248.

[6]Mahajan M，Nimbor P，Varadarajan K.The planar K-means problem is NP-hard[J].Lecture Notes in Computer Science，2009（5431）：274-285.

[7]Ball G，Hall D.ISODATA，a novel method of data analysis and pattern classification[M].California：Technical rept.NTIS AD 699616.Stanford Research Institute，1965.

[8]WANG Cheng，LI Jiao-jiao，BAI Jun-qing，et al.Max-Min K-means Clustering Algorithm and Application in Post-processing of Scientific Computing[C]//Napoli：ISEM，2011：7-9.

[9]Pena J M，Lozano J A，Larranaga P.An empirical comparison of four initialization methods for the K-means algorithm[J].Pattern Recognition Letters，1999（20）：1027-1040.

[10]Lai J Z C，Tsung-Jen H.Fast global K-means clustering using cluster membership and inequality[J].Pattern Recognition，2010（43）：1954-1963.

[11]Mao J，Jain A K.A self-organizing network for hyperellipsoidal clustering（hec）[J].IEEE Transactions on neural networks，1996（7）：16-29.

[12]Dunn J C.A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters[J].Journal of Cybernetics，1973（3）：32-57.