宇野 毅明 （国立情報学研究所 ＆総合研究大学院大学）

Presentation on theme: "宇野 毅明 （国立情報学研究所 ＆総合研究大学院大学）"— Presentation transcript:

1 宇野 毅明 （国立情報学研究所 ＆総合研究大学院大学）
あいまい性を考慮した列挙手法 宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2007年12月15日 計算限界全体会議

2 動機と問題

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

4 部分構造を見つける ・ データから何らかの構造を見つけ出す、という手法は、データマイニングやデータ工学を始めとする情報学の分野で非常に基礎的であり、多くの研究で用いられている （クラスタリング・webコミュニティー、 グループ化、カテゴリー発見．．．） ・ 構造としてはクリークや文字列などが比較的単純ではっきりとしたものが重宝されてきた 　－パス，クリーク，文字列，頻出パターン… ・ 計算的には扱いやすく、最適化や列挙に関して多くの研究がある。 　　アルゴリズムも、理論＆技術に大きな成果がある

5 あいまいさを扱いたい ・ はっきりとしたものが効率良く扱えるようになったので、次のステップとして、エラーやあいまいさ、不完全さを扱いたくなってきた  そもそも欲しいものは「あいまいなもの」（クリークっぽいもの、など） ・ いくつもの重なり合う極大クリークが１つになる、データにノイズやエラーがあっても、解が比較的ぶれない 　－パス、ツリー  パスっぽいもの、 ツリーっぽいもの 　－クリーク　　　　 クリークっぽいもの 　－文字列　　　　 　 ある程度一致する文字列 　－頻出集合　　　　 多くの項目にそれなりに含まれるもの ・ あいまいさを導入すると、計算のコストは増大する 　（推移律が成り立たない、距離の評価に時間がかかる、など）

6 「アルゴリズム理論」から課題を見つめたい
あいまいさに対する既存のアプローチ ・ あいまいなものを扱う研究は、以前からたくさんある  そもそもクラスタリングは「データの濃い部分」を抽出している  ゲノム配列の相同検索 ・ モデリング、計算の難しさから、ヒューリスティックに基づく探索を行うものが多い 　利点： よいと思われるものが見つかっている、かな？ 　課題： 何を見つけているのかわかりにくい 　　　　　条件をいろいろ入ると、計算的に（解１つあたりの） 　　　　　コストが増える 「アルゴリズム理論」から課題を見つめたい ・ クリーク・頻出集合・文字列検索にあいまい性を導入する

7 擬似クリークの列挙

8 クリーク： 完全グラフになっている部分グラフ （完全2部グラフになっている部分グラフ  2部クリーク）
クリーク：　完全グラフになっている部分グラフ （完全2部グラフになっている部分グラフ  2部クリーク） 類似する、あるいは互いに 関連するグループ 互いに背反だが、 立場が同じ項目のグループ ・ クラスタリング発見などに使われる ・ 現実問題は、通常それほど密ではない（次数高々100）が、 　 局所的に密な部分が存在、パワー則、スモールワールド性 ・ 単調性が成り立つので、列挙しやすい ・ クリーク・極大クリークの列挙は効率良くできる(1秒10万、100万)

9 あいまいなクリーク ・クリークっぽいもの  完全グラフに近い部分グラフ （完全2部グラフになっている部分グラフ  2部クリーク）
・クリークっぽいもの  完全グラフに近い部分グラフ （完全2部グラフになっている部分グラフ  2部クリーク）  クリークから少しだけ枝を取り除いたものとすればいいだろう ・ 抜く本数に制限をつけて、あいまいなクリークとそうでないものを分ける  見つけるものが数理的にはっきりする ・ 全て見つける列挙問題として定式化する

10 あいまいの境界 ・境界を固定して k 本とする  単調性が保持されるのがうれしい、
　が、小さい部分グラフはOK、大きな部分グラフはだめ、になる ・境界をクリーク枝数のθ ％とする  部分グラフの大きさに密度が依存しないのがうれしい  単調性がなくなる 今回はこれを解く

