サブグラフ列挙と頻出パターンマイニング － データサイエンスで活躍する列挙アルゴリズム

Presentation on theme: "サブグラフ列挙と頻出パターンマイニング － データサイエンスで活躍する列挙アルゴリズム"— Presentation transcript:

1 サブグラフ列挙と頻出パターンマイニング － データサイエンスで活躍する列挙アルゴリズム
サブグラフ列挙と頻出パターンマイニング 　　　　　－　データサイエンスで活躍する列挙アルゴリズム 宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2008年9月2日 FIT

2 １．列挙の利用

3 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった （POS、web、文書、顧客データ、財務、利用者、人事…）
実用面：　データ中心の科学 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった （POS、web、文書、顧客データ、財務、利用者、人事…） 既存のデータを多角的な視点から解析し、何かを得たい 問題発見 定式化 求解 データの選別 モデル化 データ処理 いわば、データを出発点とした問題解決の科学 （人工知能、データマイニング、自然言語処理、セマンティックweb… 近年の情報学でもメジャーな研究スタイル） データ全体を調べるために、常に高速なデータ処理が課題

4 データ中心科学の特徴と列挙 不正確さやあいまい性を許容するモデルと計算が必要。また、
・ データが整形されていない：ノイズ、うそ、質・作成目的の違いがある 不正確さやあいまい性を許容するモデルと計算が必要。また、 ・ 評価値があいまい： 数理的に表現しにくい評価値、目的そのものが不明確 ・ データが巨大である：うそ、質・作成目的の違いがある ・ データが構造を持つ： べき乗則、局所的な密構造

5 データ中心科学でのアプローチ ・ データが整形されていない： ノイズ、うそ、質・作成目的の違いがある
　　－ データ収集の目的が、解析の目的と異なる 　　－ 半自動的に、多様な場面でデータを収集している 　 あいまいさを許容するモデルと計算が必須 ・ 評価値があいまい： 数理的に表現しにくい評価値、目的自体が不明確 　　－ 役に立つ、わかりやすい、面白いといった尺度 　 最適解がベストとは限らないため、良い解が多量に必要 ・ 巨大で構造を持つデータ： 100万項目、べき乗則、局所的な密構造 　 単純な問題を高速に解く必要がある 　 データの平均的な特徴を捉えた、平均的に高速な手法が重要 ・ 個々の場面で問題が変化： 　 共通する基礎的な問題を解くツールが、実用上・応用乗重要 　 個別の尺度を最適化するより、条件を満たす解の列挙

6 まとめると、「大規模で基礎的な問題に対する、 あいまいさを考慮した、高速な列挙アルゴリズムの開発」が重要
アプローチの変化 きれい非整形 列挙モデル あいまい計算 現実的高速計算 基礎的問題のツール 明確あいまい 個別対応 中規模大規模 まとめると、「大規模で基礎的な問題に対する、 あいまいさを考慮した、高速な列挙アルゴリズムの開発」が重要

7 列挙の利点 ・ 最適解がどの程度「最適」なのか、最適化ではわからない  列挙なら、いい解の分布が分かる
　　 列挙なら、いい解の分布が分かる ・ 確かでない目的関数を最適化しても、欲しいものは得られない 　　 良い解の列挙なら、多くの候補の中から最も良いものが選べる ・ 個別の問題の最適解は、他の問題でも良いとは限らない 　　 基本的な制約を満たす解の列挙なら、汎用性が高い ・ 最適化はシステムの極みを見せるのに対して、列挙は問題の構造すべてを知ることができ、解析や知らないものの発見に有利

8 列挙の応用 ・ 最適化の別解：　複数の目的を持つ最適化や、目的がはっきりしない、あるいはゆらぐような問題では、準最適解を候補として列挙して、次のプロセスで真の最適解を探す ・ データマイニング：　役に立ちそうなもの、特徴などが満たすべき制約を考え、それを満たす解を列挙する。多数の解の生成により見つけ損ないをなくす ・ 特徴量（カーネル）：　機械学習で使われる、構造をベクトルデータとして表す方法の一つに全ての部分構造を列挙、数を勘定するものがある。 ・ 探索、特にゲーム：　着手可能な手を、評価値が良さそうなものから順に列挙して手を読む ・ 証明、不具合がないことの確認：　列挙を完全に行うことで場合を尽くす。条件を設定することで、自明でない高速化を行う

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

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

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

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

