宇野 毅明 （国立情報学研究所 ＆総合研究大学院大学） 発見問題に対する 列挙手法を用いた探索 宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2007年9月27日 産業総合研究所

計算からのアプローチ ・ 発見的な目的を持つアルゴリズムは、多くの研究がある －画像・音声などの認識 －遺伝子予測など － クラスタリング 　－画像・音声などの認識 　－遺伝子予測など 　－ クラスタリング 　－ 類似構造の検出 ・ モデリング、計算の難しさから、ヒューリスティックに基づく探索を行うものが多い 　利点： よいと思われるものが見つかっている、かな？ 　課題： 何を見つけているのかわかりにくい 　　　　　条件をいろいろ入ると、計算的にコストが増える ・ ここでは、「アルゴリズム理論」から課題を見つめたい

アルゴリズム理論からの観察 ・ データマイニング的な問題では、モデリングの目的は多くの場合「面白いもの」「役に立つもの」  そもそも数理化・定式化困難  基本的な条件だけを搾り出し、アルゴリズム設計の観点から有利なモデル化をしてみよう  そのさい、入力と出力をしっかり決めて、問題をしっかりと定式化する（使いやすく？なる？） ・ 実際には、基本的な問題を解いて得られる解に、オーダーメード的な処理をして質を高めるという使い方が一般的  候補を見つけ、必要なものを絞り込む "列挙的なアプローチ"

列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ 数の合計の可能性 ．．． A B ・ 1,3,5,8,14 の中から数字を 選んでできる合計を列挙せよ ・頂点 A と B を結ぶパスを列挙せよ 解） … 解） 0, 1, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 28, 30, 31 情報科学の基礎的な問題 近年、広く使われ始めている

極大・極小なもの、代表者をいかに選ぶかが重要 列挙モデルの難しさ ・ 組合せ的に選択可能な箇所があると、解数が爆発 例）　2点を結ぶパス  最短路のみを列挙すれば、回避できうる 例）　グラフのクリーク  極大クリークのみを列挙すれば、回避できうる 大きなクリーク 極大・極小なもの、代表者をいかに選ぶかが重要

指数個解のある問題は、現実的には解く意味がない 列挙アルゴリズムの難しさ ・ 解は多いが、総当りは非効率 　列挙は解が指数個存在するので、ほぼ全ての組合せが解になりうる  総当り的な検索が計算量の意味で最適 　例）　2点間を結ぶパスは指数個ありうる 　　　2点間を結ぶパスは、枝の組合せ全てより指数分の１である 指数個解のある問題は、現実的には解く意味がない ボトルネック ＝ 解の個数 ＝ 出力の時間  解が少なければ速く、解が多ければ遅いアルゴリズムが望ましい － 解１つあたりの計算時間が短い（定数） － 1秒あたりの出力数が大きい（スループット）

いかに効率よい探索ルートを作り、短時間で移動するかが課題 効率的な探索が重要 例題） (3,2) から１つ、(9,3,5) から1つ、(4,1,3) から１つ、 (0,7,1) から１つ、合計4つの数字を選んでできる組合せの 中で、合計が10以下のものを求める　（予算10以下の組合せ） 4 1 3 7 9 3,9,4,0 3,9,4,7 3,9,4,1 3,9,1,0 3,9,1,7 3,9,1,1 3,9,3,0 3,9,3,7 3,9,3,1 3,3,4,0 3,3,4,7 3,3,4,1 3,3,1,0 3,3,1,7 3,3,1,1 3,3,3,0 3,3,3,7 3,3,3,1 5 3,5,4,0 3,5,4,7 3,5,4,1 3,5,1,0 3,5,1,7 3,5,1,1 3,5,3,0 3,5,3,7 3,5,3,1 2 2,9,4,0 2,9,4,7 2,9,4,1 2,9,1,0 2,9,1,7 2,9,1,1 2,9,3,0 2,9,3,7 2,9,3,1 2,3,4,0 2,3,4,7 2,3,4,1 2,3,1,0 2,3,1,7 2,3,1,1 2,3,3,0 2,3,3,7 2,3,3,1 2,5,4,0 2,5,4,7 2,5,4,1 2,5,1,0 2,5,1,7 2,5,1,1 2,5,3,0 2,5,3,7 2,5,3,1 全ての組合せより はるかに少ない いかに効率よい探索ルートを作り、短時間で移動するかが課題

