(19)【発行国】日本国特許庁(JP)
【公報種別】再公表特許(A1)
(11)【国際公開番号】WO2013105636
(43)【国際公開日】20130718
【発行日】20150511
(54)【発明の名称】ルール発見装置と方法並びにプログラム
(51)【国際特許分類】
   G06F 17/30 20060101AFI20150414BHJP
   G06F 19/00 20110101ALI20150414BHJP
   G06N 5/04 20060101ALI20150414BHJP
【FI】
   !G06F17/30 220Z
   !G06F17/30 180D
   !G06F17/30 170Z
   !G06F19/00 130
   !G06N5/04 550N
   !G06N5/04 580J
【審査請求】未請求
【予備審査請求】未請求
【全頁数】19
【出願番号】2013553325
(21)【国際出願番号】JP2013050399
(22)【国際出願日】20130111
(31)【優先権主張番号】2012004414
(32)【優先日】20120112
(33)【優先権主張国】JP
(81)【指定国】 AP(BW,GH,GM,KE,LR,LS,MW,MZ,NA,RW,SD,SL,SZ,TZ,UG,ZM,ZW),EA(AM,AZ,BY,KG,KZ,RU,TJ,TM),EP(AL,AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MK,MT,NL,NO,PL,PT,RO,RS,SE,SI,SK,SM,TR),OA(BF,BJ,CF,CG,CI,CM,GA,GN,GQ,GW,ML,MR,NE,SN,TD,TG),AE,AG,AL,AM,AO,AT,AU,AZ,BA,BB,BG,BH,BN,BR,BW,BY,BZ,CA,CH,CL,CN,CO,CR,CU,CZ,DE,DK,DM,DO,DZ,EC,EE,EG,ES,FI,GB,GD,GE,GH,GM,GT,HN,HR,HU,ID,IL,IN,IS,JP,KE,KG,KM,KN,KP,KR,KZ,LA,LC,LK,LR,LS,LT,LU,LY,MA,MD,ME,MG,MK,MN,MW,MX,MY,MZ,NA,NG,NI,NO,NZ,OM,PA,PE,PG,PH,PL,PT,QA,RO,RS,RU,RW,SC,SD,SE,SG,SK,SL,SM,ST,SV,SY,TH,TJ,TM,TN,TR,TT,TZ,UA,UG,US,UZ,VC
(71)【出願人】
【識別番号】000004237
【氏名又は名称】日本電気株式会社
【住所又は居所】東京都港区芝五丁目7番1号
(74)【代理人】
【識別番号】100080816
【弁理士】
【氏名又は名称】加藤 朝道
(72)【発明者】
【氏名】中山 裕貴
【住所又は居所】東京都港区芝五丁目7番1号 日本電気株式会社内
【テーマコード(参考)】
5L049
【Fターム(参考)】
5L049DD04
(57)【要約】
データベースの内容に対応したルールを効率よく発見可能とする装置、方法、プログラムを提供する。データベースからルール候補を生成するルール候補生成部(21)と、ルール候補の1つを選択するルール選択部(22)と、選択されたルールがデータベースの内容に対して妥当であるか判定するルールの妥当性判定部(23)と、ルールの妥当性判定部(23)で妥当と判定されたルールを受け取り、これまでに得られたルールの集合によるデータベースの各タプルのカバー度を更新し、カバー度が所定のパラメータで定義される計算の打ち切り条件を満たした場合、その時点でのルールの集合を出力し、ルール発見の計算を終了する、タプルのカバー度更新・判定部(24)を備える(図1)。
【特許請求の範囲】
【請求項1】
複数の属性と複数のタプルの表を有するデータベースと、
前記データベースにアクセスして前記データベースの前記属性間の値に関するルールの候補を生成して第1の記憶部に記憶するルール候補生成部と、
前記ルールの候補から1つのルールを選択するルール選択部と、
前記ルール選択部で選択された前記1つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部に記憶する、ルールの妥当性判定部と、
前記ルールの妥当性判定部によって前記第2の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定部と、
を含む、ことを特徴とするルール発見装置。
【請求項2】
前記ルール候補生成部は、
前記データベースと、
入力装置から入力されたパラメータ、及び/又は、すでに生成され前記第1の記憶部に保持されているルール候補と、
に基づき、前記ルールの候補を生成する、ことを特徴とする請求項1記載のルール発見装置。
【請求項3】
前記タプルのカバー度定部は、前記第2の記憶部に記憶されている前記ルールの集合による前記データベースのカバー度が、予め定められた所定の条件を満たしたときに、ルール発見処理を打ち切り、前記第2の記憶装置に記憶されているルールの集合を出力する、ことを特徴とする請求項2記載のルール発見装置。
【請求項4】
前記打ち切り条件として、前記ルールの妥当性判定部で前記妥当性の条件が成り立つと判定された前記ルールに応じて更新されるカバー度と、前記入力装置から入力された1つ又は複数のパラメータを用いた所定の基準により判定を行う、ことを特徴とする請求項3記載のルール発見装置。
【請求項5】
前記1つ又は複数のパラメータが、第1のパラメータs(0<s≦100)と、第2のパラメータN(所定の正整数)を含み、
前記データベース中のs%以上のタプルが、N個以上のルールとマッチしているという基準を前記打ち切り条件とする、ことを特徴とする請求項4記載のルール発見装置。
【請求項6】
データ処理装置が、
データベースから初期ルール候補を生成し、
前記生成したルール候補が妥当であるかチェックし、
妥当であれば、前記ルールをリストに追加し、
前記リストに保存されたルールの集合により、前記データベースのカバー度が予め定められた所定の打ち切り条件を満たした時、前記リスト内のルール集合を、出力装置に出力する、ことを特徴とするルール発見方法。
【請求項7】
前記データ処理装置でルール候補生成処理、ルール選択処理、ルールの妥当性判定処理、タプルのカバー度判定処理を実行し、
前記ルール候補生成処理は、複数の属性と複数のタプルの表を有する前記データベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成して第1の記憶部に記憶し、
前記ルール選択処理は、前記ルールの候補から1つのルールを選択し、
前記ルールの妥当性判定処理は、前記選択された前記1つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部に記憶し、
前記タプルのカバー度判定処理は、前記ルールの妥当性判定処理によって前記第2の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックする、ことを特徴とする請求項6記載のルール発見方法。
【請求項8】
前記タプルのカバー度判定処理では、前記データベース中の予め定められた値s%(0<s≦100)以上のタプルが、予め定められた個数N個以上のルールとマッチしているという基準を満たしたときに、ルール発見処理を打ち切る、ことを特徴とする請求項7記載のルール発見方法。
【請求項9】
複数の属性と複数のタプルの表を有するデータベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成し第1の記憶部に記憶するルール候補生成処理と、
前記ルールの候補から1つのルールを選択するルール選択処理と、
前記ルール選択処理で選択された前記1つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部に記憶する、ルールの妥当性判定処理と、
前記ルールの妥当性判定処理によって前記第2の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定処理と、
をコンピュータに実行させるプログラム。
【請求項10】
前記タプルのカバー度判定処理が、前記データベース中の予め定められた値s%以上のタプルが、予め定められた個数N個以上のルールとマッチしているという基準を満たしたときに、ルール発見処理を打ち切る、請求項9記載のプログラム。
【発明の詳細な説明】
【技術分野】
【0001】
[関連出願についての記載]
本発明は、日本国特許出願:特願2012−004414号(2012年1月12日出願)に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、ルールを発見する装置と方法並びにプログラムに関する。
【背景技術】
【0002】
関数従属性(Functional Dependency:FD)は、複数の属性間において、一方の値集合によって他方の値集合が決定される制約をいう。例えば[郵便番号]→[住所]:郵便番号が決まれば住所が決まる。これに対して、条件付関数従属性(Conditional Functional Dependency:CFD)は、一方の値集合が特定の条件を満たすときに限り、他方の値集合が決定される制約をいう。例えば、[商品種別、国=日本]→[税率]:国と商品種別によって税率が決まる(ただし、国が日本の場合のみ)。CFDは、例えば(X→A,tp)の形式としても表わされる。X→Aは、FDである。tpはXとYの属性値からなるパタンタプルである。パタンタプルは定数又は‘_’(‘_’は任意の値ともマッチする名前無し変数)からなる。CFDの発見は、FD X→Aだけでなく、パタンタプルtpを発見する必要がある。同一のFD X→Aに対して、異なったパタンタプルで定義される複数のCFDが存在する可能性がある。タプル(tuple:組)とは、関係(relation)を表(table)で表したときの行と同義であり、属性は表の列である。
【0003】
データベース(リレーショナルデータベース)の属性間で成り立つルールの発見において、該ルールをCFDとして表現する場合、生成されたCFDの候補からデータベースの内容に合致したCFDを出力することになる。この場合、関連技術のCFD発見の典型的な構成としては、例えば以下のような構成とされる。CFDを保存する記憶装置と、データベースからCFDの候補を生成し、該CFD候補がデータベースの内容に合致しているか判定する計算手段と、当該データベースの内容に合致していると判定されたCFDを記憶装置に保存する保存手段から構成される。計算手段は、所定のルール(CFD)発見アルゴリズムを用いてCFDを生成し、次にチェックの対象とするCFDを候補の中から選び、それがデータベースの内容に合致しているかどうか調べ、合致していると判定された場合、妥当なCFDとして出力する。保存手段は、妥当なCFDを記憶装置に保存する。
【0004】
データベースからのFDやCFDの候補の生成として、例えば非特許文献1、2の記載が参照される。非特許文献1は、既知の属性のリスト、または属性と値のペアのリストを合成し、そのうちの1つの項を従属項(Aとする)、残りを条件項(Xとする)に置き、式:X→Aを得る。CFDの候補の生成の順序は、幅優先(breadth-first)または深さ優先(depth-first)によって与えられる。非特許文献2には、ユーザによって与えられるFDから、一部の項に値を代入することでCFDを得る構成が開示されている。なお、条件項をLHS(Left Hand Side)、従属項(帰結部)をRHS(Right Hand Side)ともいう。
【0005】
ルールの妥当性のチェックとして、例えば特許文献1には、条件部と結論部(帰結部)からなるルールを格納するルールベースと、ルールの適用結果に関する事例情報を格納する事例情報データベースと、ルールと該ルールを満たす事例情報を関係付ける関係付け部と、妥当性チェック対象のルールの条件部をキーとして事例情報データベースから事例情報集合を事例検索部に検索させ、事例情報集合において該ルールの結論部を満たす事例情報の割合を算出し、該割合に基づき、ルールの妥当性をチェックする妥当性チェック部と、を備えたルールベース管理装置が開示されている。
【0006】
また、特許文献2には、リレーションの属性間の関数従属性(FD)を見つけ出し、リレーション分割による正規化を行う構成が開示されている。特許文献2の実施形態によれば、属性組み合せ情報の先頭の組み合せに対して関数従属性が存在するか調べるために(属性Dは属性Aに関数従属であるかを調べる)、関数従属性判定プロセスを呼び出し、SQL(Structured Query Language)文を実行し1つもタプルを検索できなければ、属性Dは属性Aの関数従属であると判断し、タプルが検索できれば、属性Dは属性Aの関数従属ではないと判断し、関数従属である場合、A→Dを従属性情報として格納する構成が開示されている。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】国際公開第2004/36496号公報
【特許文献2】特開平6−110749号公報
【非特許文献】
【0008】
【非特許文献1】Wenfei Fan et al., “Discovering Conditional Functional Dependencies,” pp.1231-1234, IEEE International Conference on Data Engineering, 2009 [2011年12月21日検索]インターネットURL<:http://homepages.inf.ed.ac.uk/fgeerts/pdf/icde09.pdf>
【非特許文献2】Lukasz Golab et al., “On Generating Near-Optimal Tableaux for Conditional Functional Dependencies,”pp376-390 VLDB Endowment, 2008 [2011年12月21日検索]インターネットURL<http://www.vldb.org/pvldb/1/1453900.pdf>
【発明の概要】
【発明が解決しようとする課題】
【0009】
本発明者による分析によれば、関連技術には、代表的には、以下のような問題点(A)、(B)がある。
【0010】
(A)関連技術のCFD発見アルゴリズムにより得られるCFDとして、データベースの内容と合致し、且つ、サポート値が予め定められた閾値以上である、という条件を満たすCFDは、一般に、多量に存在する。しかも、前記多量のCFDのうち、データベースの内容の把握のために必ずしも有用とはいえないCFDも多数存在する。
【0011】
これは、関連技術のCFD発見アルゴリズムにより生成されるCFDのほとんどは、条件節(LHS)のサイズが大きなものであり、当該CFDの意味を、人手で把握することが困難であるためである。
【0012】
また、CFDにおいて、条件節(LHS)のサイズが大きくなるほど、該条件節中の定数項も増加し、データベースにおいて、限定された一部のタプルとしかマッチせず、他の大部分のタプルとは関係の無いルールとなる。サポート値について、以下に概説しておく。
【0013】
【0014】
上記表1の関係のデータセットにおいて、例えばCFD
φ1:([A,B]→[C]、(1,_‖_))
(属性Aの値が1の場合、属性Bによって、属性Cの値が決定される)が抽出される。なお、上記CFD φ1において、パタンタプルtp=(1,_‖_)の‘‖’の左側(1,_)は条件節(LHS)A、Bの属性値、‘‖’の右側(_)は、従属節(RHS)Cの属性値である。表1において、上記φ1の条件節が成り立つのは、IDが1、2、3と、8、9、10のタプルであり、10件中6件存在する。したがって、例えばサポート値(support)=6/10=0.6となる(サポート値を、条件節(前提)と従属節(帰結)が成り立つタプルの割合とする場合もある。この場合、φ1のサポート値は0.6)。このサポート値が予め定められた閾値以上のCFDが生成される。
【0015】
(B)関連技術のCFD発見アルゴリズムは多量の計算時間を要する。例えば非特許文献1では、CFDの候補の生成を、FDの各項に、データベース中に出現している値を代入することで行っている。また非特許文献2では、2つのCFDの候補を合成することで、CFDの候補の生成を行っている。いずれの場合も、生成されるCFDの候補が莫大な個数となる。そのため、多量の時間、演算量を要する。
【0016】
したがって、本発明は上記問題点に鑑みて創案されたものであって、その目的は、データベースの内容に対応したルールを効率よく発見することを可能とする装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【0017】
本発明によれば、複数の属性と複数のタプルの表を有するデータベースと、
前記データベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成して第1の記憶部に記憶するルール候補生成部と、
前記ルールの候補から1つのルールを選択するルール選択部と、
前記ルール選択部で選択された前記1つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部に記憶する、ルールの妥当性判定部と、
前記ルールの妥当性判定部によって前記第2の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定部と、
を含むルール発見装置が提供される。
【0018】
本発明によれば、データ処理装置でルール候補生成処理、ルール選択処理、ルールの妥当性判定処理、タプルのカバー度判定処理を実行し、
前記ルール候補生成処理は、複数の属性と複数のタプルの表を有するデータベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成して第1の記憶部に記憶し、
前記ルール選択処理は、前記ルールの候補から1つのルールを選択し、
前記ルールの妥当性判定処理は、前記選択された前記1つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部に記憶し、
前記タプルのカバー度判定処理は、前記ルールの妥当性判定処理によって前記第2の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックする、ルール発見方法が提供される。
【0019】
本発明によれば、複数の属性と複数のタプルの表を有するデータベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成し第1の記憶部に記憶するルール候補生成処理と、
前記ルールの候補から1つのルールを選択するルール選択処理と、
前記ルール選択処理で選択された前記1つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部に記憶する、ルールの妥当性判定処理と、
前記ルールの妥当性判定処理によって前記第2の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定処理と、
をコンピュータに実行させるプログラムが提供される。
【発明の効果】
【0020】
本発明によれば、データベースの内容に対応したルールを効率よく発見することを可能としている。
【図面の簡単な説明】
【0021】
【図1】本発明の第1の実施の形態の構成を示す図である。
【図2】本発明の第1の実施の形態の動作を示す流れ図である。
【図3】本発明の第1の実施の形態の動作を説明するための図である。
【図4】本発明の第2の実施の形態の構成を示す図である。
【発明を実施するための形態】
【0022】
本発明の概要を説明する。本発明の好ましい形態によれば、CFDの候補(ルール候補)の一部を生成し(初期CFD候補として、例えば条件節を空とし従属節のみのルールを生成する)、該CFD候補(ルール候補)が、データベースと合致するかチェックを行う。そして、これまでに得られたCFDのみでは、データベースの内容の把握のために不十分であると判定されたときに、次のCFD候補(ルール候補)を逐次的に生成し、生成したCFD候補(ルール候補)に対して、データベースと合致するかのチェックを行う。このような構成(逐次的な反復構成)としたことで、データベースの内容把握のために有用と考えられるCFD(ルール)から逐次的に順次に発見されることになる。すなわち、本発明の好ましい形態によれば、データベースの内容を把握するのに有用なCFD(ルール)の集合を優先して(データベースの内容把握に有用でないCFD(ルール)に対して優先して)得ることができる。
【0023】
本発明の好ましい形態によれば、「これまでに得られたCFD(ルール)の集合により、ユーザがデータベースの内容を十分把握できる」という条件を定式化して表し、当該条件が満たされたときに、計算(CFD発見処理)を打ち切り、それ以上のCFDの発見処理を行わない(データベースの内容を把握するのに有用でないCFDの発見処理は行われない)。このため、本発明の好ましい形態によれば、ユーザが例えばデータベースの修正や要約を行うために有用なCFD(ルール)、すなわち、データベースの内容の把握に十分なCFD(ルール)の集合を、効率的に導出することができる。
【0024】
本発明の好ましい形態の1つの方法によれば、データ処理装置が、
データベースから初期ルール候補を生成し、
前記生成したルール候補が妥当であるかチェックし、
妥当であれば、前記ルールをリストに追加し、
前記リストに保存されたルールの集合により、前記データベースのカバー度が予め定められた所定の打ち切り条件を満たした時、前記リスト内のルール集合を、出力装置に出力する、上記各ステップを含む。
【0025】
本発明の好ましい形態の1つによれば、複数の属性(attributes)と複数のタプル(tuples)の表(table)を有するデータベースからルールの候補を生成して第1の記憶部(例えば内部メモリ)に記憶するルール候補生成部(図1の21)と、前記ルール候補の中から、妥当性判定対象のルールを1つ選ぶルール選択部(図1の22)と、前記ルール選択部(図1の22)で選択された前記1つのルールの候補が、前記データベースの内容に対して妥当であるかチェックし、前記1つのルールが妥当性の条件が成り立つ場合、前記1つのルールを第2の記憶部(リストL:内部メモリ)に記憶するルールの妥当性判定部(図1の23)と、前記ルールの妥当性判定部(図1の23)で前記妥当性の条件が成り立つとされ前記第2の記憶部(リストL:内部メモリ)に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた程度でマッチしているか否かをチェックする(前記データベースのカバー度を更新し、打ち切り条件を満たすか否かをチェックする)、タプルのカバー度更新・判定部(図1の24)と、を含む。
【0026】
本発明の好ましい形態の1つによれば、ルール候補生成部(図1の21)は、前記データベースと、入力装置から入力されたパラメータ、及び/又は、すでに生成したルール候補に基づき、ルールの候補を生成するようにしてもよい。
【0027】
本発明の好ましい形態の1つによれば、ルール生成のための打ち切り条件を導入し、データベースのルールの発見の高速化を図っている。タプルのカバー度更新・判定部(図1の24)は、これまでに得られた前記ルールの集合による前記データベースのカバー度が、予め定められた所定の条件を満たしたときに、計算(ルール発見アリゴリスムの計算)を打ち切る。
【0028】
本発明の好ましい形態の1つによれば、前記打ち切り条件として、ルールを発見するごとに更新される、前記データベースのカバー度と、少なくとも1つのパラメータを用いた、所定の基準により判定を行うようにしてもよい。
【0029】
本発明の好ましい形態の1つによれば、前記データベースの前記カバー度として、前記データベース中の各タプルのIDをキーとし、前記タプルが、今までに発見されたルール(CFD)のうちいくつとマッチしているかの個数を値(バリュー)として記憶するキー・バリュー・ストア(ハッシュマップ)として保持し、ルールが発見された場合、当該ルールとマッチするタプル(ID:キー)のバリューを1増やす構成としてもよい。また、前記パラメータの例として、例えば、パラメータs、N(ただし、0<s≦100、Nは所定の正整数)を用い、
「データベース中のs%以上のタプルが、N個以上のCFDとマッチしている」
という基準を用いてもよい。
【0030】
本発明の好ましい形態の1つによれば、ルール候補生成部(図1の21)において、過去に生成されたルール候補に基づき、新たなルールの候補を生成するにあたり(後述する図3のステップA8)、例えば条件節(CFDのLHS)のサイズがkであり(kは所定の正整数)、そのうちの1つの部分のみが異なる2つのルール候補を合成することで、条件節のサイズがk+1であるルール候補を生成するようにしてもよい。
【0031】
本発明の好ましい各形態によれば、データベースの内容の把握に有用なCFD(ルール)の集合を、効率的に導出することができる。以下、本発明の例示的な実施の形態について図面を参照して詳細に説明する。
【0032】
<実施形態1>
図1を参照すると、本発明の例示的な第1の実施の形態は、キーボード、タッチパネル等の入力装置1と、プログラム制御により動作するデータ処理装置2と、情報を記憶する記憶装置3と、表示(ディスプレイ)装置や印刷(プリンタ)装置などの出力装置4を含む。
【0033】
記憶装置3は、データベース記憶部31を備えている。データベース記憶部31は、データベースを記憶している。データベースはリレーショナルデータベース(複数の属性と複数のタプルで構成される)からなり、当該リレーショナルデータベースから、属性間のルールとしてCFDが抽出される。
【0034】
データ処理装置2は、ルール候補生成部21と、ルール選択部22と、ルールの妥当性判定部23と、タプルのカバー度更新・判定部24とを備える。
【0035】
ルール候補生成部21は、データベース記憶部31に記憶されたデータベースからルール候補を生成し、データ処理装置2の内部メモリ(不図示)に記憶する。なお、ルール候補生成部21は、入力装置1から入力されたパラメータや、これまでに生成されたルール候補を、データ処理装置2の内部のメモリ(不図示)に保持する。これらを用いて、ルール候補生成部21は、データベースからルール候補を生成する。ルール候補生成部21で生成されたルール(CFD)は初期CFD候補として、例えば内部のメモリ(不図示)に保持される。
【0036】
ルール選択部22は、ルール候補生成部21によって生成され不図示の内部メモリに記憶されたルール候補を参照して、ルールの妥当性判定部23で妥当性のチェックを行うルールを1つ選択する。
【0037】
ルールの妥当性判定部23は、ルール選択部22によって選択された1つのルールを参照し、これが妥当なルールであるかチェックし、妥当なものである場合、不図示の内部メモリに記憶されるリストL(CFDのリスト)に加えて保存する。例えば(X→A、tp1)、(X→B、tp1)等の複数のCFDを連結したリスト構造((X→A、tp1)、(X→B、tp1))として記憶する。ただし、CFDを記憶するデータ構造は連結リスト(線形リスト)(Linked-List)に制限されるものでなく、任意のデータ構造であってよいことは勿論である。なお、リストLは、データ処理装置2の内部メモリ(不図示)において、初期CFD候補を記憶する領域と別の記憶領域に格納してもよい。
【0038】
また、本願において、「妥当である」とは、
・ルールの条件節(LHS)がマッチする、データベースの全てのタプルに対して、ルールの従属節(RHS)とタプルの内容がマッチしており、且つ、
・当該ルールに反するタプルが存在しない、
ことをいう。
【0039】
タプルのカバー度更新・判定部24は、ルールの妥当性判定部23で得られたルールを入力として受け、データベースのカバー度の更新を行う。タプルのカバー度更新・判定部24は、更新したカバー度が予め定められた打ち切り条件を満たした場合、ルール発見処理の繰り返しを終了し、出力装置4に、処理結果(リストにつながれたルール)を出力する。
【0040】
図2は、第1の実施形態の処理手順を説明する流れ図である。図1および図2を参照して、第1の実施形態の動作について詳細に説明する。
【0041】
入力装置1から与えられたパラメータ、およびデータベース記憶部31から与えられたデータベースの内容は、ルール候補生成部21に供給される。
【0042】
<ステップA1>
ルール候補生成部21は、データベース中に出現している属性と値のペアからその頻度が、予め設定されたパラメータk(kは所定の正整数)以上であるものを全て抽出し、条件節(LHS)が空、抽出されたペアが従属節(RHS)となるルール(CFD)を生成し、これをルール(CFD)の候補(初期CFD候補)とする。条件節(LHS)が空で従属節(RHS)のみのCFDは常に成立する。これらのCFDをCFD候補の一部として上記初期CFD候補とし、以下のステップを繰り返すことでCFDの発見を行う。
【0043】
<ステップA2>
次に、ルール選択部22は、ルール候補生成部21により生成されたルールの候補から、次に妥当性のチェックを行うルールを1つ選択する。具体的には、選択されたルールが妥当なものである場合、予め定めた打ち切り条件に最も近づくようなルール(CFD φ)を選択する。
【0044】
<ステップA3>
ルールの妥当性判定部23は、選択されたルール(CFD φ)がデータベースの内容と整合しているかチェックする。すなわち、ルールの妥当性判定部23は、ルール選択部22により選択されたルールを、データベース記憶部31に保存されているデータベースと照合し、ルールが妥当なものであるかチェックを行う。具体的には、ルールの妥当性判定部23は、ルール(CFD φ)の条件節(LHS)がマッチするデータベースの全てのタプルに対して、ルールの従属節(RHS)と、タプルの内容(各属性の値)がマッチしており、ルールに反するタプルが存在しない場合、妥当なものであると判定する。
【0045】
<ステップA4>
選択されたルール(CFD φ)がデータベースの内容と整合している場合、ルールの妥当性判定部23は、CFD φをリストLに入れて保存する。ステップA3で、妥当なルールと判定されない場合、ステップA6に移行する。
【0046】
このステップA4において、次に、タプルのカバー度更新・判定部24は、データベースのカバー度の更新を行う。具体的には、ステップA3にて整合していると判定されたルール(CFD φ)と、条件節(RHS)がマッチするデータベースの全てのタプルの各々に対して、該マッチしているルールの個数を1つ増やす。前記データベース中の各タプルのIDをキーとし、タプルが、これまで発見されたルール(CFD)のうちのいくつとマッチしているかの個数を、バリューとしたハッシュマップとして保持するようにしてもよい。ルール(CFD)が発見された直後に、当該ルール(CFD)とマッチするタプル(IDをキーとする)のバリューを1増やす。
【0047】
<ステップA5>
タプルのカバー度更新・判定部24は、ステップA4で更新されたカバー度が、入力装置1から与えられたパラメータによって決定される計算の打ち切り条件を満たしているかチェックする。タプルのカバー度更新・判定部24は、更新されたカバー度が打ち切り条件を満たしている場合、処理を終了し、ステップA10に移行し、現在のリストLの内容を出力装置4に表示する。
【0048】
<ステップA6>
更新されたカバー度が打ち切り条件を満たしていない場合、タプルのカバー度更新・判定部24は、選択されたルール(CFD φ)と不要となったルールを候補から削除する。
【0049】
<ステップA7>
タプルのカバー度更新・判定部24は、ルール(CFD)の候補が空かチェックを行う。ルール(CFD)の候補が空でない場合、ステップA2に戻り、ルール選択部22は、残りのルールから1つ選択し、ルールの妥当性判定部23は、当該ルールが妥当なものであるかチェックを行う。
【0050】
<ステップA8>
ステップA7の判定でルール(CFD)の候補が空の場合、ルール候補生成部21は、新たなルール候補を生成する。ルール候補生成部21が、ルール候補に基づき新たなルールの候補を生成する場合、条件節のサイズがk(kは所定の正整数)であり、サイズkのうち1つの部分のみが異なる2つのルール候補を合成することで、条件節のサイズが、(k+1)のルール候補を生成する。
【0051】
<ステップA9>
ステップA8で1つ以上のルールが生成された場合、ステップA2に移行する。ステップA9で何もルールが生成されない場合、ステップA10に移行する。ステップA1において、ルール候補生成部21で生成された全てのルール候補が妥当なものでないと判定された場合には、たとえ、カバー度が計算の打ち切り条件を満たしていなかったとしても、繰り返し処理を終了し、現在のリストLの内容を、出力装置4に表示する。
【0052】
次に、本実施の形態の作用効果について説明する。
【0053】
本実施の形態では、それまでに得られたルール(CFD)によってデータベースのカバー度が打ち切り条件を満たした時に計算を終了し、それ以上のルールを計算しない。このため、ユーザにとって有用でないルールの発見を抑えつつ、限られた時間で有用なルールを重点的に収集することが可能となる。
【0054】
次に、具体的な実施例を用いて説明する。図3に示すように、例えば、データベース記憶部31には以下の属性・タプルからなるデータ集合が登録されている。
【0055】
【0056】
ルール候補生成部21は、上記の表2およびパラメータとして、k=2、s=75%、N=2を受け取る。
ここで、
kは、妥当なルールと判定するためのサポート値の下限、
sとNは「データベース中のs以上のタプルがN個以上のルールによってカバーされている場合、計算を終了する」という終了条件を定義するためのパラメータである。
【0057】
そして、データベース中の出現頻度(タプル数)がk以上である、全ての属性と値のペア{属性A=_,属性B=_,属性C=_,属性A=1,属性B=P,属性C=S,属性C=T}を抽出し、(記号_は任意の値にマッチする変数である)、条件節(LHS)が空、抽出された各々のペアが従属節(RHS)となる7つのルールを生成し、これをルールの候補とする(ステップA1)。条件節が空のルールは常に成り立つ。
【0058】
この7つのルールは、いずれもデータベースの内容に対して妥当ではないため(前記妥当性の条件を満たさない)、属性と値のペアの集合から、新たなルールの生成を行う。具体的には、集合から互いに矛盾しない2つの要素を選び合成し、要素のうち1つを従属節、残りを条件節としたルールを生成する(例えば図2のステップA8)。
【0059】
ステップA8で新たに生成されたルールのうち、
CFD φ1(A→B,(_‖_))(属性A=_→属性B=_)
というルール(属性Aの値が、属性Bの値を一意に決定する)は妥当なものであると、ルールの妥当性判定部23は判定し、このφ1をリストLに加える。次に、タプルのカバー度更新・判定部24は、全てのタプル1〜4(タプルID=1〜4)に対するカバー値を1つ増やす更新を行う(図2のステップA4)。
【0060】
この時点で、計算の打ち切り条件は満たしていないため(図2のA5のNo分岐)、続いて、ステップA8で新たに生成された別のルール
CFD φ2 (A→B,(1‖P)) (属性A=1→属性B=P)
を妥当なルールであるとルールの妥当性判定部23で検出し、このφ2をリストLに加える。次にタプルのカバー度更新・判定部24は「属性A=1」という条件にマッチするタプル1、2のカバー値を1つ増やす更新を行う(図2のステップA4)。
【0061】
続いて、
CFD φ3 (C→B,(T‖P))、(属性C=T → 属性B=P)
というルールを、ルールの妥当性判定部23で妥当なものと判定し、φ3をリストLに加える。タプルのカバー度更新・判定部24は、カバー度の更新として、「属性C=T」という条件にマッチするタプル2、3の値を1つ増やす更新を行う。
【0062】
この時点で、各タプル1、2、3、4のカバー値は、それぞれ2、3、2、1となり、打ち切り条件である「データベース中の75%以上のタプルが2個以上のルールによってカバーされている場合、計算を終了する」を満たすため、得られたルール(CFD)として、
φ1 (A→B,(_‖_))、
φ2 (A→B,(1‖P))、
φ3 (C→B,(T‖P))、
の3つを出力し、処理を終了する(図2のステップA10)。
【0063】
ここで、打ち切り条件を設けない場合、例えば、
φ4 ([C,B]→A,(Q,_‖_))、(属性C=Q、属性B=_→属性A=_)というルールが続いて生成されることになる。
【0064】
これに対して、本実施形態によれば、上記打ち切り条件を設けることで、このルールを生成する前に、CFD発見アルゴリズムを終了する。
【0065】
<実施形態2>
次に、本発明の第2の実施の形態について説明する。図4を参照すると、本発明第2の実施の形態は、ルール発見用プログラム5を備える。
【0066】
ルール発見用プログラム5は、所定の記憶媒体に記憶保持されるか、図示されないネットワークを介して他のノードからデータ処理装置6にダウンロードしてもよい。ルール発見用プログラム5は、データ処理装置6に読み込まれて図示されないCPU(Central Processing Unit)で実行され、データ処理装置6の動作を制御する。データ処理装置6は、ルール発見用プログラム5の制御により、図1の各部21〜24の処理(図2の処理ステップ)を実行する。すなわち、ルール発見用プログラム5は、入力装置1からの設定にしたがい、記憶装置3内のデータベース記憶部31に記憶されているデータベースから初期ルール候補の生成を行い、生成されたルール候補が妥当であるかチェックし、妥当であれば、当該ルールをリストに追加する。リストに保存されたルールの集合により、データベースのカバー度が打ち切り条件を満たした時、リスト内のルール集合を、出力装置4に表示させる。
【0067】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示(請求の範囲を含む)の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素(各請求項の各要素、各実施例の各要素、各図面の各要素等を含む)の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【0068】
1 入力装置
2 データ処理装置
3 記憶装置
4 出力装置
5 ルール発見用プログラム
6 データ処理装置
21 ルール候補生成部
22 ルール選択部
23 ルールの妥当性判定部
24 タプルのカバー度更新・判定部
31 データベース記憶部
【図1】
【図2】
【図3】
【図4】
【国際調査報告】