1. はじめに
データマイニングとは、大量のデータから隠された知識や新しい規則を発見するプロセスです。
データマイニングを行う枠組みとして注目されているものの一つに帰納論理プログラミング(Inductive Logic Programming : ILP)があります。これは述語論理を使用することで豊かな表現力を持ち、可読性の高い解析が行うことができます。
ILPの枠組みにおけるデータマイニングでは多くの手法が提案されてきましたが、多くの手法はパターンの候補が膨大に存在し、それらを調べるのに多くの時間がかかってしまうという問題があります。
よって、本研究では対象となる事例に見られる性質に注目することで、高速にマイニングを行う手法を提案します。
2. アイディア
図のような家族関係のデータがあったとします。
これは，親子関係を表す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という孫息子をもつ」という事実であり、このような事例が表す述語の組の中でも意味のある述語の組を性質と考えます。この性質を使用して、意味のあるパターンに限定してマイニングを行うことが本提案手法のアイディアです。
3. 提案手法
性質を利用して以下の方法でマイニングを行います。
(1) 事例に見られる性質をすべて取り出す
(2) 性質を使ってマイニングをおこなう
性質を使ったマイニングの方法として3つの方法を考えます。
3.1 MAPIX
まずそれぞれの性質について、その性質を持つかどうかの真偽を一つの属性と考えることで、相関ルールマイニングをおこないます。相関ルールマイニングとは、マーケットバスケット分析を目的として提起された方法論で、マーケットで売られている個々の商品について、どのように買われているかの規則性を見つけることが目的です。相関ルールは、効率的な探索をおこなう手法としてAprioriアルゴリズムが考案されています。
マイニングの方法は、(1)性質を事例から取り出し、(2)それぞれの性質を事例が満たしているかどうか調べ、(3)Aprioriアルゴリズムを利用して、性質を組み合わせて頻出なパターンを枚挙します。
これによって、より高速にILPの枠組みでマイニングをおこなうことができますが、問題点として得ることのできないパターンが存在します。
3.2 DUPLIPIX
DUPLIPIXは，MAPIXの出力するパターンの問題点を解決する手法です。以下のような事例について考えます。
| gfather(Koji)← | parent(Koji, Yozo)∧male(Yozo)∧parent(Yozo, Kyoichi)∧male(Kyoichi). |
この事例は、「息子をもつ」という性質「gfather(A)←parent(A, B)∧male(B)」と「孫息子をもつ」という性質「gfather(A)←parent(A, B)∧parent(B, C)∧male(C)」を満たします。それぞれの性質をp1、p2としたとき、事例Kojiはp1、 p2をどちらも満たしているので、p1∧p2というパターンを満たすと考えることができますが、p1∧p2は「息子をもつ∧孫息子をもつ」という意味であり、事例Koji に現れる「息子と孫息子がおり、孫息子は息子の息子である」というパターンにはなりません。
よってDUPLIPIXでは、性質を使って事例の部分的な構造を生成することを考えます。具体的には、「調べたい性質の組み合わせを実際に事例に見られるような述語の組で取り出す方法」を提案し、それらの複数の性質をパターンと考えマイニングをおこないます。
このアルゴリズムの問題点として、論理的に同値なパターンが出力されるため、それらを出さないように削除するなどして制御する必要はありますが、この処理には多くの時間がかかってしまうことです。
3.3 EQUIVPIX
前節のDUPLIPIXアルゴリズムは、事例に見られるすべての構造をマイニングすることができます。しかし、ILPデータマイニングでは事例には見られない構造でも、事例が満たすならば出力したいという要求があります。例えば、事例Kojiからは以下のようなパターンは、事例の本来の構造に無いため出力されません。
| gfather(A)← | parent(A, B)∧male(B)∧parent(A, C)∧parent(C, D)∧male(D). |
しかし、A=Koji、B=Yozo、C=Yozo、D=Kyoichiとすることで、事例Kojiはパターンを満たすことがわかります。
4. まとめ
本研究ではデータマイニングに注目し、帰納推論と論理プログラミングを結合した強力なアプローチであるILPを使用することで、データマイニングに重要な可読性の高い知識を得る三つの手法を提案しました。提案手法では性質というものに注目し、性質を使うことで従来手法より高速にマイニングをおこなうことを可能にしました。