聚類分析實例

1、k-means聚類”數(shù)據(jù)分析、數(shù)據(jù)挖掘一、概要     分類作為一種監(jiān)督學(xué)習(xí)方法，要求必須事先明確知道各個類別的信息，并且斷言所有待分類項都有一個類別與之對應(yīng)。但是很多時候上述條件得不到滿足，尤其是在處理海量數(shù)據(jù)的時候，如果通過預(yù)處理使得數(shù)據(jù)滿足分類算法的要求，則代價非常大，這時候可以考慮使用聚類算法。聚類屬于無監(jiān)督學(xué)習(xí)，相比于分類，聚類不依賴預(yù)定義的類和類標(biāo)號的訓(xùn)練實例。本文介紹一種常見的聚類算法k 均值和k 中心點聚類，最后會舉一個實例：應(yīng)用聚類方法試圖解決一個在體育界大家頗具爭議的問題中國男足近幾年在亞洲到底處于幾流水平。二、聚類問題    所謂聚

2、類問題，就是給定一個元素集合D，其中每個元素具有n 個可觀察屬性，使用某種算法將D 劃分成k 個子集，要求每個子集內(nèi)部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。    與分類不同，分類是示例式學(xué)習(xí)，要求分類前明確各個類別，并斷言每個元素映射到一個類別，而聚類是觀察式學(xué)習(xí)，在聚類前可以不知道類別甚至不給定類別數(shù)量，是無監(jiān)督學(xué)習(xí)的一種。目前聚類廣泛應(yīng)用于統(tǒng)計學(xué)、生物學(xué)、數(shù)據(jù)庫技術(shù)和市場營銷等領(lǐng)域，相應(yīng)的算法也非常的多。本文僅介紹一種最簡單的聚類算法k 均值（k-means）算法。三、概念介紹區(qū)分兩個概念：hard clustering：一

3、個文檔要么屬于類w，要么不屬于類w，即文檔對確定的類w是二值的1或0。soft clustering：一個文檔可以屬于類w1，同時也可以屬于w2，而且文檔屬于一個類的值不是0或1，可以是0.3這樣的小數(shù)。K-Means就是一種hard clustering，所謂K-means里的K就是我們要事先指定分類的個數(shù)，即K個。k-means算法的流程如下：1）從N個文檔隨機選取K個文檔作為初始質(zhì)心2）對剩余的每個文檔測量其到每個質(zhì)心的距離，并把它歸到最近的質(zhì)心的類3）重新計算已經(jīng)得到的各個類的質(zhì)心4）迭代23步直至滿足既定的條件，算法結(jié)束在Kmeans算法里所有的文檔都必須向量化，n個文檔的質(zhì)心可以認(rèn)

4、為是這n個向量的中心，計算方法如下：                    這里加入一個方差RSS的概念：RSSk的值是類k中每個文檔到質(zhì)心的距離，RSS是所有k個類的RSS值的和。算法結(jié)束條件：1）給定一個迭代次數(shù)，達到這個次數(shù)就停止，這好像不是一個好建議。2）k個質(zhì)心應(yīng)該達到收斂，即第n次計算出的n個質(zhì)心在第n1次迭代時候位置不變。3）n個文檔達到收斂，即第n次計算出的n個文檔分類和在第n1次迭代時候文檔分類結(jié)果相同。4）RSS值小于一個閥值，實際中往往把這個條件結(jié)合條件1使用回過

5、頭用RSS討論質(zhì)心的計算方法是否合理    為了取得RSS的極小值，RSS對質(zhì)心求偏導(dǎo)數(shù)應(yīng)該為0，所以得到質(zhì)心           可見，這個質(zhì)心的選擇是合乎數(shù)學(xué)原理的。 K-means方法的缺點是聚類結(jié)果依賴于初始選擇的幾個質(zhì)點位置，看下面這個例子：如果使用2means方法，初始選擇d2和d5那么得到的聚類結(jié)果就是d1，d2，d3d4，d5，d6，這不是一個合理的聚類結(jié)果解決這種初始種子問題的方案：1）去處一些游離在外層的文檔后再選擇2）多選一些種子，取結(jié)果好的（RSS小）的K個類繼續(xù)算法3）用層次聚類

