基于密度峰值聚類的陣型識別算法

程澤凱，陳梅，秦鋒

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

?

基于密度峰值聚類的陣型識別算法

程澤凱，陳梅，秦鋒

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

摘要：針對RoboCup2D足球仿真中陣型識別問題，提出了使用一種基于密度峰值聚類的機(jī)器學(xué)習(xí)算法來識別陣型。該算法是根據(jù)坐標(biāo)點(diǎn)與坐標(biāo)點(diǎn)之間的距離計(jì)算與第i個(gè)點(diǎn)之間的距離小于截?cái)嗑嚯x的個(gè)數(shù)，并對個(gè)數(shù)進(jìn)行順序排列，尋找被低密度區(qū)域分離的高密度區(qū)域，得到聚類中心。算法核心是對聚類中心的刻畫以及數(shù)據(jù)的選取。聚類中心本身的密度大，被密度均不超過它的鄰居所包圍，與其他密度更大的數(shù)據(jù)點(diǎn)之間的“距離”相對更大。對有效數(shù)據(jù)進(jìn)行聚類的仿真結(jié)果表明，該算法將數(shù)據(jù)聚類成3類，通過陣型讀取顯示文件證實(shí)了聚類結(jié)果的正確性,同時(shí)也印證了對球隊(duì)中前鋒、中鋒、后衛(wèi)的區(qū)域的定義。

關(guān)鍵詞：RoboCup2D；陣型；密度峰值聚類；機(jī)器學(xué)習(xí)

在RoboCup2D足球仿真比賽中，每個(gè)“隊(duì)員”都對應(yīng)一個(gè)智能體，即“agent”，同時(shí)該比賽也是一場由多個(gè)智能體協(xié)作的比賽[1]。因此，在多智能體系統(tǒng)中，智能體之間的協(xié)作是非常重要的，那么智能體協(xié)作的策略也是決定比賽勝負(fù)的一個(gè)關(guān)鍵因素[2]。

另外，在多智能體仿真比賽系統(tǒng)中，比賽是實(shí)時(shí)的、動(dòng)態(tài)的、連續(xù)的以及非確定性的。對于每個(gè)球員來說，在不確定的球場信息中，很難做出一個(gè)相對正確的決策，只能考慮多個(gè)球員之間的協(xié)作關(guān)系，而多球員之間的協(xié)作關(guān)系在宏觀上反映出來的便是陣型[2]。

對于 RoboCup2D 陣型的研究主要基于三方面，分別是陣型策略[3]、陣型識別[4]、陣型分析。陣型策略指的是我方球隊(duì)在陣型方面需要做的策略，主要是針對不同球隊(duì)不同的陣型，更或者是在比賽中根據(jù)對方球隊(duì)的陣型來變換我方陣型；陣型識別是我方在識別對方陣型的情況下才能做出相應(yīng)的決策，這個(gè)是陣型研究中比較重要的環(huán)節(jié)；陣型分析主要是分析對方陣型是強(qiáng)攻擊型陣型，還是強(qiáng)防守型陣型。

本文的研究工作是陣型識別方面,目的在于根據(jù)對手陣型的變化從策略庫中選擇合適的陣型，以期待球隊(duì)能夠在比賽中有更精彩的表現(xiàn)。

1陣型定義及識別

1.1陣型定義

從足球常識中引入“陣型”的概念，用于對RoboCup仿真中全局合作的命名。

1)陣型可以看為智能體分布在場上位置的集合[3]。

式中：xi指第i個(gè)智能體的橫坐標(biāo)；yi指第i個(gè)智能體的縱坐標(biāo)，它包括6 000個(gè)周期的10個(gè)智能體的位置信息。

2)陣型可以根據(jù)球員的角色定義。球隊(duì)的角色分為后衛(wèi)、中場、前鋒和守門員。后衛(wèi)負(fù)責(zé)阻止對方球員進(jìn)球；中場負(fù)責(zé)銜接球隊(duì)的防守與進(jìn)攻；前鋒負(fù)責(zé)進(jìn)球。

3)根據(jù)球的位置進(jìn)行跑位的陣型定義。隊(duì)伍的陣型是以球員和球員之間的位置來定義的，也有根據(jù)球員的位置在球場的分布結(jié)構(gòu)來定義。

