2015.07.24

Spark GraphXを使ったグラフ分析: サッカーチームのパフォーマンスをグラフ理論で解いてみる

185

この記事は1年以上前に投稿されました。情報が古い可能性がありますので、ご注意ください。

1. はじめに・Spark GraphX のご紹介

クリエーションラインの渡辺です。前回の記事に続けてSparkの魅力をご紹介したいと思います。Sparkには以下の主要なコンポーネントがあります。

前回はMLlibを用いたレコメンドエンジンの試作を行いましたが、今回はGraphXを使ったグラフ分析について、活用例とともにご紹介いたします。

Spark GraphXはApache Sparkのコンポーネントの一つで、大容量のグラフデータを並列分散環境で処理するためのフレームワークです。また他のSparkコンポーネントと連携することもできるので、ETL処理やSQL処理、機械学習処理と合わせ単一のSpark環境内でひとつの処理フローを実装することもできます。

グラフデータ、グラフ分析はSQLや機械学習と比べるとまだ一般的な技術ではありませんが、ナレッジグラフ、マーケティングリレーション、経路探索、ページランク分析など特定の分野に対しては非常に有効な解決手段として積極的に活用されています。

今回は一般の方にもなじみのあるサッカーチームの分析を通じて、グラフデータおよびSpark GraphXの魅力について語ってみることにします。

2. サッカーとグラフ

先に掲載している、Neo4jの記事でグラフ理論の可能性を感じていただけたかと思います。今回はこのグラフ理論がどう役に立つのかを違う視点から探っていきたいと思います。ここで目に付いたのがただの週末の娯楽でもありながら、世界で100億ドル規模のビジネスでもあるサッカーです。

サッカー試合風景はキックオフと同時に選手たちがピッチ上を自由に動いて不規則に見えるのですが、少し整理するとある規則性が現れてきます。選手をグラフの頂点に見立てると、ボールが選手の間で移動する道がグラフの辺に見えてきます。

サッカーのフォーメーション図を見たことがある人ならば、各ポジションの間にパス交換した数の線を入れれば、頭にグラフが浮かび上がってくるでしょう。*以下の図やページトップの写真を参考にして下さい。

今回はサッカー選手をグラフの頂点とし、パスを各頂点の入次数および出次数と考え、試合中のパスデータをグラフ化してみます。ここでの目的はこの理論が本当に活用できるのかと、そしてもし出来るのであればグラフアルゴリズムに基づいて重要選手などを計算することができるのかを検証することです。

そうであればサッカーをネットワークと考え、どういう戦術が科学的に効果があるのかを証拠づけることもできます。スポーツは科学ではないですが、科学はスポーツを新しい視点から解釈することが可能になるのではないかと思います。

3. GraphXの詳細

今回の検証で用いたApache Sparkは近年急激に開発が進んでおりビッグデータ処理の次世代主役とも言われているフレームワークであり、GraphXはグラフ作りとグラフ並列計算処理を得意とするSparkのAPIです。

従来のグラフ処理システムと違う所はグラフ並列とデータ並列が統合されたプロセスで行われる事です。従来のグラフ処理システムはグラフ並列とデータ並列が異なるプロセスで行われていたために、大量のデータ移動や複製が求められ、課題次第では複数のテーブルやグラフの見方を作らなければありません。

GraphXはユーザが状況に応じてデータの見方を変えることを複製なしで行いますので、非常に高速な処理を可能にします。

4. データ

