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