聚類分析實(shí)例

1、v1.0可編輯可修改k-mea ns聚類”數(shù)據(jù)分析、數(shù)據(jù)挖掘一、概要分類作為一種監(jiān)督學(xué)習(xí)方法，要求必須事先明確知道各個(gè)類別的信息， 并 且斷言所有待分類項(xiàng)都有一個(gè)類別與之對(duì)應(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è)在體育界大家頗具爭(zhēng)議的問題中國(guó)男足近幾年在亞洲到底處于幾流水 平。二、聚類問題所謂聚類問題，就是給定一

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ù) 庫(kù)技術(shù)和市場(chǎng)營(yíng)銷等領(lǐng)域，相應(yīng)的算法也非常的多。本文僅介紹一種最簡(jiǎn)單的聚 類算法k均值（k-means）算法。三、概念介紹區(qū)分兩個(gè)概念：hard clustering : 一個(gè)文檔要么屬于類 w,要么不屬于類w

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

4、，計(jì)算方法如下：這里加入一個(gè)方差RSS的概念： RSS, = 爪吐廠KRSS =匸 RSSkk= 1RSSk的值是類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ì)心在第n+ 1次迭代時(shí)候位 置不變。3) n個(gè)文檔達(dá)到收斂，即第n次計(jì)算出的n個(gè)文檔分類和在第n+ 1次迭代時(shí)候 文檔分類結(jié)果相同。4) RSS值小于一個(gè)閥值，實(shí)際中往往把這個(gè)條件結(jié)合條件1使用回過頭用RSS討論質(zhì)心的計(jì)算方法是否合理RSS(u)二胡氐(巧 _ 麗tnE I蓼-評(píng)= 匸2伽- g

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

6、次聚類代價(jià)非常高。以上的討論都是基于K是已知的，但是我們?cè)趺茨軓碾S機(jī)的文檔集合中選擇這個(gè)k值呢我們可以對(duì)k去1N分別執(zhí)行k-means，得到RSS關(guān)于K的函數(shù)下圖：gL當(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ù)平均數(shù)。4、將D中全部元素按照新的中心重新聚類。5、重復(fù)第4步，直到聚類結(jié)果不再變化

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

8、越迥BJ朝印克爾昔別50281725O4-BI91540其中包括兩次世界杯和一次亞洲杯。我提前對(duì)數(shù)據(jù)做了如下預(yù)處理：對(duì)于世界杯，進(jìn)入決賽圈則取其最終排名，沒有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40,預(yù)選賽小組未出線的賦予50。對(duì)于亞洲杯，前四名取其排名，八強(qiáng)賦予5，十六強(qiáng)賦予9,預(yù)選賽沒出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。下面先對(duì)數(shù)據(jù)進(jìn)行0,1規(guī)格化，下面是規(guī)格化后的數(shù)據(jù)：6v1.0可編輯可修改22356799101112131屯1516fi-sr克克爾苗別國(guó)本國(guó)館牲匸匸y茲國(guó)南曼林鮮尼中日韓伊抄伊卡阿烏垂越阿巴朝印111- Ml-JI5 Ji o.16 6 6 1

9、7 7 7 - o o O16 8 17 6 O 0Go o0 5 5 5-5 2 o O 0O5 5 15DAM其中包括兩次世界杯和一次亞洲杯。我提前對(duì)數(shù)據(jù)做了如下預(yù)處理：對(duì)于世界杯，進(jìn)入決賽圈則取其最終排名，沒有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40,預(yù)選賽小組未出線的賦予50。對(duì)于亞洲杯，前四名取其排名，八強(qiáng)賦予5，十六強(qiáng)賦予9,預(yù)選賽沒出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。下面先對(duì)數(shù)據(jù)進(jìn)行0,1規(guī)格化，下面是規(guī)格化后的數(shù)據(jù)：7v1.0可編輯可修改10*和曰/!:/個(gè)入 bin/Debug/krtiejris. EXE1 -212436fl,51961500.6

10、92821.21249G1212436I732OS1ft.1033230.796731.3163SfP,692821.2124361212436CL 1961501.212436B.51?61501.212360.$196150.S92820.519615.21243fc&51 呵 5i 212436& 51961501,212436晉.51961500.&92S200.51961SB.69282Q0.S196151-2124366_S1?6150EncZhang百 Tech Blog (httpJ/leoo2sk cnblogs com)從做到右依次表示各支球隊(duì)到當(dāng)前中心點(diǎn)的歐氏距離,將每支

11、球隊(duì)分到最近的簇，可對(duì)各支球隊(duì)做如下聚類:中國(guó)C,日本A,韓國(guó)A,伊朗A,沙特A,伊拉克C,卡塔爾C,阿聯(lián)酋C,烏茲別克斯坦 B,泰國(guó)C,越南C,阿曼C,巴林B,朝鮮B,印尼Co第一次聚類結(jié)果：A:日本，韓國(guó)，伊朗，沙特；B:烏茲別克斯坦，巴林，朝鮮；C:中國(guó)，伊拉克，卡塔爾，阿聯(lián)酋，泰國(guó)，越南，阿曼，印尼。下面根據(jù)第一次聚類結(jié)果，調(diào)整各個(gè)簇的中心點(diǎn)。A 簇的新中心點(diǎn)為： +0+/4= , (0+/4=,+/4= = , , 用同樣的方法計(jì)算得到B和C簇的新中心點(diǎn)分別為, , , 1, ,用調(diào)整后的中心點(diǎn)再次進(jìn)行聚類，得到: file：/ El丿個(gè)人丈匕 /kmns/kmeari/bi n/D

12、bLig/icnnans.EXE0683200,1558851.21243603637311.2124361-7320510-0519&2(1.7967431.3163E99.1558856.692821.2124361-3G832P1.360320.51?&1501-368329 51961509.8487050.S196151-3G832.51961501.3G832019G1S01.368320.51H1S0團(tuán).848705e8.S196153.848705陌0.5196151.368320.5196150EricZhangs Tech Blog (tittp /le2sk cnblogs com第二次迭代后的結(jié)果為:中國(guó)C,日本A,韓國(guó)A,伊朗A,沙特A,伊拉克C,卡塔爾C,阿聯(lián)酋C,烏茲別克斯坦 B, 泰國(guó)C,越南C,阿曼C,巴林B,朝鮮B,印尼Co結(jié)果無變化，說明結(jié)果已收斂，于是給出最終聚類結(jié)果：亞洲一流：日本，韓國(guó)，伊朗，沙特亞洲二流：烏茲別克斯坦，巴林，朝鮮亞洲三流：中國(guó)，伊拉克，卡塔爾，阿聯(lián)酋，泰國(guó)，越南，阿曼，印尼看來數(shù)據(jù)告訴我們，說國(guó)足近幾年處在亞洲三流水平真的是沒有冤枉他們，至少?gòu)膰?guó)際杯賽戰(zhàn)績(jī)是這樣的。其實(shí)上面的分析數(shù)據(jù)不僅告訴了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出各個(gè)球隊(duì)之間的差距