Document

大規模データ処理に対する
アルゴリズム理論からのアプローチ
宇野毅明（国立情報学研究所
＆総合研究大学院大学）
2007年4月23日第20回回路とシステム軽井沢ワークショップ
データ中心科学の発達
データ中心の科学
・近年、IT技術の発達で、大規模なデータが半自動的に収集で
きるようになった
（POS、web、文書、顧客データ、財務、利用者、人事…）
既存のデータを使って何かを得たい
データの選別
モデル化
データ処理
いわば、データを出発点とした問題解決の科学
（人工知能、データマイニング、自然言語処理、セマンティックweb…
近年の情報学でもメジャーな研究スタイル）
データ中心科学の特徴
・データが整形されていない
目的がはっきりしない、あるいは異なる目的のために集められたデータを用いるため、
必要なものがすぐ取り出せるとは限らない。また、ノイズや不正確な情報も含まれうる。
・目的関数があいまい
データが情報の塊のようなものなので、そこから得られるものはやはり情報であること
が多い（知識、特徴分析といったもの）。それら情報の価値は数理的な尺度では計りにく
い。また、従来の最適化とは異なる尺度を用いることが多い。（グラフクラス、シークエ
ンス、情報量、隣接性、類似度、頻出度・・・）
・データが巨大で、構造を持つ
半自動で集められたデータであるので、データは通常、巨大である。しかし各
項目が持つ属性は少なく、疎である。
・データ処理は比較的簡単なものが多い
データ処理の計算は、最適化のような複雑ではなく、
組合せの検索や整形などいくつかの簡単な処理の組合せ
データ処理の変化
▪ 不ぞろいなデータから有用な情報を得るには複雑で豊かなモデ
ルを解く必要がある
▪ そのためには、解く問題を複雑にする必要がある
▪ 比較・統計量  全対比較・組合せ的な統計量
▪ キーワード検索  パターンマイニング
▪ 完全一致  類似検索
データベース
▪ 最適化  列挙
・このように処理が変化すると、既存のアルゴリズムを用いて行っ
た場合に、非常に時間がかかることがある
例）全対比較を通常の検索を用いて行うと、レコード数だけのクエ
リを必要とする
複雑かつ大量の計算を効率良く行う手法の開発が重要
アルゴリズム理論の利点
・大規模な計算には、アルゴリズム理論に基づいた技術が有効
 アルゴリズム理論による高速化は、問題の大きさに対する計算
時間の増加を抑える
 計算の結果は変化しない
100項目
100万項目
2-3倍
10000倍
データが巨大になるほど、アルゴリズム改良の加速率は上がる
今、巨大データにできること
・データベースの構築（データ構造）
・キーワード検索
・ソート、整列
・フィルタリング
・統計量の計算
・圧縮
・最短路検索
．．．
１次的な処理が多い。組合せ的な構造を処理するものは少ない
より高度な解析のため、より複雑な基礎処理アルゴリズムが必要
類似文字列の列挙
データベースから類似する項目を見つける
・データベースの項目の中で、似た項目のペアを全て見つけたい
（項目のペア全てについて、
2項関係が成り立つかを調べる）
・類似している項目の検出は、
データベース解析の基礎的な手法
 基礎的なツールがあれば、使い方しだいで
いろいろなことができる
（大域的な類似性、データの局所的な関連の構造・・・）
類似項目発見の計算時間
・似たもののペアを全て見つけるさい、項目のペア全てについて、
単純に全対比較を行うと項目数の２乗の時間がかかる
 項目数が100万を越えるころか現実的には解けなくなる
100万×100万 ÷100万（演算per秒） = 100万秒
・類似検索を使う手もあるが、100万回のクエリを実行しなければ
ならない。類似検索は完全一致より大幅に時間がかかる
 1秒間にクエリが1000回できるとして、1000秒
