頻出パターン発見アルゴリズム入門 － アイテム集合からグラフまで － Part 1

Presentation on theme: "頻出パターン発見アルゴリズム入門 － アイテム集合からグラフまで － Part 1"— Presentation transcript:

1 頻出パターン発見アルゴリズム入門 － アイテム集合からグラフまで － Part 1
宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2008年6月13日 人工知能学会

2 列挙（マイニング）の利用と難しさ

3 列挙 ≠ マイニング  完全性の保証が必要 多くの場合暗に完全性を要求している － 全探索を効率化 － 解候補を簡単に生成
列挙 ≠ マイニング ・ 「マイニング」「発見」は、解を見つける手法の総称 ・ 「列挙」は、全ての解を重複無く見つける手法の総称 　 完全性の保証が必要　 ・ マイニングでは、完全性を問わないこともあるが、 　　多くの場合暗に完全性を要求している ・ 列挙的なアプローチでは、 　－ 全探索を効率化 　－ 解候補を簡単に生成 　－ 候補から良い解を選んで、最適性を保証 　－ 全体像の把握、個別の解のランキング

4 列挙の利用法 ・ 列挙は解を全て見つける  最適化してベストを見つける － 最適解がどの程度「最適」なのか、最適解からはわからない
・ 列挙は解を全て見つける  最適化してベストを見つける 　－ 最適解がどの程度「最適」なのか、最適解からはわからない 　　 列挙なら、良い解の分布が分かる 　－ 目的関数が真の目的に合致していると限らない場合、 　　　　　解候補を列挙して真の目的で再評価 　－ 目的関数の評価が大変な場合、直接的な探索が難しい場合も、部分条件を満たす解を列挙して真の目的で再評価 　－ 解の完全性を利用して、データの評価値として利用

5 列挙の難しさ ・ 列挙アルゴリズムを設計するときには、いくつかの難しさがある － 計算を速くする難しさ （計算アルゴリズム）
　－　計算を速くする難しさ　（計算アルゴリズム） 　－　全てを見つける難しさ　（探索経路構築） 　－　重複を回避する難しさ （逆探索） 　－　同型なものを同一視する難しさ　（標準型 ） … しかし、実際はうまく解ける物も多い

6 探索の難しさ ・ 列挙の対象はたいてい、１つ見つけるのは簡単な物 ・ 今まで見つけた物が全ての解であるか、どのように調べる？
　－ 経路列挙で、今まで見つけた経路が全てか調べる？ ・ クリークやパス（経路）は、隣接性を持つ 　－ クリークは１つずつ付け足すと全てが得られる 　－ パスは再帰的な場合分けができ、空の問題のチェックが簡単 ・ しかし、こううまくいくものばかりではない。 　－ 極大な××、極小な○○ 　－ あの条件とこの条件とこの条件と．．． 　 互いに隣接していない、場合分けも難しい 頻出 111…1 000…0

7 重複を回避する難しさ ・ 探索はできるので、全て見つけることはできるとする
・ しかし、どうやって同じものを２度出さないようにするか、あるいは同じ探索を繰り返さないようにするかは、それほど自明でない ・ 簡単に回避するなら、解を全部メモリに保存すればよい 　 解が多くなるとメモリ効率が悪い 　 　動的にメモリを確保して解を保存するルーチンと、解を効率よく検索するルーチンが必要（ハッシュがあればいい） ・ 今の解を出力するか、あるいは探索を続けるか、過去の履歴を見ずに、解自体から計算できるようにすることが重要

8 計算の高速化 ・ 高速化は、通常のアルゴリズムに対するテクニックが有効 ・ 各反復の計算の高速化 － ２分木、ハッシュなどのデータ構造、
　－ ２分木、ハッシュなどのデータ構造、 　－ 隣接行列　 接続行列による疎性の利用 　－ よけいな処理を省いて、高速化  計算オーダー減少 　－ キャッシュ、コードの最適化 ・ 列挙の場合、解を少しずつ変更する操作が多いので、 　データを動的に管理する方法が有効 　　 各頂点の次数、重み和、頻出度など ・ 指数的に広がる再帰構造を使った高速化が特に有効

9 頻出集合・半構造のマイニングについて解説
　アルゴリズム理論の利点 ・ 大規模な計算には、アルゴリズム理論に基づいた技術が有効 　 アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を抑える 　 計算の結果は変化しない 100項目 2-3倍 100万項目 10000倍 データが巨大になるほど、アルゴリズム改良の加速率は上がる 本レクチャーでは、パターンマイニングアルゴリズムの設計手法を 頻出集合・半構造のマイニングについて解説

