ダウンロード

大規模データに対する
高速類似性解析手法の研究
宇野毅明（国立情報学研究所
＆総合研究大学院大学）
2011年3月16日 JSTさきがけセッション
知識獲得における基礎計算
• データから知識を取り出すには、良いモデルが重要
• 良いモデルを効率良く解くには、良いアルゴリズムが必要
• 中くらい基礎的で、知識獲得に良く現れるような問題に対し、高速
なアルゴリズムを作るのが本研究の目的
研究のゴール：巨大なデータに対しても効率良く動くデータ
処理アルゴリズムを構築するための構築理論の解明
• やがては「大規模問題のアルゴリズム基礎」という分野を作りたい
計算
データベース
実験1
●
●
●
▲
●
実験2
▲
●
●
●
●
●
▲
▲
実験3
▲
実験4
▲
▲
▲
▲
▲
実験結果
▲
●
●
●
●
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
知識
• 実験1● ,実験3 ▲
• 実験2● ,実験4●
• ATGCAT
• 実験2●, 実験3 ▲, 実験4●
• 実験2▲ ,実験3 ▲
• CCCGGGTAA
．
• GGCGTTA
．
• ATAAGGG
．
．
．
．
どうして大規模データ？
• Web サーチのように「全てのデータを取っておくこと」に意味があ
るのでない限り、データを大量に保存せずともいいんじゃない？
 データ解析して全体的な傾向を見るのなら、ある程度たくさん
あつまれば十分でしょ？（世論調査、出口調査、、、）
• 統計理論が発達してるので、少ないデータでも全体の傾向を十
分に捕らえられるようになってきている（1億件  1万件）
 大規模データの蓄積は不要？？？
• 全体的なものに関しては、確かにその通り。
でも、部分的な特徴は、大規模データが必要
エラーの訂正
• OCR（スキャナ）で文章を読みました
「実は大規撲データの解析で、、、」
 まちがってる
• と思いきや、「実は大規撲データの解析で大関の、、、」だったり
すると、「実は大相撲データの解析で大関の、、、」となるべき
 前後を見ないと、何が正解か分からない
 意味を解析しないと分からない？？？
• でも、事例があれば推測はできる
「先月の大相撲データの解析で大関の取り組みが、、、」
「実は大相撲データを解析を大関の成績にあてはめて、、、」
• 「大の次に何が来る可能性が高いか」程度の統計では難しい
数の暴力
• ゲノム情報の読み取りはエラーがつきもの。いろいろな方法で精
度を高めようとするが、、、
自信がない
自信がない
….ATCCGCTAGGTGAATATGCGC…
….ATCCGCTAGGAGAATATTCGC…
….ATCCGCTAGGAGAATATGCGC…
….TTCCCCTAGGGGAATATTCGC…
….ATCCGCTAGGAGAATATTCGC…
….ATCCGCAAGGAGAATATTCGC…
….ATCCGCTAGGAGAATATCCGC…
• 気にせずに、たくさん読んでしまえばいい！！
どうして使わないの？
＋大規模データの利用で（ある種自動的に）精度を高められる
＋非常にまれな（1万分の1）事象でも、1億件のデータでは1万件
もある（解析するのに十分）
• なのに、それほど大規模データをがんがんと解析しているわけで
はない（企業には、眠っているデータが山ほど）
• 大きな理由は、
 1億件のデータの、どれとどれが似ているかを調べるには、1
億×1億／２のチェックが必要。一秒に1億回比較しても2年くらい
かかる
• 実際はもっといい方法を使うが、それでも1週間とか。
（大量の似たものグループを見つけるなど、とてもとても、となる）
何の計算をする？
• 計算が大変。では何の計算を速くする？
 「検索」と同じように、まずは基礎的な問題から取り組みたい
• 前にも述べたように、知識のない大規模データでは、「関係性」
がベースになることが多い
 「関係性の計算」が問題設定としていいだろう
• ただし、単に２つのものの関係性を高速に計算するのではなく、
「重要な関係がどこにあるか」を調べる方がよい
 全ての組を扱う時点で破綻
 類似性の場合、「似ている組」に興味があり、「似てない組」が
どれくらい似ていないかには興味はない。そして、「似ている組」の
数はたいていとても少ない（短時間で扱える！）
類似性∈関係性
• 「関係性」にもいろいろあるが（包含、相補・対極、強弱…）、そ
の中でも、情報処理では「類似性」がとてもよく使われる
 例えば「クラスタリング」は、通常類似性に基づいて行われる
問題与えられたデータの、似た項目のペア（組）を全て見つけよ
• どのようなデータを扱うか（文字列、パケット、遺伝子、画像…）、
どのような類似性の尺度を用いるかで、多種の問題がある
問題の難しさ
• 簡単な問題設定だが、意外と難しい
 ペアの数がとても大きいので、似てないペア（組）をちょっとで
もチェックした時点でもう動かない
• 類似度には「順位」がない
 順位付けできるよう数値化されるのであれば、小さい順に並
べることで、似た値を持つ物が簡単に見つかる
• いかに「望みのないペアを見ないようにするか」がポイント
 例えば、探索や分類、絞り込みを基本として、
