基于GraphX的傳球網(wǎng)絡(luò)構(gòu)建及分析研究

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

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

?

基于GraphX的傳球網(wǎng)絡(luò)構(gòu)建及分析研究

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

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

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

大數(shù)據(jù)應(yīng)用;傳球網(wǎng)絡(luò);GraphX框架;PlayerRank算法;球員重要性

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

Fig. 1 MapReduce computing model ecosystem.圖1 MapReduce計算模型生態(tài)系統(tǒng)

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

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

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

問題2. 傳切戰(zhàn)術(shù)、擋拆戰(zhàn)術(shù)及三角進(jìn)攻戰(zhàn)術(shù)中,由誰來傳球最好?

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

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

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

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

1 相關(guān)研究及背景

1.1 圖的相關(guān)研究

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

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

1.2 相關(guān)背景知識介紹

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

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

1.2.2 相關(guān)籃球術(shù)語介紹

為了方便讀者對本文的閱讀及理解,表1對本文中涉及到籃球方面的一些專業(yè)術(shù)語或?qū)Ｓ忻~(如NBA、NBA球隊、NBA賽制、技術(shù)統(tǒng)計等)進(jìn)行解釋.

Table 1 Basic Professional Terminology

Continued (Table 1)

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

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

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

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

2 傳球網(wǎng)絡(luò)圖的構(gòu)建

2.1 圖的構(gòu)建總體流程

傳球網(wǎng)絡(luò)圖的構(gòu)建及應(yīng)用框架流程圖如圖2所示,主要分為6個步驟:

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

2) 數(shù)據(jù)清洗及格式轉(zhuǎn)化.通過程序抓取而來的原始數(shù)據(jù)一般為XML或JSON格式,需通過數(shù)據(jù)清洗及格式轉(zhuǎn)化,以滿足網(wǎng)絡(luò)圖的構(gòu)建對數(shù)據(jù)格式的要求.

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

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

5) 傳球網(wǎng)絡(luò)的構(gòu)建及可視化.在步驟3的基礎(chǔ)上,通過GraphX構(gòu)建出傳球網(wǎng)絡(luò)圖,通過提取并計算圖相關(guān)的數(shù)據(jù)(如傳球次數(shù)、PR值等)并結(jié)合大數(shù)據(jù)可視化技術(shù),可實現(xiàn)傳球網(wǎng)絡(luò)圖的可視化.

Fig. 2 The construction and application framework of passing network diagram.圖2 傳球網(wǎng)絡(luò)圖構(gòu)建及應(yīng)用框架流程圖

6) 基于傳球網(wǎng)絡(luò)的應(yīng)用:傳球網(wǎng)絡(luò)可輔助教練的決策、戰(zhàn)術(shù)支撐、輔助球員的訓(xùn)練、對手分析、球員交易分析等.具體的應(yīng)用場景分析請參見第4節(jié).

下文將圍繞上述6個步驟進(jìn)行詳細(xì)介紹,其中2.2節(jié)圍繞步驟1、步驟2的內(nèi)容進(jìn)行了詳細(xì)的闡述; 2.3節(jié)討論定義并構(gòu)建Vertex表及Edge表的問題；2.4節(jié)介紹傳球網(wǎng)絡(luò)的構(gòu)建方法. 步驟4在步驟2、步驟3的基礎(chǔ)上通過調(diào)用SparkSQL及對應(yīng)數(shù)據(jù)庫的API便可完成. 而第3節(jié)闡述傳球網(wǎng)絡(luò)的可視化問題;第4節(jié)圍繞傳球網(wǎng)絡(luò)的應(yīng)用場景進(jìn)行分析.

2.2 傳球數(shù)據(jù)的獲取、清洗及格式轉(zhuǎn)化

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

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

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

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

Fig. 3 Data acquisition process.圖3 數(shù)據(jù)獲取流程

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

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

核心代碼1. CURL Python調(diào)用代碼.

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) 循環(huán)playerids數(shù)組中所有的playerid,重復(fù)調(diào)用步驟3中的Python代碼,直到執(zhí)行完playerids數(shù)組中所有的元素.最終生成如圖3所示的JSON文件集合,每個JSON文件對應(yīng)一個球員的傳球數(shù)據(jù).

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

Table 2 Interpretation of Parameters

Continued (Table 2)

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

核心代碼2. JSON數(shù)據(jù)轉(zhuǎn)化代碼.

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 定義并構(gòu)建Vertex表及Edge表

