基于GraphX的傳球網絡構建及分析研究

張 陶 于 炯 廖 彬 國冰磊 卞 琛 王躍飛 劉 炎

1(新疆大學信息科學與工程學院 烏魯木齊 830046)2(新疆財經大學統計與信息學院 烏魯木齊 830012)3(清華大學軟件學院 北京 100084)(zt59921661@126.com)

?

基于GraphX的傳球網絡構建及分析研究

張 陶1于 炯1廖 彬2國冰磊1卞 琛1王躍飛1劉 炎3

1(新疆大學信息科學與工程學院 烏魯木齊 830046)2(新疆財經大學統計與信息學院 烏魯木齊 830012)3(清華大學軟件學院 北京 100084)(zt59921661@126.com)

雖然大數據技術在社交網絡、金融、公共安全、醫療衛生等領域的應用不斷成熟,但在競技體育方面的應用還處于探索階段.常規籃球統計中缺乏對傳球數據的記錄,更缺乏對傳球數據的統計分析、價值挖掘及應用等方面的研究.1)由于傳球數據匯聚形態為圖,在傳球數據獲取、數據清洗及格式轉化、Vertex與Edge表構建的基礎上,通過GraphX構建傳球網絡圖為其應用打下基礎;2)提出PlayerRank值區分球員重要度、球員位置個性化圖頂點等方法提高傳球網絡可視化質量;3)通過GraphX構建的傳球網絡分析傳球數量與質量對比賽結果的影響,并例舉了傳球網絡在球隊傳球數據分析、戰術人員選擇、臨場戰術制定、網絡子圖及游戲體驗改進等方面的應用.

大數據應用;傳球網絡;GraphX框架;PlayerRank算法;球員重要性

據互聯網數據中心(Internet data center)發布的報告顯示,2015年全球產生的數據量達到近10 ZB,而2020年全球產生的數據量將達到40 ZB[1].數據的產生過程在經歷被動和主動2種產生過程后,發展到了自動產生階段,預示著大數據時代的來臨.數據從簡單的處理對象開始轉變為一種基礎性資源,如何更好地管理和利用大數據已經成為普遍關注的話題,大數據的規模效應給數據存儲、管理以及數據分析帶來了極大的挑戰[2].在Victor的大數據理論中,大數據最核心的問題并不是數據的種類(variety)及量(volume),而是大數據的價值(value).大數據時代并不代表所有應用數據量都大,大數據也是由一個個小數據集合而成,正是對小數據的持續采集、融合分析,才有積跬步而致千里的大數據價值能量的爆發.自2003年Google發表論文公開分布式存儲系統GFS[3](Google file system)及分布式數據處理模型MapReduce[4]以來,諸多的大數據計算系統及框架(如Hadoop,Storm,Spark[5],Pig,Hive,Hbase,Dryad等)以MapReduce為計算模型,并形成了以MapReduce為核心的大數據計算生態系統,如圖1所示:

Fig. 1 MapReduce computing model ecosystem.圖1 MapReduce計算模型生態系統

隨著大數據技術的不斷成熟,其在社交網絡、金融、公共安全、醫療等方面的應用也不斷發展成熟;但是大數據技術在競技體育方面的應用,還處于探索階段.大數據技術在足球方面的應用首次亮相是在2014年的巴西世界杯,幫助德國再次捧得大力神杯的“秘密武器”之一,則是來自SAP公司的足球大數據技術解決方案Match Insights. Match Insights能夠迅速收集、處理分析球員和球隊的技術數據,基于大數據分析優化球隊配置,提升球隊作戰能力,并通過分析對手技術數據,找到在世界杯比賽中的“制敵”方式.利用大數據分析,德國隊教練可以迅速了解當前比賽的狀況、每個球員的特點和表現、球員的防守范圍、對方球隊的空擋區等信息.通過這些信息,教練可以更有效地對球員上場時間、位置、技戰術等情況優化配置,以提升球員及球隊的整體表現.

在籃球比賽中,常規的技術統計有:得分、籃板、助攻、搶斷、蓋帽、失誤、犯規、投籃命中率、出場時間等;但缺乏對傳球數據的記錄,更缺乏對傳球數據的統計分析、數據挖掘及應用方法的研究.導致基于已有的技術統計數據,無法回答5個與傳球有關的問題:

問題1. 某球員這場比賽傳球多少次?接球多少次?傳球質量怎樣?傳球助攻率多少?

問題2. 傳切戰術、擋拆戰術及三角進攻戰術中,由誰來傳球最好?

問題3. 比賽還剩5 s,落后2分,誰來執行絕殺投籃?誰來傳球?

問題4. 林書豪傳球質量比庫里好?還是差?好多少?差多少?

問題5. NBA中傳球質量最好的是哪個隊?傳球最頻繁的是哪個隊?

以上僅僅例舉了5個較為常見的問題,而基于已有的技術統計,無法回答或解決的問題遠遠不止這些.因此，為了解決這5個問題,本文將球員之間的傳球關系進行關聯(將傳球人與接球人作為頂點,頂點之間的傳球關系作為邊),發現隨著傳球數據量的不斷增加,最終形成一張穩定的傳球網絡圖.與FaceBook、微博等社會關系網絡最大不同的是,社會網絡中邊的屬性較為簡單(通常為好友或關注關系),而傳球網絡中的邊屬性(邊屬性包括傳球次數、助攻次數、傳球概率、投籃命中率等)則復雜得多.由于傳球數據匯聚的頂層模型為圖,所以本文選取基于Spark[5]的圖分析工具GraphX[6-7]構建傳球網絡圖,并在此基礎上分析NBA球員之間的傳球數據,充分挖掘傳球數據的內涵,為球員的訓練、戰術制定、對手分析、教練決策等提供支持.

1 相關研究及背景

1.1 圖的相關研究

早期經典的圖理論研究工作,如AGM[8],FSM[9],GSAPN[10],FFSM[11]等為圖應用系統的開發提供了理論基礎.隨著Hadoop的快速發展,MapReduce計算模型得到廣泛應用,其中FSM-H[12]及MRFSM[13]就是基于MapReduce框架的圖算法,由于Map-Reduce的優勢在于處理批處理作業,對于具有復雜業務處理邏輯的圖計算,MapReduce計算效率并不理想[14-15].在此背景下,基于內存計算的分布式圖計算框架得到了快速發展(如GraphX是基于Spark的圖計算框架).分布式的圖計算框架是將對圖的操作(如圖的構建、PR計算、最短路徑查找等)封裝為接口,使得圖的分布式存儲及計算等復雜問題對上層應用透明.圖計算框架能夠讓圖算法及圖應用工程師忽略圖底層細節(如圖頂點、邊及其相關屬性的分布式存儲及計算方法),將精力聚集到具體的圖相關模型設計和應用層面上來.

當前的圖計算框架基本上都遵循BSP(bulk synchronous parallell)[16-17]計算模式.在BSP中,一次計算過程由一系列全局超步組成,每一個超步由并發計算、通信和柵欄同步3個步驟組成,同步完成標志著這個超步的完成及下一個超步的開始.基于BSP模式,目前較為成熟的圖計算模型主要有Pregel[18-20]及GAS[21-22]兩種.其中Pregel模型來自于Google,借鑒MapReduce的思想,Pregel提出了“像頂點一樣思考”(think like a vertex)的圖計算模式,讓用戶無需考慮并行分布式計算的細節,只需要實現一個頂點更新函數,讓框架在遍歷頂點時進行調用即可.但是對于鄰居數較多的頂點,Pregel模型需要處理的消息非常龐大,并且它們是無法被并發處理的.所以對于符合冪律分布的自然圖,Pregel模型容易出現應用假死或者崩潰的現象.相比Pregel模型的消息通信范式,GraphLab[23]提出的GAS模型更偏向共享內存風格.它允許用戶的自定義函數訪問當前頂點的整個鄰域,可抽象成Gather,Apply,Scatter三個階段(GAS),與此對應,用戶需要實現與GAS所對應的函數gather,apply,scatter.正是由于gather和scatter以單條邊為計算粒度,所以對于頂點眾多的鄰邊,可以分別由相應的計算節點獨立調用gather和scatter,從而較好地解決了Pregel中存在的問題.

1.2 相關背景知識介紹

1.2.1 基于Spark的分布式圖框架GraphX