11 擬似クリーク（密部分グラフ）の定義 ・ 頂点部分集合 S に対して、S の枝密度を (S の頂点誘導グラフの枝数)
クリークの枝数 頂点の組のうち結ばれているものの割合 閾値 θに対して S が擬似クリーク  (Sの枝密度) ≧ θ 擬似クリーク列挙問題： 与えられたグラフ G、密度閾値θに対し、G の擬似クリークを全て出力する問題

12 擬似クリークに関わる既存の結果 ・ １つ見つけるのは簡単  空集合、１頂点の集合、枝の両端点が必ず擬似クリークになる
・ 大きさ k の擬似クリークを見つける問題はNP完全  θ= 1 とすると、大きさ k のクリークを見つける問題になる ・ 最も枝密度の高い頂点数 k の部分グラフを見つける問題はNP完全 － O(|V|1/3-ε) の近似率のアルゴリズムがある 　　－ 最適解がある程度濃い、とい条件では O((n/k)ε) 近似 [鈴木徳山] 　　－ 枝数が Ω(n2) ならPTASがある[Aroraら] ・データマイニングなどの分野で、擬似クリークを発見するアルゴリズムはいくつか提案されているが、いずれも完全性がなく、列挙問題として捉えている研究はない

13 分割法によるアプローチは困難 ・ 列挙アルゴリズムの基本的な構築の仕方として、分割法（分枝限定法）がある ・ 各反復で、ある頂点を含むものと
含まないものに解集合を分割し、 できた集合が空でなければ、 再帰的に列挙を行う v1 v1, v2 解があるか判定 する問題がNP完全

14 与えられたグラフ G と閾値 θ、頂点部分集合 U に対して、U を含む擬似クリークが存在するかどうかを判定 する問題はNP完全である
困難性の証明 Theorem 1 　　　　　　　与えられたグラフ G と閾値 θ、頂点部分集合 U に対して、U を含む擬似クリークが存在するかどうかを判定 する問題はNP完全である 証明: 大きさkのクリークの存在判定を帰着 2|V|2 個の頂点を追加し、Uとする |V|2 -1 |V|2 θ= ε 入力グラフ G=(V,E) ・ (U + クリーク) のみが擬似クリーク ・ 大きくなると枝密度が真に増加） ・ εを適当に設定すると、大きさが k 以上のクリークのみが擬似 クリークになる 枝密度 = |V|2 -1 |V|2

15 ????? 果たして本当に困難か？ ・ この証明は「とても濃い」グラフの判定問題が難しいことを 証明しただけ
 密度が中くらいのところについては、良くわからない  出力多項式時間アルゴリズムはできるかもしれない θ= 1 θ= 0 出力多項式時間 計算時間が入力の大きさと出力の大きさに対して多項式 困難 簡単 ????? 簡単

16 擬似クリークの 多項式遅延列挙アルゴリズム

17 ・ 列挙する対象の間に、非巡回的な親子関係を定義
逆探索法によるアプローチ ・ 列挙する対象の間に、非巡回的な親子関係を定義 objects 親子関係が導く根付き木を深さ優先探索することで列挙 探索は、再帰的に子どもを見つけることで行えるので、子どもを見つけるアルゴリズムがあれば十分

18 ・ v*(K) ： G[K] の最小次数頂点の中で最小添え字のもの ・ 擬似クリーク K の親を K＼v*(K) で定義
擬似クリークの親 ・ v*(K) ： G[K] の最小次数頂点の中で最小添え字のもの ・ 擬似クリーク K の親を K＼v*(K) で定義 K K の親 ・ K の枝密度 ＝ G[K] の平均次数 ÷(|K|-1) ・ 親は、K から最も枝密度の薄い部分を取り除いたものなので、 やはり擬似クリークになる ・ 親は大きさがちょうど１小さい　　親子関係は非巡回的

19 擬似クリーク列挙木の例 ・ 閾値を70%に設定 1 2 3 4 5 6 7

