大規模データに対する 効率的な列挙アルゴリズム

Presentation on theme: "大規模データに対する 効率的な列挙アルゴリズム"— Presentation transcript:

1 大規模データに対する 効率的な列挙アルゴリズム
宇野 毅明 （情報学研究所） 　　　　　　（総合研究大学院大学） 牧野 和久 （東京大学） 有村 博紀 （北海道大学） 佐藤 健 （情報学研究所） 佐藤 寛子 （情報学研究所） 清見 礼 （北陸先端～大学） ゲノムの方々 （情報学研究所など） 2006年 12月20日 小島研総合ゼミ

2 今日の講演内容 ・ 列挙問題、列挙アルゴリズムの特徴 問題の難しさ、研究の動向、歴史 ・ 応用事例 （モデル化とアルゴリズムの キモ ）
　　問題の難しさ、研究の動向、歴史 ・ 応用事例 （モデル化とアルゴリズムの キモ ） 　 － クリークの列挙 　－ サイクルの列挙 　－ （類似項目ペアの列挙）

3 列挙とその応用の基本

4 典型的なOR的なアプローチは、データ収集でつまづくことが多い
問題発見 定式化 解法（最適化） 典型的な OR（＋数理計画） 的アプローチ データ収集 （システム構築） 求解 運用 できたモデルを実際に使う ここがボトルネック であることが多い その一方で、データが あふれている場所もある

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

6 データ中心ゆえの難しさとアプローチ web ページの検索 （見つけたいページを見つける） ① キーワードを指定
　① キーワードを指定 　② キーワードを含むページを列挙 　③ 見つかったページを実際に検証 Enumerations from databases solve many problems and give new knowledge キーワード検索 候補 Enumerations from databases solve many problems and give new knowledge 実際にページ を見て検証 Web ページ データベース ・ 数理的な部分をコンピュータで解く　（候補の列挙） ・ 残りはユーザに任せる　（候補の絞込み）

7 データ中心科学の特徴 つまり、列挙 組合せの検索
・ データが整形されていない 　目的がはっきりしない、あるいは異なる目的のために集められたデータを用いるため、必要なものがすぐ取り出せるとは限らない。また、ノイズや不正確な情報も含まれうる。 ・ 目的関数があいまい 　データが情報の塊のようなものなので、そこから得られるものはやはり情報であることが多い（知識、特徴分析といったもの）。それら情報の価値は数理的な尺度では計りにくい。また、従来の最適化とは異なる尺度を用いることが多い。（グラフクラス、シークエンス、情報量、隣接性、類似度、頻出度・・・） ・ データが巨大で、構造を持つ 半自動で集められたデータであるので、データは通常、巨大である。しかし各項目が持つ属性は少なく、疎である。 ・ データ処理は比較的簡単なものが多い データ処理の計算は、最適化のような複雑ではなく、 組合せの検索や整形などいくつかの簡単な処理の組合せ つまり、列挙 組合せの検索

8 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ 数の合計の可能性 ．．．
列挙問題とは何でしょう 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの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 情報科学の基礎的な問題 近年、広く使われ始めている

9 ・ 最適化は問題の一部分を見つける  列挙は問題の全ての部分を見つける
列挙は多面的 ・ 最適化は問題の一部分を見つける 　列挙は問題の全ての部分を見つける 列挙では解の全てを見つけるため、 問題の構造を全体的に把握することができる 「最適ではないが、役に立つ解」を、見つけ損なわない 問題の構造を調べたいとき、数理的にクリアでない 目的関数で解を得たいときに、列挙が有効

10 列挙 モデルから見ると 列挙は中間に位置する ・ シンプルかつ小規模なら、最適化が有効 （きれいな問題の良質な解を１つ求める）
　　　（きれいな問題の良質な解を１つ求める） ・ 複雑あるいは大規模ならばシミュレーションが有効 　　　（複雑・大規模な問題の多数の解を見つける） モデルが 列挙 列挙は中間に位置する 良質な解を多数見つける 最適化 シミュレ ーション シンプルなモデル をじっくり解く 複雑なモデル を粗く解く 線形計画 局所探索 組合せ最適化 アドホック ネットワーク 物理現象の計算

