機(jī)器學(xué)習(xí)中K—means聚類算法的分析和應(yīng)用

王子橋

摘 要：本文采用機(jī)器學(xué)習(xí)中的聚類算法對(duì)高水平足球聯(lián)賽五十名頂尖球員的進(jìn)攻數(shù)據(jù)進(jìn)行無監(jiān)督聚類學(xué)習(xí)和分析，并以進(jìn)球數(shù)、射正數(shù)和助攻數(shù)為評(píng)價(jià)指標(biāo)，將球員分成三個(gè)類別。本文首先分析了K-means聚類算法的流程和特點(diǎn)，進(jìn)而應(yīng)用于對(duì)足球運(yùn)動(dòng)員比賽數(shù)據(jù)的聚類運(yùn)算。對(duì)聚類后的分類結(jié)果進(jìn)行分析和比較，從而找出球員的優(yōu)勢劣勢。其結(jié)果不僅對(duì)球員個(gè)人發(fā)展有極大的指導(dǎo)作用，也對(duì)中國足球取長補(bǔ)短、提升自身能力有重要意義。

關(guān)鍵詞：K-means算法；聚類；機(jī)器學(xué)習(xí)

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2017）04-0030-02

計(jì)算機(jī)是迄今為止最為高效的信息處理工具，特別是近年來隨著互聯(lián)網(wǎng)的發(fā)展，應(yīng)用計(jì)算機(jī)輔助工作和學(xué)習(xí)已經(jīng)成為常態(tài)。但普通計(jì)算機(jī)缺乏自主學(xué)習(xí)的能力，只是被動(dòng)地執(zhí)行人為設(shè)定好的程序。因此人們開始尋找一種能以與人類智能學(xué)習(xí)相似的方式進(jìn)行數(shù)據(jù)處理的方法，于是人工智能應(yīng)運(yùn)而生。

從1997年深藍(lán)在國際象棋中戰(zhàn)勝卡帕羅耶夫，到2016年AlphaGo在圍棋中擊敗李世石，不難看出，人工智能的發(fā)展?jié)摿κ志薮?。然而，目前的人工智能仍處于十分初?jí)的弱人工智能階段，想要進(jìn)一步發(fā)展人工智能就必須探索新的更有效的方法。

近年來，人工智能領(lǐng)域中的重要方向——機(jī)器學(xué)習(xí)，得到了越來越多的重視，顧名思義，機(jī)器學(xué)習(xí)是通過經(jīng)驗(yàn)自動(dòng)改進(jìn)計(jì)算機(jī)算法的研究，[1]也就是說，機(jī)器學(xué)習(xí)能用數(shù)據(jù)或以往的經(jīng)驗(yàn)優(yōu)化計(jì)算機(jī)程序的性能標(biāo)準(zhǔn)，在不斷進(jìn)行自我學(xué)習(xí)的過程中，對(duì)機(jī)器自身程序算法進(jìn)行優(yōu)化。在機(jī)器學(xué)習(xí)中，聚類是一種極其重要的算法。聚類源于包括數(shù)學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)、生物學(xué)等的許多領(lǐng)域，其工作原理是通過研究各個(gè)樣本之間的相似度，利用數(shù)學(xué)方法對(duì)樣本進(jìn)行分類。[2]這其中，K-means算法是最為經(jīng)典的聚類算法之一。K-means算法是聚類分析中一種基于劃分的算法，屬于無監(jiān)督的學(xué)習(xí)，該算法是聚類分析中一種十分經(jīng)典且非常高效的方法，具有高效率和相對(duì)可伸縮的優(yōu)點(diǎn)，在處理大數(shù)據(jù)集時(shí)簡單快速，十分方便。[3]

1 K-means算法

作為一種無監(jiān)督的聚類算法，K-means算法在解決多個(gè)樣本數(shù)據(jù)進(jìn)行分類的問題時(shí)十分有效，給定一組樣本{}，K-means算法將會(huì)把樣本聚成k個(gè)簇，具體步驟如下：

