大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発

Presentation on theme: "大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発"— Presentation transcript:

1 大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発
宇野 毅明 国立情報学研究所 ＆　総合研究大学院大学（博士募集中） 2003年1月20日　アルゴリズム研究会

2 研究背景 ・ ある種の部分グラフを見つけ出す ・ データマイニング、ウェブマイニング、計算言語学など ・ 大量にほしい
　 ・ データマイニング、ウェブマイニング、計算言語学など ・ 大量にほしい 　　→ 　出てきたものをもう一度加工 　　→ 　統計的に処理（頻出度など） 　　→ 　何かの候補（フィルタリング） ・ 入力データは巨大 　 ・ ウェブネットワーク　 ・ 辞書　 ・ 文書データベース

3 対象： ウェブのネットワーク 部分グラフ： 2部クリーク リンク先： 共通の話題に関するページ リンク元： 共通の話題を持つコミュニティー
例１：ウェブコミュニティーの発見（村田） 対象：　ウェブのネットワーク 部分グラフ：　2部クリーク リンク先： 共通の話題に関するページ リンク元： 共通の話題を持つコミュニティー

4 対象： 単語の組合せからなる 複合語の辞書 部分グラフ： 2部クリーク ある種似た意味を持つ単語の集合
例2：類義語群の発見（中渡瀬） 関東 関西 中国 北陸 対象：　単語の組合せからなる 　　　　　複合語の辞書 部分グラフ：　2部クリーク ある種似た意味を持つ単語の集合 地方 地区 電力

5 対象： 論文とそのアブストラクト 部分グラフ： 情報量の多い頂点集合 （準クリーク） 語： 研究分野 論文： その分野の論文
例3：類似論文のグループ化（相澤） 論文A 論文B 論文C 論文D 対象：　論文とそのアブストラクト 部分グラフ：　 情報量の多い頂点集合 （準クリーク） 語：　研究分野 論文：　その分野の論文 語1 語2 語3

6 共通点 ・ 目的に合うように、ある種の目的関数を最適化する部分グラフを見つけている
・ 現在使っているシステムは、かなり遅い（なんとかしたい） ・ 厳密に最適解であることにはあまり意味がない ・ 大量に、高速に求めたい ・ モデルが変化することがありうる

7 今回扱った問題 u,v∈S, (u,v)∈E v∈S 入力： 大規模＆疎なグラフ G=(V,E)
問題１： 高速かつ大量に極大（2部）クリークを求めよ 問題２： 高速かつ大量に評価値の大きい部分グラフ S を求めよ （最適でなくても良い：（準クリークと呼ぶ）） 枝重み wE ,頂点重み wV, 頂点数の関数 g(|S|) 評価値 f(S) ＝ ΣwE (u,v) 　+ ΣwV (v) + g(|S|) 　　　 　　　　u,v∈S, (u,v)∈E v∈S

8 いろいろな評価値 クリークにどれだけ近いか： 2 × S 内部の枝数 ／ （頂点数） ×（頂点数－1） カット容量 ：
カット容量 ：　 　　頂点v の重み ：＝ －（ v に接続する枝のコストの総和 ） 　　枝 e の重み 　 ：＝ （ e のコストの2倍 ） S の重み 　 ＝ 　S から出て行く枝重みの総和 （ S 内の枝 (u,v) の枝重みと、 u,v のコストがキャンセル）

9 貪欲解法 問題１の極大クリークは、貪欲解法で求められる ・ S = φ ・ S の全ての頂点に隣接するV＼S の頂点を、繰り返し加える
計算量：　 O(|E| |S|) 単純に計算すると、枝数が100万、 |S|=30 程度だと、 10 秒程度 大量に計算するには時間がかかる