事例研究の評価 モデル 入力の大きさ、事後処理のコストに対して、解数が十分小さいか データの性質などから解数を見積もり、求解時間を算定 　データの性質などから解数を見積もり、求解時間を算定 　　 － 極大性、代表解の選出などがうまく使えているか アルゴリズム 解１つあたりの計算時間が十分短いか 　計算量と理論的根拠に基づく計算時間の算定 　　 － 出力数依存の計算手法になっているか 　　 － 余計な組合せを見ない、効率よい探索 　　 － 疎性、パワー則などの上手な利用 　　 － 末広がり性を利用した反復的な問題縮小

列挙事例：　クリークの列挙

グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの クリーク列挙問題 グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの ・ 2部クリークの列挙問題は、グラフの変換でクリーク列挙に帰着できる ・ 最大クリークを求める問題はNP完全 ・ 極大クリークは簡単に求められる ・ 最適化を中心に非常に多くの研究がある

SQL でもかけるが、巨大データでは長時間 クリークの単調性 ・ クリークの部分集合はクリーク  単調性が成り立つ  原点を出発して山を登り、 クリークでなくなったら、 戻って、他の方向に登る、 というバックトラック式の 列挙ができる クリークであるかどうかのチェック はO(n2) 時間、最高 n 方向に登る  １つあたり O(n3) 時間 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 SQL でもかけるが、巨大データでは長時間

追加できる候補を絞り込む ・ 追加できる頂点を効率よく見つけたい 追加できる  クリークの全ての頂点に隣接 追加できる  クリークの全ての頂点に隣接 あらかじめ、追加できる候補を調べておくと楽 ・ さらに、新しい頂点を１つ追加したとき、 候補に残る頂点  新しい頂点に隣接 候補の集合の更新は、 追加する頂点に隣接する頂点と、 候補の共通部分をとればいい クリーク一個あたり、頂点の次数の時間

・ バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル 末広がり性 ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル ・・・ 次数大きい頂点 次数小さい頂点 ほぼ全ての反復が短時間で終了 （1秒間におよそ100万個） 多くの列挙アルゴリズムが似たような再帰構造を持つので、 下のレベルの仕事を上のレベルがやれば、同様の改良ができる

クリークの個数 ・ 実データには、比較的大きなクリークがよくある ・ 大きなクリークの任意の部分集合はやはりクリーク なので、個数は大きくなる ・ 極大クリークのみを列挙しよう 　－ 数が1/10～1/1000 に減る 　－ 任意のクリークは極大クリークに含ま 　　　　　れるので、情報の損失がない 　－ 極大なほうが、中途半端なグループを含みにくく、 　　　　　モデルとして的確 クリーク 極大なクリークだけを上手に列挙できるか

探索の難しさと枝刈り ・ 極大クリークは山の頂上に対応  単純な操作では行きあえない ・ そもそも、原点のそばに極大クリークがない ・ バックトラックが通じない が、枝刈りをすると実に効率が良い （上に登っても、以前見つけた 極大クリークに含まれるクリークしか みつからないとき、枝刈りをする） 111…1 クリーク 000…0 現実的には１つあたり定数時間で列挙できる （1秒間におよそ10万個）

現実的な疎データでは、だいたい全列挙可能と考えてよい 計算時間 ・ 疎なグラフであれば、極大クリークの数は通常非常に小さい （頂点数の 10から100倍くらい） ソーシャルネットワークデータ： 4万頂点 6万枝  3秒 辞書データ： 4万頂点 10万枝  50秒 webデータ： 500万頂点 5000万枝  1時間くらい？ … 現実的な疎データでは、だいたい全列挙可能と考えてよい

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

列挙事例：　頻出パターンの列挙

頻出パターンの列挙 データベースの中に多く現れるパターンを頻出パターンという  データの解析、特徴分析、知識・ルール発見 頻出する データベース： トランザクション、ツリー、グラフ、多次元ベクトル パターン： 部分集合、木、パス・サイクル、グラフ、図形  データの解析、特徴分析、知識・ルール発見 データベース 頻出する パターンを抽出 ・ 実験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 　　　　． 実験結果 ゲノム情報

