データマイニング技術に関する国際的動向と課題

森下 真一
東京大学 医科学研究所
http://platinum.ims.u-tokyo.ac.jp/~moris/

  1. 調査概要

    近年、データマイニング分野の成長は米国において顕著である。1998 年、ACM にデータマイニング関連の分科会 SIGKDD が発足し、国際会議 KDD'98 は大盛況に終わり、マイクロソフト研究所のデータマイニンググループは増大した。我々は、北米・欧州地域におけるデータマイニング研究の動向調査するために、データマイニングに関する国際会議に参加し、また活発な研究組織の研究者を訪問し意見交換を行った。具体的には、3 名のメンバーが 4 重要国際会議を調査した。

    • 有村 博紀 (九州大学)

      1. Very Large Data Bases, New York City, NY, USA, August 24-27, 1998.
      2. 4th International Conference on Knowledge Discovery and Data Mining, New York City, NY, USA, August 27-31, 1998.

    • 河野 浩之 (京都大学)
      PKDD-98: 2nd European Symposium on Principles of Data Mining and Knowledge Discovery, Nantes, France, September 23-26, 1998

    • 岩間 一雄 (京都大学)
      39th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, November 8-11, 1998

    また、著者は米国における 3 主要研究機関を訪問し、マイクロソフト研究所では Surajit Chaudhuri, Heikki Mannila, IBM アルマデン研究所では Rakesh Agrawal, Ramakrishnan Srikant, スタンフォード大学では Jeffrey D. Ullman, Rajeev Motwani らのデータマイニング分野を代表する研究者たちと今後の展望について意見交換を行った。

  2. なぜブームなのか?

    データマイニングにしばしば登場する様々な技術、例えば 決定木・回帰木・アソシエーションルール・クラスタリング・ベイジアンネットワーク・重回帰分析・k-nearest neighborhood 探索・ニューラルネットワーク・HMM等は、既に機械学習・統計学・人工知能分野で提案されてきた方法であり、データ分析手法としての新規性はあまりない。ではなぜブームとなっているのか? 今回の調査からも見えてくる、技術的側面からの研究課題、および新しい応用例について紹介したい。

    2.1 技術的研究テーマ

    1. 巨大化するデータベースの効率的処理方法の模索: 従来の機械学習では比較的少数のデータを扱っていた。一方、近年、データ読取装置や WWW が普及し、記憶装置が低価格化したため、巨大なデータベースを構築しかつ利用可能になった。大規模データを効率よく取り扱うためには、主記憶を効率よく使うデータ構造の工夫や、2 次記憶と主記憶間のデータ転送量を減らす仕組みを考える必要がある。ただこのような研究テーマはデータベース問合せ最適化分野で既に長年の研究の歴史があるように見える。でありながらデータベース研究者がデータマイニングを研究対象として注目している理由は、多数の関連した非定型問合せを同時に高速するという新たな研究テーマがあるためである。詳しくは、非定型問合せといった場合、従来は 1 つないしは数個の入れ子型問合せ文の処理だけを考えればよかったのに比べ、はるかに難しい研究題材を提供している。また並列処理の観点からも、主記憶 2 次記憶間に発生するデータ入出力の並列化等の新たな研究テーマも提供している。国際会議では VLDB と KDD (今回調査)、そしてACM SIGMOD/PODS では、このような実装技術に関する質の高い論文が数多く発表されている。

    2. 組合せ爆発の回避: データベースの巨大化は、パラメータ (データ属性) 数の増加を伴う。例えば、顧客の危険率を予測するために有効なデータ属性の組合せを、数多くのデータ属性から抽出することは典型的な組合せ問題となる。この際、効率的に組合せを見つけるためのアルゴリズムを設計できるか困難かは、アルゴリズム分野の新たな研究題材となっている。また、効率化が理論的に困難な場合でも、ランダムサンプリングや、探索＋分岐限定法で現実の問題をどれだけ解けるかということが研究課題となっている。 データマイニングのアルゴリズムや計算量に関する論文は ACM SIGMOD/PODS, KDD, VLDB, FOCS 等で発表されている。

    3. GUI の工夫: GUI が身近になった現在において、データ解析結果をビジュアルに表示することは、ユーザの知識発見を促すのに効果的である。国際会議等でデータマイニング向けの GUI に関する研究発表は少ない。その中で米国ウイスコンシン大学 Raghu Ramakrishnan 教授率いるチームの研究は秀逸である。大規模データを扱う GUI の技術的困難さを分析し、高速な実装方法を提案し、研究プロトタイプ DEVise の完成度は高い。一方、データマイニング製品および研究プロトタイプが GUI に力を入れているのは明らかであり、例えば、IBM の Intelligent Miner や SGI の Mineset はその代表例である。今回の調査でも、河野先生 (京都大学) が Simon Fraser 大学の Jiawei Han 教授の研究チームが開発したDBMiner を紹介しているが、様々な GUI を提供している。

    2.2 応用

    大規模データを扱えるようになったことで、以前は不可能だったデータベースの解析が可能になっている。以下にいくつかの例を示す。

    1. 1993 年に IBM アルマデン研究所の Agrawal らがアソシエーションルールの効率的枚挙方法を提示した論文の中で、スーパーマーケットの商品購買の相関関係解析への応用を示している。このような応用は浸透しつつあり、例えば、amazon で書籍を検索すると、目的の書籍と一緒に購入されがちな書籍がリストされてくる。また、WWW ページでの単語の共起関係を調べるなどテキストマイニングへの応用が盛んである。日本では河野先生、有村先生らがこの分野で成果を挙げている。

    2. 類似性から顧客をグループ分けする際に使われるクラスタリング技術や、属性が類似のデータを類似度に応じて列挙する k-nearest neighborhood 法は、従来からある手法であるが、データマイニング技術の進歩は、分析可能なデータベースの範囲を広げている。

    3. Microsoft Research ではデータマイニング技術を Office の Wizard やヘルプの設計に応用している。またユーザのテクニカルサポートへの応用を考えている。

  3. 今後の方向性は?

    データマイニングシステム実装技術は今後も米国を中心に、大学やデータベースベンダーで開発が進むものと考えられる。

    1. アソシエーションルール、決定木、クラスタリングを高速に実装する実装方法はかなり研究が進み、小さな改良が目立ちつつある。今後は市場の広がりに呼応して、小刻みな実装の改良が繰り返されるであろう。

    2. 並列処理に関しては SMP での実装方式に研究の余地があると思う。

    3. アルゴリズム分野から、ランダムサンプリングやランダムアルゴリズムを使う手法が導入され、論文数も増えてきている。

    4. GUI のデザイン方法は数多くのレパートリーがあるものの、データサイズにスケーラブルな実装方法の研究は少ない。ウイスコンシン大学 Raghu Ramakrishnan らの研究が一つの方向性を与えている。

    5. 応用面では、WWW やメール等のテキストからのデータマイニングが注目されており、重要な方向性であろう。