Document

極大2部クリークの高速列挙法と
データマイニングへの応用
宇野毅明
情報学研究所
有村博紀
浅井達哉
九州大学
九州大学
2003年7月16日夏のLAシンポジウム
研究の概要
・極大2部クリークを高速に列挙するアルゴリズムの提案
・そのアルゴリズムの実装
・データマイニングのclosed item set 列挙問題に適用
ベンチマーク問題を解いて、既存アルゴリズムと比較する
列挙がしたい
・ある種の部分グラフを見つけ出す
データマイニング、ウェブマイニング、計算言語学など
・大量にほしい
→ 出てきたものをもう一度加工
→ 統計的に処理
→ 出現数を調べる（グラフマイニング）
→ クラスタの種にする（計算言語学）
・入力データは巨大だが、解の個数は意外と少ない
・ウェブネットワーク・辞書・文書データベース
可能であれば、全部列挙したい
極大2部クリーク列挙問題
問題：
「与えられたグラフ G = (V,E ) の全ての極大2部クリーク(極大ク
リーク)を、ちょうど一度ずつ出力せよ（列挙せよ）」
・極大安定集合の列挙に変換可能
 築山らのアルゴリズムで、１つあたり O(|V||E| ) 時間でできる
研究の動機
 築山らのアルゴリズムで、１つあたり O(|V||E|) 時間でできる
・しかし、現実問題では、 |V|、|E| ともに大きい（1万～100万）
・ただし、グラフが疎である事が多く、
最大次数・平均次数はそれほど大きくない
 平均次数・最大次数に依存するアルゴリズムがありがたい
計算量は最大次数、ランダムグラフでの実験的実行時間は
平均次数に依存するアルゴリズムを作った
ウェブコミュニティーの発見
対象：ウェブのネットワーク
極大2部クリークの
リンク先：共通の話題に関するページ
リンク元：共通の話題を持つコミュニティー
グラフマイニング
・与えられた大きなグラフ、あるいはたくさんのグラフの中か
ら、頻出する部分グラフを出力する
・部分グラフ＝
木、サイクル、クリークなど
・候補を作り、列挙して勘定する
アルゴリズムが一般的
・クリーク、2部クリークは、
極大なものを列挙すれば、後が簡単
類義語群の発見
対象：単語の組合せからなる
複合語の辞書
関東
地方
関西
地区
中国
電力
北陸
極大2部クリークがある種似た意味を持つ単語
の集合
類似論文のグループ化
対象：論文とそのアブストラクト
論文A
論文B
論文C
論文D
2部極大クリークの
語：研究分野
論文：その分野の論文
語1
語2
語3
頻出集合
対象：売上データなど
客１
客２
客３
客４
2部極大クリークの
客：同じような商品を買うグループ
商品：一緒に売れやすい商品
ビール
紙おむつ
タバコ
極大2部クリークの列挙法
・築山らの列挙法の改良版
G ＝ ( V1 ∪ V2 , E )
X (K) ： K の全ての頂点に隣接する頂点の集合
K≦i ： K の添え字 i 以下の頂点の集合
・極大クリーク K に対して X( K ∩ V2 ) = K ∩ V1
なので、以後 K ∩ V2 で極大2部クリークを定める
・同様に X( K ∩ V1 ) = K ∩ V2 も成り立つ
V1
V2
極大2部クリークの親
・ X ( X ( K≦i-1 ) ) ：極大クリーク K の親：
ただし i は X( K≦i-1 ) ≠ X( K≦i )が成り立つ最大のi
・ K の親 ⊂ K が成り立つので、この親子関係は非巡回的
X(K)
X(K≦i-1 )
V1
vi
V2
K≦i-1
K
X(X (K≦i-1 )) （Kの
親）
親子関係を逆探索
・極大2部クリークの親子関係は非巡回的
 グラフで書くと、木（列挙木）になる