GraphX基于Spark并擴展了Spark RDD[24](resilient distributed datasets)彈性分布式數據集的抽象,提出了Resilient Distributed Property Graph[6](點和邊都帶屬性的有向多重圖).由于GraphX提供Table與Graph兩種視圖,并且這2種視圖都擁有自己獨立的操作符,這使得GraphX的操作具有更大的靈活性.GraphX對Pregel及GAS模型的改進的同時性能也是優于GraphLab[23]和Giraph[25].GraphX不僅提供節點度(出度入度)的計算、子圖查詢、PageRank、最大連通圖及最短路徑等基本圖算法,并且能夠無縫地調用SparkCore中的API接口(包括map,filter,flatMap,sample,groupByKey,reduceByKey,union,join,cogroup,mapValues,sort,partionBy等).雖然基于GraphX的應用并不成熟,但是從運行效率及編程模型支撐的角度考慮,運用GraphX進行NBA傳球網絡數據的分析是一個較為理想的選擇.

1.2.2 相關籃球術語介紹

為了方便讀者對本文的閱讀及理解,表1對本文中涉及到籃球方面的一些專業術語或專有名詞(如NBA、NBA球隊、NBA賽制、技術統計等)進行解釋.

Table 1 Basic Professional Terminology

Continued (Table 1)

1.3 本文工作與已有工作的不同

本文研究范疇屬于圖的應用,圖廣泛應用于社交網絡,包括用戶網絡的社區發現、用戶影響力、能量傳播、標簽傳播等,用以提升用戶黏性和活躍度;而應用到推薦領域時,標簽推理、人群劃分、年齡段預測等可以提升推薦的豐富度和準確性.除社交網絡外,圖還在生物信息學、化學信息學、智能交通、輿情監控等等領域發揮著巨大的作用.由于GraphX于Spark版本1.2之后才發布正式版,導致基于GraphX的算法及應用方面的工作較少，并且,其應用場景通常在互聯網領域,如淘寶基于GraphX搭建了圖譜平臺,可以支撐多圖合并、能量傳播模型計算、用戶影響力計算、商品推薦等算法.在國內,嚴玉良等人在文獻[26]中提出一種基于GraphX的大規模頻繁子圖挖掘算法FSMBUS,使得算法性能較GRAMI提高一個量級.

在籃球數據研究方面,文獻[27]提出EPV(expected possession value)的概念,將球員場上的行為(如傳球、運球、投籃等)轉化為動態的EPV值,以此量化球員在球場上每次動作的價值；文獻[28]關注籃板球數據,將每次籃板數據的產生分解為Positioning,Hustle,Conversion三個階段,并基于籃板球數據對NBA中球員的籃板球能力進行了分析；文獻[29]對球員加速行為進行了量化研究,并對球員的加速數據進行了可視化；文獻[30]對NBA中的投籃選擇(2分球與3分球)與對應的風險進行了研究,分析了不同場景下的投籃選擇對比賽結果的影響；文獻[31]提出了通過防守矩陣(defensive metrics)分析并量化球員防守有效性的方法；文獻[32]對球員在投籃結束后的沖搶前場籃板與退位防守的選擇性問題進行了研究,研究結果表明退位防守能夠提高防守成功率,但減少了搶下前場籃板球的數量，文中還針對不同球隊的數據進行了分析,并提出相應的改進策略.

本文與已有研究工作不同的是,本文發現常規的籃球比賽統計中缺乏對傳球數據的統計,更缺乏對傳球數據的統計分析、價值挖掘及應用等方面的研究.本文將球員之間的傳球關系進行關聯(將傳球人與接球人作為頂點,頂點之間的傳球關系作為邊),發現隨著傳球數據量的不斷增加,最終形成一張穩定的傳球網絡圖.并且,本文將GraphX應用于NBA傳球數據的分析,通過建立球員之間的傳球網絡,充分挖掘傳球數據的內涵,為球員的訓練、戰術制定、對手分析、教練決策、游戲體驗改進等應用提供支撐.

2 傳球網絡圖的構建

2.1 圖的構建總體流程

傳球網絡圖的構建及應用框架流程圖如圖2所示,主要分為6個步驟:

1) 原始數據獲取.球隊及球員的傳球數據一般可通過NBA官方網站或通過具體場次的錄像分析提取數據.

2) 數據清洗及格式轉化.通過程序抓取而來的原始數據一般為XML或JSON格式,需通過數據清洗及格式轉化,以滿足網絡圖的構建對數據格式的要求.

3) 定義并構建Vertex表及Edge表.首先需根據后期應用的需求確定Vertex表及Edge表中的屬性,并通過步驟1與步驟2確定對應屬性數據是否可獲得或者是否可計算.

4) Vertex及Edge數據的持久化.由于Vertex表及Edge表為關系表,所以可選擇MySQL,Postgre-SQL,ORACLE等關系型數據庫存儲頂點及邊的數據.

5) 傳球網絡的構建及可視化.在步驟3的基礎上,通過GraphX構建出傳球網絡圖,通過提取并計算圖相關的數據(如傳球次數、PR值等)并結合大數據可視化技術,可實現傳球網絡圖的可視化.

Fig. 2 The construction and application framework of passing network diagram.圖2 傳球網絡圖構建及應用框架流程圖

6) 基于傳球網絡的應用:傳球網絡可輔助教練的決策、戰術支撐、輔助球員的訓練、對手分析、球員交易分析等.具體的應用場景分析請參見第4節.

下文將圍繞上述6個步驟進行詳細介紹,其中2.2節圍繞步驟1、步驟2的內容進行了詳細的闡述; 2.3節討論定義并構建Vertex表及Edge表的問題；2.4節介紹傳球網絡的構建方法. 步驟4在步驟2、步驟3的基礎上通過調用SparkSQL及對應數據庫的API便可完成. 而第3節闡述傳球網絡的可視化問題;第4節圍繞傳球網絡的應用場景進行分析.

2.2 傳球數據的獲取、清洗及格式轉化

籃球比賽中,常規的技術統計,如得分、籃板、助攻、搶斷、蓋帽、失誤、犯規、投籃命中率、出場時間等,在比賽過程中會被技術臺工作人員記錄下來.比賽結束后,球迷可通過各大體育網站或論壇查詢常規的技術統計數據.但是,對于傳球相關的數據,如Stephen Curry在總決賽的第1場比賽中有多少次傳球、多少次傳給了Klay Thompson、傳球的助攻轉化率等并不屬于常規的技術統計,加之比賽過程中傳球數據產生速度較快,很難通過現場人工的方法進行記錄.所以,現階段得到傳球數據的最好方法,就是通過觀看比賽錄像人工地對傳球數據進行記錄,但是該方法的弊端就是工作量巨大.

NBA作為世界上頂級籃球聯盟,其官方網站*http://www.nba.com于2016年開始公開包括傳球、防守影響、移動速度及距離等非常規技術統計.但是,中國的CBA及國家籃球隊,對于傳球數據的獲取、統計分析及圍繞傳球數據的戰術、訓練等方面的運用還是空白.雖然NBA官方網站提供傳球數據的查詢功能,但是并沒有提供轉存功能,通過手工收集整理數據效率太低,本文以金州勇士隊為例,傳球數據獲取流程如圖3所示.

如圖3所示為通過本文編寫的數據下載程序從NBA官網獲取金州勇士隊傳球數據的流程.流程步驟如下:

1) 收集金州勇士隊中每個隊員在NBA數據庫中所對應的playerid,如Stephen Curry的playerid=201939,Klay Thompson的playerid=202691.

Fig. 3 Data acquisition process.圖3 數據獲取流程

2) 將步驟1中所收集到的playerid形成playerids數組，該數組中存放著勇士隊中所有隊員的playerid.

3) 通過調用CURL API功能,通過拼接URL*http://stats.nba.com/stats/playerdashptpass,利用HTTP Get方法得到返回的數據,生成當前playerid所對應的JSON文件.CURL的Python調用如核心代碼1所示:

核心代碼1. CURL Python調用代碼.

forplayeridinplayerids:

os.system(′curl ″http:stats.nba.comstatsplayerdashptpass?′

′DateFrom=&′

′DateTo=&′

′GameSegment=&′

′LastNGames=0&′

′LeagueID=00&′

′Location=&′

′Month=0&′

′OpponentTeamID=0&′

′Outcome=&′

′PerMode=Totals&′

′Period=0&′

′PlayerID={playerid}&′

′Season=2015-16&′

′SeasonSegment=&′

′SeasonType=Regular+Season&′

′TeamID=0&′

′VsConference=&′

′VsDivision=″>{playerid}.json′.

format(playerid=playerid))

