Document

疑似頻出アイテム集合の
多項式遅延列挙アルゴリズム
宇野毅明（情報学研究所）
有村博紀（北海道大学）
2007年7月26日人工知能学会DMSM研究会
頻出パターン列挙
・データベースの中に多く現れるパターンを全て見つける問題を
頻出パターン列挙（あるいは発見、マイニング）問題という
データベース：トランザクション、ツリー、グラフ、多次元ベクトル
パターン：部分集合、木、パス・サイクル、グラフ、図形
データベース
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
頻出する
パターンを抽出
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
・実験1● ,実験3 ▲
・実験2● ,実験4●
・実験2●, 実験3 ▲, 実験4●
・実験2▲ ,実験3 ▲
．
．
．
・ ATGCAT
・ CCCGGGTAA
・ GGCGTTA
・ ATAAGGG
．
．
．
本研究では
・いわゆる頻出集合列挙をターゲットにする
入力：トランザクションデータベース：
各トランザクション T がアイテム集合 E の部分集合
になっているようなデータベースD
つまり、D, ∀T ∈D, T ⊆ E
・解が多い（大きくて面白いものは少ない）
・包含関係が厳密
 「多くの項目になんとなく含まれている」ものを見つけたい
アイテム集合に対して、あいまいな包含関係を考え、
頻出集合の列挙アルゴリズムを提案する
既存研究
・ fault-tolerant pattern、degenerate pattern、soft occurrence
などとよばれて、研究されている
－包含関係を一般化する場合、アイテムの含有率が閾値異常
のとき、含まれると定義
－あるいは、アイテム集合・トランザクションの組で、アイテム
が項目に含まれない回数が小さいようなもの
－文字列などでは、もっと一般的に「類似」を包含関係に使う
－完全性を保証した列挙型の解法は少ない
アルゴリズム的な観点からモデルと解法を見つめたい
まずは通常の頻出集合
集合K に対して：
K の出現： K を含む D のトランザクション
K の出現集合 Occ(K)： K の出現の集合
K の頻出度 frq(K)： K の出現集合の大きさ
1,2,5,6,7,9
2,3,4,5
D ＝ 1,2,7,8,9
1,7,9
2,7,9
2
{1,2}の出現集合
＝ { {1,2,5,6,7,9},
{1,2,7,8,9} }
{2,7,9}の出現集合
＝ { {1,2,5,6,7,9},
{1,2,7,8,9},
{2,7,9} }
頻出集合
・頻出集合： D の閾値σ個以上のトランザクションに含まれる集合
（頻出度がσ以上の集合）（ σを最小サポートとよぶ）
例）データベース D の3つ以上のトランザクションに含まれる集合
D＝
1,2,5,6,7,9
2,3,4,5
1,2,7,8,9
1,7,9
2,7,9
2
３つ以上に含まれるもの
{1} {2} {7} {9}
{1,7} {1,9}
{2,7} {2,9} {7,9}
{1,7,9} {2,7,9}
与えられたトランザクションデータベースと最小サポートσに対
して、頻出集合を全て見つける問題が頻出集合列挙
擬似包含関係
・アイテム集合 P がトランザクション T 含まれる、の定義
・良く使われる方法：閾値θ<1 に対して |P∩T| ／ |P| ≧ θ
 頻出集合の単調性がなくなる
 「空集合以外の部分集合は全て頻出でない」頻出集合もある
 難しい
・代わりに「含まないでいいアイテムの数」を使う
閾値θ≧1 に対して |P＼T| ≦θ （k 擬似包含関係とよぶ）
 単調性は保持
 多くの項目が P のうち３個のアイテムを含む、といったルー
ルが見つかる
k 擬似頻出集合
・ k 頻出集合： D のσ個以上のトランザクションに k 擬似包含の意
味で含まれるアイテム集合
D ＝
σ=3での1擬似頻出集合
1,2,5,6,7,9 {1,2,3} {1,2,4} {1,2,5} {1,2,7} {1,2,9} {1,3,7}
2,3,4,5
{1,3,9} {1,4,7} {1,4,9} {1,5,7} {1,5,9} {1,6,7}
1,2,7,8,9
{1,6,9} {1,7,8} {1,7,9} {1,8,9} {2,3,7} {2,3,9}
1,7,9
{2,4,7} {2,4,9} {2,5,7} {2,5,8} {2,5,9} {2,6,7}
2,7,9
{2,6,9} {2,7,8} {2,7,9} {2,8,9} {3,7,9} {4,7,9}
2
{5,7,9} {6,7,9} {7,8,9}
{1,2,7,9} {1,3,7,9} {1,4,7,9}{1,5,7,9}
{1,6,7,9} {1,7,8,9} {2,3,7,9} {2,4,7,9}
{2,5,7,9} {2,6,7,9} {2,7,8,9}
自明なパターンがたくさんある
効率良い列挙アルゴリズムを考える
擬似頻出パターンの単調性
・擬似頻出集合は単調なのでバックト
ラック法で多項式時間列挙できる
111…1
・各末尾拡張のk 擬似頻出度を振り分け
で計算することで、1反復の計算時間は
O(||D||) 時間になる
頻出
000…0
1,2,3,4
・データの構造・計算の内容が
頻出集合と同じなので、
同じテクニックがそのまま使える
－ビットマップ
－ダウンプロジェクト
－データベース縮約、FP-tree
1,2,3 1,2,4
1,2
1,3
1
1,3,4
1,4
2,3,4
2,3
2,4
3,4
2
3
4
φ
k 擬似出現集合の計算
・ Occ=k(P) = {T∈D| |P＼T|=k } とする
 つまりちょうど k 個含まないトランザクションの集合
