聚類分析實(shí)例

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

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

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

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

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

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

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

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

9、出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。下面先對數(shù)據(jù)進(jìn)行0,1規(guī)格化，下面是規(guī)格化后的數(shù)據(jù)：從做到右依次表示各支球隊(duì)到當(dāng)前中心點(diǎn)的歐氏距離，將每支球隊(duì)分到最近的簇，可對各支球隊(duì)做如下聚類：中國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)整各個(gè)簇的中心點(diǎn)。A 簇的新中心點(diǎn)為： (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用同樣的方法計(jì)算得到B 和C 簇的新中心點(diǎn)分別為0.7, 0.7333, 0.4167，1, 0.94,0.40625。用調(diào)整后的中心點(diǎn)再次進(jìn)行聚類，得到：第二次迭代后的結(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í)上面的分析數(shù)據(jù)不僅告訴了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出各個(gè)球隊(duì)之間的差距，例如，在亞洲一流隊(duì)伍中，日本與沙特水平最接近，而伊朗則相距他們較遠(yuǎn)，這也和近