K-means算法原理與R語(yǔ)言實(shí)例

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

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

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

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

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

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

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

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

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

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

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

對(duì)于聚類(lèi)結(jié)果，限于篇幅我們?nèi)匀恢涣谐隽俗铋_(kāi)始的幾條。但是如果用圖形來(lái)顯示的話，可能更易于接受。下面是示例代碼。

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

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