基于密度峰值聚类的阵型识别算法

程泽凯，陈梅，秦锋

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



基于密度峰值聚类的阵型识别算法

程泽凯，陈梅，秦锋

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

摘要：针对RoboCup2D足球仿真中阵型识别问题，提出了使用一种基于密度峰值聚类的机器学习算法来识别阵型。该算法是根据坐标点与坐标点之间的距离计算与第i个点之间的距离小于截断距离的个数，并对个数进行顺序排列，寻找被低密度区域分离的高密度区域，得到聚类中心。算法核心是对聚类中心的刻画以及数据的选取。聚类中心本身的密度大，被密度均不超过它的邻居所包围，与其他密度更大的数据点之间的“距离”相对更大。对有效数据进行聚类的仿真结果表明，该算法将数据聚类成3类，通过阵型读取显示文件证实了聚类结果的正确性,同时也印证了对球队中前锋、中锋、后卫的区域的定义。

关键词：RoboCup2D；阵型；密度峰值聚类；机器学习

在RoboCup2D足球仿真比赛中，每个“队员”都对应一个智能体，即“agent”，同时该比赛也是一场由多个智能体协作的比赛[1]。因此，在多智能体系统中，智能体之间的协作是非常重要的，那么智能体协作的策略也是决定比赛胜负的一个关键因素[2]。

另外，在多智能体仿真比赛系统中，比赛是实时的、动态的、连续的以及非确定性的。对于每个球员来说，在不确定的球场信息中，很难做出一个相对正确的决策，只能考虑多个球员之间的协作关系，而多球员之间的协作关系在宏观上反映出来的便是阵型[2]。

对于 RoboCup2D 阵型的研究主要基于三方面，分别是阵型策略[3]、阵型识别[4]、阵型分析。阵型策略指的是我方球队在阵型方面需要做的策略，主要是针对不同球队不同的阵型，更或者是在比赛中根据对方球队的阵型来变换我方阵型；阵型识别是我方在识别对方阵型的情况下才能做出相应的决策，这个是阵型研究中比较重要的环节；阵型分析主要是分析对方阵型是强攻击型阵型，还是强防守型阵型。

本文的研究工作是阵型识别方面,目的在于根据对手阵型的变化从策略库中选择合适的阵型，以期待球队能够在比赛中有更精彩的表现。

1阵型定义及识别

1.1阵型定义

从足球常识中引入“阵型”的概念，用于对RoboCup仿真中全局合作的命名。

1)阵型可以看为智能体分布在场上位置的集合[3]。

式中：xi指第i个智能体的横坐标；yi指第i个智能体的纵坐标，它包括6 000个周期的10个智能体的位置信息。

2)阵型可以根据球员的角色定义。球队的角色分为后卫、中场、前锋和守门员。后卫负责阻止对方球员进球；中场负责衔接球队的防守与进攻；前锋负责进球。

3)根据球的位置进行跑位的阵型定义。队伍的阵型是以球员和球员之间的位置来定义的，也有根据球员的位置在球场的分布结构来定义。

1.2 阵型识别

在RoboCup仿真发展的数年中，各种不同的阵型设计方案被提出并实现。因此，不同的队伍可能有不同的阵型设计模式，对于阵型的识别可能也有不同的方法。国内外也提出了许多关于阵型识别的方法。

通过神经网络[5]的方法学习并识别阵型，神经网络算法是一种无监督的机器学习[6]算法，秦锋等[7]提出通过BP神经网络的方法在线学习阵型；蔡剑怀等[2]提出使用神经网络来训练阵型；Nakashima等[8]提出使用三层前馈神经网络学习对手阵型，并使用了一定的方法修正神经网络的输出，目的是模仿RoboCup2D参赛队中强队的阵型。

基于球场不同区域球员之间位置关系来识别阵型,是由Riley等[9]提出根据球员的本属区域来识别对方阵型。对于这种识别阵型的算法，Huberto等[4]进行了改进，定义点与点之间位置的模板，得到一个标准阵型文件的模板序列，与实际的阵型序列进行比对，以发现该队主要使用的阵型。这种方法也被Yusuke Kobayashi等用于球队的反击行为检测[10]。

基于聚类和德内洛三角形的阵型识别[11]，提出将聚类方法和德内洛三角形模型两方法结合从坐标数据中识别未知阵型。为了分析从日志文件中提取的坐标数据，结合Growing Neural Gas Network 和Delaunay Triangulation来重新塑造一个阵型。

本文采用的阵型定义是根据球员的位置在球场上的分布结构。本文是使用一种基于密度峰值聚类的分析方法对坐标文件进行聚类分析[12]，即DPCA算法[13]。

2数据

2.1数据来源

本文中采用的数据是RoboCup2D仿真比赛中由系统所产生的日志文件。在RoboCup2D仿真比赛平台中产生了2种日志文件，分别是RCG文件和RCL文件，本文中主要使用的是RCG文件。

① RCG文件。标识了每个周期ball以及agent的位置等。格式如下：

