基于改進K-Means聚類算法的NBA球員價值評估*

蔡鵬飛,趙開新

(1.河南工學院 計算機科學與技術學院,河南 新鄉 453003;2.河南省制造業物聯網應用工程技術研究中心,河南 新鄉 453003)

0 引言

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

1 K-Means聚類算法

K-Means聚類算法是無監督的聚類算法,它實現起來比較簡單,聚類效果也不錯,因此應用得很廣泛。K-Means算法的思想很簡單:對于給定的樣本集,按照樣本之間的距離大小,將樣本集劃分為k個簇;讓簇內的點盡量緊密地連在一起,而讓簇間的距離盡量地大。

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

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

算法步驟為:

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

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

2 改進的K-Means聚類算法

改進的K-Means聚類算法步驟為:

(1)在數據集里的所有點中隨機選取一個點當成種子點。(2)逐個計算出數據集里的每個點和種子點之間的間距D(x)。(3)選擇D(x)大的點作為新的種子點。(4)重復第2步驟和第3步驟直到新的種子被選出來。

對本算法而言,k的選取值相當重要,因為可在給出不同k值的時候,通過比較重要評價參數的變化程度,選取出相對合理的k值。當前主要的k值選取方法有拐點法和輪廓系數法。

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

輪廓系數法的研究重點在于簇的密集和分散特性,把數據集劃分成理想狀態下的k個簇,則相應簇內的樣本數會變密集,同時簇之間的樣本數會分散。輪廓法的計算如公式(1)所示:

(1)

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

本文分析拐點法和輪廓系數法的優點,在實際應用中采用兩種方法綜合選取最佳k值。

3 實驗

3.1 實驗環境、數據來源

本文的實驗環境硬件為:CPU,Intel(R)Core(TM)i3-7100@3.90GHz;內存,8GB;操作系統,Windows10。軟件編譯環境為Python3.8。

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

表1 NBA球員數據集的部分數據實例展示信息

在數據集中,具體參數,如得分、命中率、上場次數和時間等均是數值類型的變量,經觀察發現一些數據間的量綱有所區別,因此要對數據執行標準化的處理流程。經研究本文選取得分、命中率、三分球命中率以及罰球命中率這4個維度作為球員集合聚類的指標參數[6]。

3.2 預處理

在Python編譯環境中,球員數據標準化通過sklearn子模塊的預處理中的scale函數和minmax_scale函數進行實現,scale函數和minmax_scale函數公式如(2)和(3)所示:

(2)

(3)

兩個公式中mean(x)指的是變量x的平均數,std(x)為變量x的標準差,max(x)和min(x)分別為變量x的最大值與最小值。

3.3 數據可視化

實驗過程如下:執行數據標準化算法初步繪制球員的得分和命中率之間關系散點如圖2所示,并觀察散點數據的分布,執行的算法如算法1所示。

算法1:數據標準化算法

(1)data←players,

(2)scatter_kws←{‘alpha’:0.8,‘color’:‘steelblue’}

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

圖2 NBA球員得分和命中關系散點圖

3.4 聚類中心選擇

根據拐點法得出最佳k值,具體算法如算法2所示,并得到簇的個數圖,如圖3所示。

(1)X←preprocessing.minmax_scale(players[[‘得分’,‘罰球命中率’,‘命中率’,‘三分命中率’]])//數據標準化處理

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

(3)X←pd.DataFrame(X, columns)//將數組轉換為數據框

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

圖3 用拐點法計算得到的簇的個數

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

圖4 用輪廓系數法計算得到的簇的個數

從圖4可以看出,k值是2的時候對應的系數最大,k值是3的時候對應的系數次之,通過對兩種方法得到的k值進行綜合考慮,本文把最佳聚類k確定為3。

然后使用最佳k值對NBA球員數據執行聚類運算,具體實現如算法3所示。

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

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

執行上述代碼得到聚類后的數據,再次畫出得分和命中率關系散點圖,通過散點圖直觀顯示和分析聚類結果和效果,具體實現如算法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←{‘alpha’: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()//圖形顯示

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

圖5 聚類后的散點圖

3.5 評估結果及分析

這三類球員的雷達示意圖如圖6所示,直觀比較一下這三類球員在四個參數上的區別。因四個參數在量綱上有區別,無法保持一致,所以本文采用標準化后的簇中心畫出雷達圖,具體實現如算法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 三類球員雷達圖

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

4 總結

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