頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
List decoding for Reed-Muller codes and its application to polar codes 安永 憲司 東京工業大学 大学院情報理工学研究科 数理・計算科学専攻 1.
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
いいプログラムは コーディング技術だけではない
極小集合被覆を列挙する 実用的高速アルゴリズム
ラベル付き区間グラフを列挙するBDDとその応用
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
A: Attack the Moles 原案:高橋 / 解説:保坂.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
On the Enumeration of Colored Trees
頻出集合列挙アルゴリズムに対する 実用的高速化技術について
An Algorithm for Enumerating Maximal Matchings of a Graph
Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム
列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.
Paper from PVLDB vol.7 (To appear in VLDB 2014)
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
9.NP完全問題とNP困難問題.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
宇野 毅明 国立情報学研究所 2002年3月 東北大大学院 情報科学研究科ワークショップ
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
疑似頻出アイテム集合の 多項式遅延列挙アルゴリズム
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
クリークマイニングとその応用 ~ 大規模データの活用 ~
最短路問題のための LMS(Levelwise Mesh Sparsification)
頻出パターン発見アルゴリズム入門 - アイテム集合からグラフまで - Part 1
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
第6章 連立方程式モデル ー 計量経済学 ー.
型付きアセンブリ言語を用いた安全なカーネル拡張
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
近年の列挙技術の進展 ー 計画立案と解法 ー 宇野 毅明 (情報学研究所) 有村 博紀 (北海道大学) 中野 眞一 (群馬大学)
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
実行時情報に基づく OSカーネルのコンフィグ最小化
トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
頻出集合発見問題に対する アルゴリズム技術
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
A Simple Algorithm for Generating Unordered Rooted Trees
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
GPGPUによる 飽和高価値 アイテム集合マイニング
プログラミング 4 整列アルゴリズム.
不確実データベースからの 負の相関ルールの抽出
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング 4 木構造とヒープ.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.
情報経済システム論:第13回 担当教員 黒田敏史 2019/5/7 情報経済システム論.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
重み付き投票ゲームにおける 投票力指数の計算の高速化
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発
構造的類似性を持つ半構造化文書における頻度分析
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
大規模データ処理に対する 列挙アルゴリズムの活用
擬似クリークを列挙する 多項式時間遅延アルゴリズム
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
情報処理Ⅱ 小テスト 2005年2月1日(火).
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
1 ひとりにしてくれ数 東北大学 大学院情報科学研究科 ◎鈴木 顕 内澤 啓 国立情報学研究所 情報学プリンシプル研究系 宇野 毅明.
Presentation transcript:

頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装 宇野 毅明 清見 礼 有村 博紀 国立情報学研究所 北海道大学 2004年 9月30日 データマイニングワークショップ

トランザクションデータベース トランザクションデータベース: 各トランザクション T がアイテム集合 E の部分集合になっているようなデータベース  つまり、 T , ∀T ∈T , T ⊆ E ・ POSデータ(各項目が、客1人の購入品目) ・ アンケートのデータ(1人がチェックした項目) ・ web log (1人が1回のwebサーフィンで見たページ) ・ オプション装備 (車購入時に1人が選んだオプション) 1,2,5,6,7 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T = 実際のデータは、疎であり大きいものが多い

集合K に対して: K のオカレンス: K を含むT の項目 K のオカレンス集合 Occ(K): K を含むT の項目全ての集合 集合のオカレンス 集合K に対して: K のオカレンス:  K を含むT の項目 K のオカレンス集合 Occ(K):  K を含むT の項目全ての集合 1,2,5,6,7,9 2,3,4,5 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 の定数α個以上のトランザクションに含まれる集合 (オカレンス集合のサイズがα以上の集合)(α:最小サポート)  (オカレンス集合のサイズがα以上の集合)(α:最小サポート) 極大頻出集合:他の頻出集合に含まれない頻出集合 例) データベースT の3つ以上のトランザクションに含まれる集合 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 3つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {2,7,9} T =

飽和集合 ・ 頻出集合をオカレンス集合が等しいものでグループにわける (これを同値類と見なす) ・ 飽和集合: グループの中の極大元 ・ 頻出集合をオカレンス集合が等しいものでグループにわける     (これを同値類と見なす) ・ 飽和集合: グループの中の極大元   (= オカレンス集合の共通部分)  ⇒ ユニークに定まる ・ アイテム集合に対して、 そのオカレンス集合の 共通部分を閉包という 極大頻出集合 頻出飽和集合