13 アルゴリズム理論の利点 ・ 大規模な計算には、アルゴリズム理論に基づいた技術が有効
　アルゴリズム理論の利点 ・ 大規模な計算には、アルゴリズム理論に基づいた技術が有効 　 アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を抑える 　 計算の結果は変化しない 100項目 2-3倍 100万項目 10000倍 データが巨大になるほど、アルゴリズム改良の加速率は上がる

14 ２．頻出集合の列挙　（LCM）

15 頻出集合発見用のプログラム ・ 頻出集合発見は、データマイニングと呼ばれる最近興ったデータ解析の中でも基礎的な問題なので、プログラムが多く作られている ・ 入力データ、出力する解、どちらも大きいことが多いので、計算速度は非常に重要 ・ しかも、アルゴリズムの設計しだい で、パフォーマンスが大きく変わる ・ 国際プログラミングコンテスト でも、こんな感じ。ばらつき大きい （時間軸は対数） どういう高速化技法あるのか、見てみよう

16 データベースを分析したい ・ データベース構築と検索は、もうできるようになった （絞込みや、あいまい検索はまだ改良の余地があるけど）
　（絞込みや、あいまい検索はまだ改良の余地があるけど） ・ より詳しくデータを解析するために、データの特徴を捉えたい 各種統計量（データベースの大きさ、密度、項目に現れる属性値の総計、分布）よりも、深い解析がしたい  組合せ（パターン）的な構造に注目 （どういう組合せ（パターン）が どれくらい入っているか） ・ 組合せ・パターンの個数は指数なの で、全てを尽くすのは効率的でない  多く現れるものだけに注目 データベース 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT 実験結果 ゲノム情報

17 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを全て見つける問題を 頻出パターン列挙（あるいは発見、マイニング）問題という
　データベース： トランザクション、ツリー、グラフ、多次元ベクトル 　パターン： 部分集合、木、パス・サイクル、グラフ、図形 データベース 頻出する パターンを抽出 ・ 実験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 　　　　． 実験結果 ゲノム情報