10 貪欲解法の改良 U(S) ： S のすべての頂点に隣接する頂点の集合 ・ S = φ
・ U(S) の頂点を Sに繰り返し加え、 U(S) を更新 ・ U(S) = φとなったら S を出力 U（S∪｛v｝） = ｛ u | ∀u∈U(S), (v,u)∈E ｝ 計算量：　 O（ Δ|S| ）　　　 (Δ ：最大次数 ) ・ Δ は高々100程度であるので、1/1000秒程度 ・ 2部クリークも、同じ方法でできる

11 局所探索 問題2の準クリークは、局所探索で求めると効率が良い N(S) ： S の近傍の集合
N(S) = ｛ X| ∃v, X=S∪v or X=S＼v ｝ ・ S = φ ・ f(S') < f(S) になる S'∈N(S) に対して S=S’ とし、繰り返す ・ S' が存在しなければ S を出力 1反復の計算量：　 O(|V|Δ) 頂点数が 10万くらいだと、 1反復 1秒程度

12 最良の近傍を選ぶ ・ 補助のデータを用意する（改善値と呼ぶ） f+(S,v) = wV(v) + Σ wE((u,v)) u∈S
・ S' ∈ N(S) に対して f(S') - g(|S'|) = f(S) - g(|S|) + f+(S,v) 　if S'=S∪ v f(S) - g(|S|) - f+(S,v) if S'= S＼v ・ S に含まれる頂点で f+(S,v) を最小にする頂点 ・ S に含まれない頂点で f+(S,v) を最大にする頂点 のどちらかが N(S) 内で f() を最大化する ⇒ 　ヒープで保持すれば O(log |V|) 時間で見つかる

13 改善値の変化 ・ S=S∪w か S= S＼w と更新したとする f+(S,v) = wV(v) + Σ wE((u,v)) u∈S
・ w及び w に隣接しない頂点は改善値が変化しない ・ w に隣接する頂点 v は f+(S,v) + wE ((w,v))　　　に変化する ⇒ 　更新にかかる時間は O( Δlog |V|) ・ 頂点数 10万なら log |V| ≦ 20、Δが100程度とすると 　　　　　　　 1反復の計算時間は1/500秒程度 ・ 2部グラフでも、同様にできる

14 ・ 近傍の中から最良のものを短時間で見つけられるので、高速なタブーサーチが作れる
余談：タブーサーチへの応用 ・ 近傍の中から最良のものを短時間で見つけられるので、高速なタブーサーチが作れる

15 計算実験 ・ C で作ってみると、おおよそ予想通りの計算時間で動いた ・ マシン：パソコン PentiumIII 500MHz
・ OS＆コンパイラ： Linux、gcc ・ 一般グラフでの問題を解いた（2部クリークではない） ・ 解の精度は不明 　（そもそも最適解は求められない。 　原点は、「巨大なグラフで、どのようなことができるか」 　　なので、気にしない ）

16 入力グラフと実行結果 ・ 一般のグラフ ・ 各頂点の次数がほぼ同じになるランダムグラフ ・ f =（頂点数＊平均次数）/2－（外に出る枝数）
・ 各頂点の次数がほぼ同じになるランダムグラフ ・ f =（頂点数＊平均次数）/2－（外に出る枝数） ・ それぞれの頂点を初期解として実行（頂点数回実行）

17 入力グラフと実行結果 クリーク 頂点数 枝数 平均次数 総計算時間 総反復数 1万反復平均計算時間 極大 1000 30万 300
0.78 秒 6111 6.1 秒 1万 1000万 29 秒 46002 6.3 秒 準 10万 100 462 秒 239万 1.9 秒 100万 10 269　秒 799万 0.34 秒

18 まとめと今後の展開 ・ 高速に極大クリーク、準クリークを大量に見つけるアルゴリズムを開発し、実装した ・ 実際問題への適用
　・ web community の発見（村田） 　・ 類似語群の発見（中渡瀬） 　・ 大規模重み付きkカット問題（有限要素法計算の前処理） 　・ 論文のカテゴリー化（相澤） 　　　などなど