CCCMKホールディングス TECH LABの Tech Blog

TECH LABのエンジニアが技術情報を発信しています

ブログタイトル

グラフ構造に着目したデータ分析

こんにちは!研究所の萩原です。
この記事はグラフについてのお話です。
グラフ畳み込みの技術について研究所内で情報共有した際に、前提知識としてまとめました。

※ここで言うグラフとは折れ線グラフのようなものではなく、 グラフ理論で取り扱うタイプのグラフです。

グラフとは

データ分析で馴染み深いデータと言えばテーブルデータですが、本日はグラフのデータの活用を考えてみたいと思います。

現実の世界は様々なデータ形式で表現することができますが、データ分析・機械学習の領域でよく使われるデータはテーブル形式です。
その他のデータ形式としては、以下のようなものがあります。

  • 画像
  • 動画
  • 音声
  • 文章
  • グラフ

どのデータに関しても、テーブル(あるいは行列)として記述することも可能ですが、通常のテーブルデータとは違い単純にカラムやレコードのような概念で理解すると不都合も多いです。
例えば、画像のデータでは、近くのピクセルとの関係が重要であるということが知られており、単なるテーブルデータに対するアプローチとは異なる方法が取られることが多いです。

グラフの具体例

グラフに馴染みのない人も多いかと思うので、具体例を交えながらの簡単な説明をします。

グラフの代表例として、路線図の数学的表現を考えてみます。
以下の図は山手線と中央線の簡略的な図です。よくある図のように見えますが、これがグラフです。

f:id:hagiccc:20200409092349p:plain
山手線を表すグラフ

グラフはノードエッジにより構成されます。この例では、ノードが駅、エッジが線路を表しています。
エッジはノードとノードが一定の関係にあることを表しており、ここではX分で到達可能なことを表しています。

グラフはノードとエッジという二つの要素しか存在しませんが、意外にも複雑な関係をとらえることができます。
例えば、ノードについているエッジの数(次数)を見ることで、駅の規模や重要度を推察することができます。次数が大きい駅は色々な路線を使える便利な駅ですからね、直観と一致します。その他では、駅間の距離や経路数などにより離れた駅同士の関係も考えることが可能になります。

テーブルデータへの変換

グラフを用いることでノードが持つ様々な情報を扱えることがわかりましたが、一つ問題があります。
我々が普段扱う学習器や分析手法はテーブルデータであることを仮定しています。例えば、KaggleでもおなじみのLightGBMに直接適用させることはできません。

ここではグラフからテーブル形式のデータへの変換を考えていきます。このプロセスの良し悪しでグラフの持つ情報の活用具合が決まるわけです。

データの特性から抽出する

ここでは、データへの知識を利用してテーブルデータに変換する一例を紹介します。

タスク
とある駅付近のTSUTAYAでイベントをすることになりました。TSUTAYAの会員に向けてDMを送ろうと思います。過去のイベントの履歴と会員の情報から効果的にDMを打ちたいです。

効果的なDMが少し抽象的なので、ここでは単純化します。DMを送った場合の反応率(イベント来る率)を予測して、上位の人にDMを打つことにします。
機械学習のタスクとしては、DMの反応率予測をするだけの単純なものになりました。

さて、タスクが明確になったのでいつも通り?LightGBMで予測しようかと思うのですが、最寄り駅のデータの取り扱いに困ってしまいます。
最寄り駅をカテゴリ変数として扱うことも可能ですが、対象のTSUTAYAまでの距離が大事なことが明らかです。最寄り駅のデータは最寄り駅からTSUTAYAのある駅までの距離のデータとして扱うことにすると、LightGBMでの取り扱いも可能になりつつ最寄り駅の重要な情報も取り入れられそうです。
その他の性別や年代などのデータと組み合わせることで、より良い予測が立てられるようになりました。

このように、扱うデータへの知識を利用してデータを解釈することでグラフの情報を活用することが可能になります。

Embedding

データをベクトルに変換することをEmbedding(埋め込み)と呼びます。 ベクトルはテーブルデータの一行として解釈できます。「データの特性から抽出する」で行ったグラフデータの変換もノードのEmbeddingとみなせます。

例えば、上記のDMを送るタスクでの重要な情報は駅間の距離です。駅間の距離を保存するようなEmbeddingを行うことで、駅のつながりを保持したベクトルに変換することができます。
このようなEmbeddingが可能になると二つのメリットがあることがわかります。

  • 対象のTSUTAYAがどこにあるかを意識する必要がない
    • 他のタスクでもこのデータを利用可能
  • 予測に地域性を取り入れることができる
    • 催し物に積極的な地域、消極的な地域
    • 近くに競合するイベントや店舗がある地域

グラフのEmbeddingを行う技術としては、深層学習を用いたグラフ畳み込みやMDS(多次元尺度構成法)などが用いられます。

おわりに

この記事ではグラフデータの活用について簡単にまとめてみました。
これからもまだ活用できていないデータの活用方法についても、調査・研究を行っていきたいと思います。