もろず blog

もろちゃんがITに関しての様々なトピックを解説します

グラフ解析でうちの社長の脳内晒す!

Nextremer アドベントカレンダーのため、半年ぶりくらいに記事を書きます

qiita.com


さて、今回は何を書こうかと考えた時に、
うちの社長は普段から「僕はオープンデータだから好きに使って」と言ってくれているので、
お言葉に甘えて、日頃の slack 上での発言を解析して社長の脳内を思い切って晒してやろうと思います


この記事では
1. ひとまず脳内晒す
2. グラフを作る
3. 解析する
4. 可視化する
5. まとめ
について解説します

今年に入ってから全く記事を書けてなかったです・・・
いろいろと新しいことも勉強して書きたいネタはいっぱいあるので、時間をつくってゆるゆると書いていきたいと思います


1. ひとまず脳内晒す

では、とりあえず社長の脳内を見てみましょう
slack のデータを解析した結果、こんな感じの発言をしています

f:id:chanmoro999:20161209185850p:plain

全てのノードを表示すると多すぎてよくわからなくなるので、pagerank のスコアが高い方から300ノードくらいまでに絞って表示しました
同じ色になっている言葉は、クラスタリングをした結果同じクラスタに属している言葉です

ざっと見てみると、いくつか強そうなクラスタがあります

だいたいが仕事中の会話なので、当然仕事や会社に関係したものが大きい割合を占めてますが、
普段の発言の傾向をとてもよく捉えているような気がします
※もちろん、特定の企業名やプロジェクト名が出てこないように、センシティブな情報はがっつりフィルタしています 笑

うちの社長を知らない人もとりあえず「なんだか高知が大好きそうな人なんだなー」と思ってくれればいいと思います


解析結果が実際と合ってるどうかは、うちの会社に遊びに来て直接社長と話してみましょう!

www.wantedly.com



さて、結果の吟味は置いておいて、どうやったらこういう脳内メーカー的なものが作れるのか次から見ていきましょう


記事の先頭に戻る


2. グラフを作る

今回は slack のデータを使いましたが、元となるデータの文章を1文づつ形態素解析し、単語1つ1つをグラフのノードとします

この際、ストップワードやあまり意味をなさない単語は除外して、動詞は基本形にしてノードにセットします
だいたい名詞、動詞、形容詞あたりを使っておけばそれっぽい感じにはなります

それぞれの単語の出現回数も数えておきます

f:id:chanmoro999:20161209203049p:plain

それぞれの単語が一定の範囲にセットで登場していれば、その単語間にエッジを設定します
"一定の範囲"というのは、同じ文に出現している単語の共起を利用する方法と、
一定の単語数(例えば5単語とか)を取り出してそのウィンドウ内の共起関係を利用する方法(滑走窓)があります

滑走窓の場合は、文をまたいだ共起関係を考慮することができるので1つ1つの文書が長い場合には有効かと思います
今回は同じ文内の共起を使っています


このようにして計算した値をもとに、 GML(Graph Modeling Language) の形式でグラフをファイルに保存します
書式はとても簡単でこんな感じでノードとエッジを定義するだけです

graph [
  node [
    part "名詞-固有名詞-一般"
    id 4768
    count 1
    label "バーテンダー"
  ]
  node [
    part "名詞-一般"
    id 155
    count 88
    label "社長"
  ]

〜 省略 〜

  edge [
    count 2
    source 163
    target 4627
  ]
  edge [
    count 2
    source 4839
  ]
]

エッジリストの形式が必要な時もありますが、プロパティを自由に定義できないのが使いにくいので、
とりあえず GML で書くのがいいかと思います


記事の先頭に戻る


3. 解析する

さて、そのようにして作成したグラフに対して解析した数値をセットしていきます。

まず、エッジがある2単語間の相互情報量を計算し、その値をエッジの重みとしてセットします
相互情報量をものすごく簡単に説明すると、ある2つのデータがどれくらい一緒に出現しやすいか、を表す尺度です
ある2単語が別の単語よりも共起する割合が多い場合にこの数値が大きくなります

相互情報量についてはこの記事がわかりやすく参考にさせて頂きました

d.hatena.ne.jp

単語Aが単独で出現する時の情報量は、単語Bが出現したことがわかっている時の単語Aの情報量よりPMIだけ大きい、ということを表してるらしいです
なので、単語Aと単語Bが必ず共起するのであれば、単語A単語Bの情報量は少ない(というか0)なので、PMIの値が大きくなるということですね


相互情報量の計算は python で書くとこんな感じです