1.2 陣型識別

在RoboCup仿真發(fā)展的數(shù)年中，各種不同的陣型設(shè)計(jì)方案被提出并實(shí)現(xiàn)。因此，不同的隊(duì)伍可能有不同的陣型設(shè)計(jì)模式，對于陣型的識別可能也有不同的方法。國內(nèi)外也提出了許多關(guān)于陣型識別的方法。

通過神經(jīng)網(wǎng)絡(luò)[5]的方法學(xué)習(xí)并識別陣型，神經(jīng)網(wǎng)絡(luò)算法是一種無監(jiān)督的機(jī)器學(xué)習(xí)[6]算法，秦鋒等[7]提出通過BP神經(jīng)網(wǎng)絡(luò)的方法在線學(xué)習(xí)陣型；蔡劍懷等[2]提出使用神經(jīng)網(wǎng)絡(luò)來訓(xùn)練陣型；Nakashima等[8]提出使用三層前饋神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)對手陣型，并使用了一定的方法修正神經(jīng)網(wǎng)絡(luò)的輸出，目的是模仿RoboCup2D參賽隊(duì)中強(qiáng)隊(duì)的陣型。

基于球場不同區(qū)域球員之間位置關(guān)系來識別陣型,是由Riley等[9]提出根據(jù)球員的本屬區(qū)域來識別對方陣型。對于這種識別陣型的算法，Huberto等[4]進(jìn)行了改進(jìn)，定義點(diǎn)與點(diǎn)之間位置的模板，得到一個(gè)標(biāo)準(zhǔn)陣型文件的模板序列，與實(shí)際的陣型序列進(jìn)行比對，以發(fā)現(xiàn)該隊(duì)主要使用的陣型。這種方法也被Yusuke Kobayashi等用于球隊(duì)的反擊行為檢測[10]。

基于聚類和德內(nèi)洛三角形的陣型識別[11]，提出將聚類方法和德內(nèi)洛三角形模型兩方法結(jié)合從坐標(biāo)數(shù)據(jù)中識別未知陣型。為了分析從日志文件中提取的坐標(biāo)數(shù)據(jù)，結(jié)合Growing Neural Gas Network 和Delaunay Triangulation來重新塑造一個(gè)陣型。

本文采用的陣型定義是根據(jù)球員的位置在球場上的分布結(jié)構(gòu)。本文是使用一種基于密度峰值聚類的分析方法對坐標(biāo)文件進(jìn)行聚類分析[12]，即DPCA算法[13]。

2數(shù)據(jù)

2.1數(shù)據(jù)來源

本文中采用的數(shù)據(jù)是RoboCup2D仿真比賽中由系統(tǒng)所產(chǎn)生的日志文件。在RoboCup2D仿真比賽平臺中產(chǎn)生了2種日志文件，分別是RCG文件和RCL文件，本文中主要使用的是RCG文件。

① RCG文件。標(biāo)識了每個(gè)周期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坐標(biāo)為-49，y坐標(biāo)為0，依次類推。

② RCL文件。標(biāo)識了每個(gè)周期比賽team與sever的交互，agent做出何種動(dòng)作。

2.2數(shù)據(jù)提取

對RCG文件進(jìn)行解析[14]，得到含每個(gè)周期每個(gè)球員坐標(biāo)的數(shù)據(jù)文件。步驟如下：

①讀取RCG文件中含有show的1行內(nèi)容。

(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

③根據(jù)“，”標(biāo)志，分離出agent的坐標(biāo)。即可得初始實(shí)驗(yàn)所需要的二維坐標(biāo)源數(shù)據(jù)，之后對源數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘和分析。

3聚類算法描述

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

本文采用的是一種基于密度峰值聚類算法來識別陣型，即DPCA算法，該算法核心在于對聚類中心的刻畫。算法中定義的聚類中心需同時(shí)具有以下特點(diǎn)：①本身的密度大，被密度均不超過它的鄰居包圍；②與其他密度更大的數(shù)據(jù)點(diǎn)之間的“距離”更大。

對于S中的任何數(shù)據(jù)點(diǎn)可以為其定義ρi和δi2個(gè)量，這2個(gè)量分別用來對上文中提到的聚類中心的2個(gè)特點(diǎn)進(jìn)行刻畫。使用ρi刻畫1個(gè)數(shù)據(jù)集S中每個(gè)數(shù)據(jù)點(diǎn)的密度，使用δi來刻畫與高密度點(diǎn)之間的距離。

1)局部密度定義為

