JPH09134363A - データベース検索方法及び装置 - Google Patents
データベース検索方法及び装置Info
- Publication number
- JPH09134363A JPH09134363A JP7285416A JP28541695A JPH09134363A JP H09134363 A JPH09134363 A JP H09134363A JP 7285416 A JP7285416 A JP 7285416A JP 28541695 A JP28541695 A JP 28541695A JP H09134363 A JPH09134363 A JP H09134363A
- Authority
- JP
- Japan
- Prior art keywords
- data
- attribute
- section
- program code
- computer
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2458—Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
- G06F16/2465—Query processing support for facilitating data mining operations in structured databases
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2216/00—Indexing scheme relating to additional aspects of information retrieval not explicitly covered by G06F16/00 and subgroups
- G06F2216/03—Data mining
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
- Y10S707/99936—Pattern matching access
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Probability & Statistics with Applications (AREA)
- Mathematical Physics (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Fuzzy Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 数値属性と０−１属性の結合ルールを導き出
す。 【解決の手段】（１）数値属性を複数の区間（バケッ
ト）に分け、数値属性の値に応じて、各データを１つの
バケットに入れる。そして、各バケット内のデータ数
と、０−１属性が１であるデータの数をカウントする。
（２）検出すべき区間の開始区間を検出する。これは、 【数１】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）の条件を
満たすようなｓを見つけ出すことである。（３）先の開
始区間に対応する終了区間を検出する。これは、予め決
められた確信度α以上となる最大の区間を見つけ出すこ
とである。（４）以上のように見つけ出された開始区間
と終了区間の組のうち、最も顧客が含まれる区間の組が
答である。この後に、回答となる区間に含まれるデータ
のうち、必要なデータ属性を取り出す。
す。 【解決の手段】（１）数値属性を複数の区間（バケッ
ト）に分け、数値属性の値に応じて、各データを１つの
バケットに入れる。そして、各バケット内のデータ数
と、０−１属性が１であるデータの数をカウントする。
（２）検出すべき区間の開始区間を検出する。これは、 【数１】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）の条件を
満たすようなｓを見つけ出すことである。（３）先の開
始区間に対応する終了区間を検出する。これは、予め決
められた確信度α以上となる最大の区間を見つけ出すこ
とである。（４）以上のように見つけ出された開始区間
と終了区間の組のうち、最も顧客が含まれる区間の組が
答である。この後に、回答となる区間に含まれるデータ
のうち、必要なデータ属性を取り出す。
Description
【０００１】
【発明の属する技術分野】本発明は、データベースにお
けるデータ相関の解析に関し、より詳しくは数値属性と
０−１属性を有するデータ間の相関を見い出す手法に関
する。
けるデータ相関の解析に関し、より詳しくは数値属性と
０−１属性を有するデータ間の相関を見い出す手法に関
する。
【０００２】
【従来の技術】データベースのデータの相関を解析し、
意味ある属性間の結合ルール（association rule）を発
見することを、データマイニングと呼ぶ。
意味ある属性間の結合ルール（association rule）を発
見することを、データマイニングと呼ぶ。
【０００３】「顧客が商品Ａを購入した」といった事実
や「顧客がクレジットカードを有している」といった事
実は、商品Ａを購入したか又はしないか、クレジットカ
ードを有しているか又はいないかといった、０又は１で
示される、０−１属性を有するデータとみなすことがで
きる。このような０−１属性間の相関からルールを見い
出すことは従来から行われてきた。例えば「商品Ａを購
入した顧客の中で商品Ｂを購入する割合はｒである」と
いう情報を結合ルールとして見い出すことを説明した論
文に、R.Agrawal, T.Imielinski, and A.Swami, "Minin
g associationrules between sets of items in large
databases" In proceedings of the ACM SIGMOD Confer
ence on Management of data, May 1993. や、R.Agrawa
l and R.Srikant, "Fast algorithms for mining assoc
iation rules" In Proceedingsof the 20th VLDB Confe
rence, 1994. 等がある。
や「顧客がクレジットカードを有している」といった事
実は、商品Ａを購入したか又はしないか、クレジットカ
ードを有しているか又はいないかといった、０又は１で
示される、０−１属性を有するデータとみなすことがで
きる。このような０−１属性間の相関からルールを見い
出すことは従来から行われてきた。例えば「商品Ａを購
入した顧客の中で商品Ｂを購入する割合はｒである」と
いう情報を結合ルールとして見い出すことを説明した論
文に、R.Agrawal, T.Imielinski, and A.Swami, "Minin
g associationrules between sets of items in large
databases" In proceedings of the ACM SIGMOD Confer
ence on Management of data, May 1993. や、R.Agrawa
l and R.Srikant, "Fast algorithms for mining assoc
iation rules" In Proceedingsof the 20th VLDB Confe
rence, 1994. 等がある。
【０００４】また、従来の関係データベースにおいて、
その問い合わせ言語を用い、数値属性Ａとその区間Ｉを
与えて「Ａの値がＩに入るデータのＸ％は０−１属性Ｂ
を有する」といった問題を解くことは容易ではあった
が、区間Ｉを入力しなければならなかった。この区間Ｉ
を出力するような機能は現在のデータベース・システム
においてはない。これは、数値属性とその区間の組と０
−１属性間の結合ルールは区間の取り方に自由度が大き
く、仮にある評価関数を定義し最良の区間を一意に定め
ても、その区間を高速に取り出すアルゴリズムが難しい
からである。
その問い合わせ言語を用い、数値属性Ａとその区間Ｉを
与えて「Ａの値がＩに入るデータのＸ％は０−１属性Ｂ
を有する」といった問題を解くことは容易ではあった
が、区間Ｉを入力しなければならなかった。この区間Ｉ
を出力するような機能は現在のデータベース・システム
においてはない。これは、数値属性とその区間の組と０
−１属性間の結合ルールは区間の取り方に自由度が大き
く、仮にある評価関数を定義し最良の区間を一意に定め
ても、その区間を高速に取り出すアルゴリズムが難しい
からである。
【０００５】しかし、例えば銀行の顧客データのデータ
ベースを考えた時に、次のような数値属性（定期預金残
高の伸び）と０−１属性（クレジットカードを利用する
か否か）の組み合わせに関する結合ルールを満たす区間
Ｉを求められれば非常に有用である。すなわち、「定期
預金残高の伸びが区間Ｉに入る顧客の５０％がクレジッ
トカードを利用する。」といった問題である。この区間
Ｉには自由度があるが、最大の顧客を含む区間Ｉはほぼ
一意に決まる。この区間Ｉが分かれば、さまざまな営業
活動に有効な情報を得ることができようになる。
ベースを考えた時に、次のような数値属性（定期預金残
高の伸び）と０−１属性（クレジットカードを利用する
か否か）の組み合わせに関する結合ルールを満たす区間
Ｉを求められれば非常に有用である。すなわち、「定期
預金残高の伸びが区間Ｉに入る顧客の５０％がクレジッ
トカードを利用する。」といった問題である。この区間
Ｉには自由度があるが、最大の顧客を含む区間Ｉはほぼ
一意に決まる。この区間Ｉが分かれば、さまざまな営業
活動に有効な情報を得ることができようになる。
【０００６】但し、このような問題は非常に大きなデー
タ数を含むデータベースに対しても適用可能であり、そ
れを実時間で処理できなければ何等の意味もない。
タ数を含むデータベースに対しても適用可能であり、そ
れを実時間で処理できなければ何等の意味もない。
【０００７】
【発明が解決しようとする課題】よって、本発明の目的
は、数値属性と０−１属性を有するデータの相関を見い
出すことができるようにすることである。
は、数値属性と０−１属性を有するデータの相関を見い
出すことができるようにすることである。
【０００８】また、他の目的は、上述の処理を高速に行
うことも目的とする。
うことも目的とする。
【０００９】また、区間Ｉ＝［ｒ1,ｒ2］に数値属性ｚ
が入るデータの割合を、区間Ｉのサポートとし、この区
間Ｉに数値属性ｚが入るデータのうち０−１属性ａが１
であるデータの割合を確信度とすると、確信度α％以上
の条件で、サポートを最大とする区間Ｉ（双対結合ルー
ルという。）を求めることができるようにすることを目
的とする。
が入るデータの割合を、区間Ｉのサポートとし、この区
間Ｉに数値属性ｚが入るデータのうち０−１属性ａが１
であるデータの割合を確信度とすると、確信度α％以上
の条件で、サポートを最大とする区間Ｉ（双対結合ルー
ルという。）を求めることができるようにすることを目
的とする。
【００１０】
【課題を解決するための手段】本発明を大きく４つに分
けて説明すると、以下のとおりになる。 （１）数値属性を複数の区間（バケット）に分け、数値
属性の値に応じて、各データを１つのバケットに入れ
る。そして、各バケット内のデータ数と、０−１属性が
１であるデータの数をカウントする。 （２）検出すべき区間の開始区間を検出する。これは、
けて説明すると、以下のとおりになる。 （１）数値属性を複数の区間（バケット）に分け、数値
属性の値に応じて、各データを１つのバケットに入れ
る。そして、各バケット内のデータ数と、０−１属性が
１であるデータの数をカウントする。 （２）検出すべき区間の開始区間を検出する。これは、
【数４】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）の条件
を満たすようなｓを見つけ出すことである。 （３）先の開始区間に対応する終了区間を検出する。こ
れは、予め決められた確信度α以上となる最大の区間を
見つけ出すことである。 （４）以上のように見つけ出された開始区間と終了区間
の組のうち、最も顧客が含まれる区間の組が、本問題の
答えとなる。この後に、回答となる区間に含まれるデー
タのうち、必要なデータ属性を取り出す。
おいて前記０−１属性が１であるデータの割合）の条件
を満たすようなｓを見つけ出すことである。 （３）先の開始区間に対応する終了区間を検出する。こ
れは、予め決められた確信度α以上となる最大の区間を
見つけ出すことである。 （４）以上のように見つけ出された開始区間と終了区間
の組のうち、最も顧客が含まれる区間の組が、本問題の
答えとなる。この後に、回答となる区間に含まれるデー
タのうち、必要なデータ属性を取り出す。
【００１１】以上述べたことをまとめると、各々数値属
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
【数５】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、開
始インデックス検出ステップによって検出されたｓ以上
であって０−１属性が１である確率がα以上である最大
のｔを求める終了インデックス検出ステップと、最もデ
ータ数の大きい区間［ｓ，ｔ］を選択するステップと、
区間［ｓ，ｔ］に入るデータをデータベースから取り出
すステップとを含む。これにより双対結合ルールが導き
出される。
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、開
始インデックス検出ステップによって検出されたｓ以上
であって０−１属性が１である確率がα以上である最大
のｔを求める終了インデックス検出ステップと、最もデ
ータ数の大きい区間［ｓ，ｔ］を選択するステップと、
区間［ｓ，ｔ］に入るデータをデータベースから取り出
すステップとを含む。これにより双対結合ルールが導き
出される。
【００１２】先の複数の区間の各々が、実質的に同一の
データ数を含むように設定されているようにすることも
考えられる。
データ数を含むように設定されているようにすることも
考えられる。
【００１３】この実施的に同一のデータ数を含むように
し且つ高速に前記カウントするステップを行うには、Ｎ
個のデータのうちＸ個のデータをランダム・サンプリン
グするステップと、Ｘ個のデータを数値属性の値でソー
トするステップと、ソートされたデータ中のｉ・Ｘ／Ｍ
（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に該
当するデータの数値属性の値を保持するステップと、保
持された値に基づき、各区間に該当するデータの数をカ
ウントするステップとを含むようにすることも考えられ
る。
し且つ高速に前記カウントするステップを行うには、Ｎ
個のデータのうちＸ個のデータをランダム・サンプリン
グするステップと、Ｘ個のデータを数値属性の値でソー
トするステップと、ソートされたデータ中のｉ・Ｘ／Ｍ
（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に該
当するデータの数値属性の値を保持するステップと、保
持された値に基づき、各区間に該当するデータの数をカ
ウントするステップとを含むようにすることも考えられ
る。
【００１４】また、先の開始インデックス検出ステップ
が、ｗ＜０であって、ｖs-1−αｕs -1≧０であるかどう
かを判定するステップと、判定ステップが肯定的な回答
を返す場合には、ｗ＝ｖs-1−αｕs-1として、ｗ＜０で
あるかを判断するステップと、判定ステップが否定的な
回答を返す場合には、ｗ＝ｗ＋ｖs-1−αｕs-1として、
ｗ＜０であるかを判断するステップとを含むようにする
ことも考えられる。これにより、簡単に開始インデック
スが見つけ出せる。
が、ｗ＜０であって、ｖs-1−αｕs -1≧０であるかどう
かを判定するステップと、判定ステップが肯定的な回答
を返す場合には、ｗ＝ｖs-1−αｕs-1として、ｗ＜０で
あるかを判断するステップと、判定ステップが否定的な
回答を返す場合には、ｗ＝ｗ＋ｖs-1−αｕs-1として、
ｗ＜０であるかを判断するステップとを含むようにする
ことも考えられる。これにより、簡単に開始インデック
スが見つけ出せる。
【００１５】また、先の終了インデックス検出ステップ
が、最も大きい開始インデックスｓに対応する終了イン
デックスｔを検出する動作から開始されるようにするこ
とも考えられる。これにより、終了インデックスｔを見
つけ出す処理が簡潔になる。
が、最も大きい開始インデックスｓに対応する終了イン
デックスｔを検出する動作から開始されるようにするこ
とも考えられる。これにより、終了インデックスｔを見
つけ出す処理が簡潔になる。
【００１６】さらに、１の開始インデックスｓに対応す
る終了インデックスｔは、前記１の開始インデックスｓ
の１つ前に処理された開始インデックスｓ'に対応する
終了インデックスｔ'以下について処理することにより
求めることも考えられる。これにより、さらに処理が簡
単になる。
る終了インデックスｔは、前記１の開始インデックスｓ
の１つ前に処理された開始インデックスｓ'に対応する
終了インデックスｔ'以下について処理することにより
求めることも考えられる。これにより、さらに処理が簡
単になる。
【００１７】また、上述した方法を特別の装置を構成し
て実施することも、またコンピュータ・プログラムにて
実施し、そのコンピュータプログラムを記憶した媒体に
ても具現化することも通常考えられる本発明の１つの形
態である。
て実施することも、またコンピュータ・プログラムにて
実施し、そのコンピュータプログラムを記憶した媒体に
ても具現化することも通常考えられる本発明の１つの形
態である。
【００１８】
【発明の実施の形態】上述した４つのステップを順に説
明していく。
明していく。
【００１９】（１）バケット処理 バケットとは、データの数値属性の値の特定の範囲を区
分するものであり、Ｂ1，Ｂ2，Ｂ3，．．．ＢM（Ｂi＝
［ｘi,ｙi］，ｘi≦ｙi＜ｘi+1）として表すことができ
る。データの数値属性の値は、いずれかのバケットに属
する。高解像度を必要とする場合には、Ｂi＝［ｘ，
ｘ］とすることもできる。
分するものであり、Ｂ1，Ｂ2，Ｂ3，．．．ＢM（Ｂi＝
［ｘi,ｙi］，ｘi≦ｙi＜ｘi+1）として表すことができ
る。データの数値属性の値は、いずれかのバケットに属
する。高解像度を必要とする場合には、Ｂi＝［ｘ，
ｘ］とすることもできる。
【００２０】また、どのバケットにどのデータが入るか
を調べるために、全データをその数値属性の値でソート
することも考えられる。しかし、このような処理を行う
こととすると、データベースのようにデータ数が莫大で
ある場合、メインメモリ内で処理できないという問題が
あり、処理は実時間内に終了しない。よって、以下のよ
うな処理を行う。
を調べるために、全データをその数値属性の値でソート
することも考えられる。しかし、このような処理を行う
こととすると、データベースのようにデータ数が莫大で
ある場合、メインメモリ内で処理できないという問題が
あり、処理は実時間内に終了しない。よって、以下のよ
うな処理を行う。
【００２１】まず、Ｎ個のデータがあることを想定し、
そのデータをＭ個のバケットに分けることを考える。そ
して、ｉ番目のバケットはｉ＋１番目のバケットには入
らないものとする。
そのデータをＭ個のバケットに分けることを考える。そ
して、ｉ番目のバケットはｉ＋１番目のバケットには入
らないものとする。
【００２２】（ａ）全データから（Ｍ・Ｎ）0.5個のラ
ンダムサンプリングを行う（図１ステップ１１０）。Ｍ
は、例えば１０００程度で、Ｎは１０億程度である。よ
って、この（Ｍ・Ｎ）0.5は、１００万ぐらいである。
この程度の処理はメインメモリ内の処理を行うことがで
きる。 （ｂ）ランダムサンプリングしたデータをソートする
（ステップ１２０）。これには、Ｏ（（Ｍ・Ｎ）0.5・
ｌｏｇＭ・Ｎ）のオーダーで計算することができる。 （ｃ）ｉ（Ｎ／Ｍ）0.5番目の値をｐiとして記憶する
（ステップ１３０）。但し、ｐ0＝−∞、ｐM＝∞とす
る。 （ｄ）各データをバケットに分配する（ステップ１４
０）。バケットＢiにはｐi＜ｘ≦ｐi+1に該当するｘを
有するデータが属する。これを２分探索を用いれば、こ
の処理はＯ（ＮｌｏｇＭ）のオーダーで処理できる。そ
して、同時に、各バケットに入るデータ数と、０−１属
性が１であるデータの数をカウントしていく。
ンダムサンプリングを行う（図１ステップ１１０）。Ｍ
は、例えば１０００程度で、Ｎは１０億程度である。よ
って、この（Ｍ・Ｎ）0.5は、１００万ぐらいである。
この程度の処理はメインメモリ内の処理を行うことがで
きる。 （ｂ）ランダムサンプリングしたデータをソートする
（ステップ１２０）。これには、Ｏ（（Ｍ・Ｎ）0.5・
ｌｏｇＭ・Ｎ）のオーダーで計算することができる。 （ｃ）ｉ（Ｎ／Ｍ）0.5番目の値をｐiとして記憶する
（ステップ１３０）。但し、ｐ0＝−∞、ｐM＝∞とす
る。 （ｄ）各データをバケットに分配する（ステップ１４
０）。バケットＢiにはｐi＜ｘ≦ｐi+1に該当するｘを
有するデータが属する。これを２分探索を用いれば、こ
の処理はＯ（ＮｌｏｇＭ）のオーダーで処理できる。そ
して、同時に、各バケットに入るデータ数と、０−１属
性が１であるデータの数をカウントしていく。
【００２３】このようにすれば、全体としてＯ（Ｎｌｏ
ｇＭ）程度のオーダーで処理可能である。また、サンプ
リングの数が（Ｍ・Ｎ）0.5個であれば十分高い確率で
誤差をＭ／２Ｎから２Ｍ／Ｎに抑えることが可能とな
る。
ｇＭ）程度のオーダーで処理可能である。また、サンプ
リングの数が（Ｍ・Ｎ）0.5個であれば十分高い確率で
誤差をＭ／２Ｎから２Ｍ／Ｎに抑えることが可能とな
る。
【００２４】また、ステップ（ｄ）は最も時間を消費す
るような処理であるが、並列処理させることにより容易
に処理時間を短縮させることができる。すなわち、デー
タベースを各プロセッサ・エレメントのために分割し
（図２のステップ２１０）、主プロセッサ・エレメント
において先のステップ（ａ）から（ｃ）を行い（ステッ
プ２２０）、各プロセッサ・エレメントにてステップ
（ｄ）を行い（ステップ２３０）、主プロセッサ・エレ
メントが各プロセッサ・エレメントから結果を取り寄せ
て、集計する（ステップ２４０）。このようにすれば、
各プロセッサ・エレメント間のデータ通信の量は少な
く、負荷の重いステップ（ｄ）を並列に行えるので、処
理時間の短縮に効果がある。
るような処理であるが、並列処理させることにより容易
に処理時間を短縮させることができる。すなわち、デー
タベースを各プロセッサ・エレメントのために分割し
（図２のステップ２１０）、主プロセッサ・エレメント
において先のステップ（ａ）から（ｃ）を行い（ステッ
プ２２０）、各プロセッサ・エレメントにてステップ
（ｄ）を行い（ステップ２３０）、主プロセッサ・エレ
メントが各プロセッサ・エレメントから結果を取り寄せ
て、集計する（ステップ２４０）。このようにすれば、
各プロセッサ・エレメント間のデータ通信の量は少な
く、負荷の重いステップ（ｄ）を並列に行えるので、処
理時間の短縮に効果がある。
【００２５】以上のように、最初のバケットに関する処
理は終了する。
理は終了する。
【００２６】（２）開始インデックス検出処理 以上のようなバケットが用意された後に、確信度がα以
上であって、サポートが最大の連続バケット群を取り出
す処理を行う。まず、バケットは図３のようにＢ1,Ｂ2,
Ｂ3,．．．ＢMと分けられており、各バケットのデータ
数をｕi（i＝１，２，．．．Ｍ）、条件を満たすデータ
数をｖi（i＝１，２，．．．Ｍ）とする。ここでｓｕｐ
ｐｏｒｔ（ｓ，ｔ）は、ｘs≦Ａ≦ｙtのサポートであり
（Ａはデータの属性を示す）、実際には、連続するバケ
ット群の組Ｂs，Ｂs+1，Ｂs+2，．．．Ｂtのデータ数の
和をデータ全体の数Ｎで除したものであり、
上であって、サポートが最大の連続バケット群を取り出
す処理を行う。まず、バケットは図３のようにＢ1,Ｂ2,
Ｂ3,．．．ＢMと分けられており、各バケットのデータ
数をｕi（i＝１，２，．．．Ｍ）、条件を満たすデータ
数をｖi（i＝１，２，．．．Ｍ）とする。ここでｓｕｐ
ｐｏｒｔ（ｓ，ｔ）は、ｘs≦Ａ≦ｙtのサポートであり
（Ａはデータの属性を示す）、実際には、連続するバケ
ット群の組Ｂs，Ｂs+1，Ｂs+2，．．．Ｂtのデータ数の
和をデータ全体の数Ｎで除したものであり、
【数６】 で示される。
【００２７】また、ｃｏｎｆ（ｓ，ｔ）は、ｘs≦Ａ≦
ｙtであって条件Ｃを満たす確信度であって、
ｙtであって条件Ｃを満たす確信度であって、
【数７】 で示される。
【００２８】本発明の目的は、このｃｏｎｆ（ｓ，ｔ）
がα以上で、ｓｕｐｐｏｒｔ（ｓ，ｔ）が最大となる
ｓ，ｔを求めることにある。このｓ，ｔの対を最適対
（optimal pair）という。そして、すべてのｊ＜ｓとな
るｊについて、ｃｏｎｆ（ｊ，ｓ−１）＜αとなるｓ
を、エフェクティブ（effective）であるということと
する。
がα以上で、ｓｕｐｐｏｒｔ（ｓ，ｔ）が最大となる
ｓ，ｔを求めることにある。このｓ，ｔの対を最適対
（optimal pair）という。そして、すべてのｊ＜ｓとな
るｊについて、ｃｏｎｆ（ｊ，ｓ−１）＜αとなるｓ
を、エフェクティブ（effective）であるということと
する。
【００２９】ここで、ｓ≦ｔとなるｓ，ｔが最適対であ
る場合には、ｓはエフェクティブとなる。これは、ｃｏ
ｎｆ（ｊ，ｓ−１）≧αとなるようなｊが存在するとす
ると、ｃｏｎｆ（ｓ，ｔ）≧αであって、且つｃｏｎｆ
（ｊ，ｔ）≧αとなるが、これはｓ，ｔが最適対である
という前提に反する結果を生じるからである。
る場合には、ｓはエフェクティブとなる。これは、ｃｏ
ｎｆ（ｊ，ｓ−１）≧αとなるようなｊが存在するとす
ると、ｃｏｎｆ（ｓ，ｔ）≧αであって、且つｃｏｎｆ
（ｊ，ｔ）≧αとなるが、これはｓ，ｔが最適対である
という前提に反する結果を生じるからである。
【００３０】このことを用いて、全てのエフェクティブ
となるｓを見つけ出し、その後に最適対を検出するもの
とする。よって、
となるｓを見つけ出し、その後に最適対を検出するもの
とする。よって、
【数８】 となるようなｓを見つけ出すことがエフェクティブな
ｓ、すなわち、開始インデックスを見つけ出す処理とな
る。
ｓ、すなわち、開始インデックスを見つけ出す処理とな
る。
【００３１】エフェクティブなｓを見つけ出すために、
次のようなステップ（図４）により処理する。但し、ｓ
＝１はエフェクティブとしておく。まず、初期値をセッ
トするために、ｓ＝２，ｗ＝０とする（ステップ１１
０）。そして、ｓを２からＭまで変化させるために、ｓ
＝Ｍ＋１であるかを判断する（ステップ１２０）。も
し、ｓがＭ以下であれば、ｗ＜０であって且つｖs-1−
αｕs-1≧０であるかどうかを判断する（ステップ１３
０）。
次のようなステップ（図４）により処理する。但し、ｓ
＝１はエフェクティブとしておく。まず、初期値をセッ
トするために、ｓ＝２，ｗ＝０とする（ステップ１１
０）。そして、ｓを２からＭまで変化させるために、ｓ
＝Ｍ＋１であるかを判断する（ステップ１２０）。も
し、ｓがＭ以下であれば、ｗ＜０であって且つｖs-1−
αｕs-1≧０であるかどうかを判断する（ステップ１３
０）。
【００３２】これは、すべてのｊ＜ｓであるｊについて
数８を満たさなければならないので、ｖs-1−αｕs-1≧
０であれば、数７は満たさなくなる。よって、数８のカ
ッコ内を最大とするｖs-1−αｕs-1をｗとする（ステッ
プ１４０）。一方、ステップ１３０の条件を満たさない
場合には、ｗ＝ｗ＋ｖs-1−αｕs-1とする（ステップ１
５０）。このようなｗについて、ｗ＜０が成り立つのか
を検査する（ステップ１６０）。
数８を満たさなければならないので、ｖs-1−αｕs-1≧
０であれば、数７は満たさなくなる。よって、数８のカ
ッコ内を最大とするｖs-1−αｕs-1をｗとする（ステッ
プ１４０）。一方、ステップ１３０の条件を満たさない
場合には、ｗ＝ｗ＋ｖs-1−αｕs-1とする（ステップ１
５０）。このようなｗについて、ｗ＜０が成り立つのか
を検査する（ステップ１６０）。
【００３３】もしｗ＜０であれば、そのｓはエフェクテ
ィブである（ステップ１７０）。ステップ１６０でｗ≧
０であると判断された場合及びステップ１７０の後に、
ｓを１インクリメントする（ステップ１８０）。そし
て、ステップ１２０に戻る。
ィブである（ステップ１７０）。ステップ１６０でｗ≧
０であると判断された場合及びステップ１７０の後に、
ｓを１インクリメントする（ステップ１８０）。そし
て、ステップ１２０に戻る。
【００３４】このような処理にてエフェクティブなｓが
見つかる。これは、開始インデックスである。なお、こ
の処理は、Ｏ（Ｍ）のオーダーで処理可能である。
見つかる。これは、開始インデックスである。なお、こ
の処理は、Ｏ（Ｍ）のオーダーで処理可能である。
【００３５】簡単な具体例を示す。
【表１】
【００３６】ｓが１から１０までの各ｕsとｖsを示して
おり、ｗを計算するためのαは０．５とした。そうする
と、先に述べたように、ｓ＝１は０で、且つエフェクテ
ィブであるので、マーク（矢印）が示される。ｓ＝２で
はｗ＝０（ｗ＝０＋（５−１０×０．５））となるの
で、マークは付かない。ｓ＝３では、ｗ＝−２（＝０＋
（３−１０×０．５））となり、マークされる。ｓ＝４
では、ｖs-1−αｕs-1＝−３であるから、ｗ＝−５（＝
−２＋（−３））となり、マークされる。同様にしてｓ
＝５ではｗ＝−９でマークされる。ｓ＝６となると、ｖ
s-1−αｕs-1＝２となるので、ｗ＝２となり、マークさ
れない。ｓ＝７では、ｗ＝−１（＝２＋（−３））とな
り、マークされる。ｓ＝８になると、ｖs-1−αｕs-1＝
３となり、ｗ＝３でマークされない。同様に、ｓ＝９，
１０もマークされない。よって、本例においては、エフ
ェクティブなｓは、１，３，４，５，７となる。
おり、ｗを計算するためのαは０．５とした。そうする
と、先に述べたように、ｓ＝１は０で、且つエフェクテ
ィブであるので、マーク（矢印）が示される。ｓ＝２で
はｗ＝０（ｗ＝０＋（５−１０×０．５））となるの
で、マークは付かない。ｓ＝３では、ｗ＝−２（＝０＋
（３−１０×０．５））となり、マークされる。ｓ＝４
では、ｖs-1−αｕs-1＝−３であるから、ｗ＝−５（＝
−２＋（−３））となり、マークされる。同様にしてｓ
＝５ではｗ＝−９でマークされる。ｓ＝６となると、ｖ
s-1−αｕs-1＝２となるので、ｗ＝２となり、マークさ
れない。ｓ＝７では、ｗ＝−１（＝２＋（−３））とな
り、マークされる。ｓ＝８になると、ｖs-1−αｕs-1＝
３となり、ｗ＝３でマークされない。同様に、ｓ＝９，
１０もマークされない。よって、本例においては、エフ
ェクティブなｓは、１，３，４，５，７となる。
【００３７】（３）終了インデックス検出処理 まず用語の定義を行うと、ｓ≦ｔであってｃｏｎｆ
（ｓ，ｔ）≧αである最も大きいｔをｔｏｐ（ｓ）と記
すこととする。ここでは、各ｓに対するｔｏｐ（ｓ）を
求めることが目的である。
（ｓ，ｔ）≧αである最も大きいｔをｔｏｐ（ｓ）と記
すこととする。ここでは、各ｓに対するｔｏｐ（ｓ）を
求めることが目的である。
【００３８】そうすると、エフェクティブｓ及びｓ'で
ｓ≦ｓ'とすると、ｔｏｐ（ｓ）≦ｔｏｐ（ｓ'）となる
ことがわかる。これは、ｃｏｎｆ（ｓ，ｓ'−１）＜α
であり、ｃｏｎｆ（ｓ，ｔｏｐ（ｓ））≧α、ｃｏｎｆ
（ｓ'，ｔｏｐ（ｓ））≧αとなるためである。
ｓ≦ｓ'とすると、ｔｏｐ（ｓ）≦ｔｏｐ（ｓ'）となる
ことがわかる。これは、ｃｏｎｆ（ｓ，ｓ'−１）＜α
であり、ｃｏｎｆ（ｓ，ｔｏｐ（ｓ））≧α、ｃｏｎｆ
（ｓ'，ｔｏｐ（ｓ））≧αとなるためである。
【００３９】この性質を用いると、エフェクティブなｓ
は大きい順に処理し、１つ求められたｔｏｐ（ｓ）より
も小さい値がｓ≧ｓ'となるｓ'に対するｔｏｐ（ｓ'）
となるので、より処理が少なくなり、計算速度が速くな
る。具体的には以下のような処理にてｔｏｐ（ｓ）が求
められる（図５）。なお、ｓ（ｊ）は、エフェクティブ
なｓを小さい順に並べた数列｛ｓ（１），ｓ
（２），．．ｓ（ｑ）｝であって、ｊ番目のｓを示すも
のとする。また、このエフェクティブなｓはｑ個あり、
バケットは先に述べたようにＭ個ある。
は大きい順に処理し、１つ求められたｔｏｐ（ｓ）より
も小さい値がｓ≧ｓ'となるｓ'に対するｔｏｐ（ｓ'）
となるので、より処理が少なくなり、計算速度が速くな
る。具体的には以下のような処理にてｔｏｐ（ｓ）が求
められる（図５）。なお、ｓ（ｊ）は、エフェクティブ
なｓを小さい順に並べた数列｛ｓ（１），ｓ
（２），．．ｓ（ｑ）｝であって、ｊ番目のｓを示すも
のとする。また、このエフェクティブなｓはｑ個あり、
バケットは先に述べたようにＭ個ある。
【００４０】ステップ３００にて開始された処理は、ス
テップ３１０にて初期化が行われ、ｊ＝ｑ、ｉ＝Ｍとさ
れる。そして、全てのエフェクティブなｓについて処理
するために、ｊ＝０であるかを判断する（ステップ３２
０）。ここで、全てのエフェクティブなｓが処理されて
いなければ、ｃｏｎｆ（ｓ（ｊ），ｉ）＜αであるかを
判断する（ステップ３３０）。もし、ｃｏｎｆ（ｓ
（ｊ），ｉ）＜αであれば、ｉを１デクリメントする
（ステップ３４０）。しかし、何回かｉをデクリメント
すると、ｉ＝ｓ（ｊ）−１となる場合がある。これは、
エフェクティブの定義に反することとなるので、これ以
上は計算しても意味がないので、次のエフェクティブな
ｓの処理に移るために、ステップ３６０に移行する（ス
テップ３４５）。そうでなれば、ステップ３３０に戻
る。
テップ３１０にて初期化が行われ、ｊ＝ｑ、ｉ＝Ｍとさ
れる。そして、全てのエフェクティブなｓについて処理
するために、ｊ＝０であるかを判断する（ステップ３２
０）。ここで、全てのエフェクティブなｓが処理されて
いなければ、ｃｏｎｆ（ｓ（ｊ），ｉ）＜αであるかを
判断する（ステップ３３０）。もし、ｃｏｎｆ（ｓ
（ｊ），ｉ）＜αであれば、ｉを１デクリメントする
（ステップ３４０）。しかし、何回かｉをデクリメント
すると、ｉ＝ｓ（ｊ）−１となる場合がある。これは、
エフェクティブの定義に反することとなるので、これ以
上は計算しても意味がないので、次のエフェクティブな
ｓの処理に移るために、ステップ３６０に移行する（ス
テップ３４５）。そうでなれば、ステップ３３０に戻
る。
【００４１】ステップ３３０にてｃｏｎｆ（ｓ（ｊ），
ｉ）＜αでなければ、ｔｏｐ（ｓ（ｊ））が見つかった
ことになるので、ｔｏｐ（ｓ（ｊ））＝ｉとする（ステ
ップ３５０）。そして、次のエフェクティブなｓについ
てｔｏｐ（ｓ）を見つけるために、ｊを１デクリメント
する（ステップ３６０）。このような処理を繰り返し、
エフェクティブなｓについてｔｏｐ（ｓ）を見つけ出
す。
ｉ）＜αでなければ、ｔｏｐ（ｓ（ｊ））が見つかった
ことになるので、ｔｏｐ（ｓ（ｊ））＝ｉとする（ステ
ップ３５０）。そして、次のエフェクティブなｓについ
てｔｏｐ（ｓ）を見つけるために、ｊを１デクリメント
する（ステップ３６０）。このような処理を繰り返し、
エフェクティブなｓについてｔｏｐ（ｓ）を見つけ出
す。
【００４２】上述のステップ３３０を簡単に処理するた
めに、
めに、
【数９】 を予め計算しておき、テーブルに保持しておく。そうす
ると、Ｇ（ｉ）−Ｇ（ｓ（ｊ）−１）＜０であれば、ｃ
ｏｎｆ（ｓ（ｊ），ｉ）＜αであるから、計算が高速に
なる。
ると、Ｇ（ｉ）−Ｇ（ｓ（ｊ）−１）＜０であれば、ｃ
ｏｎｆ（ｓ（ｊ），ｉ）＜αであるから、計算が高速に
なる。
【００４３】これにてｔｏｐ（ｓ）が求まり、終了イン
デックスｔが求まった。この処理は、Ｏ（Ｍ）で処理可
能である。
デックスｔが求まった。この処理は、Ｏ（Ｍ）で処理可
能である。
【００４４】なお、上述した簡単な例（表１）にて処理
を説明しておく。先の例ではエフェクティブなｓは
｛１，３，４，５，７｝であったので、ｓ＝７から処理
が開始される。まず、ｉ＝１０にセットされ、ｃｏｎｆ
（７，１０）を計算すると、０．５となり、ｉ＝１０は
ｔｏｐ（７）となることがわかる。次に、ｓ＝５とする
と、ｉ＝１０，ｉ＝９，の場合には、ｃｏｎｆ（５，１
０），ｃｏｎｆ（５，９）は０．５より小さいが、ｉ＝
８の場合にｃｏｎｆ（５，８）＝０．５となり、ｔｏｐ
（５）＝８となる。
を説明しておく。先の例ではエフェクティブなｓは
｛１，３，４，５，７｝であったので、ｓ＝７から処理
が開始される。まず、ｉ＝１０にセットされ、ｃｏｎｆ
（７，１０）を計算すると、０．５となり、ｉ＝１０は
ｔｏｐ（７）となることがわかる。次に、ｓ＝５とする
と、ｉ＝１０，ｉ＝９，の場合には、ｃｏｎｆ（５，１
０），ｃｏｎｆ（５，９）は０．５より小さいが、ｉ＝
８の場合にｃｏｎｆ（５，８）＝０．５となり、ｔｏｐ
（５）＝８となる。
【００４５】そしてｓ＝４について、ｉ＝８から処理を
始めるが、ｉ＝４となっても確信度が０．５以上になら
ないので、ｓ＝４に対応する終了インデックスは存在し
ないこととなる。よって、ｓ＝３の処理に移るが、これ
もｉ＝４，ｉ＝３について、確信度は０．５以上になら
ない。そこで、最後のｓ＝１を処理するわけであるが、
ｉ＝１でないと確信度が０．５以上にならないので、ｔ
ｏｐ（１）＝１となる。
始めるが、ｉ＝４となっても確信度が０．５以上になら
ないので、ｓ＝４に対応する終了インデックスは存在し
ないこととなる。よって、ｓ＝３の処理に移るが、これ
もｉ＝４，ｉ＝３について、確信度は０．５以上になら
ない。そこで、最後のｓ＝１を処理するわけであるが、
ｉ＝１でないと確信度が０．５以上にならないので、ｔ
ｏｐ（１）＝１となる。
【００４６】このようにして、ｔｏｐ（７）＝１０，ｔ
ｏｐ（５）＝８，ｔｏｐ（１）＝１となる。
ｏｐ（５）＝８，ｔｏｐ（１）＝１となる。
【００４７】（４）最大サポート区間検出処理 このように、開始インデックスと終了インデックスが対
で求まったものがある場合には、その区間Ｉ［ｓ，ｔ］
に含まれる顧客の割合が最も高い、又は顧客数が最も多
い区間を選択する。これは、
で求まったものがある場合には、その区間Ｉ［ｓ，ｔ］
に含まれる顧客の割合が最も高い、又は顧客数が最も多
い区間を選択する。これは、
【数１０】 で求まる。但し、これ自体１つあたりＯ（Ｍ）のオーダ
ーで手数がかかるが、これも
ーで手数がかかるが、これも
【数１１】 を計算しておき、Ｓｕｍ（ｔ）−Ｓｕｍ（ｓ−１）で求
める。
める。
【００４８】なお、先の具体例では、［７，１０］と
［５，８］ともデータ数は同一であるので、どちらも出
力されることとなる。
［５，８］ともデータ数は同一であるので、どちらも出
力されることとなる。
【００４９】この区間Ｉを得ることにより、この区間Ｉ
に属するデータについて必要な属性をユーザは容易に取
り出すことができる。このユーザが必要な属性とは、例
えばダイレクトメールを送る際であれば、顧客の名前・
宛先等のデータであるし、破産危険の高い顧客の抽出で
あれば、顧客ＩＤ等であり、そのＩＤにてこれ以上の貸
し出しを停止する手続きをとる。区間Ｉが求まってしま
えば、従来技術の説明の欄で説明したように、関係デー
タベースでは簡単な操作にて行えるので、ここではこれ
以上述べない。
に属するデータについて必要な属性をユーザは容易に取
り出すことができる。このユーザが必要な属性とは、例
えばダイレクトメールを送る際であれば、顧客の名前・
宛先等のデータであるし、破産危険の高い顧客の抽出で
あれば、顧客ＩＤ等であり、そのＩＤにてこれ以上の貸
し出しを停止する手続きをとる。区間Ｉが求まってしま
えば、従来技術の説明の欄で説明したように、関係デー
タベースでは簡単な操作にて行えるので、ここではこれ
以上述べない。
【００５０】以上述べた処理をまとめて、図６に全体を
示しておく。
示しておく。
【００５１】以上本発明の一実施例を示したが、速度を
多少遅くしてもよい場合には、予め必要な行列を計算し
ておき、その行列を探索することにより開始又は終了イ
ンデックスを求めるようにすることもできる。すなわ
ち、例えば数８のカッコ内を計算しておき、それをＦ
（ｊ，ｓ）とするような行列を用意し、上半三角形のす
べての要素が負である列を取り出し、その列を開始イン
デックスとすることもできる。また、ｓからｊまでを加
算していくように数８のカッコ内を変形し、それによっ
てできた行列の下半三角形について、開始インデックス
ｓの列を探索して終了インデックスを求めるようにする
こともできる。
多少遅くしてもよい場合には、予め必要な行列を計算し
ておき、その行列を探索することにより開始又は終了イ
ンデックスを求めるようにすることもできる。すなわ
ち、例えば数８のカッコ内を計算しておき、それをＦ
（ｊ，ｓ）とするような行列を用意し、上半三角形のす
べての要素が負である列を取り出し、その列を開始イン
デックスとすることもできる。また、ｓからｊまでを加
算していくように数８のカッコ内を変形し、それによっ
てできた行列の下半三角形について、開始インデックス
ｓの列を探索して終了インデックスを求めるようにする
こともできる。
【００５２】以上、本発明における処理のプロセスを説
明した。このような処理プロセスは、コンピュータ・プ
ログラムによって実現し、実行するようにしてもよい。
例えば、図７のような通常のコンピュータ・システムに
おいて実行できるようなプログラムにすることもでき
る。処理プログラムは、ＨＤＤ１０５０に格納され、実
行時にはメインメモリ１０２０にロードされ、ＣＰＵ１
０１０によって処理される。また、ＨＤＤ１０５０はデ
ータベースをも含んでおり、処理プログラムはそのデー
タベースに対するアクセスを行う。ユーザは、入力装置
１０７０にて確信度Ｔの値や、データ出力の命令を入力
する。表示装置１０６０には、必要な場合には求められ
た区間Ｉや、区間Ｉに含まれるデータの必要な属性を表
示する。入力装置には、キーボードやマウス、ポインテ
ィング・デバイスやディジタイザを含む。さらに、出力
結果を補助記憶装置であるＦＤＤ１０３０のフロッピー
・ディスクに記憶したり、また新たなデータをＦＤＤ１
０３０から入力することもできる。さらに、ＣＤ−ＲＯ
Ｍドライブ１０４０を用いて、データを入力することも
できる。
明した。このような処理プロセスは、コンピュータ・プ
ログラムによって実現し、実行するようにしてもよい。
例えば、図７のような通常のコンピュータ・システムに
おいて実行できるようなプログラムにすることもでき
る。処理プログラムは、ＨＤＤ１０５０に格納され、実
行時にはメインメモリ１０２０にロードされ、ＣＰＵ１
０１０によって処理される。また、ＨＤＤ１０５０はデ
ータベースをも含んでおり、処理プログラムはそのデー
タベースに対するアクセスを行う。ユーザは、入力装置
１０７０にて確信度Ｔの値や、データ出力の命令を入力
する。表示装置１０６０には、必要な場合には求められ
た区間Ｉや、区間Ｉに含まれるデータの必要な属性を表
示する。入力装置には、キーボードやマウス、ポインテ
ィング・デバイスやディジタイザを含む。さらに、出力
結果を補助記憶装置であるＦＤＤ１０３０のフロッピー
・ディスクに記憶したり、また新たなデータをＦＤＤ１
０３０から入力することもできる。さらに、ＣＤ−ＲＯ
Ｍドライブ１０４０を用いて、データを入力することも
できる。
【００５３】さらに、本発明の処理プロセスを実現した
コンピュータ・プログラムは、フロッピー・ディスクや
ＣＤ−ＲＯＭといった記憶媒体に記憶して、持ち運ぶこ
とができる。この場合、通常のデータベース検索プログ
ラムのデータ取り出し部分や、表示装置１０６０に表示
するだけの処理を行うプログラムは、すでにＨＤＤ１０
５０に記憶されている場合もある。よって、それ以外の
部分が、上記のような記憶媒体にて流通することは通常
行われる事項である。
コンピュータ・プログラムは、フロッピー・ディスクや
ＣＤ−ＲＯＭといった記憶媒体に記憶して、持ち運ぶこ
とができる。この場合、通常のデータベース検索プログ
ラムのデータ取り出し部分や、表示装置１０６０に表示
するだけの処理を行うプログラムは、すでにＨＤＤ１０
５０に記憶されている場合もある。よって、それ以外の
部分が、上記のような記憶媒体にて流通することは通常
行われる事項である。
【００５４】また、本発明の処理を専用に行うような装
置を設けてもよい。例えば、図８のような装置が考えら
れる。データベース１５００は、バケット処理部１５１
０及び出力部１５４０に接続されており、バケット処理
部１５１０は開始インデックス検出部１５２０に接続さ
れている。また、開始インデックス検出部１５２０の出
力は、終了インデックス検出部１５３０に接続されてお
り、この終了インデックス検出部１５３０の出力は出力
部１５４０に接続される。入力部１５５０は、出力部１
５４０及び開始及び終了インデックス検出部１５２０，
１５３０に接続されている。
置を設けてもよい。例えば、図８のような装置が考えら
れる。データベース１５００は、バケット処理部１５１
０及び出力部１５４０に接続されており、バケット処理
部１５１０は開始インデックス検出部１５２０に接続さ
れている。また、開始インデックス検出部１５２０の出
力は、終了インデックス検出部１５３０に接続されてお
り、この終了インデックス検出部１５３０の出力は出力
部１５４０に接続される。入力部１５５０は、出力部１
５４０及び開始及び終了インデックス検出部１５２０，
１５３０に接続されている。
【００５５】このバケット処理部１５１０は、先に述べ
たバケット処理を行う部分であり、各バケット内のデー
タ及びその中で０−１属性が１であるデータの数をカウ
ントする。また、その結果を用いて開始インデックス検
出部１５２０は、入力手段からの入力である確信度αを
用いて、先に述べたエフェクティブなｓの検出処理を行
う。その検出されたエフェクティブなｓを用いて、終了
インデックス検出部１５３０も、入力部１５５０からの
確信度αに従い、ｔｏｐ（ｓ）検出処理を行う。出力部
１５４０は、求められたｓ及びｔｏｐ（ｓ）の中から最
もサポートが大きい区間Ｉを選択し、ユーザの入力を伝
える入力部１５５０からの信号に応答して、区間Ｉに属
するデータの適当な属性を抽出する。そして、表示装置
（図示せず）に表示したり、印刷装置に打ち出したり、
フロッピー・ディスクや、ハードディスクに記憶したり
する。
たバケット処理を行う部分であり、各バケット内のデー
タ及びその中で０−１属性が１であるデータの数をカウ
ントする。また、その結果を用いて開始インデックス検
出部１５２０は、入力手段からの入力である確信度αを
用いて、先に述べたエフェクティブなｓの検出処理を行
う。その検出されたエフェクティブなｓを用いて、終了
インデックス検出部１５３０も、入力部１５５０からの
確信度αに従い、ｔｏｐ（ｓ）検出処理を行う。出力部
１５４０は、求められたｓ及びｔｏｐ（ｓ）の中から最
もサポートが大きい区間Ｉを選択し、ユーザの入力を伝
える入力部１５５０からの信号に応答して、区間Ｉに属
するデータの適当な属性を抽出する。そして、表示装置
（図示せず）に表示したり、印刷装置に打ち出したり、
フロッピー・ディスクや、ハードディスクに記憶したり
する。
【００５６】図８のような装置は、一例であって、先に
述べた処理を実行できるようないかなる装置にしてもよ
い。例えば、全体を制御する制御部を設けて、この制御
部が全体の処理の流れや、入力部１５５０からの信号を
処理して出力の形態を決定するようにしてもよい。
述べた処理を実行できるようないかなる装置にしてもよ
い。例えば、全体を制御する制御部を設けて、この制御
部が全体の処理の流れや、入力部１５５０からの信号を
処理して出力の形態を決定するようにしてもよい。
【００５７】
【効果】以上述べたように、数値属性と０−１属性を有
するデータの相関を見い出すことができた。
するデータの相関を見い出すことができた。
【００５８】また、上述の処理を高速に行うこともでき
た。
た。
【００５９】また、確信度α以上の条件で、サポートを
最大とする区間Ｉを求めることができた。
最大とする区間Ｉを求めることができた。
【図１】バケット処理のフローチャートである。
【図２】バケット処理を複数のプロセッサ・エレメント
にて行う場合のフローチャートである。
にて行う場合のフローチャートである。
【図３】バケット処理が終了した状態を示す模式図であ
る。
る。
【図４】エフェクティブなｓを求める処理のフローを示
した図である。
した図である。
【図５】ｔｏｐ（ｓ）を求めるための処理のフローを示
した図である。
した図である。
【図６】全体のフローを示した図である。
【図７】通常のコンピュータ・システムで本発明を実施
した場合の装置構成の一例を示す図である。
した場合の装置構成の一例を示す図である。
【図８】本発明を専用の装置で実施した場合のブロック
図である。
図である。
１０１０ ＣＰＵ １０２０ メインメモリ １０３０ ＦＤＤ １０４０ ＣＤ−ＲＯＭドライブ １０５０ ＨＤＤ １０６０ 表示装置 １０７０ 入力装置 １５００ データベース １５１０ バケット処理部 １５２０ 開始インデック
ス検出部 １５３０ 終了インデックス検出部 １５４０ 出力部 １５５０ 入力部
ス検出部 １５３０ 終了インデックス検出部 １５４０ 出力部 １５５０ 入力部
【手続補正書】
【提出日】平成７年１１月２４日
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】請求項１
【補正方法】変更
【補正内容】
【数１】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって、当該ｓとの間に属するデータの前記０
−１属性が１である確率がα以上である最大のｔを求め
る終了インデックス検出ステップと、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって、当該ｓとの間に属するデータの前記０
−１属性が１である確率がα以上である最大のｔを求め
る終了インデックス検出ステップと、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】請求項７
【補正方法】変更
【補正内容】
【数２】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって、当該ｓとの間に属するデータの前記０−１
属性が１である確率がα以上である最大のｔを求める終
了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって、当該ｓとの間に属するデータの前記０−１
属性が１である確率がα以上である最大のｔを求める終
了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】請求項１３
【補正方法】変更
【補正内容】
【数３】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求させる開始インデックス検出用プログラム
コード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって、
当該ｓとの間に属するデータの前記０−１属性が１であ
る確率がα以上である最大のｔを求めさせる終了インデ
ックス検出用プログラムコード手段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求させる開始インデックス検出用プログラム
コード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって、
当該ｓとの間に属するデータの前記０−１属性が１であ
る確率がα以上である最大のｔを求めさせる終了インデ
ックス検出用プログラムコード手段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正内容】
【００１１】以上述べたことをまとめると、各々数値属
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
【数５】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、開
始インデックス検出ステップによって検出されたｓ以上
であって、当該ｓとの間に属するデータの０−１属性が
１である確率がα以上である最大のｔを求める終了イン
デックス検出ステップと、最もデータ数の大きい区間
［ｓ，ｔ］を選択するステップと、区間［ｓ，ｔ］に入
るデータをデータベースから取り出すステップとを含
む。これにより双対結合ルールが導き出される。 ─────────────────────────────────────────────────────
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、開
始インデックス検出ステップによって検出されたｓ以上
であって、当該ｓとの間に属するデータの０−１属性が
１である確率がα以上である最大のｔを求める終了イン
デックス検出ステップと、最もデータ数の大きい区間
［ｓ，ｔ］を選択するステップと、区間［ｓ，ｔ］に入
るデータをデータベースから取り出すステップとを含
む。これにより双対結合ルールが導き出される。 ─────────────────────────────────────────────────────
【手続補正書】
【提出日】平成８年６月２８日
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】請求項１
【補正方法】変更
【補正内容】
【数１】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって、当該ｓとの間に属するデータの前記０
−１属性が１となる確率がα以上である最大のｔを求め
る終了インデックス検出ステップと、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって、当該ｓとの間に属するデータの前記０
−１属性が１となる確率がα以上である最大のｔを求め
る終了インデックス検出ステップと、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】請求項７
【補正方法】変更
【補正内容】
【数２】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって、当該ｓとの間に属するデータの前記０−１
属性が１となる確率がα以上である最大のｔを求める終
了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって、当該ｓとの間に属するデータの前記０−１
属性が１となる確率がα以上である最大のｔを求める終
了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】請求項１３
【補正方法】変更
【補正内容】
【数３】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求させる開始インデックス検出用プログラムコ
ード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって、
当該ｓとの間に属するデータの前記０−１属性が１とな
る確率がα以上である最大のｔを求めさせる終了インデ
ックス検出用プログラムコード手段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求させる開始インデックス検出用プログラムコ
ード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって、
当該ｓとの間に属するデータの前記０−１属性が１とな
る確率がα以上である最大のｔを求めさせる終了インデ
ックス検出用プログラムコード手段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正内容】
【００１０】
【課題を解決するための手段】本発明を大きく４つに分
けて説明すると、以下のとおりになる。 （１）数値属性を複数の区間（バケット）に分け、数値
属性の値に応じて、各データを１つのバケットに入れ
る。そして、各バケット内のデータ数と、０−１属性が
１であるデータの数をカウントする。 （２）検出すべき区間の開始区間を検出する。これは、
けて説明すると、以下のとおりになる。 （１）数値属性を複数の区間（バケット）に分け、数値
属性の値に応じて、各データを１つのバケットに入れ
る。そして、各バケット内のデータ数と、０−１属性が
１であるデータの数をカウントする。 （２）検出すべき区間の開始区間を検出する。これは、
【数４】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）の条件を
満たすようなｓを見つけ出すことである。 （３）先の開始区間に対応する終了区間を検出する。こ
れは、予め決められた確信度α以上となる最大の区間を
見つけ出すことである。 （４）以上のように見つけ出された開始区間と終了区間
の組のうち、最も顧客が含まれる区間の組が、本問題の
答えとなる。この後に、回答となる区間に含まれるデー
タのうち、必要なデータ属性を取り出す。
おいて前記０−１属性が１であるデータの数）の条件を
満たすようなｓを見つけ出すことである。 （３）先の開始区間に対応する終了区間を検出する。こ
れは、予め決められた確信度α以上となる最大の区間を
見つけ出すことである。 （４）以上のように見つけ出された開始区間と終了区間
の組のうち、最も顧客が含まれる区間の組が、本問題の
答えとなる。この後に、回答となる区間に含まれるデー
タのうち、必要なデータ属性を取り出す。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正内容】
【００１１】以上述べたことをまとめると、各々数値属
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
【数５】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、開始
インデックス検出ステップによって検出されたｓ以上で
あって、当該ｓとの間に属するデータの０−１属性が１
となる確率がα以上である最大のｔを求める終了インデ
ックス検出ステップと、最もデータ数の大きい区間
［ｓ，ｔ］を選択するステップと、区間［ｓ，ｔ］に入
るデータをデータベースから取り出すステップとを含
む。これにより双対結合ルールが導き出される。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、開始
インデックス検出ステップによって検出されたｓ以上で
あって、当該ｓとの間に属するデータの０−１属性が１
となる確率がα以上である最大のｔを求める終了インデ
ックス検出ステップと、最もデータ数の大きい区間
［ｓ，ｔ］を選択するステップと、区間［ｓ，ｔ］に入
るデータをデータベースから取り出すステップとを含
む。これにより双対結合ルールが導き出される。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正内容】
【００１３】この実質的に同一のデータ数を含むように
し且つ高速に前記カウントするステップを行うには、Ｎ
個のデータのうちＸ個のデータをランダム・サンプリン
グするステップと、Ｘ個のデータを数値属性の値でソー
トするステップと、ソートされたデータ中のｉ・Ｘ／Ｍ
（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に該
当するデータの数値属性の値を保持するステップと、保
持された値に基づき、各区間に該当するデータの数をカ
ウントするステップとを含むようにすることも考えられ
る。
し且つ高速に前記カウントするステップを行うには、Ｎ
個のデータのうちＸ個のデータをランダム・サンプリン
グするステップと、Ｘ個のデータを数値属性の値でソー
トするステップと、ソートされたデータ中のｉ・Ｘ／Ｍ
（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に該
当するデータの数値属性の値を保持するステップと、保
持された値に基づき、各区間に該当するデータの数をカ
ウントするステップとを含むようにすることも考えられ
る。
【手続補正書】
【提出日】平成８年６月２８日
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】請求項１
【補正方法】変更
【補正内容】
【数１】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって、当該ｓとの間に属するデータの前記０
−１属性が１となる確率がα以上である最大のｔを求め
る終了インデックス検出ステップと、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって、当該ｓとの間に属するデータの前記０
−１属性が１となる確率がα以上である最大のｔを求め
る終了インデックス検出ステップと、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】請求項７
【補正方法】変更
【補正内容】
【数２】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって、当該ｓとの間に属するデータの前記０−１
属性が１となる確率がα以上である最大のｔを求める終
了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって、当該ｓとの間に属するデータの前記０−１
属性が１となる確率がα以上である最大のｔを求める終
了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】請求項１３
【補正方法】変更
【補正内容】
【数３】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求させる開始インデックス検出用プログラムコ
ード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって、
当該ｓとの間に属するデータの前記０−１属性が１とな
る確率がα以上である最大のｔを求めさせる終了インデ
ックス検出用プログラムコード手段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求させる開始インデックス検出用プログラムコ
ード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって、
当該ｓとの間に属するデータの前記０−１属性が１とな
る確率がα以上である最大のｔを求めさせる終了インデ
ックス検出用プログラムコード手段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正内容】
【００１０】
【課題を解決するための手段】本発明を大きく４つに分
けて説明すると、以下のとおりになる。 （１）数値属性を複数の区間（バケット）に分け、数値
属性の値に応じて、各データを１つのバケットに入れ
る。そして、各バケット内のデータ数と、０−１属性が
１であるデータの数をカウントする。 （２）検出すべき区間の開始区間を検出する。これは、
けて説明すると、以下のとおりになる。 （１）数値属性を複数の区間（バケット）に分け、数値
属性の値に応じて、各データを１つのバケットに入れ
る。そして、各バケット内のデータ数と、０−１属性が
１であるデータの数をカウントする。 （２）検出すべき区間の開始区間を検出する。これは、
【数４】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）の条件を
満たすようなｓを見つけ出すことである。 （３）先の開始区間に対応する終了区間を検出する。こ
れは、予め決められた確信度α以上となる最大の区間を
見つけ出すことである。 （４）以上のように見つけ出された開始区間と終了区間
の組のうち、最も顧客が含まれる区間の組が、本問題の
答えとなる。この後に、回答となる区間に含まれるデー
タのうち、必要なデータ属性を取り出す。
おいて前記０−１属性が１であるデータの数）の条件を
満たすようなｓを見つけ出すことである。 （３）先の開始区間に対応する終了区間を検出する。こ
れは、予め決められた確信度α以上となる最大の区間を
見つけ出すことである。 （４）以上のように見つけ出された開始区間と終了区間
の組のうち、最も顧客が含まれる区間の組が、本問題の
答えとなる。この後に、回答となる区間に含まれるデー
タのうち、必要なデータ属性を取り出す。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正内容】
【００１１】以上述べたことをまとめると、各々数値属
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
性と０−１属性を含む、複数のデータを有するデータベ
ースにおいて、０−１属性が１である確率がα以上であ
って且つ最大数のデータが属する数値属性の区間を導き
出し、該当するデータを取り出すデータベース検索方法
であって、数値属性に対応する軸を複数の区間に分割
し、各区間に含まれるデータ数及び０−１属性が１であ
るデータの数をカウントするステップと、
【数５】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、開始
インデックス検出ステップによって検出されたｓ以上で
あって、当該ｓとの間に属するデータの０−１属性が１
となる確率がα以上である最大のｔを求める終了インデ
ックス検出ステップと、最もデータ数の大きい区間
［ｓ，ｔ］を選択するステップと、区間［ｓ，ｔ］に入
るデータをデータベースから取り出すステップとを含
む。これにより双対結合ルールが導き出される。
おいて前記０−１属性が１であるデータの数）であるよ
うなｓを求める開始インデックス検出ステップと、開始
インデックス検出ステップによって検出されたｓ以上で
あって、当該ｓとの間に属するデータの０−１属性が１
となる確率がα以上である最大のｔを求める終了インデ
ックス検出ステップと、最もデータ数の大きい区間
［ｓ，ｔ］を選択するステップと、区間［ｓ，ｔ］に入
るデータをデータベースから取り出すステップとを含
む。これにより双対結合ルールが導き出される。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正内容】
【００１３】この実質的に同一のデータ数を含むように
し且つ高速に前記カウントするステップを行うには、Ｎ
個のデータのうちＸ個のデータをランダム・サンプリン
グするステップと、Ｘ個のデータを数値属性の値でソー
トするステップと、ソートされたデータ中のｉ・Ｘ／Ｍ
（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に該
当するデータの数値属性の値を保持するステップと、保
持された値に基づき、各区間に該当するデータの数をカ
ウントするステップとを含むようにすることも考えられ
る。
し且つ高速に前記カウントするステップを行うには、Ｎ
個のデータのうちＸ個のデータをランダム・サンプリン
グするステップと、Ｘ個のデータを数値属性の値でソー
トするステップと、ソートされたデータ中のｉ・Ｘ／Ｍ
（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に該
当するデータの数値属性の値を保持するステップと、保
持された値に基づき、各区間に該当するデータの数をカ
ウントするステップとを含むようにすることも考えられ
る。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 福田 剛志 神奈川県大和市下鶴間1623番地14 日本ア イ・ビー・エム株式会社 東京基礎研究所 内 (72)発明者 森下 真一 神奈川県大和市下鶴間1623番地14 日本ア イ・ビー・エム株式会社 東京基礎研究所 内 (72)発明者 徳山 豪 神奈川県大和市下鶴間1623番地14 日本ア イ・ビー・エム株式会社 東京基礎研究所 内
Claims (18)
- 【請求項１】各々数値属性と０−１属性を含む、複数の
データを有するデータベースにおいて、 前記０−１属性が１である確率がα以上であって且つ最
大数のデータが属する前記数値属性の区間を導き出し、
該当するデータを取り出すデータベース検索方法であっ
て、 前記数値属性に対応する軸を複数の区間に分割し、各前
記区間に含まれるデータ数及び前記０−１属性が１であ
るデータの数をカウントするステップと、 【数１】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出ステップと、 前記開始インデックス検出ステップによって検出された
ｓ以上であって前記０−１属性が１である確率がα以上
である最大のｔを求める終了インデックス検出ステップ
と、 最もデータ数の大きい区間［ｓ，ｔ］を選択するステッ
プと、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出すステップとを含むデータベース検索方法。 - 【請求項２】前記複数の区間の各々が、実質的に同一の
データ数を含むように設定されていることを特徴とする
請求項１記載のデータベース検索方法。 - 【請求項３】前記カウントするステップが、 前記Ｎ個のデータのうちＸ個のデータをランダム・サン
プリングするステップと、 前記Ｘ個のデータを前記数値属性の値でソートするステ
ップと、 ソートされたデータ中のｉ・Ｘ／Ｍ（ｉ＝１，
２，．．．Ｍ−１，Ｍは区間の数）番目に該当するデー
タの前記数値属性の値を保持するステップと、 保持された前記値に基づき、各前記区間に該当するデー
タの数をカウントするステップとを含む請求項１記載の
データベース検索方法。 - 【請求項４】前記開始インデックス検出ステップが、 ｗ＜０であって、ｖs-1−αｕs-1≧０であるかどうかを
判定するステップと、 前記判定ステップが肯定的な回答を返す場合には、ｗ＝
ｖs-1−αｕs-1として、ｗ＜０であるかを判断するステ
ップと、 前記判定ステップが否定的な回答を返す場合には、ｗ＝
ｗ＋ｖs-1−αｕs-1として、ｗ＜０であるかを判断する
ステップとを含む請求項１記載のデータベース検索方
法。 - 【請求項５】前記終了インデックス検出ステップが、最
も大きい開始インデックスｓに対応する終了インデック
スｔを検出する動作から開始されることを特徴とする請
求項１記載のデータベース検出方法。 - 【請求項６】１の開始インデックスｓに対応する終了イ
ンデックスｔは、前記１の開始インデックスｓの１つ前
に処理された開始インデックスｓ'に対応する終了イン
デックスｔ'以下について処理することにより求められ
ることを特徴とする請求項５記載のデータベース検索方
法。 - 【請求項７】各々数値属性と０−１属性を含む、複数の
データを有するデータベースにおいて、 前記０−１属性が１である確率がα以上であって且つ最
大数のデータが属する前記数値属性の区間を導き出し、
該当するデータを取り出すデータベース検索装置であっ
て、 前記数値属性に対応する軸を複数の区間に分割し、各前
記区間に含まれるデータ数及び前記０−１属性が１であ
るデータの数をカウントする手段と、 【数２】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求める開始インデックス検出手段と、 前記開始インデックス検出手段によって検出されたｓ以
上であって前記０−１属性が１である確率がα以上であ
る最大のｔを求める終了インデックス検出手段と、 最もデータ数の大きい区間［ｓ，ｔ］を選択する手段
と、 前記区間［ｓ，ｔ］に入るデータを前記データベースか
ら取り出す手段とを含むデータベース検索装置。 - 【請求項８】前記複数の区間の各々が、実質的に同一の
データ数を含むように設定されていることを特徴とする
請求項７記載のデータベース検索装置。 - 【請求項９】前記カウントする手段が、 前記Ｎ個のデータのうちＸ個のデータをランダム・サン
プリングし、 前記Ｘ個のデータを前記数値属性の値でソートし、 ソートされたデータ中のｉ・Ｘ／Ｍ（ｉ＝１，
２，．．．Ｍ，Ｍ−１は区間の数）番目に該当するデー
タの前記数値属性の値を保持し、 保持された前記値に基づき、各前記区間に該当するデー
タの数をカウントすることを特徴とする請求項７記載の
データベース検索装置。 - 【請求項１０】前記開始インデックス検出手段が、 ｗ＜０であって、ｖs-1−αｕs-1≧０であるかどうかを
判定し、 前記判定が肯定的である場合には、ｗ＝ｖs-1−αｕs-1
として、ｗ＜０であるかを判断し、 前記判定が否定的である場合には、ｗ＝ｗ＋ｖs-1−α
ｕs-1として、ｗ＜０であるかを判断することを特徴と
する請求項７記載のデータベース検索装置。 - 【請求項１１】前記終了インデックス検出手段が、最も
大きい開始インデックスｓに対応する終了インデックス
ｔを検出する動作から始動されることを特徴とする請求
項７記載のデータベース検出装置。 - 【請求項１２】１の開始インデックスｓに対応する終了
インデックスｔは、前記１の開始インデックスｓの１つ
前に処理された開始インデックスｓ'に対応する終了イ
ンデックスｔ'以下について処理することにより求めら
れることを特徴とする請求項１１記載のデータベース検
索装置。 - 【請求項１３】各々数値属性と０−１属性を含む、複数
のデータを有するデータベースにおいて、 コンピュータに、前記０−１属性が１である確率がα以
上であって且つ最大数のデータが属する前記数値属性の
区間を導き出させるプログラムコード手段を含む、コン
ピュータが読み取り可能な記憶媒体であって、 前記プログラムコード手段が、 前記コンピュータに、前記数値属性に対応する軸を複数
の区間に分割させ、各前記区間に含まれるデータ数及び
前記０−１属性が１であるデータの数をカウントさせる
コンピュータコード手段と、 前記コンピュータに、 【数３】 （ｕiはある区間に含まれるデータ数、ｖiはある区間に
おいて前記０−１属性が１であるデータの割合）である
ようなｓを求させる開始インデックス検出用プログラム
コード手段と、 前記コンピュータに、前記開始インデックス検出用プロ
グラムコード手段によって検出されたｓ以上であって前
記０−１属性が１である確率がα以上である最大のｔを
求めさせる終了インデックス検出用プログラムコード手
段と、 前記コンピュータに、最もデータ数の大きい区間［ｓ，
ｔ］を選択させるプログラムコード手段とを含むコンピ
ュータが読み取り可能な記憶媒体。 - 【請求項１４】前記複数の区間の各々が、実質的に同一
のデータ数を含むように設定されていることを特徴とす
る請求項１３記載のコンピュータが読み取り可能な記憶
媒体。 - 【請求項１５】前記カウントするプログラムコード手段
が、 前記コンピュータに、前記Ｎ個のデータのうちＸ個のデ
ータをランダム・サンプリングさせるプログラムコード
手段と、 前記コンピュータに、前記Ｘ個のデータを前記数値属性
の値でソートさせるプログラムコード手段と、 前記コンピュータに、ソートされたデータ中のｉ・Ｘ／
Ｍ（ｉ＝１，２，．．．Ｍ−１，Ｍは区間の数）番目に
該当するデータの前記数値属性の値を保持させるプログ
ラムコード手段と、 前記コンピュータに、保持された前記値に基づき、各前
記区間に該当するデータの数をカウントさせるプログラ
ムコード手段とを含む請求項１３載のコンピュータが読
み取り可能な記憶媒体。 - 【請求項１６】前記開始インデックス検出用プログラム
コード手段が、 前記コンピュータに、ｗ＜０であって、ｖs-1−αｕs-1
≧０であるかどうかを判定させる判定用プログラムコー
ド手段と、 前記コンピュータに、前記判定用プログラムコード手段
が肯定的な回答を返す場合には、ｗ＝ｖs-1−αｕs-1と
して、ｗ＜０であるかを判断させるプログラムコード手
段と、 前記コンピュータに、前記判定用プログラムコード手段
が否定的な回答を返す場合には、ｗ＝ｗ＋ｖs-1−αｕ
s-1として、ｗ＜０であるかを判断させるプログラムコ
ード手段とを含む請求項１３載のコンピュータが読み取
り可能な記憶媒体。 - 【請求項１７】前記終了インデックス検出用プログラム
コード手段が、最も大きい開始インデックスｓに対応す
る終了インデックスｔを検出する動作から始動されるこ
とを特徴とする請求項１３記載のコンピュータが読み取
り可能な記憶媒体。 - 【請求項１８】１の開始インデックスｓに対応する終了
インデックスｔは、前記１の開始インデックスｓの１つ
前に処理された開始インデックスｓ'に対応する終了イ
ンデックスｔ'以下について処理することにより求めら
れることを特徴とする請求項１７記載のコンピュータが
読み取り可能な記憶媒体。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP07285416A JP3072708B2 (ja) | 1995-11-01 | 1995-11-01 | データベース検索方法及び装置 |
| US08/738,666 US5983222A (en) | 1995-11-01 | 1996-10-25 | Method and apparatus for computing association rules for data mining in large database |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP07285416A JP3072708B2 (ja) | 1995-11-01 | 1995-11-01 | データベース検索方法及び装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09134363A true JPH09134363A (ja) | 1997-05-20 |
| JP3072708B2 JP3072708B2 (ja) | 2000-08-07 |
Family
ID=17691246
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP07285416A Expired - Fee Related JP3072708B2 (ja) | 1995-11-01 | 1995-11-01 | データベース検索方法及び装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5983222A (ja) |
| JP (1) | JP3072708B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0959415A3 (en) * | 1998-05-21 | 2000-03-15 | Fujitsu Limited | Apparatus for data decomposition, and method and storage medium therefor |
| US9152852B2 (en) | 2012-11-27 | 2015-10-06 | Fujitsu Limited | Perceptual reaction analyzer, and method and program thereof |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3548617B2 (ja) * | 1995-01-31 | 2004-07-28 | 株式会社日立製作所 | 情報検索装置 |
| JPH1115842A (ja) * | 1997-06-24 | 1999-01-22 | Mitsubishi Electric Corp | データマイニング装置 |
| US7054827B1 (en) * | 1997-09-24 | 2006-05-30 | Unisys Corporation | Method and apparatus for validating a survey database |
| JPH11328186A (ja) * | 1997-11-11 | 1999-11-30 | Mitsubishi Electric Corp | 相関ルール生成方法および相関ルール生成装置 |
| US6301575B1 (en) * | 1997-11-13 | 2001-10-09 | International Business Machines Corporation | Using object relational extensions for mining association rules |
| US6094645A (en) * | 1997-11-21 | 2000-07-25 | International Business Machines Corporation | Finding collective baskets and inference rules for internet or intranet mining for large data bases |
| IL122850A0 (en) * | 1998-01-05 | 1999-03-12 | Wizsoft | Pattern recognition using generalized association rules |
| US6266668B1 (en) * | 1998-08-04 | 2001-07-24 | Dryken Technologies, Inc. | System and method for dynamic data-mining and on-line communication of customized information |
| US6182070B1 (en) * | 1998-08-21 | 2001-01-30 | International Business Machines Corporation | System and method for discovering predictive association rules |
| US6236982B1 (en) * | 1998-09-14 | 2001-05-22 | Lucent Technologies, Inc. | System and method for discovering calendric association rules |
| US6278997B1 (en) * | 1999-02-05 | 2001-08-21 | International Business Machines Corporation | System and method for constraint-based rule mining in large, dense data-sets |
| US6278998B1 (en) * | 1999-02-16 | 2001-08-21 | Lucent Technologies, Inc. | Data mining using cyclic association rules |
| US7047212B1 (en) * | 1999-09-13 | 2006-05-16 | Nextmark, Inc. | Method and system for storing prospect lists in a computer database |
| US7246077B1 (en) | 1999-09-13 | 2007-07-17 | Nextmark, Inc. | Systems and methods for generating highly responsive prospect lists |
| US20020069134A1 (en) * | 1999-11-01 | 2002-06-06 | Neal Solomon | System, method and apparatus for aggregation of cooperative intelligent agents for procurement in a distributed network |
| US20020055903A1 (en) * | 1999-11-01 | 2002-05-09 | Neal Solomon | System, method, and apparatus for a cooperative communications network |
| US7007020B1 (en) * | 2000-03-10 | 2006-02-28 | Hewlett-Packard Development Company, L.P. | Distributed OLAP-based association rule generation method and system |
| US20020059219A1 (en) * | 2000-07-17 | 2002-05-16 | Neveitt William T. | System and methods for web resource discovery |
| US6711577B1 (en) | 2000-10-09 | 2004-03-23 | Battelle Memorial Institute | Data mining and visualization techniques |
| US7539677B1 (en) * | 2000-10-09 | 2009-05-26 | Battelle Memorial Institute | Sequential pattern data mining and visualization |
| WO2002033626A1 (en) * | 2000-10-16 | 2002-04-25 | Engage Technologies | Demographic profiling engine |
| US6763148B1 (en) | 2000-11-13 | 2004-07-13 | Visual Key, Inc. | Image recognition methods |
| CA2374298A1 (en) * | 2002-03-01 | 2003-09-01 | Ibm Canada Limited-Ibm Canada Limitee | Computation of frequent data values |
| KR100497212B1 (ko) * | 2002-03-02 | 2005-06-23 | (주)비엘시스템스 | 데이터 마이닝에서의 앙상블 기법에 적용되는 연관성 규칙생성 장치 및 그 방법 |
| US7962483B1 (en) * | 2002-12-20 | 2011-06-14 | Oracle International Corporation | Association rule module for data mining |
| US20050021489A1 (en) * | 2003-07-22 | 2005-01-27 | Microsoft Corporation | Data mining structure |
| KR100632387B1 (ko) | 2005-08-11 | 2006-10-09 | (주) 기산텔레콤 | 약식 데이터베이스 생성/관리 방법과 그 방법을 컴퓨터에기능시키는 프로그램을 기록한 컴퓨터가 읽을 수 있는기록매체 |
| US9256687B2 (en) * | 2013-06-28 | 2016-02-09 | International Business Machines Corporation | Augmenting search results with interactive search matrix |
| FR3066289B1 (fr) * | 2017-05-09 | 2021-03-19 | Quantics Tech | Procede, mise en oeuvre par ordinateur, de recherche de regles d'association dans une base de donnees |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5615341A (en) * | 1995-05-08 | 1997-03-25 | International Business Machines Corporation | System and method for mining generalized association rules in databases |
-
1995
- 1995-11-01 JP JP07285416A patent/JP3072708B2/ja not_active Expired - Fee Related
-
1996
- 1996-10-25 US US08/738,666 patent/US5983222A/en not_active Expired - Fee Related
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0959415A3 (en) * | 1998-05-21 | 2000-03-15 | Fujitsu Limited | Apparatus for data decomposition, and method and storage medium therefor |
| US6341283B1 (en) | 1998-05-21 | 2002-01-22 | Fujitsu Limited | Apparatus for data decomposition and method and storage medium therefor |
| US9152852B2 (en) | 2012-11-27 | 2015-10-06 | Fujitsu Limited | Perceptual reaction analyzer, and method and program thereof |
Also Published As
| Publication number | Publication date |
|---|---|
| US5983222A (en) | 1999-11-09 |
| JP3072708B2 (ja) | 2000-08-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3072708B2 (ja) | データベース検索方法及び装置 | |
| US6542896B1 (en) | System and method for organizing data | |
| JP3282937B2 (ja) | 情報検索方法及びシステム | |
| US5943670A (en) | System and method for categorizing objects in combined categories | |
| IL147736A (en) | Method and system for organizing data | |
| WO2002027532A1 (en) | System and method for use in text analysis of documents and records | |
| JP2002278761A (ja) | 否定項を含む相関ルール抽出方法およびシステム | |
| JPH11120203A (ja) | データベースを合併する方法およびデータベースからドキュメントを検索する装置 | |
| US6505198B2 (en) | Sort system for text retrieval | |
| WO2017065891A1 (en) | Automated join detection | |
| JPH09134365A (ja) | 最適化結合ルール導出方法及び装置 | |
| US20040162824A1 (en) | Method and apparatus for classifying a document with respect to reference corpus | |
| JPH04205560A (ja) | 情報検索処理方式および検索ファイル作成装置 | |
| JP3370787B2 (ja) | 文字配列検索方法 | |
| JP3131142B2 (ja) | 地図データリンケージシステム | |
| JPH04152468A (ja) | 文書検索装置 | |
| JP2001155020A (ja) | 類似文書検索装置、類似文書検索方法及び記録媒体 | |
| JP3249743B2 (ja) | 文書検索システム | |
| JPH0773187A (ja) | 検索システム | |
| JP2682448B2 (ja) | 索引検索方式 | |
| JPH03294964A (ja) | 文書検索方法 | |
| JPH0991297A (ja) | 文字列検索方法及び装置 | |
| JPH07104869B2 (ja) | データ検索加工システム | |
| WO2013069149A1 (ja) | データ検索装置、データの検索方法及びプログラム | |
| JPH10320402A (ja) | 検索式作成方法、検索式作成装置、及び記録媒体 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |