(57)【要約】【課題】最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング技術を提供すること。【解決手段】本発明によれば、多数のＮトランザクションの標本の大きさｎが、精度要件に基づいて決定される。標本の大きさｎは、少なくとも推定の標本の大きさｎ*程度となるように選ばれる。最後に、アソシエーション・ルールが、標本の大きさｎである多数のＮ個のトランザクションの標本に基づいて、アソシエーション・ルールを多数のＮ個のトランザクションの推定アソシエーション・ルールとして使用するアソシエーション・ルールのマイニングのための任意の方法に従って計算される。
2005502130.tif 000002
【特許請求の範囲】
【請求項１】
最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法であって、
前記多数のＮトランザクションの標本の大きさｎを決定する第１ステップを含み、
前記標本の大きさｎが精度要件に基づいて決定され、
前記標本の大きさｎが、前記精度要件を達成するために多変量推定解析に基づいて決定され、
前記多数のＮトランザクションの推定アソシエーション・ルールとして前記アソシエーション・ルールを使用するアソシエーション・ルールのマイニングのための任意の方法に従って、標本の大きさｎを有する前記多数のＮトランザクションの標本に基づいてアソシエーション・ルールを計算する第２ステップを含む方法。
【請求項２】
前記精度要件が、
標本に基づく推定についての信頼度（１−α）と、
前記多数のＮトランザクションと比較した、標本内の項目ｋの許容できるサポート値の偏差を定義し、項目ｋのサポート値の標準偏差に対して測定される、標本の項目ｋについての相対精度εｋとを含み、
前記標本の大きさｎが、少なくとも推定の標本の大きさｎ*
【数１】
2005502130.tif 000113
程度であり、上式で、
【数２】
2005502130.tif 000114
が自由度ｐのχ２分布の百分位数であり、
ｐが、前記多数のＮトランザクションを特徴付けるための前記異なる項目数である、請求項１に記載のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法。
【請求項３】
前記相対精度εｋ＝εがすべての項目ｋについて同一であり、
前記標本の大きさｎが、少なくとも推定の標本の大きさｎ*
【数３】
2005502130.tif 000115
程度である、請求項２に記載のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法。
【請求項４】
最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法であって、
前記多数のＮトランザクションの標本の大きさｎを決定する第１ステップを含み、
前記標本の大きさｎが、アソシエーション・ルールに対する精度要件に基づいて決定され、
前記精度要件が、標本に基づく推定についての信頼度（１−α）を含み、
前記精度要件が、前記多数のＮトランザクションと比較した、標本内の一定の規則のサポート値の許容できる偏差を定義し、前記一定の規則のサポート値に対して測定される相対精度δを含み、
前記精度要件が、期待サポート値についての下界ｐを含み、
前記標本の大きさｎが、少なくとも推定の標本の大きさｎ*
【数４】
2005502130.tif 000116
程度であり、上式で、
【数５】
2005502130.tif 000117
が標準正規分布の百分位数であり、
前記多数のＮトランザクションの推定アソシエーション・ルールとして前記アソシエーション・ルールを使用するアソシエーション・ルールのマイニングのための任意の方法に従って、標本の大きさｎを有する前記多数のＮトランザクションの標本に基づいてアソシエーション・ルールを計算する第２ステップを含む方法。
【請求項５】
最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法であって、
前記多数のＮトランザクションの標本の大きさｎを決定する第１ステップを含み、
前記標本の大きさｎが、アソシエーション・ルールに対する精度要件に基づいて決定され、
標本に基づく推定についての信頼度（１−α）を含み、
前記精度要件が、前記多数のＮトランザクションと比較した、標本内の一定の規則のサポート値の許容できる正または負の偏差を定義し、前記一定の規則のサポート値に対して測定される相対精度δを含み、
前記精度要件が、期待サポート値についての下界ｐを含み、
前記標本の大きさｎが、少なくとも推定の標本の大きさｎ*
【数６】
2005502130.tif 000118
程度であり、上式で、ｕ１−αが標準正規分布の百分位数であり、
前記多数のＮトランザクションの推定アソシエーション・ルールとして前記アソシエーション・ルールを使用するアソシエーション・ルールのマイニングのための任意の方法に従って、標本の大きさｎを有する前記多数のＮトランザクションの標本に基づいてアソシエーション・ルールを計算する第２ステップを含む方法。
【請求項６】
期待サポート値についての前記下界ｐが、アソシエーション・ルールのマイニングのための前記方法で使用される最小サポート値ｐ＝Ｍｉｎｓｕｐである、請求項４または５に記載のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法。
【請求項７】
最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法であって、
前記多数のＮトランザクションの標本の大きさｎを決定する第１ステップを含み、
前記標本の大きさｎが、アソシエーション・ルールに対する精度要件に基づいて決定され、
前記精度要件が、標本に基づく推定についての信頼度（１−α）を含み、
前記精度要件が、前記多数のＮトランザクションと比較した、標本内の一定の規則のサポート値の許容できる偏差を定義する相対精度ｄを含み、
前記精度要件が、期待サポート値についての上界ｐを含み、
前記標本の大きさｎが、少なくとも推定の標本の大きさｎ*
【数７】
2005502130.tif 000119
程度であり、上式で、
【数８】
2005502130.tif 000120
が標準正規分布の百分位数であり、
前記多数のＮトランザクションの推定アソシエーション・ルールとして前記アソシエーション・ルールを使用するアソシエーション・ルールのマイニングのための任意の方法に従って、大きさｎを有する前記多数のＮトランザクションの標本に基づいてアソシエーション・ルールを計算する第２ステップを含む方法。
【請求項８】
最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法であって、
前記多数のＮトランザクションの標本の大きさｎを決定する第１ステップを含み、
前記標本の大きさｎが、アソシエーション・ルールに対する精度要件に基づいて決定され、
前記精度要件が、標本に基づく推定についての信頼度（１−α）を含み、
前記精度要件が、前記多数のＮトランザクションと比較した、標本内の一定の規則のサポート値の許容できる正または負の偏差を定義する絶対精度ｄを含み、
前記精度要件が、期待サポート値についての上界ｐを含み、
前記標本の大きさｎが、少なくとも推定の標本の大きさｎ*
【数９】
2005502130.tif 000121
程度であり、上式で、ｕ１−αが標準正規分布の百分位数であり、
前記多数のＮトランザクションの推定アソシエーション・ルールとして前記アソシエーション・ルールを使用するアソシエーション・ルールのマイニングのための任意の方法に従って、大きさｎを有する前記多数のＮトランザクションの標本に基づいてアソシエーション・ルールを計算する第２ステップを含む方法。
【請求項９】
期待サポート値についての前記上界ｐがｐ＝０．５である、請求項７または８に記載のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法。
【請求項１０】
アソシエーション・ルールをマイニングするための前記方法が演繹的方法である、請求項１、４、５、７、または８に記載のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法。
【請求項１１】
前記標本が無作為抽出によって抽出される、請求項１、４、５、７、または８に記載のアソシエーション・ルールを決定するためのコンピュータ化データ・マイニング方法。
【請求項１２】
最大ｐ個の異なる項目をそれぞれ含む多数のＮトランザクション内のアソシエーション・ルールの決定を制御するためのクライアント・コンピュータであって、
少なくとも推定の標本の大きさｎ*程度の標本の大きさｎを有する前記多数のＮトランザクションから標本を抽出し、前記推定の標本の大きさが、請求項１ないし１１のいずれかに記載の方法によって決定され、
アソシエーション・ルールを決定するために前記標本をサーバ・コンピュータに送信し、
前記クライアント・コンピュータが、前記サーバ・コンピュータから、前記決定したアソシエーション・ルールを受信し、前記多数のＮトランザクションの推定アソシエーション・ルールとして前記アソシエーション・ルールを使用するクライアント・コンピュータ。
【請求項１３】
前記クライアント・コンピュータが前記推定の標本の大きさｎ*を決定し、または
前記クライアント・コンピュータの代わりに、前記サーバ・コンピュータが、前記推定の標本の大きさｎ*を決定する、請求項１２に記載のアソシエーション・ルールの決定を制御するためのクライアント・コンピュータ。
【請求項１４】
前記プログラムが前記コンピュータ上で動作するときに、請求項１ないし１１のいずれかに記載の方法をデータ処理システムで実行させるためのプログラム。
【請求項１５】
請求項１ないし１１のいずれかに記載の方法をコンピュータに実行させるプログラムを記録したコンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、大規模データベース中の項目間の関係またはアソシエーション・ルールを発見する方法、システム、およびプログラム製品に関する。
【背景技術】
【０００２】
データ・マイニングは台頭しつつある技術領域であり、その目標は、大規模データベースから顕著なパターンまたは興味深い規則を抽出することである。一般には、データ・マイニングの領域には、大量の既存データから「知識」を抽出するのに適用できるすべての方法が含まれる。このプロセス全体は、データベースにおける知識発見として知られている。アソシエーション・ルールを発見することが１つの課題であり、そのためにデータ・マイニング方法が開発された。
【０００３】
アソシエーション・ルール・マイニングは、アグラワル（Agrawal）等によって紹介され（例えば、アール・アグラワル（R.Agrawal）およびアール・スリカント（R. Srikant）、アソシエーション・ルール・マイニング用高速アルゴリズム（Fast algorithmsfor mining association rules）、第２０回ＶＬＤＢ会議議事録（Proc. 20th VLDB Conf.）、１９９４年９月参照）、買物かごの解析に動機付けを得たものであった。この規則は、店のどの物品または商品が一緒に購入されたかを発見するために生成された。より一般には、アソシエーション・ルールは、データベース内のレコードの属性値間の依存関係を発見するのに使用することができる。さらに、特定の買物かごデータは通常、顧客ごとのレコード、取引日付、および顧客が購入した商品からなる。そうしたデータベースに関するアソシエーション・ルールの一例は、パンとミルクを購入した顧客の８０％が卵も購入したということであり得る。アソシエーション・ルールを求めるデータ・マイニング作業は、２つのステップに分けることができる。第１のステップは、最小サポート（minimumsupport）と呼ばれるユーザ指定のある頻度でデータベース中に出現する、アイテムセット（itemset）と呼ばれる項目のすべての組を見つけることからなる。こうしたアイテムセットは大きいアイテムセットと呼ばれる。ｋ個の項目のアイテムセットはｋアイテムセットと呼ばれる。第２のステップは、第１のステップで見つかった大きいアイテムセット間の含意規則を形成することからなる。
【０００４】
アソシエーション・ルールを効率的に生成するためにいくつかのアルゴリズムが開発された。周知であり、非常に成功しているＡＰＲＩＯＲＩアルゴリズムが、アグラワル等により、例えば前述の文書中で開示されている。アソシエーション・ルールを測定する最も重要な値は、１つの項目、または１つの規則中で一緒になったいくつかの項目の相対出現頻度であるサポート値である。
【０００５】
今日、データベースが非常に大規模（エントリ数が数百万レコード以上）である場合、アソシエーション・ルールの生成に著しく時間がかかる可能性がある。アソシエーション・ルールのデータ・マイニングに対して提案された多くのアルゴリズムは、よく出現するアイテムセット（または項目のセット）を判定するのに、データベース上を繰り返し走査する。大規模データベースの場合、データベースを走査する際のＩ／Ｏオーバーヘッドが著しく多くなる可能性がある。この処理時間は、マイニング・アルゴリズム自体を実行するためだけに必要なわけではない。前処理ステップの間にも多くの時間が費やされる。この時間には、データのインポートのための処理時間、さらにはアルゴリズムを適用する目的でデータを変換するための処理時間も含まれる。この準備には、大型ＭＶＳシステムの場合でも、数時間もの貴重なＣＰＵ時間を必要とする可能性がある。
【０００６】
この性能の方程式を改善するために、アソシエーション・ルールの生成のためにデータベース全体を取得する代わりに、標本を抽出し、それに基づいてアソシエーション・ルールを生成することが提案された。この教示は、エイチ・トイボネン（H. Toivonen）、アソシエーション・ルールのための大規模データベースの標本抽出（Sampling Large Databasesfor Association Rules）、第２２回ＶＬＤＢ会議ムバイ（ボンベイ）（Proceedings of the 22nd VLDBConference Mumbai (Bombay)）、インド、１９９６年、ならびにザキ・エム・ジェイ（Zaki, M. J.）、パーササラシー・エス（Parthasarathy,S.）、リ・ダブリュー（Li, W.）、オギハラ・エム（Ogihara, M.）、アソシエーション・ルールのデータ・マイニングのための標本抽出の評価（Evaluationof Sampling for Data Mining of Association Rules）、計算機科学部（Computer ScienceDepartment）、技術レポート６１７（Technical Report 617）、ロチェスター大学（University of Rochester）（１９９６）によって紹介された。
【０００７】
トイボネン等は、「厳密な」（一部の標本に基づくのではない）アソシエーション・ルールを検出するためのアルゴリズムを示した。この教示の中では、標本抽出は、規則のサポート値の事前計算のためだけにアルゴリズム中の１ステップとして使用されている。トイボネン等は、一部の標本に基づく「推定の」（近似の）アソシエーション・ルールを求めるデータ・マイニングという概念については完全に沈黙している。トイボネン等は、標本の大きさに関する必要な境界も開示している。単変量手法を使用して、任意のアソシエーション・ルールのサポート値が推定される。トイボネン等は、二項分布を使用し、チェルノフ境界を適用することにより、真のサポート値と推定サポート値との間の誤差が所与のしきい値を超える確率を計算した。これを用いて、トイボネン等は十分な標本の大きさに関する公式を導出した。
【０００８】
ザキ等は、この概念を取り上げ、標本抽出下で生成された近似アソシエーション・ルールに対するこうした境界を発表した。こうした境界は、チェルノフ境界を含むトイボネンによって提案された単変量手法を使用しても計算された。こうした調査により、必要な標本の大きさが非常に巨大となる可能性があるのでこうした境界はあまり効率的でないことがわかった。ザキ等によって示されているように、必要な標本の大きさは、元のデータベースよりも大きくなる可能性がある（！）。したがって、現況技術の教示は完全に不満足なものであり、現実世界の問題に実際に適用することができない。
【０００９】
したがって、標本に基づくアソシエーション・ルールを求めるデータ・マイニングの手法により、原理上は、前処理ステップならびに解析段階での処理時間を節約することが可能となる。しかし、生じる根本的な問題は、生成されるアソシエーション・ルールの正確さである。標本を適切に選んだ場合、この手法によって現れる誤差を推定することが可能である。この誤差は、十分な標本の大きさを計算することによって制御することができる。しかし現状では、妥当な標本の大きさを求める方法が全く不明である。
【非特許文献１】
アール・アグラワル（R. Agrawal）およびアール・スリカント（R.Srikant）、アソシエーション・ルールのマイニング用高速アルゴリズム（Fast algorithms for mining associationrules）、第２０回ＶＬＤＢ会議議事録（Proc. 20th VLDB Conf.）、１９９４年９月
【非特許文献２】
エイチ・トイボネン（H. Toivonen）、アソシエーション・ルールのための大規模データベースの標本抽出（SamplingLarge Databases for Association Rules）、第２２回ＶＬＤＢ会議ムバイ（ボンベイ）（Proceedings of the22nd VLDB Conference Mumbai (Bombay)）、インド、１９９６年
【非特許文献３】
ザキ・エム・ジェイ（Zaki, M. J.）、パーササラシー・エス（Parthasarathy,S.）、リ・ダブリュー（Li, W.）、オギハラ・エム（Ogihara, M.）、アソシエーション・ルールのデータ・マイニングのための標本抽出の評価（Evaluationof Sampling for Data Mining of Association Rules）、計算機科学部（Computer ScienceDepartment）、技術レポート６１７（Technical Report 617）、ロチェスター大学（University of Rochester）（１９９６）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、アソシエーション・ルールのデータ・マイニング用の技術の性能を改善するという目的に基づく。
【課題を解決するための手段】
【００１１】
本発明の目的は、独立クレームによって解決される。本発明の別の有利な構成および実施形態が、それぞれのサブクレームに記載されている。
【００１２】
本発明は、それぞれ最大ｐ個の異なる項目を含む多数のＮ個のトランザクション内のアソシエーション・ルールを決定するためのデータ・マイニング技術に関する。
【００１３】
本発明によれば、多数のＮ個のトランザクションの標本の大きさｎが、精度要件に基づいて決定される。標本の大きさｎは、少なくとも推定の標本の大きさｎ*程度となるように選ばれる。
【００１４】
最後に、アソシエーション・ルールが、標本の大きさｎである多数のＮ個のトランザクションの標本に基づいて、アソシエーション・ルールを多数のＮ個のトランザクションの推定アソシエーション・ルールとして使用するアソシエーション・ルールのマイニングのための任意の方法に従って計算される。
【００１５】
本発明のすべての実施形態の基礎となる重要な概念は、はるかに小さい標本の大きさを求めることができ、同時にその標本の大きさが、標本の大きさの決定において多数のトランザクションを特徴付ける別のパラメータを導入した場合に、必要な精度要件を満たすということである。このことは、多数のトランザクションの特性を使用しない現況技術の知識（例えば、前述のChernoff境界を参照）とは全く対照的である。そのような特徴付け特性（characterizing property）として、本発明は、多数のトランザクションのサイズＮ、またはトランザクション内に出現する異なる項目の数ｐを使用することを提案する。
【００１６】
もちろん、このような特徴付け特性を含むこうした標本の大きさについての公式を決定した後に、追加の近似技法を適用してこうした特徴付け特性を再び除去することができる。このような追加の近似に基づく標本の大きさであっても、すべての現況技術の推定に勝る著しい改善が表される。
【００１７】
実施例からわかるであろうが、本発明に従って決定される標本の大きさは、元のトランザクションの数よりもずっと少なく、かつ周知の現況技術の手法よりもずっと少ない。したがって、本教示により、アソシエーション・ルールのデータ・マイニングに関して非常に著しい性能の改善が得られる。
【発明を実施するための最良の形態】
【００１８】
図面および明細書において、本発明の好ましい実施形態を説明する。特定の術語を使用するが、そのようにして与える説明は、総称的に、かつ説明として術語を使用しているだけであり、限定のためではない。しかし、添付の特許請求の範囲に記載の本発明のより広い精神および範囲から逸脱することなく、それに様々な修正および変更を行えることは明らかであろう。
【００１９】
本発明は、ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組合せとして実現することができる。どんな種類のコンピュータ・システム、または本明細書に記載の方法を実施するのに適したその他の機器でも適している。ハードウェアとソフトウェアの典型的な組合せは、汎用コンピュータ・システム、ならびにロードされ実行されたときに本明細書に記載の方法を実施するようにコンピュータ・システムを制御するコンピュータ・プログラムでよい。本明細書に記載の方法の実施を可能にするすべての機能を含み、コンピュータ・システム内にロードされたときにこうした方法を実施することができるコンピュータ・プログラム製品内に本発明を組み込むこともできる。
【００２０】
この状況でのコンピュータ・プログラム手段またはコンピュータ・プログラムは、情報処理能力を有するシステムに、直接的に、あるいはａ）別の言語、コード、もしくは表記への変換、ｂ）異なる素材形式としての再現の一方または両方の後に、特定の機能を実行させるための１組の命令の任意の表現、任意の言語、コード、または表記を意味する。
【００２１】
本明細書内では、トランザクション・レコード、または略してトランザクションとは、単に１組の項目を指す。もちろん、そのようなレコードが何らかのコンピュータ・トランザクションの一部であることが必要なわけではない。トランザクション・レコードという表現は、単に歴史的な理由で使用されるに過ぎない。さらに、項目は、現実世界の項目に必ずしも関係しないどんなタイプの属性によっても表すことができる。
【００２２】
導入
データ・マイニングの領域では、いわゆるアソシエーション・ルールが、通常は非常に大規模なデータ・セットから未知の関係または規則を求めるための方法である。この方法は、以下の手続きからなる。１組のいわゆる項目が与えられたとする。これらの項目は、スーパーマーケットかごデータから獲得することができる。この１組の項目の部分集合がいわゆるトランザクションであり、例えばビールとクリスプが１つのトランザクションであり、別のトランザクションは、パンとバターからなることがある。１組の項目は、しばしばアイテムセットとも呼ばれる。したがって、あらゆるトランザクションはアイテムセットを含む。
【００２３】
より正式には、多数のＮ個のトランザクションである買物かごデータに関するアソシエーション・ルールのマイニングの問題は、以下のように述べることができる。
【００２４】
項目とも呼ばれる１組のｐ個の別個の属性値をＩ＝｛ｉ１，ｉ２，．．．，ｉＰ｝とする。（多数のＮ個のトランザクションである）データベースＤ中の各トランザクションＴは、固有識別子ＴＩＤを有し、Ｔ⊆Ｉとなるような１組の項目を含む。アソシエーション・ルールは、Ａ＝＞Ｂという式である。ただしＡはアイテムセットであり、Ｂ⊆Ｉであり、かつ
【数１】
2005502130.tif 000003
である。各アイテムセットは、Ｄ中のトランザクションのｓ％がそのアイテムセットを含む場合、サポートｓを有すると言われる（したがって、サポート尺度は相対頻度を表す）。アソシエーション・ルールは、Ａを含むトランザクションのｃ％がＢも含む場合、信頼度ｃを有すると言われる。すなわちｃ＝ｓｕｐｐｏｒｔ（Ａ∪Ｂ）／ｓｕｐｐｏｒｔ（Ａ）であり、すなわち、トランザクションがアイテムセットＡを含むとした場合に、トランザクションがアイテムセットＢを含む条件付き確率である。例えば、パンとミルクを購入した顧客の８０％が卵も購入したという情報を有することがある。８０％という数字は、規則の信頼度であり、規則のサポートはｓｕｐｐｏｒｔ（Ａ∪Ｂ）である。このようなデータベースからのアソシエーション・ルールのデータ・マイニングは、ユーザ指定の最小信頼度およびサポート値と合致するすべてのこのような規則の組を見つけることからなる。
【００２５】
アソシエーション・ルールを求めるデータ・マイニングの作業は、２つのステップに分けることができる。
１．ｋ＝１，２，．．．についてすべての大きいｋアイテムセットを見つける。
２．こうした大きいアイテムセットから規則を生成する。Ｘが大きいｋアイテムセットであるとして、空でない部分集合Ａ⊂Ｘごとに、形式Ａ＝＞Ｂの規則を生成する。ただしＢ＝Ｘ−Ａであり、この規則が必要な信頼度を有することを条件とする。
【００２６】
すべての前述の尺度は、考慮中の１組のすべてのトランザクションに基づいて求められることに留意されたい。
【００２７】
性能改善のために、この時点で、すべてのトランザクションの組の中からよく選んだ標本によってこうした所望の尺度を推定するよう考慮することができる。標本抽出理論の言い方では、すべてのトランザクションの組は、母集団に対応し、その特性（すなわち相対頻度やその他の尺度）は、よく選ばれた標本によって推定される。この標本に限定して、所望のイベントの相対頻度を、母集団に対するこうしたイベントの相対頻度に関する推定量として計算することができる。
【００２８】
したがって、その場合以下の問題を解決しなければならない。
１．データベースの可能な順序によって引き起こされる可能性のある可能な系統的偏りを可能な限り除去するようにどのように標本を選ぶべきか？
２．最重要：（相対頻度の場合に）推定量の所望の精度を保証するようにどのように標本の大きさを選ぶべきか？
３．推定量の精度をどのように理解すべきか？
【００２９】
最初の質問は、可能な系統的誤差を除去することを目的とするものである。例えば、データベースから例えばｎ番目ごとのレコードを選択することは、このような深刻な系統誤差を選ぶ可能性がある。
【００３０】
第２の質問は、全母集団から取得するトランザクションの数、すなわち標本の大きさについての点を扱っている。直感的に、この問題が標本によって達成することができる精度に関係することは極めて明らかである。これは、１００トランザクションの標本の保証する推定量の精度は、１０，０００トランザクションの標本よりも低いことを意味する。
【００３１】
第３の質問は、次のことを扱っている。すべてのトランザクションの組が１，０００，０００トランザクションを含むと仮定する。１００トランザクションの標本を無作為に取得した場合、全母集団に対する項目Ａの相対頻度についての推定量を計算することができる。１００トランザクションの第２標本を無作為に取得した場合、この第２標本に基づいて項目Ａの相対頻度を推定量として計算することもできるが、両者の計算した頻度は異なる。この手続きを数百回反復した場合、そのように計算した相対頻度は、全母集団に対する項目Ａの相対頻度の周辺にある程度分散することになる。
【００３２】
最もよく知られた標本抽出方式の１つは、いわゆるベルヌーイ標本抽出である。この方式は、データが例えば、レコードをｖｏｎ  １からＮまで番号付けすることができ、データベースをこの順序に沿ってトラバースすることができる順次ファイルまたはデータベースとして与えられると仮定する。あらゆる要素を選ぶことができる確率πが与えられたとして、この標本抽出方式は以下のように機能する。ｉ番目の要素について確率的実験を行い、この要素は確率πで選ばれる。このことは、区間（０，１）に関して乱数を生成することによって行うことができ、考慮する乱数がπよりも小さい場合はｉ番目の要素を取得し、そうでない場合はこの要素を拒絶する。
【００３３】
注：いわゆる線形合同乱数発生器（linear congruent randomnumber generator）の場合、そのような発生器の周期が十分大きいことが極めて重要である。これは、例えば周期５の場合、区間（０，１）から５個の乱数を得た後に、各数字が反復されることを意味する。これはもちろんあまり賢明なことではない。大きな１つの規則として、周期Ｌと母集団の数Ｎは、以下の関係を満たすことが必要である。
【００３４】
【数２】
2005502130.tif 000004
【００３５】
この標本抽出方式のために、標本の大きさは固定数ではなく、確率論の観念では、確率変数の統計パラメータである期待値Ｅおよび分散Ｖａｒが以下のように与えられる。
ＥＢＥ（ｎ）＝Ｎπ
ＶａｒＢＥ（ｎ）＝Ｎπ（１−π）
【００３６】
加えて、αを標本の大きさに対する誤差の指定の確率として、以下の公式によって規定の信頼水準（１−α）に対する信頼区間を計算することが可能である。
【００３７】
【数３】
2005502130.tif 000005
【００３８】
上式で、
【００３９】
【数４】
2005502130.tif 000006
は、所与の確率αに対する標準正規分布Ｎ（０，１）分布の百分位数である。αが与えられた場合、百分位数
【００４０】
【数５】
2005502130.tif 000007
は、単位正規分布確率変数（Ｎ（０，１）と略記する）が確率
【００４１】
【数６】
2005502130.tif 000008
で超過する値である。ゆえに、
【００４２】
【数７】
2005502130.tif 000009
上式で、（Ｎ（０，１）分布確率変数としての）Ｘの密度ｄは、
【００４３】
【数８】
2005502130.tif 000010
【００４４】
ｉ番目の観測が標本内に入れられる包含確率（inclusion probability）πｉは以下によって与えられる。
πｉ＝π
上式は、あらゆる要素についてこの確率が一定であり、規定の確率πに等しいことを意味する。
【００４５】
ｉ番目の要素ならびにｊ番目の要素が同時に標本に入れられる包含確率πｉｊは、この場合にはπ２に等しい。
【００４６】
標本抽出方式の大きな利点は、コンピュータ上で容易に実施できることである。欠点は、標本の大きさがもはや固定量ではなく確率変数であることである。
【００４７】
あらかじめ標本の大きさについての量を固定にすることに関心がある場合、いわゆる単純無作為抽出を用いなければならない。これは、大きさｎの標本に入れられるあらゆる観測についての包含確率が一定である追加の標本抽出方式である。ｎが標本の大きさであり、Ｎが母集団の大きさである場合、
【００４８】
【数９】
2005502130.tif 000011
である。
【００４９】
ｉ番目の要素ならびにｊ番目の要素が同時に標本に入れられる包含確率πｉｊについては、
【００５０】
【数１０】
2005502130.tif 000012
【００５１】
このような標本抽出方式は以下のように実施することができる。ε１，ε２，．．．を、区間［０，１］上に一様に分布する独立な確率変数であると仮定する。
１．
【００５２】
【数１１】
2005502130.tif 000013
である場合は要素ｋ＝１を取得し、そうでない場合は取得しない。
２．続く要素ｋ＝２，３，．．．について、全母集団の最初のｋ−１個の要素の下で既に取得した要素数をｎｋと仮定する。
ｋ番目の乱数εｋのケースで
【００５３】
【数１２】
2005502130.tif 000014
である場合はｋ番目の要素を取得し、そうでない場合は取得しない。
３．ｎｋ＝ｎである場合、手続きは終了する。
【００５４】
このような標本抽出方式の欠点は、既に選んだ要素の数を保存しなければならないことである。一方で、標本抽出手順が所望の要素数で終了するという利点がある。
【００５５】
アソシエーション・ルールのデータ・マイニングのための標本抽出手法
本発明は、全母集団ではなく標本に基づいてアソシエーション・ルールを計算するための方法を説明する。こうしたアソシエーション・ルールを、トランザクションの全母集団の推定アソシエーション・ルールとして使用することを提案する。アソシエーション・ルールのマイニングのための実際の方法を標本のみに限定することができるので、著しい性能改善が達成される。
【００５６】
提案の発明の重要な特徴は、標本の大きさを決定すると同時に規定の精度要件を達成する技法である。前述のように、現況技術とは対照的に、本発明の本質的な概念は、ずっと小さく、同時に、多数のトランザクションを特徴付ける別のパラメータを標本の大きさ決定の際に導入した場合に、必要な精度要件を満たす標本の大きさを決定することができるということである。本発明の一実施形態では、そのような特徴付け特性として、多数のトランザクションの大きさＮを使用することが提案される。本発明の別の実施形態では、トランザクション内に出現する相異なる項目の数ｐが特徴付け特性として使用される。もちろん、そのような特徴付け特性を含むこうした標本の大きさについての公式を決定した後に、追加の近似技法を適用してこうした特徴付け特性を再び除去することができる。このような追加の近似に基づく標本の大きさであっても、すべての現況技術の推定に勝る著しい改善が表される。言い換えれば、多数のトランザクションを特徴付ける別のパラメータを考慮に入れることによってより小さい標本の大きさを達成できるという著しい利点は、後で追加の近似によってこうしたパラメータが再び除去された場合であっても失われない。
【００５７】
現況技術に従って計算される推定（例えばサポート値についての推定）は、単変量解析だけに基づいて行われる。単変量解析とは、単一の値のみを推定することを意味する。
【００５８】
それとは対照的に、本発明の一実施形態は、多変量推定解析を適用することによる全く新しい手法を提案する。多変量解析とは、ベクトルが推定解析を受け、そのベクトルの各成分が推定量であり、すべての成分が同時に推定されることを意味する。例えば、サポート値に関しては、この手法に伴う概念は、単一項目のすべてのサポートを同時に指定の正確さで推定する標本の大きさを有することである。提案の多変量手法は、必要な標本の大きさを決定するための信頼度楕円体に基づくものであり、いくつかの利点を有する。この方法の基本的概念は、項目当たり１つのサポート値を推定するだけでなく、すべてのサポート値を同時に推定することである。このサポート値のベクトルが、現実に存在するサポート値のベクトルに十分近い場合、データ中の構造は標本中でも有効であり、したがって規則は良好な精度を有することになる。言い換えれば、標本は母集団と同じ構造を含み、したがって同じ規則を含む。
【００５９】
多変量解析に基づくそのような実施形態は、ザキ等またはトイボネン等の教示内には示唆されてさえいない。
【００６０】
加えて、データベース中のレコードを可能な限り無作為に選択するようにこうしたレコードを選択する方法を説明する。
【００６１】
単変量モデル
基本的概念は、任意の規則Ｒのサポート値を相対頻度と見なすことができることである。この値は、以下のように推定量によって近似的に測定することができる。
【００６２】
全データベースがＮ個の順次並べられた要素からなると仮定する（ただし、各要素はレコードによって表される）。各要素について、要素が規則をサポートする場合、すなわち規則の項目がレコード中に出現するときに１、規則が要素によってサポートされない場合に０となる２進属性を構築することができる。この２進属性の平均値がサポートである（ｐで表す）。このサポート値について不偏推定量を置換せずに標本を抽出すること（推定量の期待値が推定するパラメータと等しい場合、推定量は不偏である）は、標本中のすべての要素にわたって測定した２進属性の平均である（この平均を
【００６３】
【数１３】
2005502130.tif 000015
で表す）。さらに、サポート値についての信頼区間を構築することができる。信頼区間の背後にある概念は、次のようなものである。標本から抽出された推定量は真の値を近似し、そのことは、推定量がいつも同一の値を取るわけではないことを意味する。しかし多数の標本を抽出し、推定量を計算した場合、こうした値が真の値の周辺に分散することがわかる。次に、計算した推定量の周辺の区間を見つけようと試み、その結果、真の値は所与の確率１−αでこの区間内にあることがわかる。本発明者等の標本方法および推定量の種類によれば、信頼区間を構築するために以下の公式を使用することができる。
【００６４】
【数１４】
2005502130.tif 000016
上式で、
【００６５】
【数１５】
2005502130.tif 000017
は推定量であり、
【００６６】
【数１６】
2005502130.tif 000018
は標準正規分布の百分位数であり、Ｎは全母集団の大きさであり、ｎは標本の大きさである。
【００６７】
確率αが与えられた場合、百分位数
【００６８】
【数１７】
2005502130.tif 000019
は、単位正規分布確率変数（Ｎ（０，１）と略記する）が確率
【００６９】
【数１８】
2005502130.tif 000020
で超過する値である。ゆえに、
【００７０】
【数１９】
2005502130.tif 000021
上式で、（Ｎ（０，１）分布確率変数としての）Ｘの密度ｄは、
【００７１】
【数２０】
2005502130.tif 000022
【００７２】
このことは、規則についてこのような区間を計算する場合、真の値がこの区間によって覆われる確率が１−αであることを確信できることを意味する。この公式は、この区間の長さを標本の大きさで制御できることを示している。これが長いと、信頼区間の最大長が与えられたとき、標本の大きさを計算するのに使用することができる信頼区間が短くなる。
【００７３】
問題は、標本を抽出する前に値
【００７４】
【数２１】
2005502130.tif 000023
が未知であるので、上記の公式を直接使用できないことである。したがって、和の第２項を置き換えた以下の公式を考慮する必要がある（この差は、第１の公式では
【００７５】
【数２２】
2005502130.tif 000024
の分散についての推定量を考慮し、第２の公式では
【００７６】
【数２３】
2005502130.tif 000025
の真の分散を考慮する際の差である。
【００７７】
【数２４】
2005502130.tif 000026
【００７８】
信頼区間の長さを定義するのに２つの可能性がある。一方は、相対誤差を与えることであり、他方は、真の値からの絶対誤差を与えることである。以下で両者の可能性を説明する。
【００７９】
ユーザは、最大近似誤差は真の値からの因子δ、すなわち相対誤差となるべきであると述べることになる。それにより、標本の大きさを計算するために以下の周知の公式を使用することができる。
【００８０】
【数２５】
2005502130.tif 000027
【００８１】
この公式の問題は、真の値を知る必要があることである。この値が所与のしきい値Ｍｉｎｓｕｐを超えること、および関数がｐの減少関数であることがわかるので、以下の公式を用いて最小の標本の大きさに関する境界を求めることができる。
【００８２】
【数２６】
2005502130.tif 000028
【００８３】
以下の例で、この公式の使用法を実演する。４，０００，０００レコードのデータベースが与えられたとする。指定のＭｉｎｓｕｐ値は０．０１であり、規則Ｒについての推定量は９０％の確率で真の値から１％以内である。その場合、１，４１５，２０４要素の大きさの標本を抽出することが必要である。
【００８４】
ザキは、相対誤差が真の値ｐから因子δ未満｛超｝であることを意味する、ｐから（１−δ）｛（１＋δ）｝未満｛超｝の大きさｎの標本から導出された推定値
【００８５】
【数２７】
2005502130.tif 000029
を推定するために以下の公式を使用することを提案した。
【００８６】
【数２８】
2005502130.tif 000030
【００８７】
上式より、ザキは、右辺を所与の誤差確率αと比較することによって必要な標本の大きさを導出した。
【００８８】
それにより、ザキは以下を得た。
ｎ＝−２ｌｎ（α）／ｐδ２（下界）
ｎ＝−３ｌｎ（α）／ｐδ２（上界）
【００８９】
上式では、ザキは、本発明者等が上記で考慮した、閉信頼区間を考慮していない。ザキは、本発明者等が後で扱う開区間についての確率を述べたに過ぎない。この点で、本発明者等の手法は、より少ない標本を取ることによって正確さがより高くなると言うことができる。本発明者等の手法がザキの手法よりも優れていることを示すために、標本の大きさの計算を再び考慮する。本発明者等は、標本の大きさについての近似公式（式１の近似を表す）を与えることができる。
【００９０】
【数２９】
2005502130.tif 000031
【００９１】
これを、ザキの下界公式（ザキによれば、それが最小の標本の大きさを与える）と比較する。
【００９２】
どちらの公式も同じ分母を有するので、
【００９３】
【数３０】
2005502130.tif 000032
であることを示せば十分である。
【００９４】
実際には、通常はαについて値０．１、０．０５、および０．０１が選ばれる。以下の表に、そのαの値に対する値−２ｌｎ（α）および
【００９５】
【数３１】
2005502130.tif 000033
を示す。
【００９６】
【表１】
2005502130.tif 000034
【００９７】
したがって、上記で述べた値について−２ｌｎ（α）は常に
【００９８】
【数３２】
2005502130.tif 000035
よりも大きく、このことから、上記で与えた不等式はこれらの値について成り立つと結論付けることができる。
【００９９】
標本の大きさを計算するその他の可能性は、推定量と真の値の間の絶対誤差ｄを指定することに関係する。絶対誤差尺度ｄに基づいて、以下の公式を導くことができる。
【０１００】
【数３３】
2005502130.tif 000036
【０１０１】
やはりこの公式は、真のパラメータｐについての知識が必要である。しかし、解析により、上記の公式はｐ＝０．５のときに最大値を有することが示される。したがって、標本の大きさを計算する１つの可能性は、ｐ＝０．５を代入することであり、標本の大きさ
【０１０２】
【数３４】
2005502130.tif 000037
を得る。
【０１０３】
以下の例でこの計算を例示する。母集団の大きさが７，０００，０００、信頼水準が９９％、および絶対誤差が０．０１とすると、標本の大きさ１６，５５１を得る。この大きさは、現況技術に勝る著しい改善である。
【０１０４】
トイボネン等は、絶対誤差ｄおよび誤差確率αが与えられたとして、以下の標本の大きさを取ることを提案している。
【０１０５】
【数３５】
2005502130.tif 000038
【０１０６】
上記のように、本発明者等の手法により、より小さい標本の大きさが得られることを示すことができる。再び、近似公式を使用する。
【０１０７】
【数３６】
2005502130.tif 000039
【０１０８】
したがって、
【０１０９】
【数３７】
2005502130.tif 000040
であることを示せば十分である。
【０１１０】
０≦ｐ≦１の場合にｐ（１−ｐ）≦０．２５であることに留意すると、
【０１１１】
【数３８】
2005502130.tif 000041
であることを示せば十分である。
【０１１２】
上記と同様に、この不等式が少なくともαの一般的な値について成り立つことを示す。
【０１１３】
【表２】
2005502130.tif 000042
【０１１４】
これにより、本発明者等の手法がトイボネン等よりも標本の大きさが小さくなることが示される。
【０１１５】
次に、必要な標本の大きさを計算するのに適用することができる別の結果について述べる。上記の信頼区間を考慮する場合、生じ得る２つの種類の誤差が存在する。一方は、真のサポート値が計算した上界よりも大きいものであり、他方は真のサポート値が下界よりも小さいものである。実際の環境では、一方の側だけに有界である真の値についての信頼区間だけが必要である状況が存在する（ザキ等と比較）。
【０１１６】
わずか確率αだけで真の値が超過する境界を得ることだけに関心がある場合、信頼区間
【０１１７】
【数３９】
2005502130.tif 000043
を使用することができる。
【０１１８】
これは、規則の真のサポート値が上界よりも大きくならないことを確信できることを意味する。これは、Ｍｉｎｓｕｐしきい値よりも大きいサポート値を有する規則が標本中にこの特性を有さない誤差を制御する場合に重要となる可能性がある。例えば、Ｍｉｎｓｕｐ値が与えられ、標本中の規則のサポート値が、Ｍｉｎｓｕｐ未満の上界を有する上述の信頼区間を生成すると仮定する。すると、この規則がＭｉｎｓｕｐよりも大きい母集団上の真のサポート値を得る確率は、α未満である。
【０１１９】
関心を持つことのできるその他のケースでは、下界だけを有する以下の信頼区間が使用される。
【０１２０】
【数４０】
2005502130.tif 000044
【０１２１】
この信頼区間は、真のサポート値が下界未満である誤差が誤差確率α未満であることにのみ関心がある場合に使用することができる。これは、規則がＭｉｎｓｕｐしきい値よりも大きいサポート値を有し、真の値がこのしきい値未満である誤差を制御するときに当てはまる。例えば、標本中で、規則が、対応する信頼区間の下界がＭｉｎｓｕｐしきい値よりも大きいようなサポート値を有する場合、高々αの誤差確率で、真の値がこの境界よりも小さくなる。
【０１２２】
両者の公式から、先に行ったのと同様に標本の大きさを導出することができる。公式中で変化したのは、
【０１２３】
【数４１】
2005502130.tif 000045
が
【０１２４】
【数４２】
2005502130.tif 000046
で置き換えられたことだけである。
【０１２５】
したがって、片側有界（single bounded）信頼区間に対する標本の大きさは、真の値の相対誤差δが与えられたとき、
【０１２６】
【数４３】
2005502130.tif 000047
【０１２７】
上述のようにｐをＭｉｎｓｕｐで置き換えると、
【０１２８】
【数４４】
2005502130.tif 000048
【０１２９】
絶対誤差が与えられたとき、標本の大きさを計算するために以下の公式を使用することができる。
【０１３０】
【数４５】
2005502130.tif 000049
上式で、ｎに対して最大の値となるようにｐを０．５と選ぶことができ、それによって、
【０１３１】
【数４６】
2005502130.tif 000050
【０１３２】
こうした公式によって得られた標本の大きさは、対応する閉信頼区間について計算した標本の大きさよりも小さい。後者の標本の大きさがザキ等およびトイボネン等によって提案された標本の大きさよりも小さいことが示されたので、ここで標本の大きさが導出された。
【０１３３】
多変量モデル
先の節では、規則のサポートを示す、項目または１組の項目のサポートを推定するために信頼区間を使用する方法を示した。前述のように、信頼水準（１−α）の信頼区間の意味は、すべての標本の（１−α）×１００パーセントで、全母集団に対する項目Ａの相対頻度が対応する信頼区間で覆われるということである。
【０１３４】
この概念の（ｐ個の項目を同時に考慮する意味での）一般化は、信頼水準（１−α）でいわゆる信頼度楕円体を構築するものである。ｐ次元の信頼度楕円体は、真の値が一定の確率（１−α）でこの領域中に囲まれるｐ次元の領域を定義する。
【０１３５】
ｐ＝２個の項目の場合、この楕円体は楕円形である。図１に、ｐ＝２の信頼度楕円体の一例を示す。ｐ＝３個の項目の場合、信頼度楕円体の一例を図２に示す。
【０１３６】
一方、幅（それぞれ、面積または体積）は精度についての尺度である。したがって、一定の精度を必要とする場合、幅（それぞれ、面積または体積）が（所望の信頼水準についての）規定の境界を超えないように標本の大きさを選ぶことができる。
【０１３７】
各単一項目のサポートを同時に推定するためには、すべてのトランザクションを２進ベクトルに変換することが必要である。そのようなベクトルのすべての成分は項目に対応し、値１は、考慮する項目が考慮するトランザクション中に存在することを意味し、値０は、項目が存在しないことを意味する。２進ベクトルの次元は、すべての可能な単一項目の数ｐによって示されることに留意されたい。
【０１３８】
次に、
【０１３９】
【数４７】
2005502130.tif 000051
（ｉ＝１，．．．，Ｎ）によって示されるｐ次元ベクトルを有する母集団から標本を取ると仮定する。さらに、
【０１４０】
【数４８】
2005502130.tif 000052
（ｋ＝１，．．．，ｐ）
【０１４１】
【数４９】
2005502130.tif 000053
（ｋ≠ｌ＝１，．．．，ｐ）
【０１４２】
【数５０】
2005502130.tif 000054
と定義する。
【０１４３】
標本に関する対応する量を得るように、標本中のベクトルをｙｉと表し、一方、標本の共分散行列が
【０１４４】
【数５１】
2005502130.tif 000055
によって表されることを除いて、Ｙをｙで置き換え、Ｎをｎで置き換える。上式で、
【０１４５】
【数５２】
2005502130.tif 000056
は、標本に基づく共分散の対応する推定量である。
【０１４６】
この表記を用いて、単純無作為標本に関して以下の定理を証明することができる。
【０１４７】
定理１：
【０１４８】
【数５３】
2005502130.tif 000057
は
【０１４９】
【数５４】
2005502130.tif 000058
の不偏推定量である。
【０１５０】
【数５５】
2005502130.tif 000059
は
【０１５１】
【数５６】
2005502130.tif 000060
の共分散行列である。
【０１５２】
【数５７】
2005502130.tif 000061
は
【０１５３】
【数５８】
2005502130.tif 000062
の不偏推定量である。
【０１５４】
加えて、推定量
【０１５５】
【数５９】
2005502130.tif 000063
について中心極限定理を述べることができる。
【０１５６】
定理２：
単純無作為抽出の状況において以下を仮定する。
ｎｖ→∞の場合、ｎｖ→∞かつ（Ｎｖ−ｎｖ）→∞
Ｉｖ＝｛１，．．．，Ｎｖ｝として、
ｉ∈Ｉｖについて
【０１５７】
【数６０】
2005502130.tif 000064
ｉ＝１，．．．，ｎｖについて
【０１５８】
【数６１】
2005502130.tif 000065
すべてのτ＞０かつｋ＝１，．．．，ｐについて
【０１５９】
【数６２】
2005502130.tif 000066
すべてのｋ＝１，．．．，ｐについて
【０１６０】
【数６３】
2005502130.tif 000067
上式で
【０１６１】
【数６４】
2005502130.tif 000068
ｋ番目の変数と残りのｐ−１個の変数との間の重相関係数
【０１６２】
【数６５】
2005502130.tif 000069
【０１６３】
【数６６】
2005502130.tif 000070
【０１６４】
【数６７】
2005502130.tif 000071
の共分散行列
【０１６５】
すると、Ｎ（０，Ｉｄｐ）分布に対する量
【０１６６】
【数６８】
2005502130.tif 000072
の分布の集束は、以下の条件に等しいと言える。
【０１６７】
【数６９】
2005502130.tif 000073
上式で、ｐ次元Ｎ（０，Ｉｄｐ）分布確率変数Ｙは、密度関数ｆを得る。
【０１６８】
【数７０】
2005502130.tif 000074
（ｙもｐ次元であることに留意）
【０１６９】
この定理により、ベクトル
【０１７０】
【数７１】
2005502130.tif 000075
に対して少なくとも近似の信頼度楕円体を構築する可能性が開かれる。
【０１７１】
（現況技術および前の節で与えた改良とは逆に）多変量問題に関心があるので、次に、信頼度楕円体とその構成を考慮したい。
【０１７２】
まず、観測が独立であり、同様に、期待ベクトルμ０および逆行列が存在する共分散行列Σの多変量正規分布ｐ次元ベクトルの状況を考慮する。
【０１７３】
次に、大きさｎの標本に基づいて、未知の期待ベクトルμ０について所望の信頼度楕円体を構築したいと仮定する。そのような楕円体は以下の式で与えられる。
【０１７４】
【数７２】
2005502130.tif 000076
上式で、
【０１７５】
【数７３】
2005502130.tif 000077
は、
【０１７６】
【数７４】
2005502130.tif 000078
によって与えられ、
【０１７７】
【数７５】
2005502130.tif 000079
は、確率αが与えられた場合に
【０１７８】
【数７６】
2005502130.tif 000080
となるような値である。ただしＹは、自由度ｐのχ２分布、すなわち以下の密度関数を有する。
【０１７９】
【数７７】
2005502130.tif 000081
上式で、Γはガンマ関数を表す。
【０１８０】
【数７８】
2005502130.tif 000082
【０１８１】
したがって、
【０１８２】
【数７９】
2005502130.tif 000083
は、自由度ｐのχ２分布の百分位数である。
【０１８３】
これは、データが多変数正規分布である場合に、量
【０１８４】
【数８０】
2005502130.tif 000084
が自由度ｐのχ２分布であるためである。
【０１８５】
共分散行列Σが未知である場合、この行列Σをデータから推定しなければならない。Σについての可能な推定量は以下の式で与えられる。
【０１８６】
【数８１】
2005502130.tif 000085
【０１８７】
対応する信頼度楕円体は以下の式で与えられる。
【０１８８】
【数８２】
2005502130.tif 000086
上式で、Ｆ１−α：ｐ，ｎ−ｐは、確率αが与えられた場合に
Ｐ（Ｙ≧Ｆ１−α：ｐ，ｎ−ｐ）＝α
となるような値である。ただしＹは、自由度ｍ１（＝ｐ）およびｍ２（＝ｎ−ｐ）のＦ分布、すなわち以下の密度分布を有する。
【０１８９】
【数８３】
2005502130.tif 000087
上式で、Γはガンマ関数を表す。
【０１９０】
データが多変量正規分布であるという条件が満たされず、その代わりに期待ベクトルの推定量に対して中心極限定理が成り立つ場合、上記で与えた信頼度楕円体は、近似的に有効であるに過ぎない。このような近似に基づいて、以下の置換を導入することができる。
期待ベクトルμ０をベクトル
【０１９１】
【数８４】
2005502130.tif 000088
で置き換える。
期待ベクトルμ０についての推定量
【０１９２】
【数８５】
2005502130.tif 000089
を推定量
【０１９３】
【数８６】
2005502130.tif 000090
で置き換える。
共分散行列Σの推定量Ｓを共分散行列ΣＹの推定量ｓで置き換える。
【０１９４】
中心極限定理が成り立つと仮定した場合、与えられた信頼度楕円体は提示した楕円体のままとなる。したがって、楕円体
【０１９５】
【数８７】
2005502130.tif 000091
について楕円体
【０１９６】
【数８８】
2005502130.tif 000092
を得、Ｋｓについて、
【０１９７】
【数８９】
2005502130.tif 000093
を得る。
【０１９８】
ｎ→∞の場合
【０１９９】
【数９０】
2005502130.tif 000094
ｐ≧１の場合
【０２００】
【数９１】
2005502130.tif 000095
となることに留意されたい。これにより、以下の近似信頼度楕円体が得られる。
【０２０１】
【数９２】
2005502130.tif 000096
【０２０２】
必要な標本の大きさを求めるために、所望の信頼水準と、信頼度楕円体の所望の最大体積を固定する。ｐ次元楕円体の体積が以下の式で与えられることに留意されたい。
【０２０３】
【数９３】
2005502130.tif 000097
上式で、ｈｋ  ｋ＝１，．．．，ｐは、楕円体の半軸（semiaxe）を表し、ｃｏｎｓｔ（ｐ）は、次元ｐに依存する定数である。
【０２０４】
最大許容信頼度体積Ｖ＊を定義する場合、以下のようになる。
【０２０５】
【数９４】
2005502130.tif 000098
【０２０６】
この式から、必要なｎを標本の大きさとして得る。
【０２０７】
【数９５】
2005502130.tif 000099
【０２０８】
必要な標本の大きさに関するこの式に関係するのは次の２つの問題である。
ａ．ｃｏｎｓｔ（ｐ）が次元ｐに依存する
ｂ．共分散行列の演繹的推定が必要である
【０２０９】
この問題を解決するために、半軸ｄｋ，ｋ＝１，．．．，ｐを有する信頼度楕円体を側部の長さが２ｄｋ，ｋ＝１，．．．，ｐのブリック（brick）で囲むことを提案することができる。
【０２１０】
したがって、体積に関して、ブリックによって囲まれる最大の楕円体の体積は、
【０２１１】
【数９６】
2005502130.tif 000100
【０２１２】
この公式から、以下の必要な標本の大きさｎを導くことが可能である。
【０２１３】
【数９７】
2005502130.tif 000101
上式で、
【０２１４】
【数９８】
2005502130.tif 000102
は共分散行列ｓの第ｋ対角成分である。
【０２１５】
関係式
【０２１６】
【数９９】
2005502130.tif 000103
によって量εｋを定義した場合、必要な標本の大きさは、相対精度
【０２１７】
【数１００】
2005502130.tif 000104
によって与えられる。これは、半軸の長さが標準偏差ｓｙ：ｋの分数であることを意味する。
【０２１８】
したがって、必要な標本の大きさをεｋによって表すことができる。
【０２１９】
【数１０１】
2005502130.tif 000105
【０２２０】
このような必要な標本の大きさｎ*を用いると、対応する信頼度楕円体が、側部の長さ２ｄｋのブリックによって囲まれることになる。２ｄｋ＝εｋｓｙ：ｋである。
【０２２１】
すべてのεｋを選ぶことは、所望の相対精度εを選ぶことと同じであり、必要な標本の大きさを得る。
【０２２２】
【数１０２】
2005502130.tif 000106
上式は、特にｐが非常に大きい場合に、専門家向けの公式として使用することができる。
【０２２３】
最後に、以下の問題を扱うことにする。全母集団から標本を取るために、サポートについての推定を、ユーザが選んだ所望の最小のサポートと比較することしかできない。したがって、ランダムな変動のために、単に偶然に所与の最小のサポート未満である推定量を取得する可能性があるという問題に直面する。これは、この状況が考慮する項目または変数にどれほど著しく関係するかという統計的尺度に関心を持つべきであるということを意味する。統計的観点から、これにより、同時信頼区間の理論が得られ、それを次に扱う。
【０２２４】
これらの区間は、構築した信頼度楕円体から以下のように受け取ることができる。
【０２２５】
任意の
【０２２６】
【数１０３】
2005502130.tif 000107
、および正の有限ｐ×ｐ行列と仮定するＡについて、以下を得る。
【０２２７】
【数１０４】
2005502130.tif 000108
この式に基づいて、楕円体Ｋについて以下を得る。
【０２２８】
【数１０５】
2005502130.tif 000109
【０２２９】
したがって、ｖが第ｋ単位ベクトル（ｋ＝１，．．．，ｐ）である場合、区間の積として与えられるＫをｐ次元ブリックに直接埋め込むことができる。
【０２３０】
【数１０６】
2005502130.tif 000110
【０２３１】
これらの区間のすべては、同時信頼区間として表される。成分状に、
【０２３２】
【数１０７】
2005502130.tif 000111
についての区間を得る。
【０２３３】
【数１０８】
2005502130.tif 000112
【０２３４】
アソシエーション・ルールの標本抽出のための処理フロー
図３に、前の章で大要を述べた多変量の場合のアソシエーション・ルールの標本抽出のための処理フローを示す。この処理フローは、どんな別の問題も伴わずに単変量モデルにもそれに応じて適用することができる。
【０２３５】
ステップ３０１では、アソシエーション・ルールを求めるデータ・マイニングを完全な多数のトランザクション・レコードに基づいて実施すべきか（経路３０２を選択）、それとも標本に基づいて実施すべきか（経路３０３を選択）について判定を行う。経路３０２を選択した場合、アソシエーションのマイニングの方法をステップ３０４内で適用し、その後に続いて、計算したアソシエーション・ルールをステップ３０５で視覚化する。
【０２３６】
経路３０３を取ることにより、標本に基づいてアソシエーション・ルールを計算すべき場合、まず、ステップ３０６内で標本の大きさを求めなければならない。一手法は、標本の大きさを直接指定するものである。別の手法は、標本の大きさを計算するステップである。多変量手法では、標本の大きさは、以下に基づいて計算される。
ａ．多数のトランザクションをより完全に特徴付けるパラメータとしての、多数のトランザクション内に出現する異なる項目の数ｐ。
ｂ．近似の品質についてのさらなる精度要件。例えば以下を含む。
ｂ１．標本に基づく推定に対する信頼度（１−α）。
ｂ２．式１０による、個々の項目についての相対精度要件εｋ、またはすべての項目についての共通精度要件ε。一部の項目を他の項目よりも高い精度で推定する必要がある場合、個々の項目についての相対精度要件を指定する手法を選択しなければならない。
【０２３７】
こうした仕様に基づいて、近似公式１１または１２に従って、推定の標本の大きさをステップ３０７で計算する。この推定の標本の大きさを標本の大きさとして直接使用することができ、または方向付けとしてのみ使用することができる。後者の場合、少なくとも推定の標本の大きさ程度に最終標本の大きさを選ばなければならない。
【０２３８】
多数のレコードおよび計算した標本の大きさに基づいて、ステップ３０８で、最終標本を無作為抽出によって抽出する。
【０２３９】
この標本を入力として使用して、アソシエーションのマイニングのための現況技術の方法をステップ３０４で適用して推定アソシエーション・ルールを求めることができ、それに続いて、ステップ３０５で推定アソシエーション・ルールを視覚化することができる。
【０２４０】
ステップ３０６が、必要な最小のサポート値の指定も含む場合、ステップ３０５では、考慮するアソシエーション・ルールが関心あるものか否かについての判定も可能である。このために、式１３で計算した同時信頼区間を利用することができる。以下の判定処理を適用する。
１．式１３による信頼区間が、完全にこの最小のサポート値の左側にある（すなわち、この区間の上界が最小のサポート値よりも小さい）場合、考慮する項目は関心あるものではない。そのサポートの推定量が最小のサポート未満であるからである。
２．考慮する項目についての式１３による信頼区間が最小のサポート値を囲む場合、または完全に右側にある場合、項目は関心あるものである。そのサポートの推定量が最小のサポートより大きいからである（項目のサポート値が事前定義した最小のサポート値以上である場合に項目を関心あるものと定義することを想起されたい）。
【０２４１】
こうした信頼区間の構成により、共通の信頼度ですべての関心ある規則を取得することを確実にすることができる。
【０２４２】
応用例
現況技術によれば、多数のトランザクション・レコードを構成するデータのサイズが巨大であること、およびアソシエーション・ルールを計算するための処理時間が極めて長いことのために、アソシエーションを計算するコンピュータ・システムが多数のトランザクション・レコードを格納するコンピュータ・システムと同一であることが必要であった。本発明はデータ量を低減することができるので、実際のマイニング技術がトランザクション・レコードのうちの非常に小さい（完全な多数のトランザクション・レコードと比較して極めて小さい）標本だけに適用され、インターネットなどのある通信ネットワークで接続されたクライアント・コンピュータおよびサーバ・コンピュータを含む新しい分散処理モデルが提案される。
【０２４３】
図４に、アソシエーション・ルールのマイニングのための分散処理モデルを示す。
【０２４４】
図４内には、アソシエーション・ルールの決定を制御するクライアント・コンピュータ４０１が示されている。クライアントは多数のＮトランザクション・レコード４０２を格納する。クライアント・コンピュータは、ステップ４０３で、多数のＮトランザクションから標本の大きさｎの標本４０４を抽出する。標本の大きさは、先に開示した手法のいずれによっても決定することができる。
【０２４５】
通信ネットワーク４０５を使用して、アソシエーション・ルールのマイニングに関する特定のサービスを提供するサーバ・コンピュータ４０６に標本を送る。ステップ４０７内で、提供された標本に基づいてアソシエーション・ルールを計算し、通信ネットワークを介してクライアント・コンピュータに返す。この場合、解析のための時間が短い（小さい標本だけに基づく）ので、得られる近似規則を非常に迅速に送り返すことが可能である。
【０２４６】
最後に、ステップ４０８内で、クライアント・システム上の別の活動のためにこうした規則を解析することができる。
【０２４７】
サーバ・システム上のアソシエーション・ルールのマイニングのために提供するサービスの範囲に応じて、クライアント・コンピュータ自体が標本の大きさを決定し、あるいはサーバ・コンピュータが標本の大きさを決定する任を担うという２つの異なる実施形態が可能である。いずれにしても、本明細書内で開示した、標本の大きさを決定するための技術が利用される。
【図面の簡単な説明】
【０２４８】
【図１】ｐ＝２の信頼度楕円体の一例である。
【図２】ｐ＝３の信頼度楕円体の一例である。
【図３】多変量の場合のアソシエーション・ルールの標本抽出についての処理フローを示す図である。この処理フローは、何ら別の問題を伴わずに単変量モデルにも適用することができる。
【図４】アソシエーション・ルールのマイニングのための分散処理モデルを示す図である。
【図１】
2005502130.tif 000122
【図２】
2005502130.tif 000123
【図３】
2005502130.tif 000124
【図４】
2005502130.tif 000125
【国際公開パンフレット】
2005502130.tif 000126
2005502130.tif 000127
2005502130.tif 000128
2005502130.tif 000129
2005502130.tif 000130
2005502130.tif 000131
2005502130.tif 000132
2005502130.tif 000133
2005502130.tif 000134
2005502130.tif 000135
2005502130.tif 000136
2005502130.tif 000137
2005502130.tif 000138
2005502130.tif 000139
2005502130.tif 000140
2005502130.tif 000141
2005502130.tif 000142
2005502130.tif 000143
2005502130.tif 000144
2005502130.tif 000145
2005502130.tif 000146
2005502130.tif 000147
2005502130.tif 000148
2005502130.tif 000149
2005502130.tif 000150
2005502130.tif 000151
2005502130.tif 000152
2005502130.tif 000153
2005502130.tif 000154
2005502130.tif 000155
2005502130.tif 000156
2005502130.tif 000157
2005502130.tif 000158
2005502130.tif 000159
2005502130.tif 000160
2005502130.tif 000161
2005502130.tif 000162
2005502130.tif 000163
2005502130.tif 000164
2005502130.tif 000165
2005502130.tif 000166
2005502130.tif 000167
2005502130.tif 000168
2005502130.tif 000169
2005502130.tif 000170
2005502130.tif 000171
2005502130.tif 000172
2005502130.tif 000173
2005502130.tif 000174
【国際公開パンフレット（コレクトバージョン）】
2005502130.tif 000175
2005502130.tif 000176
【手続補正書】
【提出日】平成16年1月27日(2004.1.27)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
式１１、１２からわかるであろうが、本発明に従って決定される標本の大きさは、元のトランザクションの数よりもずっと少なく、さらにはＮと無関係である。したがって、本教示により、アソシエーション・ルールのデータ・マイニングに関して非常に著しい性能の改善が得られる。


【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
図面および明細書において、本発明の好ましい実施形態を説明する。特定の術語を使用するが、そのようにして与える説明は、総称的に、かつ説明として術語を使用しているだけであり、限定のためではない。


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０２４８
【補正方法】変更
【補正の内容】
【０２４８】
【図１】ｐ＝２の信頼度楕円体の一例である。
【図２】ｐ＝３の信頼度楕円体の一例である。
【図３】多変量の場合のアソシエーション・ルールの標本抽出についての処理フローを示す図である。
【図４】アソシエーション・ルールのマイニングのための分散処理モデルを示す図である。




【国際調査報告】
2005502130.tif 000177
2005502130.tif 000178
2005502130.tif 000179