(show 1((b)0 0 0 0)((l 1)0 0x9-49 0 0 0-55.856 0(v h 180)(s 8000 1 1 130600)(c 0 0 153 0 1 154 1 0 0 0 0))

其中，加粗字体分别指左方1号球员的x坐标为-49，y坐标为0，依次类推。

② RCL文件。标识了每个周期比赛team与sever的交互，agent做出何种动作。

2.2数据提取

对RCG文件进行解析[14]，得到含每个周期每个球员坐标的数据文件。步骤如下：

①读取RCG文件中含有show的1行内容。

(show 131((b)1.988 25.8408 1.6566 1.4176)((l 1)0 0x9-43.3077 3.1504-0 0 118.271-90；

②使用“，”分割RCG文件[14]。

(show，131，((b)，1.988，25.8408，1.6566，1.4176)][((l 1)，0，0x9，-43.3077，3.1504，-0，0，118.271，-90

③根据“，”标志，分离出agent的坐标。即可得初始实验所需要的二维坐标源数据，之后对源数据进行数据挖掘和分析。

3聚类算法描述

3.1基于密度峰值的聚类分析算法

本文采用的是一种基于密度峰值聚类算法来识别阵型，即DPCA算法，该算法核心在于对聚类中心的刻画。算法中定义的聚类中心需同时具有以下特点：①本身的密度大，被密度均不超过它的邻居包围；②与其他密度更大的数据点之间的“距离”更大。

对于S中的任何数据点可以为其定义ρi和δi2个量，这2个量分别用来对上文中提到的聚类中心的2个特点进行刻画。使用ρi刻画1个数据集S中每个数据点的密度，使用δi来刻画与高密度点之间的距离。

1)局部密度定义为

(1)

式中

式中dc称为截断距离(cut-offdistance)。式(1)的意义在于找到与第i个数据点之间的距离dc小于截断距离的数据点个数。

2)与高密度点之间的距离δi为

(2)

3)数据点xi和xj之间的距离。关于点与点之间的距离，本文中采用的是欧式距离，计算公式为

实验所定义的距离文件格式如下，并以.dat文件格式存储：

1 2 102 3 23.021

1 3 13.03842 4 13.0384

1 4 23.02172 5 15.8114

1 5 15.81142 6 17.2621

1 6 11.07162 7 11.0785

1 7 17.19692 8 36.4005

1 8 29.06892 9 29.0689

1 9 36.40052 10 25.1128

1 10 25.11283 4 36

3.2如何聚类

DPCA核心思想是寻找被低密度区域包围的高密度区域。根据算法中对聚类中心的定义，对于1个数据集，聚类中心是被一些低局部密度的数据点包围。这些低局部密度的点距离其他高局部密度的点的距离都比较大。

对于聚类问题，需要回答的是聚类中心是什么？对于每个数据点，如何定义所属的类别[15]，在DPCA算法中，将那些同时具有较大距离和较大局部密度的点定义为聚类中心。

聚类过程如下：

1)利用样本点之间的距离求得样本点的密度。

2)利用聚类中心是局部中密度最大的样本点，并由密度较低的样本所包围的特点，求得δ(表示离该样本点最近且密度大于该点的样本点之间的距离，当为局部最大时或为另一聚类中离自己较近的且有比本身大的密度的样本点之间的距离，当为全局最大时给予最大的距离)。

3)绘出决策图(decisiongraph)，很容易将聚类中心和噪声、基本样本点区别开来，或者采用ρ×δ 排序后找出聚类中心，并按照最近邻原则对样本点进行分配。

至此完成了样本的聚类过程。

4实验结果及数据分析

采取数据HELIOS2013与YuShan2014比赛的日志文件，使用C++编程语言实现坐标数据文件的提取和坐标距离文件的计算，使用Matlab编程实现DPCA算法。

4.1不同大小数据集聚类结果

实验采用从比赛产生的日志文件中生成的1 000个数据点和10 000个数据点进行聚类，并将10 000个数据点的数据集使用Kmeans方法进行聚类，将2种结果进行比对，得出聚类结果相同。图1中显示了源数据的概率分布。

图1　1场比赛坐标数据概率分布图

由图2的聚类决策图可知，该1 000个数据点被聚成三隔类簇。由表1可知，3个聚类簇元素个数分别为290,283,467，比例约为4∶3∶3，可知该队采用的是4∶3∶3阵型。

图2　生成1 000个数据点聚类决策图

clustercenterelementscoreHalo164829027392680283822713782427154427

由图3的聚类决策图可知，该10 000个数据点被聚成三隔类簇。由表2可知3个聚类簇元素个数分别为3 961,3 184,2 855，,比例约为4∶3∶3，可知该队采用的是4∶3∶3阵型。

图3　生成10 000个数据点聚类决策图

clustercenterelementscorehalo162293961254682679031848547339908285529361

综上所述，根据不同数据集的聚类决策图可知，该队的主要阵型是4∶3∶3阵型。

4.2与Kmeans聚类算法进行对比