18 頻出集合列挙は、与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題
トランザクションデータベース： 各トランザクション T がアイテム集合 E の部分集合 になっているようなデータベース、つまり、∀T ∈D, T ⊆ E ３つ以上に含まれるもの {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 ＝ 　{1,2}を含むトランザクション 　　＝　{ {1,2,5,6,7,9}, 　 　　 {1,2,7,8,9} } 頻出集合列挙は、与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題

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

20 頻出集合の単調性 ・ 工夫をするためには、何か問題の特徴をつかまなくてはいけない 111…1
・ 使えそうなのが、「頻出集合の部分集合は必ず頻出」、というもの（単調性という）  つまり、ハッセ図（包含関係を 図示したもの）の上で、頻出集合 は連結なエリアに存在 ・ 空集合から出発し、１つずつアイテム を加えることで、全ての頻出集合が作れる が、適当に作ると重複がでる 頻出 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

21 こういう探索方法をバックトラック法という
バックトラック法による探索 ・ そもそも重複が起こるのは、各頻出集合がいくつもの部分集合から「アイテムを１つ追加」として得られるのが原因 　（{1,2,3} には、{2,3}+1, {1,3}+2, {1,2}+3 の3通りある） ・ そこで、各頻出集合に対して、「作られ方」と1通りに制限する ・ 具体的には、「一番大きなアイテムを加えた場合のみ」とする 　（{1,2,3} は、{1,2}+3 という 　　作り方でしか作らない、 　　ということ） 探索ルートが木構造に 　　なるので、重複がなくなる φ 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 こういう探索方法をバックトラック法という

22 バックトラック法の計算時間 ・計算時間を算定してみる。擬似コードは Backtrack (K) 1 Output K
2 For each e > K の末尾（ K の最大のアイテム） If K ＋e が頻出集合 call Backtrack　(K＋e) －再帰呼び出しの回数は、 　　頻出集合の数と同じ －1呼び出し（反復と言う）の 　　計算時間は （n-K の末尾）×（頻出度計算時間） φ 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 O(|D|) 解の個数に線形の計算時間になった

23 各反復の高速化 ・ アイテム集合 X+e を含むトランザクションを見つけたい ・ X＋e を含めば X を含むので、X を含むトラン
ザクションだけを調べればよい（すでに計算済み） （検索で言うところの絞り込みと同じ）  データ全体を見る必要はない ・ さらに、追加するアイテム e を選ぶ際にも 「X を含むトランザクションに含まれるもの」 だけで十分 ・ ２つを合わせると、大幅な計算の省略ができる （一部だけの高速化に見えるが、全体を高速化できている

24 ほぼ全ての反復が短時間で終了  全体も速くなる
末広がり性 ・ 再帰呼び出しを繰り返すと、 Pの頻出度は小さくなる  振り分けの計算時間も短くなる ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル ・・・ 計算時間長 計算時間短 ほぼ全ての反復が短時間で終了  全体も速くなる

25 最小サポートが大きい場合も ・ σが大きいと、下のレベルでも多くの場所を見ることになる  末広がり性による高速化はいまひとつ
 末広がり性による高速化はいまひとつ ・ データベースの縮約により、下のレベルの高速化をはかる （１） 前回追加したアイテムより小さいアイテムは消す （２） 現在のデータベースの中で、頻出になっていないアイテムは消去する 　（再帰呼び出しの中で加えられることが無いから） （３） まったく同一のトランザクションは、１つにまとめる ・ 実データだと、下のほうのレベルでは 大きさがだいたい定数になる １ ３ ４ ５ ２ ６ ７ 頻出度が小さいときと同程度の速度

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

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

28 ３．頻出集合の応用事例

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

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

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

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

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

34 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする
２部グラフによる表現 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする 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＝ ・ アイテム集合と、それらを含むトランザクションの集合 　 ２部グラフの２部クリーク ・ アイテム集合とその出現集合 　 トランザクション側が極大な２部クリーク

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

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

37 実装の参照先 ・ 宇野のHP （頻出集合の他の構造のマイニング、列挙や類似比較アルゴリズムの実装）
・ 実装、問題、論文のレポジトリ　（比較実験の数々も） ・ 羽室・森田による GUI

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

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

40 ４．その他の実用的列挙

41 部分グラフ列挙問題 部分グラフ列挙： 与えられたグラフの（頂点誘導）部分グラフで、定められたグラフクラスに属する物を全て見つける
　－パス、サイクル、木、スター、クリーク、コーダルグラフ、インターバルグラフ、密部分グラフ、... 　－ラベル付き、重み付き、同型性の扱い、... ・ 応用でのモデルがグラフクラスに対応 ・ クラスによって、解の数、列挙の難しさが変わる ・ 頻出集合は、2部グラフの2部クリークに対応 グラフ

42 グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの
クリーク列挙問題 グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの ・ 2部クリークの列挙は、グラフの変換でクリーク列挙に帰着可能 ・ 最大クリークを求める問題はNP完全 ・ 極大クリークは簡単に求められる ・ 最適化を中心に非常に多くの研究がある ・ 大規模かつ疎なグラフでの、クラスタリングなどの応用が多い

43 単調性を利用して列挙 ・ クリークの部分集合はクリーク 111…1  単調性が成り立つので、山登り法（バックトラックで列挙可能）
・ 単純に作った手法では１つ O(n3) 時間 ・ クリークに追加できる  クリークの全ての頂点に隣接なので、これらの頂点を更新することで、１つ O(Δ) 時間 ・ 末広がり的な計算構造により、実際はほぼ定数時間 111…1 クリーク 000…0

44 新旧アルゴリズムの比較 ・ 次数の増加に対しては、ほぼ線形で伸びる ・ 共著関係を表す実データに対しても、ほぼ１つあたり定数時間

45 小野拓史, 豊田正史, 喜連川優, リンク解析を用いたウェブ上のスパム発見手法に関する一考察
スパムサイト検出 ・ スパムサイト： ある種のリンク構造を構築してページの重要性を上げ、（不正な）商業活動や、違法な行為を行うサイト 　 web検索では、スパムサイトを表示したくない 　 スパムサイトを機械的に判別したい ・ スパムサイトは、ランキングを上げるために密なリンク構造（完全に密ならばクリーク）を作っている 　 クリークを見つけることでスパムサイトを検出 　 実際には、スパムサイトは非常に大きな次数を持っており、巨大な、少しずつ違う極大クリークがあり見つけきれない 小野拓史, 豊田正史, 喜連川優, リンク解析を用いたウェブ上のスパム発見手法に関する一考察

46 その他の応用研究 ・ Core Stability of Minimum Coloring Games
・ Biclustering Protein Complex Interactions with a Biclique Finding Algorithm ・ Faster Algorithms for Constructing a Concept (Galois) Lattice ・ An Efficient Algorithm for the Extended (l, d)-Motif Problem With Unknown Number of Binding Sites ・ Rapid Detection of Botnets through Collaborative Networks of Peers

47 参考文献など ・ 築山らのアルゴリズム (‘78) 初の多項式時間アルゴリズム
・ 築山らのアルゴリズム (‘78)　　初の多項式時間アルゴリズム ・ 宇野らのアルゴリズム (‘03) 改良版。大きく疎なデータでも速い ・ 富田らのアルゴリズム (‘04) 枝刈りを用いた列挙。密でも速い ・ クリークの応用の文献は星の数ほど(Nature などにもある) 　　　　　 “クラスタリング” + “クリーク” などで検索 ・ 実装 MACE: (MAximal Clique Enumerator) 宇野のHP

48 サイクルの列挙 ・ グラフの中から、わっかになっている経路を全て見つける問題がサイクル列挙問題
・ 分割法（場合分けをしていき、解が無くなった場合を枝刈りする）　　　　で、１つあたり O（|E|）時間で解ける、という1972年の結果がある ・ 実際は、中くらいのグラフでも大量のサイクルがあり、非実用的 ・ ショートカットのないサイクルのみに限定 すると、数が実用的な範囲に収まる。 計算時間は１つあたり O（|E|）時間

49 応用と性能 ・ グサイクルの列挙も、分割していくに従い問題が小さくなるため、末広がり的な構造を持ち、高速な列挙が可能
・ 化学化合物では、ショートカットのないサイクルは環構造と呼ばれ、特徴を知る上で大切な概念 ・ 化合物の性質を予測する際に、環構造列挙の結果を使って精度を上げている研究もある

50 類似項目が同一グループに入るよう分類する、
類似項目対の列挙 ・非常に多くの項目を持つデータベースの、どの項目とどの項目が似ているか、含むかを調べる 　 普通に全対比較したのでは、とても終わらない ・テキストのような切れ目のないデータは、小さく切って似てるものを探すことで、中規模の類似構造を検出 例：共通部分が2以上のペア (A,B), (A,C), (A,D), (A,E) (C,D), (C,E), (D,E) 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 D ＝ 類似項目が同一グループに入るよう分類する、 という手法で高速化

51 リンク先が似ているwebページ ・ webリンクのデータの一部を使用 － ノード数 550万、枝数1300万
　　　－ ノード数 550万、枝数1300万 　　　－ Pentium4 3.2GHz、メモリ2GB ・ リンク先 20個以上 個、20個以上共有する ペア数が 個、計算時間、約8分 ・ リンク元 20個以上が 個、20個以上共有する ペア数が 個、計算時間、約3分 ・ 方向を無視して、リンクが 100個以上あるものが 個、 100個以上共有するペア数が 個、計算時間、約7分 ・方向を無視して、リンクが20個以上あるものが 個、 20個以上共有するペア数が 個、計算時間、約14分

52 ゲノムの比較 (2) ヒトX染色体とマウスX染色体の比較 ・ 30文字で間違い2文 字以下のペアを列挙 ・ 長さ3000、幅300
の領域に3つペア があれば点を打つ （誤差10%弱で似て いるものは、必ず３つ のペアを含む） ・ ノイズをかなり 除去できている ヒトX番染色体 マウスX染色体 PCで 1時間で可能

53 まとめ ・ データ中心化学に対する列挙からのアプローチ － あいまい性、ノイズ、個別対応．．．  列挙が効果的に使える ・ 頻出集合の列挙
　　－ あいまい性、ノイズ、個別対応．．． 　 列挙が効果的に使える ・ 頻出集合の列挙 　－ 単調性を使った列挙法 　－ データベース縮小を使い、計算構造の末広がりに合わせた高速化 ・ クリーク、サイクルの列挙 ・ 類似項目・包含関係の列挙 ■ 厳密解法、ランダムサンプリング、数え上げなどへの応用 ■ データ解析分野での、列挙を用いたアプローチの確立 ■ 実践的な列挙アルゴリズムを説明する理論構築