蔡鵬飛,趙開新

(1.河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 新鄉(xiāng) 453003;2.河南省制造業(yè)物聯(lián)網(wǎng)應(yīng)用工程技術(shù)研究中心,河南 新鄉(xiāng) 453003)

0 引言

球員價(jià)值的評估是困擾俱樂部管理者多年的一道難題。在信息膨脹的時(shí)代,數(shù)據(jù)來源不斷豐富,數(shù)據(jù)規(guī)模迅速增加,數(shù)據(jù)讓球隊(duì)評估球員價(jià)值時(shí)可以更加嚴(yán)謹(jǐn)[1]。本文提出了一種改進(jìn)的K-Means聚類算法,把NBA球員的數(shù)據(jù)集中起來進(jìn)行分析,根據(jù)該算法的結(jié)果,可以實(shí)現(xiàn)對NBA球員價(jià)值的評估。

1 K-Means聚類算法

K-Means聚類算法是無監(jiān)督的聚類算法,它實(shí)現(xiàn)起來比較簡單,聚類效果也不錯(cuò),因此應(yīng)用得很廣泛。K-Means算法的思想很簡單:對于給定的樣本集,按照樣本之間的距離大小,將樣本集劃分為k個(gè)簇;讓簇內(nèi)的點(diǎn)盡量緊密地連在一起,而讓簇間的距離盡量地大。

K-Means算法使用間隔作為相似性的評估參數(shù),即意味著對象之間的間隔越近,其相似度越大[2]。K-Means算法認(rèn)為類簇是由間隔接近的對象組合的,所以該算法把獲得緊密和獨(dú)立的簇作為終極任務(wù)。在實(shí)際使用K-Means算法的時(shí)候需要掌握k值的大小,即聚類數(shù)量,以達(dá)到最終的聚類效果。K-Means聚類算法的流程如圖1所示。

圖1 K-Means聚類算法的流程圖

算法步驟為:

(1)在多個(gè)向量里任選出k個(gè)向量作為起始的聚類中心點(diǎn)。(2)以這k個(gè)中心點(diǎn)為參照點(diǎn),計(jì)算出數(shù)據(jù)集中所有對象和這些中心點(diǎn)各自的間距。(3)數(shù)據(jù)集每個(gè)向量和k個(gè)向量的間隔不同,把向量和距離它最近的中心點(diǎn)劃到一個(gè)類簇里。(4)重新計(jì)算每個(gè)類簇的中心點(diǎn)的位置。(5)重復(fù)第3步驟和第4步驟,直到類簇的聚類方案里的向量變化非常少時(shí)為止[3]。通常情況下,在完成迭代后,若是只有不到1%的向量還在聚類漂移,可認(rèn)定為完成聚類。

K-Means算法的主要缺點(diǎn)有:k值的選取不好把握;對于不是凸的數(shù)據(jù)集比較難收斂;如果各隱含類別的數(shù)據(jù)不平衡,比如各隱含類別的數(shù)據(jù)量嚴(yán)重失衡,或者各隱含類別的方差不同,則聚類效果不佳;采用迭代方法,得到的結(jié)果只是局部最優(yōu);對噪音和異常點(diǎn)比較敏感。

2 改進(jìn)的K-Means聚類算法

改進(jìn)的K-Means聚類算法步驟為:

(1)在數(shù)據(jù)集里的所有點(diǎn)中隨機(jī)選取一個(gè)點(diǎn)當(dāng)成種子點(diǎn)。(2)逐個(gè)計(jì)算出數(shù)據(jù)集里的每個(gè)點(diǎn)和種子點(diǎn)之間的間距D(x)。(3)選擇D(x)大的點(diǎn)作為新的種子點(diǎn)。(4)重復(fù)第2步驟和第3步驟直到新的種子被選出來。

對本算法而言,k的選取值相當(dāng)重要,因?yàn)榭稍诮o出不同k值的時(shí)候,通過比較重要評價(jià)參數(shù)的變化程度,選取出相對合理的k值。當(dāng)前主要的k值選取方法有拐點(diǎn)法和輪廓系數(shù)法。

拐點(diǎn)法比較簡單,選取不一樣的k值,并計(jì)算其簇內(nèi)離差的平方和,繪制出線性圖形,然后直觀地從圖中找出“拐點(diǎn)”以及其相對的k值。若簇的數(shù)量增加,則簇內(nèi)樣本的數(shù)量會變少,離差的平方和會變得更小[4]。

輪廓系數(shù)法的研究重點(diǎn)在于簇的密集和分散特性,把數(shù)據(jù)集劃分成理想狀態(tài)下的k個(gè)簇,則相應(yīng)簇內(nèi)的樣本數(shù)會變密集,同時(shí)簇之間的樣本數(shù)會分散。輪廓法的計(jì)算如公式(1)所示:

(1)