問題 ・ 本発表で扱う問題: 与えられたデータベース T と α に対して、その 1.頻出集合を全て見つける 2.頻出飽和集合を全て見つける   1.頻出集合を全て見つける   2.頻出飽和集合を全て見つける   3.極大頻出集合を全て見つける ・それぞれ多くの研究がある ・実装の研究も多くある これらの問題に対して、アルゴリズム LCM (Linear time Closed itemset Miner)を提案

各レベルを順に計算(apriori) (既存) ・ 最初に大きさ1の頻出集合を全て見つけ、メモリに蓄える ・ 次に大きさ2の頻出集合を、大きさ1の頻出集合を組合せて全て見つけ、メモリに蓄える ・ 以後、1つずつ大きさを増やす メリット:   オカレンス計算の高速化 デメリット: メモリを大量消費&既発見解検索時間の増加

バックトラック法 (既存) ・ 空集合から出発し、分枝限定法的に探索するアルゴリズム バックトラック法 (既存) ・ 空集合から出発し、分枝限定法的に探索するアルゴリズム ・ 現在の解に、1つアイテムを加えた各解に対し、再帰呼び出し ・ 重複を避けるため、現在の解の末尾より大きなアイテムのみ追加 Backtrack (K) 1 Output K 2 For each e > K の末尾( K の最大のアイテム) If K ∪{e}が頻出 call Backtrack (K ∪{e}) 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 1,4 2,3 2,4 3,4 1 2 3 4 φ 計算時間 = O( 頻出度のチェック時間×|E| )

頻出度計算 (既存) ・ 集合 K∪{e} のオカレンスを求める際、素直に行うと、 データベースの全ての項目を調べる必要がある 頻出度計算 (既存) ・ 集合 K∪{e} のオカレンスを求める際、素直に行うと、    データベースの全ての項目を調べる必要がある ・ Occ( K∪{e} )  ⊆  Occ(K) という性質を用いる  ⇒ K のオカレンスで e を含むものを見つければよい ⇒ Occ(K) ∩ Occ({e}) を計算すればよい (ダウン・プロジェクト、という) O( | Occ(K)| + | Occ({e})|) 時間

検索用のデータ構造 (既存) FP-tree: 今までに発見した頻出集合を蓄えるデータ構造 検索用のデータ構造 (既存) FP-tree: 今までに発見した頻出集合を蓄えるデータ構造 prefix tree、trie とよばれるものと同じ ・ FP-treeは入力したデータベースを保管するのにも使われる (同一項目の縮約などの操作が楽なため) ・圧縮したprefixの分だけ、 頻出度の計算が速くなる ・圧縮率は通常1/2-1/3倍、 最良でも1/6倍程度 ・2分木操作のため、 計算時間は増大  1 2 3 4 5 /|\ /|\   |  | 2 3 5 2 3 4 5 5 || /|    4 5 4 5 | |    5 5

各 e について O( |Occ(K∪{e}|) ) 時間 オカレンスの配布 (新規) ・各 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} のオカレンス集合を計算  ⇒ 疎な行列の転置を求めているのと同じ  ⇒ 非ゼロ要素数の線形時間で求められる 3 4 5 A B C 4 5 3 A B C 1,2,3 1,2,4 1,2,5 B C A 各 e について O( |Occ(K∪{e}|) ) 時間

実際の計算では (新規) ・ 頻出度計算では、生成した集合 K∪{e} が非頻出なら、 実際の計算では (新規) ・ 頻出度計算では、生成した集合 K∪{e} が非頻出なら、 それは無駄な計算 (うまくすれば省略できる可能性がある) ・ しかし、そのような無駄は、計算全体の1/3 以下    (ただし、アイテムを「含まれる項目数」の小さい順でソート) K∪ α 3 4 5 6 7 8 9 AD ELM ABCEFGH JKLN ABDEFGI JKLMSTW BEGILT MTW ABCDFGH IKLMNST 検索の手間がない分 オカレンス配布が 有利と思われる

データベースの縮小 (既存&新規) ・ 入力したデータべースを縮小して、計算を高速化する ◆ e を含むトランザクションがα個未満 データベースの縮小 (既存&新規) ・ 入力したデータべースを縮小して、計算を高速化する     ◆ e を含むトランザクションがα個未満        or 全てのトランザクションに含まれる         ⇒ e をデータベースから削除     ◆ 等しいトランザクションは1つにまとめる ・サポートが大きいと劇的に小さくなる(データベース縮約とよぶ) さらに、バックトラック法なら、各反復で      ◆ 末尾以前のアイテムを消去 してからデータベース縮約をすると、反復的に縮約され、 さらなる高速化が行われる(反復型データベース縮約とよぶ)

