基于KNN的RoboCup傳球模式識(shí)別研究

李 旭，程澤凱，蘇 麗，郭金波，陳俊品

(安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243031)

機(jī)器人世界杯(RoboCup)是一項(xiàng)級(jí)別高、規(guī)模大、影響廣泛的國(guó)際機(jī)器人賽事，比賽設(shè)想最早由Alan Mackworth在1992年[1]中提出．其初衷是引入足球競(jìng)技，為人工智能和智能機(jī)器人學(xué)科研究提供一個(gè)支持多智能體動(dòng)態(tài)對(duì)抗的標(biāo)準(zhǔn)化平臺(tái)，促進(jìn)人工智能相關(guān)領(lǐng)域的發(fā)展．仿真2D作為機(jī)器人世界杯2050計(jì)劃的重要一環(huán)，主要關(guān)注多智能體協(xié)同和團(tuán)隊(duì)決策的制定．

近年來(lái)各支球隊(duì)基于數(shù)據(jù)挖掘的思想，構(gòu)建球隊(duì)畫(huà)像，改進(jìn)球員決策，取得了很多成就，但對(duì)于傳球模式這一分支的研究較少．本文先對(duì)球場(chǎng)進(jìn)行區(qū)域劃分和篩選，得到三個(gè)有效區(qū)域，然后解析日志文件，提取傳球特征，最后采用KNN算法挖掘分析傳球特征，得到不同球隊(duì)的傳球模式．針對(duì)不同球隊(duì)傳球模式間差異采用不同的應(yīng)對(duì)策略，為球隊(duì)的決策改良提供理論指導(dǎo)．

1 問(wèn)題的提出

基于RoboCup仿真2D平臺(tái)，各支球隊(duì)的發(fā)展歷程是一個(gè)迭代增量式開(kāi)發(fā)過(guò)程，研發(fā)方向的不同使得不同球隊(duì)有著不同的進(jìn)攻和防守策略．基于數(shù)據(jù)挖掘和建模的思想，前人曾做過(guò)有關(guān)傳球、球員跑位、邊界球、球員陣型、評(píng)估函數(shù)等方面的研究．例如秦鋒等對(duì)比賽日志文件中的傳球信息進(jìn)行挖掘，采用最小二乘法探究對(duì)勝負(fù)影響最大的傳球類型[2]；宋園等挖掘分析日志文件，探究球隊(duì)的進(jìn)攻跑位策略優(yōu)化[3];余培利用相關(guān)性分析找尋邊界球分布對(duì)球隊(duì)勝敗的影響[4];陳梅等利用密度峰值聚類算法對(duì)球隊(duì)陣型進(jìn)行研究[5]；Takuya Fukushima等采用五層神經(jīng)網(wǎng)絡(luò)作為評(píng)估函數(shù)，用不同的特征來(lái)檢驗(yàn)球員的表現(xiàn)，指導(dǎo)球員決策的制定[6]．

在仿真2D平臺(tái)環(huán)境下，傳球是球員的基礎(chǔ)動(dòng)作之一，作為聯(lián)系全隊(duì)球員的紐帶，對(duì)比賽勝負(fù)起著至關(guān)重要的作用．比賽中與傳球相關(guān)聯(lián)的因素有很多，例如傳球數(shù)、傳球距離、傳球區(qū)域、傳接球球員等，本文選取傳球數(shù)、傳球距離和傳球區(qū)域作為研究對(duì)象．

2 研究方法

本文使用KNN算法挖掘分析比賽日志文件中的球員傳球信息，得到不同球隊(duì)的傳球模式并進(jìn)行分類，配合使用交叉驗(yàn)證、距離度量和加權(quán)多數(shù)表決等方法．

2.1 KNN算法

KNN即K近鄰，全稱為K-Nearest Neighbor，是一個(gè)經(jīng)典的數(shù)據(jù)挖掘分類算法．KNN的應(yīng)用場(chǎng)景十分廣泛，例如鐘建敏等利用KNN算法對(duì)傳感器采集到的手部動(dòng)作數(shù)據(jù)進(jìn)行初步分類[7]；陳朝文將KNN算法用于高速列車車內(nèi)壓力的模糊控制[8]；王海濤等使用基于中心向量的KNN分類方法提取非結(jié)構(gòu)數(shù)據(jù)的城市屬性信息[9]．

