第十一章 K-Means(K均值)演算法模型實現（下）

05-08

KMeans的應用

聚類是數據挖掘領域中重要的技術之一，用於發現數據中未知的分類。聚類分析已經有了很長的研究歷史，其重要性已經越來越受到人們的肯定。聚類演算法是機器學習、數據挖掘和模式識別等研究方向的重要研究內容之一，在識別數據對象的內在關係方面，具有極其重要的作用。聚類主要應用於模式識別中的語音識別、字元識別等，機器學習中的聚類演算法應用於圖像分割，圖像處理中，主要用於數據壓縮、信息檢索。聚類的另一個主要應用是數據挖掘、時空資料庫應用、序列和異常數據分析等。此外，聚類還應用於統計科學，同時，在生物學、地質學、地理學以及市場營銷、銀行客戶等級劃分等方面也有著重要的作用。

優點

1.演算法快速、簡單;

2.當聚類是密集的，且類與類之間區別明顯時，效果較好。

3.對大數據集有較高的效率並且是可伸縮性的;

4.時間複雜度近於線性，而且適合挖掘大規模數據集。

K-Means聚類演算法的時間複雜度是O(nkt) ,其中n代表數據集中對象的數量，t代表著演算法迭代的次數，k代表著簇的數目。

缺點

1.在 K-means 演算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。有的演算法是通過類的自動合併和分裂，得到較為合理的類型數目 K，例如 ISODATA 演算法。

2.在 K-means 演算法中，首先需要根據初始聚類中心來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果，這也成為 K-means演算法的一個主要問題。對於該問題的解決，許多演算法採用遺傳演算法，例如文獻中採用遺傳演算法（GA）進行初始化，以內部聚類準則作為評價指標。

3.從 K-means 演算法框架可以看出，該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。所以需要對演算法的時間複雜度進行分析、改進，提高演算法應用範圍。

應用案例

k-means演算法一個有趣的應用示例：中國男足近幾年到底在亞洲處於幾流水平？

今年中國男足可算是杯具到家了，幾乎到了過街老鼠人人喊打的地步。對於目前中國男足在亞洲的地位，各方也是各執一詞，有人說中國男足亞洲二流，有人說三流，還有人說根本不入流，更有人說其實不比日韓差多少，是亞洲一流。既然爭論不能解決問題，我們就讓數據告訴我們結果吧。

下圖是我採集的亞洲15隻球隊在2005年-2010年間大型杯賽的戰績（由於澳大利亞是後來加入亞足聯的，所以這裡沒有收錄）。

其中包括兩次世界盃和一次亞洲杯。我提前對數據做了如下預處理：對於世界盃，進入決賽圈則取其最終排名，沒有進入決賽圈的，打入預選賽十強賽賦予40，預選賽小組未出線的賦予50。對於亞洲杯，前四名取其排名，八強賦予5，十六強賦予9，預選賽沒出現的賦予17。這樣做是為了使得所有數據變為標量，便於後續聚類。

下面先對數據進行[0,1]規格化，下面是規格化後的數據：

接著用k-means演算法進行聚類。設k=3，即將這15支球隊分成三個集團。

現抽取日本、巴林和泰國的值作為三個簇的種子，即初始化三個簇的中心為A：{0.3, 0, 0.19}，B：{0.7, 0.76, 0.5}和C：{1, 1, 0.5}。下面，計算所有球隊分別對三個中心點的相異度，這裡以歐氏距離度量。下面是我用程序求取的結果：

從做到右依次表示各支球隊到當前中心點的歐氏距離，將每支球隊分到最近的簇，可對各支球隊做如下聚類：

中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡達C，阿聯酋C，烏茲別克B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。

第一次聚類結果：

A：日本，韓國，伊朗，沙特；

B：烏茲別克，巴林，朝鮮；

C：中國，伊拉克，卡達，阿聯酋，泰國，越南，阿曼，印尼。

下面根據第一次聚類結果，調整各個簇的中心點。

A簇的新中心點為：{(0.3+0+0.24+0.3)/4=0.21, (0+0.15+0.76+0.76)/4=0.4175, (0.19+0.13+0.25+0.06)/4=0.1575} = {0.21, 0.4175, 0.1575}

用同樣的方法計算得到B和C簇的新中心點分別為{0.7, 0.7333, 0.4167}，{1, 0.94, 0.40625}。

用調整後的中心點再次進行聚類，得到：

第二次迭代後的結果為：

中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡達C，阿聯酋C，烏茲別克B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。

結果無變化，說明結果已收斂，於是給出最終聚類結果：

亞洲一流：日本，韓國，伊朗，沙特

亞洲二流：烏茲別克，巴林，朝鮮

亞洲三流：中國，伊拉克，卡達，阿聯酋，泰國，越南，阿曼，印尼

看來數據告訴我們，說國足近幾年處在亞洲三流水平真的是沒有冤枉他們，至少從國際杯賽戰績是這樣的。

其實上面的分析數據不僅告訴了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出各個球隊之間的差距，例如，在亞洲一流隊伍中，日本與沙特水平最接近，而伊朗則相距他們較遠，這也和近幾年伊朗沒落的實際相符。另外，烏茲別克和巴林雖然沒有打進近兩屆世界盃，不過憑藉預算賽和亞洲杯上的出色表現佔據B組一席之地，而朝鮮由於打入了2010世界盃決賽圈而有幸進入B組，可是同樣奇蹟般奪得2007年亞洲杯的伊拉克卻被分在三流，看來亞洲杯冠軍的分量還不如打進世界盃決賽圈重啊。其它有趣的信息，有興趣的朋友可以進一步挖掘。

上面的應用案例取自參考文獻3，資料有點久遠，只供學習演算法運用。Kmeans演算法目前就寫這麼多，之後有應用與新的自己的改進或想法會繼續補充的。

參考文獻

1、《機器學習實戰》（書）

2、《k-means聚類演算法的研究》（碩士論文）

3、演算法雜貨鋪——KMeans均值聚類（博客）

4、K均值聚類（kmeans）演算法及應用（博客）

5、其他各種網站（略）