Document

頻出集合列挙アルゴリズムに対する
実用的高速化技術について
宇野毅明
浅井達哉
有村博紀
内田雄三
国立情報学研究所
九州大学
九州大学
九州大学
2004年 3月19日アルゴリズム研究会
本日の発表内容
頻出集合列挙アルゴリズムに対する
「実用的な高速化を行う技法」の議論をする
・既存の頻出集合列挙アルゴリズムの技術
・ Closed itemset の線形列挙と
同値類を用いた頻出集合の列挙
・実装コンテストFIMI'03での結果を紹介
・結果から、高速化に必要な技術を考察
今日は報告と考察がメインです
トランザクションデータベース
トランザクションデータベース：各項目 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 のオカレンス集合T(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 の定数α個以上の項目に含まれる集合
（オカレンス集合のサイズがα以上の集合）
極大頻出集合：他の頻出集合に含まれない頻出集合
例）このデータベースの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}
Closed itemset
・頻出集合をオカレンス集合が等しいもので
グループにわける（これを同値類と見なす）
・ closed itemset：グループの中の極大元
オカレンス集合の共通部分
⇒ ユニークに定まる
・オカレンス集合の共通部分
を閉包という
極大頻出集合
closed itemset
バックトラック法（既存研究）
・空集合から出発し、分枝限定法的に探索するアルゴリズム
・現在の解に、１つ要素を加えた各解に対し、再帰呼び出し
・重複を避けるため、現在の解の要素より大きな要素のみ追加
Backtrack (X)
1 Output X
2 For each e > Xの最大の要素
If X∪{e}が頻出 call Backtrack (X∪{e})
O( 頻出度のチェック時間×|E| )
オカレンス集合の計算（既存研究）
・集合 X∪{e} のオカレンス計算は、素直に行うと、データベース
の全ての項目を調べる
・ T( X∪{e} ) ⊆ T(X)
⇒ X のオカレンスで e を含むものを見つければよい
Occurrence (X, e)
1 For each T ∈ T(X)
If T が e を含む output T
O( |T(X)| ) 時間
有利な方法で計算しよう（既存研究）
・集合 Y={1,2,3,4,5} のオカレンス計算は、
－{1,2,3,4 } のオカレンスで 5 を含むもの
－{1,2,3, 5} のオカレンスで 4 を含むもの
－{1,2, 4,5} のオカレンスで 3 を含むもの
－{1, 3,4,5} のオカレンスで 2 を含むもの
－{ 2,3,4,5} のオカレンスで 1 を含むもの
どの方法で計算しても良い
（バックトラックの場合は一通りしかできないが．．．）
・オカレンス集合が小さいものを使うと高速
・そもそも、これらの中に非頻出なものがあれば「Yは非頻出」
各レベルを順に計算（apriori）（既存研究）
・最初に大きさ1の頻出集合を全て見つけ、メモリに蓄える
・次に大きさ2の頻出集合を全て見つけ、メモリに蓄える
・以後１つずつ大きさを増やす
・大きさ k の頻出集合は、大きさ k-1 の頻出集合に要素を１つ
加えたもの
⇒ 大きさ k-1 の頻出集合に各要素を加えて、候補を作る
・このとき、オカレンス計算が有利な作り方選ぶ
メリット：
オカレンス計算の高速化
デメリット：メモリを大量消費＆既発見解検索時間の増加
検索用のデータ構造（既存研究）
FP-tree：今までに発見した頻出集合を蓄えるデータ構造
Suffix tree、trie とよばれるものと同じ
・ FP-treeは入力したデータベースを保管するのにも使われる
（同一項目の縮約などの操作が楽なため）
1
／｜＼
2 3 5
｜｜
4 5
｜
5
2
／｜＼
2 3 4
／｜
4 5
｜
5
3
｜
5
4 5
｜
5
オカレンスの配布（既存研究？）
X = {1,2}
Xのオカレンス
A{1,2,3,4} B{1,2,5}
C{1,2,4,5}
・ X = {1,2,3}, {1,2,4}, {1,2,5}
のオカレンス集合を求めたい
Occ[3]: A
Occ[4]: A C
Occ[5]: B C
O( T(X∪e) )時間
diffset（既存研究）
・ T(X) と T(X∪{e}) がそれほど異ならない場合
T(X)＼T(X∪{e}) が計算できれば、オカレンス計算は速い
T(X) :
Occ[3]:
Occ[4]:
Occ[5]:
Hybrid
（新規）
・ diffset を使うと高速になるかどうかは、状況しだい
⇒ diffset とオカレンス配布の計算時間を見積もり、
有利なほうを選択する
・ある反復でdiffset が有利なら、子孫では必ずdiffset が有利
⇒ 切り替えは「通常」－> 「diffset」のみを考えればよい
オカレンス計算のまとめ（既存＆新規）
・ X∪{e} のオカレンス集合を計算するのにかかる時間
工夫無し： O（データベースサイズ）
工夫あり： O（|T(X)| ）
apriori： O（ 1つ小さい部分集合の最小オカレンス集合サイズ
＋検索時間、非頻出の場合は、検索時間のみ）
オカレンス配布： O（ |T(X∪{e})| ）
diffset： O（ |T(X)＼T(X∪{e})| ) ）
hybrid： O（ min{ オカレンス配布, diffset ）
・ Apriori とオカレンス配布が競合
・ diffset は問題によっては速い
実際の計算では（新規）
・ X∪{e}のオカレンス集合のサイズの合計を比べる
頻出のもの全部：非頻出のもの全部＝２～３：１
（ただし、要素を「含まれる項目数」の小さい順でソート）
X∪
3
4
5
6
7
8
9
α
AD
ELM
ABCEFGH JKLN
ABDEFGI JKLMSTW
BEGILT
MTW
ABCDFGH IKLMNST
検索の手間がない分
オカレンス配布が
有利と思われる
データベースの縮小（既存研究）
・ αが大きければ、データベースを小さくして計算時間を短縮
できる
◆ e を含む項目がα個未満
⇒ e をデータベースから削除
◆ 等しい項目は１つにまとめる
・ 10分の1程度になることもある
極大＆closeditemsetの列挙（既存研究）
・頻出集合列挙のバックトラックアルゴリズムやapriori に
限定操作を加える
限定操作：
１つ極大解が見つかったら、その部分集合は極大解
(closed itemset)の候補からはずす
・ aoriori タイプのアルゴリズムだと簡単に実装できる
・その場合、1レベルごとの計算は行わない
極大2部クリーク列挙
・ closed itemset の列挙は極大2部クリークの列挙と等価
・入力したデータベース T に対してあるグラフ G を作ると、
そのグラフの極大2部クリークとclosed itemset が対応
・クリーク列挙のアルゴリズムでclosed itemset が列挙できる
－築山 et.al. '77
－宇野 '03
O( 頂点数×枝数 ) 時間
O( 最大次数 3 ) 時間
逆探索
・ closed itemset 上に、非巡回的な親子関係を定義する
（各closed itemset に親を定義する）
・非巡回的なので、親子関係は木を導出する（列挙木）
列挙木を深さ優先探索して全ての解を出力する
・子供を見つけるアルゴリズムがあれば十分
closed itemset の親
・集合 K の閉包： K を含む項目の共通部分
⇒ K が属する同値類の極大元であるclosed itemset
・ closed itemset K の親添え字 i(K) ：
K∩{1,…,i} の閉包が K であるような最小のi
・ closed itemset K の親
K∩{1,…,i(K)-1} の閉包
1,2,6,7,8,9
2,5,8
例） {2,7,8,9} の親添え字： 7
1,2,6,7,8,9
T
＝
{2,7,8,9} の親： {2,8}
1,7,9
2,7,8,9
・ φ 以外には必ず親が存在
2,8
・親はサイズが真に小さいので非巡回的
closed itemset の子
K の子供を求めるには、親を求める作業の逆をすればよい
・ K[i] ：K∪iの閉包。ただし i > i(K)
・K'= K[i] ＆ K[i]とK の i 以下の部分が等しい
⇔ K' はK の子供
1,2,4,6,7,8,9
2,4,5,8
例） {2,4,7,8,9} の親添え字： 7
1,2,4,6,7,8,9
T
＝
{2,4,7,8,9} の親： {2,4,8}
1,7,9
2,4,7,8,9
2,4,8
・ K[i] は親を求める操作の逆
・ i > i(K) でなければ i(K')≠i
・K[i]とK の i 以下の部分が異なると、K' の親はK でない
全ての子供を見つける
・K の全ての子供を求める
⇒ 全ての i > i(K) に対して K[i]（K∪iの閉包）を計算
1 オカレンス配布で、各K[i] のオカレンス集合を計算
2 各K[i] のオカレンス集合の共通部分で、
Kに含まれないものがあるかどうかチェック
3 Kに含まれないものがなければ、K の子供
closed itemset １つあたり多項式時間
出力線形アルゴリズム
子供を見つける計算時間
1 オカレンス配布で、各K[i] のオカレンス集合を計算
⇒ 各々 O（ |T(K[i])| ）時間
2 各K[i] のオカレンス集合の共通部分で、
Kに含まれないものがあるかどうかチェック
⇒ 最小サイズのK[i]のオカレンスT*の各要素 e について
全てのK[i]のオカレンスに含まれるか調べる
⇒ O（ |T*＼K|×|T(K[i])| ）時間
（含まないものが１つでも見つかればその時点で終了。
実際はO（ |T(K[i])| ）より小さい）
・隣接行列を用いるとチェックが速い
（メモリ節約のため、大きなサイズの項目に対してのみ行を構築）
全ての子供を見つける
K の全ての子供を求める
⇒ 全ての i > i(K) に対して K[i]（K∪iの閉包）を計算
1 オカレンス配布で、各K[i] のオカレンス集合を計算
2 各K[i] のオカレンス集合の共通部分で、
Kに含まれないものがあるかどうかチェック
3 Kに含まれないものがなければ、K の子供
・ 2 のチェックは最小サイズのオカレンスに含まれるものだけでよい
・隣接行列を用いるとチェックが速い
（メモリ節約のため、大きなサイズの項目に対してのみ行を構築）
極大頻出集合の列挙
・極大頻出集合ならばclosed itemset
⇒ closed itemset を列挙して、極大性をチェックする
・オカレンス配布、あるいは diffset で、
簡単に判定できる
頻出集合の列挙
・頻出集合列挙のボトルネックは、オカレンス計算
・ closed itemset の同値類内は、オカレンス集合が等しい
⇒ オカレンス計算が省略できる
・閉包を取らない解と閉包を取った解を保持
⇒ 両者は、同値類中の超立方体を導出
・全ての組
⇒ 全ての同値類を超立方体に分割
FIMI '03
・ Frequent Itemset Mining Interpretation
頻出集合列挙アルゴリズムの実装コンテスト
・ 20ほどのアルゴリズムが参加した
（我々も参加）
・この結果を簡単に解説
他のアルゴリズムの特徴
・基本は、頻出集合列挙。apriori が主流
・がんばった人は FP-treeを使用
・前処理によるデータベースの縮小がさかん
(long の代わりに short を使い、キャッシュ効率を良くする、
という重箱隅的なものまである）
・極大頻出集合列挙には、限定操作を多用
・ diffset はよく使われるが、オカレンス配布は使ってないようだ
これらを丁寧にじっくり実装したアルゴリズムが高速
奇抜なアイディアもあったが、全部遅い
使用技術の比較
・他のアルゴリズム
－apriori
－diffset
－データベースの縮小
－FP-tree
・我々のアルゴリズム
－closed itemset の
出力線形時間列挙
－オカレンス配布
－diffset と hybrid
－rightmost sweep
－hypercube decomposition
実験に使われたデータベース
－ web log
－ POS
－機械学習用の問題
－事故処理のデータ
－リテール
－人工データ
・問題規模は大きく、項目数は 1万-100万
台集合の大きさも500-5万
問題の分類
・計算にかかる手間は
－オカレンス集合の大きさ（αの大きさ）
－ closed itemset の同値類の大きさ
に依存するだろう
T(X)小
同値類 Weblog
・これらで問題を分類
大きいリテール
それぞれのカテゴリで
アルゴリズムの効率を比較
T(X)大
機械学習
データ
同値類 POS
事故処理
小さい人工データ
データ
結果
頻出集合
closed itemset
極大頻出集合
T(X)小
T(X)大
α小
α小
α大
α大
同値類大我々我々我々
両方
同値類小両方他
他
他
T(X)小
T(X)大
α小
α小
α大
同値類大我々他
他
他
同値類小他
他
他
α大
他
観察と考察
・出力線形アルゴリズム＆hypercuve decomposition は
closed itemset の同値類が大きいと効率良いようだ
・データベースの縮小は
αが大きいとき＆ T(X) が大きいとき、とても良く効くようだ
・ apriori、FP-treeはそれほど効果がないようだ
・オカレンス配布＆rightmost sweep は、
αが小さいとき＆ T(X) が小さいとき、効くようだ
・ αが大きいとき＆ T(X) が大きいときは、hybrid が効くようだ
我々のアルゴリズムは、
構造があり、解が多い場合に強い

Download Report