列挙木を深さ優先探索して全ての解を出力する
・子供を見つけるアルゴリズムがあれば十分
極大2部クリークの子
・ K[i] = X ( X ( K≦i-1 ∪{vi} ) )
H が K の子  ある i に対して H = K[i]、H≦i = K≦i
K[i]≦i = K≦i  K[i] は K の子
X(K≦i-1 ∪{vi} ) )
X(K)
V1
vi
V2
K≦i-1
K
X(X (K≦i-1 ∪{vi} )) （Kの子）
計算時間
・全ての i について K[i] を求め、子供かどうか判定
・判定は O( | X (K[i])|Δ) 時間でできる。
・ X (K[i] ) =φ ならば K[i] = V2 なので、
X (K ) に隣接する vi のみK[i]の判定をすれば良い
・このような vi の | X (K[i])|Δ の合計は O(Δ3 )
 1反復の計算時間は O(Δ3 ) になる
各反復で極大2部クリークを1つ見つけるので、
計算時間は極大2部クリーク１つあたり O(Δ3 )
V1
V2
vi
計算実験
・ランダムなグラフに対して実験
・ V1の各頂点から、対応するV2の頂点の±r個の頂点に確
率1/2で枝を張る
頻出集合
E ：アイテムセット
F ：アイテムセットの部分集合（トランザクション）の族
α ：閾値（定数）
例） E ：商品の集合
トランザクション：各客の購買商品
F ：売上データのデータベース
頻出集合とclosed item set
E ：アイテムセット
F ：部分集合の族
α ：閾値（定数）
・ S ⊆E がα 個のトランザクションに含まれる  S は頻出集合
・頻出集合 S が他の頻出集合に含まれない  S は極大頻出集合
・ {T | T ∈F , S⊆T }＝C となる S の集合  closed item set
・頻出集合はデータベースの特徴を現している
・マーケッティングなどでの知識の掘り出しに使える
例）頻出集合の
客：同じような商品を買うグループ
商品：一緒に売れやすい商品
closed item set の列挙
たいていの問題では、
＃極大頻出集合＜＃closed item set ＜＃頻出集合
・頻出集合は数が多すぎる
・極大頻出集合は、少なすぎて、情報が失われているかも
＆列挙に手間がかかる
 closed item set の極大元で、
頻出集合になっているものを列挙しよう
2部極大クリークと closed item set
V1 = F
V2 = E
T ∈ F が e ∈ Eを含む ⇔ 枝 (T, e )が存在
極大2部クリークとclosed item set の極大元が1対1対応
V1 = F
客１
客２
客３
客４
V2 = E
ビール
紙おむつ
タバコ
極大2部クリークを
列挙すれば、
Closed item set の
極大元が列挙できる
実装上の工夫
今回の実装では、以下のような工夫を加えた
(1) 頂点の添え字を次数の昇順でソートする
（判定を行う K[i] の数の減少）
(2) 次数大の頂点には隣接行列を用意
（隣接性を定数時間で判定）
(3) 各 K[i] を O(|X(K)|Δ) 時間で求める
(4) K[i]≦i の頂点を添え字の小さい順に求めK≦i と比較する
（比較途中で異なることが分かれば、 K[i]の生成時間が短
縮される）
ベンチマーク問題
・計算実験を行ったベンチマーク問題は以下の4つ
どれも、良く用いられるもの
BMS-WebView1 （Webから抽出したデータ）
|E|=500 が|F | = 6万、平均次数 2.5
BMS-WebView2 （Webから抽出したデータ）
|E|=3300 が|F | = 6万、平均次数 5
BMS-POS （POSデータ）
|E|=1650 が|F | = 51万、平均次数 6
IBM-Artificial （人工的に生成したデータ）
|E|=1000 が|F | = 10万、平均次数 10
実験結果
まとめ
・疎グラフの極大2部クリークを1つあたり O(Δ3 ) 時間で列
挙するアルゴリズムを提案した
・ランダムに作成したグラフに対する実験的な計算時間は、
O(Δ) であることを確認した
・ closed item set 列挙のベンチマーク問題に対して計算機
実験を行い、特に、時間のかかる難しい問題で、既存のア
ルゴリズムよりも大幅に高速化されることを確認した

Download Report