4) 循環playerids數組中所有的playerid,重復調用步驟3中的Python代碼,直到執行完playerids數組中所有的元素.最終生成如圖3所示的JSON文件集合,每個JSON文件對應一個球員的傳球數據.

特別地指出：在步驟3的代碼中,可修改具體的參數實現不同傳球數據的獲取,如參數DateFrom表示獲取傳球數據所對應的比賽開始時間,具體的參數及解釋如表2所示:

Table 2 Interpretation of Parameters

Continued (Table 2)

JSON(Javascript object notation)作為輕量級的數據交換格式,可以與XML(extensible markup language)格式相互轉化.本文中利用Python代碼將JSON文件中的數據轉化為pandas DataFrame,并將JSON中感興趣的字段解析出來,并存儲為CSV格式,核心代碼如下:

核心代碼2. JSON數據轉化代碼.

import pandas aspds

df=pds.DataFrame()

forplayeridinplayerids:

withopen(″{playerid}.json″.format(playerid=playerid)) asjson_file:

parsed=json.load(json_file) [′resultSets′][0]

df=df.append(pd.DataFrame(parsed

[′rowSet′],columns=parsed[′headers′]))

df=df.rename(columns={′PLAYER_ NAME_LAST_FIRST′: ′PLAYER′})

df[df[′PASS_TO′]

.isin(df[′PLAYER′])][[′PLAYER′, ′PASS_TO′,′PASS′]].to_csv(′passes.csv′,index=False)

df[′id′]=df[′PLAYER′].str.replace(′, ′, ′′)

2.3 定義并構建Vertex表及Edge表

由于Vertices,Edges,Triplets是GraphX中最重要的3個概念.其中Vertices類所對應的RDD為VertexRDD,屬性有ID及頂點屬性;Edges類所對應的RDD為EdgeRDD,屬性有源頂點的ID、目標頂點的ID及邊屬性;Triplets所對應的RDD類型為EdgeTriplets,而Triplets可通過所對應的Vertices與Edges經過JOIN操作得到,所以Triplets屬性有:源頂點ID、源頂點屬性、邊屬性、目標頂點ID、目標頂點屬性.由于GraphX統一了Table View與Graph View,即實現了Unified Representation,通過構造Vertex及Edge表,并將Vertex Edge表數據加載到Spark內存中便可構造出傳球網絡圖.

定義1. 傳球網絡圖. 傳球網絡圖用G={V,E}表示,其中V={p1,p2,…,pn}表示傳球網絡中所有球員的集合(設傳球網絡中球員的數量為n);而E={〈pi→pj〉|pi∈V,pj∈V}表示任意頂點(球員)之間傳球關系的集合,例如pi→pj表示球員pi傳球給pj.

在實際的傳球網絡應用場景中,設關系表Vertex(PLAYERID,PLAYERNAME)及Edge(PASSERID,PASSTOID,FREQUENCY,PASSNUM,AST,FGM,FGA,FGP,FGM2,FGA2,FGP2,FGM3,FGA3,FGP3)分布存儲節點集合V及關系集合E的數據.Vertex及Edge表數據字典如表3及表4所示.

結合Spark中對Vertices類的定義,字段PLAYERID為頂點ID,字段PLAYERNAME為頂點屬性.

結合Spark中對Edges類的定義,字段PASSERID為源頂點ID,字段PASSTOID為目標頂點ID,字段FREQUENCY,PASSNUM,AST,FGM,FGA,FGP,FGM2,FGA2,FGP2,FGM3,FGA3,FGP3都為邊屬性.特別地,在Edge表中,對于任意的PASSERID都需滿足約束(設Edge表中的FREQUENCY字段為變量Frequency，并設任意球員的傳球隊員數為i，其中i∈[1,n]):

Table 3 Data Dictionary of Table Vertex

Table 4 Table Edge’s Data Dictionary

(1)

并且,對于給定的〈PASSERID,PASSTOID〉,Frequency的計算公式為(設Edge表中PASSERID與PASSTOID字段為變量passerid與passtoid):

Frequency〈passerid,passtoid〉=

(2)

式(2)能計算出任意2個球員之間的傳球概率.設Edge表中FGM,FGA,FGP字段分別為變量fgm,fga,fgp,那么對于給定的〈PASSERID,PASSTOID〉,fgp可計算為

(3)

同樣,對于給定的〈PASSERID,PASSTOID〉,字段FGP2及FGP3的值可由計算為

(4)

(5)

在實際的應用場景中,變量Frequency,fgp,fgp2,fgp3是教練制定即時戰術最重要的數據支撐.

2.4 傳球網絡的構建

本節以2015—2016賽季的總冠軍騎士隊為例,構建其82場常規賽期間所有場次的傳球網絡圖.首先,通過2.2節中的數據獲取及清洗獲得傳球網絡圖的頂點數據如表5所示:

Table 5 The Cavaliers Passing Network Diagram’s Vertex Data

Continued (Table 5)

以2015—2016賽季NBA總決賽MVP LeBron James為例.通過解析2.2節中獲得的JSON數據,通過如下數據清洗及格式轉化程序(Scala代碼,如核心代碼3所示),得到符合2.2節中對邊Edge表結構的數據如表6所示.

核心代碼3. 數據清洗及格式轉化.

objectWebPageDataTransfer{

defmain(args:Array[String]):Unit={

vallines=Source.fromFile(″Cavaliers_data

James_LeBron.cvs″).

getLines().toList

varedges=lines.map {

line=>valfields=line.split(″ ″)

(″James_LeBron″,fields(0).toString,fields(2).toString,fields(3).toLong,fields(4).toLong,fields(5).toLong,fields(6).toLong,fields(7).toFloat,fields(8).toLong,fields(9).toLong,fields(10).toFloat,fields(11).toLong,fields(12).toLong,fields(13).toFloat)}

valpw=new PrintWriter(new File (″Cavaliers_dataout_dataJames_ LeBron.cvs″))

for (i<-edges) {

pw.write(i.toString()+″ ″)

}

pw.close()

}

}

數據格式轉化程序將原始數據從目錄Cavaliers_data讀入數據,數據處理完畢后將數據寫入out_data目錄中.

Table 6 LeBron James Regular Season’s Passing Network Edge Data

Notes: srcId,dstId and attr field are corresponding to the Edges class source vertex ID,target vertex ID and edge attribute. The attr can be further divided into: FREQUENCY,PASSNUM,AST,FGM,FGA,FGP,FGM2,FGA2,FGP2, FGM3,FGA3,FGP3.

表6只是LeBron James單個球員的數據,當將騎士隊所有隊員的傳球數據累加便形成整個球隊82場常規賽所有的傳球數據.構建騎士隊常規賽騎士對傳球網絡的Spark GraphX如核心代碼4所示:

核心代碼4. 騎士隊常規賽傳球網絡構建.

① package Cavaliers.pass.anlaysis.datamaker

② import org.apache.spark._import org.apache.spark.graphx._import org.apache.spark.rdd.RDD

