大規模データ処理に対する アルゴリズム理論からのアプローチ 宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2007年4月23日 第20回 回路とシステム軽井沢ワークショップ

データ中心科学の発達

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

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

複雑かつ大量の計算を効率良く行う手法の開発が重要 データ処理の変化 ▪ 不ぞろいなデータから有用な情報を得るには複雑で豊かなモデルを解く必要がある ▪ そのためには、解く問題を複雑にする必要がある 　　▪ 比較・統計量  全対比較・組合せ的な統計量 　　▪ キーワード検索  パターンマイニング 　　▪ 完全一致  類似検索 　　▪ 最適化  列挙 ・ このように処理が変化すると、既存のアルゴリズムを用いて行った場合に、非常に時間がかかることがある 例） 全対比較を通常の検索を用いて行うと、レコード数だけのクエリを必要とする データベース 複雑かつ大量の計算を効率良く行う手法の開発が重要

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

より高度な解析のため、より複雑な基礎処理アルゴリズムが必要 　今、巨大データにできること ・ データベースの構築（データ構造） ・ キーワード検索 ・ ソート、整列 ・ フィルタリング ・ 統計量の計算 ・ 圧縮 ・ 最短路検索 ．．． １次的な処理が多い。組合せ的な構造を処理するものは少ない より高度な解析のため、より複雑な基礎処理アルゴリズムが必要

類似文字列の列挙

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

問題が大きいので、平均的な意味でよいので、 計算オーダーの小さいアルゴリズムがほしい 類似項目発見の計算時間 ・ 似たもののペアを全て見つけるさい、項目のペア全てについて、単純に全対比較を行うと項目数の２乗の時間がかかる 　　項目数が100万を越えるころか現実的には解けなくなる 　　　100万×100万 ÷100万（演算per秒） = 100万秒 ・ 類似検索を使う手もあるが、100万回のクエリを実行しなければならない。類似検索は完全一致より大幅に時間がかかる 　 1秒間にクエリが1000回できるとして、1000秒 問題が大きいので、平均的な意味でよいので、 計算オーダーの小さいアルゴリズムがほしい

応用１：似ているwebページの発見 ・ web 検索を行うと、よく似た内容、あるいは引用しているものを多量に見つけることがある 　　ニュース記事、レビューの記事の一部など ・ あらかじめ、類似しているページをグループのように検出できれば、こういった似たものをひとくくりにでき、検索エンジンの効率化にもつながる （検索結果を出してから似たものを見つける、という方法もあり） ・ さらに、例えば、最近のホットな話題は何ですか、 　　　というような検索もできるかもしれない

応用２：リンクが似ているwebページ ・ リンク先、あるいはリンク元が、集合として似ているページは、よく似ていると考えられる 　　サッカーのページ、料理のページ、地域のページ ・ グループ化すれば、コミュニティー発見、著名なトピック、web の構造の解析など、いろいろなことがやりやすくなる ・ さらに、例えば、「スパムサイト」の検出にも使えるかも 　（レポート課題のコピーの検出、とか）

応用３：長い文章の比較 ・ （文庫本のような）長い文章がいくつかあるときに、類似する部分がどことどこにあるかを検出したい 　 長い文章の比較はそれ自体が大変（時間がかかる）ので、複数あると手が出ない ・ 長い文章を、短い文字列にスライスし、全体を比較する 　 大域的に似た部分は、局所的に似ている 　　　　ところを多く含むと思われる 　　　つまり、似ている短い文字列のペアを多く含む ・ 短い文字列の全対比較からアプローチできる

応用４： ゲノムの比較 ・ 異なる種のゲノムを比較して、類似するところを見つけ出したい － ２つの染色体の比較（1億文字以上） 応用４：　ゲノムの比較 ・ 異なる種のゲノムを比較して、類似するところを見つけ出したい 　－　 ２つの染色体の比較（1億文字以上） 　－　複数の、短い染色体の比較（バクテリアなど：400万程度） 　－　 両方とも、ゲノムをスライスして全対比較する ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

応用５： 特異的な部分を見つける ・ 似ているものがない項目は、データの中で特異的な部分と考えられる 　 － 携帯電話・クレジットカードの不正使用 　 － 制御システムの故障・異常の発見 　 － 実験データから新しいものを発見 　 － マーカーの設計 （「宇野毅明のホームページは、”助教授，宇野毅明の研究”で検索するとユニークに定まる） ・ 比較的大きなデータが複数あるような場合でも、特異な項目を多く含むもの、他のどのデータとも、似ている部分が少ないものは、特異なデータだと考えられる ・ 「似ている項目の数」は、データがエラーを含む際の統計量として使えるかも知れない

応用５＋： マイクロアレイのデザイン ・ マイクロアレイは調べたいDNAに、ある特定の短い文字列（20文字程度）が含まれているかどうかを検出する実験装置（いっぺんにたくさん実験できる） ・ 特定の遺伝子（あるいは変化）が含まれているか、たくさんの微生物が含まれているコロニーの中に、特定の生物種がいるか、といったことを調べる際に使われる ・ 短い文字列が、他の場所にも含まれていると、検出が効率良くできない  固有の短い文字列があらかじめわかっているとうれしい

問題設定：短い文字列の比較 ・ 具体的に見るため、扱うデータベースと問題を具体化する 問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデータベースを入力したときに、文字列のペアで異なり数が d 文字以下である組を全て見つけよ （ハミング距離がd 以下） ・ 長くて、ある程度似ている文字列は、このような似ている部分列をある一定数以上含む ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