KNN算法的思路是選取K個(gè)和樣本距離最近(即最相似)的樣例，根據(jù)選取樣例所屬類別的情況，決定該樣本所屬的類別．KNN作為機(jī)器學(xué)習(xí)入門(mén)算法，分類思路簡(jiǎn)單明確．使用時(shí)需要關(guān)注：如何選取最佳的K值、距離度量與分類決策方法來(lái)搭建高效能的KNN分類模型．

2.2 K值選取

K值較小，表示預(yù)測(cè)結(jié)果取決于較少的樣例點(diǎn)，帶來(lái)較小訓(xùn)練誤差的同時(shí)使得模型變得復(fù)雜，容易導(dǎo)致過(guò)擬合的情況；K值較大，表示預(yù)測(cè)結(jié)果取決于較多的樣例點(diǎn)，帶來(lái)較大訓(xùn)練誤差的同時(shí)使得模型變得簡(jiǎn)單，容易導(dǎo)致欠擬合的情況．對(duì)于最佳K值的選取，通常使用交叉驗(yàn)證法，選擇一個(gè)較小K值作為初值，不斷增大K值，計(jì)算每個(gè)K值對(duì)應(yīng)的驗(yàn)證集均方誤差，從中選擇一個(gè)最佳的最終值．

交叉驗(yàn)證(Cross Validation)在機(jī)器學(xué)習(xí)領(lǐng)域主要用于檢測(cè)分類器的性能．它的基本思路是按某種意義將原始數(shù)據(jù)分為驗(yàn)證集和訓(xùn)練集，驗(yàn)證集用作測(cè)試，訓(xùn)練集用作模型訓(xùn)練，最后根據(jù)模型測(cè)試結(jié)果對(duì)分類器性能優(yōu)劣進(jìn)行合理評(píng)價(jià)．本文使用K折交叉驗(yàn)證法來(lái)檢驗(yàn)KNN分類器模型．

K折交叉驗(yàn)證法會(huì)對(duì)原始數(shù)據(jù)進(jìn)行隨機(jī)劃分，將完整的數(shù)據(jù)集等分成K份，每次取其中1份作為驗(yàn)證集，剩余K-1份作為訓(xùn)練集．進(jìn)行K次交叉驗(yàn)證，記錄每次的均方誤差，對(duì)K次均方誤差取平均值作為評(píng)價(jià)最終模型性能的指標(biāo)．K折交叉驗(yàn)證法的均方誤差公式為：

(1)

式中k是數(shù)據(jù)子集劃分的數(shù)量，MSEi是每份訓(xùn)練集訓(xùn)練得到的模型在驗(yàn)證集上的均方誤差，MSE是模型最終的均方誤差．

2.3 距離度量方法

2.3.1 歐幾里得距離

歐幾里得距離用于指代兩個(gè)n維向量間的真實(shí)距離，值為兩向量各坐標(biāo)差值平方和的算術(shù)平方根．歐幾里得距離廣泛應(yīng)用于數(shù)字圖像處理領(lǐng)域，經(jīng)典的歐氏距離變換可作為圖像骨架提取時(shí)的參照[10]．

假設(shè)存在n維向量X(x1，x2，…，xn)和Y(y1，y2，…，yn)，它們的歐氏距離求解方法如下：

(2)

2.3.2 曼哈頓距離

曼哈頓距離用于指代兩個(gè)n維向量間的L1距離，值為兩向量各坐標(biāo)差值的絕對(duì)值和．

假設(shè)存在n維向量X(x1，x2，…，xn)和Y(y1，y2，…，yn)，它們的曼哈頓距離求解方法如下：

(3)

2.3.3 切比雪夫距離

切比雪夫距離用于指代兩個(gè)n維向量間的L∞距離，值為兩向量各坐標(biāo)差絕對(duì)值的最大值．

假設(shè)存在n維向量X(x1，x2，…，xn)和Y(y1，y2，…，yn)，它們的切比雪夫距離求解方法如下：

d(X，Y)=max(|x1-x2|，|y1-y2|，…，|xn-yn|)

(4)

2.4 分類決策規(guī)則

決定了最佳的K值和距離度量方式后，可以從特征空間中找出與測(cè)試樣例最近(即最相似)的K個(gè)樣本，如何依靠K個(gè)樣本的特點(diǎn)確定測(cè)試樣例所屬類別就是分類決策規(guī)則．KNN模型的分類決策通常采用多數(shù)表決法和加權(quán)多數(shù)表決法．

多數(shù)表決法不考慮樣本權(quán)重，只考慮樣本數(shù)量，模型最終的預(yù)測(cè)結(jié)果取決于鄰近樣本中不同類別的數(shù)量．加權(quán)多數(shù)表決法彌補(bǔ)了多數(shù)表決法的不足，同時(shí)考慮樣本數(shù)量和樣本權(quán)重，通常樣本權(quán)重根據(jù)距離反比計(jì)算，鄰近樣本中權(quán)值最大的那個(gè)類就是模型最終的預(yù)測(cè)結(jié)果．

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)建模

首先將球場(chǎng)劃分為三個(gè)有效區(qū)域使得傳球的橫、縱坐標(biāo)離散化，再通過(guò)解析日志文件提取出對(duì)方球隊(duì)的傳球數(shù)、平均傳球距離和三個(gè)有效區(qū)域的傳球數(shù)作為傳球特征，將傳球信息按上述傳球特征抽象成向量，由此構(gòu)造訓(xùn)練所需的數(shù)據(jù)集．

3.1.1 球場(chǎng)劃分

仿真2D的球場(chǎng)總長(zhǎng)度105 m，總寬度68 m．傳球的橫坐標(biāo)和縱坐標(biāo)均是連續(xù)型變量，為了將其離散化，將球場(chǎng)劃分為不同區(qū)域．本文將球場(chǎng)劃分為CrossBlock、DribbleField、CrossAttack、Danger、MidField、ShootChance六個(gè)區(qū)域．考慮到Danger區(qū)域比賽中傳球數(shù)很少，誤差較大；CrossAttack和ShootChance區(qū)域與我方球隊(duì)關(guān)聯(lián)性較大，不能很好地反映對(duì)方球隊(duì)傳球特征；最終選取CrossBlock、DribbleField、MidField三個(gè)區(qū)域作為傳球有效區(qū)域．球場(chǎng)區(qū)域(圖1)以及每個(gè)有效區(qū)域坐標(biāo)范圍見(jiàn)表1.

圖1 球場(chǎng)區(qū)域劃分

表1 有效區(qū)域劃分范圍

3.1.2 日志文件的解析

RoboCup仿真2D的比賽進(jìn)程由Soccer Server實(shí)時(shí)控制和記錄，比賽結(jié)束時(shí)Server會(huì)產(chǎn)生相應(yīng)的比賽日志文件，分為rcg后綴名文件和rcl后綴名文件．rcg文件由當(dāng)前周期、球信息和球員信息等部分組成，rcl文件包含具體的裁判命令信息．傳統(tǒng)RoboCup數(shù)據(jù)挖掘使用rcg和rcl文件作為數(shù)據(jù)源，從中挖掘具有潛在價(jià)值的信息．

本文使用Python語(yǔ)言解析單場(chǎng)比賽的rcg文件和rcl文件，提取對(duì)方在比賽中的每次傳球信息，包括傳球周期、傳球源點(diǎn)、傳球目標(biāo)點(diǎn)和傳球距離(采用傳球源點(diǎn)與傳球目標(biāo)點(diǎn)間直線距離，即歐幾里得距離，以便與現(xiàn)實(shí)世界中人類對(duì)距離的感知保持一致)．部分比賽解析結(jié)果示例如表2．

表2 部分比賽解析結(jié)果示例

3.1.3 數(shù)據(jù)集的構(gòu)造

為了研究傳球特征與隊(duì)伍間的關(guān)系，本文選取安徽工業(yè)大學(xué)的YuShan隊(duì)與Fractals2019、HELIOS2019、CYRUS2019三支隊(duì)伍總共2 102場(chǎng)比賽的日志文件作為數(shù)據(jù)源，對(duì)上文的球場(chǎng)區(qū)域劃分與比賽日志文件解析結(jié)果進(jìn)行匯總，提取每場(chǎng)比賽對(duì)方隊(duì)伍的傳球數(shù)、平均傳球距離、CrossBlock(記為CB)區(qū)域傳球數(shù)、DribbleField(記為DF)區(qū)域傳球數(shù)和MidField(記為MF)區(qū)域傳球數(shù)共五個(gè)特征，與標(biāo)識(shí)信息隊(duì)伍編號(hào)一起寫(xiě)入csv文件中，其中三個(gè)有效區(qū)域的傳球數(shù)由傳球目標(biāo)點(diǎn)與有效區(qū)域劃分范圍共同得出，得到的部分csv文件如表3所示．

