平成19年度卒業

牧野 敏行
関係データベースシステムを結合した論理データマイニングの実装



1.　はじめに

　データマイニングとは、大量のデータから隠された知識や新しい規則を発見するプロセスです。
　データマイニングを行う枠組みとして注目されているものの一つに帰納論理プログラミング(Inductive Logic Programming : ILP)があります。これは述語論理を使用することで豊かな表現力を持ち、可読性の高い解析が行うことができます。

　ILPの枠組みにおけるデータマイニングでは多くの手法が提案されてきました。その中で当研究室で考案されたMAPIX [元山 '04]があります。この手法は、性質という意味のある特徴を表す基本パターンに限定してマイニングを行う手法です。
　ただ、現在までのMAPIXの手法は、Prologプログラムで主記憶上にあるデータをマイニングするように実装されていました。そのため、データベースシステムにあるような大規模なデータには対応していないという問題点がありました。
　よって、本研究ではProlog側からデータベースシステムに接続して、データベース内のデータをマイニングできるようにMAPIXを拡張した手法の提案をします。


2.　MAPIX

　図のような家族関係のデータがあったとします。 これは，親子関係を表すparent と性別を表すmale、female の複数の表を持つ関係データベースで表されており、xはyの親であるというparent(x, y)とxの性別を表すmale(x)、female(x)という述語で表すことができます。図の*がついている名前はfemaleを満足するものであるとします。また目標事例としてgfatherの表も与えられています。目標事例はその特徴が未知であるか、その特徴が分かっていても、実際の例に見られる特徴に興味があるとします。
　例えば、この家族関係のデータベースにおいて事例gfather(Koji)に見られる述語の組として以下のようなものがあります。

gfather(Koji)←parent(Koji, Yozo)∧parent(Yozo, Kyoichi)∧male(Kyoichi).


これは「KojiがKyoichiという孫息子をもつ」という事実であり、このような事例が表す述語の組の中でも意味のある述語の組を性質と考えます。この性質を使用して、意味のあるパターンに限定してマイニングを行うことがMAPIXのアイディアです。


まずそれぞれの性質について、その性質を持つかどうかの真偽を一つの属性と考えることで、相関ルールマイニングをおこないます。相関ルールマイニングとは、マーケットバスケット分析を目的として提起された方法論で、マーケットで売られている個々の商品について、どのように買われているかの規則性を見つけることが目的です。相関ルールは、効率的な探索をおこなう手法としてAprioriアルゴリズムが考案されています。

マイニングの方法は、(1)性質を事例から取り出し、(2)それぞれの性質を事例が満たしているかどうか調べ、(3)Aprioriアルゴリズムを利用して、性質を組み合わせて頻出なパターンを枚挙します。

これによって、より高速にILPの枠組みでマイニングをおこなうことができます。


3.　提案手法

このアルゴリズムでは、Prolog 側とデータベース側の操作に分け、データベース側にSQL文によるクエリーを出すことによりマイニングをおこないます。



このアルゴリズムは、上記の図のようなステップによって構成されています。以下では、各ステップについての説明をします。

@．データベースシステム内にある事例のテーブルから、いくつかの事例を選択したテーブルを新たに作ります。

A．@で作成したテーブルから、その事例を説明し得るリテラルを全て結合したものである事例に関連したタプルのテーブルを生成します。また、性質を取り出すためにテーブルの表形式のデータをProlog 側に持ってきて述語論理の形式に変換する必要があります。

B．Aで生成した事例の関連タプルのテーブルからProlog側で性質を抽出し、各性質を変数化してパターン化したものである性質アイテムを生成します。

C．Bで生成した各性質アイテムからデータベース側で事例がその性質アイテムを持つかどうかのテーブルを作成し、そのテーブルから性質アイテムの頻度を計算し、1-頻出アイテムセットのトランザクションデータベースを作成します。さらに、作成したトランザクションデータベースからApriori アルゴリズムと同様の手法でデータベース側で閾値以上の頻度を持つ頻出アイテムセットを生成していきます(C)。この部分はSQL 文によるApriori アルゴリズムの手法を提案したS.Sarawagi らによる文献に従います。

D．Cで生成された全ての頻出アイテムセットをProlog側で出力します。

以上がアルゴリズムの流れとなります。このアルゴリズムの中で、AとCの2 つ以外(図の左側の部分)は既存のMAPIXと同様にできます。



4.　まとめ

　本研究ではILPの枠組みにおけるデータマイニングアルゴリズムであるMAPIXを拡張し、データベース内の表形式で表現されたデータに対してもマイニングを可能にしました。