問題が大きいので、平均的な意味でよいので、
計算オーダーの小さいアルゴリズムがほしい
応用１：似ているwebページの発見
・ web 検索を行うと、よく似た内容、あるいは引用しているものを
多量に見つけることがある
 ニュース記事、レビューの記事の一部など
・あらかじめ、類似しているページをグループのように検出でき
れば、こういった似たものをひとくくりにでき、検索エンジンの効率
化にもつながる
（検索結果を出してから似たものを見つける、という方法もあり）
・さらに、例えば、最近のホットな話題は何ですか、
というような検索もできるかもしれない
応用２：リンクが似ているwebページ
・リンク先、あるいはリンク元が、集合として似ているページは、
よく似ていると考えられる
 サッカーのページ、料理のページ、地域のページ
・グループ化すれば、コミュニティー発見、著名なトピック、web
の構造の解析など、いろいろなことがやりやすくなる
・さらに、例えば、「スパムサイト」の検出にも使えるかも
（レポート課題のコピーの検出、とか）
応用３：長い文章の比較
・（文庫本のような）長い文章がいくつかあるときに、類似する部
分がどことどこにあるかを検出したい
 長い文章の比較はそれ自体が大変（時間がかかる）ので、
複数あると手が出ない
・長い文章を、短い文字列にスライスし、全体を比較する
 大域的に似た部分は、局所的に似ている
ところを多く含むと思われる
つまり、似ている短い文字列のペアを多く含む
・短い文字列の全対比較からアプローチできる
応用４：ゲノムの比較
・異なる種のゲノムを比較して、類似するところを見つけ出したい
－２つの染色体の比較（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以下のものを求めよ
A
A
A
E
F
A
G
B
B
C
F
F
F
A
C
D
C
G
G
G
B
G
A
A
A
E
F
A
A
B
B
C
F
F
F
B
C
D
C
G
G
G
A
A
A
A
E
F
G
B
C
B
F
F
F
A
C
C
D
G
G
G
B
A
A
A
A
E
F
G
B
B
C
F
F
F
A
C
D
C
G
G
G
B
重複の回避
・まったく同じ文字列があると、全てのブロックの組合せで見
つかるので、 kCd 。回出力される
 重複を回避する必要がある
・各見つかったペアについて、選択されていないブロックが選
択したブロックの間にあったら出力しないようにする
 等しいブロックが一番左端によっている場合にのみ出力
メモリに解を保持せずとも、重複が回避できる
イメージ的には
・似ているもののペアを探す問題は、マトリクスのセルの中で必
要なものを全て見つける問題
・全対比較は、マトリクスのセルをすべて見ていることに対応
・分類によるアルゴリズムは、
分類を順々にしていると思えば、
木構造の探索を行っていることに対応
実験：長さ20文字で異なり数 d を変化
10000
1000
d=0
d=1
d=2
d=3
10
20
00
70
00
22
95
3
0.1
70
0
1
20
0
計算時間(秒)
100
長さ(1000文字)
ゲノムの比較
染色体と染色体を比較する
－ 1億以上の文字列の比較になるので、非常に時間がかかる
－アラインメントでは部分が入れ替わった構造が見つけられない
・比較するゲノムを、オーバーラップするようにスライスし、全対比較
・縦横に比較するゲノムをおき
マトリクスを作って類似するペアが
あるセルの色を白くする
（実際は細長い四角でいい）
類似する構造が見える
ゲノムの比較 (1)
ヒト21番染色体とチンパンジー22番染色体の比較
・長さ3000万の配列×2 から、30文字の切片を3000万個取る
・似ている部分配列のペアの数に応じて、各ドットの明るさを変える
ヒト 21番染色体
・白い部分が
「似ている可能性のある部分」チ
ン
・黒い部分が
パ
「(絶対に)似ていない部分」ン
ジ
・格子模様は、繰り返し
配列を拾っている
PCで 1時間で可能
ー
22
番
染
色
体
ゲノムの比較 (2)
ヒトX染色体とマウスX染色体の比較
・ 30文字で間違い2文
字以下のペアを列挙
・長さ3000、幅300
の領域に3つペア
があれば点を打つ
PCで 1時間で可能
X
・ノイズをかなり
除去できている
マ
ウ
ス
染
色
体
ヒトX番染色体
ゲノムの比較 (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 = {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)
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
D が巨大かつ疎で（各Ti が平均的に小さい）、出力の数がそれ
ほど多くない（ ||D|| の数倍）状況での高速化を考える
単純に全対比較すると
・単純に全対比較するアルゴリズムを考える
D ＝
for i=1 to |D|-1
for j=i to |D|
if |Ti∩Tj|≧ θ then output (Ti, Tj )
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
・共通部分の計算は、各 Ti をアイテム順でソートしておき、Ti 、Tj
をマージソートのように並行してスキャンすればよい。
時間はO(|Ti |＋| Tj|)
・全体の計算時間は ∑i,j(|Ti |＋| Tj|) = 2n ||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) を見つけるのも簡単
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 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)| が平均的に小さければ、かなり速い
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
1再帰呼び出しの計算時間のイメージ
・共通部分による計算は
D(e) と D(e) のをスキャンする
 D(X) を n-t 回スキャンし、