11 列挙研究の歴史 計算機パワーの増大 応用の発達 1960 1990 2000 実用の可能性が発現 黎明期： 基礎問題と計算量
応用で使われ始める （データマイニングなど） 1960 1990 2000 黎明期： 基礎問題と計算量 解が多さで、実用の観点はなし 逆探索 の出現 実用的なアルゴ リズムの発達 （疎な構造の利用、 巨大データ処理等） 極大元列挙法の出現 複雑な構造に対する列挙法の発達

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

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

14 極大クリークの列挙

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

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

17 Web コミュニティ発見 Webコミュニティ： 内容や嗜好が似ているweb サイトの集合
だろう　　 （リンクは、似た内容・嗜好のページに貼られるから） サイト サイト ラーメン 好き ラーメン 命 趣味バイク ホンダ バイク好き カワサキ 博多 ラーメン 札幌 ラーメン バイク万歳 ヤマハ バイク人生 ・ ごみページを除いた後のグラフの大きさは100万～1億程度 ・ 平均次数10程度、パワー則が成り立ち、局所的に密

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

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

20 既存研究 クリーク列挙： ほぼ自明なので論文はないが、たぶん1960年代 極大クリーク列挙 － 1960年代に指数時間アルゴリズム
－ 1978年に築山らの、初の多項式時間アルゴリズム O(|V||E|) － 1985年に西関らの、アーボリシティを用いた解析 O(a(|V|)) － 1995年ごろから、クラスタリングやデータマイニングで 　　　　極大クリーク列挙がはやり出す － 2002年ごろから、基礎的なツールとの認識（Natureなどに論文） － 2003年に牧野宇野の疎なグラフ用のアルゴリズム O(Δ4) 　　　　　　　および行列演算を用いたアルゴリズム O(|V|2.31) － 2004年に富田らの、入力サイズに対する最適アルゴリズム 　　　　　　　実用上もとても速い

21 既存研究（２部グラフ） － ヒューリスティックなものが多数ある
－ 1998年ごろより、closed itemset として、データマイニングの 　　　　分野で盛んに研究される － 2002年ごろより、web community として、web 科学の分野で 　　　　注目される － 2002年 Zaki による closed itemset の列挙　（効率的な枝刈り） － 2003年 有村宇野清見に LCM （今のところ実用上最速） － 2004年 KDCI （LCMと同じ手法で同じくらい速い）

22 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 でもかけるが、巨大データでは長時間

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

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

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

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

27 極大クリーク枝刈り（富田法） ・ 各反復で、バックトラック法が使う頂点の変更する － 最初の頂点に隣接するものは後半部分に押しやる
　－ 最初の頂点に隣接するものは後半部分に押しやる ・ 後半部分の頂点に関しては、 　　再帰呼び出しをしなくて良い 　　 （見つかるクリーク）＋（最初の頂点） 　　　がクリークになっているから ・ 「最初の頂点」には次数の大きい 　頂点を使うと有利 現実的には１つあたり定数時間で列挙できる （1秒間におよそ10万個）

28 極大クリークの隣接関係 （築山法） ・ 極大クリーク K から、添え字の大きい順に頂点を抜いていく
極大クリークの隣接関係　（築山法） ・ 極大クリーク K から、添え字の大きい順に頂点を抜いていく ・ どこかで「現在のクリークを含む辞書順最小の極大クリークK’」が K でなくなる （辞書順最小極大クリーク 　　　　 ＝添え字の小さい順に頂点を加えてできる極大クリーク） ・ その K’を K の親 とする （一意的に定まる） ・ 親は子どもより必ず辞書順で小さいので、親子関係は非巡回的 　 親子関係は有向根付き木を導出する

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

