基于AdaBoost的某競技游戲得分預測的應用

(云南財經大學 云南 昆明 650221)

一、機器學習概述

主流的機器學習算法包括支持向量機、神經網絡、集成學習和邏輯回歸。本節對這些算法的基本原理進行簡要介紹。

(一)支持向量機

支持向量機(SupportVectorMachines，SVM)，其早期工作來自前蘇聯學者VladimirN.Vapnik和AlexanderY.Lerner在1963年發表的研究，是一類按監督學習方式對數據進行分類的廣義線性分類器。其核心思想即，二維數據分布在樣本空間上，由一個超平面對多維數據進行分割，這個平面叫做分類的決策邊界，支持向量就是離決策邊界最近的一些點，支持向量機的目的就是最大化支持向量到決策邊界的距離，從而，如果數據犯錯的話，分類器會盡可能的健壯。

當遇到多維或者復雜數據時，就需要引用核函數將數據轉換成易于分類器理解的形式，其中最流行的一種成為徑向基函數(radialbasisfunction)，利用核函數講數據映射到高維空間，可以將在低維空間中的非線性問題轉換成高維空間下的線性問題來求解。支持向量機是一個二分類器，當用其解決多分類問題時，則需要額外的方法對其進行擴展。SVM效果取決于優化參數和和函數中的參數設置。

(二)神經網絡

1958年，計算科學家Rosenblatt提出了由兩層神經元組成的神經網絡。他給它起了一個名字——“感知器”(Perceptron)，也就是單層神經網絡，它由一個輸入層和輸出層組成，每一個特征屬于代表一個神經單元，輸入層只負責傳輸數據，不做計算。在輸出層則需要對前一層的數據進行計算，連接輸入層和輸出層的帶有箭頭的線表示一個權重，預測值則是輸入和權值之間的線性加權和疊加了一個激活函數g的值，即Z=g(W*a)，在單層神經網絡中，g函數使用sgn函數，也就是取符號函數。這個函數當輸入大于0時，輸出1，否則輸出0。

但是Minsky在1969年出版了一本叫《Perceptron》的書，里面用詳細的數學證明了單層神經網絡的弱點，尤其是對異或這樣的簡單分類任務都無法解決[2]。

兩層神經網絡，在單層神經網絡基礎上，增加一個中間層，此時，中間層和輸出層都是計算層，激活函數也由sgn變為sigmoid。我們將yp作為預測值，y為真實值，將loss=(yp-y)2定義為損失函數，因此我們做的工作就是讓loss值盡可能的小，一般采用梯度下降法，直到梯度接近零，在神經網絡中，由于結構復雜，每次計算梯度的代價很大。因此1986年，Rumelhar和Hinton等人提出了反向傳播(Backpropagation，BP)算法，解決了兩層神經網絡所需要的復雜計算量問題。也就是經典的BP神經網絡，反向傳播法利用神經網絡的結構，首先計算輸出層的梯度，然后是第二個參數梯度，接著計算中間層梯度，再然后計算第一個參數的梯度，最后計算輸入層梯度。盡管使用了BP算法，一次神經網絡的訓練仍然耗時太久，而且困擾訓練優化的一個問題就是局部最優解問題，這使得神經網絡的優化較為困難。同時，隱藏層的節點數需要調參，這使得使用不太方便。

多層神經網絡，隨著計算機硬件性能提升(如GPU圖形加速卡)，在二層的基礎上，中間層的層次繼續擴張，參數也隨之增加，通過研究和實踐發現，更深的網絡層次往往比淺層有更好的識別率，這點在ImageNet大賽上獲得的證實。因為通過每一層，對前一層的抽象表示更加深入。ReLU函數(f(x)=max(0，x))在訓練多層神經網絡時，更容易收斂，并且預測性能更好。

(三)集成學習

俗話說，三個臭皮匠頂個諸葛亮，這就是元算法的思路，集成學習就是對其它算法進行組合的一種學習方式。集成方法主要包括Bagging和Boosting兩種方法。Bagging方法即在原始樣本中，根據Bootstraping方法，隨機抽取一部分數據集作為訓練數據，一共抽取K次，每一次的訓練集訓練出一個模型，一共訓練出K個模型，最后再由K個模型投票得出結果，如果是對于回歸問題，則計算K個模型的均值為最后的結果[3]。Boosting則是每一輪訓練集相同，但是會賦予訓練集一個權重，根據模型的錯誤率來調整權值，錯誤率越高，權值越高。其中具有代表性的AdaBoost分類器，具有泛化錯誤率低，可以應用在大部分分類器上，無需調參。但是對離群點敏感等特點。

二、數據說明

本文數據來自國內某款流行競技游戲官網RiotAPI中，通過玩家ID獲取到前十分鐘的游戲狀態數據，玩家水平控制在一定范圍，即代表玩家水平大致相同。本數據集收集了共19項狀態數據，一共38項(紅藍兩方玩家)。

數據集狀態屬性包括19項，共38個，分別是blueWardsPlacedDestroyed，blueFirstBlood，blueKills，blueDeaths，blueAssists，blueEliteMonsters，blueDragons，blueHeralds，blueTowersDestroyed，blueTotalGold，blueAvgLevel，blueTotalExperience，blueTotalMinionsKilled，blueTotalJungleMinionsKilled，blueGoldDiff，blueExperienceDiff，blueCSPerMin，blueGoldPerMin。以上狀態特征除blueFirstBlood為分類變量，1為是，0為否，其它均為連續變量。目標變量為blueWins，是否取勝。數據集一共包括9879個樣本。

三、得分預測

(一)數據處理步驟

1.讀取數據

使用python中的csv包，讀取樣本數據文件‘high_diamond_ranked_10min.csv’，同時引用numpy包，創建訓練數據矩陣和標簽矩陣，遍歷樣本數據，將特征一一讀取到訓練舉證，同時讀取每一個樣本數據中的標簽，將其添加到標簽矩陣。自此，已經建立了訓練數據。接著我們分析該矩陣的數據特點。

2.歸一化

由于blueTotalGold，blueAvgLevel，blueTotalExperience，blueTotalMinionsKilled，blueTotalJungleMinionsKilled，blueGoldDiff等幾個特征數值偏大，有的甚至是周圍值的幾千倍，不同指標往往具有不同的量綱和量綱單位，這樣的情況會影響到數據分析的結果，為了消除指標之間的量綱影響，需要進行數據標準化處理。在本文中，采取將數據做線性變換，使結果值映射到[0-1]之間。

經過歸一化處理后，各指標處于同一數量級，便于綜合對比。同時，求最優解的過程會變得平緩，更容易正確收斂。即能提高梯度下降求最優解時的速度，提高計算精度。此過程使用SK-Learn包中的preprocession函數完成。自此數據處理大致完成，如果還需要調整的話，可以根據實驗最后的精度來做下一步分析。

預測模型

本文采用泛化程度較高的AdaBoost分類器來完成預測工作。其偽代碼如下：

對每次迭代：

利用buildStump()函數找到最佳的單層決策樹

將最佳單層決策樹加入到單層決策樹組

計算alpha

計算新的權重向量D

更新累計類別估計值

如果錯誤率等于0，則退出循環

使用SK-Learn中的AdaBoost模型，分類器選取DecisionTreeClassifier，最后，訓練結果如圖所示：

結果解釋：可以看到使用AdaBoost模型，參數取以上值時，通過交叉驗證，最佳參數為，決策樹參數最高3層，其它參數由于樣本特征，均為默認值，基分類器提升(循環)次數n_estimators為1000次，模型提升準則選擇SAMME。AdaBoost其它參數均為默認值。分類器在訓練集上的錯誤率為26.26%，在測試集上錯誤率為27.46%，可以看出并沒有過擬合，模型擬合效果比較合適。整體預測準確率為72.5%。

四、預測模型的評價

在機器學習算法中，模型本身所需要的假設比較少，相應地，對模型進行評價的工具也不多，通常只能通過對模型的預測結果與真實結果進行比較來判斷模型的預測精度。

在本文中，得分預測是屬于分類問題。對于分類問題，預測精度的評價指標主要有查全率和查準率，AUC值和F值。

混淆矩陣

模型的精度，即模型預測正確的個數/樣本的總個數

召回率，真正類率，表示的是，模型預測為正類的樣本的數量，占總的正類樣本數量的比值:

一般情況下，Recall越高，說明有更多的正類樣本被模型預測正確，模型的效果越好。除了上述的評價指標，另一個用于度量分類中的非均衡的工具是ROC曲線(ROC curve)。

本分類器ROC曲線如下圖：

ROC曲線是從[0，0]到[1，1]的上凸曲線。ROC曲線越趨近于左上角的[0，1]點，說明分類器的效果越好。ROC 曲線下方的面積稱為AUC值，AUC介于0到1之間，當AUC小于0.5時，說明分類器的效果不如隨機預測的效果; AUC 越接近于1，說明分類器的效果越好。本實驗中，隨機將樣本集劃分6次，平均AUC值如圖所示，為0.81，證明模型能夠有效預測比賽勝負。

五、小結

通過實驗，可以證明基于AdaBoost模型的某競技游戲勝負分類器是有效的，平均AUC為0.81左右，不同的訓練模型對數據的擬合效果有時差距是非常大的，所以本文后續工作還可以應用更加合適的模型來提高其精度，比如可以利用回歸分析，對特征相關度進行分析，根據分析適當增加或降低模型復雜度，可以提高分類準確率，本文由于篇幅有限，不再做贅述。

電子競技是隨著行業越來越規范和飛速發展，無論是個人電腦端還是手機端，每天都有大量的數據產生，本文僅對其中游戲類中的一個小方向做了簡單分析。機器學習，深度學習，強化學習模型作為一種工具已經在許多領域取得了良好的應用效果，如語音，圖片識別，自然語言處理等領域中大放光彩。去年，騰訊AILab實驗室研發的虛擬角色在2100場游戲對抗中，取得了99,8%的獲勝率，讓我們的認知不僅僅停留在alphaGo大戰圍棋高手，而電子競技作為一項體育運動，不論在專業領域和普通玩家中，都深受喜愛，從前文的報告中，在2020年，電競整體規模有望達到1300億元，但是相關研究并沒有成型，希望本文是拋磚引玉，今后的學習中能夠有更多的研究應用到電競行業。最后，機器學習以及其后面一系列學習模型算法作為一種新興的預測模型，在電子競技行業具有廣闊的應用前景，對于提升用戶游戲體驗度，增強用戶黏性，完善游戲內部機制，改善游戲生態有著重要的應用價值。