（1）根據(jù)給定的k值隨機(jī)選取k個(gè)質(zhì)心{}。

（2）重復(fù)迭代兩步直到質(zhì)心不變或變化很?。?）計(jì)算每一個(gè)樣本i應(yīng)屬于的類別=argmin，2）對(duì)每一個(gè)類別j，重新計(jì)算它的質(zhì)心，其中k是已知的聚類數(shù)，是樣本i與k個(gè)類別中最近的一類，質(zhì)心位置是初始隨機(jī)選定的。其算法流程圖如圖1所示。

下面用算法圖例來展示K-means算法的具體運(yùn)算流程，如圖2所示。

如上圖所示，數(shù)據(jù)的初始分布如圖（a）所示，數(shù)據(jù)點(diǎn)用二維平面的加號(hào) ”+”表示，共9個(gè)數(shù)據(jù)點(diǎn)。在圖（b）中，用星號(hào)“*”表示K-means算法的初始聚類中心。根據(jù)上述算法流程，K-means通過計(jì)算初始聚類中心到數(shù)據(jù)點(diǎn)的歐氏距離對(duì)樣本點(diǎn)進(jìn)行第一次分類，用紅色與綠色表明第一次的分類結(jié)果，結(jié)果如圖（b）所示。在第一次分類后，對(duì)每一類的全部樣本點(diǎn)重新計(jì)算質(zhì)心，再次計(jì)算樣本與每個(gè)質(zhì)心的距離進(jìn)行下一次分類，結(jié)果如圖（c）。重復(fù)該過程直到聚類質(zhì)心的位置不變或質(zhì)心變化很小達(dá)到穩(wěn)定狀態(tài)，結(jié)果如圖（d），最終得到了樣本的2分類結(jié)果。

由以上介紹，我們可以看出K-means算法操作簡便，分類效率高。在速度上有很明顯的優(yōu)勢，特別是在處理大量復(fù)雜樣本時(shí)，K-means能利用比較各個(gè)樣本相似度特性的方法就使問題得到簡化，從而達(dá)到快速分類的目的。它的另一優(yōu)點(diǎn)是時(shí)間復(fù)雜度較低，其時(shí)間復(fù)雜度可以表示為O（nkt）。n是數(shù)據(jù)集中對(duì)象的數(shù)量，k是類別數(shù)，t是迭代次數(shù)。也就是說，其時(shí)間復(fù)雜度是近于線性的，相對(duì)于其他的聚類算法復(fù)雜度較低。

然而K-means算法只能達(dá)到局部最優(yōu)，因此在其k值的選擇和初始質(zhì)心的選取上較難控制，不同取值會(huì)導(dǎo)致較大的差異.且K-means對(duì)數(shù)據(jù)源要求較高，只適用于球狀分布的聚類特性數(shù)據(jù)，不能處理非球狀分布或差別很大的樣本集，這是該算法一個(gè)很大的局限性。另外，因?yàn)榈螖?shù)無法確定，K-means算法的算法不夠穩(wěn)定，在某些特殊的數(shù)據(jù)集上可能導(dǎo)致其復(fù)雜度急劇增加，導(dǎo)致算法的運(yùn)行效率較低。

2 球員數(shù)據(jù)應(yīng)用

足球運(yùn)動(dòng)員在訓(xùn)練或比賽中會(huì)有許多個(gè)人表現(xiàn)的數(shù)據(jù)，比如進(jìn)球數(shù)、助攻數(shù)等等。對(duì)球員數(shù)據(jù)的合理分析有助于指導(dǎo)球員的訓(xùn)練和提升技術(shù)水平。本文收集了歐洲范圍內(nèi)五大高水平聯(lián)賽50名頂尖球員（排名榜前十名）的運(yùn)動(dòng)數(shù)據(jù)。由于所列球員都為進(jìn)攻性球員，故采取進(jìn)球數(shù)、助攻數(shù)、射門成功率為評(píng)價(jià)指標(biāo)，其中射門成功率為 （進(jìn)球數(shù)/射門數(shù)）*100%。由于各個(gè)數(shù)據(jù)的變化范圍不統(tǒng)一，因此首先對(duì)數(shù)據(jù)進(jìn)行歸一化處理，再讀入K-means程序進(jìn)行聚類分析。