其中,a(i)表示簇內(nèi)密集程度,樣本i和相同簇內(nèi)別的樣本間距的平均值;b(i)表示簇間分散程度。計(jì)算方法為:樣本i和別的非同簇的樣本間距的平均值,之后從其中選取出最小的值。

本文分析拐點(diǎn)法和輪廓系數(shù)法的優(yōu)點(diǎn),在實(shí)際應(yīng)用中采用兩種方法綜合選取最佳k值。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境、數(shù)據(jù)來源

本文的實(shí)驗(yàn)環(huán)境硬件為:CPU,Intel(R)Core(TM)i3-7100@3.90GHz;內(nèi)存,8GB;操作系統(tǒng),Windows10。軟件編譯環(huán)境為Python3.8。

實(shí)驗(yàn)數(shù)據(jù)為NBA球員投籃情況的記錄,包含有球員姓名、隸屬球隊(duì)、每場得分和各種投球命中率等[5]。我們讀入數(shù)據(jù)并觀察其部分?jǐn)?shù)據(jù),部分?jǐn)?shù)據(jù)實(shí)例展示如表1所示。

表1 NBA球員數(shù)據(jù)集的部分?jǐn)?shù)據(jù)實(shí)例展示信息

在數(shù)據(jù)集中,具體參數(shù),如得分、命中率、上場次數(shù)和時(shí)間等均是數(shù)值類型的變量,經(jīng)觀察發(fā)現(xiàn)一些數(shù)據(jù)間的量綱有所區(qū)別,因此要對數(shù)據(jù)執(zhí)行標(biāo)準(zhǔn)化的處理流程。經(jīng)研究本文選取得分、命中率、三分球命中率以及罰球命中率這4個(gè)維度作為球員集合聚類的指標(biāo)參數(shù)[6]。

3.2 預(yù)處理

在Python編譯環(huán)境中,球員數(shù)據(jù)標(biāo)準(zhǔn)化通過sklearn子模塊的預(yù)處理中的scale函數(shù)和minmax_scale函數(shù)進(jìn)行實(shí)現(xiàn),scale函數(shù)和minmax_scale函數(shù)公式如(2)和(3)所示:

(2)

(3)

兩個(gè)公式中mean(x)指的是變量x的平均數(shù),std(x)為變量x的標(biāo)準(zhǔn)差,max(x)和min(x)分別為變量x的最大值與最小值。

3.3 數(shù)據(jù)可視化

實(shí)驗(yàn)過程如下:執(zhí)行數(shù)據(jù)標(biāo)準(zhǔn)化算法初步繪制球員的得分和命中率之間關(guān)系散點(diǎn)如圖2所示,并觀察散點(diǎn)數(shù)據(jù)的分布,執(zhí)行的算法如算法1所示。

算法1:數(shù)據(jù)標(biāo)準(zhǔn)化算法

(1)data←players,

(2)scatter_kws←{‘a(chǎn)lpha’:0.8,‘color’:‘steelblue’}

(3)sns.lmplot(x=‘得分’,y=‘命中率’, data, fit_reg=False, scatter_kws)

圖2 NBA球員得分和命中關(guān)系散點(diǎn)圖

3.4 聚類中心選擇

根據(jù)拐點(diǎn)法得出最佳k值,具體算法如算法2所示,并得到簇的個(gè)數(shù)圖,如圖3所示。

(1)X←preprocessing.minmax_scale(players[[‘得分’,‘罰球命中率’,‘命中率’,‘三分命中率’]])//數(shù)據(jù)標(biāo)準(zhǔn)化處理

(2)columns←[‘得分’,‘罰球命中率’,‘命中率’,‘三分命中率’]

(3)X←pd.DataFrame(X, columns)//將數(shù)組轉(zhuǎn)換為數(shù)據(jù)框

(4)k_SSE(X,15)//使用拐點(diǎn)法選擇最佳的k值

圖3 用拐點(diǎn)法計(jì)算得到的簇的個(gè)數(shù)

隨著簇?cái)?shù)的增加,簇內(nèi)離差平方和的總和在不斷減小,當(dāng)k值在4附近時(shí),折線斜率變動變得緩慢,因此k值的選定范圍是3或4。為了得到更精確的聚類結(jié)果,可以再通過輪廓系數(shù)法計(jì)算k值,對k值進(jìn)行進(jìn)一步的選擇[7]。采用輪廓系數(shù)法得到的簇的個(gè)數(shù)圖如圖4所示。

圖4 用輪廓系數(shù)法計(jì)算得到的簇的個(gè)數(shù)

從圖4可以看出,k值是2的時(shí)候?qū)?yīng)的系數(shù)最大,k值是3的時(shí)候?qū)?yīng)的系數(shù)次之,通過對兩種方法得到的k值進(jìn)行綜合考慮,本文把最佳聚類k確定為3。

然后使用最佳k值對NBA球員數(shù)據(jù)執(zhí)行聚類運(yùn)算,具體實(shí)現(xiàn)如算法3所示。

