(57)【要約】【課題】レコード数で定義された頻度情報による支持度、確信度を満たさないルールは出力されない、という問題を解消する装置、方法、プログラムの提供。            【解決手段】ルール発見装置は、複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置と、前記データベースを読み出し、前記データベースの属性間のルールを導出して出力装置から出力するルール生成手段と、を備え、前記ルール生成手段は、レコードのグループ化の基準となる属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、前記支持度及び確信度が予め定められた所定の条件を満たすルールを前記出力装置から出力する。【選択図】図１
2014146119.tif 000002
【特許請求の範囲】
【請求項１】
複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置と、
前記データベースを読み出し、前記データベースの属性間のルールを導出して出力装置から出力するルール生成手段と、
を備え、
前記ルール生成手段は、レコードのグループ化の基準となる少なくとも１つの属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、前記支持度及び確信度が予め定められた所定の条件を満たすルールを前記出力装置から出力する、ことを特徴とするルール発見装置。
【請求項２】
前記データベースが、１つのセルに複数の属性値が含まれる少なくとも１つのレコードを有し、
１つのセルに複数の属性値が含まれる１つのレコードを、同一グループに属する複数のレコードに分割する分割手段を備えた、ことを特徴とする請求項１記載のルール発見装置。
【請求項３】
前記ルール生成手段が前記支持度及び確信度の計算に用いるグループを、前記ルールの要素となるアイテムセットに対して保持する記憶部を備えた、ことを特徴とする請求項１記載のルール発見装置。
【請求項４】
前記解像度に対応する前記属性は、前記ルールの要素から外される、ことを特徴とする請求項１乃至３のいずれか１項に記載のルール発見装置。
【請求項５】
前記ルール生成手段は、前記ルールと関係のあるグループの数を前記支持度とし、前記ルールと関係のあるグループのうち前記ルールを満たすレコードを含むグループの割合を前記確信度として計算する、ことを特徴とする請求項１乃至４のいずれか１項に記載のルール発見装置。
【請求項６】
前記ルール生成手段は、前記アイテムセットに対して１つアイテムを追加したアイテムセットの支持度を計算し、前記アイテムセットの支持度に対する前記アイテムセットに１つアイテムを追加したアイテムセットの支持度の比が予め定められた所定値以上である場合、妥当なルールと判定する、ことを特徴とする請求項１又は２記載のルール発見装置。
【請求項７】
データ処理装置によるルール発見方法であって、
複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置から前記データベースを読み出し、前記データベースの属性間のルールを生成するにあたり、
レコードのグループ化の基準となる少なくとも１つの属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、
グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、
前記支持度及び確信度が予め定められた所定の条件を満たすルールを出力装置から出力する、ことを特徴とするルール発見方法。
【請求項８】
前記データベースが、１つのセルに複数の属性値が含まれる少なくとも１つのレコードを有し、
１つのセルに複数の属性値が含まれる１つレコードを、同一グループに属する複数のレコードに分割する、ことを特徴とする請求項７記載のルール発見方法。
【請求項９】
データ処理装置に、
複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置から前記データベースを読み出し、前記データベースの属性間のルールを生成するにあたり、
レコードのグループ化の基準となる少なくとも１つの属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、
グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、
前記支持度及び確信度が予め定められた所定の条件を満たすルールを出力装置から出力する処理、を実行させるプログラム。
【請求項１０】
１つのセルに複数の属性値が含まれる少なくとも１つのレコードを有する前記データベースに対して、１つのセルに複数の属性値が含まれる１つのレコードを、同一グループに属する複数のレコードに分割する処理を実行させる請求項９記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルールの発見装置、方法及びプログラムに関する。
【背景技術】
【０００２】
関数従属性（Functional Dependency：FD）は、複数の属性間において、一方の値集合によって他方の値集合が決定される制約をいう。条件付関数従属性（Conditional Functional Dependency：CFD）は、一方の値集合が特定の条件を満たすときに限り、他方の値集合が決定される制約をいう。CFDは、例えば(X → A, tp）の形式として表わされる。ここで、Xは関係Rの属性の集合、Aは属性Rの１つの属性である。X → AはFDである。tpはXとAの属性値からなるパタンタプルであり、constant（定数）か、unnamed variable (変数)‘_’をとる。なお、XをCFDの左辺（Left Hand Side: LHS）、Aを右辺（Right Hand Side :RHS）ともいう。X(LHS)とA(RHS)の属性値はパタンタプルtpにおいて例えば‘||’で分離される。CFD (X → A, tp）は、パタンタプルtpがconstant（定数）のみとるときconstant CFDといい、tpのRHSがunnamed variable ‘_’のとき、variable CFDという。CFDの発見(CFD discovery)は、FD （X → A）だけでなく、パタンタプルtpを発見する必要がある。同一のFD （X → A）に対して、異なったパタンタプルtpで定義される複数のCFDが存在する可能性がある。なお、関係（relation）を表(table)で表したとき、属性を列とすると、タプル（tuple）は行と同義である。
【０００３】
データベース（リレーショナルデータベース）の属性間で成り立つルールの発見において、該ルールをCFDとして表現する場合、生成されたCFDの候補からデータベースの内容に合致したCFDを出力することになる。この場合、関連技術のCFD発見の典型的な構成例としては、例えば、CFDを保存する記憶装置と、CFDの候補を生成し、CFD候補がデータベースの内容に合致しているか判定する計算装置と、内容に合致していると判定されたCFDを記憶装置に保存する保存手段から構成される。記憶装置には、CFD発見アルゴリズムで得られたCFDを保存する。計算装置は、生成されたCFD候補が、データベースの内容に対して支持度（ルールと関係のあるレコードの個数）、確信度（ルールと関係のあるレコードのうち、ルールを満たすレコードの割合）が与えられた閾値以上であるか調べ、条件を満たす場合、妥当なCFDとして出力する。保存手段は、得られた妥当なCFDを、記憶装置に保存する。
【０００４】
確信度・支持度の定義のもとでのルール（CFD）を発見する手法として、例えば特許文献１や非特許文献１には、(A) constant CFDのみを発見するCFDMiner、(B) constant CFD及びvariable CFDを発見するCTANE（幅優先ベース）、(C) FastCFD（深さ優先ベース）が開示されている。
【０００５】
特許文献１、非特許文献１等に基づき、これらのCFD発見（Discovery of CFDs）を概説しておく（なお、以下は特許文献１、非特許文献１の関連箇所の抄訳であり、詳細は特許文献１、非特許文献１等が参照される）。CFD発見の前に、まずminimal (極小) CFDとfrequent CFD等について説明する。
【０００６】
＜Minimal CFD＞
CFD φ (X→A, tp）はA∈Xのときtrivialであるという。Constant CFD （X → A, (tp || a)）は、LHSのいかなる属性集合も他のCFDのLHSの属性集合Yを包含しない場合、left-reducedであるという。Variable CFD (X → A, (tp || _))がleft-reducedであるとき、(1)LHSの属性のどれも削除できず（属性のminimality）、(2)LHSのパタンにおけるconstantのいずれもunnamed variable‘_’に更新することはできない（パタンtp[X]はmost generalである(パタンのminimality）)。関係のインスタンスｒにおいてMinimalなCFD φは（φ|=ｒ）は、non-trivial, left-reducedである。MinimalなCFDはnon-redundantである。
＜Frequent CFD＞
CFD φは関係のインスタンスｒにおいて支持度supp(φ,r)がk以上であるとき、k-frequentであるという。なお、CFD φ(X→A ,tp)の支持度supp(φ,r)はφのパタンにマッチするタプル数である。ｋに関して関係インスタンスｒ上のCanonical cover of CFDs（正準被覆）は、minimal, k-frequent CFDの集合の総和Σであり、non-redundant CFDのみからなる(non-redundant set consisting of minimal constant CFDs only)。CFD発見は、パラメータｋに関してCanonical cover of CFDsを発見することである。
＜Free and Closed Itemsets＞
アイテムセット(Itemset)は対（X, tp）である。ただし、Xは関係(relation schema)Rの属性集合(X∈attr(R))、tpはX上の定数パタン（constant pattern）である。Itemset（X, tp）は、関係のインスタンスｒにおいて支持度supp (X,tp,r) （属性X上においてtpとマッチするタプル数）がk以上であるとき、k-frequent Itemsetという。Itemset（X, tp）は、支持度supp (Y,sp,r)=supp (X,tp,r)であり、（Y,sp）<=(X,tp) となるitemset（Y,sp）が存在しない場合、closedであるという。Closed itemsetは、支持度の減少なしに拡大できない。
Itemset （X, tp）は支持度supp (Y,sp,r)=supp (X,tp,r)であり、(X,tp)<=（Y,Sp）となるitemset（Y,sp）が存在しない場合に、freeであるという。(X,tp)<=（Y,Sp）の記号‘<=’は、（Y,sp）が(X,tp)よりmore generalであることを表す。Free itemsetは支持度の増加なしに汎化できる(can be generalized)。言い換えれば、free itemsetは任意の１つ以上のアイテムを除去することで支持度（頻度）が増加するitemsetのことである。支持度がｋ以上であるfree itemsetをk-frequent free itemsetという。
【０００７】
＜CFDMiner＞
CFDMinerは、関係Rのインスタンスと支持度(support)の閾値kを入力し、(X→A,(tp||a）)の形式のk-frequent minimal constant CFDのcanonical cover (non-redundant set consisting of minimal constant CFDs only)を出力する。例えば特許文献１の例では、k-frequent free itemsetに関連付けたk-frequent closed itemset (X,tp)に対して、CFDMinerでは、itemset RHS(Y, sp)=(X\Y, tp[X\Y])がfree itemset（Y,sp）に関連付けられる。すなわち各free itemsetは、対応するconstant CFDにおける候補となるRHS属性と関係付けられる。この過程でk-frequent free itemsetの順序リストLが作成される。リストLにおいて、Itemsetはサイズの昇順に順序付け(odering)が行われる。CFDMinerは、リストLのitemset (Y, sp)に関して、各サブセットY’Yに対して(Y’, sp[Y’])∈Lとなるように、RHS(Y, sp)を、RHS(Y, sp)∩RHS(Y’, sp[Y’])で置換える。（Y,sp）の全てのサブセットのチェック後、対応するk-frequent constant CFD （Y→A, (sp || a)） (for all (A,a)∈RHS(Y,sp)を出力し、Lが空でない場合、リストLの次の要素を処理する。
【０００８】
＜CTANE＞
CTANEアルゴリズムは、特許文献１のFig.3、非特許文献１の4. CTANEの記載が参照される。CRANEはパタンラティLをレベル方式でトラバースし、minimal k-frequent minimal CFDを求める。L１をリストL内のサイズｌの（X,sp）の要素の集まりとし、L2、L3と順に求める。
【０００９】
以下をLｌが空でない限り実行する。
1．リストLl内のLHSを持つminimal CFDのRHS候補を計算する。
2．各（X,sp）∈Lｌに対して有効なCFDを探す（特許文献１のFIG.3、非特許文献１のAlgorithm CTANEの2.(a), (b), (c)参照）。
3．Llを刈り取る。
4．Ll+1を求める（特許文献１のFIG.3, 非特許文献１のAlgorithm CTANEの4.(a) ,(b), (c)参照）。
【００１０】
＜FastCFD＞
FastCFDは、k-frequent CFDをDepth First Approachで発見する。関係のインスタンスｒと閾値kが与えられると、minimal CFD φ(supp(φ, r)>=k)のcanonical coverを求める。CTANEが幅優先（breadth first）であるのに対してFastCFDはk-frequent minimal CFDを深さ優先（depth first）で求める。X⊆attr(R)と、attr(R)\Xの属性Aに関してfixlhs(X,A,r,k)は、Y⊆X ,φはminimal, supp(φ,r)>=kであるCFD φ(Y →A, tp)を示すものとする。k-frequent CFDは∪attr(R) fixlhs(attr(R)\{A},A,r,k)を計算する（深さ優先で計算）ことで求められる。各A∈attr(R)についてfixlhs(attr(R)\{A},A,r,k)の計算はFindCoverで計算される。FindCoverでは、タプルt1,t2に関してdifference set  D(t1,t2:r)={B ∈attr(R)| t1[B]≠t2[B]}を定義する。rのdifference setはD(R)={D(t1,t2:r)|t1, t2∈r}である。DA(ｒ)を集合｛Y\｛A｝｜Y∈D(r), A∈Y｝とする。サイズが｜X｜-1の任意のX'⊂Xに対して、 DA(rtp)=0、DA(rtp[X'])≠0である、関係ｒにおけるk-frequent itemset (X,tp)が発見される。次に、left-reducedの条件をみたす ｋ-frequent variable CFD (XY →A,(tp,_,・・・||_))を発見するため、YがDA(rtp)のminimal coverであり、tp[X]のconstantは１つも除去できないか、あるいはunnamed variable ‘_’に更新不可であるようなk-frequent itemset（X,tp）が発見される。k-frequent itemsetsはvariable CFD φ(X→A, (tp || _))におけるconstant patternの候補とも考えられる（刈り取りによって候補の絞り込みも行われる）。すなわち、FindCoverはDA(Xtpc)のminimal coverを、attr(R)\{A}のオーダリングに基づき 深さ優先で左から右に発見する。候補CFD φ（XY →A,(tp||_))はφがminimalである場合に出力される。なお、Z⊆attr(R)、X⊆P（attr(R)）(P（attr(R)はattr(R)のべき集合)とすると、任意のY∈Zについて、Y∩Z≠０の場合にのみ、ZはZを被覆(cover)する。Z'⊂ZがZを被覆するZ'が存在しないとき、Zをminimal coverという。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】米国特許出願公開第2010/0250696号明細書（US 2010/0250696 A1）
【非特許文献】
【００１２】
【非特許文献１】Fan et al., “Discovering Conditional Functional Dependencies,” in IEEE International Conference on Data Engineering, 2009
【発明の概要】
【発明が解決しようとする課題】
【００１３】
以下に関連技術の分析を与える。
【００１４】
非特許文献１に開示された手法においては、出力されるCFDはパラメータとして与えた支持度、確信度以上のもののみであり、該支持度、確信度を満たさないものは出力されない、という問題点がある。その理由は、支持度、確信度の計算は、レコード数（タプル数)によって定義された頻度情報に基づき行われるためである。
【００１５】
具体的には、例えば、A社が月の初めに取引を行っていることを表すCFD
φ（営業日 → 会社名, (月の初め || A社）)
は、「月の初めに取引を行っている会社は、すべてA社である」と解釈されてしまい、他にも月の初めに取引を行っている会社がある場合に、CFD φの確信度が下がり、閾値以下となると、CFD発見アルゴリズムにおいて当該CFD φは出力されなくなる。なお、本明細書では、CFD （営業日 → 会社名, (月の初め || A社）)は、条件部、帰結部のそれぞれにおいて、属性と属性値を対応させ（営業日：月の初め → 会社名：A社）としても表す。
【００１６】
CFD発見アルゴリズムは、1つのセルに1つの値（属性値）をとる構成にしか対応していず、「セル中の複数の値（属性値）のうちどれか1つとマッチしている」といったルールを表すことができない、ということである。
【００１７】
したがって、本発明は、上記問題点に鑑みて創案されたものであって、その目的は、上記問題点の少なくとも１つを解消する装置、方法、プログラムを提供することにある。すなわち、本発明の目的は、レコード数で定義された頻度情報による支持度、確信度を満たさないルールは出力されない、という問題を解消する装置、方法、プログラムを提供することにある。また、本発明の他の目的は、セル中の複数の値のうちどれか1つとマッチしているといったルールを表すことを可能とした装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１８】
本発明によれば、複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置と、
前記データベースを読み出し、前記データベースの属性間のルールを導出して出力装置から出力するルール生成手段と、
を備え、
前記ルール生成手段は、レコードのグループ化の基準となる少なくとも１つの属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、前記支持度及び確信度が予め定められた所定の条件を満たすルールを前記出力装置から出力するルール発見装置（システム）が提供される。
【００１９】
本発明によれば、データ処理装置によるルール発見方法であって、
複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置から前記データベースを読み出し、前記データベースの属性間のルールを生成するにあたり、
レコードのグループ化の基準となる少なくとも１つの属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、
グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、
前記支持度及び確信度が予め定められた所定の条件を満たすルールを出力装置から出力する、ルール発見方法が提供される。
【００２０】
本発明によれば、データ処理装置に、
複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置から前記データベースを読み出し、前記データベースの属性間のルールを生成するにあたり、
レコードのグループ化の基準となる少なくとも１つの属性を解像度として受け、前記解像度としての前記属性の属性値が同一値である複数のレコードを１つのグループとみなし、
グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、
前記支持度及び確信度が予め定められた所定の条件を満たすルールを出力装置から出力する処理、を実行させるプログラムが提供される。本発明によれば、該プログラムを記録したデータ処理装置（コンピュータ）で読み出し可能な記録媒体（半導体メモリ、磁気／光ディスク媒体）が提供される。
【発明の効果】
【００２１】
本発明によれば、レコード数で定義された頻度情報による支持度、確信度を満たさないルール（CFD）は出力されない、という問題を解消することができる。また、本発明によれば、セル中の複数の値のうちどれか1つとマッチしているといったルール（CFD）を表すことができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施の形態の構成を例示する図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図(CFDMiner)である。
【図３】本発明の第１の実施の形態の動作の具体例（データベース）の内容を例示する図である。
【図４】本発明の第１の実施の形態の動作の具体例を例示する図 (CFDMiner)である。
【図５】本発明の第１の実施の形態の動作を示す流れ図 (CTANE)である。
【図６】本発明の第１の実施の形態の動作の具体例を例示する図 (CTANE)である。
【図７】本発明の第１の実施の形態の動作を示す流れ図 (FastCFD)である。
【図８】本発明の第１の実施の形態の動作の具体例を例示する図 (FastCFD)である。
【図９】本発明の第２の実施の形態の構成を例示する図である。
【図１０】本発明の第２の実施の形態の動作を示す流れ図である。
【図１１】本発明の第２の実施の形態の動作の具体例を説明するための図である。
【図１２】本発明の第３の実施の形態の構成を例示する図である。
【発明を実施するための形態】
【００２３】
本発明の実施の形態について図面を参照して詳細に説明する。本発明の一形態のシステム、装置によれば、複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置（図１の３）と、前記データベースを読み出し、前記データベースの属性間のルールを導出して出力装置（４）から出力するルール生成手段（例えば図１の可変解像度版ルール生成手段２１に対応する）を備え、前記ルール生成手段は、レコードのグループ化の基準となる、少なくとも１つの属性を解像度として受け、前記解像度として入力した前記属性の属性値が同一である複数のレコードを１つのグループとみなし、また、グループ化できない個々のレコード（前記解像度として入力した前記属性の属性値が互いに異なるためグループ化できない個々のレコード）をそれぞれ個々のグループとみなし、グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、前記支持度及び確信度が予め定められた所定の条件を満たすルールを前記出力装置から出力する。
【００２４】
本発明の一形態によれば、ユーザが入力したパラメータ（支持度、確信度の閾値）に加えて、グルーピングの単位（「解像度」という）を定める属性集合を与え、属性集合の値が同じ複数のレコードを１つのグループと看做し、グループの個数によって定義した頻度を用いて支持度（ルールと関係のあるレコードが存在するグループの個数）と、確信度（ルールと関係のあるグループのうち、ルールを満たすレコードが存在するグループの割合）の計算を行い、データベースの内容に合致したCFDの集合を計算する。
【００２５】
本発明の一形態によれば、ルール生成手段（装置、ユニット：図１の可変解像度版ルール生成手段２１）と、ルールの計算の際に支持度、確信度の計算に用いるためのグループの集合を各アイテムセット（itemset）に対して保持するための記憶装置（図１の３）を有する。
【００２６】
本発明の一形態によれば、与えた属性集合が定める解像度に基づき、支持度、確信度の計算を行う。このため、タプル単位の頻度情報による支持度、確信度では、確信度が小さくなってしまうようなルール（CFD）も、CFD発見アルゴリズムにより出力することができる。
【００２７】
例えば「年月日」の属性を解像度とした場合、CFD φ（営業日：月の初め→会社名：A社）は、「毎月の初めに行われる取引には、A社のものが1件以上存在する」と解釈され、他の会社が月の初めに取引を行っていたとしても、CFD φの確信度は減少しない。
【００２８】
例えば、年月日：2012年4月2日を営業日とした会社名がA社、B社、年月日：2012年5月2日を営業日とした会社名がA社、C社である場合、例えばグループ化の基準をなす解像度として指定された属性「年月日」に関して、同一属性値（＝2012年4月2日）であるレコード集合（２つのレコード）を１つのグループ（グループ１）とみなし、同一属性値（＝2012年5月2日）のレコード集合（２つのレコード集合）を別の１つのグループ（グループ２）とみなし、支持度、確信度を、レコード単位（タプル単位）ではなく、グループ単位で計算する。例えばCFD  φと関係のあるグループはグループ1、２の２つであることから、CFD  φの支持度は２である。また、CFD  φと関係のある２つのグループ（グループ１、２）のうち、CFD  φを満たすレコード（2012年4月2日に営業日のA社、2012年5月2日に営業日のA社）が存在するグループは２つであるため、確信度は１である。すなわち、A社以外の他の会社であるB社が月の初めに取引を行っていたとしても、CFD  φ（営業日：月の初め→会社名：A社）の確信度の値は減少しない。このため、当該CFD  φはCFD発見アルゴリズムにより、ルール（CFD）として出力することができる。
【００２９】
本発明の別の形態によれば、複数の属性値を含むレコードを複数備えたデータベースを記憶する記憶装置(図９の３)と、前記データベースを読み出し、前記データベースの属性間のルールを導出して出力装置から出力するルール生成手段（図９の可変解像度版ルール生成手段２１)を備え、前記データベースが、１つのセルに複数の属性値が含まれる少なくとも１つのレコードを有し、１つのセルに複数の属性値が含まれる１つのレコードを、同一グループに属する複数のレコードに分割する分割手段（図９の２３)を備え、前記ルール生成手段(図９の可変解像度版ルール生成手段２１)は、分割手段から、レコードのグループ化の基準となる属性（仮想属性）を解像度として受けると、前記解像度に対応する属性の属性値が同一の複数のレコードを１つのグループとみなし、グループを単位とした頻度を用いて前記ルールの支持度及び確信度の計算を行い、前記支持度及び確信度が予め定められた所定の条件を満たすルールを前記出力装置から出力する。
【００３０】
本発明の実施の形態によれば、セル中の複数の値のうちのいずれか1つとマッチしているといったルールを表すことができる。これは、１つのセルに複数の値を持つことを認めた上で、複数の値のうちどれか１つとマッチすればよいという条件を、複数の値を持つセルを含む１つのレコードを同一グループの複数のレコードに分割し解像度に対応したCFD発見を行うことで、実現できる。
【００３１】
＜実施形態１＞
図１を参照すると、本発明の第１の実施の形態は、キーボード等を含む入力装置１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、ディスプレイ装置や印刷装置等を含む出力装置４を含む。なお、記憶装置３は、データ処理装置２と通信手段を介して接続する構成としてもよい。入力装置１あるいは出力装置４をデータ処理装置２と通信手段を介して接続する端末、出力装置等としてもよい。
【００３２】
記憶装置３は、データベース記憶部３１を備えている。データベース記憶部３１は、それ自体からルールを抽出するためのデータベースを予め記憶している。
【００３３】
データ処理装置２は、可変解像度版ルール生成手段２１と、グループ集合記憶装置２２とを備えている。
【００３４】
可変解像度版ルール生成手段２１は、入力装置１から与えられたパラメータ（支持度の閾値ｋ、確信度の閾値ｐ）と、解像度情報（レコードのグループ化の基準となる１つ又は複数の属性）、グループ集合記憶装置２２に格納される情報（itemsets）を用い、データベース記憶部３１に記憶されたデータベースのルール（CFD）を生成し、出力装置４にそのルール（CFD）を表示する。あるいは、可変解像度版ルール生成手段２１は、生成したルール（CFD）を記憶装置３に記憶するか、不図示の通信インタフェース等を介してネットワーク接続される他のノード装置（不図示）等に転送するようにしてもよい。
【００３５】
グループ集合記憶装置２２は、可変解像度版ルール生成手段２１によって生成されるアイテム（itemset）（データベース中に出現している属性と、属性値のペア）やその集合について、それとマッチするレコード（タプル）を含むグループを保持する。
【００３６】
なお、可変解像度版ルール生成手段２１は、解像度情報（グループ化の基準となる属性情報）が指定入力されない場合には、指定された解像度に基づくレコードのグループ化は行わず、レコード単位で計算される頻度情報に基づき、支持度、確信度を計算するようにしてもよい。
【００３７】
次に、図１及び図２、図４、図６を参照して、本実施の形態の動作について詳細に説明する。まず、CFD発見アルゴリズムとしてCFDMinerを用いた場合の動作を、図２を用いて説明する。
【００３８】
可変解像度版ルール生成手段２１は、入力装置１から与えられたパラメータ、及びデータベース記憶部３１から与えられたデータベースの内容から、サポート（support：支持度）がパラメータｋ以上であるすべてのk-frequent free itemsetを抽出する（ステップA1）。ただし、実施形態において、サポート（support）は、アイテムセット(Itemset)に対応付けられて保持されているグループ集合のサイズ（グループの個数）である。なお、グループは、解像度の属性に関して属性値が同一のタプル（レコード）を１つのグループにグループ化したものである。
【００３９】
次に、可変解像度版ルール生成手段２１は、ステップA1で生成された各free itemsetから、妥当なルール候補を生成する。具体的には、ステップA１で生成された各、k-frequent free itemsetに対して、free itemset αとは属性を共有しないアイテムをxとし、αのsupportと、αに１つのアイテムxを加えたitemset α+{x}のsupportを計算する（ステップA2）。
【００４０】
可変解像度版ルール生成手段２１は、（α+{x}の頻度）／（αの頻度）≧ｐであるとき（ステップA3のYes分岐）、
constant CFD ψ （α → x）
を妥当なルール候補（CFD候補）とし、リストＬに追加する（ステップA4）。
【００４１】
可変解像度版ルール生成手段２１において、全てのα、ｘに対してチェックが終了していない場合（ステップA5のNo分岐）、ステップA2に戻る。全てのα、ｘに対してチェックが終了している場合（ステップA5のYes分岐）、ステップA６に移る。
【００４２】
次に、可変解像度版ルール生成手段２１は、リストLに追加された各CFDについて、CFDがminimalであるか否か（minimal CFDであるか否か）のチェックを行う。具体的には、要素がサイズ（CFDの条件部のアイテムの個数）の昇順にソートされたリストＬの先頭からCFDを順に取り出し、CFD ψを出力し（ステップA７）、リストＬに含まれているルール候補（CFD）の中で、今取り出したCFD ψに対して冗長なものを除去する（ステップA８）。リストＬが空でない場合（ステップA９のNo分岐）、ステップA7に戻り、リストＬが空となると、アルゴリズムを終了する。
【００４３】
次に、図５の流れ図を参照して、CFD発見アルゴリズムとしてCTANEを用いた場合の動作について説明する。
【００４４】
可変解像度版ルール生成手段２１は、入力装置１から与えられたパラメータ、及びデータベース記憶部３１に記憶されたデータベースから、その頻度がパラメータｋ以上のすべてのアイテムを抽出し、条件節が空、抽出されたアイテムが従属節となるCFD候補を生成する（ステップB１、B２）。
【００４５】
次に、可変解像度版ルール生成手段２１は、生成されたCFD候補を、データベース記憶部３１に保存されているデータベースと照合し、CFD候補が妥当なものであるかチェックを行う。具体的には、可変解像度版ルール生成手段２１は、CFDの支持度がk以上、確信度がp以上の場合（閾値以上でマッチしているとき）、CFD候補は妥当なものであると判定する（ステップB３）。
【００４６】
可変解像度版ルール生成手段２１は、妥当なCFDが得られたとき、該CFDを出力装置４に出力し、よりサイズの大きいCFD候補の枝刈り（Pruning）を行う（ステップB４）。
【００４７】
可変解像度版ルール生成手段２１は、上記ステップB3とB４の処理を繰り返し、それ以上CFDの候補が無くなったときは（ステップB5のYes）、ステップB６により、２つのアイテムセットを合成することで得られたアイテムセットのうち１つのアイテムを帰結節、残りを条件節に置くことで、新たなCFD候補を生成する（ステップB6）。ステップB6でCDF候補が生成できた場合（ステップB7のNo分岐）、ステップB３の判定処理に戻り、ステップB3の判定の結果、妥当である場合、当該CFD候補を出力する。ステップB3〜B６の処理を、ステップB6でCFD候補がそれ以上生成されなくなるまで繰り返す。
【００４８】
次に、図７の流れ図を参照して、CFD発見アルゴリズムとしてFastCFDを用いた場合の動作について説明する。
【００４９】
可変解像度版ルール生成手段２１は、入力装置１から与えられたパラメータ、及びデータベース記憶部３１から与えられたデータベースの内容から、支持度（support）がパラメータｋ以上であるすべてのfree itemsetを抽出する（ステップC１）。支持度（頻度）の計算は、解像度情報に基づきレコードをグループ化したグループ単位で行われる。
【００５０】
可変解像度版ルール生成手段２１では、すべてのfree itemsetが得られた後、それらをサイズ（含まれるアイテムの個数）の昇順に並べておく。
【００５１】
次に、可変解像度版ルール生成手段２１は、生成された各free itemsetからルール候補（CFD候補）を生成する。具体的には、可変解像度版ルール生成手段２１は、free itemset αを、条件部、αと属性を共有しないアイテムxを帰結部に固定し、αにもxにも含まれない属性の部分集合（サブセット）βを前提部に置いたCFD
ψ （［α, β = _ ）→ x）
を、βに対して深さ優先探索を行うことで生成する（ステップC２）。
【００５２】
次に、可変解像度版ルール生成手段２１は、生成したCFD ψ([α, β= _ ]→x）を、データベース記憶部３１に保存されているデータベースと照合し、生成したCFDが妥当なものであるかチェックを行い、妥当(支持度がｋ以上、確信度がｐ以上）である場合、それ以上深い探索を行わない（ステップC２）。
【００５３】
次に、可変解像度版ルール生成手段２１は、生成したCFD ψについて、CFD ψがminimal(冗長な要素を含まない）であるかチェックを行う（ステップC３）。
【００５４】
可変解像度版ルール生成手段２１は、CFD  ψがminimulである場合、CFD  ψを出力する（ステップC４）。
【００５５】
可変解像度版ルール生成手段２１は、すべてのfree itemset及び属性xの組合せに対して上記の処理が完了した時、処理を終了し（ステップC5のYes）、それまでに得られたすべてのCFDが、出力装置４に出力されている。
【００５６】
次に、本実施の形態の作用効果について説明する。本実施の形態によれば、グループ単位での頻度に基づき、支持度・確信度の計算を行う。このため、レコード単位の支持度・確信度の定義を用いて行われるCFD発見では、確信度が減少してしまい、CFDとして出力されないようなCFDを出力することができる。
【００５７】
例えば、年月日の属性をグルーピングの単位（属性値が同一のレコード集合を１つのグループとする）とした場合において、CFD φ (営業日：月の初め→会社名：A社)は、「毎月の初めに行われる取引には、A社のものが存在する」と解釈され、他の会社が月の初めに取引を行っていたとしても、確信度の値は減少しない。このため、ルールとして出力することが可能になる。
【００５８】
＜実施例＞
次に、具体的な実施例を用いて本実施の形態の動作を説明する。CFD発見アルゴリズムとしてCFDMinerを用いた場合の動作について図３及び図４を参照して説明する。
【００５９】
図３に示すように、例えば、データベース記憶部３１には、以下の属性（年月日、営業日、会社名）、タプルからなるデータ集合が登録されている。上記したレコードはタプルに対応する。
【００６０】
2014146119.tif 000003
【００６１】
可変解像度版ルール生成手段２１は、データベース記憶部３１から、上記表１を読み込み、入力装置１からパラメータとして、ｋ＝１、ｐ＝1、さらに、解像度を定める属性として「年月日」を受け取る。ここで、ｋは妥当なルールと判定するための支持度の下限（閾値）、ｐは確信度の下限（閾値）である。
【００６２】
可変解像度版ルール生成手段２１において、「年月日」の属性は解像度のためだけに用いられ、CFDの中に含まれる対象（LHS、RHSの属性）からは、除外するものとする（後述のCTANE、FastCFDにおいても同様とする）。
【００６３】
データベース中の出現頻度がｋ＝１以上である、すべてのfree itemsetを列挙すると、図４（A）が得られる。なお、emptyは属性が空の場合である。（営業日＝10日で営業日）：｛2012/04/10, 2012/05/10｝は、属性（営業日）＝属性値（10日で営業日）のパタンが出現する「年月日」の属性値である。free itemsetの中の１つである「営業日＝20日で営業日」は、異なる3つの「年月日」｛2012/04/20, 2012/05/20, 2012/06/20｝において出現しているため、その出現頻度は３となる。
【００６４】
これをルール（CFD）の条件節（部）とし、ルール（CFD）の帰結節（部）として、アイテム「会社名=C社」を採用すると、2つのアイテム「営業日=20日で営業日」、「会社名=C社」が同時に出現するレコードは、異なる3つの「年月日」において存在している。
【００６５】
このため、可変解像度版ルール生成手段２１において、constant CFD（営業日：20日で営業日→会社名：C社）の支持度は３、確信度は１となり、条件（支持度閾値ｋ＝１、確信度閾値ｐ＝１以上）を満たすことから、出力装置４から出力される。なお、表１において、「年月日」の属性値2012/04/10が同一の２つのレコード（タプル１、２）をグループ１、「年月日」の属性値2012/05/10が同一の２つのレコード(タプル４、５)をグループ２、「年月日」の属性値2012/05/20が同一の２つのレコード(タプル６、７)をグループ３、「年月日」の属性値2012/04/20、2012/06/10、2012/06/20の各々のレコード（タプル３、８、９）をそれぞれグループ４、５、６とすると、全体で６つのグループからなる。表１のタプル３、８、９の各タプルは、各々、１タプル（１レコード）で１グループとなる。すなわち、グループ化できない個々のレコード（解像度として入力した「年月日」の属性値が互いに異なる１つ１つのレコード）をそれぞれ１グループとしてみなす。CFD（営業日：20日で営業→会社名：C社）と関係のあるグループはグループ３、４、６の３つであるため、CFD  φの支持度は３である。また、CFD  φと関係のある３つのグループ３、４、６のうち、CFD  φを満たすレコード（20日で営業日、C社）が存在するグループの数は３であるため、確信度は３／３＝１である。
【００６６】
なお、「営業日=20日で営業日」に、「会社名=C社」を追加した、「営業日=20日で営業日」＋「会社名=C社」のsupportは３、「営業日=20日で営業日」のsupportは４であり、（「営業日=20日で営業日」＋「会社名=C社」のsupport：３）／（「営業日=20日で営業日」のsupport：４）＝３／４が予め定められた閾値以上であるため、CFD「営業日:20日で営業→会社名：C社」をリストLに追加する構成としてもよい。
【００６７】
図４（B）に示したように、可変解像度版ルール生成手段２１は、４個のconstant CFDを出力する。
【００６８】
図６を参照して、CFD発見アルゴリズムとしてCTANEを用いた場合の動作を説明する。CFDMinerの動作例と同一のデータ集合（図３参照）がデータベース記憶部３１に登録されているとする。
【００６９】
可変解像度版ルール生成手段２１は、上記の表１、及びパラメータとしてｋ＝１、ｐ＝1、さらに解像度として「年月日」を受け取る。
【００７０】
図６（A)は、frequent itemである。サイズが１のアイテムセットから生成される（条件節が空）CFD候補には妥当な（valid）ものが存在しない。
【００７１】
このため、可変解像度版ルール生成手段２１は、続いて、サイズ２のitemsetを、サイズ１のitemset２つから合成し、CFD候補を生成する（図６（B））。図６（C）は、サイズ１のitemset２つから合成したサイズ２のitemsetの例である。例えば、サイズ２のitemset「営業日：_ 、会社名：_ 」（_は、任意の属性値とマッチするunnamed variable）から得られるvariable CFDの候補（営業日：_ → 会社名：_ ）は、「営業日という属性がとる各属性値について、会社名という属性がとる属性値が存在する」を表す。このCFD候補の支持度は、全グループ数と同じ6、確信度は1である。そのため、これを妥当なvariable CFDとして出力する。可変解像度版ルール生成手段２１は、他にも同様にして図６（C）の５個のconstant CFD（minimal constant CFD）を出力し、処理を終了する。
【００７２】
次に図８を参照して、CFD発見アルゴリズムとしてFastCFDを用いた場合の動作について説明する。前記したCFDMinerの動作例と同一のデータ集合がデータベース記憶部３１に登録されているものとする。
【００７３】
可変解像度版ルール生成手段２１は、上記の表１、及びパラメータとしてｋ＝１、ｐ＝1、さらに解像度として「年月日」を受け取る。
【００７４】
可変解像度版ルール生成手段２１は、free itemsetを空集合（empty）とし、CFDのうちvariableの条件となる属性を「営業日」、帰結部となる属性を「会社名」として得られるCFD候補「営業日：_ → 会社名：_ 」は、CTANEを用いた場合の実施例と同じく、支持度は6、確信度は1であり、妥当なvariable CFDとして出力される。
【００７５】
可変解像度版ルール生成手段２１は、free itemsetを「営業日＝20日で営業日」とし、CFDの変数の条件部は空、帰結部となる属性及び属性値を「会社名＝C社」として得られるCFD候補「営業日：20日で営業→会社名：C社」は、CFDMinerを用いた場合の実施例と同じく、妥当なconstant CFDとして出力される。可変解像度版ルール生成手段２１は、他も同様にして、図８（B）の４個のconstant CFDを出力し処理を終了する。
【００７６】
＜実施形態２＞
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。図９を参照すると、本発明の第２の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、ディスプレイ装置や印刷装置などの出力装置４を含む。
【００７７】
記憶装置３は、データベース記憶部３１を備えている。データベース記憶部３１は、それ自体からルールを抽出するためのデータベースを予め記憶している。
【００７８】
データ処理装置２は、可変解像度版ルール生成手段２１と、グループ集合記憶装置２２と、１セル内に複数の属性値を持つ１つのレコードを複数のレコードに分割する分割手段２３とを備える。
【００７９】
可変解像度版ルール生成手段２１は、入力装置１から与えられたパラメータや、グループ集合記憶装置２２に格納される情報を用い、データベース記憶部３１に記憶されたデータベースのルールを生成し、出力装置４にそのルールを表示する。
【００８０】
グループ集合記憶装置２２は、可変解像度版ルール生成手段２１によって生成されるアイテムやアイテムセットについて、それを含むグループの集合を保持する。
【００８１】
分割手段２３は、データベース記憶部３１に記憶されたデータベースのデータについて、１つのセル内に複数の属性値を持つレコードを、複数のレコード（タプル）に分割し、可変解像度版ルール生成手段２１に受け渡す。可変解像度版ルール生成手段２１では、前記実施形態１に従いCFDを生成する。分割手段２３は解像度情報として、後述する仮想属性（タプルID）を可変解像度版ルール生成手段２１に渡すようにしてもよい。
【００８２】
次に、図１０及び図１１を参照して、本実施の形態の動作について説明する。データベース記憶部３１から与えられたデータベースの内容は、複数の値が格納されているセルが存在する行（タプル）について、元が同一行であるものを同一グループとして、複数の行に分割される（ステップＤ１）。分割された後は、前記実施の形態１と同様にして、CFDが得られる（ステップＤ２）。
【００８３】
次に、実施の形態２の作用効果について説明する。
【００８４】
実施の形態２によれば、１つのセルに複数の値（属性値）を持つことを認め、複数の値のうちどれか１つとマッチすればよいという条件を、複数の値を持つセルを含むレコードを同一グループの複数のレコードに分割し、前記第１の実施の形態の可変解像度版ルール生成手段２１を用いて、ルール（CFD）（複数レコードへの分割前のデータに対してレコード単位でのルール）を生成することができる。
【００８５】
次に、具体的な実施例を用いて本実施の形態の動作を説明する。図１１（A）に示すように、データベース記憶部３１には、以下の表２の属性、タプルからなるデータ集合が登録されているものとする。また、ここでは、解像度は、レコード単位とする。
2014146119.tif 000004
【００８６】
タプル１、３、４には、複数の値が属性「会社名」に含まれており、それらのタプルについて、複数行に分ける分割を行う。なお、表２は、表１（図３）を、グループ化の基準となる解像度を定義する属性「年月日」に基づき、６つのグループ化にグループ化した結果と等価である。
【００８７】
例えば、タプル１は、「仮想属性=タプル１、営業日=10日で営業日、会社名=A社」、
「仮想属性=タプル１、営業日=10日で営業日、会社名=B社」という2つのレコードに分割され、タプル３、４も同様に分割され、図１１（B）に示すような、分割結果が得られる。図１１（B）の営業日と会社名の属性値の関係は、図３の営業日と会社名の属性値の関係と同一である。
【００８８】
これにより、図３、図４に示したデータベース記憶部３１に保持されているものと同様のデータに変換され、仮想属性（図１１（B）のタプルID）を解像度として、前記実施例と同様に、CFD発見を行うことで、データベースの内容に合致したルールが得られる。
【００８９】
＜第３の実施の形態＞
次に、本発明の第３の実施の形態について説明する。図１２を参照すると、本発明の第３の実施の形態は、ルール発見用プログラム５を備える。ルール発見用プログラム５は、データ処理装置６に読み込まれ、データ処理装置６の動作を制御する。データ処理装置６はルール発見用プログラム５の制御により、以下の処理（実施の形態１、２におけるデータ処理装置２）での処理と同一の処理、を実行する。
【００９０】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【００９１】
１  入力装置
２  データ処理装置
３  記憶装置
４  出力装置
５  ルール発見用プログラム
６  データ処理装置
２１  可変解像度版ルール生成手段
２２  グループ集合記憶装置
２３  分割手段（セルに複数値を持つ行の分割手段）
３１  データベース記憶部
【図１】
2014146119.tif 000005
【図２】
2014146119.tif 000006
【図３】
2014146119.tif 000007
【図４】
2014146119.tif 000008
【図５】
2014146119.tif 000009
【図６】
2014146119.tif 000010
【図７】
2014146119.tif 000011
【図８】
2014146119.tif 000012
【図９】
2014146119.tif 000013
【図１０】
2014146119.tif 000014
【図１１】
2014146119.tif 000015
【図１２】
2014146119.tif 000016