極大&飽和頻出集合の列挙 (既存) ・ 頻出集合列挙のアルゴリズムに限定操作を加える 極大用、限定操作: 1つ極大解が見つかったら、 極大&飽和頻出集合の列挙 (既存) ・ 頻出集合列挙のアルゴリズムに限定操作を加える 極大用、限定操作: 1つ極大解が見つかったら、          その部分集合は極大解の候補からはずす 飽和用、限定操作: 同一のオカレンス集合を持つ集合の中で、          極大でないものを候補からはずす ・ メモリに解を保持して実装する

飽和拡張 (既存) ・ 飽和集合 K に対して、 K の飽和拡張 = (K + アイテム) の閉包 飽和拡張  (既存) ・ 飽和集合 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 1,2,7,8,9 1,7,9 2,7,9 2 1,7,9 T = 2,5 2,7,9 1,2,7,9 2,3,4,5 飽和拡張 prefix保存飽和拡張 1,2,7,8,9 1,2,5,6,7,9

頻出集合の列挙 ・ 頻出集合列挙のボトルネックは、頻出度計算 ・ 同値類内は、オカレンス集合が等しい ⇒ 頻出度計算が省略できる  ⇒ 頻出度計算が省略できる ・ 閉包を取らない解と閉包を取った解を保持  ⇒ 両者は、同値類中の超立方体を導出  ⇒ 超立方体内の解を列挙 同値類が大きければ効率が良い

極大頻出集合の列挙 (新規) ・ バックトラック法による頻出集合列挙を考える K : 現在の解 ⇒ H: K を含む閉包 ⇒ 極大頻出集合の列挙 (新規) ・ バックトラック法による頻出集合列挙を考える K : 現在の解   ⇒ H: K を含む閉包 ⇒ ・ H に含まれるアイテムが 最後に来るよう、並び替える ・ H のアイテムを追加した再帰呼び出しでは、 極大頻出集合は見つからない   ⇒ 再帰呼び出しを省略 1 2 3 4 5 6 7 8 9 10 並び替え 6 8 10 4 5 7 9 反復数が劇的に減少

閉包・極大性判定 (新規) ・ 閉包の計算や、極大性の判定を素直に行うと、 データベース縮約を用いない頻出度計算と、 閉包・極大性判定 (新規) ・ 閉包の計算や、極大性の判定を素直に行うと、 データベース縮約を用いない頻出度計算と、 同程度、あるいはそれ以上の手間がかかる ・ 閉包・極大性判定にもデータベース縮約を使う  -閉包末尾以後が等しいトランザクションを1つにまとめる   ただし、閉包末尾以前は以下を保存      ・ 閉包計算    ⇒ 共通部分      ・ 極大性判定  ⇒ 各アイテムの含まれる数 頻出度計算と同程度、データベースが縮小される

計算機実験 ・ 計算機環境: 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) が大きいとき、効くようだ 大きいサポート、疎なデータベースでは全勝。Closed でほぼ全勝。 all,maximal + 小さなサポート、密なデータベースで半々。 我々のアルゴリズムは、構造があり、解が多い場合に強い

まとめと今後の課題 ・ prefix保存飽和拡張と、それを用いた、線形時間・多項 式メモリの飽和集合列挙アルゴリズムLCM を提案した ・ 計算を高速化するアルゴリズムを提案した ・ 多くの問題において既存手法より良い結果を出した ・ FP-tree 的な手法を加味した、さらなる高速化が課題

FIMI '03 ・ Frequent Itemset Mining Interpretation 頻出集合列挙アルゴリズムの実装コンテスト   頻出集合列挙アルゴリズムの実装コンテスト ・ 20ほどのアルゴリズムが参加した    (我々も参加)

他のアルゴリズムの特徴 ・ 基本は、頻出集合列挙。apriori が主流 ・ がんばった人は FP-treeを使用 ・ 前処理によるデータベースの縮小がさかん  (long の代わりに short を使い、キャッシュ効率を良くする、   という重箱隅的なものまである) ・ 極大頻出集合列挙には、限定操作を多用 ・ diffset はよく使われるが、オカレンス配布は使ってないようだ これらを丁寧にじっくり実装したアルゴリズムが高速 奇抜なアイディアもあったが、全部遅い

実験に使われたデータベース - web log - POS - 機械学習用の問題 - 事故処理のデータ - リテール - 人工データ ・ 問題規模は大きく、項目数は 1万-100万    台集合の大きさも500-5万