30 通常は K に隣接する i のみ調べればよい （高々（Δ+1）2個）
子どもの特徴づけ ・ K[i]： K に頂点 i を加え、i に隣接する頂点を取り除きできたクリークを、含む辞書順最小のクリーク ・ K' が K の子供　  K[i] = K' がいずれかの i について成り立つ i K[i] だけ調べればよい （高々|V|個） ・ i が K のどの頂点とも隣接しないなら、K[i] の親は i を含む辞書順最小のクリーク 通常は K に隣接する i のみ調べればよい （高々（Δ+1）2個）

31 例題 ・このグラフで実際の親子関係を見てみる １, ２ １ ２ １, ３, ５ ２, ４, ６, ８ ３ ５ ４ ６ ７ ８ ９
10 11 ７ ８ ９ ３, ５, ７, ９, 12 10 11 ６, ８, 10 ４, ８, 11 12 11 11 12 ９, 11 ８, 10, 11 10, 12

32 例題 ・このグラフで実際の親子関係を見てみる １, ２ １ ２ １, ３, ５ ２, ４, ６, ８ ３ ５ ４ ６ ７ ８ ９
10 11 ７ ８ ９ ３, ５, ７, ９, 12 10 11 ６, ８, 10 ４, ８, 11 12 11 11 12 ９, 11 ８, 10, 11 10, 12

33 O(Δ2) 時間で、「K を含む辞書順最小のクリーク」が求められる
辞書順最小の極大クリークを求める ・ CAND(K)：頂点集合 K の全ての頂点に隣接する頂点の集合 ・ CAND(K) の中で最小添え字の頂点を K に加える、という作業を、 CAND(K) が空になるまで続ける ・ CAND(K∪i) ＝ CAND(K) ∩ （iに隣接する頂点） なので、 i の次数の時間で更新可能 ・ クリークの大きさは、最大次数 Δよりも高々1大きいだけなので、繰り返し解数は、高々 Δ＋１ O(Δ2) 時間で、「K を含む辞書順最小のクリーク」が求められる

34 親を計算する ・ K のいずれかの頂点に隣接する頂点全てについて、「 K のいくつの頂点と隣接するか」を記録 （r(v)とする)
　 r(v) = |K| ⇒ K に追加可能 ・ K の最大添え字の頂点から順に消していき r(v) を更新する （ O(Δ2) 時間） 　 r(v) = |K| となるものができたら K に追加可能な頂点が現れたということ ・ その時点で、 K を含む極大クリークを見つければよい O(Δ2) 時間で、K の親が計算できる

35 極大クリークは１つあたり O(Δ4) 時間で列挙できる
子どもを見つける 通常は K に隣接する i のみ調べればよい （高々（Δ+1）2個） O(Δ2) 時間で、K[i] の親が計算できる ・ 以上から、子どもを全て見つけるのにかかる時間はO(Δ4) であることがわかる ・ アルゴリズムは、各反復で極大クリークを１つ見つける 極大クリークは１つあたり O(Δ4) 時間で列挙できる

36 子どもの特徴づけ ・ K<i： K に含まれる、添え字が i 未満の頂点の集合 ・ C(K）： K を含む辞書順最小のクリーク
・ N(v）： v に隣接する頂点の集合（近傍） ・ K[i] が K の子ども  　① K<i ∩N(vi) ＝ K[i]<i 　② C(K<i ∩N(vi) ) ＝ K 特に ② は、 が Kの親 L に対して、K ＝ L[j]、j<i となることと、 　② C(K<i ∩N(vi) )>i ＝ K>i が成り立つことが必要十分 頂点 vi より前のみを見ればよい

37 高速計算の技法 ・ 全ての集合は、配列で保持する（メモリもまとめて確保） ・ アクセスを良くするため、頂点の添え字順に並べておく
① K<i ∩N(vi)： 普通に計算すれば、 O（|K<i|＋| N(vi)<i| ) 　　　　　  　振り分けを使って改良 ・ K の各頂点 vj に対し、 N(vj)>j の各頂点のバケツにvjを挿入 ・ 終了後、vi のバケツの中身は K<i ∩N(vi) 　  計算時間は O（|K<i∩N(vi)<i| ) ・ 再帰呼び出しを添え字の大きい順にすることで、バケツは再帰呼び出し内で繰り返し使える 　  初期設定でvi に大きさ N(vi) のバケツを確保すれば、 　　　　　２度と確保しないでよい

