(57)【要約】      （修正有）【課題】多次元データベースの要約を可視化する。【解決手段】データベースのための問い合わせが多数の要素を含むベクトルとして表される。各要素は、１つのコントロールであり、各コントロールは、１つの現在の設定を有する。データベースは、その問い合わせによって問い合わせられて、現在のシノプシスを生成する。現在のシノプシスは、現在の要約に追加される。現在のシノプシス、現在のコントロールおよび現在のシノプシスを含む現在の要約は、グラフィカルユーザインターフェース上に表示される。現在の要約に追加されるときに、次の要約が現在の要約と最も異なるようにする新たなシノプシスを生成するために、コントロールのための新たな設定が指示される。終了条件に達し、データベースの最も興味を引く要約が作成されるまで、問い合わせること、可視化すること、および指示することが繰り返される。【選択図】図３
2005339548.tif 000002
【特許請求の範囲】
【請求項１】
データベースを要約し、データベースの要約を可視化するための方法であって、
各要素がそれぞれ１つのコントロールであり、各コントロールがそれぞれ現在の設定を有しており、データベースのための問い合わせを複数の要素を含むベクトルとして表すことと、
前記問い合わせによって前記データベースに問い合わせ、現在のシノプシスを生成することと、
前記現在のシノプシスを現在の要約に追加することと、
前記現在のシノプシス、前記現在のコントロール、および前記現在のシノプシスを含む現在の要約を可視化することと、
前記現在の要約に追加されるときに、次の要約が前記現在の要約と最も異なるようにする次のシノプシスを生成するために、コントロールのための新たな設定を指示することと、
終了条件に達し、前記データベースの最も興味を引く要約が作成されるまで、前記問い合わせること、前記可視化すること、および前記指示することを繰り返すことと
を含むデータベースを要約し、データベースの要約を可視化するための方法。
【請求項２】
前記シノプシス毎に、かつ前記要約毎に１つの興味レベルスコアを決定することと、
利用者に対して、各コントロールを調整することによって生成されることができる前記シノプシスの前記興味レベルスコアを指示することと
をさらに含む請求項１に記載の方法。
【請求項３】
前記興味レベルスコアが所定の閾値よりも大きい場合にのみ前記次のシノプシスを追加することをさらに含む請求項２に記載の方法。
【請求項４】
所定の数のシノプシスに対する前記興味レベルスコアを最大にする要約を作成することをさらに含む請求項２に記載の方法。
【請求項５】
前記データベースは、多次元である請求項１に記載の方法。
【請求項６】
前記興味レベルスコアを最も増加させる前記シノプシスによって要約を繰返し拡張することをさらに含む請求項２に記載の方法。
【請求項７】
前記コントロールは、要約コントロール、集計コントロールおよびデータコントロールを含む請求項１に記載の方法。
【請求項８】
前記興味レベルスコアは、前記次のシノプシスが前記現在のシノプシスとどれくらい異なるかによって決定される請求項２に記載の方法。
【請求項９】
前記興味レベルスコアは、前記次のシノプシスが、前記現在の要約が前記興味レベルスコアについて予測するものからどれくらい異なるかによって決定される請求項２に記載の方法。
【請求項１０】
前記興味レベルスコアは、前記シノプシスに関連する前記データベース内のデータの量に依存する請求項１に記載の方法。
【請求項１１】
前記興味レベルスコアは、前記利用者によって与えられる重み付けに依存する請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にデータ要約に関し、より詳細には、多次元データベースの要約を可視化することに関する。
【背景技術】
【０００２】
要約の作業（task）を例示するために、ある利用者が、ある団体の会員登録簿を格納するデータベースへのアクセスを許可され、「ある特定の会員が何歳であるか」という質問に答えるプレゼンテーションを生成することを求められるものと仮定する。可視化は、種々の年齢層の会員数を示すヒストグラムを含むことができる。
【０００３】
その際、その利用者は、予め作成されたグラフに基づいて、いくつかの興味を引く変化を生成することを望むかもしれない。たとえば、あるグラフが、その団体内の女性が男性よりも平均して年齢が低いことを示すことができ、またノースウェストに住んでいる会員が、他の場所に住んでいる会員よりも平均して年齢が高いことを示すことができる。
【０００４】
一般的に、その団体の会員の年齢を要約することは、データベース全体から実効的に特徴を抽出する、比較的少数の可視化表現を選択することを含むであろう。
【０００５】
本発明において用いられる用語では、上記のグラフは、それぞれデータベースのシノプシスを可視化したものであり、シノプシスを集めたものが要約である。
【０００６】
インテリジェントなデータ要約（ＩＤＳ：Intelligent Data Summarization）の目的は、データベース全体から実効的に特徴を抽出する、比較的少数のこれらのグラフを迅速に生成することである。
【０００７】
シノプシスを繰返し生成し、可視化するための数多くの方法が知られている。A. Buja、D. CookおよびD. Swayne「Interactive high-dimensional data visualization」（Journal of Computational and Graphical Statistics, vol. 5, pp. 78-99, 1996）を参照願いたい。それらの方法の大部分では、利用者は、原則的に、全ての興味を引く可能性があるシノプシスを可視化するために、網羅的な探索を実行しなければならない。上記の例では、利用者は、個々の取り得る次元にわたってデータを手作業で調査し、それぞれの組み合わせを検討して、顕著な観察結果が見落とされないようにするであろう。
【０００８】
網羅的な探索は、自動的に実行され、また、さらに調査するに値するか否かが利用者に通知されることが望ましい。探索の情報を可視化したものが提供されることが、さらに望ましい。
【０００９】
要約の作業は、圧縮、機械学習およびデータマイニングに密接に関係する。R. Agrawal、T. ImielinskyおよびA. Swami「Mining association rules between sets of items in large databases」（Proc, of ACM SIGMOD Intl. Conf. on Management of Data, pp. 207-216, 1993）、ならびにR. AgrawalおよびR. Srikant「Mining Sequential Patterns」（Intl. Conf. on Data Engineering, pp. 3-14, 1995）を参照願いたい。
【００１０】
その目的が大規模データベースをより深く理解できるようにすることであるなら、最も密接に関係するのがデータマイニングである。
【００１１】
データベースの可視化
利用者が多次元データベースを調査し、かつ要約を作成するのを助けるために、数多くの可視化方法およびシステムが開発されている。１つの方法は、データベースをある角度から見た多数の相関のある図を提供する。M. Q. W. Baldonado、A. WoodruffおよびA. Kuchinsky「Guidelines for using multiple views in information visualization」（Advanced Visual Interfaces (AVI 2000), pp. 110-119, 2000）を参照願いたい。その方法、およびパラレルコーディネートと呼ばれるさらに複雑な技法は、利用者に数多くの異なるシノプシスを同時に提供し、利用者に興味を引くシノプシスあるいは相関を特定させる。H. Hauser、F. LedermannおよびH. Doleisch「Angular brushing of extended parallel coordinates」（IEEE Visualization 2002 Proceedings. IEEE Determiner Society, 2002）ならびにA. Inselberg「The plane with parallel coordinates」（The Visual Determiner, 1(2), pp.69-92, 1985）も参照願いたい。
【００１２】
それらの方法は、その利用者が多数の図にわたってデータのサブセットをハイライトできるようにするブラッシングとともに用いるときに特に有効である。R. BeckerおよびW. Cleaving「Brushing scatterplots」（Technometrics, 29(2), pp.127-142, 1987）を参照願いたい。しかしながら、データベースが非常に小さい場合を除いて、多数の図を提供するために、依然として利用者が手作業で調査する必要がある。
【００１３】
別の方法は、ＸＧｏｂｉと呼ばれる可視化ツールによって例示される。A. Buja、D. CookおよびD. Swayne「Interactive high-dimensional data visualization」（Journal of Computational and Graphical Statistics, vol. 5, pp.78-99, 1996）を参照願いたい。ＸＧｏｂｉは、データベースを効果的に探索するために、利用者が可視化を連続して改良できるようにすることにより、可視化のリアルタイムで、インタラクティブなコントロールを提供する。さらに、ＸＧｏｂｉは、情報を豊富に含む可視化を提供し、利用者が、さらに調査を進めるために興味を引くシノプシスを突き止めるのを助けるために、動きの使用などの方法を用いる。
【００１４】
データマイニング
大規模データベース内の興味を引くパターンおよび関係を見つけるための種々のデータマイニング技法が知られている。「興味を引くもの」に関する数多くの異なる概念が、R. J. HildermanおよびH. J. Hamilton「Knowledge discovery and interestingness measures: A survey」（Technical Report CS 99-04, Department of Determiner Science, University of Regina, 1999）に記載されている。
【００１５】
連想マイニングは、一般的で、かつ代表的なデータマイニング作業である。R. Agrawal、T. ImielinskyおよびA. Swami「Mining association rules between sets of items in large databases」（Proc, of ACM SIGMOD Intl. Conf. on Management of Data, pp. 207-216, 1993）を参照願いたい。たとえば、連想マイニングタスクは、承認された申込者および承認されていない申込者を記述するデータベースから、誰がローンを承認され、誰がローンを承認されないかを予測するためのルールを生成することができる。たとえば、性別＝男性＾年齢＝［４０‐５０］→ステータス＝承認というルールは、４０〜５０歳の男性がローンを承認される傾向があることを示す。このルールのサポートは、そのデータベース内の４０〜５０歳の男性である申込者のパーセンテージである。そのルールの確信度は、ローンが承認された、それらのレコードのパーセンテージである。
【００１６】
多くの場合に、そのルールの「興味を引くもの」は、たとえば、有意性を決定するためにカイ２乗検定を用いて、そのルールの確信度を、ローンを承認された申込者の全パーセンテージと比較することによって決定される。
【００１７】
１組のルールを有向二次元グラフとして提供することができる。そのグラフでは、要素毎に１つのノード、たとえば、性別＝男性が存在し、ルールを表すエッジがそれらのノードを連結する。可視化では、色およびエッジサイズを用いて、サポートあるいは確信度のような、そのルールの特性を指示することができる。P. Kuntz、F. Fuillet、R. LehnおよびH. Briand「A userdriven process for mining association rules」（Proc. of the 4th European Conf. of Principles of Data Mining and Knowledge Discovery, pp. 160-168, 2000）を参照願いたい。
【００１８】
小さなルールセットのための別の手法は、三次元マトリクスであり、１つのルールの前提部および結論部が１つのセルの場所を決定し、そのセルの高さあるいは色を用いて、そのルールの特性が示される。H. HofmannおよびA. Wilhelm「Visual comparison of association rules」（Computational Statistics, 16(3), 399-415, 2001）を参照願いたい。
【００１９】
Blanchard等は、大規模なルールセットのための、これらの技法およびその制約を説明する。J. Blanchard、F. GuilletおよびH. Briand「Exploratory Visualization for Association Rule Rummaging」（Multimedia Data Mining Workshop(MDM/KDD'03), 2003を参照願いたい。また、彼らは、ルールの特性が球の直径、錐体の高さおよび錐体の色に符号化される三次元「情報ランドスケープ」において、錐体の上にある球として、ルールの集合を表す方法も記載する。
【００２０】
別の方法は、利用者が多次元データベースを調査するのを追跡し、誘導する。S. Sarawagi「User-adaptive exploration of multi-dimensional data」（Proc. of the 26th VLDB Conference, pp. 307-316, 2000）を参照願いたい。その方法は、最大エントロピー原理を用いて、データキューブの未調査の部分の利用者の期待値をモデル化する。その方法は、データベースのある指定された次元を予測する能力を最も改善することになるデータまで利用者を誘導する。
【００２１】
要約対データマイニング
１つの大きな違いは、要約が、１組の興味を引くシノプシスを見つける典型的なデータマイニングタスクではなく、興味を引くシノプシスのサブセットを構成することを含むことである。微妙な違いは、従来技術が個々のシノプシスの品質を評価するのに対して、本発明は、完全な１組のシノプシスの品質に関心があることである。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
本明細書において定義されるような要約は、利用者に全てのシノプシスについての情報を如何に良好に知らせるかという観点から、シノプシスを評価することを含む。この根底を成すのは、利用者が要約から推測するものについての仮定である。その目的が所与のデータベースを最も良好に近似するコンパクトなモデルを構成することであるので、この特徴によれば、要約は不可逆的圧縮あるいは機械学習に最も類似している。
【課題を解決するための手段】
【００２３】
本発明は、大規模な多次元データベースをインテリジェントに要約するための方法を提供する。それゆえ、本発明は、要約と対話するための可視化手段を提供する。
【００２４】
データベースのための問い合わせが多数の要素を含むベクトルとして表される。各要素は、１つのコントロールであり、各コントロールは、１つの現在の設定を有する。データベースは、現在のシノプシスを生成するための問い合わせによって問い合わせされる。現在のシノプシスは、現在の要約に追加される。現在のシノプシス、現在のコントロールおよび現在のシノプシスを含む現在の要約は、グラフィカルユーザインターフェース上に可視化される。
【００２５】
現在の要約に追加されるときに、次の要約が現在の要約と最も異なるようにする新しいシノプシスを生成するために、コントロールのための新たな設定が指示される。
【００２６】
終了条件に達し、データベースの最も興味を引く要約が作成されるまで、問い合わせすること、可視化することおよび指示することが繰り返される。
【発明を実施するための最良の形態】
【００２７】
図３は、データベースを要約し、データベースの要約を可視化するための本発明による方法３００を示す。そのデータベースのための問い合わせ３０１が多数の要素を含むベクトルとして表される。各要素は、１つのコントロールであり、各コントロールは、現在の設定を有する。
【００２８】
データベース３０２が問い合わせ３０１によって問い合わせられて（３１０）、現在のシノプシス３０３が生成される。現在のシノプシスは、現在の要約３０４に追加される（３２０）。現在のシノプシス、現在のコントロールおよび現在のシノプシスを含む現在の要約が、グラフィカルユーザインターフェース２００上に可視化される（３３０）。
【００２９】
現在の要約に追加されるときに、次の要約が現在の要約と最も異なるようにする新たなシノプシスを生成するために、コントロールのための新しい設定が指示される（３４０）。
【００３０】
終了条件３０５に達し、データベースの最も興味を引く要約が作成されるまで、問い合わせること、可視化することおよび指示することが繰り返される。
【００３１】
用語
最初に、本発明による要約作成、データマイニングおよび可視化のために、用語および一定の枠組みを説明する。
【００３２】
かなり抽象的なレベルでは、データベースシステムが１組の問い合わせをサポートする。問い合わせ毎に、出力として複数の統計量が生成される。より形式的には、データベースＤが１組のペア＜ｑ、ｓ＞を含む。ただし、ｑは、１組の取り得る問い合わせＱからの１つの問い合わせであり、ｓは、１組の取り得る統計量からの１つの統計量である。問い合わせ−統計量のペアがシノプシスと呼ばれる。
【００３３】
データベース、問い合わせおよび統計量のさらに具体的な例が後に記載される。本発明では、多次元データベースへの問い合わせが特に対象にされる。便宜上、ＱＵＥＲＹ（Ｄ、ｑ）が、データベースＤ内で問い合わせｑとペアにされる統計量である。
【００３４】
データベースＤの要約は、データベースＤ内のシノプシス＜ｑ、ｓ＞のサブセットである。
【００３５】
伝達関数は、要約Ｍおよび問い合わせｑから統計量ｓへのマッピングである。返される統計量ｓは、要約Ｍを見た利用者が、データベースＤへの問い合わせｑが生成すると期待するはずのものである。
【００３６】
理想的には、Ｄを完全に反映する簡潔な要約Ｍが生成されることが望ましい。すなわち、以下の式のようなＭが見つけられるであろう。
∀ｑｉ∈Ｑ：ＣＯＮＶＥＹ（Ｍ、ｑｉ）＝ＱＵＥＲＹ（Ｄ、ｑｉ）
【００３７】
しかしながら、データベースを完全に要約して短い要約にすることは、不可能であるかもしれない。入力として１つの問い合わせを取り込む重み付け関数Ｗが、負でない実数を返す。その数が大きいほど、その問い合わせが「重要」になる。
【００３８】
相違関数Ｐが、ＱＵＥＲＹによって生成される統計量と、伝達関数によって生成される統計量とを取り込み、差スコアを返す。差スコアは、それら２つの統計量がどれくらい異なるかを指示する負でない実数である。０の差スコアは、それらの統計量が同一であることを意味する。正の差スコアは、相違を意味する。本発明は、以前に集計された統計量と最も異なる統計量を見つけることを対象にする。
【００３９】
本発明の目的は、次のシノプシスがそれぞれ、以前のシノプシスからなる要約に追加されるときに、「興味を引く」要約を作成するような、多数のシノプシスを生成することである。
【００４０】
要約問題
本発明によれば、要約問題は、タプル＜Ｄ、Ｃ、Ｗ、Ｐ＞として定義される。ただし、Ｄはデータベースであり、Ｃは伝達関数であり、Ｗは重み付け関数であり、Ｐは相違関数である。
【００４１】
ある特定の要約問題Ｚ＝＜Ｄ、Ｃ、Ｗ、Ｐ＞および要約Ｍの場合、ＳＣＯＲＥ（Ｚ、Ｍ）は、全ての実際のシノプシスと伝達されたシノプシスとの間の重み付けされた相違の和である。
【００４２】
【数１】
2005339548.tif 000003
【００４３】
要約問題Ｚ、要約Ｍおよびシノプシス＜ｑ、ｓ＞の場合、ＩＮＴＥＲＥＳＴＩＮＧＮＥＳＳ（Ｚ、Ｍ、＜ｑ、ｓ＞）は、ＳＣＯＲＥ（Ｚ、Ｍ＋＜ｑ、ｓ＞−ＳＣＯＲＥ（Ｚ、Ｍ））と定義される。
【００４４】
興味を引くシノプシスを見つける（ＦＩＳ：Find-Interesting-Synopses）問題は、要約問題Ｚ、要約Ｍおよび閾値ｈを取り込む。ただし、ｈは、実数である。ＦＩＳ問題は、要約Ｍに関して、ｈよりも大きなＩＮＴＥＲＥＳＴＩＮＧＮＥＳＳを有する全てのシノプシスを見つける。
【００４５】
要約問題Ｚのための最良優先要約は、全ての０≦ｉ≦ｎの場合に、系列＜ｑ０、ｓ０＞、・・・、＜ｑｎ、ｓｎ＞であり、ＩＮＴＥＲＥＳＴＩＮＧＮＥＳＳ（Ｚ、｛＜ｑ０、ｓ０＞、・・・、＜ｑｓ−１、ｓｓ−１＞、＜ｑｉ、ｓｉ＞｝）を最大にする。
【００４６】
サブセット最大要約（ＭＳＳ：Maximally-summarizing-Subset）問題は、要約問題Ｚおよび整数ｋを取り込み、ＳＣＯＲＥ（Ｚ、Ｍ）を最大にする長さｋの要約Ｍを返す。
【００４７】
ＦＩＳは、連想マイニングをモデル化することができることに留意されたい。この場合、１組の問い合わせは、全ての取り得るルールを含む。問い合わせ毎の統計量は、その確信度であり、おそらくサポートである。伝達関数は、ルールによって生成される「ベース統計量」を除いて、左辺において何も制限することなしには、利用者が１つのシノプシスから異なるシノプシスを推測できないことを指示する。同じように制限された伝達関数を有するＦＩＳ問題を用いて、２つの属性間の相関のような、他のタイプの興味を引く統計量を発見するための連想マイニング手法を説明することができる。
【００４８】
次に、ＭＳＳ問題を記載するが、利用者が次に要約に追加するものを判断するインタラクティブなシステム内でさらに扱いやすく、さらに有用であることから、最良優先要約を生成することに焦点を当てる。
【００４９】
データベースおよび要約
本発明は、１組の属性ａｉ、・・・、ａｎおよび限られた１組のレコードＥとして表すことができるデータベースに関し、各レコードｅは、属性ａ毎に１つの値を規定する。
【００５０】
属性ａは、各レコードｅ内のその値が数字であるときには数字で示され、数字でない場合には、その属性は記号である。
【００５１】
統計量のタイプ
図１Ａ〜図１Ｄに示されるように、本発明は、４つのタイプの統計量をサポートする。
【００５２】
点統計量１０１は、選択された数値属性の値を集計する。たとえば、点統計値は、ある人々のサブセットの所得の平均値あるいは中央値を記述することができる。
【００５３】
頻度統計量１０２は、規定された目標値に等しい、規定された属性の値のパーセンテージを決定する。たとえば、頻度統計量は、ローンの申込みのサブセットから承認されたローンのパーセンテージを指示することができる。連想ルールは、頻度統計量に直に対応する。
【００５４】
内訳統計量１０３は、規定された記号属性の値毎の頻度を決定する。たとえば、内訳統計量は、ある人々のサブセットにわたる占有分布をヒストグラムとして示すことができる。
【００５５】
ペアプロット統計量１０４は、ある規定された数値属性の、第２の規定された属性の値毎の点統計量の系列を決定する。たとえば、ペアプロット統計量は、教育レベル毎の平均的な給料を示すことができる。
【００５６】
点統計量および頻度統計量がいずれも１つの数を生成すること、ならびに内訳統計量およびペアプロット統計量がペア＜ｘ、ｙ＞の系列を生成することに留意されたい。ただし、各ｙは、１つの数である。内訳統計量は、円グラフあるいは棒グラフとして可視化することができる。ペアプロット統計量は、ｘの値が数値であるか、記号であるかによって、線グラフあるいは棒グラフとして可視化することができる。
【００５７】
コントロール
データベース３０２への問い合わせ３０１は、ベクトルとして表される。ベクトルの各要素は、コントロールと呼ばれる。本発明のデータベースの場合、３つのカテゴリのコントロール、すなわち要約コントロール、集計コントロールおよびデータコントロールが存在する。
【００５８】
要約コントロールは、統計量のタイプを選択し、その統計量を使用して、その統計量のために必要とされる属性および値を規定する。各要約タイプは、異なる入力を必要とするので、問い合わせベクトルの要素のうちのいくつかは、要約タイプの選択に基づいて無視される。
【００５９】
集計コントロールは、ポイントおよびペアプロット統計量のための集計関数を規定する。
【００６０】
データコントロールは、レコードのうちのどのサブセットが統計量を決定するために用いられるかを決定する。属性ａｉ毎に１つのデータコントロールが存在する。たとえば、「地域」属性のためのデータコントロールを用いて、その問い合わせを、ノースウエストの人々のみに限定することができる。データコントロールのための取り得る設定は、その属性が有することができる値の任意のサブセットあるいは範囲である。実際には、ユーザインターフェースあるいは探索過程は、全てのオプションをサポートするとは限らないかもしれない。たとえば、数値コントロールの場合、本発明のシステムは、単純なヒストグラムを決定し、それは、ある一定の数の範囲、たとえば、６を生成する。各範囲は、データベースからの概ね同じ数の固有の値を含む。
【００６１】
伝達関数
伝達関数は、多数の異なる方法で実施することができる。たとえば、認知モデリング手法を実施し、利用者が所与の要約から実際に学習したことを決定しようとすることができる。最終的な目的は、データベースを最大限に理解することであるので、これは、ほぼ間違いなく「最も高度な（gold standard）方法」である。当然、その手法は、極めて意欲的ではあるが、情報への人々の反応の多様性に起因して、最終的にはおそらく不可能である。
【００６２】
別法では、情報理論による手法を実施し、最小エントロピーあるいは最大尤度に基づいて伝達関数を用いることができる。その手法は、正確であるという利点を有するが、多くの場合に、利用者が行う推測を過大評価するであろう。
【００６３】
好ましい手法は、非常に簡単な伝達関数を使用し、その伝達関数は、利用者が行う推測についての仮定を最小限にとどめ、伝達関数そのものが利用者に容易に伝達されることができる。
【００６４】
トレードオフをさらに深く理解するために、ある団体の全ての会員の平均年齢が４０歳であり、レコードのうちの半分が、その平均年齢が３０歳の女性のものであることを利用者が教えられるものと仮定する。当然、利用者が、男性の平均年齢が５０歳であるという結論を出すことを期待することができる。しかしながら、７つのレコードのうちの５つが女性のものである場合には、利用者が、男性のための平均年齢が６５歳であるとの結論を出すものと仮定するのは、おそらくあまりにも楽観的である。ここで、利用者が、ニュージャージに住む会員の平均年齢が４５歳であることを教えられるものと仮定する。本発明の伝達関数は、利用者がニューヨークに住む人々について考えるときに、何を教えてくれるべきであろうか。利用者が、彼らの平均年齢が４０歳よりわずかに低いと推測することを期待することができると思われる。しかしながら、別の妥当な可能性は、利用者が、ニューヨークとニュージャージが地理的に互いに近いので、類似の会員を有することになると推測することである。本発明は、利用者が推測するとシステムが想定するものについて利用者に知らせることにより、そのように混乱する可能性を明白に避けようとする。
【００６５】
それゆえ、本発明の好ましい手法は、簡単な伝達関数を採用し、人々が所与の問い合わせよりも一般的であるシノプシスからのみ推測を行うことを想定する。たとえば、上記の例では、ニューヨークの人々の平均年齢が４０歳であることを利用者が推測することが期待される。ニュージャージの女性会員の年齢を尋ねられる場合には、ニュージャージからの人々を記述するシノプシスがニュージャージからの女性よりも一般的であるので、利用者は４５歳を推測するであろう。
【００６６】
そのデータコントロール設定においてのみ異なるシノプシスの場合に、あるシノプシスが他のシノプシスのデータの上位集合を記述する場合には、そのシノプシスは、別のシノプシスと同程度に一般的であると言われ、それが完全な上位集合を記述する場合には、より一般的であると言われる。要約ＭがシノプシスＰについて伝達するものを予測するために、シノプシスｐと同程度に一般的である１組のシノプシスＭｒｅｌ⊂Ｍが見つけられる。その後、Ｍｒｅｌ内の別のシノプシスよりも一般的である、Ｍｒｅｌ内の任意のシノプシスが除去される。
【００６７】
Ｍｒｅｌが空である場合には、その要約Ｍは、シノプシスｐについて何も伝達しないものと仮定される。Ｍが１つのシノプシスを含む場合には、それが本発明の伝達関数によって返される。Ｍｒｅｌが多数のシノプシスを含む場合には、何をすべきかを決定することは、難しい問題である。簡単な方法、たとえば、平均することにより、それらの統計量が結合される。内訳統計量およびペアプロット統計量の場合、それらの統計量内の値毎に同じことが行われる。
【００６８】
重み付けおよび相違関数
重み付け関数は、最も興味を引くのがどの属性、属性の組み合わせ、あるいは集計方法であるかを利用者に指示することができる。そのデータコントロール設定と一致するレコードの数によって問い合わせを重み付けするという簡単な方式が用いられる。別法では、その重み付けは、統計的な有意性を測定するように規定することができる。
【００６９】
それぞれが１つの数として表される、２点あるいは頻度統計量間の差を決定するために、簡単な関数が用いられる。ＱＵＥＲＹによって返される値と、ＱＵＥＲＹによって返される値によって割られた、伝達関数によって返される値との間の差の絶対値が単に決定される。
【００７０】
内訳およびペアプロットのための相違関数は、利用者が、たとえば、あるプロットの最小点あるいは最大点が存在する場所にのみ、あるいはあるラインプロットが正の勾配を有するか、負の勾配を有するかのみに興味があるかもしれないので、若干複雑である。
【００７１】
比較シーケンス
本発明の好ましい実施形態は、ペアの２つのシーケンスを比較する５つの方法を含む。
【００７２】
ｍｉｎＤｉｆｆ（Ｓ１、Ｓ２）を、ｙが最小である場合の＜ｘ、ｙ＞∈Ｓ１のｘの値と、ｙが最小である場合の＜ｘ、ｙ＞∈Ｓ２のｘの値との間の差の絶対値であると定義する。
【００７３】
ｍａｘＤｉｆｆ（Ｓ１、Ｓ２）を、Ｓ１およびＳ２においてｙの値が最大である場合のｘの値の間の差の絶対値であると定義する。
【００７４】
値（Ｓ１、Ｓ２）を、Ｓ１およびＳ２において全ての対応する値のための差の絶対値の和、すなわち＜ｘ、ｙ＞∈Ｓ１および＜ｘ、ｙ＞∈Ｓ２のような全てのｘ、ｙｉおよびｙｊのためのΣ｜（ｙｉ−ｙｊ）｜であると定義する。
【００７５】
勾配（Ｓ１、Ｓ２）を、Ｓ１およびＳ２において対応する隣接する点の間の勾配の差の絶対値の和、すなわちΣ（ｙ１−ｙ２）／（ｙ３−ｙ４）であると定義する。ただし、＜ｘｉ、ｙ３＞およびｈｘｉ＋１；ｙ２ｉは、Ｓ１における連続した点であり、＜ｘｉ＋１、ｙ４＞は、Ｓ２における連続した点である。
【００７６】
トレンド（Ｓ１、Ｓ２）を、統計量内の対応する隣接する点の間のトレンド−比較の和であると定義する。ただしトレンド−比較は、勾配のうちの一方が負であり、他方が正であるときに２であり、勾配のうちの一方が厳密に０であるときに１であり、他の場合には０である。
【００７７】
これらの関数が組み合わせられて、入力として２つのシーケンスおよび５つの利用者が変更可能な重みｐｍｉｎ、ｐｍａｘ、ｐｖａｌｕｅｓ、ｐｓｌｏｐｅおよびｐｔｒｅｎｄを取り込む１つの関数にされ、上記の５つの比較関数の和に、それらの所与の重みを掛けたものが返される。実際には、１つの重みは、多くの場合に１．０に指定され、残りは０の重みを指定される。
【００７８】
ａｎｙｔｉｍｅ法
ここで、所与の要約Ｍの場合のＩＮＴＥＲＥＳＴＩＮＧＮＥＳＳ（Ｚ、Ｍ、Ｓ）を最大にするシノプシスＳ＝＜ｑ、ｓ＞を見つけるためのａｎｙｔｉｍｅ法について説明する。すなわち、その方法は、次の要約を現在の要約とは最も異なるようにする次のシノプシスを見つける。「ａｎｙｔｉｍｅ」は、その方法がいつでも終了されることができ、それでも妥当な結果を生成することができることを意味する。その方法は、オプションでは、探索を限定するための１組のデータあるいは集計コントロール設定を与えることができる。
【００７９】
たとえば、利用者は、ｑにおいて「地域＝ノースウエスト」と指定するかもしれない。その方法が終了まで実行される場合には、その方法は、利用者の限定を満たす最適なシノプシスＳを見つけ、要約Ｍに追加する。その方法が早期に終了する場合には、その方法は、最適なシノプシスへの良好な近似を見つける。
【００８０】
その方法は、「最適な」シノプシスを得るために繰返し適用することができる。１つまたは複数のステージにおいて、その方法が早期に終了される場合には、最適なシノプシスの近似が見つけられる。
【００８１】
取り得るシノプシスの指数関数の数値が求められなければならないが、式（１）にしたがって、単一のシノプシスのＩＮＴＥＲＳＴＩＮＧＮＥＳＳを完全に求めるには、完全な、指数関数的に大きな１組の問い合わせに対してシノプシスを処理する必要がある。
【００８２】
それゆえ、任意の時点において、所与の要約Ｍに追加するための候補として、かつ全体にわたって加算され、式（１）を近似するための問い合わせとして機能するシノプシスのサブセットのみを考慮する構造が提供される。
【００８３】
最終的には、全てのシノプシスおよび問い合わせが考慮される。その方法によって考慮される各属性ａｉが個別の１組の取り得る値を有し、１つの属性のためのコントロールが、その属性を単一の値に限定するか、全ての取り得る値を許可するかのいずれかであるものと仮定する。
【００８４】
すなわち、「ＡＬＬ」と呼ばれる、１つの属性のための単集合コントロール設定のみが全集合を許可する。この限定は、必要ではないが、この限定は、その扱いやすさを大幅に改善する。
【００８５】
この限定は、データマイニングにおいて、分離的なルールではなく、連結的なルールのみを探索することに対応する。同様に、利用者が所与のコントロールの場合に非ＡＬＬ値を指定する場合には、本発明の方法は、そのコントロールのための他の値を全く考慮しない。
【００８６】
コントロールツリー
本発明では、ツリー構造を用いて、コントロールのための設定値の全ての許可される組み合わせが探索される。本発明は、集計コントロール設定の組み合わせ毎に個別のツリーを保持し、それらは、許可される集計関数毎の１つのツリーに相当する。
【００８７】
そのツリーは、問い合わせノード（Ｑ）および値ノード（Ｖ）が交互に配置された層から構成される。各問い合わせノードは、１つの問い合わせに対応し、すなわち、同等にデータベースのサブセットのためのシノプシスに対応する。ルートノードは、所与のコントロール設定が与えられる場合には、その所与のコントロール設定によって許可されるデータベースのサブセットのためのシノプシス（ＳＹＮ）に対応する。
【００８８】
問い合わせノードから値ノードへの各ブランチは、無制限のデータコントロールのうちの１つに対応し、各ブランチは、その後、新たな問い合わせを得るために制約され得る。値ノードから問い合わせノードへの各ブランチは、その値ノードに導くブランチに関連付けられるコントロールのための取り得る非ＡＬＬ値のうちの１つに対応する。
【００８９】
取り得る値毎に１つの子が存在する。それゆえ、ツリーの第３のレベルにある問い合わせノードは、１つのデータコントロールに非デフォルト値を割り当てることによって得られる全ての取り得る問い合わせを表し、第５のレベルは、２つのデータコントロールに非デフォルト値を割り当てることによって得られる全ての問い合わせを表し、それ以降も同様である。
【００９０】
本発明は、冗長なコントロール設定を避けるためにブランチを削除する。こうして、それぞれ取り得る問い合わせは、完全に拡張されたツリーにおいて、厳密に１つの問い合わせノードによって表される。この枠組みは、データベースに関して有利な解釈を有する。
【００９１】
各ノードは、データのサブセットに対応する。ルートノードは、全ての初期データを保持する。問い合わせノードは、そのデータの全てをその各子ノードに渡し、一方、値ノードは、その子ノードの間でそのデータを分ける。すなわち、各レコードは、その値がそのレコード内の属性ａの値と一致する子ノードに進む。ただし、ａは、値ノードに導くコントロールに対応する属性である。ノードがデータを含まない場合には、もはやノードを拡張する必要はない。
【００９２】
シノプシスＳを現在の要約Ｍに追加するためのスコアを計算するために、以下の式によってＳＣＯＲＥ（Ｚ、Ｍ＋Ｓ）が計算される。
【００９３】
【数２】
2005339548.tif 000004
【００９４】
この計算は、力ずくで行われることができるが、本発明の方法は、空のツリーで開始して、問い合わせノードを一度に１つずつツリーに追加する。
【００９５】
これらのノードに対応する問い合わせは、Ｑ’⊆Ｑで表される。Ｑ’内の問い合わせノードに対応するシノプシスＳ毎に、以下の式によって表される、そのスコアが追跡される。
【００９６】
【数３】
2005339548.tif 000005
【００９７】
Ｑ’＝Ｑのとき、要約に追加することができる全ての取り得るシノプシスの場合のスコアがわかっている。式（３）は、実効的なａｎｙｔｉｍｅ法を与えるとき、早期に中止される場合には、本発明の結果が、完全な１組のＱの代わりに、部分的な１組の問い合わせＱ’に基づくことを示す。
【００９８】
任意の時点で、最も高い現在のスコアを有する問い合わせノードは、現在の要約に追加されることになる最良の取り得る選択であると考えられる。すなわち、最も異なるシノプシスが追加される。ツリーを完全に拡張することなく探索を終了するためのいくつかの方法がある。その探索は、所与の制限時間に達した後に、あるいはツリーが所与の深さまで拡張された後に終了されることができるか、あるいはその重み、あるいは別法では、それが含むレコードの数が所与の閾値未満に減少する場合には、ノードを取り除くことができる。経験的には、最後のオプションが特に有用であることが示唆される。
【００９９】
ツリーは、深さを優先して、あるいはブランチを優先して拡張することができる。深さ優先探索は、メモリをより効率的に利用するが、ブランチ優先探索は、制限時間が用いられる場合に、あるいはその結果がプロセス実行中に利用者に対して表示されている場合により適している。
【０１００】
最も有用な手法は、ツリーをインタラクティブに深くしていることである可能性が高く、それは、両方のタイプの探索を組み合わせる。ここで、式（３）による計算が如何に効果的に実行されるかについて説明する。
【０１０１】
シノプシスＳを有する問い合わせノードがツリーに追加されるとき、要約Ｍ＋Ｓのためのスコアを求める必要がある。これは、力ずくで計算される。しかし、一方では、式（３）において、ＳをＱに追加する効果を反映するために、現時点で既に同様にツリー内にある他のシノプシスＳ’にそれぞれ対応するスコアも更新する必要がある。
【０１０２】
すなわち、ｑがＳに関連付けられる問い合わせである場合には、シノプシスＳ’毎に、付加的な項Ｗ（ｑ）×Ｐ（ＱＵＥＲＹ（Ｄ、ｑ）、Ｃ（Ｍ＋Ｓ’、ｑ））を考慮しなければならない。
【０１０３】
ノードがツリーに追加されるとき、現在の１組のノードＱ’に基づく推定スコアが増減することができる。第２の事実に対応する問い合わせノードをツリーに追加するとき、第１の事実に対応する問い合わせノードのスコアが減少する。再び、その方法が最終的に終了するまで実行される場合には、要約毎に正確な値が決定されることに留意されたい。
【０１０４】
重みがレコードの数に対応する場合には、ツリー構造において高い重みのノードに早期に達成し、それは、その方法が早期に終了するときでも、本発明によって推定された値が、取り得る要約をランク付けする際に概ね正確であることを示唆している。
【０１０５】
インタラクティブなデータベース調査
図２は、本発明によるインタラクティブなグラフィカルユーザインターフェース２００を示す。
【０１０６】
本発明による可視化は、ＩＤＳガイダンスがない場合であっても、適度に有用なデータ調査ツールを提供するように作られており、要約をサポートするためのいくつかの新規の態様を含む。
【０１０７】
インターフェース２００は、３つのウインドウ、すなわち、問い合わせを表現し、作成し、提示するための問い合わせウインドウ２１０と、問い合わせから生じるシノプシスを表示する結果ウインドウ２２０と、対象となるシノプシスを収集するために用いられる要約ウインドウ２３０とを含む。
【０１０８】
問い合わせウインドウは、利用者がコントロール毎に現在の設定を指定し、データベースに問い合わせできるようにする「ウィジェット（widget）」２１１を含む。また問い合わせウインドウは、使用すべき統計量のタイプを選択するためのメニュー２１２も含む。統計量のタイプに応じて、問い合わせウインドウは、関連する属性および値を選択するためのメニューを含む。
【０１０９】
また、問い合わせウインドウは、「更新」を付されたボタン２１３も含む。利用者は、コントロールが更新された後にこのボタンを押し、新しいコントロール設定を用いて問い合わせを再提示することが望ましい。
【０１１０】
結果として生成された次のシノプシスが、結果ウインドウ２２０に表示される。統計量は、グラフで提供され、問い合わせは、グラフのタイトルに表示される。要約ウインドウ２３０は、シノプシスの集合を含む。
【０１１１】
各行によって、利用者は、１つのコントロールを設定できるようになる。行は、コントロールの名称を表示し、その後に、そのコントロールのための１組の現在の値が表示される。利用者は、それらをクリックすることによって、それらの値を選択するか、あるいは選択しないことができる。データコントロールのために、それらの値の任意の部分が選択されてよい。それらの値のうちのいずれかが選択された場合には、選択された値は、関連する属性のための選択された値を有するレコードを含むようにデータを限定する。
【０１１２】
データコントロールの値のうちのいずれも選択されない場合には、そのコントロールを基にしてレコードは除外されない。利用者は、一度に１つの値だけを選択することができることを除いて、集計コントロールを同じようにして調整することができる。
【０１１３】
利用者が任意のコントロール値を選択するか、あるいは選択しない度に、現在のコントロール設定に基づいて、１つの問い合わせが直ちに提示され、結果として生成されたシノプシスが結果ウインドウ内に表示される。
【０１１４】
要約ウインドウは、利用者によって収集されたシノプシスを保持する。利用者が「追加」ボタン２１４を押すとき、そのシステムは、全てのコントロールの現在の値を収集する。要約ウインドウ内に、現在のグラフあるいは現在のシノプシスの小さな画像が可視化される。
【０１１５】
利用者が１つのアイテムをクリックして選択するとき、そのコントロール設定は、問い合わせウインドウに復元され、適当なシノプシスが結果ウインドウに表示される。利用者が「削除」ボタン２１５を押すとき、現時点で選択されているシノプシスが要約ウインドウから削除される。
【０１１６】
問い合わせウインドウは、現時点で選択されている統計量のための相違関数をカスタマイズするための１組の相違「ウィジェット」も含むことができる。１組のパラメータ名が統計量の各タイプに関連付けられる。たとえば、内訳統計量およびペアプロット統計量の場合、パラメータ名は「値」、「最小」、「最大」、「勾配」および「トレンド」である。各相違ウィジェットは、全てのパラメータ名を有するドロップダウンメニューと、「ガイド」を付されたボタン２１６とを含む。利用者は、ガイドボタンを押すことによって、相違関数のためのパラメータ値を設定する。パラメータの重みは、その名称の相違ウィジェット上のガイドボタンが押された回数である。ガイドボタンは、その相対的な重みを反映するように陰を付けられる。
【０１１７】
利用者は、「クリア」ボタン２１７を押すことによって全てのパラメータをクリアすることができる。利用者がガイドボタンを押す度に、現在のコントロール設定で、本発明の要約方法が実行される。最初に、要約アルゴリズムは、データおよび集計コントロール内の選択されないボタンのいずれかを押すことによって生成されることができる、各シノプシスの、指定された相違関数を用いる現在の要約に対する興味レベルを決定する。原則的には、現在のシノプシスにはあらゆる「隣接シノプシス」、すなわち、それぞれ現在のコントロール設定への変更を行うことによって生成されることができるシノプシスが存在する。
【０１１８】
その後、興味レベルに対してコントロールボタンに陰を付けることによって、最も興味を引く隣接シノプシスが存在する場所に関して、可視化が視覚的な合図を与える。より暗い陰は、より興味を引くシノプシスを指示する。点統計量のような単一の値の統計量の場合、ボタンの色が、そのシノプシスが期待されるものよりも高いか、低いかを指示し、たとえば、高い場合には赤色に、低い場合には青色になるであろう。
【０１１９】
要約過程が興味を引く隣接シノプシスを決定した後に、その過程は、その探索を続け、Ｎ個の最も興味を引く非隣接シノプシスのリストを動的に保持する。ただし、Ｎは、システムへの入力である。これらのシノプシスは、陰付きのボタンのリストとして表される。
【０１２０】
ボタンは、これらのシノプシスのための問い合わせを付される。リストが変化するとき、これらのボタンの陰が変化して、その相対的な興味レベルを反映する。利用者が現在のシノプシスを更新するときには必ず、これは、要約アルゴリズムを再び呼び出し、コントロールボタン、および再生成されることになる非隣接リストに新たな陰が指定されるようにする。
【０１２１】
本発明が好ましい実施形態の例を用いて説明されてきたが、本発明の精神および範囲内で種々の他の改変および変更がなされることが理解される。それゆえ、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内に入るような全ての変形および変更を網羅することである。
【図面の簡単な説明】
【０１２２】
【図１Ａ】本発明による点統計量のグラフである。
【図１Ｂ】本発明による頻度統計量のグラフである。
【図１Ｃ】本発明による内訳統計量のグラフである。
【図１Ｄ】本発明によるペアプロット統計量のグラフである。
【図２】本発明による要約を可視化するためのグラフィカルユーザインターフェースのブロック図である。
【図３】本発明による多次元データベースを要約し、かつ可視化するための方法の流れ図である。
【図１Ａ】
2005339548.tif 000006
【図１Ｂ】
2005339548.tif 000007
【図１Ｃ】
2005339548.tif 000008
【図１Ｄ】
2005339548.tif 000009
【図２】
2005339548.tif 000010
【図３】
2005339548.tif 000011
【外国語明細書】
2005339548.tif 000012
2005339548.tif 000013
2005339548.tif 000014
2005339548.tif 000015
2005339548.tif 000016
2005339548.tif 000017
2005339548.tif 000018
2005339548.tif 000019
2005339548.tif 000020
2005339548.tif 000021
2005339548.tif 000022
2005339548.tif 000023
2005339548.tif 000024
2005339548.tif 000025
2005339548.tif 000026
2005339548.tif 000027
2005339548.tif 000028
2005339548.tif 000029
2005339548.tif 000030
2005339548.tif 000031
2005339548.tif 000032
2005339548.tif 000033
2005339548.tif 000034
2005339548.tif 000035
2005339548.tif 000036
2005339548.tif 000037
2005339548.tif 000038
2005339548.tif 000039
2005339548.tif 000040
2005339548.tif 000041
2005339548.tif 000042
2005339548.tif 000043