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
客1
客2
客3
客4
V2 = E
ビール
紙おむつ
タバコ
極大2部クリークを
列挙すれば、
Closed item set の
極大元が列挙できる
研究の動機
極大2部クリーク列挙は、築山らのアルゴリズムで、1つあたり
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 を高速に列挙するアル
ゴリズムを提案した
・ アルゴリズムを実装し、ベンチマーク問題を解いた
・ 特に、時間のかかる難しい問題で、既存のアルゴリズムよ
りも大幅に高速化が行われた