Document

2部クリークを用いた
closed item set の効率的な列挙
宇野毅明
情報学研究所
有村博紀
浅井達哉
九州大学
九州大学
2003年7月31日人工知能と知識処理研究会
研究の概要
・データベースから closed item set を見つけ出す問題を
2部グラフの極大2部クリークに変換
・極大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部クリーク列挙と等価
φ
極大2部クリーク列挙問題
問題：
「与えられたグラフ G = (V,E ) の全ての極大2部クリークを、ちょう
ど一度ずつ出力せよ（列挙せよ）」
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 の
極大元が列挙できる
研究の動機
極大2部クリーク列挙は、築山らのアルゴリズムで、１つあたり
O(|V||E|) 時間でできる
・しかし、現実問題では、 |V|、|E| ともに大きい（1万～100万）
・ただし、グラフが疎である事が多く、
最大次数・平均次数はそれほど大きくない
 平均次数・最大次数に依存するアルゴリズムがありがたい
計算量は最大次数、ランダムグラフでの実験的実行時間は
平均次数に依存するアルゴリズムを作った
極大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部クリーク1つあたり O(Δ3 )
V1
V2
vi
実装上の工夫
今回の実装では、以下のような工夫を加えた
(1) 頂点の添え字を次数の昇順でソートする
（判定を行う K[i] の数の減少）
(2) 次数大の頂点には隣接行列を用意
（隣接性を定数時間で判定）
(3) 各 K[i] を O(|X(K)|Δ) 時間で求める
(4) K[i]≦i の頂点を添え字の小さい順に求めK≦i と比較する
（比較途中で異なることが分かれば、 K[i]の生成時間が短
縮される）
計算実験
・ランダムなグラフに対して実験
・ V1の各頂点から、対応するV2の頂点の±r個の頂点に確
率1/2で枝を張る
ベンチマーク問題
・計算実験を行ったベンチマーク問題は以下の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部クリークの
リンク先：共通の話題に関するページ
リンク元：共通の話題を持つコミュニティー
グラフマイニング
・与えられた大きなグラフ、あるいはたくさんのグラフの中か
ら、頻出する部分グラフを出力する
・部分グラフ＝
木、サイクル、クリークなど
・候補を作り、列挙して勘定する
アルゴリズムが一般的
・クリーク、2部クリークは、
極大なものを列挙すれば、後が簡単
類義語群の発見
対象：単語の組合せからなる
複合語の辞書
関東
地方
関西
地区
中国
電力
北陸
極大2部クリークがある種似た意味を持つ単語
の集合
類似論文のグループ化
対象：論文とそのアブストラクト
論文A
論文B
論文C
論文D
2部極大クリークの
語：研究分野
論文：その分野の論文
語1
語2
語3
まとめ
・疎グラフの極大2部クリークを列挙するアルゴリズムに実
装上の工夫を加え、closed item set を高速に列挙するアル
ゴリズムを提案した
・アルゴリズムを実装し、ベンチマーク問題を解いた
・特に、時間のかかる難しい問題で、既存のアルゴリズムよ
りも大幅に高速化が行われた

Download Report