ここで用いたデータは欧州サッカーサイトFourFourTwo (http://www.fourfourtwo.com/)の公開データと試合動画を元に私が作成した、2015年のチャンピオンズリーグ決勝バルセロナ対ユベントスのパスデータの一部です。

5. 実践

この操作はSparkのシェルからScala言語を使い行います。シェルを開いたら始めにグラフ分析に必要なGraphXとRDDをインポートします。

ソースコード１ - GraphXとRDDのインポート

scala> import org.apache.spark.graphx._
//import org.apache.spark.graphx._

scala> import org.apache.spark.rdd.RDD
//import org.apache.spark.rdd.RDD

インポートしたらまずは、バルセロナの各選手間のパスデータを手作業で選手配列とパス配列として入力していきます。ここで使うのがプロパティグラフです。

プロパティグラフとは各頂点と各辺にユーザが定義した特性（プロパティ）を付け加えることができる有向多重グラフです。

有向とは辺に方向が付いていることで、パスを出した選手を接続元、パスを受けた選手を接続先として入力ができます。

多重とは選手の間に複数のパスが通ったことを意味します。

ソースコード２ - 選手配列とパス配列の作成

scala> val playerArray = Array( (1L, ("Messi", "FW")), (2L, ("Suarez", "FW")), (3L, ("Neymar", "FW")), (4L, ("Iniesta", "MF")), (5L, ("Rakitic", "MF")), (6L, ("Busquets", "MF")), (7L, ("Alves", "DF")), (8L, ("Pique", "DF")), (9L, ("Mascherano", "DF")), (10L, ("Alba", "DF")), (11L, ("Stegen", "GK")) )
// playerArray: Array[(Long, (String, String))] = Array((1,(Messi,FW)), (2,(Suarez,FW)), (3,(Neymar,FW)), (4,(Iniesta,MF)), (5,(Rakitic,MF)), (6,(Busquets,MF)), (7,(Alves,DF)), (8,(Pique,DF)), (9,(Mascherano,DF)), (10,(Alba,DF)), (11,(Stegen,GK))) //出力

scala> val passArray = Array( Edge(1L, 2L, 8), Edge(1L, 3L, 12), Edge(1L, 4L, 7), Edge(1L, 5L, 6), Edge(1L, 6L, 10), Edge(1L, 7L, 10), Edge(1L, 8L, 1), Edge(1L, 10L, 7), Edge(2L, 1L, 6), Edge(2L, 3L, 6), Edge(2L, 4L, 2), Edge(2L, 5L, 3), Edge(2L, 6L, 1), Edge(2L, 7L, 3), Edge(2L, 8L, 1), Edge(3L, 1L, 10), Edge(3L, 2L, 6), Edge(3L, 4L, 6), Edge(3L, 5L, 1), Edge(3L, 6L, 3), Edge(3L, 7L, 3), Edge(3L, 10L, 9), Edge(4L, 1L, 6), Edge(4L, 2L, 2), Edge(4L, 3L, 10), Edge(4L, 5L, 3), Edge(4L, 6L, 7), Edge(4L, 7L, 2), Edge(4L, 8L, 1), Edge(4L, 9L, 4), Edge(4L, 10L, 14), Edge(5L, 1L, 12), Edge(5L, 2L, 2), Edge(5L, 3L, 1), Edge(5L, 4L, 2), Edge(5L, 6L, 5), Edge(5L, 7L, 14), Edge(5L, 8L, 3), Edge(5L, 9L, 5), Edge(5L, 10L, 1), Edge(6L, 1L, 8), Edge(6L, 2L, 2), Edge(6L, 4L, 9), Edge(6L, 5L, 8), Edge(6L, 7L, 16), Edge(6L, 8L, 5), Edge(6L, 9L, 7), Edge(6L, 10L, 5), Edge(6L, 11L, 2), Edge(7L, 1L, 25), Edge(7L, 2L, 2), Edge(7L, 4L, 1), Edge(7L, 5L, 21), Edge(7L, 6L, 7), Edge(7L, 8L, 3), Edge(7L, 9L, 2), Edge(7L, 10L, 4), Edge(8L, 1L, 2), Edge(8L, 2L, 2), Edge(8L, 4L, 1), Edge(8L, 5L, 1), Edge(8L, 6L, 1), Edge(8L, 7L, 12), Edge(8L, 9L, 6), Edge(8L, 10L, 3), Edge(8L, 11L, 6), Edge(9L, 1L, 1), Edge(9L, 2L, 1), Edge(9L, 3L, 1), Edge(9L, 4L, 4), Edge(9L, 5L, 3), Edge(9L, 6L, 7), Edge(9L, 7L, 7), Edge(9L, 8L, 4), Edge(9L, 10L, 10), Edge(9L, 11L, 2), Edge(10L, 2L, 2), Edge(10L, 3L, 21), Edge(10L, 4L, 14), Edge(10L, 6L, 8), Edge(10L, 7L, 1), Edge(10L, 9L, 13), Edge(10L, 11L, 1), Edge(11L, 1L, 1), Edge(11L, 5L, 1), Edge(11L, 6L, 1), Edge(11L, 7L, 2), Edge(11L, 8L, 1), Edge(11L, 9L, 1), Edge(11L, 10L, 4) )
// passArray: Array[org.apache.spark.graphx.Edge[Int]] = Array(Edge(1,2,8), Edge(1,3,12), Edge(1,4,7), Edge(1,5,6), Edge(1,6,10), Edge(1,7,10), Edge(1,8,1), Edge(1,10,7), Edge(2,1,6), Edge(2,3,6), Edge(2,4,2), Edge(2,5,3), Edge(2,6,1), Edge(2,7,3), Edge(2,8,1), Edge(3,1,10), Edge(3,2,6), Edge(3,4,6), Edge(3,5,1), Edge(3,6,3), Edge(3,7,3), Edge(3,10,9), Edge(4,1,6), Edge(4,2,2), Edge(4,3,10), Edge(4,5,3), Edge(4,6,7), Edge(4,7,2), Edge(4,8,1), Edge(4,9,4), Edge(4,10,14), Edge(5,1,12), Edge(5,2,2), Edge(5,3,1), Edge(5,4,2), Edge(5,6,5), Edge(5,7,14), Edge(5,8,3), Edge(5,9,5), Edge(5,10,1), Edge(6,1,8), Edge(6,2,2), Edge(6,4,9), Edge(6,5,8), Edge(6,7,16), Edge(6,8,5), Edge(6,9,7), Edge(6,10,5), Edge(6,11,2), Edge(7,1,25), Edge(7,2,2), Edge(7,4,1), Edge(7,5,21), Edge(7,6,7), Edge(7,8,3), Edge(...// 出力

ソースコード２：playerArrayが選手配列変数でpassArrayがパス配列変数の定義です。今回の選手配列変数は選手のID,　名前,　ポジションを入力しましたが、必要であればそれ以外の情報も付け加えて入力できます。パス配列変数は選手IDを使い、引数１が接続元選手、引数２が接続先選手、引数３がパスの数として入力しました。

ここで頂点と辺の配列変数をRDDに置き換えます。RDDはSparkの基本抽象概念で、効率的な並列処理を可能にするデータセットです。RDDに置き換えますと、Sparkが提供しているオペレータを自由に使うことができます。

ソースコード３ - 選手RDDとパスRDDの作成

scala> val playerRDD: RDD[(Long, (String, String))] = sc.parallelize(playerArray)
// playerRDD: org.apache.spark.rdd.RDD[(Long, (String, String))] = ParallelCollectionRDD[0] at parallelize at :27 // 出力

scala> val passRDD: RDD[Edge[Int]] = sc.parallelize(passArray)
// passRDD: org.apache.spark.rdd.RDD[org.apache.spark.graphx.Edge[Int]] = ParallelCollectionRDD[1] at parallelize at :27 // 出力

ソースコード３：sc.parallelizeオペレータを使って選手RDDとパスRDDを作成しました。これでグラフを作ることができます。

選手RDDとパスRDDを使ってグラフを作る作業はGraphXで以下のグラフオペレータを呼ぶだけの単純な操作です。

ソースコード４：選手RDDとパスRDDを統合したグラフの作成

scala> val graph: Graph[(String, String), Int] = Graph(playerRDD, passRDD)
// graph: org.apache.spark.graphx.Graph[(String, String),Int] = org.apache.spark.graphx.impl.GraphImpl@4488af25 // 出力

作成後はグラフが正確に出来ているかを確認します。この結果を調べるためにトリプレットという近接集合のオペレータを呼びます。トリプレットは二つの頂点とその間にある辺を集合したエレメントです。

ソースコード５ - 作成されたグラフの確認

scala> for (triplet <- graph.triplets.collect) { println(s"${triplet.srcAttr._1} passed to ${triplet.dstAttr._1}") }
// Messi passed to Suarez
Messi passed to Neymar
Messi passed to Iniesta
Messi passed to Rakitic
Messi passed to Busquets
Messi passed to Alves
Messi passed to Pique
Messi passed to Alba
Suarez passed to Messi
Suarez passed to Neymar
Suarez passed to Iniesta
Suarez passed to Rakitic
Suarez passed to Busquets
Suarez passed to Alves
Suarez passed to Pique
Neymar passed to Messi
Neymar passed to Suarez
Neymar passed to Iniesta
Neymar passed to Rakitic
Neymar passed to Busquets
Neymar passed to Alves
Neymar passed to Alba
Iniesta passed to Messi
Iniesta passed to Suarez
Iniesta passed to Neymar... // 出力省略

ソースコード５：　これで入力したデータがしっかりパスを表していることが確認できます。トリプレットの接続元（srcAttr._1)がトリプレットの接続先（destAttr._1)にパスを送っています。