20 親から子どもを作る ・ 親は、子どもから頂点を１つ抜いて得られる  子どもは、親に１つ頂点を付け加えて得られる
　 子どもは、親に１つ頂点を付け加えて得られる 　 与えられた親の子どもを見つけるには、各頂点を加える ・ 親に頂点を付け加えて擬似クリークができても、それが子どもとは限らない 　 加えたアイテムが v* にならず、異なるものが親になる可能性 　 v* を計算して照合 ・ 素朴にすると 　　O(|V|+|E|) 時間 objects

21 子どもである条件 ・ degK(v): v に隣接する K の頂点の数
 degK(v) がある一定値以上であるときのみ、 K∪v は擬似クリークになる （擬似クリークである条件） ・各反復でdegK(v)を更新し（O(deg(v)) 時間）、その値ごとに分類しておくと、 条件を満たすものを１つあたり定数時間で見つけられる ・条件 v*(K∪v) = v も、degK(v)の値で場合分けするとクリア 　－ degK(v) < K の最小次数  K∪v は必ず Kの子ども 　－ degK(v) > K の最小次数＋１  K∪v は Kの子どもでない

22 子どもである条件 (2) ・ S(K): K の最小次数の頂点を、添え字順に並べた列
・ degK(v) ＝ K の最小次数 or ＋１  v が、 　　－ v より degK、添え字ともに小さい頂点はない 　　－ degK(u) ＝ degK(v) かつ添え字が v より小さい u 、および 　　　　degK(u) ＝ degK(v)-1 かつ添え字が v より大きい u 　　　　　は必ず v と隣接 ・ K の頂点を次数順・添え字順に見て、隣接リストをスキャンし、 　 K に含まれない各頂点に対して「隣接しない初めての頂点」 を見つける　　 それと、自分の添え字を比べればよい １反復のチェック・データ更新時間は O(Δ2 + log |V|)) となる

23 擬似クリーク計算機実験

24 ・ バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル
末広がり性 ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル ・・・ 計算時間長 計算時間短 擬似クリークが少々大きく（4以上くらい？に）なると、最小次数は平均的に小さいだろう  平均的に計算時間は短いだろう

25 実装 実験環境： Pentium M 1.1GHz、256MBメモリ ＋ cywin ＆ C ・ 実装は、単純なものを用いた
－ degK(v) の更新とグループ分けはするが、並び替えはしない － degK(v)＝ Kの最小添え字 or ＋１ となる頂点に対して、素朴にチェックをする 　　 この条件を満たす頂点はそれほど多くないだろう 　　 隣接しない頂点がすぐ見つかって、頂点１つに対するチェックも結局は短時間でできるだろう

26 実験に用いたグラフ - 通常のランダムグラフ （確率 p で枝をはる） - 局所的に密なランダムなグラフ （自分と添え字が近い頂点のみに
　- 通常のランダムグラフ 　　（確率 p で枝をはる） 　- 局所的に密なランダムなグラフ 　　（自分と添え字が近い頂点のみに 　　　　確率1/2で枝を張る） 　- ランダムに作成したスケールフリーグラフ 　　（頂点を順に追加し、次数に比例する確率で 他の頂点を定数本選び、枝を張る） 　- 現実のデータ 　　（ソーシャルネットワークデータ）

27 ・ 枝の確率が 0.1 で、頂点数が 200-2000。閾値は90%。時間は百万個あたり。クリーク列挙と比べると10倍程度遅い
ランダムグラフ ・ 枝の確率が 0.1 で、頂点数が 。閾値は90%。時間は百万個あたり。クリーク列挙と比べると10倍程度遅い 次数が大きくなるにつれて、ほぼ線形に時間が伸びる

28 ・ 自分の回り±30頂点に確率が 0.5で枝を張る ・ 100～25600 頂点、閾値は90%。同じくクリークより10倍遅い
局所的に密なランダムグラフ ・ 自分の回り±30頂点に確率が 0.5で枝を張る ・ 100～25600 頂点、閾値は90%。同じくクリークより10倍遅い 次数が変化しないので、時間は伸びない

29 ・ 大きさ10のクリークに１つずつ頂点を加える ・ 次数に比例する確率で他の頂点を10個選び、枝をはる
ランダムに作成したスケールフリーグラフ ・ 大きさ10のクリークに１つずつ頂点を加える ・ 次数に比例する確率で他の頂点を10個選び、枝をはる 時間は非常にゆっくりと増加

