グラフのクラスタリング
グラフのクラスタリングというものを少し考えてみます。既にあちこちで研究されているものですので、「どこかで誰かが書いてたなあ」という話を少しまとめます。
グラフとは
大前提として、グラフとは何かということになります。グラフといって、この世界では棒グラフだの円グラフだのを意味しません。
この世界ではズバリこれです。
ノード(図の○)がエッジ(図の線)によって結ばれているものをいいます。ノードにはそれぞれ番号を振ってあります。さらにこの図では、エッジに数字が書いてありますが、これはエッジの重みです。重みを規定しないグラフもありますが、重みをつけたグラフを特に「重み付きグラフ」と呼びます。
これが何を意味するのかといえば、例えばノードを「都市」、エッジを「線路」、エッジの重みを「時間」だとすれば、路線図となります。
最短経路問題
さて、グラフの中で古典的な問題に「最短経路問題」があります。Shortest Path Problemで、少し気取ってSPPと呼ぶこともできます。すると嫌われることができます。
「最短経路問題」とは、あるノードからあるノードに最短の重みの和で行ける経路(と重みの合計)を求めるものです。路線図の場合でいいますと、「東京駅から大阪駅に行くためには、どの都市を経由していくと一番近いですか？その場合は何時間かかりますか？」というものです。ナビタイムも乗換案内もこれを解いているわけです。(たぶん。)
で、例に出した図でノード1について考えてみましょう。
- 目的地2：1->2 (2)
- 目的地3：1->3 (1)
- 目的地4：1->3->4 (3)
- 目的地5：1->6->5 (5)
- 目的地6：1->6 (4)
ということになります。ここで、使った経路だけを取り出してみましょう。(重みが同一のために複数の経路で行けるものもありますが、とりあえず、一つだけ取り出しています。)
このように、出発ノードを一つだけ決めると、そこからの最短経路を利用する時に利用するエッジや重みだけが現れます。
このようなグラフはツリーの形になりますが、これを特に最短経路木と呼びます。かっこいい言い方をしたい方は、Shortest Path Spanning Treeと呼んで下さい。スパニングツリーという言葉は、何となくかっこいい割には特に嫌われるものではありません。
ダイクストラ法
で、先ほどの最短経路ですが、どうやって求めればいいのでしょうか？私が上の最短経路を求める上でとった方法は、「じっと目で見る法」と呼ばれるもので、ノードの数が少ないときには非常に有功です。
しかし、ノードが多くなってくると、「じっと目で見る法」は破綻します。そこで出てくるのが「ダイクストラ法」です。ダイクストラというのは人の名前でして、スペルを覚えられないことで有名です。
この方の数多の業績はおいておきまして、ダイクストラ法というアルゴリズムがあるのです。それを使うと比較的簡単に最短経路を求めることができます。
クラスタリングとは
さて、次にクラスタリングです。
クラスタリングというのも、何となくかっこいい名前ですが、簡単に言えば「グループに分割する」ということです。グラフの場合には、そのノードで近いものをまとめてグループ化することになります。
どういう基準でグループ化するのかという話になりまして、いろいろな考え方があります。しかし、例えば次のようなグラフの場合は何となく分かることと思います。
ノードの図の中での位置もわざとわかりやすくは書いていますが、何となく「1,2,3,6」と「4,5,7」が別れるような気がするのではないでしょうか。
クラスタリングの手法
クラスタリングにもいろいろな手法がありますが、よく利用されるのは、「各ノードが全て独立のクラスタ(グループ)の状態」から開始して、近いノードをくっつけてそれをクラスタ化するということを行うものです。で、新たにできたクラスタ同士で「近い」クラスタをくっつけていきます。
ノードとノードの「近さ」は先ほどの「最短経路」によって求められますが、クラスタとクラスタの「近さ」って何だ？という話になりますが、それにはいろいろな方法があります。例えばクラスタ内で一番近いノード同士だけをみるなんていうものでも十分に実用的です。
それに対して、逆に「全部がつながった状態からはじめる」というものもあります。この場合には、不要なエッジを削除していくという作業になります。「不要なエッジ」はどのように検出するかといえば、これもいろいろな方法がありますが、例えば先ほどの「最短経路」で何度もたどられる場所はこれにあたります。
先ほどの図ですが、1から4、2から7、6から5、その他数多くの最短経路において「3→5」を利用します。このようなよく使われる場所こそが、切断すべきエッジなのです。
従いまして、最短経路を求めては、よく使われる道を検出し、エッジを切断、ということを繰り返していくとクラスタリングができます。(なお、切断していくと、完全に分割されたグラフができますので、その状況では、最短経路の計算を少し工夫する必要はあります。)
図の場合は、3-5のエッジが7回も最短経路に含まれることから最初に切断されます。(ちなみに、以下、3-6, 1-6, 1-2...が切断されます。この手法の場合、重みが小さい(近い)ところはよく通るために切断されやすくなるので問題が起きます。重みなし(全て重みが1)グラフならば、もう少しうまくいくのです。)
応用
「それがどうした」という話になるわけですが、このようなクラスタリングはウェブにおけるコミュニティ検出に利用されるのです。
各ノードを各ウェブページ(やサイト・ブログ)に当てはめ、エッジの重みを関連度(この関連度をどのように計算するかは問題ですが)とすることで、クラスタリングしていくことでページのまとまりが判明していきます。
研究者の皆様はこれをやっております。どのようなアルゴリズムでクラスタリングを行うか、それから、どのようにして計算量を下げるかというのが課題といえます。(ここでは触れませんでしたが、最短経路を見つけるのは、それなりに計算量のコストがかかります。ノード数が必然的に多くなるウェブへの応用では、かなりの問題です。)
