構造化・非構造化データの特異な部分構造の検出 区 分 ： 甲

（別紙様式２）
氏
名
：
谷口
雄太
論文題名
： 構造化・非構造化データの特異な部分構造の検出
区
：
分
甲
論
文
内
容
の
要
旨
人類が蓄積しているデータは膨大な量に及 んでおり，この蓄積を利活用するための基盤技術の
確立が強く求められている．これらのデータは，内容・形式ともに多岐に渡っているが，大きく
構造化データと非構造化データの 2 つに分けられる．非構造化データには，例えば文書などのテ
キストデータ，音声データや自然現象を観測した時系列データなどがある．これらは明示的には
構造をもたず，連続した記号や事象などの単純な列，すなわち, 文字列と見なすことができる．
他方，構造化データには，例えば原子同士の結合を表す分子構造，論文の共著関係など人間同士
の関係を表すソーシャルネットワークなどがある．こうした明示的な構造をもつデータの多くは，
異なる 2 つの実体間の関係を集めたもの，すなわち，グラフと見なすことができる．今日では，
文字列とグラフは，計算機科学において様々なデ ータを抽象的に取り扱うための基本的な表現と
して用いられている．
大量データ利活用のためには，構造化・非構造化データのどちらにおいても，データの中に埋
没したより高次の部分構造を捉えることが重要である．例えば，テキストデータは文字の並びで
あるが，その意味を把握する場合には単語の列と見なす必要があり，さらに 高次の意味を捉える
ためには，文の列など，より高次の構造について解析する必要が出てくる．同様に，例えば，
ソーシャルネットワークの中に築かれるコミュニティを見つけることは社会学，マーケティング
において有用である．
こうした部分構造の検出に関する既存研究の多くは，部分構造のもつ特異性に基づいて検出を
行っている．これら既存手法は，専門家による領域知識を利用するものとそれ以外とに分けられ
る．前者のアプローチでは，領域知識を活用することで精度が高くなる反面，コストが高く，未
知のデータに対応できないという問題がある．一方，後者 のアプローチでは，大きなコストをか
けず未知データを含む様々なデータに普遍的に適用でき，より発見的な結果を期待することがで
きる．本研究では，構造化・非構造化データそれぞれに対し，データに隠れた部分構造を後者の
アプローチで検出する問題に取り組んだ．その結果，(1) Purity尺度によるゲノム配列上の水平
伝播遺伝子の発見，(2) アルファベットサイズの大きい文字列に対するPurity尺度の改良，(3)
ノイズに対し頑健なグラフクラスタリング手法の提案，という研究成果をあげた．
(1)では，文字列の部分文字列の特異性を測る尺度として，Yamadaら(2012)によって提案された
Purity尺度に着目し，複数の細菌ゲノムの配列においてPurity尺度が水平伝播遺伝子と呼ばれる
遺伝子を特徴付けることを明らかにした．細菌などの微生物には，通常の生殖とは異なる遺伝子
伝播メカニズムである水平伝播が存在する．水平伝播により獲得された遺伝子を特定することは，
ゲノムの理解や進化の過程の解明に繋がるため重要視されている．本研究では ，実験および配列
マップや配列注釈を用いた評価を通して，RNAやトランスポゾン，モバイルエレメントやファージ
など，水平伝播したと考えられる遺伝子が，Purity尺度により高いスコアを与えられることを確
かめた．
(2)では，短い部分文字列に対するPurity尺度の問題点を指摘し，それを克服した新しい尺度で
あるAtomicity尺度を提案した．ゲノム配列は 4 種類程度の記号により記述されるため，解析の対
象となるのは比較的長い部分文字列である．一方，英文テキストなど の文字列データではより多
くの記号が使われており，情報が短い文字列で記述されるため，比較的短い部分文字列も解析の
対象としなければならない．対象となる部分文字列が短い場合，Purity尺度の値が特定の値に集
中するため短い部分文字列をうまく差別化できないという問題がある．本研究で提案した
Atomicity尺度は，この問題を改善したものである．英文テキスト中の単語を文字とみなした実験
により，Purity尺度では差別化できない部分文字列がAtomicity尺度によって差別化できることを
確認した．
(3)では，グラフの頂点のクラスタリング問題に対し，巨視的構造と呼ぶ粗視化されたグラフを
導入することで，既存手法と比べてノイズに頑健な手法を提案した．グラフクラスタリング問題
として定式化される種々の問題の中には，クラスタ間に多数の辺(ノイズ)があるグラフを扱わな
ければならない場合がある．本研究では，巨視的構造と呼ぶクラスタ間の関係性を記述するグラ
フの導入により，クラスタ間の辺の絶対数に左右されず，クラスタ間およびクラスタ内の辺密度
の差のみに依存する手法を提案した．人工データおよび実データを用いた実験から，提案手法が
ノイズの多いグラフ上において既存手法を凌ぐ性能をもつことが示された．