38 ・ 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

39 高速計算の技法 (2) ② K[i]<i と C(K<i ∩N(vi) )：
　　 普通は O（∑v∈K[i]<i |N(v)|）、O（∑v∈C(K<i ∩N(vi) |N(v)|） ・ 調べたい K<i ∩N(vi) ＝ K[i]<i 、C(K<i ∩N(vi)) ＝ K の等号が成り立たないとわかった時点で、計算をやめてよい 　  K[i]<i と C(K<i ∩N(vi) ) を添え字順に計算して比べる ・ K<i ∩N(vi) ＝ K[i]<i の例を解説 　　まず、定義から K<i ∩N(vi) ⊆ K[i]<i は自明 ・ K[i]<i の頂点で、K<i ∩N(vi) に含まれないものがあるか？ 　添え字順に、計算して、比べる　

40 逐次比較の手間 ・定義 K[i]<i ＝ C(K<i ∩N(vi) ∪vi)
・ K<i ∩N(vi) の頂点から１つ、次数の小さい頂点 u を選ぶ 　  K[i]<i ⊆ N(u) だから、 N(u) の頂点のみ K[i]<i に入るか調べればよい ・ ある K<i ∩N(vi) に含まれない 　　頂点が K[i]<i に含まれる  その頂点が K<i ∩N(vi) ∪vi の全ての頂点に隣接 ・ K<i ∩N(vi) ∪vi の頂点の 次数の合計、の時間がかかる 2 4 5 9 1 3 11 6 u vi K<i ∩N(vi)

41 スウィープポインタ ・ K<i ∩N(vi) の頂点、および viの頂点隣接リストに対して、始まりの位置を指すポインタを準備
・ u に隣接する各頂点 vj に対して（小さい順） vj未満でない頂点が見つかるまでポインタを進める ・ vj 以上のものを指すポインタが あったら、u に隣接する次の 頂点の チェックへ進む ・ 全ての頂点に隣接する頂点が あるなら、K に含まれるか調べる K<i ∩N(vi) 2 2 11 4 ∞ u 3 3 4 4 6 6 9 9 1 1 3 3 4 4 5 5 9 9 2 3 4 4 5 5 9 9 1 1 2 2 4 4 6 6 9 9 1 1 4 4 9 9 11

42 ビットマトリクス ・ スウィープポインタは、隣接行列を持ってないがゆえの工夫 隣接行列を持って入れば、もっと単純に速くできる
　隣接行列を持って入れば、もっと単純に速くできる ・が、大きすぎて構築することすら不可能 ・ 隣接行列で、各反復で利用するのはクリークの頂点の行のみ 　 その部分のみをアップデートしよう ・ 通常、クリークの大きさは最大でも 20 程度 　  ビットで持てば、各列が1つの変数に入る！

43 ビットマトリクスの定数時間計算 ・ 各列を１変数で持っていると、隣接性のチェックが1ステップでできる
　 u が K<i ∩N(vi) の全ての頂点に隣接するかどうかを判定するには、 u の行の変数と、 K<i ∩N(vi) のビットパターンの共通部分をとり、欠損が無いか（それ自身と等しいか）を調べる ・・・ K<i ∩N(vi) K の頂点

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

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

46 計算実験 ・言語： C ・ マシン： パソコン PentiumIII 500MHz ・ OS＆コンパイラ： Linux、gcc
・ 一般グラフ、2部グラフの問題を解いた ・ 通常のランダムグラフでは面白い実験ができないので、 添え字が近い頂点にしか枝を張らないランダムグラフを作った。

47 新旧アルゴリズムの比較

48 新旧アルゴリズムの比較 (2)

49 ２部グラフの場合

50 次数の変化に対する挙動 ※　だいたい、次数の２乗に比例

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

52 results

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

54 コードレスサイクルの列挙

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

56 化合物の立体構造の推定 (2) ・ 推定する化合物と部分的な平面構造が一致する化合物をデータベースから探し出す  大域的な構造が拾えない
　 大域的な構造が拾えない ・ 検索結果を、環構造の複雑さ 　　で絞り込む 　 立体構造の要因が入り、精度が増す グラフのサイクルを列挙することで、どのような サイクル構造を持つか、全て調べ上げる

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

58 サイクル列挙の既存研究 － 1972年に、Read & Tarjan による初の多項式時間アルゴリズム （１つあたり O（|E|）時間）
－ 2000年あたりから、グラフのパス／サイクルを 　　　列挙するモデルが出始める － 2003年に宇野のコードレスサイクルを列挙するアルゴリズム ※ コードレスサイクル： 　　 コードを持たないサイクル

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

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

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

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

63 ・ ランダムグラフを作り実験（1パターンあたり1回） ・ 1万個あたりの計算時間
実験結果（計算時間） ・ ランダムグラフを作り実験（1パターンあたり1回） ・ 1万個あたりの計算時間 10% 40% 70% 80% 90% 100 0.17 0.09 0.10 0.12 200 0.18 0.11 400 0.15 0.26 800 0.2 0.13 0.54 1600 0.24 0.21 0.29 1.30 3200 0.19 0.25 0.61 1.79 密度 頂点数

64 ・ コードレスサイクルと、普通のサイクルの数の比較
実験結果（コードレスサイクル数） ・ コードレスサイクルと、普通のサイクルの数の比較 10% 30% 50% 70% 90% 10 3 4 20 352 45 3697 81 108906 15 34 1470 165 247 - 350 1 298 637 771 908 25 8 2049 2099 1775 1928 密度 頂点数

65 実験結果（コードレスサイクル数 その２） ・ コードレスサイクル数 10% 30% 50% 70% 90% 50 64383 267435
82607 34137 18873 75 221990 73810 100 - 877466 199133 150 200 300

66 化学シフト値予測システムに組み込み ・ 化学シフト値：核磁気共鳴で原子核の解析をする際に得られる、原子の観測値の1つ
・ 局所的な、立体的な構造により、変化するため、化合物の構造を解析する際に用いられる（化学シフト値から、経験と過去の解析結果から、構造を予測する） ・ 化学シフト値を精度よく予測すると、立体構造を精度よく予測できる

67 化学シフト値予測システムに組み込み (2) ・ CASTシステム：佐藤 寛子 (NII), 越野 広雪 (理研)
立体構造も考慮した、化合物データベース 1. 化学シフト値を予測したい化合物の各原子に対して、 局所的な平面構造が等しく　＆　環構造が似ている 化合物の原子をデータベースから検索 2. 検索でヒットした原子の化学シフト値の平均で予測する （環構造が類似 ＝ 各長さに対し、含まれる環の数が類似） （局所構造のみ見たい ＆ 全ての環を考慮すると、オーバーフィット　　コードレスサイクルが都合よい）

68 化学シフト値予測システムに組み込み (3) ・ 実験結果

69 まとめ ・ データ中心の科学： あいまいな目的と不ぞろいなデータ ・ 列挙による解析は多面的
・ データ中心の科学：　あいまいな目的と不ぞろいなデータ ・ 列挙による解析は多面的 ・ 出力数依存アルゴリズム、解数の小さいモデルの重要性 ・ クリーク列挙の、末広がり性の利用による高速化 ・ 極大クリーク列挙：枝刈りと逆探索 ・ 分割法によるコードレスサイクルの列挙 ・ データマイニングなどでの応用を意識した、より複雑なモデルに対する高速アルゴリズムの開発 ・ツールとしての完成度を高める（解の圧縮など）