表3 部分csv文件

3.2 KNN分類模型的建立

本文利用七折交叉驗(yàn)證法，將上文構(gòu)造的傳球特征數(shù)據(jù)集隨機(jī)等分成七份，每次將其中的一份用作驗(yàn)證，剩余的七份用作訓(xùn)練，記錄訓(xùn)練得到的模型在驗(yàn)證集上的錯(cuò)誤率，取七次平均值作為最終模型性能的評(píng)價(jià)指標(biāo)．K從1開(kāi)始選取，不斷增加K的值，記錄每個(gè)K值對(duì)應(yīng)的錯(cuò)誤率，得到的K值與錯(cuò)誤率關(guān)系曲線圖(圖2)．

圖2 K值與錯(cuò)誤率關(guān)系曲線圖

從上圖可以看出，K值為21時(shí)誤差最?。虼?，本文選取21作為最佳K值，使用歐氏距離、切比雪夫距離和曼哈頓距離組合度量特征空間內(nèi)樣本點(diǎn)與測(cè)試樣例間距離，篩選同測(cè)試樣例最相近的21個(gè)樣本點(diǎn)，最后使用距離反比加權(quán)多數(shù)表決法確定測(cè)試樣例的所屬類別．根據(jù)上述三要素搭建的KNN模型的傳球模式識(shí)別成功率如表4．

表4 傳球模式識(shí)別成功率

4 球隊(duì)決策優(yōu)化

為直觀感受不同球隊(duì)傳球信息間差異，為球隊(duì)決策優(yōu)化提供理論指導(dǎo)．本文使用Python的Matplotlib庫(kù)對(duì)Fractals2019、HELIOS2019、CYRUS2019三支隊(duì)伍各10場(chǎng)的傳球信息進(jìn)行了可視化處理，繪制球隊(duì)傳球路線圖(圖3)．

圖3 球隊(duì)傳球路線圖

在球隊(duì)傳球路線圖中，每條線段表示一次完整的傳球動(dòng)作，包含開(kāi)始點(diǎn)和結(jié)束點(diǎn)．根據(jù)線段的疏密分布情況，可以看出不同傳球模式下的主要進(jìn)攻路徑和進(jìn)攻區(qū)域．結(jié)合圖3繪制的不同傳球模式下的主要進(jìn)攻路徑和進(jìn)攻區(qū)域如圖4所示．

圖4 不同傳球模式下的主要進(jìn)攻路徑和進(jìn)攻區(qū)域

圖4中箭頭所指方向代表對(duì)方的進(jìn)攻方向，箭頭構(gòu)成的路徑是對(duì)方的主要進(jìn)攻路徑，箭頭所在的區(qū)域是對(duì)方的主要進(jìn)攻區(qū)域．比賽時(shí)實(shí)時(shí)采集對(duì)方球隊(duì)的傳球信息，利用KNN分類模型識(shí)別對(duì)方球隊(duì)的傳球模式，根據(jù)不同傳球模式下的主要進(jìn)攻路徑和進(jìn)攻區(qū)域，調(diào)配己方的防守球員進(jìn)行針對(duì)性防守，優(yōu)化球隊(duì)的防守決策．應(yīng)用防守策略前和應(yīng)用防守策略后的球隊(duì)與三支隊(duì)伍在仿真2D平臺(tái)下進(jìn)行比賽，比賽結(jié)果如表5．

表5 比賽結(jié)果

從表5可以看出，球隊(duì)?wèi)?yīng)用防守策略后對(duì)三支球隊(duì)的勝率均有提升，驗(yàn)證了傳球模式識(shí)別用于球隊(duì)決策改良的可行性和正確性．

本文使用KNN分類模型，以數(shù)據(jù)挖掘?yàn)橹饕枷?，探究傳球模式與球隊(duì)決策之間的關(guān)系．該分類模型對(duì)于實(shí)際比賽的啟示是，根據(jù)對(duì)方球隊(duì)的主要進(jìn)攻區(qū)域和進(jìn)攻路徑，合理調(diào)配己方的防守球員進(jìn)行針對(duì)性防守，優(yōu)化球隊(duì)的防守策略．