データベースの t より大きな
アイテムをスキャンする
・振り分けは D(X) に含まれるトラン
ザ
クションの t のをスキャンする t より
大きなアイテムをスキャンする
＋
t
t
(n-t)個
計算実験
・ webリンクのデータの一部を使用
－ノード数 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| ≧ α
・ |A∪B| －|A∩B| ≦ θ
など。
この手の、共通部分や和集合の大きさから計算できる評価値
であれば、簡単に評価できる
・計算時間は、ほぼ線形で増えていくと思われるので、多少
大きなデータでも大丈夫であろう
その他列挙的なアルゴリズム
クリーク列挙問題
グラフのクリーク：部分グラフで、全ての頂点間に枝があるもの
(２部クリーク：完全２部グラフになっている部分グラフ)
・クリークは、グラフの中の密な構造をあらわす
クラスタ、コミュニティーなどをあらわす
・極大クリークの列挙は比較的高速にできる(秒速10万個）
・クリークっぽい構造の列挙もできる
頻出パターンの列挙
・データベースの中に多く現れるパターンを頻出パターンという
 データの解析、特徴分析、知識・ルール発見に使える
データベース
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
頻出する
パターンを抽出
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
・実験1● ,実験3 ▲
・実験2● ,実験4●
・実験2●, 実験3 ▲, 実験4●
・実験2▲ ,実験3 ▲
．
．
．
・ ATGCAT
・ CCCGGGTAA
・ GGCGTTA
・ ATAAGGG
．
．
．
・グラフ、木、文字列、時系列など、多くのパターンが扱える
・頻出パターンの列挙は、通常非常に高速で行える
・極大性を考慮することで効率よい計算ができる
各種サブグラフ列挙問題
列挙問題：与えられた問題の解を全て重複なく見つけ出す問題
・グラフの2点間を結ぶパス
・グラフのサイクル
・部分木
・マッチング
・全張木
A
・高速だが、解の数が大きい
・サイクルの代わりにコードレス
サイクルを使う、といった工夫が必要
B
…
まとめ
・データ中心の科学：あいまいな目的と不ぞろいなデータ
・類似する項目のペアを列挙する出力数依存型のアルゴリズム
異なりの場所に注目し、分類による絞込みを行う
・部分的な比較を用いて、大域的な類似構造を検出するモデル
・ゲノムの比較：
ヒト、チンパンジー、マウスの染色体の比較
バクテリアゲノムの多対多比較
アセンブリングの高速化
・データマイニングなどでの応用を意識した、より複雑なモデルに
対する高速アルゴリズムの開発
・ツールとしての完成度を高める（解の圧縮など）

Download Report