(1)

式中

式中dc稱為截?cái)嗑嚯x(cut-offdistance)。式(1)的意義在于找到與第i個(gè)數(shù)據(jù)點(diǎn)之間的距離dc小于截?cái)嗑嚯x的數(shù)據(jù)點(diǎn)個(gè)數(shù)。

2)與高密度點(diǎn)之間的距離δi為

(2)

3)數(shù)據(jù)點(diǎn)xi和xj之間的距離。關(guān)于點(diǎn)與點(diǎn)之間的距離，本文中采用的是歐式距離，計(jì)算公式為

實(shí)驗(yàn)所定義的距離文件格式如下，并以.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核心思想是尋找被低密度區(qū)域包圍的高密度區(qū)域。根據(jù)算法中對聚類中心的定義，對于1個(gè)數(shù)據(jù)集，聚類中心是被一些低局部密度的數(shù)據(jù)點(diǎn)包圍。這些低局部密度的點(diǎn)距離其他高局部密度的點(diǎn)的距離都比較大。

對于聚類問題，需要回答的是聚類中心是什么？對于每個(gè)數(shù)據(jù)點(diǎn)，如何定義所屬的類別[15]，在DPCA算法中，將那些同時(shí)具有較大距離和較大局部密度的點(diǎn)定義為聚類中心。

聚類過程如下：

1)利用樣本點(diǎn)之間的距離求得樣本點(diǎn)的密度。

2)利用聚類中心是局部中密度最大的樣本點(diǎn)，并由密度較低的樣本所包圍的特點(diǎn)，求得δ(表示離該樣本點(diǎn)最近且密度大于該點(diǎn)的樣本點(diǎn)之間的距離，當(dāng)為局部最大時(shí)或?yàn)榱硪痪垲愔须x自己較近的且有比本身大的密度的樣本點(diǎn)之間的距離，當(dāng)為全局最大時(shí)給予最大的距離)。

3)繪出決策圖(decisiongraph)，很容易將聚類中心和噪聲、基本樣本點(diǎn)區(qū)別開來，或者采用ρ×δ 排序后找出聚類中心，并按照最近鄰原則對樣本點(diǎn)進(jìn)行分配。

至此完成了樣本的聚類過程。

4實(shí)驗(yàn)結(jié)果及數(shù)據(jù)分析

采取數(shù)據(jù)HELIOS2013與YuShan2014比賽的日志文件，使用C++編程語言實(shí)現(xiàn)坐標(biāo)數(shù)據(jù)文件的提取和坐標(biāo)距離文件的計(jì)算，使用Matlab編程實(shí)現(xiàn)DPCA算法。

4.1不同大小數(shù)據(jù)集聚類結(jié)果

實(shí)驗(yàn)采用從比賽產(chǎn)生的日志文件中生成的1 000個(gè)數(shù)據(jù)點(diǎn)和10 000個(gè)數(shù)據(jù)點(diǎn)進(jìn)行聚類，并將10 000個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集使用Kmeans方法進(jìn)行聚類，將2種結(jié)果進(jìn)行比對，得出聚類結(jié)果相同。圖1中顯示了源數(shù)據(jù)的概率分布。

圖1　1場比賽坐標(biāo)數(shù)據(jù)概率分布圖

由圖2的聚類決策圖可知，該1 000個(gè)數(shù)據(jù)點(diǎn)被聚成三隔類簇。由表1可知，3個(gè)聚類簇元素個(gè)數(shù)分別為290,283,467，比例約為4∶3∶3，可知該隊(duì)采用的是4∶3∶3陣型。

圖2　生成1 000個(gè)數(shù)據(jù)點(diǎn)聚類決策圖

clustercenterelementscoreHalo164829027392680283822713782427154427