③ objectCavalierPassNetWork{

④ defmain(args: Array[String]): Unit={

⑤ valconf=newSparkConf().setAppName(″CavalierPassNetWork″).setMaster(″local[4]″)

⑥ valpasses:RDD[String]=sc.textFile(″Cavaliersedgs.cvs″)

⑦ valplayer:RDD[String]=sc.textFile(″Cavaliersvertex.cvs″)

⑧ valvertices:RDD[(VertexId,String)]=player.map{

line=>valfields=line.split(″ ″)

(fields(0).toLong,fields(1))

}

⑨ valedges:RDD[Edge[(String,Long, Long)]]=passes.map{

line=>valfields=line.split(″ ″)

Edge(fields(0).toLong,fields(1).toLong,(fields(2).toString(),fields(3).toLong,fields(4).toLong))

}

⑩ valgraph=Graph(vertices,edges)

在如上傳球網絡構建代碼中,行⑥⑦代碼分別將頂點與邊的數據從cvs文件中讀取到內存,行⑧從player常量構建圖頂點,行⑨在行⑥常量pass的基礎上構建傳球網絡的邊,邊的屬性可根據應用場景進行自定義.行⑩在常量vertices及edges的基礎上,通過調用Graph類的構造函數,構造出傳球網絡graph,為傳球網絡的應用打下基礎.

3 傳球網絡的可視化研究

3.1 傳球網絡與社交網絡可視化的不同

大數據可視化技術將枯燥的海量數據通過圖表的形式展示出來,能夠更加直觀地向用戶展示數據之間的聯系,從而減少用戶挖掘數據內涵所耗費的時間.對于具有海量節點和邊的大規模網絡,如何在有限的屏幕空間中進行可視化,是大數據時代的可視化技術面臨的難點和重點[33].Herman等人[34]對圖的可視化基本方法和技術進行了綜述,雖然針對圖的可視化研究人員提出了不少的新方法與技術(如樹圖技術Treemaps[35]、Voronoi圖填充[36]、綜合性的TreeNetViz[37]等),但是經典的基于節點和邊的可視化方法依然是圖可視化的主要形式.

傳球網絡的可視化與社交網絡圖的可視化非常類似,其中社交網絡圖可通過NodeXL等工具進行可視化.但是,本文在嘗試利用NodeXL繪制傳球網絡圖時,發現NodeXL等社交網絡的可視化工具并不適合傳球網絡的可視化.因為傳球網絡相比社交網絡單純的好友關系,需要表達出4項更多的個性化信息:

1) 傳球網絡圖中球員重要性的區分.因為不同的球員在傳球網絡中的地位與影響力有所不同(如常規賽MVP Stephen Curry在傳球網絡中的重要度肯定比其他角色球員高).本文通過設定不同頂點的半徑,以此區分不同球員在傳球網絡中的重要性,所以,需要探索計算球員重要性的方法.

2) 傳球網絡中球員角色(位置)的區分.NBA中場上5名隊員角色有控球后衛(point guard)、得分后衛(shooting guard)、小前鋒(small forward)、大前鋒(power forward)及中鋒(center),不同的位置擔任的場上任務、跑位、戰術、傳球方法等等存在著很大的差異,所以傳球網絡中應區分不同球員的位置.本文中將球員的角色用不同顏色的頂點表示,解決不同球員之間的角色區分問題.

3) 任意2個球員之間傳球次數(頻率)的區分.球員之間的傳球次數屬于邊的屬性信息,為了表達任意2個球員之間的傳球次數,可采用具體數字標注的形式,即在邊上顯示具體的傳球數據.但是,實踐中發現由于邊的數量龐大,采用數字標注的方法導致傳球網絡圖過于雜亂.因此,本文中將傳球次數(或頻率)信息通過邊的粗細來表達,即2個球員之間的傳球次數越多,他們之間的邊越粗;反之,他們之間的傳球次數越少,邊越細.

4) 傳球網絡圖的用戶交互能力.傳統數據可視化技術大多通過靜態的圖片進行數據展示,不具備動態的交互能力.本文生成的傳球網絡圖由于底層采用JavaScript腳本,通過瀏覽器展示傳球網絡圖的同時提供動態的用戶事件響應機制,用戶可利用鼠標操作關注某一特定球員的傳球情況.

3.2 傳球網絡可視化的輸入數據

綜合3.1節中的4點個性化需求,本節從超過10種(如iCharts,Fusion Charts Suit,Modest Maps,Chartkick,Bonsai,Google Charts,Gephi,Protvis等)可視化工具(框架)中,挑選出networkD3(R語言中基于JavaScript的數據可視化工具)框架中的forceNetwork作為傳球網絡的可視化工具.利用networkD3繪制forceNetwork傳球網絡圖需要準備的輸入數據有2類:

1) 頂點數據.頂點數據包括頂點名稱、頂點ID、頂點分類信息(區分球員位置)、頂點大小(區分球員重要性).頂點數據中,頂點名稱為球員姓名PLAYERNAME字段,頂點ID為PLAYERID字段.

2) 邊數據.邊數據包括源節點、目標節點、邊屬性.其中,源節點與Edge表中的PASSERID字段對應；目標節點與Edge表中的PASSTOID字段對應；邊屬性可根據應用場景或用戶需求的不同進行自定義.例如，如果用戶關注球員之間的傳球次數,則邊屬性為Edge表中PASSNUM字段;如果用戶關注2個球員之間的傳球助攻轉化情況,則邊屬性為Edge表中的AST字段.

球員分類數據需要人工標注,由于某些球員可打2個以上的位置(如Tristan Thompson可打中鋒與大前鋒2個角色),所以實踐中并不是嚴格按照控球后衛、得分后衛、小前鋒、大前鋒、中鋒的角色進行劃定,而是定義出5種新的角色分類:Guard,Forward,Center,Forward-Guard,Forward-Center.同樣以騎士隊為例,球員位置分類及顏色信息如表7所示:

Table 7 The Cavaliers Player’s Position Classification Table

3.3 球員在傳球網絡中的重要度計算

計算球員重要度(即傳球網絡中頂點半徑大小)本質上與計算網頁重要度算法PageRank思想非常類似,都是將圖中節點的重要性映射為一個具體的數字.所以借鑒Google的PageRank算法,本文提出計算球員在傳球網絡中重要程度的算法PlayerRank,其計算為

(6)

由于GraphX中提供了PageRank的實現,在2.4節中傳球網絡構造的基礎上,通過調用PageRank API能夠快速地對球員重要度進行計算.但是,PageRank算法的輸入參數并不支持計算邊的屬性(如傳球次數、頻率等),所以需要將2.4節中的傳球網絡進行變換,才能進行球員重要度的計算.如圖4為數據轉化示例.

如圖4所示,將選出Edge Table中的一條記錄作為示例,示例中passerid=2544,passtoid=202618,passnum=721,這行記錄表示LeBron James在常規賽期間總共給Kyrie Irving傳球721次.轉化為只有字段PASSERID與PASSTOID的臨時表,并且passerid值為2544,passtoid值為202618,并將行重復721次.數據變換程序的Scala核心代碼如下:

Fig. 4 Input data transformation for PR computing.圖4 PR計算輸入數據變換示例

核心代碼5. PageRank算法數據變換程序.

