K-means算法原理與R語言實例

聚類是將相似對象歸到同一個簇中的方法，這有點像全自動分類。簇內的對象越相似，聚類的效果越好。支持向量機、神經(jīng)網(wǎng)絡所討論的分類問題都是有監(jiān)督的學習方式，現(xiàn)在我們所介紹的聚類則是無監(jiān)督的。其中，K均值（K-means）是最基本、最簡單的聚類算法。

在K均值算法中，質心是定義聚類原型（也就是機器學習獲得的結果）的核心。在介紹算法實施的具體過程中，我們將演示質心的計算方法。而且你將看到除了第一次的質心是被指定的以外，此后的質心都是經(jīng)由計算均值而獲得的。

首先，選擇K個初始質心（這K個質心并不要求來自于樣本數(shù)據(jù)集），其中K是用戶指定的參數(shù)，也就是所期望的簇的個數(shù)。每個數(shù)據(jù)點都被收歸到距其最近之質心的分類中，而同一個質心所收歸的點集為一個簇。然后，根據(jù)本次分類的結果，更新每個簇的質心。重復上述數(shù)據(jù)點分類與質心變更步驟，直到簇內數(shù)據(jù)點不再改變，或者等價地說，直到質心不再改變。

基本的K均值算法描述如下：

根據(jù)數(shù)據(jù)點到新質心的距離，再次對數(shù)據(jù)集中的數(shù)據(jù)進行分類，如圖13-2(c)所示。然后，算法根據(jù)新的分類來計算新的質心，并再次根據(jù)數(shù)據(jù)點到新質心的距離，對數(shù)據(jù)集中的數(shù)據(jù)進行分類。結果發(fā)現(xiàn)簇內數(shù)據(jù)點不再改變，所以算法執(zhí)行結束，最終的聚類結果如圖13-2(d)所示。

對于距離函數(shù)和質心類型的某些組合，算法總是收斂到一個解，即K均值到達一種狀態(tài)，聚類結果和質心都不再改變。但為了避免過度迭代所導致的時間消耗，實踐中，也常用一個較弱的條件替換掉“質心不再發(fā)生變化”這個條件。例如，使用“直到僅有1%的點改變簇”。

盡管K均值聚類比較簡單，但它也的確相當有效。它的某些變種甚至更有效， 并且不太受初始化問題的影響。但K均值并不適合所有的數(shù)據(jù)類型。它不能處理非球形簇、不同尺寸和不同密度的簇，盡管指定足夠大的簇個數(shù)時它通?？梢园l(fā)現(xiàn)純子簇。對包含離群點的數(shù)據(jù)進行聚類時，K均值也有問題。在這種情況下，離群點檢測和刪除大有幫助。K均值的另一個問題是，它對初值的選擇是敏感的，這說明不同初值的選擇所導致的迭代次數(shù)可能相差很大。此外，K值的選擇也是一個問題。顯然，算法本身并不能自適應地判定數(shù)據(jù)集應該被劃分成幾個簇。最后，K均值僅限于具有質心（均值）概念的數(shù)據(jù)。一種相關的K中心點聚類技術沒有這種限制。在K中心點聚類中，我們每次選擇的不再是均值，而是中位數(shù)。這種算法實現(xiàn)的其他細節(jié)與K均值相差不大，我們不再贅述。

最后我們給出一個實際應用的例子。（代碼采用我最喜歡用做數(shù)據(jù)挖掘的R語言來實現(xiàn)）

一組來自世界銀行的數(shù)據(jù)統(tǒng)計了30個國家的兩項指標，我們用如下代碼讀入文件并顯示其中最開始的幾行數(shù)據(jù)?？梢?，數(shù)據(jù)共分三列，其中第一列是國家的名字，該項與后面的聚類分析無關，我們更關心后面兩列信息。第二列給出的該國第三產(chǎn)業(yè)增加值占GDP的比重，最后一列給出的是人口結構中年齡大于等于65歲的人口（也就是老齡人口）占總人口的比重。

為了方便后續(xù)處理，下面對讀入的數(shù)據(jù)庫進行一些必要的預處理，主要是調整列標簽，以及用國名替換掉行標簽（同時刪除包含國名的列）。

如果你繪制這些數(shù)據(jù)的散點圖，不難發(fā)現(xiàn)這些數(shù)據(jù)大致可以分為兩組。事實上，數(shù)據(jù)中有一半的國家是OECD成員國，而另外一半則屬于發(fā)展中國家（包括一些東盟國家、南亞國家和拉美國家）。所以我們可以采用下面的代碼來進行K均值聚類分析。

對于聚類結果，限于篇幅我們仍然只列出了最開始的幾條。但是如果用圖形來顯示的話，可能更易于接受。下面是示例代碼。

上述代碼的執(zhí)行結果如圖13-3所示。

另外一種與k-means非常類似的算法是k-median算法。此處已經(jīng)無需再詳細介紹k-中值算法的細節(jié)了，基本上和k-means一樣，只是把所有均值出現(xiàn)的地方換成中值而已。這個思想看起好像很不起眼，但是你還別說，k-median算法還真的存在，而且是k-means算法的一個重要補充和改進。