由圖3的聚類決策圖可知，該10 000個(gè)數(shù)據(jù)點(diǎn)被聚成三隔類簇。由表2可知3個(gè)聚類簇元素個(gè)數(shù)分別為3 961,3 184,2 855，,比例約為4∶3∶3，可知該隊(duì)采用的是4∶3∶3陣型。

圖3　生成10 000個(gè)數(shù)據(jù)點(diǎn)聚類決策圖

clustercenterelementscorehalo162293961254682679031848547339908285529361

綜上所述，根據(jù)不同數(shù)據(jù)集的聚類決策圖可知，該隊(duì)的主要陣型是4∶3∶3陣型。

4.2與Kmeans聚類算法進(jìn)行對比

對上文提取的10 000個(gè)數(shù)據(jù)點(diǎn)，使用Kmeans算法進(jìn)行聚類，結(jié)果見圖4。

圖4　Kmeans算法聚類10 000個(gè)數(shù)據(jù)點(diǎn)

由表2與圖4的對比，得2個(gè)聚類結(jié)果，每個(gè)類簇所含有點(diǎn)的個(gè)數(shù)相近，可知算法的正確性。

此外，對該日志文件使用rcsslogplayer進(jìn)行播放觀察，可得該隊(duì)伍采用的陣型是4∶3∶3陣型，如圖5所示(黑色球)。

圖5　HELLOS球隊(duì)陣型圖示

通過不同大小實(shí)驗(yàn)數(shù)據(jù)集的聚類決策圖說明，每個(gè)不同數(shù)據(jù)集的決策圖都是分成3類，正驗(yàn)證了球隊(duì)對于陣型主要?jiǎng)澐忠罁?jù)為前鋒、中長和后衛(wèi)的3個(gè)區(qū)域。

5結(jié)語

文章針對RoboCup2D足球仿真中陣型識別問題，提出一種DPCA算法，即基于密度峰值聚類的機(jī)器學(xué)習(xí)算法。該算法巧妙地利用了聚類中心所具有的兩大特點(diǎn)來自動(dòng)確定聚類中心，然后對每個(gè)二維坐標(biāo)點(diǎn)根據(jù)距離聚類中心的距離遠(yuǎn)近判定屬于哪個(gè)聚類中心。經(jīng)過對不同大小數(shù)據(jù)集的實(shí)驗(yàn)，并與使用Kmeans算法聚類的結(jié)果進(jìn)行對比，該算法對于每個(gè)數(shù)據(jù)集的聚類結(jié)果較為理想。

[參考文獻(xiàn)]

[1]方寶富.機(jī)器人足球仿真[M].合肥：合肥工業(yè)大學(xué)出版社,2011.

[2]蔡劍懷,吳順祥,繆克華,等.RoboCup中基于神經(jīng)網(wǎng)絡(luò)的陣型策略[J].系統(tǒng)仿真學(xué)報(bào),2006,18(1):237-239.

[3]張浩,陳小平.基于Markov預(yù)測模型的動(dòng)態(tài)足球機(jī)器人陣型策略方法[J].計(jì)算機(jī)工程與學(xué)科,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]田景文.人工神經(jīng)網(wǎng)絡(luò)算法研究及應(yīng)用[M].北京：北京理工大學(xué)出版社,2006.

[6]HARRINGTON P.機(jī)器學(xué)習(xí)實(shí)戰(zhàn)[M].北京：人民郵電出版社,2013.

[7]秦鋒,趙真真,程澤凱,等.RoboCup中基于神經(jīng)網(wǎng)絡(luò)的陣型策略在線學(xué)習(xí)[J].計(jì)算機(jī)與現(xiàn)代化,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]韓家煒,坎伯,裴健，等.數(shù)據(jù)挖掘:概念與技術(shù)[M].3版.北京：機(jī)械工業(yè)出版社,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.

責(zé)任編輯：陳亮

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

基金項(xiàng)目：安徽省教育廳、財(cái)政廳局級高校自然科學(xué)研究重大項(xiàng)目(KJ2014ZD05)

作者簡介：程澤凱(1972—)，男，碩士，副教授。

中圖分類號：TP3-0

文獻(xiàn)標(biāo)志碼：A

文章編號：1671- 0436(2016)02- 0038- 05