多く現れる  頻出する 多く現れるものを見つけるために、多く現れるとは何か、を決める ・ データベースが項目の集まりだとする 多く現れる  頻出する 多く現れるものを見つけるために、多く現れるとは何か、を決める ・ データベースが項目の集まりだとする ・ パターンに対して、そのパターンを含む項目を出現という ・ 出現の数（頻出度）が閾値より大きければ、良く現れるとする （含む、の定義は、集合で行ったり、文字列の 包含、グラフの埋め込みなどで定義する） パターン XYZ {A,C,D} 項目 AXccYddZf {A,B,C,D,E}

トランザクションデータベース パターンとして、集合を考える トランザクションデータベース： 各トランザクション T がアイテム集合 E の部分集合 になっているようなデータベース 　つまり、　D , ∀T ∈ D , 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 D ＝ 実際のデータは、大きくて疎なものが多い パワー則、スモールワールドが成り立つ

集合の出現と頻出度 集合 K に対して： K の出現： K を含む D のトランザクション K の出現集合 Occ(K)： K を含む D のトランザクション全ての集合 K の頻出度 frq(K)：　K の出現集合の大きさ 　{1,2}の出現集合 ＝　{ {1,2,5,6,7,9}, {1,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 ＝ 　{2,7,9}の出現集合 ＝　{ {1,2,5,6,7,9}, 　　　　{1,2,7,8,9}, {2,7,9} }

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

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

・ アイテム、トランザクションを頂点とし、包含関係を枝とする 隣接行列で見ると ・ アイテム、トランザクションを頂点とし、包含関係を枝とする 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が入っている部分行列

バスケット分析 ・ スーパーなどの小売店舗で、同時に購入される事の多い品物の組を知りたい ・ 客が購入した品目  トランザクション ・ 客が購入した品目  トランザクション ・ 品目の組で、多くの客が購入したもの  多くのトランザクションに含まれるアイテム集合  （あるθに対する）頻出集合 ● 牛乳、弁当 ● お茶、弁当 ● おにぎり、雑誌 ● はさみ、のり ● ラーメン、はし ● こっぷ、皿 ● 弁当、おにぎり 　　　．．． 「おむつとビールの組合せが良く売れる」 という発見が有名

対象： データの関連を現すグラフ （データの項目が頂点、関係のある、類似する項目間に枝） 応用：クラスタリング 対象：　データの関連を現すグラフ （データの項目が頂点、関係のある、類似する項目間に枝） 互いに背反だが、 立場が同じ項目のグループ 類似する、あるいは互いに 関連するグループ ・ データの種類・規模で大きさが変わる ・ 通常、それほど密ではない（次数高々100） ・ 局所的に密な部分が存在 ・ パワー則、スモールワールドが成り立つことが多い

対象： ウェブネットワーク （ウェブページが頂点、リンクが枝） 応用：ウェブコミュニティーの発見 対象：　ウェブネットワーク （ウェブページが頂点、リンクが枝） リンク先 （同種のテーマ） リンク元 （似た興味） グループになっている ・ グラフの大きさは 世界全体で100億ページ ・ ある種のドメインに区切ったり、意味のないページを除くと 　1/10 から 1/1000 に小さくなる ・平均次数は10程度だが、局所的に密な部分が存在 ・パワー則、スモールワールドが成り立つ

対象： 単語ネットワーク （単語が頂点、単語AとB を組合せて 複合語ができるとき、枝を張る） 類義語群の発見 対象：　単語ネットワーク （単語が頂点、単語AとB を組合せて 複合語ができるとき、枝を張る） 関東 関西 中国 北陸 地方 地区 電力 2部クリークの片側が、 似た意味を持つ単語の集合 ・ 大きなものでも、15万語程度 ・ 通常、それほど密ではない（次数高々200） ・ 局所的に密な部分が存在 ・ パワー則、スモールワールドが成り立つ

対象： 論文・アブストラクトグラフ （論文が片側の頂点、単語がもう 片側の頂点で、論文のアブストラクト が単語を含むときに枝を張る） 類似論文のグループ化 論文A 論文 論文C 論文D 語1 語2 語3 対象：　論文・アブストラクトグラフ （論文が片側の頂点、単語がもう 片側の頂点で、論文のアブストラクト が単語を含むときに枝を張る） 語：　研究分野を表す単語群 論文：　その分野の論文のグループ ・ 大きなものでも、10万語程度 ・ 通常、それほど密ではない（平均次数高々200） ・ 局所的に密な部分が存在 ・ パワー則、スモールワールドが成り立つ

データベースの比較 ・ ２つのデータベースが、意味的にどの程度似ているか知りたい  大きさの違い、ノイズは無視したい ・ 各アイテム、属性などの総数だけでは、組合せがわからない ・ 組合せを細かく見ると、ノイズに振り回される データ ベース 頻出集合を列挙することで、 組合せ的な特徴を比較できる ・ いろいろな言語の辞書データ ・ 異なる種のゲノムデータ ・ 文書集合の単語データ（新聞のデータ、雑誌のデータなど） ・ 顧客のデータ

分類ルール、特性の発見 ・ データの特徴を現す規則、あるいは正例・負例を分類するような規則が知りたい （A,B,C が含まれている、A,B が含まれれば、C が含まれる、など） ・ 多く現れる組合せを用いないと、仮定部分を満たすものが少なく、ルールとして意味がない ・ 組合せを細かく見ると、ノイズに振り回される 頻出集合を仮定に用いることで、 信頼度の高いルールを 効率良く見つけられる データ ベース データ ベース 正例 ・ 実験データ ・ 利用者履歴データ、マーケッティング 負例

計算時間は、どうなるべきだろう？ ・頻出集合の数は最高で 2n個になるから、計算時間 O(2n|D|) は、|D| の部分を除けばある意味で仕方ない？  そんなことはない。そんなにたくさん答えが出てくるような計算は、そもそもしたくない  つまり、解（頻出集合）の数はそんなに多くない、と思ってよい  逆に考えると、解を出力する部分の計算は避けられない つまり、「これだけは最低かかる」 ・そこで、「解１つあたりの計算時間がどうなるか」に注目しよう

頻出集合の単調性 ・ 工夫をするためには、何か問題の特徴をつかまなくてはいけない 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 これなら、うまいことたどれば、 頻出集合をすばやく全部見つけられそう

重複に気をつける ・ また、よくよく見ると、「どの頻出集合も、空集合（アイテムが 何も入っていない集合）にアイテムを１つずつ追加して作れる ・ また、頻出集合にアイテムを追加して、頻出でなくなったら、その後いくら追加しても2度と頻出にはならない 全ての追加の仕方を尽くせば、 　全ての頻出集合が見つかる ・しかし、単純に全てを 尽くすと、大量に重複が出る 1,2,3,4 φ 1,2 1,2,3 1 φ 1,2 1,2,3 2 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 φ 1,3 1 1,4 2,3 2,4 3,4 1 2 3 4 どうやって重複を回避するか φ

メモリを使わず、本質的に重複を回避する方法がほしい 重複の回避法 ・ グラフ探索問題（幅優先探索、深さ優先探索）をするのだ、と考えれば、「一度訪れた頂点には、マークをつければいい」となる  マークをどうやってつける？　そもそも、探索するグラフを得ること自体が、解を求める作業と同じ ・ 他の手として、出力した解を全部メモリにとっておいて、新たな頻出集合が見つかるたびに、「今までにこれを出力したか」チェックをする  メモリが大量に必要。おまけに、探索の手法、というレベルでは、重複は避けられていないため、１つあたりの計算時間は長くなるはず メモリを使わず、本質的に重複を回避する方法がほしい

こういう探索方法をバックトラック法という バックトラック法による探索 ・ そもそも重複が起こるのは、各頻出集合がいくつもの部分集合から「アイテムを１つ追加」として得られるのが原因 　（{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 こういう探索方法をバックトラック法という

バックトラック法の計算時間 ・計算時間を算定してみよう。擬似コードは 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|) 解１つあたりの計算時間が算定できた

解1つ当たり、を速くする ・解１つあたりの計算時間はそれなりに（多項式時間で）抑えられたが、まだまだ大きい ・ 各 K＋e について、その頻出度を計算 　－単純にするなら、全ての項目（トランザクション）について、 K＋e を含むかどうか調べる 　 最悪、データベースの大きさに比例、 　　　平均ではだいたい、項目数、 　　頻出度×Kの大きさ、の大きいほう 　－ 2分木のようなデータ構造を作って、含むものだけ 抜き出す、あるいは勘定する、というのは、難しい 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 ここにもアルゴリズムが必要

含むものしか含まない ・ アイテム集合 X の出現集合を T とする ・ X＋e の出現は X を含む（＝ X の出現） ・ T のトランザクションで e を含むものを集めると X＋e の出現集合が得られる ・ 出現集合を更新すれば、 　　　データ全体を見なくて良い  計算時間はだいぶ短くなる

含むものしか含まない ・ アイテム集合 X の出現集合を T とする ・ X＋e の出現は X を含む（＝ X の出現） ・ T のトランザクションで e を含むものを集めると X＋e の出現集合が得られる ・ 出現集合を更新すれば、 　　　データ全体を見なくて良い  計算時間はだいぶ短くなる

計算時間は、スキャンしたアイテムの数  両者の大きさの和 共通部分をとる ・ T のトランザクションで e を含むものを集めると X＋e の出現集合が得られる 　 X＋e の出現集合は、 Xの出現集合と e の出現集合の共通部分 （両方に含まれるものを集めたもの） ・ 共通部分をとるには、両者をソートしておき、同時に先頭からスキャンする {1,3,7,8,9} {1,2,4,7,9} ＝ {1,7,9} 計算時間は、スキャンしたアイテムの数　 両者の大きさの和

振り分けによる高速化 ・ 各アイテムに空のバケツを用意する ・ X の各出現 T に対して、以下を行う 　 － T に含まれるアイテム e に対して、 e のバケツにT を入れる  この操作が終わった後は、各アイテムe のバケツの中身は X＋e の出現集合になる for each X の各出現 T for each T に含まれる e, e>Xの末尾 　　　eのバケツに T を挿入 1: A,C,D 2: A,B,C,E,F 3: B 4: B 5: A,B 6: A 7: A,C,D,E 8: C 9: A,C,D,E 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

振り分けの計算時間 for each X の各出現 T for each T に含まれる e, e>Xの末尾 eのバケツに T を挿入 ・ 計算時間は, X の各出現の (Xの末尾) より大きなアイテムの数の総和 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

・ Compute the denotations of P ∪{i} for all i’s at once, Occurrence Deliver ・ 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} Check the frequency for all items to be added in linear time of the database size Generating the recursive calls in reverse direction, we can re-use the memory

1再帰呼び出しの計算時間のイメージ 効果はこれだけではない ・ 普通に頻出度の計算をすると 各 X＋e に対してデータを 一回スキャンする ・ 共通部分による計算は D(X) と D(e) のをスキャンする 　 D(X) を n-t 回スキャンし、 データベースの t より大きな アイテムをスキャンする ・ 振り分けは D(X) に含まれるトランザ クションの t のをスキャンする t より 大きなアイテムをスキャンする (n-t)個 効果はこれだけではない ＋ (n-t)個 t t

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

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

キャッシュとの相性 ・ 速いプログラムを作るとき、キャッシュのヒット率が良く問題になる － ループを開く － メモリの配置を変える 　－ ループを開く 　－ メモリの配置を変える for i=1 to n { x[i]=0; }  for i=1 to n step 3 { x[i]=0; x[i+1]=0; x[i+2]=0; } ● ● ● ●▲ ● ▲ ▲ 再帰的に問題が小さくなり、ある反復より先ではキャッシュに入る  末広がり性より、ほぼ全ての部分でキャッシュに入っている

末広がり性の利用 １つあたり定数時間で列挙（1秒100万個くらい） ・ パターン X の出現集合を T とする X＋e の出現は X を含む（＝ X の出現） T の中で e を含むもの  X＋e の出現集合 ・ 出現集合を更新すれば、データ全体を見なくて良い ・ 反復が深くなると、見るべき出現集合は小さくなる  末広がり性が活用できる ・ θが大きいと、下のレベルでも多くの出現を見ることになるが、 不要な要素を除き、同一になったトランザクションをまとめることで データベースを小さくできる １つあたり定数時間で列挙（1秒100万個くらい）

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

極大頻出集合と飽和集合の例 ・ 頻出集合を出現集合で分類 ３つ以上に含まれるもの {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 T ＝ 頻出飽和集合 極大頻出集合

・ アイテム、トランザクションを頂点とし、包含関係を枝とする ２部グラフによる飽和集合の表現 ・ アイテム、トランザクションを頂点とし、包含関係を枝とする 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秒間に1～10万個 極大頻出集合と飽和集合 極大頻出集合 ・ 多項式時間で列挙できるかどうか、未解決 ・ クリークと同じように枝刈りをすると、高速に列挙できる ・ 数が少ないがθによる解のぶれが大きい 飽和集合 ・ 逆探索という探索手法で多項式時間列挙可能 ・ 離散アルゴリズムと末広がり性を用いて、高速列挙可能 ・ 出現の意味で情報の損失がない ・ ノイズが多いと出現集合が等しいものが少なくなり、 　　　解の減少効率が悪くなる 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個

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

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

・ データベースの全ての 飽和集合とその親子関係 親子関係の例 ・ データベースの全ての 飽和集合とその親子関係 φ 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 ＝ 出現集合が隣接 親子関係

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

比較の手間 ・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

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

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

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

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

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

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

密な実データ＆ 巨大データ accidents accidents メモリ web-doc

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

親の定義： 左が重くなるように子供をソートし、一番右の葉を除去する 逆探索の例：　根付き木 親の定義： 左が重くなるように子供をソートし、一番右の葉を除去する

逆探索の例： フロアプラン （長方形による部屋分け） 逆探索の例：　フロアプラン （長方形による部屋分け） 親の定義： 左上の部屋の 右か下の壁をスライドして 左上の部屋をつぶす

・ 実データからとった、著名なベンチマーク問題でテスト ・ 項目数は 1万 ～ 100万 ・ 属性数は 1000 ～ 1万 実験結果 ・ 実データからとった、著名なベンチマーク問題でテスト ・ 項目数は 1万 ～ 100万 ・ 属性数は 1000 ～ 1万 Pen. M 1GHz 256MB メモリ データ種別 POS クリック Web閲覧 顧客 単語 項目数 51万 99万 7.7万 8.8万 6万 データサイズ 330万 800万 31万 90万 23万 出力数 460万 110万 53万 37万 100万 計算時間 80 秒 34 秒 3 秒 6 秒 単純なスキャンは1秒で100パターン程度

参考文献など ・ 頻出集合およびその応用 (’90～) 星の数ほど ・ 頻出集合およびその応用 (’90～)　　星の数ほど 　　 “frequent pattern”、”frequent itemset” で検索すると出てくる ・ 極大頻出集合およびその応用 (’90～)　　やはり多い 　　 “maximal frequent itemset” などで検索すると出てくる ・ pasquerらのアルゴリズム (‘99) 飽和集合の導入 ・ 宇野らのアルゴリズムLCM (‘04) 現在最速のアルゴリズム ・ 実装 LCM: (Linear time Closed itemset Miner) 宇野のHP http:research.nii.ac.jp/~uno/ ・ レポジトリ　（実装、論文、比較実験の数々） http://fimi.cs.helsinki.fi/

列挙事例：　コードレスサイクルの列挙

・ 新たな化合物が得られたときに、その組成は比較的容易に得られるが、結合の構造は容易に計測できず、さらに立体的な構造の計測はもっと難しい 化合物の立体構造の推定 ・ 新たな化合物が得られたときに、その組成は比較的容易に得られるが、結合の構造は容易に計測できず、さらに立体的な構造の計測はもっと難しい NO2 NO2 OH C6H5NO4 O O OH 組成 平面構造 立体構造 化合物 すでに構造がわかっている化合物の データを検索して、構造を推定する

化合物の立体構造の推定 ・ 推定する化合物と部分的な平面構造が一致する化合物をデータベースから探し出す  大域的な構造が拾えない 　 大域的な構造が拾えない ・ 検索結果を、環構造の複雑さ 　　で絞り込む 　 立体構造の要因が入り、精度が増す

遺伝ネットワークの依存関係の解析 ・ 遺伝子を頂点とし、遺伝子Aが発現すると、遺伝子Bに影響を与え、発現するときに 枝を引いたグラフを遺伝ネットワークという ・ 循環している系を見ようとすると、 サイクルの構造が必要 　 サイクルを列挙することで、 どのような構造があるかを解析する A B F C E D

・ 実用を考えればいろいろな条件が考えられるが、ここでの問題のモデル化（定式化）では、基礎的な部分、つまりサイクルの列挙のみを考える 問題の定式化と狙い ・ 実用を考えればいろいろな条件が考えられるが、ここでの問題のモデル化（定式化）では、基礎的な部分、つまりサイクルの列挙のみを考える サイクル列挙問題： 与えられたグラフ G のサイクルを全て出力する問題 ・ 解の数に依存した計算時間 ・ 簡単な構造の解法 A B F C E D

分割法による列挙 111…1 ・ サイクルの集合は、単調性を満たさない  バックトラックは適用できない ・ 分割法というアルゴリズムを使う 　 バックトラックは適用できない ・ 分割法というアルゴリズムを使う ・ 最初の枝を選ぶ ・片方の端点に接続する枝それぞれについて、 「その枝を使うサイクル」を再帰的に列挙する ・ ただし、サイクルができない枝は行わない ・最初の枝の、もう片方の端点に帰って きたところでサイクルがひとつ見つかる 000…0

分割法の図解 ・ 分割法（分枝限定法）の再帰構造を図示してみる ・ 各反復で、ある頂点を含むものと 含まないものに解集合を分割し、 できた集合が空でなければ、 再帰的に列挙を行う v1 各反復で、解が あるか判定し、 なければ中止 v1, v2 反復数が 解の個数×n で抑えられる

サイクルの存在のチェック ・ 効率良く列挙するためには、選択した枝を含むサイクルが存在するかどうかを短時間でチェックする必要がある ・ 今まで選択した枝でできるパスの内点を全ての抜いたグラフで、端点から端点へ行ければサイクルが存在 グラフ探索1回でできる 探索1回で、加える枝 全てをチェックできる １つあたりグラフの大き さの時間で列挙できる

実用的には、１つあたり定数時間で列挙できる（1秒10万個） 末広がり性の利用 ・ 再帰構造の下の部分では、選択したパスの両端点が近い 　 幅優先探索でチェックを行えば、 　小さい範囲しか探索しない ・ 再帰が深くなるほど、 　　反復が短時間で終了する グラフ 実用的には、１つあたり定数時間で列挙できる（1秒10万個） ・ しかし、通常サイクルの数は多い

化合物データのコードレスサイクル数は小さい コードレスサイクルの利用 ・ ショートカットを持たないサイクルをコードレスサイクルという ・ 冗長なサイクルはコードレスにならない （ある意味で極小） ・ サイクルの本質部分が見える 応用上もありがたい ・ 少々の変更で、同様に列挙できる （すでに通った頂点の隣を通ると、 コードができてしまうので、それを避ける） 化合物データのコードレスサイクル数は小さい 400原子程度の化合物でも高々10万程度  1-2秒

サイクルの存在のチェック ・ このグラフを例にして動きを見る s s a b c a c b d f e g j e g d t i e g h f t f h i t h h i j i t j j j t t t t t

擬似クリークの列挙

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

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

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

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

・ アイテム、トランザクションを頂点とし、包含関係を枝とする 隣接行列で見ると ・ アイテム、トランザクションを頂点とし、包含関係を枝とする 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が入っている部分行列

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

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

与えられたグラフ 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

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

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

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

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

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

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

子どもの発見 ・ 擬似クリークの親は、頂点を１つ取り去って得られる  擬似クリークの子どもは頂点を１つつけることで得られる 　　（子どもの候補 |V| 個しかない） ・ K∪v が K の子どもである  　 ① 擬似クリークであり 　② K∪v の親が K （つまりはv*(K∪v) = v ） ・ この条件を各頂点について素朴に評価するとO(|V|+|E|) 時間 ・ もう少し速くしましょう

子どもである条件 ・ 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の子どもでない

子どもである条件 (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(Δ(Δ+log |V|)) となる

擬似クリーク計算機実験

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

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

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

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

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

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

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

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

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

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

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

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

類似文字列に関する研究 ・ ２つ文字列の編集距離（挿入／削除／変化の最小数）は最短路アルゴリズムを使って、ある程度高速に求められる 　　２つの文字列が似ていないと有効でない 　　入れ替わり構造は発見できない ・ BLASTを始めとする相同発見アルゴリズム （例えば11文字の）短い完全一致領域を見つけ、そこを種として検索 　　文字列が長いと、大量の完全一致がある 　　11文字を長くすると精度が落ちる 　　良く現れる単語は候補から除外、遺伝子部分だけ注目 　　　　といった処理をしているようだ ・ 類似検索 　　大量のクエリを実行しなければならない 　　　　類似検索は通常、完全一致検索より大幅に時間がかかる

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

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

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

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

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

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

・ 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

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

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

（全部の比較と一部の比較の速度があまり変わらない） なぜBLASTより速くできるのか？ ・オリジナルのBLASTは、連続して11文字同じところを見つける 　 大雑把に言って、分類精度は、4の11乗 ≒ 400万 　 100万塩基あたりから苦しそう ・ 今回の手法は、例えば 30文字中間違い3文字（連続して7文字同じ、と同じ精度）で6個に分割するなら、 　大雑把に、分類精度は、4の15乗 ≒ 10億を20回 　 2億塩基あたりから苦しいが、そうなったら分割数を7にすればいい ただし、(短い配列の）検索は苦手 （全部の比較と一部の比較の速度があまり変わらない）

計算実験

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

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

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

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

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

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

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

グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの (２部クリーク：完全２部グラフになっている部分グラフ) クリーク列挙問題 グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの 　　(２部クリーク：完全２部グラフになっている部分グラフ) ・ クリークは、グラフの中の密な構造をあらわす 　　クラスタ、コミュニティーなどをあらわす ・ 極大クリークの列挙は比較的高速にできる(秒速10万個） ・ クリークっぽい構造の列挙もできる

・ データベースの中に多く現れるパターンを頻出パターンという  データの解析、特徴分析、知識・ルール発見に使える 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを頻出パターンという 　 データの解析、特徴分析、知識・ルール発見に使える データベース 頻出する パターンを抽出 ・ 実験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 　　　　． 実験結果 ゲノム情報 ・ グラフ、木、文字列、時系列など、多くのパターンが扱える ・ 頻出パターンの列挙は、通常非常に高速で行える ・ 実験結果から分類規則を見つけることができる

各種最適化問題 最適化問題： 与えられた条件を満たす解の中で、評価値が最も良いもの、あるいはかなり良いものを見つける問題 ・ グラフ構造：パス、木、サイクル、クリーク、マッチング ・ 文字列構造： 部分文字列、シークエンス ・ 集合構造： カバー ・ 平面構造： 四角、直線、詰め込み、 ・ 問題によって、解法をデザインする必要があるが、比較的見通しが明るいことが多い

… 各種サブグラフ列挙問題 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ グラフのサイクル ・ 部分木 ・ マッチング ・ 全張木 ・ 高速だが、解の数が大きい ・ サイクルの代わりにコードレス サイクルを使う、といった工夫が必要 A B …

まとめ ・類似する項目のペアを列挙する、出力数依存型のアルゴリズム 異なりの場所に注目し、分類による絞込みを行う 　　異なりの場所に注目し、分類による絞込みを行う ・ 部分的な比較を用いて、大域的な類似構造を検出するモデル 　－ ゲノムの比較：　ヒト、チンパンジー、マウスの染色体の比較 　　　　　　　　　　　　　バクテリアゲノムの多対多比較 　－ EST配列のマスク、オーバーラップ検出 　－ BAC配列の全対比較 　－ 固有部分配列の発見 ・ツールとしての完成度を高める（UI、解の圧縮など） ・機能の追加

まとめ ・ 列挙手法を用いたデータマイニングへのアプローチ ・ 頻出集合・飽和集合の列挙アルゴリズム ・ コードレスパス・サイクルの列挙アルゴリズム ・ 計算実験で、現実的な疎データに対する有効性を実証 将来の課題： ・ 計算量と現実的な計算時間のギャップを、より良く説明できるか ・ あいまいな尺度によるモデル化と高速解法 ・ 極大元・代表元の効率的な列挙手法 ・ ツールとしての利便性の向上