对上文提取的10 000个数据点，使用Kmeans算法进行聚类，结果见图4。

图4　Kmeans算法聚类10 000个数据点

由表2与图4的对比，得2个聚类结果，每个类簇所含有点的个数相近，可知算法的正确性。

此外，对该日志文件使用rcsslogplayer进行播放观察，可得该队伍采用的阵型是4∶3∶3阵型，如图5所示(黑色球)。

图5　HELLOS球队阵型图示

通过不同大小实验数据集的聚类决策图说明，每个不同数据集的决策图都是分成3类，正验证了球队对于阵型主要划分依据为前锋、中长和后卫的3个区域。

5结语

文章针对RoboCup2D足球仿真中阵型识别问题，提出一种DPCA算法，即基于密度峰值聚类的机器学习算法。该算法巧妙地利用了聚类中心所具有的两大特点来自动确定聚类中心，然后对每个二维坐标点根据距离聚类中心的距离远近判定属于哪个聚类中心。经过对不同大小数据集的实验，并与使用Kmeans算法聚类的结果进行对比，该算法对于每个数据集的聚类结果较为理想。

[参考文献]

[1]方宝富.机器人足球仿真[M].合肥：合肥工业大学出版社,2011.

[2]蔡剑怀,吴顺祥,缪克华,等.RoboCup中基于神经网络的阵型策略[J].系统仿真学报,2006,18(1):237-239.

[3]张浩,陈小平.基于Markov预测模型的动态足球机器人阵型策略方法[J].计算机工程与学科,2007,29(10):120-123.

[4]Ayanegui-Santiago H.Recognizing team formations in multiagent systems:Applications in robotic soccer[C]//Computational Collective Intelligence.Semantic Web,Social Networks and Multiagent Systems.First International Conference,ICCCI 2009.Poland:Wroclaw,2009:163-173.

[5]田景文.人工神经网络算法研究及应用[M].北京：北京理工大学出版社,2006.

[6]HARRINGTON P.机器学习实战[M].北京：人民邮电出版社,2013.

[7]秦锋,赵真真,程泽凯,等.RoboCup中基于神经网络的阵型策略在线学习[J].计算机与现代化,2013(8):201-203.

[8]NAKASHIMA T,UENISHI T,NARIMOTO Y.Off-line learning of soccer formations from game logs[C]//World Automation Congress(WAC).IEEE,2010:1-6.

[9]RILEY P,VELOSO M,KAMINKA G.An empirical study of coaching[M]//Distributed Autonomous Robotic Systems 5.New Delhi:Springer,2002:215-224.

[10]KOBAYASHI Y,KAWAMURA H,SUZUKI K.Counter attack detection with machine learning from log files of RoboCup simulation[C]//International Conference on Soft Computing and Intelligent Systems,2012:1821-1826.

[11]AKIYAMA H,ARAMAKI S,NAKASHIMA T.Team formation estimation using cluster analysis and triangulation model[C]//International Conference on Soft Computing and Intelligent Systems,2012:956-959.

[12]韩家炜,坎伯,裴健，等.数据挖掘:概念与技术[M].3版.北京：机械工业出版社,2012:251-303.

[13]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014(6191):1492-1496.

[14]YAMAMOTO A,OKA N,Noda I.Imitative learning from the logs of a soccer simulator[C]//The 19th Annual Conference of the Japanese Society for Artificial Intelligence,2005.

[15]RUI X,DONALD W.Survey of clustering algorithms[J].Neural Networks,IEEE Transactions on,2005,16(3):645-678.

责任编辑：陈亮

An Algorithm for Formation Recognition Based on DPCA

CHENG Zekai，CHEN Mei，QIN Feng

(School of Computer Science and Technology,Anhui University of Technology,Maanshan 243032)

Abstract：Aiming at the problem of recognizing the formation of the opponent team in RoboCup2D soccer simulation,the paper put forward an algorithm for formation recognition,which is based on a machine learning algorithm dubbed density peaks clustering analysis (DPCA).This DPCA algorithm is to find the high density area surrounded by low density area by calculating the number of distance whose distance between the ithpoint is less than the cutoff distance according to the distance between points.Therefore the clustering center and the number of clusters can be found,and the formation is known.The core of DPCA is to define the clustering center and the selection of team formation.The clustering center itself has a high density,that is,it is surrounded by the lower density points,and it is also farther away from the points which have a higher density.The clustering simulation results show that the proposed method can effectively cluster the points to three categories,which can be seen in the competition,and the results also confirm that there are three kinds of players in a team: forwards,centre forwards and defenders.

Key words：RoboCup2D;formation;clustering based on density peaks;machine learning

doi:10.3969/j.issn.1671- 0436.2016.02.009

收稿日期：2016- 02-29

基金项目：安徽省教育厅、财政厅局级高校自然科学研究重大项目(KJ2014ZD05)

作者简介：程泽凯(1972—)，男，硕士，副教授。

中图分类号：TP3-0

文献标志码：A

文章编号：1671- 0436(2016)02- 0038- 05