程澤凱，陳梅，秦鋒

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

?

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

程澤凱，陳梅，秦鋒

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

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

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

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

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

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

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

1陣型定義及識別

1.1陣型定義

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

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

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

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

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

1.2 陣型識別

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

通過神經(jīng)網(wǎng)絡(luò)[5]的方法學(xué)習(xí)并識別陣型，神經(jīng)網(wǎng)絡(luò)算法是一種無監(jiān)督的機器學(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參賽隊中強隊的陣型。

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

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

本文采用的陣型定義是根據(jù)球員的位置在球場上的分布結(jié)構(gòu)。本文是使用一種基于密度峰值聚類的分析方法對坐標文件進行聚類分析[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文件。標識了每個周期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數(shù)據(jù)提取

對RCG文件進行解析[14]，得到含每個周期每個球員坐標的數(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ù)“，”標志，分離出agent的坐標。即可得初始實驗所需要的二維坐標源數(shù)據(jù)，之后對源數(shù)據(jù)進行數(shù)據(jù)挖掘和分析。

3聚類算法描述

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

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

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

1)局部密度定義為

(1)

式中

式中dc稱為截斷距離(cut-offdistance)。式(1)的意義在于找到與第i個數(shù)據(jù)點之間的距離dc小于截斷距離的數(shù)據(jù)點個數(shù)。

2)與高密度點之間的距離δi為

(2)

3)數(shù)據(jù)點xi和xj之間的距離。關(guā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個數(shù)據(jù)集，聚類中心是被一些低局部密度的數(shù)據(jù)點包圍。這些低局部密度的點距離其他高局部密度的點的距離都比較大。

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

聚類過程如下：

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

2)利用聚類中心是局部中密度最大的樣本點，并由密度較低的樣本所包圍的特點，求得δ(表示離該樣本點最近且密度大于該點的樣本點之間的距離，當為局部最大時或為另一聚類中離自己較近的且有比本身大的密度的樣本點之間的距離，當為全局最大時給予最大的距離)。

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

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

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

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

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

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

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

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

圖2　生成1 000個數(shù)據(jù)點聚類決策圖

clustercenterelementscoreHalo164829027392680283822713782427154427

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

圖3　生成10 000個數(shù)據(jù)點聚類決策圖

clustercenterelementscorehalo162293961254682679031848547339908285529361

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

4.2與Kmeans聚類算法進行對比

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

圖4　Kmeans算法聚類10 000個數(shù)據(jù)點

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

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

圖5　HELLOS球隊陣型圖示

通過不同大小實驗數(shù)據(jù)集的聚類決策圖說明，每個不同數(shù)據(jù)集的決策圖都是分成3類，正驗證了球隊對于陣型主要劃分依據(jù)為前鋒、中長和后衛(wèi)的3個區(qū)域。

5結(jié)語

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

[參考文獻]

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

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

[3]張浩,陳小平.基于Markov預(yù)測模型的動態(tài)足球機器人陣型策略方法[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.機器學(xué)習(xí)實戰(zhàn)[M].北京：人民郵電出版社,2013.

[7]秦鋒,趙真真,程澤凱,等.RoboCup中基于神經(jīng)網(wǎng)絡(luò)的陣型策略在線學(xué)習(xí)[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版.北京：機械工業(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

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

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

中圖分類號：TP3-0

文獻標志碼：A

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