6、的方法選擇種子。我認(rèn)為這不是一個合適的方法，因為對初始N個文檔進行層次聚類代價非常高。以上的討論都是基于K是已知的，但是我們怎么能從隨機的文檔集合中選擇這個k值呢？我們可以對k去1N分別執(zhí)行k-means，得到RSS關(guān)于K的函數(shù)下圖：當(dāng)RSS由顯著下降到不是那么顯著下降的K值就可以作為最終的K，如圖可以選擇4或9。四、算法及示例 k 均值算法的計算過程非常直觀：1、從D 中隨機取k 個元素，作為k 個簇的各自的中心。2、分別計算剩下的元素到k 個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。3、根據(jù)聚類結(jié)果，重新計算k 個簇各自的中心，計算方法是取簇中所有元素各自維度的算術(shù)平均

7、數(shù)。4、將D 中全部元素按照新的中心重新聚類。5、重復(fù)第4 步，直到聚類結(jié)果不再變化。6、將結(jié)果輸出。由于算法比較直觀，沒有什么可以過多講解的。下面，我們來看看k-means 算法一個有趣的應(yīng)用示例：中國男足近幾年到底在亞洲處于幾流水平？今年中國男足可算是杯具到家了，幾乎到了過街老鼠人人喊打的地步。對于目前中國男足在亞洲的地位，各方也是各執(zhí)一詞，有人說中國男足亞洲二流，有人說三流，還有人說根本不入流，更有人說其實不比日韓差多少，是亞洲一流。既然爭論不能解決問題，我們就讓數(shù)據(jù)告訴我們結(jié)果吧。下圖是采集的亞洲15 只球隊在2005 年-2010 年間大型杯賽的戰(zhàn)績（由于澳大利亞是后來加入亞足聯(lián)的，

8、所以這里沒有收錄）。其中包括兩次世界杯和一次亞洲杯。我提前對數(shù)據(jù)做了如下預(yù)處理：對于世界杯，進入決賽圈則取其最終排名，沒有進入決賽圈的，打入預(yù)選賽十強賽賦予40，預(yù)選賽小組未出線的賦予50。對于亞洲杯，前四名取其排名，八強賦予5，十六強賦予9，預(yù)選賽沒出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。下面先對數(shù)據(jù)進行0,1規(guī)格化，下面是規(guī)格化后的數(shù)據(jù)：其中包括兩次世界杯和一次亞洲杯。我提前對數(shù)據(jù)做了如下預(yù)處理：對于世界杯，進入決賽圈則取其最終排名，沒有進入決賽圈的，打入預(yù)選賽十強賽賦予40，預(yù)選賽小組未出線的賦予50。對于亞洲杯，前四名取其排名，八強賦予5，十六強賦予9，預(yù)選賽沒

9、出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。下面先對數(shù)據(jù)進行0,1規(guī)格化，下面是規(guī)格化后的數(shù)據(jù)：從做到右依次表示各支球隊到當(dāng)前中心點的歐氏距離，將每支球隊分到最近的簇，可對各支球隊做如下聚類：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。第一次聚類結(jié)果：A：日本，韓國，伊朗，沙特；B：烏茲別克斯坦，巴林，朝鮮；C：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼。下面根據(jù)第一次聚類結(jié)果，調(diào)整各個簇的中心點。A 簇的新中心點為： (0.3+0+0.24+0.3)/4=0.21，(0+0

10、.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。用調(diào)整后的中心點再次進行聚類，得到：第二次迭代后的結(jié)果為：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。結(jié)果無變化，說明結(jié)果已收斂，于是給出最終聚類結(jié)果：亞洲一流：日本，韓國，伊朗，沙特亞洲二流：烏茲別克斯坦，巴林，朝鮮亞洲三流：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼看來數(shù)據(jù)告訴我們，說國足近幾年處在亞洲三流水平真的是沒有冤枉他們，至少從國際杯賽戰(zhàn)績是這樣的。其實上面的分析數(shù)據(jù)不僅告訴了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出各個球隊之間的差距，例如，在亞洲一流隊伍中，日本與沙特水平最接近，而伊朗則相距他們較遠，這也和近