① objectScalaGenPassFile{

② defmain(args:Array[String]):Unit={

③ vallines=Source.fromFile(″passes. csv″).getLines().toList

④ varedges=lines.map{line=> valfields=line.split(″ ″) (fields(0).toLong,fields(1).toLong,fields(2).toLong)}

⑤ varjavalist=new JavaList[String]()

⑥ for (i<-edges)

⑦ for (j<-0 toi._3.toLong.toInt-1)

⑧javalist.add((i._1.toLong,i._2.toLong).toString())

⑨ valpw=new PrintWriter(new File (″PRdataRPInputdata.cvs″))

⑩ for (i<-javalist.toArray())

核心代碼6. 球員重要度計算.

① objectCavalierPR{

② defmain(args:Array[String]):Unit={

③ valconf=newSparkConf().setAppName(″CavalierPR″).setMaster(″local[4]″)

④ valsc=newSparkContext(conf)

⑤ valpass_file:RDD[String]=sc.textFile(″PRdataRPInputdata.cvs″)

⑥ valplayer_file:RDD[String]=sc.textFile(″PRdataCavalier_ players.cvs″)

⑦ valvertices:RDD[(VertexId,String)] =player_file.map{line=>valfields=line.split(″ ″) (fields(0).toLong,fields(1))}

⑧ valedges:RDD[Edge[Long]]=pass_file.map{line=> valfields=line.split(″ ″) Edge(fields(0).toLong,fields(1).toLong)}

⑨ valgraph=Graph(vertices,edges)

⑩ valcavalier_PR_value=graph.pageRank(0.01,0.15).vertices

Table 8 The Cavaliers Player’s PlayerRank Computing Result

從騎士隊球員重要度計算結果我們發現,PlayerRank值超過1的一共有5名球員,而這5名球員在常規賽期間通常出任首發球員.其中,LeBron James的PlayerRank值達到了驚人的2.55;而首發控球后衛Matthew Dellavedova其PlayerRank值也達到了1.99;而Kyrie Irving與Kevin Love的PlayerRank值都在1.77左右.雖然Tristan Thompson也經常擔任先發球員,但是由于他的位置為中鋒,傳接球的機會較少,導致其PlayerRank較低.PlayerRank值除了能夠評估一個球員在傳球網絡中的重要程度外,另外一個重要作用就是可以得出一個球隊球員之間的球權分配情況.

3.4 ForceNetwork可視化傳球網絡

NetworkD3是R語言下的一個繪圖工具包,使用前必須安裝NetworkD3包,然后通過library(networkD3)導入到程序中.R語言繪制騎士隊傳球網絡圖核心代碼如下:

核心代碼7. R語言繪制傳球網絡.

① library(networkD3)

②passes<-read.csv(″RPInputdata.cvs″)

③groups<-read.csv(″groupsR.csv″)

④size<-read.csv(″cavalier_PR_value.cvs″)

⑤passes$source<-as.numeric(as.factor(passes$PASSERID))-1

⑥passes$target<-as.numeric(as.factor(passes$PASSTOID))-1

⑦passes$PASSNUM<-passes$PASSNUM50

⑧groups$nodeid<-groups$PlayerName

⑨groups$name<-as.numeric(as.factor(groups$PlayerName))-1

⑩groups$group<-as.numeric(as.factor(groups$label))-1

Fig. 5 Cavaliers regular season passing network diagram.圖5 騎士隊常規賽傳球網絡圖

騎士隊傳球網絡圖中頂點的數量為17,邊的數量為216.圖5中不同位置的球員顏色不同,并且球員的PlayerRank值越大,頂點越大,任意2個球員之間的傳球數越多,連接他們之間的邊越粗.通過圖5不難發現,首發球員的PlayerRank值高,并且他們之間的傳球數多.通過顏色可以發現LeBron James與Kevin Love顏色相同,位置都為前鋒(forward);而在Kyrie Irving與Matthew Dellavedova都為后衛(guard);如果將總決賽期間的傳球網絡與常規賽進行對比,就會發現由于LeBron James與Kevin Love及Kyrie Irving與Matthew Dellavedova位置的重疊,同一位置PlayerRank值接近的2個球員很難在比賽中都發揮出色.

在2015—2016賽季創造了NBA常規賽歷史最佳戰績(73勝9負)、NBA開局最長連勝紀錄(24連勝)以及NBA主場最長連勝紀錄(54連勝)的金州勇士隊,其常規賽傳球網絡圖如圖6所示：

Fig. 6 Warriors regular season passing network diagram.圖6 勇士隊常規賽傳球網絡圖

4 傳球網絡應用場景及分析

通過GraphX構建傳球網絡,能夠利用GraphX提供的API分析傳球網絡中頂點及頂點屬性、邊及邊的屬性信息,并提供了深入挖掘傳球數據內涵的接口.傳球網絡圖實質上是一個球隊傳球數據的畫像,可幫助球員、教練、球隊、球迷各種不同角色的人從不同的層面去挖掘傳球數據,并以此給他們帶來幫助.傳球網絡從不同角色、不同方面的應用場景很多,本文無法窮舉.

4.1 NBA傳球數據對比賽結果的影響分析

通過數據獲取、清洗及統計整理后,對2013—2014,2014—2015,2015—2016賽季常規賽期間的傳球數據進行了總體統計,統計結果如表9所示.以2015—2016賽季為例,NBA中30支隊伍在2015—2016賽季總共進行了1 228場比賽,比賽總時間為593 840 min.而在這1 228場比賽中,總共產生了747 761次傳球,平均每場每隊的傳球數為304.46. 而這些傳球產生的助攻總數為54 728,即NBA比賽平均傳球13.663次才能產生1次助攻.

觀察表9中數據不難發現3個賽季中場均傳球次數在不斷地增加,從2013—2014賽季的場均299.98次,增長到2014—2015賽季的301.36次,以及到2015—2016賽季的304.46次.場均傳球次數的增長原因是因為聯盟中不少球隊受到金州勇士隊“小球”戰術(籃球術語中“小球”又稱“跑轟”,就是主要以突破和外線為主的打法)的影響,從而改變了這些球隊的比賽風格和戰術選擇.而“小球”戰術弱化了傳統中鋒的作用,比賽節奏快,相同時間內的進攻回合數更多,所以導致場均傳球次數增加.

表10將2015—2016賽季30支球隊的場均傳球數據進行了匯總,包括場均傳球數、場均助攻數、傳球助攻比(產生1次助攻需要的傳球數量)、傳球助攻率(1次傳球轉化為助攻的概率)以及球隊在2015—2016賽季的勝率(賽季總場次除以勝利場次).通過表10數據可統計出聯盟30支球隊的場均助攻數為22.277,傳球助攻率平均為7.347%.其中場均傳球數最多的為Utah Jazz隊,達到了場均354.8次;而最少的為Oklahoma City Thunder隊,場均傳球數量僅為264次,比場均最多的Utah Jazz少了90.8次之多.場均助攻數方面Golden State Warriors達到聯盟最高的28.9次,比墊底的Los Angeles Lakers的18次多出整整10.9次.Golden State Warriors以高達8.945%的傳球助攻率領跑全聯盟,而Utah Jazz的傳球助攻率僅為5.355%.本文將球隊的勝率與傳球數據(包括場均傳球數、場均助攻數、傳球助攻率)進行對比分析,其對比結果如圖7所示：

Table 9 NBA Three Season’s Overall Statistical Results for Passing Data

Table 10 Per Game Passing Data Summary for All Team in Season 2015—2016

Fig. 7 The relationship between the passing data and winning rate.圖7 球隊勝率與傳球數據之間的關系

Fig. 8 Analysis of the impact of passing data on the outcome of the game (Win or Loss) in 2015—2016 session.圖8 2015—2016賽季傳球數據對比賽結果(贏或輸)的影響分析

圖7(a)表示場均傳球次數與勝率之間的關系;圖7(b)表示傳球助攻率與勝率之間的關系;圖7(c)表示場均助攻數與勝率之間的關系.從圖7(a)中不難看出場均傳球次數與勝率之間并無直接關系(或相關性很小);而圖7(b)則能看出總體上傳球助攻率越高,球隊戰績越好;而從圖7(c)中能看出場均助攻數與球隊勝率之間的較強相關性,場均助攻數越高的球隊勝率越高,場均助攻數與勝率呈現較強的正相關.從圖7中的對比可以得出結論:球隊戰績(或勝率)與傳球的數量并無直接關系,但是與傳球質量(傳球助攻轉化率與場均助攻數越高,傳球質量越高)相關性較大.常規賽創造了NBA常規賽歷史最佳戰績(73勝9負)的金州勇士隊,其傳球助攻轉化率及場均助攻數均為聯盟第一.以上數據及結論可以輔助球隊及教練,1)可以從數據中找出球隊傳球方面存在的問題(無論是傳球數量,或是傳球質量);2)可以輔助制定提高傳球質量的戰術或具體的訓練項目.

為了分析傳球數據對比賽結果(贏球或輸球)的影響,本文將30支隊伍的贏球(總計1 228場贏球記錄)與輸球(總計1 228場輸球記錄)條件下的場均傳球數、場均助攻數及傳球助攻轉化率進行了統計,其結果如圖8所示.其中圖8(a)為贏球與輸球條件下的場均傳球數對比,雖然總體上贏球條件下的場均傳球數(304.66)略大于輸球條件下的場均傳球數(304.3),但是觀察圖8(a)可以發現場均傳球數并不直接影響比賽結果.圖8(b)為贏球與輸球條件下的場均助攻數的對比,觀察圖8(b)不難發現30支球隊贏球時的場均助攻數都大于輸球時的場均助攻數;實際上,2015—2016賽季30支球隊的1228場贏球記錄的平均場均助攻數為23.65,而輸球的平均場均助攻數為20.82.圖8(c)為贏球與輸球條件下的傳球助攻轉化率的對比,不難發現29支隊伍贏球條件下的傳球助攻轉化率都比輸球時候高(其中只有Dallas Mavericks隊贏球與輸球條件下的傳球轉化率基本持平);實際上所有贏球時的平均傳球助攻轉化率為7.799%,而輸球時的平均助攻轉化率為6.876%.結合圖8(a)(b)(c)可以得出結論:場均傳球數本身不對比賽結果產生影響,而傳球質量(如場均助攻數、傳球助攻轉化率)會對比賽結果產生巨大的影響,同時這個結論與圖7中得出的結論相吻合.

4.2 球隊傳球網絡應用

4.2.1 基于傳球網絡的整體傳球數據分析

以2015—2016賽季總冠軍球隊騎士隊常規賽數據為例,在構建表Vertex及Edge并構建傳球網絡(如圖5所示)的基礎上,可通過Vertex及Edge的JOIN操作導出傳球表及接球表的數據(過濾掉傳球或接球數小于100的球員).為了實現對球隊整體傳球數據的分析,為將來的戰術制定打下基礎,其中表11為球隊傳球數據表,表12為接球數據表.

Table 11 Passing Data Summary for Cavalier in Regular Season 2015—2016

圖9對整個2015—2016賽季騎士隊核心球員(傳球或接球次數大于100)的傳接球數據進行了對比.其中圖9(a)(b)關注球員的傳球與接球量(PASSNUM與Received Number),包括傳接球的總數及在全隊傳接球中所占的比例(FREQUENCY).從圖9(a)中可以看出,在騎士隊中傳球最多的前5位球員為:James,Love,Dellavedova,Irving,Thompson;而接球數最多的前5位球員為:James,Dellavedova,Irving,Love,Smith.而圖9(c)(d)關注球員傳球與接球的質量,指標包括傳球與接球產生助攻的概率(Pass_AST_Probability與Receive_AST_Probalility)、總體命中率(FGP)、2分球命中率(FGP2)及3分球命中率(FGP3).圖9(c)反映的是球員傳球的質量,其中最重要的指標為助攻轉化率,其中James,McRae,Dellavedova,Irving,Shumpert的傳球助攻轉化率較高,其中James達到了驚人的13.45%,很好地解釋了James持球率高的原因.圖9(d)反映的是球員接到傳球后轉化為得分的能力,其中Mozgov,Thompson,Frye,Smith,Jefferson的接球助攻轉化率較高;而投籃命中率可以輔助教練制定戰術,并幫助球員做場上的傳球決策.

Table 12 Passing Data Summary for Cavalier in Regular Season 2015—2016

Fig. 9 Comparison of players passing and receiving data in 2015—2016 regular season of Cavaliers.圖9 2015—2016賽季常規賽騎士隊球員傳球及接球數據對比

4.2.2 基于傳球網絡的戰術人員選擇

籃球進攻戰術中無論是的擋拆戰術、傳切配合還是三角進攻,都是建立在有效的移動與傳球基礎上.那么,教練在制定戰術過程中就需要通過球員角色、移動數據、傳球數據及投籃命中率等數據綜合考量并選擇戰術的執行者.由于通過3.4節中構建的傳球網絡(如圖5,6所示)中包含了球員角色、任意2個球員之間的傳球數量及質量相關的數據、投籃命中率等數據,可以很好地協助教練基于數據選擇合適的戰術執行者.

例如挑選傳切配合執行者時,教練可首先基于傳球網絡進行傳球數據的篩選,選擇條件為:配合熟練度高(相互傳球數較多)、傳球質量高(助攻數較多),并且戰術執行成功率可能性高(投籃命中率高)的球員對.以騎士隊為例,在圖9(c)的基礎上,教練能夠通過數據挑選出傳球質量高的前6為球員:James,McRae,Dellavedova,Irving,Shumpert,Smith作為傳切配合的傳球人.而通過圖9(d)教練能夠挑選出助攻轉化率高且投籃命中率高的球員,如果關注進攻成功率,應當以投籃命中率為球員選擇標準,可以挑選出球員:Thompson,Mozgov,James,Jefferson,Irving;但是由于傳切有球員角色限制,而Thompson,Mozgov都為中鋒,所以去掉他們;最終得到適合切入的球員有:James,Jefferson,Irving.在傳球人名單及切入人名單確定后,教練再根據每個球員的特點,將球員劃分為組,分別進行戰術訓練;最后采集訓練過程中戰術執行的成功率數據,最終確定戰術的執行球員.

4.2.3 基于傳球網絡的臨場戰術制定

籃球比賽在暫停結束后、一節比賽只剩一次進攻時間、甚至比賽時間所剩無幾卻落后時,教練需要重新布置一次進攻戰術.特別是最后一次投籃決定比賽勝負時,教練的戰術制定就顯得尤為重要.無論戰術選擇投籃為2分球還是3分球,都可結合圖9(c)選擇合適的傳球人，并通過圖9(d)選擇接球并執行投籃的人.當然,教練的人員選擇需要與當場比賽球員的狀態進行結合.實際上,當前的NBA教練選擇執行絕殺的球員往往只是根據當場球員的狀態決定,這樣使得對方教練很容易猜出執行絕殺的球員,制定針對性的防守策略,從而大大減小絕殺成功的可能性.

假設教練需要制定3分絕殺戰術,結合歷史傳球數據,可通過圖9(d)選出適合執行絕殺的球員名單: McRae(60%),Dellavedova(41.6%),Smith(40.3%),Jefferson(38%),Frye(37.7%),Love(36.4%)，其中McRae僅有10次投籃,所以數據真實性較低，而James與Irving分別只有30.5%與32.4%的命中率.所以,根據歷史數據,可將James與Irving作為絕殺戰術中的傳球執行人(對方教練的防守重心在他們身上),將Smith或Dellavedova作為絕殺執行者.

如圖10所示為一種基于傳球數據的3分絕殺戰術示例,首先由Thompson邊線發球給James,Irving沿著跑動路線所示從3分頂部跑到底線附近吸引防守壓力,同時Smith沿著跑動路線指示迅速跑動到投籃點,并借助Love的檔人與防守隊員拉開空間,James傳球給Smith并完成絕殺,絕殺成功率在40%左右.

Fig. 10 The 3 points tactical lore based on passing data analysis.圖10 基于傳球數據的3分絕殺戰術

4.3 傳球網絡子圖應用

GraphX中Structural Operators主要有reverse,subgraph,mask,groupEdges四種函數,其中對于傳球網絡分析最有用的操作是subgraph.subgraph可以在傳球網絡的基礎上抽取出特定條件的子圖,例如可通過如下代碼抽取出Stephen Curry常規賽期間的傳球情況:

核心代碼8. 網絡子圖抽取代碼.

valsubgraph_Curry=graph.subgraph(epred=e=>e.srcId==201939)

如圖11所示為庫里的子圖抽取結果,從圖11中可以很直觀地看出庫里傳球的分布情況.在子圖的基礎上可以針對子圖及邊的屬性,挖掘特定球員的傳球數據內涵.通過查詢子圖的邊屬性并過濾場均傳球次數大于1的球員,將得到的數據除以Stephen Curry比賽的場次,可以得到Stephen Curry傳球數據如表13所示:

Fig. 11 Subgraph extraction results for Stephen Curry.圖11 球員庫里的子圖抽取結果

一方面,Stephen Curry本人及教練可根據表13數據改進比賽戰術,Stephen Curry有34.8%的球傳給了Green,但是卻只有7.61%的助攻轉化率,而傳給Thompson時的助攻轉化率達到了驚人的19.44%,這就要求Stephen Curry當Thompson出現投籃機會后,需要多傳球給Thompson；而另一方面,其他球隊可根據表13制定防守Stephen Curry的策略,可盡量讓他傳給不在攻擊范圍內且命中率較低,或助攻轉化率低的球員(如Barbosa,Iguodala,Rush)，尤其要防止傳給Thompson或處在內線的Bogut及Ezeli等內線球員.

而表14所示為庫里常規賽期間的場均接球數據,結合表13數據發現Stephen Curry與Green之間的傳接球(傳球率為34.8%,接球率為41.6%)最為密切.所以,其他球隊與勇士隊比賽時,重點需要切斷Stephen Curry與Green之間的配合.并且需要注意內線的Bogut傳球給外線的Stephen Curry時,命中率達到驚人的58.1%,這些數據及分析方法能幫助球隊制定針對性的防守策略并提高防守效率.

Table 13 Per Game Passing Data Summary for Stephen Curry

Table 14 Per Game Received the Pass Data Summary for Stephen Curry

如果將傳球網絡子圖中節點的大小替換為該球員傳球時的助攻轉化率,如圖12所示為Stephen Curry的傳球助攻轉化效率的圖示.圖12一方面可幫助球員明確與特定隊友之間的配合效率,協助球員在球場上做出更優化的傳球選擇;另一方面可幫助教練了解任意2個球員之間的配合默契程度,為教練戰術人員選擇提供幫助.同樣,也可以將傳球失誤率等作為子圖節點大小,讓球員明確需要與哪些隊友的配合需要改進,并在訓練中得以加強,可以減小比賽中的失誤次數.

Fig. 12 The pass assist transformation efficient for Stephen Curry.圖12 球員庫里的傳球助攻轉化效率

4.4 傳球網絡在游戲中的應用

即便在頂級的籃球游戲NBA2K16中,游戲中的球員傳球與真實的NBA比賽中的球員傳球存在著巨大的差距.主要存在3個問題:1)游戲中缺乏對傳球數據的統計;2)游戲中球員傳球的場均次數與真實比賽中的傳球次數有差距;3)游戲中任意2個球員之間的傳球頻率與真實比賽中的傳球頻率有較大偏差、并且游戲中對于球員之間的傳球失誤場景的模擬,真實性較差. NBA2K16是對真實的NBA比賽的模擬,存在的這些問題會導致游戲模擬的真實性降低,從而降低游戲者的體驗.

