知識基盤形成のための大規模半構造データからの超高速パターン発見
平成17年度～平成19年度
有村 博紀（北海道大学・大学院情報科学研究科・教授）
来るべき知識集約的社会においては、巨大なウェブから有用な知識を効率よくとりだすための技術の確立が求められている。そのための有望な方法論の一つがデータマイニングである。その一方で、ウェブは、「半構造データ」と呼ばれる非定型で多様な電子データの膨大な集積であり、表を対象として発達してきた従来のデータマイニング手法を直接利用することは難しい。そのため、巨大な半構造データを扱うための効率よい手段の研究が必要である。本研究の目的は以下の3点にまとめられる。
（a）広大なウェブ空間に分散した膨大な知識断片を有機的に結合し、そこに内在する知識をパターンや規則としてとりだすことが可能な超高速な半構造マイニングエンジン技術を開発する。とくに、計算量に徹底的にこだわりながら、理論的な性能保障をもつ高速アルゴリズムを研究開発する。
（b）この半構造データマイニング技術を、現実の多様な半構造データに適用するための周辺技術を開発し、ウェブ空間における知識基盤形成支援システムのためのアーキテクチャと、その実現のための実装技術を確立する。
（c）これらのマイニング技術を元に、半構造マイニングエンジンを実装し、知識基盤形成のための周辺技術とともに世界に公開する。さらに、インターネット上の大規模半構造データからの知識基盤形成可能性に関して、具体的な領域を選び、実証実験を行う。
本研究の特色として、超高速半構造データマイニング技術を鍵として、緊急の課題である巨大なウェブからの知識獲得に正面からとりくむ。そのために、データマイニング・アルゴリズム・機械学習・情報検索の最新成果を結集して、巨大半構造データからの知識基盤生成技術の創出を目指す。実証実験を行い成果をオープンソフトウェアとして公開する。
研究開始から現在までの約1年間に、次の項目に関して研究開発を行った。
（1）超高速半構造マイニング技術の研究。代表者らが開発した最右拡張手法を核技術として、さまざまな大規模半構造データに対する理論的な性能保障をもつ高速な極大パターン発見アルゴリズムを開発した。高速極大モチーフ列挙アルゴリズムMaxMotifは極大系列問題を入力長の多項式遅延時間・多項式領域で解き、生物情報学上の未解決問題を肯定的に解決した（ISAAC'05）。さらにアルゴリズムCLOATTでは、これをグラフの部分族に拡張した（ILP'05）（有村・喜田）。これを統計的マイニングへ拡張し高速な確率系列プロファイル発見手法を検討した（有村・伊藤）。
（2）半構造マイニングの周辺技術の研究。ネットワーク上の知識断片の相互連携のための知識獲得機構の検討を行った（伊藤、IMKB
XBV2）。大規模知識基盤形成システムのためのZBDD技術に基づく高速な知識索引技術を開発し（WIRI2,006）、この上で頻出パターン集合を直接計算する高速なアルゴリズムZBDD-growthやパターンの直交分解、対称パターン発見法を開発した（湊）。ルールを使ったウェブアプリの知的連携手法やメタデータ向け高速パターン照合技法などを開発した（伊藤，喜田）。
（3）知識獲得システムのプロトタイプ構築。応用事例を調査し、要求要件を洗い出した。さらに、本年度に開発したアルゴリズムを実装し、予備評価実験と理論的解析に基づいて最適化を行い、開発したプログラムをウェブおよび研究者への個別貸与を通して一般に公開した（Unot、VSOP、MaxMotif、WASA）。知識基盤形成技術について、学術情報獲得や人獣共通感染症領域等の具体的領域に関して検討を行った（伊藤・喜田・有村）。さらに、多CPUのデータ収集サーバと計算サーバを導入し、予備実験を行った（湊・伊藤・喜田・有村）。
項目（1）と（2）は、2年目中間（開始後12ヶ月目）で、予定より早く2年目末目標の上記の技術開発に成功しており、項目（3）も予定通りの進行であって、総じて研究計画は順調に遂行されている。
A（現行のまま推進すればよい）
計画段階からの明確な指針に基づき、数理理論を重視した取組がなされている。研究の状況としては、部分的に前倒しの成果も得られるほど順調に進行しており、半構造データマイニングの高速アルゴリズムについても、マイニングエンジンについても成果を出しつつある。研究成果は学術論文誌や国際会議などで発表され、招待講演や2件の受賞もあり、高い評価を得ている。また、研究グループにおける相互の連携も良好である。今後も計画に従って開発を進め、性能保証を実証することが期待される。
研究振興局学術研究助成課
-- 登録：平成23年03月 --