MachineLearning

関係データ解析とInfinite Relational Model

More than 3 years have passed since last update.

ましんらーにんAdvent Calendar 19日目です。「オライリーの『実践 機械学習システム』をざっくりとまとめたい」と予告していたが、あれは嘘だ。(読み終わらなかった)

その代わりに、最近興味のある関係データ解析について数式無しでざっくりとまとめます。まだ理解が浅いので指摘など頂けるととても嬉しいです。

関係データ解析

モノとモノの間のつながりを表現したデータを関係データと呼びます。ソーシャルグラフなんかが良い例ですね。

Twitter上の

  • AさんはBくんをフォローしている
  • BくんはAさんとCさんをフォローしている
  • CさんはAさんをフォローしている

といった"関係"は有向グラフで表現できます。

このような関係データをこねくり回してデータの潜在的な性質を探る取り組みが 関係データ解析 です。

関係データ解析ではその"関係"を行列(テンソル)に落としこんで考えます。

例えば先ほどのTwitterのフォロー関係であれば、フォローしている時に1、していないときに0をとる2値の関係行列で以下のように表現されます。

A B C
A 0 1 0
B 1 0 1
C 1 0 0

Infinite Relational Model

関係データ解析を実現する一手法として Infinite Relational Model (IRM) という関係データ生成モデルに基づくクラスタリングが提案されています。

この手法ではクラスタ数を事前知識として与える必要が無く、データから推定してしまいます。

以下がその動作イメージ。左が実際の関係データで、右がIRMに基づくクラスタリングの結果(青い線がクラスタの区切り)です。黒が関係行列上の1、白が0を表します。

IRMexample.png

関係データが並び替えられてイイ感じにまとめられている様子がなんとなく分かると思います。より直感的かつ面白い説明には次のスライドが良いです。

機械学習でお小遣いを稼ぐ! - 本推薦 Twitter bot の紹介 -

IRMは原論文の共著者にもなっているNTTコミュニケーション科学基礎研究所の方々が熱心に研究されており、理論的には上田さんの資料『無限関係モデルとその周辺』(PDF)あたりが分かりやすいです。あとで他の関連文献もまとめておきますね。

IRMで関係データ解析を行う意義は、クラスタリング後にクラスタ間のつながりの強さまで分かるという点にあるというのが個人的な考えです。

例えば上の図では行と列でそれぞれ3つのクラスタが生成されました。

IRMresult.png

(①, [1])の領域はスカスカだから、クラスタ①とクラスタ[1]はそんなに関係が無いんだなぁとか、

(①, [2])の領域は1が多く集まっているから、クラスタ①とクラスタ[2]は何らかの点で強いつながりがあるんだなぁとか、

そんなことが分かるわけです。

もし①,②,③がユーザクラスタ、[1],[2],[3]が商品クラスタであれば効果的なマーケティングができるかもしれませんね。

応用の可能性

最近の世の中には関係データがあふれています。TwitterやFacebookはもちろんのこと、ここQiitaだって『ユーザが記事をStockしているかどうか』で関係行列が作れますね。

データの見方として 関係データ というものがあることや、関係データに対するクラスタリング手法が存在するということを頭の片隅に入れておくとアイディアが広がりそうです。

なお原論文の著者がC言語による実装を公開しているので、まずは適当にAPI叩いたりしてデータを集めて動かしてみると楽しいと思います。

諸注意

先ほど書いた「この手法ではクラスタ数を事前知識として与える必要が無い」という点は、原論文でやたらと強調されています。しかし伝統的なモデル選択などのアプローチもあるわけで、個人的にはクラスタ数推定がそれほど重要な特徴だとは考えていません。推定する分パラメータも増えますし。

また、IRMに限らず世の中にはおもしろい手法がたくさんありますが、現場で目的が明確でないデータマイニングをするのはダメですよ。(自戒)

参考文献

  • C. Kemp, et al., "Learning Systems of Concepts with an Infinite Relational Model," Proc. of AAAI2006, pp.381-388 (July 2006).

原論文です。

  • 上田, 山田, "ノンパラメトリックベイズモデル," 応用数理, vol.17, no.3, pp.196-214 (Sep. 2007).

日本語でノンパラメトリックベイズモデルの基礎からIRMによるクラスタリングアルゴリズムまでを詳しく解説しています。

  • 上田, "ベイズモデルに基づく関係データ解析技術," 電子情報通信学会誌, vol.97, no.5, pp.348-352 (May 2014).

より平易で直感的な解説です。最近の動向についても触れられています。このページに限らず、この号は全体的に神回。