30 ・ 論文の共著関係を表すグラフ ・ 頂点数は3万、枝数は12万5千、スケールフリー
現実問題 ・ 論文の共著関係を表すグラフ ・ 頂点数は3万、枝数は12万5千、スケールフリー 1個あたりの計算時間は閾値によらないようだ

31 考察＋α ・ 実際の列挙の時間は、ひとつあたりほぼ定数時間 ・ 理論的なバウンド、最大次数の２乗よりはるかに小さい
・ なぜ現実的には速いのか？ 　－ データの更新の時間は、追加された頂点の次数に線形 　　　 degK を小さくする頂点の次数が大きいとは思えない 　－ 子どもかどうかチェックしなければならない頂点は少ない 　　　 子どもの数の定数倍

32 擬似頻出集合

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

34 アイテム集合に対して、あいまいな包含関係を考え、
ここでは ・ いわゆる頻出集合列挙をターゲットにする 入力：　トランザクションデータベース： 各トランザクション T がアイテム集合 E の部分集合 になっているようなデータベースD 　つまり、D, ∀T ∈D, T ⊆ E ・ 解が多い　（大きくて面白いものは少ない） ・ 包含関係が厳密 　 「多くの項目になんとなく含まれている」ものを見つけたい アイテム集合に対して、あいまいな包含関係を考え、 頻出集合の列挙アルゴリズムを提案する

35 既存研究 ・ fault-tolerant pattern、degenerate pattern、soft occurrence など
① 包含関係を一般化：アイテムの含有率が閾値以上  含む 　 単調性がなくなる。ひどい場合、頻出集合の任意の部分集合が頻出でない、という例がある。探索が極めて困難 ② アイテム集合・トランザクションの組で、アイテムが項目に含まれない組合せが少ないもの 　－ 密な部分グラフとイメージが同じ ・ ヒューリスティックな探索が多く、 　　　完全性を保証した列挙型の解法は少ない 1,2 2,3 1,3

36 包含関係の改善 ① 包含関係をアイテムの含有率で一般化  単調性がなくなる 含まないアイテムが閾値以下なら含む、に。単調性は保持
　含まないアイテムが閾値以下なら含む、に。単調性は保持 ・ アイテム集合 P に対して出現集合 Occ≦k(P) が定義できる Occ≦k(P∪e) ＝ Occ≦k(P) ∩ Occ(e) が成り立つなど、 頻出集合の基本的な性質をすべて継承するため、頻出集合列挙アルゴリズムがそのまま拡張できる 　 ほぼ同じパフォーマンスのアルゴリズムが構築可能 ・ ほぼ同じパフォーマンスのアルゴリズムが構築可能 － しかし、小さい集合ほぼ全てが頻出となる

37 ・ k 頻出集合： D のσ個以上のトランザクションに k 擬似包含の意味で含まれるアイテム集合
σ=3での1擬似頻出集合 {1,2,3} {1,2,4} {1,2,5} {1,2,7} {1,2,9} {1,3,7} {1,3,9} {1,4,7} {1,4,9} {1,5,7} {1,5,9} {1,6,7} {1,6,9} {1,7,8} {1,7,9} {1,8,9} {2,3,7} {2,3,9} {2,4,7} {2,4,9} {2,5,7} {2,5,8} {2,5,9} {2,6,7} {2,6,9} {2,7,8} {2,7,9} {2,8,9} {3,7,9} {4,7,9} {5,7,9} {6,7,9} {7,8,9} {1,2,7,9} {1,3,7,9} {1,4,7,9}{1,5,7,9} {1,6,7,9} {1,7,8,9} {2,3,7,9} {2,4,7,9} {2,5,7,9} {2,6,7,9} {2,7,8,9} 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D ＝

38 密な包含 ② アイテム集合・トランザクションの組で、アイテムが項目に含まれない組合せが少ないもの
　－ 単調性はないが、「包含関係のあるアイテム、トランザクションの組が○○％以上」であるアイテム集合・トランザクション集合の組を見つける、と思うと、擬似クリークと同じ仕組みで、隣接性が保証できる  密２部グラフの列挙です ・しかし、頻出集合の場合、注目しているのはアイテム集合だけ  しアイテム集合が同じでトランザクション集合が異なるものは同一視したい