(1)kmeans←KMeans(n-clusters=3)//定義聚類為3類

(2)kmeans.fit(X)//訓(xùn)練模型

執(zhí)行上述代碼得到聚類后的數(shù)據(jù),再次畫出得分和命中率關(guān)系散點(diǎn)圖,通過散點(diǎn)圖直觀顯示和分析聚類結(jié)果和效果,具體實(shí)現(xiàn)如算法4所示。

(1)players[‘cluster’]←kmeans.labels//定義聚類為3類

(2)for i in players.cluster.unique():

(3)centers.append(players.loc[players.cluster==i,[‘得分’,‘罰球命中率’,‘命中率’,‘三分命中率’]].mean())

(4)centers←np.array(centers)

(5)sns.lmplot(x=‘得分’,y=‘命中率’,hue=‘cluster’,data=players)

(6)markers←[‘＾’, ‘s’, ‘o’]

(7)fit_reg←False

(8)scatter_kws←{‘a(chǎn)lpha’:0.8},legend=False)

(9)plt.scatter(centers[:,0],centers[:,2],c=‘k’,marker=‘*’,s=180)

(10)plt.xlabel(‘得分’)

(11)plt.ylabel(‘命中率’)

(12)plt.show()//圖形顯示

聚類后的散點(diǎn)圖如圖5所示。圖中的三個(gè)五角星的意思是每個(gè)簇的中心點(diǎn)[8]。相對于正方形和圓形點(diǎn)來說,其差異表現(xiàn)為命中率的差異,正方形表示的球員的得分情況和命中率情況都相對比較低,說明這類球員的實(shí)力較差,命中率普遍在50%以下;圓形表示的球員則是代表了得分較低但命中率較高的類型,說明這一類球員很有可能為新球員,新球員的實(shí)力較強(qiáng)但由于上場時(shí)長少所以得數(shù)較低。而正方形和三角形點(diǎn)之間的區(qū)別表現(xiàn)在得分項(xiàng)上,三角形點(diǎn)代表得分較高而命中率較低的類型,說明這一類球員的上場時(shí)間和投球次數(shù)都多[9]。一個(gè)好球員的標(biāo)準(zhǔn)就是命中率和得分這兩個(gè)數(shù)值都高,如圖5里左上角的幾個(gè)點(diǎn)表示的球員。需要注意的是,因本文在對數(shù)據(jù)集聚類前進(jìn)行了數(shù)據(jù)標(biāo)準(zhǔn)化,所以聚類圖的簇中心無法用cluater_centers_函數(shù)得到。

圖5 聚類后的散點(diǎn)圖

3.5 評估結(jié)果及分析

這三類球員的雷達(dá)示意圖如圖6所示,直觀比較一下這三類球員在四個(gè)參數(shù)上的區(qū)別。因四個(gè)參數(shù)在量綱上有區(qū)別,無法保持一致,所以本文采用標(biāo)準(zhǔn)化后的簇中心畫出雷達(dá)圖,具體實(shí)現(xiàn)如算法5所示。

(1)centers_std←kmeans.cluster_centers

(2)radar_chart←pygal.Radar(fill=True)

(3)radar_chart.x_labels←[‘得分’,‘罰球命中率’,‘命中率’,‘三分命中率’]

(4)radar_chart.add(‘C1’,centers_std[0])

(5)radar_chart.add(‘C2’,centers_std[1])

(6)radar_chart.add(‘C3’,centers_std[2])

(7)radar_chart.render_to_file(‘radar_-chart.svg’)//保存圖片

圖6 三類球員雷達(dá)圖

三類球員在每個(gè)維度都有差別,以C2和C3來說明,他們的平均得分并沒有顯著差異,但是C3的命中率卻明顯比C2高很多;再從平均的罰球命中率與三分命中率來看,C2普遍要比C3要強(qiáng)一些。

4 總結(jié)

本文提出了一種改進(jìn)的K-Means聚類算法,在一個(gè)NBA球員數(shù)據(jù)集中進(jìn)行聚類實(shí)現(xiàn),通過觀察聚類的結(jié)果,可以對比球員的特點(diǎn),評估球員的價(jià)值,在實(shí)際應(yīng)用中可以輔助球隊(duì)挑選人才。與傳統(tǒng)方法相比,該聚類方法功能更豐富,應(yīng)用更靈活。這個(gè)算法對于異常的點(diǎn)較敏感,其中心點(diǎn)是通過樣本均值確定的。假如聚類數(shù)的量綱不同,就需要進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化。如果數(shù)據(jù)中含有離散型的字符變量,就需要對該變量做預(yù)處理,如設(shè)置為啞變量或轉(zhuǎn)換成數(shù)值化的因子。下一步工作主要研究對未知聚類個(gè)數(shù)的數(shù)據(jù)集采用探索方法以尋找最佳k值。