Document

頻出・飽和・極大頻出集合の効率的
な列挙アルゴリズムとその実装
宇野毅明
清見礼
有村博紀
国立情報学研究所
国立情報学研究所
北海道大学
2004年 9月30日データマイニングワークショップ
トランザクションデータベース
トランザクションデータベース：各トランザクション T がアイ
テム集合 E の部分集合になっているようなデータベース
1,2,5,6,7
∀
つまり、 T , T ∈T , T ⊆ E
2,3,4,5
T ＝ 1,2,7,8,9
1,7,9
2,7,9
・ POSデータ（各項目が、客1人の購入品目）
2
・アンケートのデータ（1人がチェックした項目）
・ web log （1人が1回のwebサーフィンで見たページ）
・オプション装備（車購入時に1人が選んだオプション）
実際のデータは、疎であり大きいものが多い
集合のオカレンス
集合K に対して：
K のオカレンス： K を含むT の項目
K のオカレンス集合 Occ(K)： K を含むT の項目全ての集合
1,2,5,6,7,9
2,3,4,5
T ＝ 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} }
頻出集合
・頻出集合：T の定数α個以上のトランザクションに含まれる集合
（オカレンス集合のサイズがα以上の集合）（α：最小サポート）
極大頻出集合：他の頻出集合に含まれない頻出集合
例）データベースT の3つ以上のトランザクションに含まれる集合
1,2,5,6,7,9
2,3,4,5
T ＝ 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}
{2,7,9}
飽和集合
・頻出集合をオカレンス集合が等しいものでグループにわける
（これを同値類と見なす）
・飽和集合：グループの中の極大元
（＝オカレンス集合の共通部分）
⇒ ユニークに定まる
・アイテム集合に対して、
そのオカレンス集合の
共通部分を閉包という
極大頻出集合
頻出飽和集合
問題
・本発表で扱う問題：
与えられたデータベース T と α に対して、その
１．頻出集合を全て見つける
２．頻出飽和集合を全て見つける
３．極大頻出集合を全て見つける
・それぞれ多くの研究がある
・実装の研究も多くある
これらの問題に対して、アルゴリズム
LCM （Linear time Closed itemset Miner）を提案
各レベルを順に計算（apriori）
（既存）
・最初に大きさ1の頻出集合を全て見つけ、メモリに蓄える
・次に大きさ2の頻出集合を、大きさ1の頻出集合を組合せて全
て見つけ、メモリに蓄える
・以後、１つずつ大きさを増やす
メリット：
オカレンス計算の高速化
デメリット：メモリを大量消費＆既発見解検索時間の増加
バックトラック法
（既存）
・空集合から出発し、分枝限定法的に探索するアルゴリズム
・現在の解に、１つアイテムを加えた各解に対し、再帰呼び出し
・重複を避けるため、現在の解の末尾より大きなアイテムのみ
追加
1,2,3
1,2
1,2,4
1,3
1,3,4
1,4
Backtrack (K)
1
1 Output K
2 For each e > K の末尾（ K の最大のアイテム）
If K ∪{e}が頻出 call Backtrack (K ∪{e})
2,3,4
2,3
2,4
2
3
φ
計算時間＝ O( 頻出度のチェック時間×|E| )
3,4
4
頻出度計算
（既存）
・集合 K∪{e} のオカレンスを求める際、素直に行うと、
データベースの全ての項目を調べる必要がある
・ Occ( K∪{e} ) ⊆ Occ(K) という性質を用いる
⇒ K のオカレンスで e を含むものを見つければよい
⇒ Occ(K) ∩ Occ({e}) を計算すればよい
（ダウン･プロジェクト、という）
O( | Occ(K)| ＋ | Occ({e})|) 時間
検索用のデータ構造
（既存）
FP-tree：今までに発見した頻出集合を蓄えるデータ構造
prefix tree、trie とよばれるものと同じ
・ FP-treeは入力したデータベースを保管するのにも使われる
（同一項目の縮約などの操作が楽なため）
1
／｜＼
2 3 5
｜｜
4 5
｜
5
2
／｜＼
2 3 4
／｜
4 5
｜
5
3
｜
5
4 5
｜
5
・圧縮したprefixの分だけ、
頻出度の計算が速くなる
・圧縮率は通常1/2-1/3倍、
最良でも1/6倍程度
・2分木操作のため、
計算時間は増大
オカレンスの配布
（新規）
・各 e = K の末尾, …, |E| について、Occ(K ∪{e}) を
一度に全て計算する
K = {1,2} のオカレンス
A{1,2,4,5} B{1,2,3} C{1,2,3,4}
・バックトラック法は、末尾以降のアイテムを追加
⇒ {1,2,3}, {1,2,4}, {1,2,5} のオカレンス集合を計算
⇒ 疎な行列の転置を求めているのと同じ
⇒ 非ゼロ要素数の線形時間で求められる
各 e について O( |Occ(K∪{e}|) ) 時間
A
B
C
3 4 5
4 5
5
3
3
A B C
1,2,3
B C
1,2,4 A
1,2,5 A B
実際の計算では
（新規）
・頻出度計算では、生成した集合 K∪{e} が非頻出なら、
それは無駄な計算（うまくすれば省略できる可能性がある）
・しかし、そのような無駄は、計算全体の1/3 以下
（ただし、アイテムを「含まれる項目数」の小さい順でソート）
K∪
3
4
5
6
7
8
9
α
AD
ELM
ABCEFGH JKLN
ABDEFGI JKLMSTW
BEGILT
MTW
ABCDFGH IKLMNST
検索の手間がない分
オカレンス配布が
有利と思われる
データベースの縮小
（既存＆新規）
・入力したデータべースを縮小して、計算を高速化する
◆ e を含むトランザクションがα個未満
or 全てのトランザクションに含まれる
⇒ e をデータベースから削除
◆ 等しいトランザクションは１つにまとめる
・サポートが大きいと劇的に小さくなる（データベース縮約とよぶ）
さらに、バックトラック法なら、各反復で
◆ 末尾以前のアイテムを消去
してからデータベース縮約をすると、反復的に縮約され、
さらなる高速化が行われる（反復型データベース縮約とよぶ）
極大＆飽和頻出集合の列挙
（既存）
・頻出集合列挙のアルゴリズムに限定操作を加える
極大用、限定操作：１つ極大解が見つかったら、
その部分集合は極大解の候補からはずす
飽和用、限定操作：同一のオカレンス集合を持つ集合の中で、
極大でないものを候補からはずす
・メモリに解を保持して実装する
飽和拡張
（既存）
・飽和集合 K に対して、
K の飽和拡張＝（K + アイテム）の閉包
－任意の飽和集合は、他の飽和集合の飽和拡張になる
－（ K の頻出度）＞（ K の飽和拡張の頻出度）なので、
飽和拡張が導出する関係は、閉路を含まない
・飽和拡張をもとに列挙アルゴリズムを構築すると、
計算時間が飽和集合数の線形になる
Prefix保存飽和拡張
（新規）
・ prefix保存飽和拡張は、飽和拡張のバリエーション
定義：飽和集合K の閉包末尾
⇔ K ＝閉包（K ∩{1,…,j}）が成り立つ最小の j
定義：飽和拡張 H ＝閉包（K ∪{i}）が K のprefix保存飽和拡張
⇔ i > j かつ H ∩{1,…,i-1} ＝ K ∩{1,…,i-1} が成立
・ prefix保存飽和拡張には閉包の操作のみ必要（既発見解は不
要）
・任意の飽和集合は、他の唯一の飽和集合のPrefix保存飽和拡張
⇒ メモリを使うことなく、飽和集合を重複なく探索できる
飽和拡張・prefix保存飽和拡張の例
φ
・飽和拡張 ⇒ 非閉路グラフ
・ prefix保存飽和拡張 ⇒ 木
2
7,9
1,2,5,6,7,9
2,3,4,5
T ＝ 1,2,7,8,9
1,7,9
2,7,9
2
飽和拡張
prefix保存飽和拡張
1,7,9
2,5
1,2,7,9
1,2,7,8,9
2,3,4,5
1,2,5,6,7,9
2,7,9
頻出集合の列挙
・頻出集合列挙のボトルネックは、頻出度計算
・同値類内は、オカレンス集合が等しい
⇒ 頻出度計算が省略できる
・閉包を取らない解と閉包を取った解を保持
⇒ 両者は、同値類中の超立方体を導出
⇒ 超立方体内の解を列挙
同値類が大きければ効率が良い
極大頻出集合の列挙
（新規）
・バックトラック法による頻出集合列挙を考える
K ：現在の解
⇒
1 2 3 4 5
H： K を含む閉包 ⇒
・ H に含まれるアイテムが
最後に来るよう、並び替える
6
7
8
9
10
並び替え
6
8
・ H のアイテムを追加した再帰呼び出しでは、
極大頻出集合は見つからない
⇒ 再帰呼び出しを省略
反復数が劇的に減少
10
4
5
7
9
閉包・極大性判定
（新規）
・閉包の計算や、極大性の判定を素直に行うと、
データベース縮約を用いない頻出度計算と、
同程度、あるいはそれ以上の手間がかかる
・閉包・極大性判定にもデータベース縮約を使う
－閉包末尾以後が等しいトランザクションを１つにまとめる
ただし、閉包末尾以前は以下を保存
・閉包計算
⇒ 共通部分
・極大性判定 ⇒ 各アイテムの含まれる数
頻出度計算と同程度、データベースが縮小される
計算機実験
・計算機環境：
CPU、メモリ: AMD Athron XP 1600+ 、 224MB
OS、言語、コンパイラ: Linux 、C言語、gcc
・比較アルゴリズム
FP-growth, afopt, MAFIA, PATRICIAMINE, kDCI
（どれも、実装コンテスト FIMI03 で優秀な成績をおさめたもの）
・データセット
FIMI03、KDD-cupなどで使われた、人工データ、実データ
結果
観察と考察
・ prefix保存飽和拡張・超立方体分解は、同値類が大きいと効果的
・極大性の判定は、他のアルゴリズムも優秀
・データベースの縮小は
αが大きいとき＆ Occ(K) が大きいとき、とても良く効くようだ
・ apriori はそれほど効果がないようだ
・オカレンス配布は、α、Occ(K) が小さいとき、効くようだ
・逆に FP-treeは、α、Occ(K) が大きいとき、効くようだ
我々のアルゴリズムは、構造があり、解が多い場合に強い
まとめと今後の課題
・ prefix保存飽和拡張と、それを用いた、線形時間・多項
式メモリの飽和集合列挙アルゴリズムLCM を提案した
・ LCMをもとに、同値類のグループ化と枝狩りを用いて頻
出・極大集合の列挙アルゴリズムを構築した
・計算を高速化するアルゴリズムを提案した
・多くの問題において既存手法より良い結果を出した
・ FP-tree 的な手法を加味した、さらなる高速化が課題
FIMI '03
・ Frequent Itemset Mining Interpretation
頻出集合列挙アルゴリズムの実装コンテスト
・ 20ほどのアルゴリズムが参加した
（我々も参加）
他のアルゴリズムの特徴
・基本は、頻出集合列挙。apriori が主流
・がんばった人は FP-treeを使用
・前処理によるデータベースの縮小がさかん
(long の代わりに short を使い、キャッシュ効率を良くする、
という重箱隅的なものまである）
・極大頻出集合列挙には、限定操作を多用
・ diffset はよく使われるが、オカレンス配布は使ってないようだ
これらを丁寧にじっくり実装したアルゴリズムが高速
奇抜なアイディアもあったが、全部遅い
実験に使われたデータベース
－ web log
－ POS
－機械学習用の問題
－事故処理のデータ
－リテール
－人工データ
・問題規模は大きく、項目数は 1万-100万
台集合の大きさも500-5万

Download Report