－ Occ≦k(P) = ∪Occ=i(P)
・ Occ=h(P∪i) = Occ=h(P)∩Occ(i) ∪ Occ=h-1(P∪i)＼Occ(i)
 通常の出現と性質が同じ
 更新に同じ技術が使える
A
A
（ダウンプロジェクト、振り分け…）
B
B
A B A
C
C
・データベースの圧縮も可能
B A A
B A
A D
D
B B
B C
B E C
E
・再帰が深くなり、頻出度が
C C
C D
C F D
F
D G F F D
G
小さくなると、計算が速くなる
8 9 10 11 12
末広がり性
・バックトラックは、各反復で複数の再帰呼び出しをする
 計算木は、下に行くほど大きくなる
 計算時間を支配するのは一番下の数レベル
計算時間長
・・・
計算時間の短縮が期待される
計算時間短
最小サポートが大きい場合も
・ θが大きいと、下のレベルでも多くの出現を見ることになる
 末広がり性による高速化はいまひとつ
・データベースの縮約により、下のレベルの高速化をはかる
（１）前回追加したアイテムより小さいアイテムは消す
（２）現在の出現集合からできるデータベースの中で、頻出になって
いないアイテムは消去する
（再帰呼び出しの中で加えられることが無いから）
（３）まったく同一のトランザクションは、１つにまとめる
１
・実データだと、下のほうのレベルでは
だいたい大きさが定数になる
σ小さいときと速度の大きな差はない
１
３
２
２
６
４
７
４
３
２
５
４
３
１
４
４
４
５
６
７
６
７
６
７
小さくて自明なパターン
・ k 擬似包含関係では、大きさ k 以下のアイテム集合は全ての
トランザクションに含まれる
・大きさが k より少しだけ大きいアイテム集合も多くが含む
 多くの小さくて自明な頻出集合が存在する
・実用上は、これらを無視したい
 ある程度 (l とする）の大きさを持つ頻出集合を直接的に見
つける方法を考える
部分頻出度条件
・大きさ l の集合を工夫なく調べると、指数的な時間がかかる
 ある程度絞込みをしたい
 特徴を持つ部分構造を基にしよう
・大きさ l の k 擬似頻出集合 P を考える
・一般性を失うことなく、 P={1,…,l} かつ
|Occ=k(P)＼Occ({i})| の大きい順に並んでいるとする
・アイテム集合 {1,…,y} の頻出度を考える
・ Occ=k(P)＼Occ({i}), i>y のトランザクションは
{1,…,y} を k-1 擬似包含関係の意味で含む
i=2
{1,2,3,4,5} ⊆2 {1,3,5,6,7,10,15}
部分頻出度条件
・ Occ=k(P)＼Occ({i}), i>y のトランザクションは
{1,…,y} を k-1 擬似包含関係の意味で含む
 |Occk-1({1,…,y})| ≧ |∪j=y+1,...,|P| (Occk(P)＼Occ({i}))|
・ |Occk(P)＼Occ({i})| の平均は (k / |P|) |Occ=k (P)| 以上
・ 1,…,y は|Occk(P)＼Occ({i})| の昇順で並んでいる
 |Occk-1({1,…,y})| ≧ |Occk(P)|×(|P|-y)/|P|
P までたどり着く
k-1擬似頻出度に関する条件を満たすアイテム集合の列がある
部分頻出度条件による探索経路
・大きさ l の k 擬似頻出集合は |Occk-1(P)|＞σ(l-|P|) /l を満たすP
のみを経由して見つけられる
 この条件を満たすk 擬似頻出集合を全部見つけよう
・末尾拡張は使えない（条件を満たさないものが拡張元になる）
・逆探索を使う
 条件を満たすパターン P は、P＼{i} の中で |Occk-1(P＼{i})| を
最大にするものから見つける
・ |Occk-1(P＼{i})| の計算は、振り分けで効率良くできる
１反復 O(|P|×||D||) 時間になる
部分頻出度を満たす擬似頻出集合
・ k=1 で最小サポート =3 の場合
1,2,5,6,7,9
2,3,4,5
D ＝ 1,2,7,8,9
1,7,9
2,7,9
2
部分頻出度条件を満たす頻出集合
{1} {2} {5} {7} {9} {1,2} {1,5} {1,6} {1,7}
{1,8} {1,9} {2,3} {2,4} {2,5} {2,6} {2,7}
{2,8} {2,9} {3,4} {3,5} {4,5} {5,6} {5,7}
{5,9} {6,7} {6,9} {7,8} {7,9} {8,9}
数が減るので、効率良い探索が期待できる
まとめ
・「高々 k 個のアイテムが含まれない」という条件を利用した
あいまいな包含関係
・その包含関係での頻出集合列挙
・逆探索による固定サイズの頻出集合を直接的に見つける
アルゴリズム
今後の課題
・実装と計算実験
・他のパターンへの列挙技術の活用
・「r % は含まれる」とした包含関係への取り組み

Download Report