由于Vertices,Edges,Triplets是GraphX中最重要的3個概念.其中Vertices類所對應(yīng)的RDD為VertexRDD,屬性有ID及頂點屬性;Edges類所對應(yīng)的RDD為EdgeRDD,屬性有源頂點的ID、目標(biāo)頂點的ID及邊屬性;Triplets所對應(yīng)的RDD類型為EdgeTriplets,而Triplets可通過所對應(yīng)的Vertices與Edges經(jīng)過JOIN操作得到,所以Triplets屬性有:源頂點ID、源頂點屬性、邊屬性、目標(biāo)頂點ID、目標(biāo)頂點屬性.由于GraphX統(tǒng)一了Table View與Graph View,即實現(xiàn)了Unified Representation,通過構(gòu)造Vertex及Edge表,并將Vertex Edge表數(shù)據(jù)加載到Spark內(nèi)存中便可構(gòu)造出傳球網(wǎng)絡(luò)圖.

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

在實際的傳球網(wǎng)絡(luò)應(yīng)用場景中,設(shè)關(guān)系表Vertex(PLAYERID,PLAYERNAME)及Edge(PASSERID,PASSTOID,FREQUENCY,PASSNUM,AST,FGM,FGA,FGP,FGM2,FGA2,FGP2,FGM3,FGA3,FGP3)分布存儲節(jié)點集合V及關(guān)系集合E的數(shù)據(jù).Vertex及Edge表數(shù)據(jù)字典如表3及表4所示.

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

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

Table 3 Data Dictionary of Table Vertex

Table 4 Table Edge’s Data Dictionary

(1)

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

Frequency〈passerid,passtoid〉=

(2)

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

(3)

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

(4)

(5)

在實際的應(yīng)用場景中,變量Frequency,fgp,fgp2,fgp3是教練制定即時戰(zhàn)術(shù)最重要的數(shù)據(jù)支撐.

2.4 傳球網(wǎng)絡(luò)的構(gòu)建

本節(jié)以2015—2016賽季的總冠軍騎士隊為例,構(gòu)建其82場常規(guī)賽期間所有場次的傳球網(wǎng)絡(luò)圖.首先,通過2.2節(jié)中的數(shù)據(jù)獲取及清洗獲得傳球網(wǎng)絡(luò)圖的頂點數(shù)據(jù)如表5所示:

Table 5 The Cavaliers Passing Network Diagram’s Vertex Data

Continued (Table 5)

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

核心代碼3. 數(shù)據(jù)清洗及格式轉(zhuǎn)化.

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()

}

}

數(shù)據(jù)格式轉(zhuǎn)化程序?qū)⒃紨?shù)據(jù)從目錄Cavaliers_data讀入數(shù)據(jù),數(shù)據(jù)處理完畢后將數(shù)據(jù)寫入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單個球員的數(shù)據(jù),當(dāng)將騎士隊所有隊員的傳球數(shù)據(jù)累加便形成整個球隊82場常規(guī)賽所有的傳球數(shù)據(jù).構(gòu)建騎士隊常規(guī)賽騎士對傳球網(wǎng)絡(luò)的Spark GraphX如核心代碼4所示:

核心代碼4. 騎士隊常規(guī)賽傳球網(wǎng)絡(luò)構(gòu)建.

① 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)

在如上傳球網(wǎng)絡(luò)構(gòu)建代碼中,行⑥⑦代碼分別將頂點與邊的數(shù)據(jù)從cvs文件中讀取到內(nèi)存,行⑧從player常量構(gòu)建圖頂點,行⑨在行⑥常量pass的基礎(chǔ)上構(gòu)建傳球網(wǎng)絡(luò)的邊,邊的屬性可根據(jù)應(yīng)用場景進(jìn)行自定義.行⑩在常量vertices及edges的基礎(chǔ)上,通過調(diào)用Graph類的構(gòu)造函數(shù),構(gòu)造出傳球網(wǎng)絡(luò)graph,為傳球網(wǎng)絡(luò)的應(yīng)用打下基礎(chǔ).

3 傳球網(wǎng)絡(luò)的可視化研究

3.1 傳球網(wǎng)絡(luò)與社交網(wǎng)絡(luò)可視化的不同

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

