基于KNN的RoboCup传球模式识别研究

李 旭，程泽凯，苏 丽，郭金波，陈俊品

(安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243031)

机器人世界杯(RoboCup)是一项级别高、规模大、影响广泛的国际机器人赛事，比赛设想最早由Alan Mackworth在1992年[1]中提出．其初衷是引入足球竞技，为人工智能和智能机器人学科研究提供一个支持多智能体动态对抗的标准化平台，促进人工智能相关领域的发展．仿真2D作为机器人世界杯2050计划的重要一环，主要关注多智能体协同和团队决策的制定．

近年来各支球队基于数据挖掘的思想，构建球队画像，改进球员决策，取得了很多成就，但对于传球模式这一分支的研究较少．本文先对球场进行区域划分和筛选，得到三个有效区域，然后解析日志文件，提取传球特征，最后采用KNN算法挖掘分析传球特征，得到不同球队的传球模式．针对不同球队传球模式间差异采用不同的应对策略，为球队的决策改良提供理论指导．

1 问题的提出

基于RoboCup仿真2D平台，各支球队的发展历程是一个迭代增量式开发过程，研发方向的不同使得不同球队有着不同的进攻和防守策略．基于数据挖掘和建模的思想，前人曾做过有关传球、球员跑位、边界球、球员阵型、评估函数等方面的研究．例如秦锋等对比赛日志文件中的传球信息进行挖掘，采用最小二乘法探究对胜负影响最大的传球类型[2]；宋园等挖掘分析日志文件，探究球队的进攻跑位策略优化[3];余培利用相关性分析找寻边界球分布对球队胜败的影响[4];陈梅等利用密度峰值聚类算法对球队阵型进行研究[5]；Takuya Fukushima等采用五层神经网络作为评估函数，用不同的特征来检验球员的表现，指导球员决策的制定[6]．

在仿真2D平台环境下，传球是球员的基础动作之一，作为联系全队球员的纽带，对比赛胜负起着至关重要的作用．比赛中与传球相关联的因素有很多，例如传球数、传球距离、传球区域、传接球球员等，本文选取传球数、传球距离和传球区域作为研究对象．

2 研究方法

本文使用KNN算法挖掘分析比赛日志文件中的球员传球信息，得到不同球队的传球模式并进行分类，配合使用交叉验证、距离度量和加权多数表决等方法．

2.1 KNN算法

KNN即K近邻，全称为K-Nearest Neighbor，是一个经典的数据挖掘分类算法．KNN的应用场景十分广泛，例如钟建敏等利用KNN算法对传感器采集到的手部动作数据进行初步分类[7]；陈朝文将KNN算法用于高速列车车内压力的模糊控制[8]；王海涛等使用基于中心向量的KNN分类方法提取非结构数据的城市属性信息[9]．

KNN算法的思路是选取K个和样本距离最近(即最相似)的样例，根据选取样例所属类别的情况，决定该样本所属的类别．KNN作为机器学习入门算法，分类思路简单明确．使用时需要关注：如何选取最佳的K值、距离度量与分类决策方法来搭建高效能的KNN分类模型．

2.2 K值选取

K值较小，表示预测结果取决于较少的样例点，带来较小训练误差的同时使得模型变得复杂，容易导致过拟合的情况；K值较大，表示预测结果取决于较多的样例点，带来较大训练误差的同时使得模型变得简单，容易导致欠拟合的情况．对于最佳K值的选取，通常使用交叉验证法，选择一个较小K值作为初值，不断增大K值，计算每个K值对应的验证集均方误差，从中选择一个最佳的最终值．

交叉验证(Cross Validation)在机器学习领域主要用于检测分类器的性能．它的基本思路是按某种意义将原始数据分为验证集和训练集，验证集用作测试，训练集用作模型训练，最后根据模型测试结果对分类器性能优劣进行合理评价．本文使用K折交叉验证法来检验KNN分类器模型．

K折交叉验证法会对原始数据进行随机划分，将完整的数据集等分成K份，每次取其中1份作为验证集，剩余K-1份作为训练集．进行K次交叉验证，记录每次的均方误差，对K次均方误差取平均值作为评价最终模型性能的指标．K折交叉验证法的均方误差公式为：

(1)

式中k是数据子集划分的数量，MSEi是每份训练集训练得到的模型在验证集上的均方误差，MSE是模型最终的均方误差．

2.3 距离度量方法

2.3.1 欧几里得距离

欧几里得距离用于指代两个n维向量间的真实距离，值为两向量各坐标差值平方和的算术平方根．欧几里得距离广泛应用于数字图像处理领域，经典的欧氏距离变换可作为图像骨架提取时的参照[10]．

假设存在n维向量X(x1，x2，…，xn)和Y(y1，y2，…，yn)，它们的欧氏距离求解方法如下：

(2)

2.3.2 曼哈顿距离

曼哈顿距离用于指代两个n维向量间的L1距离，值为两向量各坐标差值的绝对值和．

假设存在n维向量X(x1，x2，…，xn)和Y(y1，y2，…，yn)，它们的曼哈顿距离求解方法如下：

(3)

2.3.3 切比雪夫距离

切比雪夫距离用于指代两个n维向量间的L∞距离，值为两向量各坐标差绝对值的最大值．

假设存在n维向量X(x1，x2，…，xn)和Y(y1，y2，…，yn)，它们的切比雪夫距离求解方法如下：

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

(4)

2.4 分类决策规则