# PMI(相互情報量)を計算する
def calicuratePMI(relationSet, allWordSet):
    total_count = len(allWordSet)

    for data in relationSet.values():
        countX = data['start']['count']
        countY = data['end']['count']
        relation = data['relation']
        countXY = relation['count']

        pmi = math.log2((countXY / total_count) / ((countX / total_count) * (countY / total_count)))

        relation['pmi'] = pmi

そのようにして相互情報量による重みを付与したグラフに対して、更にページランクの計算を行います
よく利用されている単語ほどページランクのスコアが高くなり、スコアが高い単語と共起関係がある単語はスコアが高くなります

これによって、どの単語がその人にとって重要か、というのを比較するためのスコアとして利用します
とはいえ、"重要さ" と言ってもこのやり方では結局 "よく使われているかどうか" くらいの意味でしかありません

f:id:chanmoro999:20161209203533p:plain


ページランクの計算は igraph のパッケージに入っているのでそれを利用します
ちなみに、igraph は R でも使えるので、R で試したコードをそのまま python に持ってくるのが楽でした

from igraph import *

g = read(input_gml_file)
g.vs['pagerank'] = g.pagerank(weights=g.es["pmi"])


最後に、重み、スコアをセットしたグラフに対して infomap によるクラスタリングを行います
グラフのクラスタリングの手法はいくつかあり spinglass が精度がいいという報告もあるらしいです
ただ、結局のところグラフの構造に左右されるぶぶんが大きいので、いろいろ試して比較するしかないかなーと思います

f:id:chanmoro999:20161209203601p:plain


グラフのクラスタリング (コミュニティ検出) はこの記事を参考にさせていただきました
いくつかの手法を比較されていて非常にわかりやすいです

tjo.hatenablog.com


クラスタリングアルゴリズムも igraph に実装されているのでお手軽に使えます

from igraph import *

g = read(input_gml_file)
g.vs['cluster_infomap'] = g.community_infomap(edge_weights=g.es["pmi"], vertex_weights=g.vs['pagerank']).membership

最近は、グラフのノードの埋め込み表現を取得する DeepWalk とかの手法が出てきていて、
これを利用した方が従来の隣接行列を使う手法よりもクラスタリングやリンク予測の特徴量としてよく振る舞うらしいです


記事の先頭に戻る


4. 可視化する

さて、それでは解析した結果を可視化してみましょう

僕は可視化ツールに Gephi を使っています

oss.infoscience.co.jp

グラフ可視化のツールはいろいろあって、javascript で実装された Web ブラウザベースのものが多いです
igraph にも可視化の処理が実装されていますが、SVG などの画像として出力するものです

ノード数が多い巨大なグラフだとブラウザベースのものは処理が重すぎて全然使えないですし、
ノードを動かしたりフィルタをかけて部分的にいじりながらグラフを見る方がわかりやすいので、そうすると Gephi がわりと使いやすいです
とはいえ、大きいグラフだと結構な頻度でフリーズします

巨大なグラフの可視化はそれだけでも未だに研究が続けられているくらい難易度が高い問題らしいので、
いろいろなツールを使ってみるのがいいですね


さて、Gephi で GML ファイルを読み込んでグラフを表示したら、
ページランクの値をノードの大きさとしてセットして、クラスタの値ごとにノードの色を変えるように調整をします

f:id:chanmoro999:20161209203628p:plain


ノードのレイアウトのやり方もたくさん種類があってどれが良いかを決めるのは難しいんですが、
OpenOrd が一番いい感じにクラスタ毎にバラけてくれるので、だいたいまず OpenOrd を使ってます


Gephi 上でレイアウトを整えたら、画像ファイルに書きだすといい感じになります

f:id:chanmoro999:20161209185850p:plain


記事の先頭に戻る


5. まとめ

さて、今回はこんな感じで、うちの社長の脳内を解明すべく slack の発言をグラフを利用して解析する手法について解説しました

とはいえ僕もグラフ解析について勉強中なので、めちゃくちゃ詳しいというわけではないんですが、
グラフ構造でデータを扱うことでデータ間のリレーションに着目することができます

関係の強弱、扱いの異なるリレーションであっても同じグラフ内に表現できるのがとてもいいなーと感じています


ちなみに、今回のようなグラフ解析の技術は、今年の対話システムシンポジウムや CEATEC に Nextremer で出展した
うちの社長をコピーした対話botの中でも使っています

prtimes.jp


neo4j などグラフ構造に特化したデータベースもありアプリケーションに組み込むことは難しくないので、
今後もグラフを利用したアプリケーションを模索していきたいと思います


記事の先頭に戻る