傳球網(wǎng)絡(luò)的可視化與社交網(wǎng)絡(luò)圖的可視化非常類似,其中社交網(wǎng)絡(luò)圖可通過NodeXL等工具進(jìn)行可視化.但是,本文在嘗試?yán)肗odeXL繪制傳球網(wǎng)絡(luò)圖時,發(fā)現(xiàn)NodeXL等社交網(wǎng)絡(luò)的可視化工具并不適合傳球網(wǎng)絡(luò)的可視化.因為傳球網(wǎng)絡(luò)相比社交網(wǎng)絡(luò)單純的好友關(guān)系,需要表達(dá)出4項更多的個性化信息:

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

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

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

4) 傳球網(wǎng)絡(luò)圖的用戶交互能力.傳統(tǒng)數(shù)據(jù)可視化技術(shù)大多通過靜態(tài)的圖片進(jìn)行數(shù)據(jù)展示,不具備動態(tài)的交互能力.本文生成的傳球網(wǎng)絡(luò)圖由于底層采用JavaScript腳本,通過瀏覽器展示傳球網(wǎng)絡(luò)圖的同時提供動態(tài)的用戶事件響應(yīng)機(jī)制,用戶可利用鼠標(biāo)操作關(guān)注某一特定球員的傳球情況.

3.2 傳球網(wǎng)絡(luò)可視化的輸入數(shù)據(jù)

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

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

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

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

Table 7 The Cavaliers Player’s Position Classification Table

3.3 球員在傳球網(wǎng)絡(luò)中的重要度計算

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

(6)

由于GraphX中提供了PageRank的實現(xiàn),在2.4節(jié)中傳球網(wǎng)絡(luò)構(gòu)造的基礎(chǔ)上,通過調(diào)用PageRank API能夠快速地對球員重要度進(jìn)行計算.但是,PageRank算法的輸入?yún)?shù)并不支持計算邊的屬性(如傳球次數(shù)、頻率等),所以需要將2.4節(jié)中的傳球網(wǎng)絡(luò)進(jìn)行變換,才能進(jìn)行球員重要度的計算.如圖4為數(shù)據(jù)轉(zhuǎn)化示例.

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

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

核心代碼5. PageRank算法數(shù)據(jù)變換程序.

① 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

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

3.4 ForceNetwork可視化傳球網(wǎng)絡(luò)

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

核心代碼7. R語言繪制傳球網(wǎng)絡(luò).

① 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 騎士隊常規(guī)賽傳球網(wǎng)絡(luò)圖

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

在2015—2016賽季創(chuàng)造了NBA常規(guī)賽歷史最佳戰(zhàn)績(73勝9負(fù))、NBA開局最長連勝紀(jì)錄(24連勝)以及NBA主場最長連勝紀(jì)錄(54連勝)的金州勇士隊,其常規(guī)賽傳球網(wǎng)絡(luò)圖如圖6所示：

Fig. 6 Warriors regular season passing network diagram.圖6 勇士隊常規(guī)賽傳球網(wǎng)絡(luò)圖

4 傳球網(wǎng)絡(luò)應(yīng)用場景及分析

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

4.1 NBA傳球數(shù)據(jù)對比賽結(jié)果的影響分析

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

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

表10將2015—2016賽季30支球隊的場均傳球數(shù)據(jù)進(jìn)行了匯總,包括場均傳球數(shù)、場均助攻數(shù)、傳球助攻比(產(chǎn)生1次助攻需要的傳球數(shù)量)、傳球助攻率(1次傳球轉(zhuǎn)化為助攻的概率)以及球隊在2015—2016賽季的勝率(賽季總場次除以勝利場次).通過表10數(shù)據(jù)可統(tǒng)計出聯(lián)盟30支球隊的場均助攻數(shù)為22.277,傳球助攻率平均為7.347%.其中場均傳球數(shù)最多的為Utah Jazz隊,達(dá)到了場均354.8次;而最少的為Oklahoma City Thunder隊,場均傳球數(shù)量僅為264次,比場均最多的Utah Jazz少了90.8次之多.場均助攻數(shù)方面Golden State Warriors達(dá)到聯(lián)盟最高的28.9次,比墊底的Los Angeles Lakers的18次多出整整10.9次.Golden State Warriors以高達(dá)8.945%的傳球助攻率領(lǐng)跑全聯(lián)盟,而Utah Jazz的傳球助攻率僅為5.355%.本文將球隊的勝率與傳球數(shù)據(jù)(包括場均傳球數(shù)、場均助攻數(shù)、傳球助攻率)進(jìn)行對比分析,其對比結(jié)果如圖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 球隊勝率與傳球數(shù)據(jù)之間的關(guān)系

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賽季傳球數(shù)據(jù)對比賽結(jié)果(贏或輸)的影響分析

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

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