誰にパスを出したかは基本です。ここで、除外操作を行い特定の選手に10回以上パスを出した選手を調べます。

ソースコード６ - 同じ選手（接続先）に10回以上パスを出した選手を調べる

scala> for (triplet <- graph.triplets.filter(t => t.attr >= 10).collect) { println(s"${triplet.srcAttr._1} passed to ${triplet.dstAttr._1} 10 times or more") }
// Messi passed to Neymar 10 times or more
Messi passed to Busquets 10 times or more
Messi passed to Alves 10 times or more
Neymar passed to Messi 10 times or more
Iniesta passed to Neymar 10 times or more
Iniesta passed to Alba 10 times or more
Rakitic passed to Messi 10 times or more
Rakitic passed to Alves 10 times or more
Busquets passed to Alves 10 times or more
Alves passed to Messi 10 times or more
Alves passed to Rakitic 10 times or more
Pique passed to Alves 10 times or more
Mascherano passed to Alba 10 times or more
Alba passed to Neymar 10 times or more
Alba passed to Iniesta 10 times or more
Alba passed to Mascherano 10 times or more // 出力

ソースコード６：ソースコード５のトリプレット操作にフィルターオペレータを付け加えて、定義された選手を除外しました。簡単な方法ですが、これでどのパスコースが頻繁なのかが見えてきます。