39 平均包含率 ・ トランザクション t のアイテム集合 P に対する包含率 ⇔ ｜t ∩ P｜／ ｜P｜
　 ２部グラフ表現での密度と等価 ・ 閾値 θに対してアイテム集合 P の最大共起数（頻出度） 　　⇔ 平均包含率θ以上のトランザクション集合の最大の大きさ あいまい頻出集合： 最大共起数がσ以上のアイテム集合 1,3,4 2,4,5 1,2 2,350% 4,550% 1,266%

40 問題の定式化 ・ 閾値 θに対してアイテム集合 P の最大共起数（頻出度） ⇔ 平均包含率θ以上のトランザクション集合の最大の大きさ
　　⇔ 平均包含率θ以上のトランザクション集合の最大の大きさ あいまい頻出集合： 最大共起数がσ以上のアイテム集合 1,3,4 2,4,5 1,2 2,350% 4,550% 1,266% あいまい頻出集合列挙問題： 与えられたトランザクションデータベース D、密度閾値θ、最小頻度 σに対し、D のあいまい頻出集合を全て出力する問題

41 擬似頻出集合の 多項式遅延列挙アルゴリズム

42 探索法と困難性 ・ 擬似クリークと同じように、あるアイテム集合を含むあいまい頻出集合が存在するかどうかの判定はNP完全
　 分枝限定法的なアプローチではうまくいかなさそう ・ 逆探索を使いましょう  密度が一番小さいアイテムを抜いて親子関係が定義できそう

43 探索法と困難性 ・ あいまい頻出集合 P の正規出現 AmbiOcc(P) ⇔ 辞書順最小の、平均包含率θ以上の最大トランザクション集合
⇔ 辞書順最小の、平均包含率θ以上の最大トランザクション集合 ・ e*(P)： P のアイテムで AmbiOcc(P) に含まれる数が最小のもの ・ P の親： P＼e*(P)  一意に定まり、あいまい頻出集合となる θ＝66%, σ= 4 A: 1,3,4,7 B: 2,4,5 C: 1,2,7 D: 1,4,5,7 E: 2,3,6 F: 3,4,6 e*(P) = 5 Prt({1,4,5})  {1,4} AmbiOcc({1,4}) = {D,A, B,C, F} {1,4,5}  D, A,B, C,F, E AmbiOcc({1,4,5}) = {D,A,B,C}

44 ・親は子どもより１小さい  親子関係は非巡回的 ・親は子どもより最大共起数が大きい  親もあいまい頻出集合 ・親子関係は木を導出
親子関係から列挙木 ・親は子どもより１小さい 　親子関係は非巡回的 ・親は子どもより最大共起数が大きい 　親もあいまい頻出集合 ・親子関係は木を導出 θ＝66%, σ= 4 φ A: 1,3,4,7 B: 2,4,5, C: 1,2,7 D: 1,4,5,7 E: 2,3,6 F: 3,4,6 1 2 3 4 7 1,4 3,4 4,5 4,7 1,7 1,4,5 1,3,4 1,4,7 3,4,7 4,5,7 1,2,7 1,3,7 1,5,7 1,3,4,7 1,4,5,7

45 子ども列挙による深さ優先探索 ・ 列挙木を探索すれば、全てのあいまい頻出集合が見つけられる
・ 深さ優先で探索すれば、解をメモリに保持する必要もない（木の深さは高々アイテム数） ・ このような、陽に与えられていない木を深さ優先探索するにはどうすればいいか？ 　 与えられた頂点の、子どもが順に見つけられれば十分 　 見つけた子どもに対して、再帰的に子どもを見つければよい objects

46 親から子どもを作る ・ 親は、子どもからアイテムを１つ抜いて得られる  子どもは、親に１つアイテムを付け加えて得られる
　 子どもは、親に１つアイテムを付け加えて得られる 　 与えられた親の子どもを見つけるには、各アイテムを加える ・ 親にアイテムを付け加えて得られるアイテム集合があいまい集合であっても、子どもとは限らない 　 加えたアイテムが e* にならず、異なるものが親になる可能性 　 e* を計算して照合 objects