在經(jīng)過歸一化處理之后，將50組數(shù)據(jù)讀入K-means算法程序，并通過進(jìn)球數(shù)、助攻數(shù)和射門成功率三維坐標(biāo)進(jìn)行顯示，其分類結(jié)果如圖3所示。

由該分類結(jié)果我們可以看出，越靠近坐標(biāo)為（1，1，1）的點(diǎn)說明球員的數(shù)據(jù)越突出。在本結(jié)果中，綠色類為數(shù)據(jù)較優(yōu)秀的球員，藍(lán)色類為數(shù)據(jù)一般的球員，而紅色類為數(shù)據(jù)較差的球員。在助攻數(shù)和射門成功率上，綠色類都要明顯優(yōu)于其他兩組，而在進(jìn)球數(shù)上，三個(gè)類別沒有體現(xiàn)出明顯的分類差異。特別是，在助攻數(shù)這一評(píng)價(jià)標(biāo)準(zhǔn)中，三類的區(qū)分度尤其明顯，這也就意味著，助攻數(shù)和射門成功率是衡量一個(gè)優(yōu)秀球員最為關(guān)鍵的因素，而不僅僅是考量進(jìn)球數(shù)。這一點(diǎn)與人們一般認(rèn)可進(jìn)球數(shù)的常識(shí)相悖。因此要想成為一名優(yōu)秀的足球運(yùn)動(dòng)員，除了在保證進(jìn)球數(shù)的基礎(chǔ)上，提升助攻和射門成功率也是十分重要的方面。

但是，在本方法中也存在一定不足。比如數(shù)據(jù)的采集，總共選取了50名球員的運(yùn)動(dòng)數(shù)據(jù)，而且主要取自于頂尖排名，但并不一定能夠代表所有足球運(yùn)動(dòng)員的實(shí)際水平，具有一定的局限性。另一方面，本方法所分析的助攻數(shù)、進(jìn)球數(shù)和射門成功率這三項(xiàng)指標(biāo)并不能完全代表一個(gè)球員的場上表現(xiàn)，只是選取了三個(gè)可量化的評(píng)價(jià)指標(biāo)，為了得到更為全面的評(píng)價(jià)結(jié)論，還需要更加全方位的分析和總結(jié)。

3 結(jié)語

本文分析了機(jī)器學(xué)習(xí)中無監(jiān)督聚類算法K-means的詳細(xì)流程和典型應(yīng)用。對(duì)該算法的實(shí)現(xiàn)過程、算法流程進(jìn)行了仔細(xì)的分析和討論。并將該算法應(yīng)用在對(duì)頂尖足球運(yùn)動(dòng)員運(yùn)動(dòng)數(shù)據(jù)的聚類分析上，以進(jìn)球數(shù)、射正數(shù)和助攻數(shù)為評(píng)價(jià)指標(biāo)，將球員分成三個(gè)類別。并對(duì)聚類后的分類結(jié)果進(jìn)行分析和比較，發(fā)現(xiàn)助攻數(shù)是較進(jìn)球數(shù)影響更大的因素，從而找出分辨球員的優(yōu)劣的新標(biāo)準(zhǔn)。該結(jié)果對(duì)足球運(yùn)動(dòng)員個(gè)人能力的提升上意義重大，更對(duì)中國足球未來的發(fā)展有一定指導(dǎo)作用。

參考文獻(xiàn)

[1]曾華軍，張銀奎，等譯.《機(jī)器學(xué)習(xí)》Tom M Mitchell[M].機(jī)械工業(yè)出版社，2003.

[2]馬俊才，趙玉峰.基于分行維數(shù)的聚類分析研究[J].微生物學(xué)通報(bào)，1986.

[3]王穎，劉建平.基于改進(jìn)遺傳算法的kmeans聚類分析[J].工業(yè)控制計(jì)算機(jī)，2011.