次に選手クラスを作成し、各選手に入る、または各選手から出るパスを入次数、出次数という特性を付け加えます。選手クラスを作成するのは、これを使って新たな特性の付いたグラフを作成するためです。

これで誰にパスを出したかだけではなく、誰からパスを受けたのかを調べることができます。

ソースコード７ - 入次数と出次数を足した選手クラスの作成

scala> case class Player(name: String, position: String, inDeg: Int, outDeg: Int)
// defined class Player

ソースコード７：新しい選手クラスは名前、ポジション、入次数(inDeg)と出次数(outDeg)を含みます。

ソースコード８ - 元のグラフに選手クラスの特徴を加えた新しい選手グラフの作成

scala> val iniPlayerGraph: Graph[Player, Int] = graph.mapVertices{ case (id, (name, position)) => Player(name, position, 0, 0) }
// iniPlayerGraph: org.apache.spark.graphx.Graph[Player,Int] = org.apache.spark.graphx.impl.GraphImpl@727a9f31 // 出力

scala> val PlayerGraph = iniPlayerGraph.outerJoinVertices(iniPlayerGraph.inDegrees) { case (id, u, inDegOpt) => Player(u.name, u.position, inDegOpt.getOrElse(0), u.outDeg) }.outerJoinVertices(iniPlayerGraph.outDegrees) { case (id, u, outDegOpt) => Player(u.name, u.position, u.inDeg, outDegOpt.getOrElse(0)) }
// PlayerGraph: org.apache.spark.graphx.Graph[Player,Int] = org.apache.spark.graphx.impl.GraphImpl@37a10c6 // 出力

ソースコード８：ここで使ったオペレータはmapVerticesとouterJoinVerticesです。これは新しいグラフの初期設定と元のグラフの情報（名前、ポジション）と新しいグラフの情報（パスを出した、受けた回数）を統合させる操作です。

新しいグラフが出来たので、各選手が何人の選手と繋がっていたのか（何人の選手からパスを受けたのか)を調べます。

ソースコード９ - 何人の選手からパスが来たのかを調べる

scala> for ((id, property) <- PlayerGraph.vertices.collect) { println(s"${property.name} recieved a pass from ${property.inDeg} people") }
// Iniesta recieved a pass from 9 people
Busquets recieved a pass from 10 people
Pique recieved a pass from 8 people
Alba recieved a pass from 9 people
Suarez recieved a pass from 9 people
Stegen recieved a pass from 4 people
Messi recieved a pass from 9 people
Neymar recieved a pass from 6 people
Alves recieved a pass from 10 people
Mascherano recieved a pass from 7 people
Rakitic recieved a pass from 9 people // 出力

ソースコード９：新しく定義されたproperty.inDegが各選手がパスを受けた回数です。ブスケッツ選手とアルべス選手が一番多く違う選手からパスを貰っていることが分かります。バルセロナはパス重視のチームなので、チーム全体でパスが回っていることも証明されています。異なるチームのデータを入力するともう少しばらつきが付くかもしれません。

最後にページランクを使ってパス回しで一番重要な選手を調べてみます。ページランクとはグーグルがサイトをラインキングするために作ったアルゴリズムです。

軽く説明するとウェブサイトの場合（サイトをグラフの頂点として、リンクを辺と考える）、多くのサイトからリンクされているものを上位とし整理されます。ここでの要件に置き換えると、たくさんの選手からパスを貰っているとランキングが上がるということになります。

ソースコード１０：ページランクを行い、パスで最重要選手を探す。

scala> val pregraph = PlayerGraph.staticPageRank(11).cache
// pregraph: org.apache.spark.graphx.Graph[Double,Double] = org.apache.spark.graphx.impl.GraphImpl@58f0aa66 // 出力