10 ３．頻出集合の列挙　（LCM）

11 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを全て見つける問題を 頻出パターン列挙（あるいは発見、マイニング）問題という
　データベース： トランザクション、ツリー、グラフ、多次元ベクトル 　パターン： 部分集合、木、パス・サイクル、グラフ、図形 データベース 頻出する パターンを抽出 ・ 実験1● ,実験3 ▲ ・ 実験2● ,実験4● ・ 実験2●, 実験3 ▲, 実験4● ・ 実験2▲ ,実験3 ▲ 　　　　． 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT ・ ATGCAT ・ CCCGGGTAA ・ GGCGTTA ・ ATAAGGG 　　　　． 実験結果 ゲノム情報

12 トランザクションデータベース トランザクションデータベース： 各トランザクション T がアイテム集合 E の部分集合
になっているようなデータベース、つまり、∀T ∈D, T ⊆ E 集合 P に対して： P の出現：　 P を含むD のトランザクション P の出現集合 Occ(P)： P の出現の集合 P の頻出度 frq( P)： P の出現集合の大きさ 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D ＝ 　{2,7,9}の出現集合 ＝　{ {1,2,5,6,7,9}, 　　　　{1,2,7,8,9}, {2,7,9} } 　{1,2}の出現集合 ＝　{ {1,2,5,6,7,9}, {1,2,7,8,9} }