4.2 球隊傳球網(wǎng)絡(luò)應(yīng)用

4.2.1 基于傳球網(wǎng)絡(luò)的整體傳球數(shù)據(jù)分析

以2015—2016賽季總冠軍球隊騎士隊常規(guī)賽數(shù)據(jù)為例,在構(gòu)建表Vertex及Edge并構(gòu)建傳球網(wǎng)絡(luò)(如圖5所示)的基礎(chǔ)上,可通過Vertex及Edge的JOIN操作導(dǎo)出傳球表及接球表的數(shù)據(jù)(過濾掉傳球或接球數(shù)小于100的球員).為了實現(xiàn)對球隊整體傳球數(shù)據(jù)的分析,為將來的戰(zhàn)術(shù)制定打下基礎(chǔ),其中表11為球隊傳球數(shù)據(jù)表,表12為接球數(shù)據(jù)表.

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

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

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賽季常規(guī)賽騎士隊球員傳球及接球數(shù)據(jù)對比

4.2.2 基于傳球網(wǎng)絡(luò)的戰(zhàn)術(shù)人員選擇

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

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

4.2.3 基于傳球網(wǎng)絡(luò)的臨場戰(zhàn)術(shù)制定

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

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

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

Fig. 10 The 3 points tactical lore based on passing data analysis.圖10 基于傳球數(shù)據(jù)的3分絕殺戰(zhàn)術(shù)

4.3 傳球網(wǎng)絡(luò)子圖應(yīng)用

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

核心代碼8. 網(wǎng)絡(luò)子圖抽取代碼.

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

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

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

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

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

Table 13 Per Game Passing Data Summary for Stephen Curry

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

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

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

4.4 傳球網(wǎng)絡(luò)在游戲中的應(yīng)用

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

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

(7)

其中FP→Pn表示傳球網(wǎng)絡(luò)中連接球員P與Pn之間邊的屬性FREQUENCY%的值.

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

Table 15 Stephen Curry’s Pass Frequency

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

Table 16 Stephen Curry’s Pass Frequency in the Game

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

5 結(jié)論及下一步工作

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

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

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

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

2) 本地化的基于傳球網(wǎng)絡(luò)的應(yīng)用開發(fā).中國的CBA甚至是中國男籃,對常規(guī)技術(shù)統(tǒng)計數(shù)據(jù)的價值挖掘及應(yīng)用都停留在初級階段.所以,研究基于傳球網(wǎng)絡(luò)的應(yīng)用軟件,從而簡化傳球數(shù)據(jù)的獲取到數(shù)據(jù)價值轉(zhuǎn)化的過程,是推動籃球競技數(shù)據(jù)化、智能化的關(guān)鍵.

3) 傳球數(shù)據(jù)與其他技術(shù)統(tǒng)計的關(guān)聯(lián)分析.需在已有的傳球數(shù)據(jù)中擴(kuò)展傳球類型、速度、失誤概率、傳球距離等信息,并挖掘傳球數(shù)據(jù)與球員位置、得分、失誤、助攻等其他技術(shù)統(tǒng)計數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系.

4) 將傳球網(wǎng)絡(luò)的研究與應(yīng)用擴(kuò)展到其他球類運動.本文的傳球數(shù)據(jù)來自于籃球賽場,可將傳球網(wǎng)絡(luò)的研究與應(yīng)用擴(kuò)展到其他球類運動,如足球、排球、橄欖球、水球、手球等.

[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)(孟小峰, 慈祥. 大數(shù)據(jù)管理: 概念、技術(shù)與挑戰(zhàn)[J]. 計算機(jī)研究與發(fā)展, 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)(廖彬, 于炯, 張?zhí)? 等. 基于分布式文件系統(tǒng)HDFS的節(jié)能算法[J]. 計算機(jī)學(xué)報, 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)(廖彬, 張?zhí)? 于炯, 等. MapReduce能耗建模及優(yōu)化分析[J]. 計算機(jī)研究與發(fā)展, 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)(嚴(yán)玉良, 董一鴻, 何賢芒, 等. FSMBUS: 一種基于Spark的大規(guī)模頻繁子圖挖掘算法[J]. 計算機(jī)研究與發(fā)展, 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)(任磊, 杜一, 馬帥, 等. 大數(shù)據(jù)可視分析綜述[J]. 軟件學(xué)報, 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]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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

國家自然科學(xué)基金項目(61562078,61262088,71261025);新疆維吾爾自治區(qū)自然科學(xué)基金項目(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