KMeans的應(yīng)用
聚類是數(shù)據(jù)挖掘領(lǐng)域中重要的技術(shù)之一，用于發(fā)現(xiàn)數(shù)據(jù)中未知的分類。聚類分析已經(jīng)有了很長(zhǎng)的研究歷史马篮，其重要性已經(jīng)越來(lái)越受到人們的肯定。聚類算法是機(jī)器學(xué)習(xí)怜奖、數(shù)據(jù)挖掘和模式識(shí)別等研究方向的重要研究?jī)?nèi)容之一浑测，在識(shí)別數(shù)據(jù)對(duì)象的內(nèi)在關(guān)系方面，具有極其重要的作用。聚類主要應(yīng)用于模式識(shí)別中的語(yǔ)音識(shí)別迁央、字符識(shí)別等掷匠，機(jī)器學(xué)習(xí)中的聚類算法應(yīng)用于圖像分割，圖像處理中岖圈，主要用于數(shù)據(jù)壓縮讹语、信息檢索。聚類的另一個(gè)主要應(yīng)用是數(shù)據(jù)挖掘蜂科、時(shí)空數(shù)據(jù)庫(kù)應(yīng)用顽决、序列和異常數(shù)據(jù)分析等。此外，聚類還應(yīng)用于統(tǒng)計(jì)科學(xué)，同時(shí)舶替，在生物學(xué)憎账、地質(zhì)學(xué)、地理學(xué)以及市場(chǎng)營(yíng)銷、銀行客戶等級(jí)劃分等方面也有著重要的作用。
優(yōu)點(diǎn)
1.算法快速、簡(jiǎn)單;
2.當(dāng)聚類是密集的进每，且類與類之間區(qū)別明顯時(shí)，效果較好命斧。
3.對(duì)大數(shù)據(jù)集有較高的效率并且是可伸縮性的;
4.時(shí)間復(fù)雜度近于線性田晚，而且適合挖掘大規(guī)模數(shù)據(jù)集。
K-Means聚類算法的時(shí)間復(fù)雜度是O(nkt) ,其中n代表數(shù)據(jù)集中對(duì)象的數(shù)量国葬，t代表著算法迭代的次數(shù)贤徒，k代表著簇的數(shù)目。
缺點(diǎn)
1.在 K-means 算法中 K 是事先給定的汇四，這個(gè) K 值的選定是非常難以估計(jì)的接奈。有的算法是通過(guò)類的自動(dòng)合并和分裂，得到較為合理的類型數(shù)目 K通孽，例如 ISODATA 算法序宦。
2.在 K-means 算法中，首先需要根據(jù)初始聚類中心來(lái)確定一個(gè)初始劃分背苦，然后對(duì)初始劃分進(jìn)行優(yōu)化互捌。這個(gè)初始聚類中心的選擇對(duì)聚類結(jié)果有較大的影響，一旦初始值選擇的不好行剂，可能無(wú)法得到有效的聚類結(jié)果秕噪，這也成為 K-means算法的一個(gè)主要問(wèn)題。對(duì)于該問(wèn)題的解決厚宰，許多算法采用遺傳算法腌巾，例如文獻(xiàn) 中采用遺傳算法（GA）進(jìn)行初始化，以內(nèi)部聚類準(zhǔn)則作為評(píng)價(jià)指標(biāo)。
3.從 K-means 算法框架可以看出澈蝙，該算法需要不斷地進(jìn)行樣本分類調(diào)整吓坚，不斷地計(jì)算調(diào)整后的新的聚類中心，因此當(dāng)數(shù)據(jù)量非常大時(shí)灯荧，算法的時(shí)間開銷是非常大的凌唬。所以需要對(duì)算法的時(shí)間復(fù)雜度進(jìn)行分析、改進(jìn)漏麦，提高算法應(yīng)用范圍。
應(yīng)用案例
k-means算法一個(gè)有趣的應(yīng)用示例：中國(guó)男足近幾年到底在亞洲處于幾流水平况褪？
今年中國(guó)男足可算是杯具到家了撕贞，幾乎到了過(guò)街老鼠人人喊打的地步。對(duì)于目前中國(guó)男足在亞洲的地位测垛，各方也是各執(zhí)一詞捏膨，有人說(shuō)中國(guó)男足亞洲二流，有人說(shuō)三流食侮，還有人說(shuō)根本不入流号涯，更有人說(shuō)其實(shí)不比日韓差多少，是亞洲一流锯七。既然爭(zhēng)論不能解決問(wèn)題链快，我們就讓數(shù)據(jù)告訴我們結(jié)果吧。
下圖是我采集的亞洲15只球隊(duì)在2005年-2010年間大型杯賽的戰(zhàn)績(jī)（由于澳大利亞是后來(lái)加入亞足聯(lián)的眉尸，所以這里沒(méi)有收錄）域蜗。
其中包括兩次世界杯和一次亞洲杯。我提前對(duì)數(shù)據(jù)做了如下預(yù)處理：對(duì)于世界杯噪猾，進(jìn)入決賽圈則取其最終排名霉祸，沒(méi)有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40袱蜡，預(yù)選賽小組未出線的賦予50丝蹭。對(duì)于亞洲杯，前四名取其排名坪蚁，八強(qiáng)賦予5奔穿，十六強(qiáng)賦予9，預(yù)選賽沒(méi)出現(xiàn)的賦予17敏晤。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量巫橄，便于后續(xù)聚類。
下面先對(duì)數(shù)據(jù)進(jìn)行[0,1]規(guī)格化茵典，下面是規(guī)格化后的數(shù)據(jù)：
接著用k-means算法進(jìn)行聚類湘换。設(shè)k=3，即將這15支球隊(duì)分成三個(gè)集團(tuán)。
現(xiàn)抽取日本彩倚、巴林和泰國(guó)的值作為三個(gè)簇的種子筹我，即初始化三個(gè)簇的中心為A：{0.3, 0, 0.19}，B：{0.7, 0.76, 0.5}和C：{1, 1, 0.5}帆离。下面蔬蕊，計(jì)算所有球隊(duì)分別對(duì)三個(gè)中心點(diǎn)的相異度，這里以歐氏距離度量哥谷。下面是我用程序求取的結(jié)果：
從做到右依次表示各支球隊(duì)到當(dāng)前中心點(diǎn)的歐氏距離岸夯，將每支球隊(duì)分到最近的簇，可對(duì)各支球隊(duì)做如下聚類：
中國(guó)C们妥，日本A猜扮，韓國(guó)A，伊朗A监婶，沙特A旅赢，伊拉克C，卡塔爾C惑惶，阿聯(lián)酋C煮盼，烏茲別克斯坦B，泰國(guó)C带污，越南C僵控，阿曼C，巴林B鱼冀，朝鮮B喉祭，印尼C。
第一次聚類結(jié)果：
A：日本雷绢，韓國(guó)泛烙，伊朗，沙特翘紊；
B：烏茲別克斯坦蔽氨，巴林，朝鮮帆疟；
C：中國(guó)鹉究，伊拉克，卡塔爾踪宠，阿聯(lián)酋自赔，泰國(guó)，越南柳琢，阿曼绍妨，印尼润脸。
下面根據(jù)第一次聚類結(jié)果，調(diào)整各個(gè)簇的中心點(diǎn)他去。
A簇的新中心點(diǎn)為：{(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}
用同樣的方法計(jì)算得到B和C簇的新中心點(diǎn)分別為{0.7, 0.7333, 0.4167}毙驯，{1, 0.94, 0.40625}。
用調(diào)整后的中心點(diǎn)再次進(jìn)行聚類灾测，得到：
第二次迭代后的結(jié)果為：
中國(guó)C爆价，日本A，韓國(guó)A媳搪，伊朗A铭段，沙特A，伊拉克C秦爆，卡塔爾C序愚，阿聯(lián)酋C，烏茲別克斯坦B鲜结，泰國(guó)C，越南C活逆，阿曼C精刷，巴林B，朝鮮B蔗候，印尼C怒允。
結(jié)果無(wú)變化，說(shuō)明結(jié)果已收斂锈遥，于是給出最終聚類結(jié)果：
亞洲一流：日本纫事，韓國(guó)，伊朗所灸，沙特
亞洲二流：烏茲別克斯坦丽惶，巴林，朝鮮
亞洲三流：中國(guó)爬立，伊拉克钾唬，卡塔爾，阿聯(lián)酋侠驯，泰國(guó)抡秆，越南，阿曼吟策，印尼
看來(lái)數(shù)據(jù)告訴我們儒士，說(shuō)國(guó)足近幾年處在亞洲三流水平真的是沒(méi)有冤枉他們，至少?gòu)膰?guó)際杯賽戰(zhàn)績(jī)是這樣的檩坚。
其實(shí)上面的分析數(shù)據(jù)不僅告訴了我們聚類信息着撩，還提供了一些其它有趣的信息诅福，例如從中可以定量分析出各個(gè)球隊(duì)之間的差距，例如睹酌，在亞洲一流隊(duì)伍中权谁，日本與沙特水平最接近，而伊朗則相距他們較遠(yuǎn)憋沿，這也和近幾年伊朗沒(méi)落的實(shí)際相符旺芽。另外，烏茲別克斯坦和巴林雖然沒(méi)有打進(jìn)近兩屆世界杯辐啄，不過(guò)憑借預(yù)算賽和亞洲杯上的出色表現(xiàn)占據(jù)B組一席之地采章，而朝鮮由于打入了2010世界杯決賽圈而有幸進(jìn)入B組，可是同樣奇跡般奪得2007年亞洲杯的伊拉克卻被分在三流壶辜，看來(lái)亞洲杯冠軍的分量還不如打進(jìn)世界杯決賽圈重啊悯舟。其它有趣的信息，有興趣的朋友可以進(jìn)一步挖掘砸民。
上面的應(yīng)用案例取自參考文獻(xiàn)3抵怎，資料有點(diǎn)久遠(yuǎn)，只供學(xué)習(xí)算法運(yùn)用岭参。Kmeans算法目前就寫這么多反惕，之后有應(yīng)用與新的自己的改進(jìn)或想法會(huì)繼續(xù)補(bǔ)充的。
參考文獻(xiàn)
1演侯、《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》（書）
2姿染、《k-means聚類算法的研究》（碩士論文）
3、算法雜貨鋪——KMeans均值聚類（博客）
4秒际、 K均值聚類（kmeans）算法及應(yīng)用（博客）
5悬赏、其他各種網(wǎng)站（略）