但是,在傳球網絡建立的基礎上,并通過4.3節的建立網絡子圖,對于任意的球員、在游戲中的任意時刻,可利用網絡子圖中的邊屬性FREQUENCY%,建立球員的傳球概率模型.設P表示游戲中場上的任意一個球員,并設P場上的其他4個隊友為P1,P2,P3及P4,而PrP→Pn(n∈[1,4])表示游戲中球員P傳球給其他4位隊友的概率.PrP→Pn的值為

(7)

其中FP→Pn表示傳球網絡中連接球員P與Pn之間邊的屬性FREQUENCY%的值.

例如，以Stephen Curry為例,表13中的FREQUENCY字段是Stephen Curry在真實的NBA賽場中的傳球概率,假設游戲中Stephen Curry擔任控球后衛,并且其他4位隊友為:中鋒Bogut、大前鋒Green、小前鋒Iguodala及得分后衛Thompson.FP→Pn的值如表15所示:

Table 15 Stephen Curry’s Pass Frequency

那么根據式(7)可計算出在游戲中Stephen Curry的傳球概率分布情況，如表16所示:

Table 16 Stephen Curry’s Pass Frequency in the Game

表16中的數據表示的是Curry與Green等其他4名球員之間的總體傳球概率分布.無論是在真實的NBA賽場還是游戲中,球員的任意一次傳球都是屬于隨機事件,與接球人的位置、防守人的位置、離籃筐的距離、接球人的角色、戰術種類等都有很大關系.而表16中的概率值只能作為游戲中球員傳球決策計算中的一個參數,并且,傳球網絡除了可以輔助計算球員在游戲中的傳球決策外,在記錄游戲中的傳球數據的基礎上還可以將傳球網絡嵌入到游戲中,在賽后將傳球網絡圖呈現給游戲者,從而增加游戲者的體驗.