决定了最佳的K值和距离度量方式后，可以从特征空间中找出与测试样例最近(即最相似)的K个样本，如何依靠K个样本的特点确定测试样例所属类别就是分类决策规则．KNN模型的分类决策通常采用多数表决法和加权多数表决法．

多数表决法不考虑样本权重，只考虑样本数量，模型最终的预测结果取决于邻近样本中不同类别的数量．加权多数表决法弥补了多数表决法的不足，同时考虑样本数量和样本权重，通常样本权重根据距离反比计算，邻近样本中权值最大的那个类就是模型最终的预测结果．

3 实验与结果分析

3.1 数据建模

首先将球场划分为三个有效区域使得传球的横、纵坐标离散化，再通过解析日志文件提取出对方球队的传球数、平均传球距离和三个有效区域的传球数作为传球特征，将传球信息按上述传球特征抽象成向量，由此构造训练所需的数据集．

3.1.1 球场划分

仿真2D的球场总长度105 m，总宽度68 m．传球的横坐标和纵坐标均是连续型变量，为了将其离散化，将球场划分为不同区域．本文将球场划分为CrossBlock、DribbleField、CrossAttack、Danger、MidField、ShootChance六个区域．考虑到Danger区域比赛中传球数很少，误差较大；CrossAttack和ShootChance区域与我方球队关联性较大，不能很好地反映对方球队传球特征；最终选取CrossBlock、DribbleField、MidField三个区域作为传球有效区域．球场区域(图1)以及每个有效区域坐标范围见表1.

图1 球场区域划分

表1 有效区域划分范围

3.1.2 日志文件的解析

RoboCup仿真2D的比赛进程由Soccer Server实时控制和记录，比赛结束时Server会产生相应的比赛日志文件，分为rcg后缀名文件和rcl后缀名文件．rcg文件由当前周期、球信息和球员信息等部分组成，rcl文件包含具体的裁判命令信息．传统RoboCup数据挖掘使用rcg和rcl文件作为数据源，从中挖掘具有潜在价值的信息．

本文使用Python语言解析单场比赛的rcg文件和rcl文件，提取对方在比赛中的每次传球信息，包括传球周期、传球源点、传球目标点和传球距离(采用传球源点与传球目标点间直线距离，即欧几里得距离，以便与现实世界中人类对距离的感知保持一致)．部分比赛解析结果示例如表2．

表2 部分比赛解析结果示例

3.1.3 数据集的构造

为了研究传球特征与队伍间的关系，本文选取安徽工业大学的YuShan队与Fractals2019、HELIOS2019、CYRUS2019三支队伍总共2 102场比赛的日志文件作为数据源，对上文的球场区域划分与比赛日志文件解析结果进行汇总，提取每场比赛对方队伍的传球数、平均传球距离、CrossBlock(记为CB)区域传球数、DribbleField(记为DF)区域传球数和MidField(记为MF)区域传球数共五个特征，与标识信息队伍编号一起写入csv文件中，其中三个有效区域的传球数由传球目标点与有效区域划分范围共同得出，得到的部分csv文件如表3所示．

表3 部分csv文件

3.2 KNN分类模型的建立

本文利用七折交叉验证法，将上文构造的传球特征数据集随机等分成七份，每次将其中的一份用作验证，剩余的七份用作训练，记录训练得到的模型在验证集上的错误率，取七次平均值作为最终模型性能的评价指标．K从1开始选取，不断增加K的值，记录每个K值对应的错误率，得到的K值与错误率关系曲线图(图2)．

图2 K值与错误率关系曲线图

从上图可以看出，K值为21时误差最小．因此，本文选取21作为最佳K值，使用欧氏距离、切比雪夫距离和曼哈顿距离组合度量特征空间内样本点与测试样例间距离，筛选同测试样例最相近的21个样本点，最后使用距离反比加权多数表决法确定测试样例的所属类别．根据上述三要素搭建的KNN模型的传球模式识别成功率如表4．

表4 传球模式识别成功率

4 球队决策优化

为直观感受不同球队传球信息间差异，为球队决策优化提供理论指导．本文使用Python的Matplotlib库对Fractals2019、HELIOS2019、CYRUS2019三支队伍各10场的传球信息进行了可视化处理，绘制球队传球路线图(图3)．

图3 球队传球路线图

在球队传球路线图中，每条线段表示一次完整的传球动作，包含开始点和结束点．根据线段的疏密分布情况，可以看出不同传球模式下的主要进攻路径和进攻区域．结合图3绘制的不同传球模式下的主要进攻路径和进攻区域如图4所示．

图4 不同传球模式下的主要进攻路径和进攻区域

图4中箭头所指方向代表对方的进攻方向，箭头构成的路径是对方的主要进攻路径，箭头所在的区域是对方的主要进攻区域．比赛时实时采集对方球队的传球信息，利用KNN分类模型识别对方球队的传球模式，根据不同传球模式下的主要进攻路径和进攻区域，调配己方的防守球员进行针对性防守，优化球队的防守决策．应用防守策略前和应用防守策略后的球队与三支队伍在仿真2D平台下进行比赛，比赛结果如表5．

表5 比赛结果

从表5可以看出，球队应用防守策略后对三支球队的胜率均有提升，验证了传球模式识别用于球队决策改良的可行性和正确性．

本文使用KNN分类模型，以数据挖掘为主要思想，探究传球模式与球队决策之间的关系．该分类模型对于实际比赛的启示是，根据对方球队的主要进攻区域和进攻路径，合理调配己方的防守球员进行针对性防守，优化球队的防守策略．