クエリ導出方法
【課題】ユーザが明確に意識せずに選んだサブ・データベースと、近似するサブ・データベースを作成するクエリを導出する方法を提供する。
【解決手段】元データベースの全ての項について問い合わせを実行し、所定の条件を満たす単項クエリを検出し、これをルートノードとし割り付け、かかるルートノードを起点として、所定条件を満たす単項クエリを終端条件が検出されるまで再帰的に実行し、ツリー構造を作成し、完成したツリー構造の全てにパスについて、ルートノードから終端ノードまでの論理積を求め、かかる全ての論理積の論理和を近似データベースを導出するクエリとする。
【解決手段】元データベースの全ての項について問い合わせを実行し、所定の条件を満たす単項クエリを検出し、これをルートノードとし割り付け、かかるルートノードを起点として、所定条件を満たす単項クエリを終端条件が検出されるまで再帰的に実行し、ツリー構造を作成し、完成したツリー構造の全てにパスについて、ルートノードから終端ノードまでの論理積を求め、かかる全ての論理積の論理和を近似データベースを導出するクエリとする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザが複数の属性値を持つ膨大なデータから成る元データベースから、ユーザが明確に意識せずに抽出したサブ・データベースと、近似するサブ・データベースを得るための問い合わせ（以下、クエリ）を特定する方法に関する。
【背景技術】
【０００２】
データマイニングとは、膨大なデータの中から有益な情報を見いだす技術である。近年、小売店でのPOSの導入やインフラの整備、データベース技術の発展から顧客に対するデータが絶え間なく入力され、膨大な量のデータが蓄積されている。この膨大な量のデータのなかから有用な知識を得ることは簡単ではないが、この膨大なデータから有用な知識を得ることが大きな利益へとつながる。
【０００３】
データマイニングの代表的手法として、1)クラシフィケーション(Classifcation)、即ち、既存データをあらかじめ定められたいくつかのクラスに分類するような規則性を発見し、それをもとに未知データの判別、予測などを行う手法、2)クラスタリング(Clustering)、即ち、データを記述する有限個のカテゴリーの集合を同定するものであり、分類基準がわかっていないデータを、データの類似性からいくつかのグループに自動的に分類する手法、3)アソシエーション(Association)、即ち、関連性抽出データ属性の間に存在する相関関係を学び、関連性の強いデータの組み合わせパターンを検索する手法、例えば相関ルール発見、などがある。
【０００４】
しかし、これらのいずれの方法も多数の変数の中から適切な変数を選択するという前処理が必要である。また、これらの方法により得られた特徴的なパターンがそのまま有効な知見として活用できていないという問題がある。
【非特許文献１】「河野雅之:"データベースからの知識発見の現状と動向",人工知能学会誌,VoL12,No,4,PP497-504(1997)」
【非特許文献２】「Blake,C,L,&Merz,CJ,,,UClRepository of ma£hineleamingdatabases,httpl//www,ics,ucLedu/mleam/MLRepository,htm1,lrvine,CAlUniversityofCa1ifomia,DepartmentoflnformationandComputerScience(1998)」 データマイニングによる属性値間相関ルール生成に関する方法として、データベースに含まれる属性間の相関係数に基づいて、相関係数が所定の値以上の相関ルールのみを生成することにより、ユーザにとって有用な相関ルールを作成する技術が開示されている。
【０００５】
しかし、この技術は属性間の関係のみを抽出してルール化しようとするものであり、従って、例えば、無相関の2つの属性の値によりユーザの意図が形成されている場合には、かかる技術では、ユーザの意図を推測することはできないという問題がある。即ち、特許文献１で開示されている技術では、身長が高い人は体重も重いという傾向をルール化できても、身長が高くて体重が軽い人をさがしているというユーザ意図を、推測することはできない。
【特許文献１】「データマイニング装置及データマイニング方法：特開2001-265596」
【発明の開示】
【０００６】
そこで本発明の課題は、膨大な元データベースの中から、例えばユーザが明確に意識せずに選んだサブ・データベースと、近似するサブ・データベースを得るに必要なクエリを導き出す、クエリ導出方法を提供することにある。
【０００７】
本発明は、複数の属性を持つタプルから成る元データベース、即ち複数の属性を行とし
、データを列とするテーブル（表）に対して、ユーザが明確に意識せずに抽出した集合、言い換えれば、元データベースに未知の問い合わせ（クエリ）を実行することにより得られたサブ・データベースと近似するデータベースを生成するに必要なクエリを導出するクエリ導出方法を提供する。
【０００８】
前記クエリ導出方法は、前記サブ・データベースの全ての項、即ち、各属性の列を単項とし、かかるサブ・データベースの全ての項毎に問い合わせ（単項クエリ）を実行する。これにより、所定の条件を満たす単項クエリを検出し、かかる単項クエリをルートノードとし割り付ける。ここで、所定の条件とは、元データベースからランダムにｎ個のタプルを抜き出し生成したランダム・データベースと前記元データベースに単項クエリを実行し生成した単項クエリ・データベースとが、前記サブ・データベースとの関係において、同じ適合率となる確率が、あらかじめ定められた危険率以下であり、かつ全ての項について実行した単項クエリのうち再現率が最大であることである。
【０００９】
前記所定の条件を満たす単項クエリを決定し、前記所定の条件を満たす単項クエリを前記サブ・データベースについて実行し、これにより肯定データベースを生成する。また、前記所定の条件を満たす単項クエリの問い合わせを否定する否定単項クエリを前記サブ・データベースについて同様に実行し、これにより否定データベースを生成する。
【００１０】
次に、前記肯定データベース又は前記否定データベースを前記元データベースとみなし、前記肯定データベースと前記サブ・データベースとの重複部分を前記サブ・データベースと、又は前記否定データベースと前記サブ・データベースとの重複部分を前記サブ・データベースとみなし、前記肯定クエリ又は前記否定クエリを前記否定データベースと前記サブ・データベースとの重複部分について実行する。
【００１１】
これにより、前記所定の条件を満たす肯定単項クエリ又は否定単項クエリを決定し、該肯定単項クエリ又は否定単項クエリが、前記ルートノードから２分木したノードとなるようにツリー構造を作成する。
【００１２】
そして、前記所定の条件を満たす単項クエリが検出できなくなるまで、これを再帰的に実行し、ツリー構造を完成させる。
【００１３】
次に、前記ルートノードから末端のノードに至るまでのパスにおいて経由する全ての単項クエリの論理積を作成し、前記パスごとに得られる論理積の全ての論理和を近似データベースのクエリとして導出する。
【実施例】
【００１４】
以下、この発明を膨大な元データベースの中からユーザが明確な意識をせずに選んだサブ・データベースに近似する近似サブ・データベースを抽出するクエリを導出する実施例について詳述する。
【００１５】
１．用語の定義
この明細書で用いられる用語の定義は次の通りである。
【００１６】
テーブルとはデータベースのことであり、図１に示すような表である。テーブルはタプルの集合である。
【００１７】
タプルとは図１に示す表の行を示し、属性に対する属性値の集まりである。
【００１８】
属性とは図１に示す価格、サイズ、色・・・等であり、その事物の有する特徴・性質を
含む。
【００１９】
属性値とは、図１に示す属性の値であり、例えば、属性“価格”の“高”、属性“サイズ”の“小”、属性“色”の“赤”である。
【００２０】
項とは、図１に示す例えば“サイズ”の列であり、一つの列が単項である。
【００２１】
単項クエリとは、図１に示すテーブルが与えられたとき、例えば、“属性”が価格：A、“属性値”が普通：aとなるようなタプルを探せ”というような、一つの属性に対し与えられた問合せをいう。この明細書では係る単項クエリを(A: a)のように記述するものとする。
【００２２】
ノードとは、ツリー構造における各ツリーの分岐点をいう。
【００２３】
パスとは、ツリー構造のノード間を結ぶ通路をいう。
【００２４】
否定クエリとは、“属性Aがaでないようなタプルを探せ”という問合せであり、この明細書では、(A: ≠a)の記述は、単項クエリ(A:a)、この単項クエリを肯定単項クエリともいう、の否定単項クエリを表す。
【００２５】
積形式（Conjunction)とは、2つの単項クエリ(A:a)、(B:b)の積を(A:a)×(B:b)のように記述した式である。
【００２６】
和形式(Disjunction)とは、2つの単項クエリ(A:a)、(B:b)の和を(A:a)＋(B:b)のように記述した式である。
【００２７】
再現率とは、図２に示すような元データベース（以下、テーブルR）とテーブルRのサブ・テーブル（以下、テーブルS）とが与えられた場合に、テーブルRに対して、単項クエリ（X:x）を作用させて、テーブルRの部分集合Sｘを導いた場合において、このSｘとSとの関係は、図２の左側に示すような関係となる。サブ・データベースSとサブ・データベースSｘとの重なっている部分（S∩Sｘ）とサブ・データベースSとの割合が再現率である。再現率はSｘがSを近似しているか否かの指標であり、再現率(Recall)は、｜S∩Sｘ｜/ |S|で表され、再現率はSｘによりSのどれくらいをカバーできたかを示す。
【００２８】
適合率(precision)とは、適合率＝｜S∩Sｘ｜/ |Sｘ| であり、適合率はSｘで近似できたSの割合を示す指標である。
【００２９】
この明細書で、｜X|と記述したときは、集合Xに含まれる要素の数を表す。
【００３０】
危険率とは、統計的仮説検定（以下、検定という。）において、帰無仮説を棄却するかどうかを決定する基準となる確率である。検定の事象が滅多に発生しないと考えられる非常に小さな確率が採用され、有意水準ともいう。この明細書においては、危険率として１%から10%を想定するが、これに限定されない。危険率の何％は、対象とするテーブルRの種類や導出しようとするクエリの精等度により変更して用いる。
【００３１】
検定とは、検討しようとする事象に対する仮説を立て、この仮説が正しいとした場合の発生確率を適当な統計分布にもとづく統計量を利用して求める行為である。この発生確率が滅多に起きない確率かどうかをあらかじめ定めた危険率と比較して判断する。発生確率が危険率より小さい場合は、滅多に起きないことが発生したのであると判断する。
【００３２】
２．ツリー構造の生成の準備
図２は、テーブルRからユーザが明確に意識しない問い合わせ（未知のクエリQｘ）により、テーブルSが与えられており、単項クエリ（X:x）をテーブルRに対して実行し、テーブルSｘを得た場合において、かかる場合のテーブルSｘとテーブルSとの関係を示したものである。図２において、再現率(Recall)＝｜S∩Sｘ｜/ |S|と定義でき、｜S∩Sｘ｜＝ｋ、|Sｘ|＝ｎとすると、適合率（Precision）は、P＝ｋ/ｎとなる。
【００３３】
一方、テーブルRから任意に1つタプルを取り出したとき、それがテーブルSに含まれる確率qは、q = |S|/|R|であるから、ランダムにn 個のタプルをテーブルRから抜き出した集合において、r個のタプルがテーブルSに含まれる確率P(r)は、
P(r)＝nCr qr(1-q)n-rとなる。
【００３４】
これはテーブルRからn個のタプルを抜き出すランダムサンプリングを実行したときの再現率である。このサンプリング結果が先の単項クエリの実行結果と同じ再現率を持つ確率は、P(k)＝nCk qk(1-q)n-k である。
【００３５】
P(k)があらかじめ定義した危険率（例えば５％）よりも小さいものであった場合、かかる確率が発生するのは、５％以下となることから、これは極めてまれな事象が発生したことになる。このことは逆に言えば、単項クエリ（A:a）の実施結果がSを近似していると言い換えることができる。
【００３６】
３．ツリー構造の生成
図３から図６は、図２に示す未知のクエリQxを導出するための手順をツリー構造として示したものである。先ず、テーブルRに対し全ての項について、単項クエリ（X: x)を実行する。即ち、単項クエリ（A:a)、次に（B:b）、・・（X:x)・・（N:n）を実行する。これらの単項クエリ（X:x)の中から危険率が予め定めた％以下、例えば５％以下であり、かつ再現率が最大である単項クエリ（X１:x１）を求め、これをルートノードとして割り付ける。
【００３７】
図３（b）は、単項クエリ（X１:x１)をテーブルRに対して実行して得られたデータベースをテーブルS１とし、テーブルSとの関係を示したものである。テーブルSとテーブルS１との重複部分がS∩Sｘである。
【００３８】
ツリー構造の生成は先ず、図3(a)に示すように、ルートノード(X１: x１)を起点として、単項クエリ（X２:x２)と補クエリ(X２:≠x２)の２分木を作成する。ここで、未知のクエリQxを実行して得られたデータベースはテーブルSである。
【００３９】
かかる２分木の作成は、図４（a）に示すようにテーブルSとテーブルS１との重複部分S∩S１をテーブルSと、テーブルS１をテーブルRとみなし、全ての項ついて単項クエリ（X:x）を実行し、所定の条件である、例えば危険率が５％以下、かつ再現率が最大である肯定単項クエリ（X２:x２）をルートノードの肯定側に継ぎ木する。
【００４０】
また、否定クエリ(X１:≠x１)を同様に実行し、所定の条件を満たす否定単項クエリ（X２:≠x２)に継ぎ木する。図４（b）はテーブルS１とテーブルS２との関係を示したものであり、これらの重複部分はS∩S１∩S２である。
【００４１】
次に、テーブルS２をテーブルRとみなし、部分集合S∩S１∩S２をテーブルSとみなし、全ての項について同様に単項クエリ（X;x）を実行し、例えば危険率が５％以下、かつ再現率を最大とする肯定単項クエリを求める。しかし、かかる条件を満たす単項クエリが見つからない場合は、単項クエリ（X２: x２)にψを継ぎ木する。図５はそのときのツリー
構造を示したものである。
【００４２】
ψを継ぎ木された場合は、ψを継ぎ木されたノードの否定単項クエリをルートと見なして、当該ルートから全ての項について、単項クエリ（X;x）同じように実行し、ψが継ぎ木されるまで再帰的に実行する。即ち、否定単項クエリ(X２:≠x２)を全ての項について同様に実行し、危険率が５％以下、かつ再現率を最大とする単項クエリ（X３;x３）を求め、ツリー構造を生成する。しかし、危険率が５％以下、かつ再現率を最大の条件を満たす単項クエリが見つからない場合はψを継ぎ木する。図６はそのときのツリー構造を示したものである。
【００４３】
図６に示すように全ての末端ノードがψによって置き換えられたとき、木の生成処理を終結し、ψおよびψに向かう矢印を取り去る。従って、肯定ノード側も否定ノード側もψが継ぎ木された末端が、ツリーの末端ノードとなる。
【００４４】
得られた木構造のルートノードから、すべての末端ノードに至るパスをトレースし、経由する単項クエリをAND結合により論理式を生成する。例えば図６の木では、論理式は、（X１:x１)×(X２:x２)×(X３:x３)＋(X１:x１)×(X２:x２)×(X３:≠x３)＋（X１: x１)×(X２:≠x２)×(X３:x３)＋(X１:x１)×(X２:≠x２)である。
【００４５】
上述した論理式によりクエリQｘを求めることができるのは、単項クエリ(X:x) を実行した結果、テーブルS1には適合部分Xと不適合部分(雑音部分)Y、および漏れた部分Zとが存在する。肯定部分の木をさらに展開していくことは、なるべく多くのXを保存しながら、テーブルS1から、雑音部分Yを取り除いていくプロセスである。このプロセスの最後は適合部分が多数を占めることになり、有意な単項クエリを見つけることができなくなり、プロセスは終結する。一方、否定の木を展開していくことは、漏れた部分Zを取り戻すプロセスであり、そのために最も有利な単項クエリを見つけ出すプロセスである。こうしてSに最も近いタプル集合を再現できる論理式を見出すことができる。
上述の木構造をメモリ上どのように実装するかについては、種種の方式が考えられる．最も直接的なものはANDとORに対応したメモリスタックを用意する方法が好適である。
【００４６】
また、上述のアルゴリズム概説では、連続した数値を取る属性については触れていない。このような属性についてはあらかじめ区間分けしておく方法が妥当と思われる。区間分けの方法については、現在までに様々な方式が提案されているが、発明者が開発したRWS(Random Walk Splitting)法が最も良い評価を得ている。
【００４７】
また、同じ結果を導くクエリの論理式表現は1通りとは限らない。このため再現率、適合率が同じ2つの論理式が与えられたとき、どちらがよい論理式かを評価する指標が必要となる。一般にANDとORで結合された単項クエリの数が少ないものの方がより一般的な論理式と考えられるため、次の指標Mを用いているのが好適である。
【００４８】
M＝-log(単項クエリの数/ 論理式の適用結果タプル数)
実施例２
上述した未知のクエリQｘが有用な手法であるかどうかを、UClリポジトリ（Blake,C,L,&Merz,CJ,,,UClRepositoryofma£hineleamingdatabases,,,
httpl//www,ics,ucLedu/mleam/MLRepository,htm1,lrvine,CAlUniversityofCalifomia,DepartmentoflnformationandComputerScience(1998)）からwineというデータベースをテーブルRとして用いた。このデータベースは、連続値属性数13で事例数178のデータ集合である。
【００４９】
本発明のクエリ導出方法を次のような評価により確認した。テーブルRに単項クエリ（A
;a）を実行し、これによりテーブルSを得る。このテーブルSと近似するデータベースを生成するクエリを実施例１の方法により導出した。なお、導出するクエリは、単項クエリ（A;a）以外のクエリである。そして、導出されたクエリをテーブルRに適用し,導出された結果について再現率、適用率、項の数の評価を行った。
【００５０】
図７に評価結果を示す。先ず、検定の危険率を変化させながら実験を繰り返した。図８は、図７の再現率と適合率をグラフ化したものである。これらの結果から、危険率が１％から10％に範囲において、再現率、適合率ともに90％以上の良好の結果を得た。なお、危険率を大きくするほどその候補クエリによって抽出されるタプルにノイズが多く含まれる。また、候補クエリから抽出されたタプルからノイズを除くために検定を繰り返えすことで、導出されたクエリの項目の数が増える。
【００５１】
次に、テーブルRを半分に分割し、その半分のデータベースをテーブルRとみなして、同様にクエリの導出を行なった。図９に評価の結果を示す。また、図１０に再現率と適合率をグラフ化したものを、図１１に項目の評価式をグラフ化したものを示す。これらの結果から、危険率を５％とすることにより、再現率、適合率ともに90％以上という良好の結果を得た。
【００５２】
次に、テーブルRを4分の1に分割し、その4分の1のデータベースをテーブルRとみなして同様にクエリの導出を行なった。図１２に評価の結果を示す。また、図１３に再現率と適合率をグラフ化したもの、図１４に項目の評価式をグラフ化したものを示す。危険率を５％とすることにより、再現率、適合率ともに90％以上の良好の結果を得た。
【産業上の利用可能性】
【００５３】
本発明によれば、膨大な元データベースの中から、例えばユーザが明確に意識せずに選んだサブ・データベースと、近似するサブ・データベースを高精度で得るに必要なクエリを導き出すことができる。
【図面の簡単な説明】
【００５４】
【図１】本実施例で説明するテーブルの一例を示した図である。
【００５５】
【図２】テーブルRからユーザが明確に意識しない問い合わせ（未知のクエリQｘ）により生成されたサブ・データベスS、近似サブ・データベースSx、再現率、適合率の関係を示した図である。
【図３】ルート(root)を起点として単項クエリ（X１:x１)と補クエリ(X１:≠x１)の２分木等の図である。
【図４】ルートノードから肯定クエリ、否定クエリを実行し、所定の条件を満たす単項クエリをノードとし作成したツリー構造等を示した図である。
【図５】所定の条件を満たす単項クエリが検出されなくなり、ツリーの末端がターミナルクエリ（ψ）になったツリー構造を示したものである。
【図６】完成したツリー構造の図を示したものである。
【図７】サンプルデータベースに本発明のクエリ導出方法を適用して得られた再現率と適合率を示した図である。
【図８】図７に示す再現率と適合率をグラフ化したものである。
【図９】サンプルデータベースを1/2として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率を示した図である。
【図１０】サンプルデータベースを1/2として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率をグラフ化した図である。
【図１１】図９の項目評価式をグラフ化した図である。
【図１２】サンプルデータベースを1/4として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率を示した図である。
【図１３】サンプルデータベースを1/4として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率をグラフ化した図である。
【図１４】図１２の項目評価式をグラフ化した図である。
【技術分野】
【０００１】
本発明は、ユーザが複数の属性値を持つ膨大なデータから成る元データベースから、ユーザが明確に意識せずに抽出したサブ・データベースと、近似するサブ・データベースを得るための問い合わせ（以下、クエリ）を特定する方法に関する。
【背景技術】
【０００２】
データマイニングとは、膨大なデータの中から有益な情報を見いだす技術である。近年、小売店でのPOSの導入やインフラの整備、データベース技術の発展から顧客に対するデータが絶え間なく入力され、膨大な量のデータが蓄積されている。この膨大な量のデータのなかから有用な知識を得ることは簡単ではないが、この膨大なデータから有用な知識を得ることが大きな利益へとつながる。
【０００３】
データマイニングの代表的手法として、1)クラシフィケーション(Classifcation)、即ち、既存データをあらかじめ定められたいくつかのクラスに分類するような規則性を発見し、それをもとに未知データの判別、予測などを行う手法、2)クラスタリング(Clustering)、即ち、データを記述する有限個のカテゴリーの集合を同定するものであり、分類基準がわかっていないデータを、データの類似性からいくつかのグループに自動的に分類する手法、3)アソシエーション(Association)、即ち、関連性抽出データ属性の間に存在する相関関係を学び、関連性の強いデータの組み合わせパターンを検索する手法、例えば相関ルール発見、などがある。
【０００４】
しかし、これらのいずれの方法も多数の変数の中から適切な変数を選択するという前処理が必要である。また、これらの方法により得られた特徴的なパターンがそのまま有効な知見として活用できていないという問題がある。
【非特許文献１】「河野雅之:"データベースからの知識発見の現状と動向",人工知能学会誌,VoL12,No,4,PP497-504(1997)」
【非特許文献２】「Blake,C,L,&Merz,CJ,,,UClRepository of ma£hineleamingdatabases,httpl//www,ics,ucLedu/mleam/MLRepository,htm1,lrvine,CAlUniversityofCa1ifomia,DepartmentoflnformationandComputerScience(1998)」 データマイニングによる属性値間相関ルール生成に関する方法として、データベースに含まれる属性間の相関係数に基づいて、相関係数が所定の値以上の相関ルールのみを生成することにより、ユーザにとって有用な相関ルールを作成する技術が開示されている。
【０００５】
しかし、この技術は属性間の関係のみを抽出してルール化しようとするものであり、従って、例えば、無相関の2つの属性の値によりユーザの意図が形成されている場合には、かかる技術では、ユーザの意図を推測することはできないという問題がある。即ち、特許文献１で開示されている技術では、身長が高い人は体重も重いという傾向をルール化できても、身長が高くて体重が軽い人をさがしているというユーザ意図を、推測することはできない。
【特許文献１】「データマイニング装置及データマイニング方法：特開2001-265596」
【発明の開示】
【０００６】
そこで本発明の課題は、膨大な元データベースの中から、例えばユーザが明確に意識せずに選んだサブ・データベースと、近似するサブ・データベースを得るに必要なクエリを導き出す、クエリ導出方法を提供することにある。
【０００７】
本発明は、複数の属性を持つタプルから成る元データベース、即ち複数の属性を行とし
、データを列とするテーブル（表）に対して、ユーザが明確に意識せずに抽出した集合、言い換えれば、元データベースに未知の問い合わせ（クエリ）を実行することにより得られたサブ・データベースと近似するデータベースを生成するに必要なクエリを導出するクエリ導出方法を提供する。
【０００８】
前記クエリ導出方法は、前記サブ・データベースの全ての項、即ち、各属性の列を単項とし、かかるサブ・データベースの全ての項毎に問い合わせ（単項クエリ）を実行する。これにより、所定の条件を満たす単項クエリを検出し、かかる単項クエリをルートノードとし割り付ける。ここで、所定の条件とは、元データベースからランダムにｎ個のタプルを抜き出し生成したランダム・データベースと前記元データベースに単項クエリを実行し生成した単項クエリ・データベースとが、前記サブ・データベースとの関係において、同じ適合率となる確率が、あらかじめ定められた危険率以下であり、かつ全ての項について実行した単項クエリのうち再現率が最大であることである。
【０００９】
前記所定の条件を満たす単項クエリを決定し、前記所定の条件を満たす単項クエリを前記サブ・データベースについて実行し、これにより肯定データベースを生成する。また、前記所定の条件を満たす単項クエリの問い合わせを否定する否定単項クエリを前記サブ・データベースについて同様に実行し、これにより否定データベースを生成する。
【００１０】
次に、前記肯定データベース又は前記否定データベースを前記元データベースとみなし、前記肯定データベースと前記サブ・データベースとの重複部分を前記サブ・データベースと、又は前記否定データベースと前記サブ・データベースとの重複部分を前記サブ・データベースとみなし、前記肯定クエリ又は前記否定クエリを前記否定データベースと前記サブ・データベースとの重複部分について実行する。
【００１１】
これにより、前記所定の条件を満たす肯定単項クエリ又は否定単項クエリを決定し、該肯定単項クエリ又は否定単項クエリが、前記ルートノードから２分木したノードとなるようにツリー構造を作成する。
【００１２】
そして、前記所定の条件を満たす単項クエリが検出できなくなるまで、これを再帰的に実行し、ツリー構造を完成させる。
【００１３】
次に、前記ルートノードから末端のノードに至るまでのパスにおいて経由する全ての単項クエリの論理積を作成し、前記パスごとに得られる論理積の全ての論理和を近似データベースのクエリとして導出する。
【実施例】
【００１４】
以下、この発明を膨大な元データベースの中からユーザが明確な意識をせずに選んだサブ・データベースに近似する近似サブ・データベースを抽出するクエリを導出する実施例について詳述する。
【００１５】
１．用語の定義
この明細書で用いられる用語の定義は次の通りである。
【００１６】
テーブルとはデータベースのことであり、図１に示すような表である。テーブルはタプルの集合である。
【００１７】
タプルとは図１に示す表の行を示し、属性に対する属性値の集まりである。
【００１８】
属性とは図１に示す価格、サイズ、色・・・等であり、その事物の有する特徴・性質を
含む。
【００１９】
属性値とは、図１に示す属性の値であり、例えば、属性“価格”の“高”、属性“サイズ”の“小”、属性“色”の“赤”である。
【００２０】
項とは、図１に示す例えば“サイズ”の列であり、一つの列が単項である。
【００２１】
単項クエリとは、図１に示すテーブルが与えられたとき、例えば、“属性”が価格：A、“属性値”が普通：aとなるようなタプルを探せ”というような、一つの属性に対し与えられた問合せをいう。この明細書では係る単項クエリを(A: a)のように記述するものとする。
【００２２】
ノードとは、ツリー構造における各ツリーの分岐点をいう。
【００２３】
パスとは、ツリー構造のノード間を結ぶ通路をいう。
【００２４】
否定クエリとは、“属性Aがaでないようなタプルを探せ”という問合せであり、この明細書では、(A: ≠a)の記述は、単項クエリ(A:a)、この単項クエリを肯定単項クエリともいう、の否定単項クエリを表す。
【００２５】
積形式（Conjunction)とは、2つの単項クエリ(A:a)、(B:b)の積を(A:a)×(B:b)のように記述した式である。
【００２６】
和形式(Disjunction)とは、2つの単項クエリ(A:a)、(B:b)の和を(A:a)＋(B:b)のように記述した式である。
【００２７】
再現率とは、図２に示すような元データベース（以下、テーブルR）とテーブルRのサブ・テーブル（以下、テーブルS）とが与えられた場合に、テーブルRに対して、単項クエリ（X:x）を作用させて、テーブルRの部分集合Sｘを導いた場合において、このSｘとSとの関係は、図２の左側に示すような関係となる。サブ・データベースSとサブ・データベースSｘとの重なっている部分（S∩Sｘ）とサブ・データベースSとの割合が再現率である。再現率はSｘがSを近似しているか否かの指標であり、再現率(Recall)は、｜S∩Sｘ｜/ |S|で表され、再現率はSｘによりSのどれくらいをカバーできたかを示す。
【００２８】
適合率(precision)とは、適合率＝｜S∩Sｘ｜/ |Sｘ| であり、適合率はSｘで近似できたSの割合を示す指標である。
【００２９】
この明細書で、｜X|と記述したときは、集合Xに含まれる要素の数を表す。
【００３０】
危険率とは、統計的仮説検定（以下、検定という。）において、帰無仮説を棄却するかどうかを決定する基準となる確率である。検定の事象が滅多に発生しないと考えられる非常に小さな確率が採用され、有意水準ともいう。この明細書においては、危険率として１%から10%を想定するが、これに限定されない。危険率の何％は、対象とするテーブルRの種類や導出しようとするクエリの精等度により変更して用いる。
【００３１】
検定とは、検討しようとする事象に対する仮説を立て、この仮説が正しいとした場合の発生確率を適当な統計分布にもとづく統計量を利用して求める行為である。この発生確率が滅多に起きない確率かどうかをあらかじめ定めた危険率と比較して判断する。発生確率が危険率より小さい場合は、滅多に起きないことが発生したのであると判断する。
【００３２】
２．ツリー構造の生成の準備
図２は、テーブルRからユーザが明確に意識しない問い合わせ（未知のクエリQｘ）により、テーブルSが与えられており、単項クエリ（X:x）をテーブルRに対して実行し、テーブルSｘを得た場合において、かかる場合のテーブルSｘとテーブルSとの関係を示したものである。図２において、再現率(Recall)＝｜S∩Sｘ｜/ |S|と定義でき、｜S∩Sｘ｜＝ｋ、|Sｘ|＝ｎとすると、適合率（Precision）は、P＝ｋ/ｎとなる。
【００３３】
一方、テーブルRから任意に1つタプルを取り出したとき、それがテーブルSに含まれる確率qは、q = |S|/|R|であるから、ランダムにn 個のタプルをテーブルRから抜き出した集合において、r個のタプルがテーブルSに含まれる確率P(r)は、
P(r)＝nCr qr(1-q)n-rとなる。
【００３４】
これはテーブルRからn個のタプルを抜き出すランダムサンプリングを実行したときの再現率である。このサンプリング結果が先の単項クエリの実行結果と同じ再現率を持つ確率は、P(k)＝nCk qk(1-q)n-k である。
【００３５】
P(k)があらかじめ定義した危険率（例えば５％）よりも小さいものであった場合、かかる確率が発生するのは、５％以下となることから、これは極めてまれな事象が発生したことになる。このことは逆に言えば、単項クエリ（A:a）の実施結果がSを近似していると言い換えることができる。
【００３６】
３．ツリー構造の生成
図３から図６は、図２に示す未知のクエリQxを導出するための手順をツリー構造として示したものである。先ず、テーブルRに対し全ての項について、単項クエリ（X: x)を実行する。即ち、単項クエリ（A:a)、次に（B:b）、・・（X:x)・・（N:n）を実行する。これらの単項クエリ（X:x)の中から危険率が予め定めた％以下、例えば５％以下であり、かつ再現率が最大である単項クエリ（X１:x１）を求め、これをルートノードとして割り付ける。
【００３７】
図３（b）は、単項クエリ（X１:x１)をテーブルRに対して実行して得られたデータベースをテーブルS１とし、テーブルSとの関係を示したものである。テーブルSとテーブルS１との重複部分がS∩Sｘである。
【００３８】
ツリー構造の生成は先ず、図3(a)に示すように、ルートノード(X１: x１)を起点として、単項クエリ（X２:x２)と補クエリ(X２:≠x２)の２分木を作成する。ここで、未知のクエリQxを実行して得られたデータベースはテーブルSである。
【００３９】
かかる２分木の作成は、図４（a）に示すようにテーブルSとテーブルS１との重複部分S∩S１をテーブルSと、テーブルS１をテーブルRとみなし、全ての項ついて単項クエリ（X:x）を実行し、所定の条件である、例えば危険率が５％以下、かつ再現率が最大である肯定単項クエリ（X２:x２）をルートノードの肯定側に継ぎ木する。
【００４０】
また、否定クエリ(X１:≠x１)を同様に実行し、所定の条件を満たす否定単項クエリ（X２:≠x２)に継ぎ木する。図４（b）はテーブルS１とテーブルS２との関係を示したものであり、これらの重複部分はS∩S１∩S２である。
【００４１】
次に、テーブルS２をテーブルRとみなし、部分集合S∩S１∩S２をテーブルSとみなし、全ての項について同様に単項クエリ（X;x）を実行し、例えば危険率が５％以下、かつ再現率を最大とする肯定単項クエリを求める。しかし、かかる条件を満たす単項クエリが見つからない場合は、単項クエリ（X２: x２)にψを継ぎ木する。図５はそのときのツリー
構造を示したものである。
【００４２】
ψを継ぎ木された場合は、ψを継ぎ木されたノードの否定単項クエリをルートと見なして、当該ルートから全ての項について、単項クエリ（X;x）同じように実行し、ψが継ぎ木されるまで再帰的に実行する。即ち、否定単項クエリ(X２:≠x２)を全ての項について同様に実行し、危険率が５％以下、かつ再現率を最大とする単項クエリ（X３;x３）を求め、ツリー構造を生成する。しかし、危険率が５％以下、かつ再現率を最大の条件を満たす単項クエリが見つからない場合はψを継ぎ木する。図６はそのときのツリー構造を示したものである。
【００４３】
図６に示すように全ての末端ノードがψによって置き換えられたとき、木の生成処理を終結し、ψおよびψに向かう矢印を取り去る。従って、肯定ノード側も否定ノード側もψが継ぎ木された末端が、ツリーの末端ノードとなる。
【００４４】
得られた木構造のルートノードから、すべての末端ノードに至るパスをトレースし、経由する単項クエリをAND結合により論理式を生成する。例えば図６の木では、論理式は、（X１:x１)×(X２:x２)×(X３:x３)＋(X１:x１)×(X２:x２)×(X３:≠x３)＋（X１: x１)×(X２:≠x２)×(X３:x３)＋(X１:x１)×(X２:≠x２)である。
【００４５】
上述した論理式によりクエリQｘを求めることができるのは、単項クエリ(X:x) を実行した結果、テーブルS1には適合部分Xと不適合部分(雑音部分)Y、および漏れた部分Zとが存在する。肯定部分の木をさらに展開していくことは、なるべく多くのXを保存しながら、テーブルS1から、雑音部分Yを取り除いていくプロセスである。このプロセスの最後は適合部分が多数を占めることになり、有意な単項クエリを見つけることができなくなり、プロセスは終結する。一方、否定の木を展開していくことは、漏れた部分Zを取り戻すプロセスであり、そのために最も有利な単項クエリを見つけ出すプロセスである。こうしてSに最も近いタプル集合を再現できる論理式を見出すことができる。
上述の木構造をメモリ上どのように実装するかについては、種種の方式が考えられる．最も直接的なものはANDとORに対応したメモリスタックを用意する方法が好適である。
【００４６】
また、上述のアルゴリズム概説では、連続した数値を取る属性については触れていない。このような属性についてはあらかじめ区間分けしておく方法が妥当と思われる。区間分けの方法については、現在までに様々な方式が提案されているが、発明者が開発したRWS(Random Walk Splitting)法が最も良い評価を得ている。
【００４７】
また、同じ結果を導くクエリの論理式表現は1通りとは限らない。このため再現率、適合率が同じ2つの論理式が与えられたとき、どちらがよい論理式かを評価する指標が必要となる。一般にANDとORで結合された単項クエリの数が少ないものの方がより一般的な論理式と考えられるため、次の指標Mを用いているのが好適である。
【００４８】
M＝-log(単項クエリの数/ 論理式の適用結果タプル数)
実施例２
上述した未知のクエリQｘが有用な手法であるかどうかを、UClリポジトリ（Blake,C,L,&Merz,CJ,,,UClRepositoryofma£hineleamingdatabases,,,
httpl//www,ics,ucLedu/mleam/MLRepository,htm1,lrvine,CAlUniversityofCalifomia,DepartmentoflnformationandComputerScience(1998)）からwineというデータベースをテーブルRとして用いた。このデータベースは、連続値属性数13で事例数178のデータ集合である。
【００４９】
本発明のクエリ導出方法を次のような評価により確認した。テーブルRに単項クエリ（A
;a）を実行し、これによりテーブルSを得る。このテーブルSと近似するデータベースを生成するクエリを実施例１の方法により導出した。なお、導出するクエリは、単項クエリ（A;a）以外のクエリである。そして、導出されたクエリをテーブルRに適用し,導出された結果について再現率、適用率、項の数の評価を行った。
【００５０】
図７に評価結果を示す。先ず、検定の危険率を変化させながら実験を繰り返した。図８は、図７の再現率と適合率をグラフ化したものである。これらの結果から、危険率が１％から10％に範囲において、再現率、適合率ともに90％以上の良好の結果を得た。なお、危険率を大きくするほどその候補クエリによって抽出されるタプルにノイズが多く含まれる。また、候補クエリから抽出されたタプルからノイズを除くために検定を繰り返えすことで、導出されたクエリの項目の数が増える。
【００５１】
次に、テーブルRを半分に分割し、その半分のデータベースをテーブルRとみなして、同様にクエリの導出を行なった。図９に評価の結果を示す。また、図１０に再現率と適合率をグラフ化したものを、図１１に項目の評価式をグラフ化したものを示す。これらの結果から、危険率を５％とすることにより、再現率、適合率ともに90％以上という良好の結果を得た。
【００５２】
次に、テーブルRを4分の1に分割し、その4分の1のデータベースをテーブルRとみなして同様にクエリの導出を行なった。図１２に評価の結果を示す。また、図１３に再現率と適合率をグラフ化したもの、図１４に項目の評価式をグラフ化したものを示す。危険率を５％とすることにより、再現率、適合率ともに90％以上の良好の結果を得た。
【産業上の利用可能性】
【００５３】
本発明によれば、膨大な元データベースの中から、例えばユーザが明確に意識せずに選んだサブ・データベースと、近似するサブ・データベースを高精度で得るに必要なクエリを導き出すことができる。
【図面の簡単な説明】
【００５４】
【図１】本実施例で説明するテーブルの一例を示した図である。
【００５５】
【図２】テーブルRからユーザが明確に意識しない問い合わせ（未知のクエリQｘ）により生成されたサブ・データベスS、近似サブ・データベースSx、再現率、適合率の関係を示した図である。
【図３】ルート(root)を起点として単項クエリ（X１:x１)と補クエリ(X１:≠x１)の２分木等の図である。
【図４】ルートノードから肯定クエリ、否定クエリを実行し、所定の条件を満たす単項クエリをノードとし作成したツリー構造等を示した図である。
【図５】所定の条件を満たす単項クエリが検出されなくなり、ツリーの末端がターミナルクエリ（ψ）になったツリー構造を示したものである。
【図６】完成したツリー構造の図を示したものである。
【図７】サンプルデータベースに本発明のクエリ導出方法を適用して得られた再現率と適合率を示した図である。
【図８】図７に示す再現率と適合率をグラフ化したものである。
【図９】サンプルデータベースを1/2として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率を示した図である。
【図１０】サンプルデータベースを1/2として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率をグラフ化した図である。
【図１１】図９の項目評価式をグラフ化した図である。
【図１２】サンプルデータベースを1/4として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率を示した図である。
【図１３】サンプルデータベースを1/4として得たデータベースについて、本発明のクエリ導出方法を適用して得られた再現率と適合率をグラフ化した図である。
【図１４】図１２の項目評価式をグラフ化した図である。
【特許請求の範囲】
【請求項１】
複数の属性を備えたタプルから成る元データベースに、未知のクエリを実行することにより得られたサブ・データベースと近似するデータベースを生成するに必要なクエリを導出するクエリ導出方法であって、
前記クエリ導出方法は、前記サブ・データベースの全ての項ついて単項クエリを実行し、所定の条件を満たす単項クエリをルートノードとして割付け、
前記所定の条件を満たす単項クエリを前記サブ・データベースについて実行し、これにより肯定データベースを生成し、
前記所定の条件を満たす単項クエリの問い合わせ条件を否定する否定単項クエリを前記サブ・データベースについて実行し、これにより否定データベースを生成し、
前記肯定データベース又は前記否定データベースを前記元データベースとみなし、
前記肯定データベース又は前記否定データベースと前記サブ・データベースとの重複データを前記サブ・データベースとみなし、全ての項について前記肯定クエリ又は否定クエリを実行し、
前記所定の条件を満たす肯定単項クエリと否定単項クエリとを検出し、該肯定単項クエリと否定単項クエリが、前記ルートノードから２分木したノードとなるようにツリー構造を作成し、
前記ノードとなった肯定単項クエリ又は否定単項クエリが、前記所定の条件を満たす単項クエリが検出できなくなるまで、これを再帰的に実行し、ツリー構造を完成させ、
前記ルートノードから末端のノードに至るまでのパスにおいて経由する全ての単項クエリの論理積を作成し、
前記パスごとに得られる論理積の全ての論理和を近似するデータベースを生成するに必要なクエリとして導くことを特徴とするクエリ導出方法。
【請求項２】
前記所定の条件とは、元データベースからランダムにｎ個のタプルを抜き出し生成したランダム・データベースの前記サブ・データベースとの関係における再現率と、前記単項クエリ・データベースの前記サブ・データベースとの関係における再現率とが、同じ適合率となる確率が、あらかじめ定められた危険率以下であり、かつ全ての項について実行した単項クエリのうち再現率が最大である請求項１に記載のクエリ導出方法。
【請求項３】
請求項１に記載のツリー構造の作成は、前記所定の条件を満たす単項クエリの論理式をメモリセルに格納するとともに、該メモリセルにルートノードとしてアドレスを割付け、
前記所定の条件を満たす肯定単項クエリ、及び所定の条件を満たす否定単項クエリが生成される毎に各単項クエリの論理式をルートノードとの関係が特定できるように、前記メモリセルにノードとしてアドレスを割付け、ツリー構造を完成させ、
前記アドレスに基づいて、前記ルートノードから末端のノードに至るまでのパスにおいて経由する全ての単項クエリの論理積の全ての論理和を近似するデータベースを生成するに必要なクエリとして導くことを特徴とするクエリ導出方法。
【請求項１】
複数の属性を備えたタプルから成る元データベースに、未知のクエリを実行することにより得られたサブ・データベースと近似するデータベースを生成するに必要なクエリを導出するクエリ導出方法であって、
前記クエリ導出方法は、前記サブ・データベースの全ての項ついて単項クエリを実行し、所定の条件を満たす単項クエリをルートノードとして割付け、
前記所定の条件を満たす単項クエリを前記サブ・データベースについて実行し、これにより肯定データベースを生成し、
前記所定の条件を満たす単項クエリの問い合わせ条件を否定する否定単項クエリを前記サブ・データベースについて実行し、これにより否定データベースを生成し、
前記肯定データベース又は前記否定データベースを前記元データベースとみなし、
前記肯定データベース又は前記否定データベースと前記サブ・データベースとの重複データを前記サブ・データベースとみなし、全ての項について前記肯定クエリ又は否定クエリを実行し、
前記所定の条件を満たす肯定単項クエリと否定単項クエリとを検出し、該肯定単項クエリと否定単項クエリが、前記ルートノードから２分木したノードとなるようにツリー構造を作成し、
前記ノードとなった肯定単項クエリ又は否定単項クエリが、前記所定の条件を満たす単項クエリが検出できなくなるまで、これを再帰的に実行し、ツリー構造を完成させ、
前記ルートノードから末端のノードに至るまでのパスにおいて経由する全ての単項クエリの論理積を作成し、
前記パスごとに得られる論理積の全ての論理和を近似するデータベースを生成するに必要なクエリとして導くことを特徴とするクエリ導出方法。
【請求項２】
前記所定の条件とは、元データベースからランダムにｎ個のタプルを抜き出し生成したランダム・データベースの前記サブ・データベースとの関係における再現率と、前記単項クエリ・データベースの前記サブ・データベースとの関係における再現率とが、同じ適合率となる確率が、あらかじめ定められた危険率以下であり、かつ全ての項について実行した単項クエリのうち再現率が最大である請求項１に記載のクエリ導出方法。
【請求項３】
請求項１に記載のツリー構造の作成は、前記所定の条件を満たす単項クエリの論理式をメモリセルに格納するとともに、該メモリセルにルートノードとしてアドレスを割付け、
前記所定の条件を満たす肯定単項クエリ、及び所定の条件を満たす否定単項クエリが生成される毎に各単項クエリの論理式をルートノードとの関係が特定できるように、前記メモリセルにノードとしてアドレスを割付け、ツリー構造を完成させ、
前記アドレスに基づいて、前記ルートノードから末端のノードに至るまでのパスにおいて経由する全ての単項クエリの論理積の全ての論理和を近似するデータベースを生成するに必要なクエリとして導くことを特徴とするクエリ導出方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００６−５３７９８（Ｐ２００６−５３７９８Ａ）
【公開日】平成１８年２月２３日（２００６．２．２３）
【国際特許分類】
【出願番号】特願２００４−２３５５７９（Ｐ２００４−２３５５７９）
【出願日】平成１６年８月１２日（２００４．８．１２）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１６年２月１７日 国立大学法人山梨大学主催の「平成１５年度 大学院工学研究科修士論文発表会」において文書をもって発表
【出願人】（８００００００７９）株式会社山梨ティー・エル・オー (11)
【Ｆターム（参考）】
【公開日】平成１８年２月２３日（２００６．２．２３）
【国際特許分類】
【出願日】平成１６年８月１２日（２００４．８．１２）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１６年２月１７日 国立大学法人山梨大学主催の「平成１５年度 大学院工学研究科修士論文発表会」において文書をもって発表
【出願人】（８００００００７９）株式会社山梨ティー・エル・オー (11)
【Ｆターム（参考）】
[ Back to top ]