47 各アイテム追加の最大共起数 ・ アイテム集合 P の最大共起数は、包含率の高い順にトランザクションを追加して得られる
・ アイテム追加による包含率の逆転はない（追いつくことはある） ・ AmbiOcc についてのみ、子ども候補の包含率を計算すればいい ・ e の最大共起数を計算するには、包含率の大きさでトランザクションをグループ分けし、それぞれの中で e を含むものを調べると、トランザクションを P∪e に対する包含率順で並べられる

48 ・ P={1,4} に e=5 追加したときの AmbiOcc(P∪e) の計算
最大共起数の計算 ・ P={1,4} に e=5 追加したときの AmbiOcc(P∪e) の計算 AmbiOcc({1,4}) = {D,A, B,C,F} ,E θ＝66%, σ= 4 A: 1,3,4,7 B: 2,4,5 C: 1,2,7 D: 1,4,5,7 E: 2,3,6 F: 3,4,6 全部含む １つ含まない 全部含まない AmbiOcc({1,4,5})= {D, A,B, C} ,F ,E 全部含む １つ含まない ２つ含まない

49 AmbiOcc の計算 ・ よって、各 P∪e の最大共起数は計算するには、AmbiOcc(P) を包含率 で分類し、各 e について、それを含むものを集め出す  e を含むトランザクション集合との共通部分をとる  振り分け、という手法を使うと速い ・ 最大共起数が大きいアイテム集合はそれほど多くないと思われるので、現実的には、一反復の実行時間は ||AmbiOcc(P)|| に依存する程度だろう

50 あいまい頻出集合計算機実験

51 実装 実験環境： Pentium M 1.1GHz、256MBメモリ ＋ cywin ＆ C ・ 実装は、単純なものを用いた
－ Occh を各 h について保持 － AmbiOcc と親は素朴に計算する 　 親の計算でアクセスする は、計算を工夫してもあまり減少しないだろう 　－ 実際、1/2 ～ 1/3 程度にしかならないようだ

52 実験に用いたデータ ・ FIMI repository のベンチマークデータ － BMS-WebView2: web 閲覧データ
アイテム数 3500、トランザクション数 77000、平均サイズ 4.6 　－ mushroom: キノコの形状のデータ アイテム数 80、トランザクション数 8100、平均サイズ 23 ・ 両方とも実データ ・ 比較対象となる実装がないので、通常の頻出集合列挙と比較 （LCM）

53 密度の閾値を下げると、解の数が爆発的に増える
BMS-WebView2 解1つあたりの計算時間は解の数によらない 密度の閾値を下げると、解の数が爆発的に増える

54 解が増えると、高速化の効果が上がりそうだ
計算効率化の余力 解が増えると、高速化の効果が上がりそうだ

55 mushroom 密度・サポートが大きくなると、 解１つあたりの計算時間は増加する

56 考察＋α ・ 実際の列挙の時間は、ひとつあたりサポートと密度に比例するように見える ・ 理論的なバウンドよりははるかに小さい
・ なぜ現実的には速いのか？ 　－ 1反復の更新の手間は、制限されたデータベースのサイズ 　　　 サポートが小さくなれば平均的に小さい 　－ 子どもの候補はそれほど多くなく、 　　　　親を調べる必要のある子どもの数も少ない 　　　 候補数は大き目の定数、子どももそのうちの定数割合

57 類似する部分文字列の発見

58 データベースから類似する項目を見つける ・ データベースの項目の中で、似た項目のペアを全て見つけたい （項目のペア全てについて、
2項関係が成り立つかを調べる） ・ 類似している項目の検出は、 　データベース解析の基礎的な手法 　　基礎的なツールがあれば、使い方しだいで いろいろなことができる （大域的な類似性、データの局所的な関連の構造・・・） 　・　ここでは、文字列について考えてみる