5 結論及下一步工作

大數據時代并不代表所有應用數據量都大,大數據最核心的問題怎樣挖掘大數據的價值.隨著以MapReduce計算模型為核心的大數據技術的不斷成熟,其在社交網絡、電子商務、金融、公共安全、健康醫療等領域不斷發揮著巨大的價值;但是在競技體育方面,大數據的相關應用研究還處于探索階段.本文研究范疇屬于圖的應用,圖廣泛應用于社交網絡、生物信息學、化學信息學、智能交通、輿情監控等等領域.

本文發現籃球比賽中除得分、籃板、助攻、搶斷、蓋帽、失誤、犯規、投籃命中率、出場時間等常規技術統計外,缺乏對傳球數據的記錄,更缺乏對傳球數據的統計分析、數據挖掘及應用方法的研究.本文將球員之間的傳球關系進行關聯,發現隨著傳球數據量的不斷增加,最終形成一張穩定的傳球網絡圖.所以本文圍繞傳球數據形成的傳球網絡進行研究.1)經過傳球數據的獲取、數據清洗及格式轉化、Vertex及Edge表構建的基礎上,通過GraphX構建傳球網絡圖,為傳球網絡的應用打下基礎.2)在傳球網絡可視化研究方面,由于與社交網絡的可視化存在諸多的不同,本文研究了區分球員在傳球網絡中的角色、重要度、傳球次數等信息的方法.3)在構建GraphX傳球網絡圖及可視化研究的基礎上,本文分析了傳球數據對比賽結果的影響、球隊傳球數據分析、戰術人員選擇、臨場戰術制定、傳球網絡子圖及游戲體驗等方面的應用.

下一步工作主要集中在4個方面:

1) 高效的傳球數據獲取方法的研究.由于已有的傳球數據只能由人工現場統計或錄像分析的方法得到,效率低下并且不能避免人為錯誤.所以,需要與圖像識別及視頻處理等技術相結合,研究自動從比賽錄像中提取傳球數據的方法.

2) 本地化的基于傳球網絡的應用開發.中國的CBA甚至是中國男籃,對常規技術統計數據的價值挖掘及應用都停留在初級階段.所以,研究基于傳球網絡的應用軟件,從而簡化傳球數據的獲取到數據價值轉化的過程,是推動籃球競技數據化、智能化的關鍵.

3) 傳球數據與其他技術統計的關聯分析.需在已有的傳球數據中擴展傳球類型、速度、失誤概率、傳球距離等信息,并挖掘傳球數據與球員位置、得分、失誤、助攻等其他技術統計數據之間的關聯關系.

4) 將傳球網絡的研究與應用擴展到其他球類運動.本文的傳球數據來自于籃球賽場,可將傳球網絡的研究與應用擴展到其他球類運動,如足球、排球、橄欖球、水球、手球等.

[1]International Data Corporation. The digital universe in 2020: Big data, bigger digital shadows, and biggest growth in the far east[EB/OL].[2015-12-15]. http://www.emc.com/collateral/analyst-reports/idc-the-digitaluniverse-in-2020.pdf

[2]Meng Xiaofeng, Ci Xiang. Big data management: Concepts, techniques and challenges[J]. Journal of Computer Research and Development, 2013, 50(1): 146-149 (in Chinese)(孟小峰, 慈祥. 大數據管理: 概念、技術與挑戰[J]. 計算機研究與發展, 2013, 50(1): 146-149)

[3]Ghemawat S, Gobioff H, Leung S T. The Google gile system[C] //Proc of the 19th ACM Symp on Operating System Principles. New York: ACM, 2003: 29-43

[4]Dean J, Ghemawat S. MapReduce: Simplifed data processing on large clusters[C] //Proc of the 6th Symp on Operating System Design and Implementation. New York: ACM, 2004: 137-150

[5]Zaharia M, Chowdhury M, Franklin M J, et al. Spark: Cluster computing with working sets[C] //Proc of the USENIX Conf on Hot Topics in Cloud Computing. Berkeley: USENIX Association, 2010: 1765-1773

[6]Xin R S, Gonzalez J E, Franklin M J, et al. GraphX: A resilient distributed graph system on Spark[C] //Proc of the Int Workshop on Graph Data Management Experiences and Systems. New York: ACM, 2013: 1-6

[7]Gonzalez J E, Xin R S, Dave A, et al. Graphx: Graph processing in a distributed dataflow framework[C] //Proc of the 11th USENIX Symp on Operating Systems Design and Implementation (OSDI’14). Berkeley: USENIX Association, 2014: 599-613

[8]Inokuchi A, Washio T, Motoda H. An apriori-based algorithm for mining frequent substructures from graph data[C] //Proc of the 4th European Conf on Principles of Data Mining and Knowledge Discovery. Berlin: Springer, 2010: 13-23

[9]Kuramochi M, Karypis G. Frequent subgraph discovery[C] //Proc of the 1st IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2001: 313-320

[10]Yan Xifeng, Han Jiawei. Gspan: Graph-based substructure pattern mining[C] //Proc of the 2nd IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2002: 721-724

[11]Huan Jun, Wang Wei, Prins J. Efficient mining of frequent subgraphs in the presence of isomorphism[C] ///Proc of the 2nd IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2003: 549-552

[12]Bhuiyan M A, Hasan M A. An iterative MapReduce based frequent subgraph mining algorithm[J]. IEEE Trans on Knowledge & Data Engineering, 2013, 27(3): 608-620

[13]Lu Wei, Chen Guang, Tung A K H, et al. Efficiently extractiong frequent subgraphs using mapreduce[C] //Proc of the 1st IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2013: 639-647

[14]Liao Bin, Yu Jiong, Zhang Tao, et al. Energy-efficient algorithms for distributed file system HDFS[J]. Chinese Journal of Computers, 2013, 36(5): 1047-1064 (in Chinese)(廖彬, 于炯, 張陶, 等. 基于分布式文件系統HDFS的節能算法[J]. 計算機學報, 2013, 36(5): 1047-1064)

[15]Liao Bin, Zhang Tao, Yu Jiong, et al. Energy consumption modeling and optimization analysis for MapReduce[J]. Journal of Computer Research and Development, 2016, 53(9): 2107-2131 (in Chinese)(廖彬, 張陶, 于炯, 等. MapReduce能耗建模及優化分析[J]. 計算機研究與發展, 2016, 53(9): 2107-2131)

[16]Righi R D R, Gomes R D Q, Rodrigues V F, et al. MigPF: Towards on self-organizing process rescheduling of bulk-synchronous parallel applications[J/OL]. Future Generation Computer Systems, 2016, 32(5): 1-18 [2016-08-01]. http://www.sciencedirect.com/science/article/pii/S0167739X16301145