枝刈りを行うようなタイプが望ましい
枝刈りと分類
• 枝刈り：木のように分かれていくルートを探索するとき、探索して
も解の見つかる見込みのない枝を切り落とすこと
• 分類：比較して意味があるものが集まったグループに全体を分
ける
短い文字列の比較
• うまくいった例として、類似する文字列のペアを全て見つけるア
ルゴリズムを紹介
問題：各項目が同じ長さ l の短い文字列（50文字程度）である
データベースから、文字列のペアで異なり数（ハミング距離）が d
文字以下である組を全て見つけよ
• 長い文字列から長さ 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回＋α で解ける。全対比較よりもかなり高速
・・・
例題
• ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミ
ング距離が1以下のものを求めよ
ABCDE
ABDDE
ADCDE
CDEFG
CDEFF
CDEGG
AAGAB
A
A
A
C
C
C
A
BCDE
BDDE
DCDE
DEFG
DEFF
DEGG
AGAB
A
A
A
C
C
C
A
BC
BD
DC
DE
DE
DE
AG
DE
DE
DE
FG
FF
GG
AB
ABC
ABD
ADC
CDE
CDE
CDE
AAG
DE
DE
DE
FG
FF
GG
AB
実験：長さ20文字で異なり数 d を変化
人のY染色体から部分配列をとって実験。PenMのノートPC
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文字)
マウスゲノムとヒトゲノムの類似領域
• マウスの染色体全部とヒトの染色体全部を比較。長さ50、異な
り数1、計算時間は10時間ほど
ACATTTGGTACAAATCCACTCTTCACCCCTTCCCAGCCCTCCTGGATTGTAATC
TCCCCCCTTTTAACCAGCTCATATATGTCTCTTGTCAGGTCTGTGAAGGCTTTC
TCCACATTAATGGCATCTCGGGCTGACGTTTCAATGTACTTCATGCCGTATGCA
GCAGCCAGTTTCTCGGCCTCGTGGCGAGTCACTTGCCTCTGTGTATCCAGGTCA
CACTTGTGACCCACCAGAACAAATACAATTTGGTAGGGCTGAACGTGTACTTTG
GTCTCTTCTAACCACTCATGGACATTCTGGAAGGACCTGCGGTTGGTAATGTCA
AATAAGAGAAGACCACCTACTGAGTTCCTGTAGATGTCAAATAAGAGAAGACCA
CCTACTGAATTCCTGTAGTAGGCGCGAGTGATGGATCTAAAACACAAGAAAGAA
GTAAAGAGTAAAG
• 300文字以上の類似領域がいくつも見つかる。既存手法では、
エラーのないつながりしか見つけられなかった。
応用：たくさん現れる文字列
• マウスゲノムの一部（150万文字)の似てる部分を調べ上げ、多く
の場所に現れるパターン文字列を発見（5分ほど）
#T#GCAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTTATGATATCTGA
#TTGCAAAGGCTTTACCACATTGATTACATTCATAAGGTTT#TCTCCAGTATGG#TTCTTTTATGATATCTGA
GAC#A#TGTGACAGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT
GATTACTGTGA#AGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT
#TGATATCTGAGACTA#TGTGACAGGAAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTA
ATGA#ATTGGAGAT#A
TGGGTTCTTTTATGATAT#TGAGAC#A
#TCTCTGAA#AAAGAAAT#AAAGAAGATCTCAGAAGATGGAAAGATCTCCCATGCTCAT#GATTGGCAGGATC
AATATAGTAAAAATGGCTATCTTGCCAAAAGCAATCTACAGATTCAATGCAATCCCCATCAAAAT#CCAACT#
AATTCTTCA
• # は多数決が決まらない場所、計算時間は10秒ほど
Webテキストからマイニング
• Webテキストで同じことをしたもの (200万文字、10分)
#組の成立となりました。## #月１#日（土）男性１２名：女性１#名のご参加
で、５組の成立となりました。## ４月７日（土）男性#０名：女性#
##，###円（税別、送料別）ＰａｕｌＳｍｉｔｈＭｅｎ’ｓ／ポールスミスメンズ
サイズフェイス：Ｈ約４．５ｃｍ×Ｗ約３．#ｃｍ、厚み約#．#ｃｍ（リューズ除
く）ベルト：幅約２．#ｃｍ腕まわり：最大約###
#年０#月２００#年０#月２００６年０#月２００６年０#月２００６年０#月２００６
年０#月２００６年０#月２００#年０#月２００#年１２月２００５年…
• 面白い物が見つかる。既存のデータマイニング手法では、ちょっと
ずつ違う解が大量に出るし、何年かかっても計算が終わらない
まとめ
• 大規模データの「数の暴力」で効果的なデータ利用をしよう
• 何も知識がないところでは、「相互関係」しか頼るものがない
• 類似性を見つけることは、データ解析の基礎。速く計算できれば
いろいろな目的に、大規模データが使えるようになる
• 速い計算のためには、枝刈り、分類などのアルゴリズム技術を
使うことが大事。文字列は分類で何万倍も速くなる
• ゲノム比較（大きい類似部分の抽出）、テキスト比較（頻出するフ
レーズの検出）など、応用の仕方でいろいろな使い方ができる
• 実装（プログラム）は宇野のホームページに
(http://research.nii.ac.jp/~uno/codes-j.html) 「宇野毅明」「公開プ
ログラム」「データマイニングの簡単」「mace クリーク」などで検索

Download Report