scala> val passAndPrGraph = PlayerGraph.outerJoinVertices(pregraph.vertices) { (v, pass, rank) => (rank.getOrElse(0.0), pass) }
// passAndPrGraph: org.apache.spark.graphx.Graph[(Double, Player),Int] = org.apache.spark.graphx.impl.GraphImpl@661c5675 //出力

scala> passAndPrGraph.vertices.top(11) { Ordering.by((entry: (VertexId, (Double, Player))) => entry._2._1) }.foreach( t => println(t._2._2 + ": " + t._2._1))
// Player(Busquets,MF,10,9): 1.0160295032184092
Player(Alves,DF,10,8): 1.0054766919442597
Player(Iniesta,MF,9,9): 0.9630340724142503
Player(Suarez,FW,9,7): 0.9404722126044849
Player(Rakitic,MF,9,9): 0.9195593375445895
Player(Messi,FW,9,8): 0.9100040842491883
Player(Alba,DF,9,7): 0.8930633194802826
Player(Pique,DF,8,9): 0.8443887489867539
Player(Mascherano,DF,7,10): 0.7597213226429775
Player(Neymar,FW,6,7): 0.6951015618391465
Player(Stegen,GK,4,7): 0.48848981657776236 // 出力

ソースコード１０：最初のコマンドがページランクを行い、ランク値を計算します。次にOuterJoinVerticesでランク値を選手グラフに統合します。最後に統合された情報を元に上から順に選手を並び替えます。

結果をみると、MFでプレーしている選手がやはりパスの上位重要選手になっています。しかし、この結果はすごく単純すぎます。分析してみるとパスを多くの選手から貰っている選手が重要視されていて、パスを多くの選手に出したことはそれほど重要ではないことになっています。

サッカーではパスを受けに行くのは大事ですが、ボールを再び送り返すのも同じくらい重要です。生データはアルべス選手が一番多くのパスを出していましたが、（一人の選手に４０％近くだしていたので）それはさほど重要でないと判断されました。

まとめ

サッカーチームをGraphXによってグラフ分析を行い、パスがどのように流れているかが図形化できます。
- GraphXはすごく使いやすいです。オペレータも豊富で、簡単にグラフ分析の基本である除外作業や近接集合などが行えます。

この試合ではブスケッツ選手がページランク的に一番重要と判断されました。
- ブスケッツ選手はコアなサッカーファンなら押しの渋い選手ですが、ページランクの分析結果においても、彼が優秀であることが理論的に証明されました。
- ブスケッツ選手がこの分析で高い評価を得ている理由は端的に言えばチーム全体にパスを貰いに行く回数が多いからです。しかしこれはスポーツ分析として単純すぎるかもしれません。
- 本格的なスポーツ分析を行うためには、これに加えて各選手からパスを受けた回数、出した回数、さらにどこのポジションで誰となどの背景情報を踏まえて分析を行っていく必要があるでしょう。

さいごに

このデータは一つの試合からなので、シーズン全体や、相手ごとの平均的なデータを要するともっと信頼できる分析ができると思います。
- グラフ理論はパス回しのデータを扱うものなので、一試合のデータだとかなり偏った傾向しか分析できません。シーズンを通して様々な試合を横断的に分析することで、サッカーファンが今までに感じていながら証明できなかった、より新たな発見があるかもしれません。
- 全シーズン、試合相手ごとのデータとなるとかなり大量なファイルになり、Sparkの特性がより有効に機能すると考えられます。

今回の例では、試合のデータを目で見て手作業で作成しています。より効率的に多くの入力データを作成するためにはウェブ上のデータをスクレイプして、GraphXに適している型に変換する能力が必要になります。もしくは、データを直接入手出来るのであれば、GraphXに合わせた形でデータを蓄積すると簡単に分析ができると思います。

今回はサッカーチームのパフォーマンスの解析を例としましたが、例えば社内でのメッセージやメールのやり取りを元にしたチームおよびメンバーの役割の評価や各種現場でのコミュニケーションの分析に応用することが可能です。Sparkとそのコンポーネントを活用することによりこのような解析を今後もっと手軽に行えるようになるでしょう。

参考資料

１．グラフ理論をサッカーに使う応用案は名古屋大学など、様々な団体が発表しています。 http://www.nagoya-u.ac.jp/about-nu/public-relations/researchinfo/upload_images/20111229_htc.pdf
２．*の画像元：　PageRank Algorithm Reveals Soccer Teams' Strategies - MIT Technology Review　(http://www.technologyreview.com/view/428399/pagerank-algorithm-reveals-soccer-teams-strategies/)

1. はじめに・Spark GraphX の ご紹介