59 類似部分文字列 ・ 文字列データ（文書）はいたるところに存在 ・ 単なるキーワード検索でなく、文書間の類似構造が知りたい
　－ web文書間の似た部分（引用？） 　－ 多数のプログラムの解析 　－ ゲノム、たんぱく質の類似構造 ・ 類似検索は非常に時間がかかる 　－ 文書数の2乗のオーダーはかけられない 　－ 編集距離を求めるのに、文書の大きさの2乗かかる web、ゲノムで大きな問題

60 類似文字列に関する研究 ・ 全対比較して編集距離を計算  編集距離（挿入／削除／変化の最小数）は最短路で２乗時間
 A*などの改良も有効だが、文字列が似ているという仮定が必要 ・ BLASTを始めとする相同発見アルゴリズム （例えば11文字の）短い完全一致領域を見つけ、そこを種として検索 　　文字列が長いと、大量の完全一致がある 　　11文字を長くすると精度が落ちる 　　良く現れる単語は候補から除外、遺伝子部分だけ注目 　　　　といった処理をしているようだ ・ その他ヒューリスティックサーチ 　－ フーリエ変換を使った判定、指紋法による分類など ・ 類似検索 　　大量の、コストの高いクエリを実行

61 アルゴリズム的に簡単な問題設定を ・ 類似殿尺度には、編集距離でなくハミング距離を  線形時間でOK ・ 長さが可変だと大変なので、固定
・ 長い文書は大変なので、短いものを 　　ハミング距離の計算がますます容易 こういう条件で定式化してみる： 問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデータベースを入力したときに、文字列のペアで異なり数（ハミング距離）が d 文字以下である組を全て見つけよ

62 長い文字列の、ハミング距離でない比較 ・ 長くて、ある程度（ハミング距離の意味で）似ている配列は、短く似ている部分列を必ずある一定数以上含む
・ 長くて、編集距離の意味で似ている配列も、短く似ている部分列を必ずある一定数以上含むだろう  長い文字列は、オーバーラップするようにスライスして短い文字列に分解すればよい

63 分解して比較 ・ 長い文字列を、オーバーラップさせてスライスし、全対比較 ・ 縦横に比較するゲノムをおき マトリクスを作って類似するペアが
あるセルの色を白くする（各ピクセル内の 個数によって色の強弱をつける） ・ 長さα、幅βの領域にいくつかのペアが あるときのみ、色を白くする  長さαの部分配列が、誤差 k %弱で 似ているなら、必ず 誤差 k %で似て いる短い部分列がいくつかある 例：長さ3000で10%弱(間違い290)なら、 長さ30で間違い2の部分列を、少なくとも3つは含む

64 問題の難しさ ・ 全ての項目が同じだと、O(項目数2) 個の出力がある  l を定数だと思えば、単純な全対比較のアルゴリズムが
　　　　　計算量の意味では最適になる 　  計算量理論的には面白くない問題 ・ 現実には、やたらと似ているものがあるものを比較しても意味が無い 　  出力は少ないと仮定する ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

65 基本のアイディア：文字列の分割 ・ 各文字列を、k（>d） 個のブロックに分割する
・ k-d 個のブロックの場所を指定したときに、そこがまったく等しくて、かつハミング距離がd 以下となるようなペアを全て見つけよ、という部分問題を考える  各文字列の k-d 個のブロックをつなげてキーにし、ソートをする。同じものはグループになる。それを総当りで比較すればよい ・ k-d 個のグループ数が大きければ、平均的にグループのメンバー数は小さくなるので、総当りで比較してもたいしたことない

66 全ての場合を尽くす ・ 先の部分問題を、全ての場所の組合せについて解く  ２つの文字列が似てれば、必ずどこか k-d 個のブロックが同じ
 必ずどれかの組合せで見つかる ・ 部分問題は、バケツソートやRadixソートで速く解ける ・ 組合せの数は kCd 。のk=5 で d=2 なら10通り 　　 ソート10回 ＋α で解ける。全対比較よりもかなり高速 ・各文字の数から、１文字比較した場合に等しくなる確率を求め、適切な分割数 k を使用する

