摘 要： 對傳統的K-平均算法作了簡單的介紹和討論，提出了一種具有單純型法思想的K-中心點輪換法。分別對比了K-均值算法與K-中心點輪換算法的時間復雜度，針對K-中心點輪換算法的時間復雜度提出了一種基于抽樣原理的改進算法，并對K-中心點輪換算法聚類數目的選擇進行了各種改進方法的探索。同時，基于主流的weka開源數據挖掘工具實現了改進算法。實驗結果表明了算法的有效性。
關鍵詞： K-均值；K-中心點輪換；抽樣；聚類數目；weka
作為統計學的一個分支，聚類分析已經被研究了許多年[1-5]，但主要集中在基于距離的聚類分析上。在機器學習領域，聚類是無指導學習的一個例子。與分類不同，聚類不依賴于預先定義的類和帶標號的訓練實例，可見，聚類是觀察式學習，而不是示例式學習[1]。在概念聚類中，一組點只有當它們可以被一個概念描述時才形成一個簇。這不同于基于幾何距離來度量相似度的傳統聚類。目前在文獻中存在著大量的聚類算法，算法的選擇取決于數據集的類型、聚類的目的和應用。如果聚類分析被用作描述或探查的工具，可以對同樣的數據集嘗試多種算法，以發現數據集可能揭示的結果。
1 基于劃分的聚類分析算法及改進
聚類分析，一般認為就是試圖發現數據點集中內在的結構，使同一簇內的數據點相似度高，不同簇之間的數據點相異度高[3]。由于相似度、相異度的定義往往根據具體情況而定，而且什么是最好的聚類結果，往往也與具體問題、具體要求有關。將聚類問題轉化為一種優化問題，再通過數學規劃的方法來進行求解是研究聚類分析的一個重要方向。
給定n個對象或者數據元組的數據庫，應用劃分方法構建數據的k個劃分，每個劃分表示一簇，k≤n。也就是說，將數據劃分為k組，并滿足如下要求：(1)每一組至少包含一個對象；(2)每個對象必須只屬于一組。
給定要構建的劃分數目k，應用劃分方法創建一個初始劃分。然后采用迭代重定位技術，嘗試通過對象在組間移動來改進劃分。
設在m維歐氏空間中有n個點，在這個空間中的某個范圍內選取k個中心位置mi(i=1，2，…，k)，使得這n個點到各自最近的中心位置的距離平方之和最小。這是最初的一種優化目標函數。
1.1 傳統的K-均值算法[1]
K-均值算法(K-means)是最基本的聚類分析算法，以k為參數，把n個對象分為k個簇，以使簇內具有較高的相似度，而簇間的相似度較低。相似度的計算根據一個簇中點的平均值(被看作簇的重心)來進行。K-means聚類算法的描述和處理流程[1-2]如下：
K-means是用于劃分的K-均值算法，每個簇的中點用簇中對象的均值表示。其輸入為簇的數目k和包含n個對象的數據集，輸出為k個簇的集合。
算法流程：
(1)從D中隨機選擇k個對象，每個對象初始地代表一個簇的平均值或質心；
(2)repeat；
(3)根據簇中對象的均值，將每個對象（重新）指派給最相似的簇；
(4)更新每個簇的平均值，即計算每個簇中點的均值；
(5)直到準則函數收斂。
1.2 K-means算法的不足
K-means算法有以下不足：(1)算法對初始值的選取依賴性極大。初始值不同，往往得到不同的局部極小值。(2)由于將均值點作為聚類中心進行新一輪計算，遠離數據密集區的孤立點和噪聲點會導致聚類中心偏離真正的數據密集區，所以K-均值算法對噪聲點和孤立點很敏感。
1.3 K-中心點輪換算法
K-平均算法在計算簇內平均值時很容易被“噪聲”和孤立點所影響。為了改進這個缺點，可以采用用簇中位置最中心的點（中心點）來取代K-平均算法中簇中點的平均值。這種劃分方法仍然是基于最小化所有點與其參照點之間的相異度(如常采用歐氏距離來度量)之和的原則來執行的。
K-中心點輪換算法(K-mediods)是以k為輸入參數，試圖以窮舉的方式重復地使用目標函數值更小的對象來代替當前的中心點，從而將n個對象分為k個簇。具體的算法過程描述如下：對基于中心點的劃分的一種K-中心點變種算法，其輸入為結果簇的數目k、包含n個對象的數據集；輸出為k個簇，使得所有對象與其最近中心點的偏差準則函數最小。
K-mediods算法流程如下：
(1)隨機選擇k個對象，每個對象初始地代表了一個簇的中心點，這k個對象就組成了當前的中心點集；
(2)repeat；
(3)將每個對象（重新）指派給離它最近的中心點所代表的簇，按照式(1)計算當前的目標函數值；
(4)對n個對象中的每一個對象Oj（j=1，2，…，n）依次執行下面的過程：試圖用當前對象Oj去依次替換現有的k個中心點中的每一個中心點mi（i=1，2，…，k），并計算試圖替換后的目標函數值，最終選擇替換后能獲得目標函數值最小的那個中心點進行替換。如果這k個待替換的中心點所對應的目標函數值比當前的目標函數值還要大，則不進行替換；
(5)直到不發生變化；
(6)最終得到一個中心點集，根據這個集合，按照最近鄰原則分配所有對象到它所歸屬的簇中，得到的k個簇就是所有對象的一個局部優化聚類結果。
1.4 算法對比分析
1.4.1 K-means算法性能
K-均值算法在步驟(3)和步驟(4)之間交互迭代，每一步都使目標函數逐步下降，從而產生一個使目標函數值逐步減小的迭代序列，它嘗試找出使目標函數值取得最小的一個k劃分，但通常只能獲得一個局部優化結果。算法的復雜度是O(nkt)，其中，n是所有點的數目，k是簇的數目，t是迭代的次數。
1.4.2 K-mediods算法性能
從算法的過程描述，可以看出該算法是一種單純型思想的算法，它以犧牲時間復雜度來獲取更好的聚類效果，下面簡單分析一下該算法的時間復雜度。
該算法由于要用到所有對象的距離度量矩陣，其時間復雜度是O(n2)。算法步驟(3)中將n個對象賦給k個中心點所代表的簇，需要時間復雜度為O(nk)；計算目標函數值需要時間復雜度為O(n)；算法步驟(4)中在每一次試圖替換中心點后都需要重新將所有點賦給新的中心點所代表的簇并計算新的目標函數值以供比較，所以這一步的時間復雜度是O(n2k2)。
1.4.3 K-mediods算法優缺點
K-中心點輪換算法是一種使目標函數下降最快的方法，它屬于啟發式搜索算法，能從n個對象中找出以k個中心點為代表的一個局部優化劃分聚類。與K-均值算法比較，K-中心點輪換算法解決了K-均值算法本身的缺陷：
(1)解決了K-均值算法對初始值選擇依賴度大的問題。K-均值算法對于不同的初始值，結果往往得到不同的局部極小值。而K-中心點輪換算法采用輪換替換的方法替換中心點，從而與初始值的選擇沒有關系。
(2)解決了K-均值算法對噪聲和離群點的敏感性問題。由于該算法不使用平均值來更改中心點而是選用位置最靠近中心的對象作為中心代表點，因此并不容易受極端數據的影響，具有很好的魯棒性。
K-中心點輪換算法也存有以下缺點：
(1)由于K-中心點輪換算法是基于劃分的一種聚類算法，仍然要求輸入要得到的簇的數目k，所以當k的取值不正確時，對聚類的結果影響甚大。
(2)從以上的時間復雜度也可以看出，當n和k較大時，計算代價很高，所以將該算法應用于大數據集時不是很理想。
1.5 K-means與K-mediods對比測試結果與分析
本次測試采用weka Iris數據集對比K-均值算法與K-中心點輪換算法對初始值的依賴性，對比結果如表1所示。通過改變初始隨機數種子，使初始值產生變化。
從表2可以看出，對于同一個數據集，K-mediods算法比K-means算法的聚類平均錯誤率低。
2 K-mediods算法的改進方向
針對K-中心點輪換算法的不足，可以從以下兩個方面對其加以改進。
2.1 基于抽樣的K-mediods算法
K-中心點輪換算法對小數據集非常有效，但對大數據集沒有良好的可伸縮性。為了處理較大的數據集，可以采用基于抽樣的方法，即不考慮整個數據集合，而是選擇實際數據的一小部分作為數據的代表。在抽樣過程中，抽樣算法盡可能保證數據不失真，又能體現數據的原始分布特征(如圖1所示)，然后對抽樣數據集使用K-中心點輪換算法。當然基于抽樣的算法的有效性取決于抽樣數據集與原數據集的相似度。在實際使用中，可以抽取原始數據集D的多個樣本，然后對每一個樣本Di進行K-中心點輪換算法，從中選擇目標準則函數E最小的結果作為輸出。
從采用K-中心點輪換算法對同一數據文件的聚類結果可以看到，最終目標函數值與聚類數目K大致滿足一個規律：合適的聚類數目往往就在平均最終目標函數值與聚類數目K所形成的關系折線的拐角位置。因為這個目標函數在距離空間中取的是所有點到其最近的中心點的距離的總和，一種極端情況是每個點都是中心點，聚類數目等于所有點數目，顯然目標函數的值是0。從直觀上可以推測，聚類數目越大，目標函數值就越小，而最終目標函數值的下降由快到慢的那個轉折位置往往就是一個關鍵位置。
通過對K-中心點輪換算法進行抽樣改進，成功地解決了K-中心點輪換算法時間復雜度問題，使其能夠處理大數據集的聚類分析問題。同時，拐點法是通過實踐總結出的一套簡單有效的判斷最優聚類數的方法。實驗表明，該方法簡單可行，計算量小，同時不影響現有的算法結構。通過上述兩個改進措施，使K-中心點輪換算法真正擁有更好的實際應用價值。
參考文獻
[1] HAN J W，KAMBER M．數據挖掘概念與技術[M].范明，孟小峰，譯．北京：機械工業出版社，2004：119-124，188-196．
[2] 鄭人杰，殷人昆，陶永雷．實用軟件工程[M]．北京：清華大學出版社，1999：51-53．
[3] JAIN A K，DUBES R C.Algorithms for clustering data[M]. NJ，USA：Prentice-Hall，Inc.，1988.
[4] 周世兵，徐振源，唐旭清.新的K-均值算法最佳聚類數確定方法[J].計算機工程與應用，2010，46(16)：27-31.
[5] KAUFMAN L，ROUSSEEUW P J.Finding groups in data：an introduction to cluster analysis[M].New York：John Wiley & Sons，1990.