| 平成９年度 委託研究ソフトウェアの提案 |
| 研究代表者： | 古川康一 教授 |
| 慶應義塾大学 大学院 政策・メディア研究科 |
現在、インターネットを中心として、情報化が加速されており、企業において もデータウエアハウスによる統合情報システムの確立が望まれている。そこで 期待される機能は、氾濫する膨大な情報の中から如何にして有益な情報を抽出 するかである。現在、そのような要求に答えるための技術として最も注目を浴 びているのが、データベースからの知識発見、あるいはデータマイニングの技 術である。ところで、データマイニングの技術は、マーケティングへの応用が 良く知られている。たとえば、商品間の組合せで、良く売れる組合せが分かれ ば、それらの商品を近くに置くことによって、売上がさらに伸びることが考え られる。
実際、データマイニングへの期待は、より大きな広がりを見せている。株価や 為替レートの予測問題や、アンケート調査の解析などである。このように、デー タマイニングへの関心が高まれば高まるほど、現在開発されているデータマイ ニングツールとの要求される機能面でのギャップが大きくなってきている。す なわち、現在データマイニングのための帰納推論エンジンとしては、ID3や C4.5などの命題論理学習器がニューラルネットワークとならんで、主要なツー ルとして一般に利用されてきたが、これらのエンジンは、より現実的な複雑な 問題を扱うことが出来ない。それは、仮説を表現する言語の表現力の不足に起 因する。
一方、帰納論理プログラミングは、一階述語論理に基づく機械学習の新しい方 法論として、現在注目を浴びている。それは、ID3やC4.5などの決定木を生成 する命題論理学習器に対して、データ間の関係に潜んでいる共通の論理的パター ンを抽出することが出来る。そのため、背景知識の利用が可能となり、命題論 理学習器に比べて、応用分野が格段に広がった。データベースの用語で言えば、 命題論理学習器は単一の表からの学習しか出来ないが、一階述語論理学習器は、 複数の表に跨るデータの中から、論理的な関連性を抽出してくれる。このため、 例えば関係データベースからの知識の発見が帰納論理プログラミングの枠組の 中で、自然に達成することが出来る。
本研究の目的は、背景で述べた、データマイニングでの機能の高度化である。 データマイニングの研究においては知識を抽出するエンジン部が重要となる。 しかし、通常データマイニングが対象とするデータベースのサイズは、1万件、 あるいはそれを越えてしまうので、一階述語論理学習器では、これまでは性 能面で手に負えなかった。本研究においては、この問題を解決して、表現力に 富みかつ効率の良い、帰納論理プログラミングに基づくデータマイニングエン ジンの開発を目指す。
本研究目的は、主として知識処理の高度化を狙っている が、同時に、並列記号処理も念頭に置いている。
本研究の目的である、表現力に富みかつ効率の良い帰納論理プログラミングに 基づくデータマイニングエンジンを開発するために、3点についての工夫を行 なう。第1は、表現言語の制限である。ID3やC4.5などの命題論理学習器と ProgolなどのHorn論理学習器との中間に位置する表現力を有する学習器として、 我々はDatalog学習器を考える。すなわち、仮説及び背景知識の表現言語とし て、Progolに見られる任意のPrologプログラムに代えて、Datalogプログラム のみを許すようにする。この制限は、一方で一般Horn論理エンジンに代わって Datalogのための専用エンジンを用いることにより、扱えるデータ量を大幅に 拡大できるばかりでなく、効率の向上も期待できる。とくに、外部データベー スの扱いが可能となり、機能的にもデータマイニングのためのエンジンとして の機能が大幅に向上する。この表現言語の選択により、本プロジェクトによっ て開発するデータマイニング用帰納論理プログラミングシステムをDatagolと 名付ける。
工夫の第2点は、帰納推論アルゴリズムの改良である。我々は、既にMGTPによ るボトムアップ型の帰納推論アルゴリズムを開発し、それが最弱仮説の計算の みならず、帰納推論の処理の大部分を占める被覆集合アルゴリズムについても、 実行効率を上げる上で大きな効果があることを示してきた。被覆集合アルゴリ ズムは仮説束上のA*$-like探索を行なうが、アルゴリズムの工夫によって、探 索すべきノードの数、および各ノードでの被覆計算の両方を効率化することが 出来る見通しを得た。具体的には、Progolが最終的に生成する仮説の引数間の 入出力の関連性を調べ、それらが連鎖として閉じていることをヒューリスティッ ク探索の手がかりとして優先探索を行ない、これによって無駄な探索の発生を 抑制する（探索すべきノードの抑制）。さらに、各被覆計算において、直接の 先祖で計算された事例の被覆集合をメモしておき、それによってそれ以下のノー ドでの被覆計算の対象事例の数を減少させる（各ノードでの被覆計算の効率化）。 我々は、本プロジェクトにおいて、これらのアルゴリズムのさらなる改良を行 なうとともに、実際に動くプログラムの開発を行なう。
第3の工夫は、Magic Set法の利用である。我々は、これまでもMagic Set法を 利用した最弱仮説の計算法を提案してきたが、ここでは、さらにDatalogと MGTPのインタフェースにMagic Set法を利用することを考えている。Magic Set 法は、元々要求駆動型の計算方式を実現しているので、それは要求駆動による データベースからのデータの取り込み（ステージング）の実現に利用すること が出来る。
また、これと並行して、本システムの有用性を高めるために、使い易いユーザ インタフェースの開発を狙う。
| | 氏 名 | 所 属 |
| 研究代表者 | 古川 康一 | 慶應義塾大学大学院 政策・メディア研究科 |
| 研究協力者 | 向井 国昭 | 慶應義塾大学 環境情報学部 |
| 研究協力者 | 清木 康 | 慶應義塾大学 環境情報学部 |
| 研究協力者 | 嶋津 恵子 | 慶應義塾大学大学院 政策・メディア研究科 |
| 研究協力者 | 尾崎 知伸 | 慶應義塾大学大学院 政策・メディア研究科 |
| 研究協力者 | 村上 知子 | 慶應義塾大学大学院 政策・メディア研究科 |
| 研究協力者 | 植野 研 | 慶應義塾大学大学院 政策・メディア研究科 |
研究は、古川、向井が全体のとりまとめを行ない、尾崎、植野は帰納推論部を 開発する。清木、嶋津はデータベースとのインタフェース部の設計、開発を担 当する。村上はユーザインタフェース部の設計、開発を担当する。システムイ ンテグレーションは、尾崎、植野が主に担当する。
本研究は、当面はアルゴリズムの検討、およびKL1、MGTPによるプログラミン グが主になるので、研究はワークステーションによるソフトウエア開発が主な 作業となる。
本システムの役割は、Datalogによって与えられた演繹データベースからの知 識発見のエンジンとして働くことである。これによって、データマイニングエ ンジンとして、表現力が命題論理よりも格段に豊かで、しかも効率的には Progolを凌ぐ実用的な帰納推論エンジンの雛型が開発されるものと期待される。 そのため、従来は不可能であった複雑な論理的パターンを演繹データベースか ら抽出することが可能になると予想される。
本システムの特徴は、帰納推論エンジンとして見た場合、Progolに匹敵する汎 用性を持ち合わせ、しかもデータベースと結合している点である。そのため、 外部データベースのスキーマさえ定義すれば、それらを容易に本システムに結 合して使うことが可能である。また、本システムは、大量データに対する処理 を効率的に行なうことが期待される。
本システムが提供するユーザインタフェースは、帰納論理プログラミングシス テムの詳細を理解していない一般ユーザに対しても、その利用を可能にするで あろう。
本ソフトウエアは、帰納推論エンジン、データベース、ユーザインターフェー ス、及び推論エンジン／データベースインターフェース、から構成される。
ユーザインターフェース部で、マイニングの対象が決定され、それに基づき、 推論エンジンを用いて実際のマイニングを行なう。
推論エンジン部は、Progolと同様、最弱仮説(仮説束)生成部、及び仮説束内探 索部からなる。最弱仮説の生成部は、MGTPを利用しボトムアップに計算を行な う。また仮説束内探索部では、その探索中に必要とされる事例の被覆計算にお いて、Magic set法を利用しデータベースからのデータの取り込みを行なう。 この際SQLを利用する。またデータベースは、商用の関係データベースを利用 する。
またポータビリティに関しては、基本的に、KL1およびOracleなどのSQLをサポー トする関係データベースシステムがあれば、利用できる。
本ソフトウエアは、演繹データベースからの知識発見を行なうことが目的であ るから、その利用は、データベースの存在を仮定する。また、帰納論理プログ ラミング自身は、教師付き学習のための枠組であるので、それが扱うことの出 来る問題は、与えられた例からの分類ルールの同定である。その際、データベー スの中の一つの表が分類クラスの正事例集合となるのが一般的である。その時、 他の表はDatagolへ与えられる背景知識となる。一般に、帰納論理プログラミ ングシステムを利用する場合に最も労力を要する部分が、負事例の用意である。 ただし、明確に定義された排反クラスへの分類問題なら、ある一つのクラスに 対する正事例は他のクラスに対する負事例となる。そのようにして、通常は負 事例を準備することが可能である。また、帰納論理プログラミングシステムの 利用を困難にするもう一つの原因は、モード情報などの付随的な情報の与え方 に対する指針の欠如である。我々はこの点を考慮して、ユーザインターフェー スを改善することにより、一般ユーザでも利用が可能なシステムの開発を目指 す。
本システムは、実用レベルの大きな問題を扱うことの出来る帰納論理プログラ ミングに基づいたデータマイニングエンジンであるので、従来のツールでは発 見できなかった知識をデータベースから抽出することが可能である。また、本 システムは演繹データベースの上に構築されるので、そのようにして得られた ルールは、直ちに同じ演繹データベースの内包データベースとすることが出来 る。これによって、演繹データベースから漸増的に知識を発見することが可能 となる。また、良好なユーザインターフェースは、システムの利用可能性を増 すものと思われる。データマイニング自身は、システムに対するパラメータの 調節を行ないながら繰り返し利用する対話的な処理となることが予想されるが、 その際、デバッグ機能をサポートした良好なインターフェースが威力を発揮す るであろう。
推論エンジンは、IFSのMGTP、昨年度九州大学で作成されたインタプリタ版 MGTP、及びMG-Progolをベースに、システムの構築を行なう。その際、データ マイニングを実現するために必要とされる大規模データの取り扱いを中心に考 え、アルゴリズムの検討、及びシステムの構築を行なう。
また今年度末の段階では、データベースとのインターフェースは考慮せず、そ れぞれ単独で動作するものを開発する。
www-admin@icot.or.jp