[17]Righi R R D, Pilla L L, Carissimi A, et al. MigBSP: A novel migration model for bulk-synchronous parallel processes rescheduling[C] //Proc of the IEEE Int Conf on High Performance Computing and Communications. Piscataway, NJ: IEEE, 2009: 585-590

[18]Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 135-146

[19]Salihoglu S, Widom J. Optimizing graph algorithms on pregel-like systems[J]. Proceedings of the VLDB Endowment, 2014, 7(7): 577-588

[20]Han M, Daudjee K, Ammar K, et al. An experimental comparison of pregel-like graph processing systems[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1047-1058

[21]Sengupta D, Song S L, Agarwal K, et al. GraphReduce: Processing large-scale graphs on accelerator-based systems[C] //Proc of the 15th Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2015: 1-12

[22]Garimella K, Morales G D F, Gionis A, et al. Scalable facility location for massive graphs on pregel-like systems[C] //Proc of the 24th ACM Int on Conf on Information and Knowledge Management. New York: ACM, 2015: 273-282

[23]Low Y, Bickson D, Gonzalez J, et al. Distributed GraphLab: A framework for machine learning and data mining in the cloud[J]. Proceedings of the VLDB Endowment, 2012, 5(8): 716-727

[24]Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C] //Proc of the USENIX Conf on Networked Systems Design and Implementation. Berkeley: USENIX Association, 2012: 141-146

[25]Han M, Daudjee K. Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems[J]. Proceedings of the VLDB Endowment, 2015, 8(9): 950-961

[26]Yan Yuliang, Dong Yihong, He Xianmang, et al. FSMBUS: A frequent subgraph mining algorithm in single large-scale graph using Spark[J]. Journal of Computer Research and Development, 2015, 52(8): 1768-1783 (in Chinese)(嚴玉良, 董一鴻, 何賢芒, 等. FSMBUS: 一種基于Spark的大規模頻繁子圖挖掘算法[J]. 計算機研究與發展, 2015, 52(8): 1768-1783)

[27]Cervone D, Amour A, Bornn L, et al. POINTWISE: Predicting points and valuing decisions in real time with NBA optical tracking data[C/OL] //Proc of the 8th MIT Sloan Sports Analytics Conf. Cambridge, MA: MIT, 2014: 1-9 [2016-08-01]. http://www.lukebornn.com/papers/cervone_ssac_2014.pdf

[28]Maheswaran R, Chang Y H, Su J, et al. The three dimensions of rebounding[C/OL] //Proc of the 8th MIT Sloan Sports Analytics Conf. Cambridge, MA: MIT, 2014: 1-7 [2016-08-01]. http://www.sloansportsconference.com/wp-content/uploads/2014/02/2014_SSAC_The-Three-Dimensions-Of-Rebounding.pdf

[29]Maymin P. Acceleration in the NBA: Towards an algorithmic taxonomy of basketball plays[C/OL] //Proc of the 7th MIT Sloan Sports Analytics Conf. Cambridge, MA: MIT, 2013: 1-7 [2016-08-01]. http://www.sloansportsconference.com/wp-content/uploads/2013/Slides/RP/Acceleration%20in%20 the%20NBA.pdf

[30]Goldman M, Rao J M. Live by the three, die by the three? The price of risk in the NBA[C/OL] //Proc of the 7th MIT Sloan Sports Analytics Conf. Cambridge, MA: MIT, 2013: 1-15 [2016-08-01]. http://www.sloansportsconference.com/wp-content/uploads/2013/Live%20by%20the%20Three,%20Die%20by%20the%20Three%20The%20Price%20of%20Risk%20in%20the%20NBA.pdf

[31]Franks A, Miller A, Bornn L, et al. Counterpoints: Advanced defensive metrics for NBA basketball[C/OL] //Proc of the 9th MIT Sloan Sports Analytics Conf. Cambridge, MA: MIT, 2015: 1-8 [2016-08-01]. http://www.lukebornn.com/papers/franks_ssac_2015.pdf

[32]Wiens J, Balakrishnan G, Guttag J. To crash or not to crash: A quantitative look at the relationship between offensive rebounding and transition defense in the NBA[C/OL] //Proc of the 7th MIT Sloan Sports Analytics Conf. Cambridge, MA: MIT, 2013: 1-7 [2016-08-01]. http://www.sloansportsconference.com/wp-content/uploads/2013/To%20Crash%20or%20Not%20To%20Crash%20A%20quantitative%20look%20at%20the%20relationship%20between%20offensive%20rebounding%20and%20transition%20defense%20in%20the%20NBA.pdf

[33]Ren Lei, Du Yi, Ma Shuai, et al. Visual analytics towards big data[J]. Journal of Software, 2014, 25(9): 1909-1936 (in Chinese)(任磊, 杜一, 馬帥, 等. 大數據可視分析綜述[J]. 軟件學報, 2014, 25(9): 1909-1936)

[34]Herman I, Melancon G, Marshall M S. Graph visualization and navigation in information visualization: A survey[J]. IEEE Trans on Visualization and Computer Graphics, 2000, 6(1): 24-43

[35]Zhang Xi, Yuan Xiaoru. Treemap visualization[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(9):1113-1124 (in Chinese)(張昕, 袁曉如. 樹圖可視化[J]. 計算機輔助設計與圖形學學報, 2012, 24(9): 1113-1124)

[36]Balzer M, Deussen O. Voronoi treemaps[C] //Proc of the IEEE Symp on Information Visualization. Piscataway, NJ: IEEE, 2005: 49-56

[37]Gou Liang, Zhang Xiaolong. Treenetviz: Revealing patterns of networks over tree structures[J]. IEEE Trans on Visualization and Computer Graphics, 2011, 17(12): 2449-2458

Zhang Tao, born in 1988. PhD candidate in the School of Information Science and Engineering, Xinjiang University. Her main research interests include big data and cloud computing, etc.

Yu Jiong, born in 1964. Professor and PhD supervisor in computer science at the School of Information Science and Engineering, Xinjiang University. His main research interests include grid computing, parallel computing, etc.

Liao Bin, born in 1986. PhD and associate professor in the School of Statistics and Information, Xinjiang University of Finance and Economics. His main research interests include database theory and technology, big data and green computing, etc.

Guo Binglei, born in 1991. PhD candidate in the School of Information Science and Engineering, Xinjiang University. Her main research interests include cloud and green computing, etc.

Bian Chen, born in 1981. PhD candidate in the School of Information Science and Engineering, Xinjiang University. His main research interests include parallel computing, distributed system, etc.

Wang Yuefei, born in 1991. PhD candidate in the School of Information Science and Engineering, Xinjiang University. His main research interests include big data and green computing, etc.

Liu Yan, born in 1990. Master candidate in the school of Software, Tsinghua University. His main research interests include cloud and green computing, etc.

The Construction and Analysis of Pass Network Graph Based on GraphX

Zhang Tao1, Yu Jiong1, Liao Bin2, Guo Binglei1, Bian Chen1, Wang Yuefei1, and Liu Yan3

1(School of Information Science and Engineering, Xinjiang University, Urumqi 830046)2(SchoolofStatisticsandInformation,XinjiangUniversityofFinanceandEconomics,Urumqi830012)3(SchoolofSoftware,TsinghuaUniversity,Beijing100084)

In the field of social networking, finance, public security, health care, etc, the application of big data technology is matured constantly, but its application in competitive sports is still in exploratory stage. Lacking of recording the pass data in basketball technical statistics leads that we can not research the statistical analysis, data mining and application on the pass data. Firstly, as the aggregation from of passing data is graph, based on data acquisition, clean and format conversion, Vertex and Edge table construction, we create the pass network graph with GraphX, which lays the foundation for other applications. Secondly, the PlayerRank algorithm is proposed to distinguish the importance of players, player position personalized the graph vertex’s color, etc, which improves the visual quality of pass network graph. Finally, we can use the pass network graph created by GraphX to analyze the effect of passing quantity and quality on the outcome of the game, and the pass network graph is also used to analyze the team’s passing data, tactical player selection, on-the-spot tactics supporting, subgraph extraction and gaming experience improvement, etc.

big data application; pass network; GraphX frame; PlayerRank algorithm; player importance

2016-08-08；

2016-10-24

國家自然科學基金項目(61562078,61262088,71261025);新疆維吾爾自治區自然科學基金項目(2016D01B014) This work was supported by the National Natural Science Foundation of China (61562078, 61262088, 71261025) and the Natural Science Foundation of the Xinjiang Uygur Autonomous Region of China (2016D01B014).

廖彬(liaobin665@163.com)

TP393.09