13 頻出集合列挙は、与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題
・ 頻出集合： D の定数σ個以上のトランザクションに含まれる集合 　（頻出度がσ以上の集合）（ σを最小サポートとよぶ） 例） データベース D の3つ以上のトランザクションに含まれる集合 ３つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {1,7,9} {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 D ＝ 頻出集合列挙は、与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題

14 パターンマイニングの応用 基礎的な問題なので、応用に広がりがある 売上げデータの分析 項目の自動分類 画像認識 Webページのトピック分類
・雑誌とおにぎりが良く一緒に売れてます ・夜 訪れる男性は高めの弁当を買ってます ・さんま と 大根 と すだち は 　　 セット販売したらどうですか？ ・・・ 遺伝子Z： ●○★ ・・・ 遺伝子A： ●△▲ 遺伝子B： ●△▲ 遺伝子D： ●△▲ ・・・ 遺伝子F1： ■□ 遺伝子F2： ■□ ・・・ 画像認識 Webページのトピック分類 ・みかんとみかんでない画像を分ける 特徴を見つける ・ Webページを、リンクやキーワードの 組合せで、トピック毎に分類 全国 ラーメン 巡り カツカレー と私 ラーメン の旅人 カレーの 作り方 基礎的な問題なので、応用に広がりがある

15 空集合から出発して、山登り的に（重複を出 さないように）探索 （共通の基本アイディア）
頻出集合の単調性 ・ 工夫をするためには、何か問題の特徴をつかまなくてはいけない ・ 使えそうなのが、「頻出集合の部分集合は必ず頻出」、というもの（単調性という）  つまり、ハッセ図（包含関係を 図示したもの）の上では、 頻出集合が存在する エリアはつながっている 頻出 111…1 000…0 φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4 空集合から出発して、山登り的に（重複を出 さないように）探索 （共通の基本アイディア）

16 マイニングの技術の歴史 ・ いくつかのブレイクスルーがある 111…1 第１世代 apriori （幅優先）： ディスク上のデータ用
第２世代 　　深さ優先探索： データをメモリに保持 第３世代 　　データベースの圧縮： trie(FP-tree) などで再帰的に圧縮 第４世代？ 　　基数ソート、振り分け、および ppc拡張による飽和集合列挙 頻出 111…1 000…0

17 第１世代： apriori ・ 各レベルごとに頻出集合の候補（１つ下のレベルの頻出集合に１つアイテムを加えたもの）を生成し、それらの頻出度を計算 S0={φ}, k := 0 while Sk が空でない for each トランザクション Ti for each P∈Sk,P⊆Ti P の頻出度＋１ 頻出でない P を Sk から除去 for each P∈Sk 　 for each アイテム e 　　　P+e を Sk+1 に挿入 ・ P+e の部分集合で、Skに入っていないものがあれば頻出でない ・ １レベルにつき、ディスクのスキャンが一回ですむ ・ メモリ使用量と検索の手間がボトルネック φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4

18 第２世代： 深さ優先（バックトラック） ・ 空集合から出発し、頻出集合である限り再帰的にアイテムを追加
第２世代：　深さ優先（バックトラック） ・ 空集合から出発し、頻出集合である限り再帰的にアイテムを追加 Backtrack　(P, Occ(P) ) output P for each e > Pの末尾（ P の最大のアイテム） Occ(P∪e) = Occ(P) ∩ Occ(e) If P∪e が頻出集合 then call Backtrack　(P＋e) ダウンプロジェクト φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4 ・メモリにデータベースが全部 　　　乗らないと効率が悪い ・ 出現を更新していくところがポイント

19 第３世代： 再帰的データ圧縮（FP-tree）
・ データベースの縮約により、再帰の深いレベルでの高速化する （１） 前回追加したアイテムより小さいアイテムは消す （２） 現在の出現集合からできるデータベースの中で、頻出になっていないアイテムは消去する 　（再帰呼び出しの中で加えられることが無いから） （３） まったく同一のトランザクションは、１つにまとめる ・ 実データだと、下のほうのレベルではだいたい大きさが定数になる ・ FP-tree（trie）を使うと、共有する prefix も圧縮されるが、オーバーヘッドも大きい １ ３ ４ ５ ２ ６ ７ σが小さいときと速度の大きな差はない

20 ダウンプロジェクトや圧縮による末端の高速化が
末広がり性 ・ 再帰の末端以外はさほど高速化されていないのに、なぜ実際には大幅に高速化されるのか？ ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  反復の平均計算時間を支配するのは一番下の数レベル ・・・ 計算時間長 計算時間短 ダウンプロジェクトや圧縮による末端の高速化が 全体を高速化している

21 第４？世代： 振り分け・基数ソート・ppc拡張
・ trie を使ったデータの圧縮には nlogn の時間がかかる  基数ソートで、（ハッシュでの）オーバーヘッドなしに線形時間 ・ 疎な行列の転置を使って、追加するアイテムの出現を、いっぺんに線形時間で求める （振り分け） ・ ppc 拡張を用いて飽和集合を無駄なく列挙 １ ３ ４ ５ ２ ６ ７

22 振り分け for each P の各出現 T for each T に含まれる e, e > Pの末尾 eのバケツに T を挿入
・ 計算時間は, P の各出現の (Pの末尾) より大きなアイテムの数の総和 ・ 各アイテムに対する再帰呼び出しの 準備をいっぺんにすることで、 効率化している A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2

23 ・ Compute the denotations of P ∪{i} for all i’s at once,
振り分けの動画 ・ Compute the denotations of P ∪{i} for all i’s at once, A 1 2 5 6 7 9 B 3 4 C 8 D E F A A A A 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D＝ C C C D P = {1,7}

24 １反復の計算時間のイメージ ・ 普通に頻出度の計算をすると 各 P＋e に対してデータを 一回スキャンする ・ ダウンプロジェクトは n個
Occ(P) と Occ({e}) をスキャンする 　 Occ(P) を n-i 回スキャンし、 データベースの i より大きな アイテムをスキャンする ・ 振り分けは出現Occ(P) 中のトランザ クションの i より大きい部分をスキャンする n個 ＋ (n-i)個 i Occ(P) i

25 実データ （すかすか） 平均の大きさ5-10 BMS-WebView2 BMS-POS retail

26 実データ （すかすか） メモリ使用量 BMS-WebView2 retail BMS-POS

27 技術のまとめ 第１世代 apriori （幅優先） 111…1 ディスク上のデータ用のスキャン回数を最小化 データがメモリに乗らないとき速い
　データがメモリに乗らないとき速い 第２世代 深さ優先（バックトラック） 　出現の集合を保持するところがミソ データをメモリに入ると速い 第３世代　再帰的データ圧縮(FP-tree) 　末端の計算の高速化が全体を高速化 第４世代　基数ソート、振り分け、 ppc拡張 　検索技術からアルゴリズム技術へ 頻出 111…1 000…0

28 ３．２　飽和集合の列挙

29 頻出集合の問題点 ・ 面白い頻出集合を見つけようとすると、σを小さくする必要がある  大量の頻出集合が出てくる
 大量の頻出集合が出てくる ・ 情報を失わずに、頻出集合的な、数の少ないものを 　　　見つけるようにモデルを変えたい １． 極大頻出集合： 他の頻出集合に含まれない頻出集合 ２． 飽和集合： 出現集合が等しいものの中で極大なもの 111…1 000…0

30 極大頻出集合と飽和集合の例 ・ 頻出集合を出現集合で分類 ３つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9}
{1} {2} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {1,7,9} {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 D＝ 頻出飽和集合 出現集合の共通部分が 飽和集合になる 極大頻出集合

31 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個
極大頻出集合と飽和集合 極大頻出集合 ・ 多項式時間で列挙できるかどうか、未解決 ・ クリークと同じように枝刈りをすると、高速に列挙できる ・ 数が少ないがσによる解のぶれが大きい 飽和集合 ・ 逆探索という探索手法で多項式時間列挙可能 ・ 離散アルゴリズムと末広がり性を用いて、高速列挙可能 ・ 出現の意味で情報の損失がない ・ ノイズが多いと出現集合が等しいものが少なくなり、 　　　解の減少効率が悪くなる 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個

32 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする
２部グラフによる表現 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする A: 1,2,5,6,7,9 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 A B C D E F P D＝ Occ(P) ・ アイテム集合と、それらを含むトランザクションの集合 　 ２部グラフの２部クリーク ・ アイテム集合とその出現集合 　 トランザクション側が極大な２部クリーク ・ 飽和集合とその出現集合　 極大２部クリーク ・ トランザクション集合の列挙へも（構造パターンにも適用可）

33 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする
隣接行列で見ると ・ アイテム、トランザクションを頂点とし、包含関係を枝とする A: 1,2,5,6,7,9 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 1 2 3 4 5 6 7 8 9 A B C D E F D＝ ・ アイテム集合と、それらを含むトランザクションの集合 　 全てのセルに1が入っている部分行列

34 飽和集合の列挙手法 第１世代 頻出集合列挙ベース － 頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く
第１世代 頻出集合列挙ベース 　－ 頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く 　－ 飽和集合のよさが出ない。計算時間の改善も少ない 第２世代 保存 ＋ 枝狩り　　 　－ 見つけた解を保存し、それを用いて無駄な分枝を刈る 　－ 計算速度はまあまあ 　－ 解保存のためにメモリを使用し、それがひとつのネック 第３世代 逆探索　＋　データベース縮約　　（LCM） 　　 － 計算効率が良い 　　 － 解保存用のメモリが不要

35 飽和集合の隣接関係 ・ 飽和集合から、添え字の大きい順に要素を抜いていく ・ どこかで出現集合が大きくなる
・ その出現集合の飽和集合を求める ・ こうして求めた飽和集合を、親とする　（一意的に定まる） ・ 親の頻出度は必ず真に大きいので、 親子関係は非巡回的 　 親子関係は有向根付き木を導出する

36 逆探索 親子関係は有向根付き木を導出する この木を深さ優先探索すれば全ての解を見つけられる
・ 探索には、子供を見つけるアルゴリズムがあれば十分 ・ 子供が１つあたり多項式時間で見つかれば、全体も多項式時間 （親に要素を１つ加えて極大をとった飽和集合が子供になる） 非巡回的な親子関係と、子供を見つける多項式時間アルゴリズムがあれば、なんでも多項式時間列挙ができる

37 ・ データベースの全ての 飽和集合とその親子関係
親子関係の例 ・ データベースの全ての 飽和集合とその親子関係 φ 1,7,9 2,7,9 1,2,7,9 7,9 2,5 2 2,3,4,5 1,2,7,8,9 1,2,5,6,7,9 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 出現集合が隣接 親子関係（ppc拡張）

38 （prefix preserving closure extension, prefix保存飽和拡張）
子どもを求める ・ 子どもから親を作る際に抜いた、最後のアイテムを親に追加すると、出現集合は子どもと等しくなる 　 子どもは、アイテムを１つ追加して、出現集合の共通部分をとると得られる 　 とはいえ、そのようにして作ったもの全てが子どもになるとは限らない 　 子どもである条件は、抜いたアイテムより前の部分に、新しくアイテムが追加されないこと （prefix preserving closure extension, prefix保存飽和拡張）

39 データベースの縮小 ・ 頻出集合と同じように、データベースの縮小をしたい ・ 追加したアイテムの前半部分を捨てられない
　 ppc 拡張の際に参照されるので ・ しかし、 　－後半が同一なら、必ず同時に Occ に入る 　－必要なのは前半（prefix）の共通部分だけ なので、前半の共通部分をとり、保存すればよい ・ 多くのトランザクションが1つになれば、 自然に共通部分も小さくなる １ ３ ４ ５ ２ ６ ７ θが小さいときと速度の大きな差はない

40 比較の手間 ・K+e の出現の共通部分、素直に計算してもよいが、「共通部分がKと等しいか」を調べるだけなので、必ずしも全て計算する必要はない
 異なることがわかった時点で、計算をやめてよい ・ K+e の出現それぞれを小さい順にたどり、 全てに共通するものがあるか調べる ・ 全てに共通するものがあったら K に入っているか調べる ・ 前回たどったところで止まって おき、次回はそこからたどる K 4 11 3 3 4 4 6 6 9 9 11 1 1 3 3 4 4 5 5 9 9 11 K+e の 出現集合 3 2 4 4 5 5 9 9 11 1 1 2 2 4 4 6 6 9 9 11 1 1 4 4 9 9 11

41 ビットマトリクス ・ スウィープポインタは、行列の形でデータを持ってないがゆえの工夫。隣接行列を持って入れば、もっと単純に速くできる
・が、隣接行列は、大きすぎて構築することすら不可能 ・ 出現集合がある程度以下に小さくなったところで、 　　　　行列を構築しよう 　  ビットで持てば、各列が1つの変数に入る！

42 ビットマトリクスの定数時間計算 ・ 各アイテムに対応する列を１変数で持っていると、K+e の出現全
てにそのアイテムが含まれるかどうか、1ステップでチェックできる ・ K+e の出現のビットパターンと、アイテム i の列のビットパターンの AND をとる ・アイテム i が K+e の出現全てに含まれるなら、共通部分はK+e の出現ビットパターンと等しくなる ・・・ K<i ∩N(vi) K の頂点

43 実データ （すかすか） 平均の大きさ5-10 BMS-WebView2 BMS-POS retail

44 実データ （すかすか） メモリ使用量 BMS-WebView2 retail BMS-POS

45 密（50%程度）で 構造があるデータ pumsb connect chess

46 密で構造があるデータ、メモリ量 pumsb connect chess

47 頻出集合発見の応用事例

48 応用： 他の頻出パターンマイニング ・ パターンマイニングは、基本的にパターン毎にプログラムを組み替える必要がある
・ もし、部分パターン列挙が可能であれば、各項目に含まれる部分パターンを列挙してしまうと、アイテム集合マイニングに帰着できる 例） 項目が高さ２以下の木であるデータから、 　　　　　　　高さ2以下の木のパターンを見つける 1 2 3 4 5 ・・・ {1, 2, 3, 4} グラフ、シークエンスの集合など 各項目が×××の集合

49 応用： 他の頻出パターンマイニング ・ 部分パターンがあまり多くない場合、例えばマルチセットのマイニングや各項目が複数のグラフや系列でできている場合など、パターンが構造の集合、という形をしているときに有効なテクニックである。 ・ 有向非閉路グラフから頻出有向グラフを見つけるアルゴリズム 有向 非閉路 グラフ ⊇ Alexandre Termier, Yoshinori Tamada, Seiya Imoto, Takashi Washio, Tomoyuki Higuchi, From Closed Tree Mining to Closed DAG Mining

50 応用： 遺伝子のクラスタリング ・ 多くの遺伝子は他の遺伝子と共起して機能する ・ 臓器などの部位、発達段階による時期などで、一緒に発現する
・ 共起しやすい遺伝子をグループ化すると、関係の深い遺伝子が分かるだろう ・ トランザクション 発現する場所（時）、　アイテム 遺伝子 とすると、頻出集合は、多くの場所で共通に発現する遺伝子のグループになる。（実際は飽和集合を見つけている） ・ 似通った物を消すため、25%の領域が他に含まれるものは消去 A: ● ● ● ● B: ● ● ● ● C: ● ● ● ● Y. Okada, W. Fujibuchi, P. Horton, Module Discovery in Gene Expression Data Using Closed Itemset Mining Algorithm

51 応用： 分類規則の発見 ・ パターンが含まれる項目の重みの合計を考えると、重み付きの頻出パターン発見ができる
　 含まれることが重要な項目を指定できる 　 頻出パターンの場合、項目の重みは全て１ ・ さらに負の重みを許すと、「含まれたくない項目」が表現できる  自動分類を行いたいデータに対して、正例の項目には正の重み、負例のデータには負の重みを与えると、分類規則に相当するアイテム集合が見つかる ・ 見つかるパターン数に対する計算時間は長くなるが、それでも実用の範囲内 正例（＋の重み） 負例（－の重み）

52 応用： 画像分類 ・ 自動分類の手法の一つに、各項目の特徴ベクトルと基準ベクトルの内積を取って、その値によって正例と負例に分類する方法がある
・ 基準ベクトルを最適化して、分類規則を学習する ・ 特徴ベクトルに使う特徴には、属性値をそのまま使うことが多いが、そこにアイテム集合を使うと可能性が広がる ・ 変数が多くなるので、列生成法を使って最適化する S. Nowozin, K. Tsuda, T. Uno, T. Kudo, G. Bakir Weighted Substructure Mining for Image Analysis

53 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする
２部グラフによる表現 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする A: 1,2,5,6,7,9 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 A B C D E F D＝ ・ アイテム集合と、それらを含むトランザクションの集合 　 ２部グラフの２部クリーク ・ アイテム集合とその出現集合 　 トランザクション側が極大な２部クリーク

54 応用： 複合語による単語の分類 ・ 単語を、複合語の作り方を 使ってグループに分類 関東 地方 ・ 単語が頂点、単語を組合せて 関西 地区
複合語ができるとき、枝を張る として2部グラフを作る ・ 極大2部クリークを見つけると、それが類義語、あるいは反対語など、関連する意味を持つ単語群になるだろう 関東 関西 中国 北陸 地方 地区 電力 中渡瀬秀一, 相澤彰子 完全N部グラフ構造を用いた単語の多義性獲得

55 応用： webコミュニティーの抽出 ・ web のリンク構造から、 2部クリークを見つけ出す －リンク元: 共通の趣味を持つページ
　　2部クリークを見つけ出す －リンク元: 共通の趣味を持つページ －リンク先: 同じカテゴリのページ ・ グラフから2部クリークを見つける には、グラフを2部グラフに変換 ホンダ カワサキ ヤマハ バイク好き 趣味バイク バイク万歳 バイク人生 サイト 隣接している頂点間に枝を張る グラフ 頂点 集合 頂点 集合

56 実装の参照先 ・ 宇野のHP （頻出集合の他の構造のマイニング、列挙や類似比較アルゴリズムの実装）
・ 実装、問題、論文のレポジトリ　（比較実験の数々も） ・ 羽室・森田による GUI 「IGVMiner」 （GUIによる操作と結果の可視化。情報大航海プロジェクトの成果物）

57 応用： その他 ・ ブログユーザ空間からの頻出なコミュニティ抽出法
・ Extracting generic basis of association rules from SAGE data ・ ローカルデータベースにおけるアイテム集合の相関の違いに基づく隠れた相関の発見 ・コンピュータゲームプレイヤの静的評価関数の自動生成に関する研究動向 ・駒位置と効き関係に注目した詰み評価関数の自動生成 ・Mining complex genotypic features for predicting HIV-1 drug resistance 　　　・・・

58 参考文献など ・ 頻出集合およびその応用 (’90～) 星の数ほど
・ 頻出集合およびその応用 (’90～)　　星の数ほど 　　 “frequent pattern”、”frequent itemset” で検索すると出てくる ・ 極大頻出集合およびその応用 (’90～)　　やはり多い 　　 “maximal frequent itemset” などで検索すると出てくる ・ pasquerらのアルゴリズム (‘99) 飽和集合の導入 ・ 宇野らのアルゴリズムLCM (‘04) 現在最速のアルゴリズム ・ 実装 LCM: (Linear time Closed itemset Miner) 宇野のHP ・ レポジトリ　（実装、論文、比較実験の数々） ・ 中野・宇野・有村 （’03～ ） 順序木・無順序木の多項式時間頻出列挙

59 前半のまとめ ・ 列挙アルゴリズムの難しさ： － 簡単な構造でも、いいかげんでは劇的に失敗 ・ 頻出集合マイニングと高速化の技法：
　－ 簡単な構造でも、いいかげんでは劇的に失敗 ・ 頻出集合マイニングと高速化の技法： 　－ １－４世代アルゴリズム 　－ 計算の局所性と、末端高速化による改良 ・ 頻出飽和集合と逆探索： 　－ 親子関係による探索路の構築 ・ 応用研究、実社会での利用： 　－ クラスタリング、分類、... 　－ 他のデータマイニングアルゴリズムでの利用 列挙的なモデルを使った研究や システムの開発が進むと嬉しいです