67 ・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ
例題 ・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ A B C A B D A C C E F G F F G A F G G A B G A B A B C A B D A C C E F G F F G A F G A B C A C C A B D A F G E F G F F G G A B A B C A B D A C C A F G E F G F F G G A B

68 メモリに解を保持せずとも、重複が回避できる
重複の回避 ・ まったく同じ文字列があると、全てのブロックの組合せで見つかるので、 kCd 。回出力される 　 重複を回避する必要がある ・ 各見つかったペアについて、選択されていないブロックが選択したブロックの間にあったら出力しないようにする 　 等しいブロックが一番左端によっている場合にのみ出力 メモリに解を保持せずとも、重複が回避できる

69 イメージ的には ・ 似ているもののペアを探す問題は、マトリクスのセルの中で必要なものを全て見つける問題
・ 全対比較は、マトリクスのセルをすべて見ていることに対応 ・ 分類によるアルゴリズムは、 分類を順々にしていると思えば、 木構造の探索を行っていることに対応

70 計算実験

71 人のY染色体から部分配列をとって実験。PenMのノートPC
実験：長さ20文字で異なり数 d を変化 人のY染色体から部分配列をとって実験。PenMのノートPC

72 ゲノムの比較 (1) ヒト21番染色体とチンパンジー22番染色体の比較 ・長さ3000万の配列×2 から、30文字の切片を3000万個取る
・ 似ている部分配列のペアの数に応じて、各ドットの明るさを変える ・ 白い部分が 「似ている可能性のある部分」 ・ 黒い部分が 「(絶対に)似ていない部分」 ・ 格子模様は、繰り返し 　　配列を拾っている ヒト 21番染色体 チンパンジー22番染色体 PCで 1時間で可能

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

74 バクテリアを30種 ABC順の取得し つなげて比較 ・ 一度に複数の ゲノムを比較できる
ゲノムの比較 (3) バクテリアを30種 ABC順の取得し つなげて比較 ・ 一度に複数の ゲノムを比較できる PCで 1時間で可能

75 （マイクロアレイ用の）固有な配列のデザイン
・ マイクロアレイの設計には、ゲノム配列中でなるべく他の部分と似ていない配列が使えるとありがたい ・ 配列の長さは２０文字、のように決まっているので、 対象となるゲノムの全て２０文字の部分配列を比較し、 似ているものがないもの、を見つければよい ・ 似ている文字列の数、はある種の統計量として利用できるかもしれない 100Mベース、25文字、間違い2文字まで、くらいなら PCで 1時間で可能

76 （生物学的な）課題点 ・ マウス13番染色体の未解読領域に適用を行っている  既にいくつかの空白部分が埋まった
・ 比較は高速にできるようになった。だが、比較結果をどう使うか、何に留意する必要があるか、といった点は、まだまだ明らかでない － 実験の指針を出すためには、 　　何を出力する必要があるか － どの程度の精度が必要か － どこまで処理を自動化すべきか － エラーをどのように扱うべきか  既存のアセンブリングソフト (phred/phrap/consed)では見つからない、 特殊な重なり方をしている相同領域が 見つかる。どう解釈すべきか？

77 （情報学的・システム的な）課題点 ・ 相同検索としての能力は高い ・ しかし、細かい部分で既存のソフトに劣る － アラインメントが取れない
－ ゲノム固有の制限を入れていない － データベースと連携していない － インストーラ、GUIがない － 実験誤差データを考慮していない － オンラインサービスをするべき ・ 既存のソフトウェアとの連携を 進めていくべきだろう

78 まとめ ・ 擬似クリーク・擬似頻出集合・あいまい頻出集合を列挙する初の多項式遅延多項式空間アルゴリズムを提案
・ 分枝限定法的の困難性を、子問題のNP困難性により証明 ・ 計算実験で、現実的な疎データに対する有効性を実証 将来の課題： ・ 計算量と現実的な計算時間のギャップを、より良く説明できるか ・ 計算量は減らせないか ・ 極大な擬似クリーク、または類するものが効率良く列挙可能か ・ 他の構造に技術の転用ができるか （グラフ、ツリー、ベクトルデータなどのあいまいマイニング、大規模全対比較）