問題の難しさ ・ 全ての項目が同じだと、およそ(項目数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 。回出力される 　 重複を回避する必要がある ・ 各見つかったペアについて、選択されていないブロックが選択したブロックの間にあったら出力しないようにする 　 等しいブロックが一番左端によっている場合にのみ出力 メモリに解を保持せずとも、重複が回避できる

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

実験：長さ20文字で異なり数 d を変化

ゲノムの比較 染色体と染色体を比較する － 1億以上の文字列の比較になるので、非常に時間がかかる 　－ 1億以上の文字列の比較になるので、非常に時間がかかる 　－ アラインメントでは部分が入れ替わった構造が見つけられない ・ 比較するゲノムを、オーバーラップするようにスライスし、全対比較 ・ 縦横に比較するゲノムをおき マトリクスを作って類似するペアが あるセルの色を白くする （実際は細長い四角でいい） 類似する構造が見える

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

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

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

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

ゲノムの読み取り ・ ゲノム配列は、そのままひも状のものを一度に読むことはできない。通常、一度に500文字程度しか読めない。 ・ そこで、染色体を10万文字程度の長さにぶつ切りにし、大腸菌に移植して増殖させる ・ 増殖したものをさらにぶつ切りにし、500文字程度ずつ読み、つなげる（できたものをBAC配列と言う） ・ BAC配列をさらにつなげて、もとの染色体を作る

重なり部分の検出 ・ 短い配列を読んだとき、あるいはBAC配列を作ったとき、それがもとの染色体、BAC配列のどの位置にあったかはわからない  配列を構成する際に使える情報は「どことどこが重なるか」 ・ 機械の読み取りエラーや大腸菌が増殖する際のコピーミスも起こりうるので、「完全に重なる」ではなく「だいたい重なる」でなければいけない ・ BAC１つ作るのに、100-1000万文字の比較が必要

BAC配列の比較 ・ ゲノム全体の配列を決める際には、BAC同士がどのようにつながるかを調べる必要がある ・ しかし、どの配列とどの配列がオーバーラップしているか調べるのは、大変。（前述のアセンブリをミスしていると、微妙に異なるところが出て、重ならなくなる） ・ 既存の手法は、直接的でない 手段を使って比較をしていて、 ときどきオーバーラップしそうな ところを落としてしまう ・ この手法なら全対比較可能 PCで 1ペア1秒

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

類似部分（アイテム）集合の列挙

D が巨大かつ疎で（各Ti が平均的に小さい）、出力の数がそれほど多くない（ ||D|| の数倍）状況での高速化を考える 問題の定義 入力： 部分集合族（トランザクションデータベース） D = {T1,…,Tn} （ ただし、各 Ti はアイテム集合 E = {1,…,n} の部分集合） 　　＋ 閾値 θ 出力： |Ti∩Tj| がθより大きいような、 　　　　　全てのTi 、Tjのペア 例： 閾値 θ=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 ＝ D が巨大かつ疎で（各Ti が平均的に小さい）、出力の数がそれほど多くない（ ||D|| の数倍）状況での高速化を考える

単純に全対比較すると 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 ・ 単純に全対比較するアルゴリズムを考える for i=1 to |D|-1 　for j=i to |D| 　if |Ti∩Tj|≧ θ then output (Ti, Tj ) ・ 共通部分の計算は、各 Ti をアイテム順でソートしておき、Ti 、Tjをマージソートのように並行してスキャンすればよい。 　　時間はO(|Ti |＋| Tj|) ・ 全体の計算時間は ∑i,j(|Ti |＋| Tj|) = 2n ||D|| D ＝ かなり時間がかかると見てよい

振り分けによる高速化 ・各Ti に対し、|Ti∩Tj|がθ以上になるものを見つける問題を考える ・ 各アイテム e に対して、e を含む部分集合の集合を D(e) とする ・ Ti が含む各 e に対して、D(e) の各 T に対して、カウントを１つ増やす、という作業をする  全ての e∈Ti についてこの作業をすると、各 Tj のカウントは |Ti∩Tj| になる for each e∈Ti for each Tj∈ D(e), j>i, do c(T)++ ・ D(e) を添え字順にソートしておくと、j>i である 　　Tj∈ 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 ＝

振り分けの計算時間 for each e∈Ti for each Tj∈ D(e), j>i, do c(T)++ ・ 計算時間は ∑j ∑e∈Ti |{ Tj∈D(e), i<j}| ＝ ∑e |D(e)|2  |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 ＝

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

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

簡単に追加できる条件 ・ |A∩B| が、|A| のα倍以上 、(and/or) |B| のα倍以上 ・ |A∩B| / |A∪B| ≧ α など。 この手の、共通部分や和集合の大きさから計算できる評価値であれば、簡単に評価できる ・ 計算時間は、ほぼ線形で増えていくと思われるので、多少大きなデータでも大丈夫であろう

その他列挙的なアルゴリズム

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

まとめ ・ データマイニングなどでの応用を意識した、より複雑なモデルに対する高速アルゴリズムの開発 ・ データ中心の科学：　あいまいな目的と不ぞろいなデータ ・類似する項目のペアを列挙する出力数依存型のアルゴリズム 　　異なりの場所に注目し、分類による絞込みを行う ・ 部分的な比較を用いて、大域的な類似構造を検出するモデル ・ ゲノムの比較： 　　　ヒト、チンパンジー、マウスの染色体の比較 　　　バクテリアゲノムの多対多比較 　　　アセンブリングの高速化 ・ データマイニングなどでの応用を意識した、より複雑なモデルに対する高速アルゴリズムの開発 ・ツールとしての完成度を高める（解の圧縮など）