JP3118181B2 - データ間結合ルール導出方法及び装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データベースにお
けるデータ相関の解析（データマイニングという。）に
関し、より詳しくは２項の数値属性と１項の真偽をとる
属性（真偽をとる条件又は０−１属性ともいう。）を有
するデータ間の相関を見い出す手法に関する。

【０００２】

【従来の技術】例えば、銀行の顧客を解析対象とし、流
動性預金残高がいくらくらいで且つ年齢が何歳ぐらいの
人であれば、定期預金残高が２００万円以上になる人が
全体の２０％となるか、といった問題を実際に解くこと
を考える。この流通性預金残高及び年齢は、整数ではあ
るが連続数値であり、一方定期預金残高２００万円以上
というのは、２００万円以上か未満かという分類になる
ので、真偽をとる属性を有するものである。真偽をとる
属性は、例えば「顧客がクレジットカードを有している
か」や「顧客が男性であるか」といった問題と置き換え
ることも可能である。このような課題を解決することが
できれば、銀行はどのような人に、例えば新型の金融商
品に関するダイレクトメールを送ればよいか簡単に分か
るので、効率的な営業活動が行える。

【０００３】従来、先に述べた真偽をとる属性間の相関
を表現するルール（結合ルール、association rule）を
高速に抽出するような研究は、データマイニングの分野
において行われてきた。例えば、R.Agrawal, T.Imielin
ski, and A.Swami, "Miningassociation rules between
sets of items in large databases" In proceedings
of the ACM SIGMOD Conference on Management of dat
a, May 1993. や、R.Agrawal and R.Srikant, "Fast al
gorithms for mining association rules" InProceedin
gs of the 20th VLDB Conference, 1994. 等がある。

【０００４】また、２項の数値データ間のルールを求め
る従来手法には、以下のようなものがある。 １．強い線形相関を見い出すために、平面上の直線で、
点集合を最適近似するものを探す方法。例えば、最小自
乗法、再帰中央法等である。これら方法の欠点は、線形
相関しか分からず、しかも相関係数の絶対値が０．５以
下の場合に線形相関を用いて各データを予測すると精度
が低く、現実にはほとんど役にたたない点にある。 ２．弱い大域相関を見い出すためには、２次元平面上で
正方形、長方形、又は円、楕円で面積に対して多くのデ
ータを含むものを見い出す方法。例えば、計算幾何学ア
ルゴリズムを利用するものである。この場合、計算時間
が大きくなってしまうという欠点がある。例えば円の場
合、Ｏ（Ｍ³）以上の手間が掛かり得る（Ｏ（Ｍ³）は、
オーダーＭ³の計算手間がかかることを示す。Ｍはデー
タ数である。）。また、取り出す相関領域としては決ま
った形をしたものしか扱うことができない。現実には、
決まった形で適切にカバーできる場合は少ない。 ３．平面を正方メッシュに分割しておき、たくさんのデ
ータを含むピクセルを取り出す方法。しかし、取り出さ
れたピクセルの集合は連結でなく、バラバラなことが多
いので、ルールとして見い出すのは困難である。

【０００５】このような手法を用いると、上記の欠点の
他に、データ間の多くのルールのうちで、意味のあるも
のと無意味なものとの区別が難しいという欠点もある。
通常、相関に実用上の意味があるかどうかは人間の判断
によらないといけないことが多いが、１．や２．では特
殊な相関しか取り出せないので意味ある相関を見逃しや
すく、３では出力を人間が見てルールを見い出せない。

【０００６】以上のように、従来２項以上の数値属性を
有するデータ間の相関を見い出す手法に有効なものはな
く、真偽をとる属性間のデータマイニングの手法を組み
合わせることができるわけでもない。よって、最初に述
べた例のような、２項以上の数値属性と真偽をとる属性
を有するデータ間の相関を見い出すために用いることが
できる手法は現在のところ提案されていない。

【０００７】

【発明が解決しようとする課題】本発明は、以上のよう
な点に鑑み、２項以上の数値属性と真偽をとる属性を有
するデータ間の相関を見い出すための手法を提案するも
のである。

【０００８】特に、（１）真偽をとる属性が真であるデ
ータの割合がある定められた値以上であって、含まれる
データ数が最大となるようなルールであるサポート最大
化ルールや、（２）最低限含まれるデータ数が定めれた
場合、真偽をとる属性が真であるデータの割合が最大と
なるようなルールであるコンフィデンス最大化ルール、
（３）取り出される領域内部と外部との分割を考えた時
に、分割前の情報量と比較した分割後の情報量の増分を
最大化するルールである最適化エントロピ・ルール、
（４）領域内外の分割を考えた時に、内外の「標準化さ
れた真偽の割合の平均からのずれ」の二乗和を最大化す
るルールである最適化インタクラスバリアンス・ルール
を満たすような範囲（領域）を導出可能とすることも目
的である。

【０００９】さらに、上記のようなデータ間の相関を実
時間内に行うことができるような手法を提供することも
目的である。

【００１０】また、データ間の相関を人間に見やすい形
で提示することも目的である。そして、多くの相関の状
態を可視化することにより、使用する人間の選択の幅を
増大させることも目的とする。

【００１１】

【課題を解決するための手段】通常、解析対象物は多く
の数値属性を有する。この中から２つの数値属性を選
び、また、１つの真偽をとる属性について、以下のステ
ップを行うことにより、上記の目的を達成するものであ
る。すなわち、 （１）２つの数値属性により平面を構成し、この平面を
メッシュ分割し、各メッシュ（バケットともいう）内の
データ数及び真偽をとる属性が真となったデータの数を
カウントする。このような平面は、各メッシュをピクセ
ルとした場合、データ数が濃淡度、真偽をとる属性が真
となるデータの数が彩度に該当するような、平面画像と
して捉えることができる。 （２）所定の条件θに従い、平面の１つの軸に凸な領域
である許容イメージを切り出し、データの相関の強い部
分を見い出す。先に述べたように、平面を画像として捉
え、平面の１つの軸に凸であるという条件を満たす部分
画像（部分領域）を許容イメージとして切り出す。 （３）切り出した許容イメージとなる領域が、先に述べ
たようなサポート最大化ルール等の条件を満たしていれ
ば、その領域をユーザに提示する。また、データベース
からその領域に含まれるデータの必要な属性を引き出す
ことも、必要に応じて行う。

【００１２】なお、切り出された領域を、そのままユー
ザに提示したり、複数の領域を切り出した場合には、そ
れを動画として可視化することにより、所望の結合ルー
ルを見い出し易くすることもできる。

【００１３】また、一旦領域を切り出した後に、それ以
外の結合ルールを見出すべく、切り出された領域につい
て、彩度を平均化し、再度切り出しステップを実行する
ことも可能である。

【００１４】最初に述べたような例の場合、流動性預金
残高の軸と、年齢の軸を設け、その平面を適当なメッシ
ュに分割する。そして、各メッシュについて該当する顧
客の数と、定期預金残高２００万円以上の顧客の数をカ
ウントする。そして、例えば顧客全体の２０％が入り且
つ定期預金残高２００万円以上である顧客の割合が最大
となるような許容イメージである領域の切り出しを行う
ことにより、コンフィデンス最大化ルールを得ることが
できる。

【００１５】また、例えば定期預金残高２００万円以上
の顧客割合が１０％で最大の顧客数を有する領域を切り
出すことにより、サポート最大化ルールを得ることがで
きる。

【００１６】以上述べた事項をまとめると、２種類の数
値属性と、１種類の真偽をとる属性を含むデータを有す
るデータベースにおいて、データ間の結合ルールを導き
出す方法であって、２種類の数値属性に対応する２つの
軸を有し且つＮ×Ｍ個のバケットに分割されている平面
の各バケットに対応して、当該バケット（座標(i,j)）
に属するデータの数ｕ(i,j)及び真偽をとる属性が真で
あるデータの数ｖ(i,j)を記憶する平面構成ステップ
と、条件θを入力するステップと、

【数１７】 を最大にするようなバケットの領域Ｓを前記平面から切
り出す領域切出ステップと、切り出された領域Ｓ内に含
まれるデータを出力するステップとを含む。

【００１７】また、入力された前記条件θとは異なる第
２の条件θ₂を入力するステップと、

【数１８】 を最大にするようなバケットの第２の領域Ｓ₂を平面か
ら切り出すステップと、

【数１９】 （領域Ｓ₂に含まれ且つ真偽をとる属性が真であるデー
タの数をＶ（Ｓ₂）、領域Ｓに含まれ且つ真偽をとる属
性が真であるデータの数をＶ（Ｓ）、領域Ｓ₂に含まれ
るデータ数をＵ（Ｓ₂）、領域Ｓに含まれるデータ数を
Ｕ（Ｓ）とする。）を第３の条件として、

【数２０】 を最大にするようなバケットの第３の領域Ｓ₃を平面か
ら切り出すステップとを含むようにすることも考えられ
る。このような処理は、最初の条件θで、初期の目的の
ルールを導き出せなかった場合に有用である。

【００１８】さらに、切り出された領域Ｓ内の各バケッ
トのｖ(i,j)／ｕ(i,j)が、平面全体のデータ数に対する
平面全体の真偽をとる属性が真であるデータ数の割合に
等しくなるようｖ(i,j)を変更するステップと、当該変
更されたｖ(i,j)を用いて、入力された条件θ₄に従い、

【数２１】 を最大にするようなバケットの第４の領域Ｓ₄を切り出
すステップとをさらに含むようにすることも考えられ
る。このようにすると、二次的な相関ルールを導き出す
ことができる。

【００１９】また、先の平面構成ステップが、複数のデ
ータから、Ｘ個のデータをランダムサンプリングするス
テップと、サンプリングされたデータを各数値属性につ
いてソートし、Ｘ・ｉ／Ｎ（ｉ＝１，２，・・Ｎ）番目
に該当する数値及びＸ・ｎ／Ｍ（ｎ＝１，２，・・Ｍ）
番目に該当する数値を記憶するステップと、記憶された
数値を基準にして、複数のデータをＮ×Ｍ個のバケット
に入れるステップとを含むようにすることも考えられ
る。このようにすると、各バケットにデータを高速に割
り振ることができる。

【００２０】ここで、

【数２２】 を評価値とし、先の領域切出ステップが、平面の各列に
おいて、少なくとも１のバケットを含み且つ評価値が最
大となるバケットの範囲を求める列内範囲導出ステップ
と、平面内の任意のバケット（座標(m,t)）の前列にあ
るもう１つのバケット（座標(m-1,l)）を含み且つ当該
前列（第ｌ列）までで最大の評価値を有する領域と、列
内範囲導出ステップにより導出される、前記任意のバケ
ット（座標(m,t)）及び前記もう１つのバケットと同一
行であって前記任意のバケットと同一列にあるバケット
（座標(m,l)）を含む評価値が最大となる範囲とを加え
た領域を加算領域とする時、各前記任意のバケットに対
し、それ自身及び当該任意のバケットを含む加算領域全
体として評価値を最大化する前記もう１つのバケットを
検出し、当該加算領域の評価値と共に記憶する検出記憶
ステップと、平面全体で加算領域の評価値が最大となる
前記任意のバケットを検出し、検出記憶ステップで検出
された前記もう１つのバケットを用いて、領域Ｓを導き
出すステップとを含むようにすることができる。

【００２１】また、切り出されるべき領域に含まれる最
低限のデータ数である最小サポート数Ｕminを入力する
ステップと、切り出された領域Ｓに含まれるデータ数Ｕ
（Ｓ）と最小サポート数Ｕminと比較するステップと、
この比較の結果、Ｕmin≒Ｕ（Ｓ）であれば、当該領域
Ｓを切り出されるべき領域として出力するステップと、
前記比較の結果、Ｕmim＞Ｕ（Ｓ）又はＵmim＜Ｕ（Ｓ）
の場合には、新たな条件θ₅にて、先の領域切出ステッ
プを実施するステップとを含むようにすることが考えれ
る。これにより、コンフィデンス最大化ルールを導出す
ることができる。

【００２２】さらに、切り出されるべき領域における真
偽をとる属性が真であるデータの数の割合minconfを入
力するステップと、切り出された領域Ｓが、minconf≒
Ｖ（Ｓ）／Ｕ（Ｓ）（Ｕ（Ｓ）は領域Ｓに含まれるデー
タ数、Ｖ（Ｓ）は領域Ｓに含まれ且つ真偽をとる属性が
真であるデータの数）である場合には、当該領域Ｓを出
力するステップと、mimconf＜Ｖ（Ｓ）／Ｕ（Ｓ）又はm
inconf＞Ｖ（Ｓ）／Ｕ（Ｓ）である場合には、新たな条
件θ₆にて領域切出ステップを実施するステップとを含
むようにすることも考えられる。これによりサポート最
大化ルールを導出することができる。

【００２３】ここで、切り出された前記領域Ｓに対し、

【数２３】 （Ｕsumは平面全体のデータ数、Ｖsumは平面全体に含ま
れる真偽をとる属性が真のデータの数）を計算し、その
値を領域Ｓに対応して記憶するエントロピ計算ステップ
と、条件を変更して先の領域切出ステップとエントロピ
計算ステップを実行するステップと、ｆ（Ｕ（Ｓ），Ｖ
（Ｓ））を最大化する領域Ｓを出力するステップとを含
むようにすれば、最適化エントロピ領域を見つけること
ができる。

【００２４】また、切り出された前記領域Ｓに対し、

【数２４】 を計算し、その値を領域に対応して記憶するインタクラ
スバリアンス計算ステップと、条件を変更して先の領域
切出ステップとインタクラスバリアンス計算ステップと
を実行するステップと、ｆ（Ｕ（Ｓ），Ｖ（Ｓ））を最
大化する領域Ｓを出力するステップとを含むようにする
ことも考えられる。これにより、最適化インタクラスバ
リアンス領域を切り出すことができる。

【００２５】以下の説明を理解すれは、上述の方法を実
施するような装置を作成すること、またこのような方法
をコンピュータに実施させるプログラムを格納した記憶
装置又は記憶媒体を作成することは容易に実施できるで
あろう。

【００２６】

【発明の実施の形態】まず、本発明の各ステップがどの
ように実施されるかを示す。 （１）平面構成ステップ 図１に、平面構成ステップのフローを示す。ステップ１
００にて処理が開始し、まずデータ集合Ｐからデータの
ランダムサンプリングを行う（ステップ１１０）。そし
て、サンプリングされたデータｐi（ｘi，ｙi）（ｘi，
ｙiはデータの２つの数値属性の値を示す。）のｘi，ｙ
iごとにソートを行う（ステップ１２０）。この時、２
つの数値属性の各々に対応するように２軸を有する平面
を考え、その平面を各軸ごとにＮ個のバケットに分割す
る。すなわち、平面上にはＮ²個のバケットが存在する
こととなる。そして、ｘi，ｙiごとに、ｉ・Ｘ／Ｎ（Ｉ
＝１，２，．．．Ｎ−１）番目の値を見つけ出す（ステ
ップ１３０）。Ｘはサンプリングされたデータの数であ
る。このようにすると、平面上の各列及び各行に属する
データの数は一致する。そして、ｘi，ｙiごとのｉ・Ｘ
／Ｎ（Ｉ＝１，２，．．．Ｎ−１）番目の値を用いる
と、各バケットの境界数値が分かるので、それを用いて
各バケット（座標(i,j)）に入るデータｐiの数ｕ(i,j)
と、真偽をとる属性が真であるデータの数ｖ(i,j)を、
各バケットごとにカウントする（ステップ１４０）。各
バケットごとに、ｕ(i,j)とｖ(i,j)を記憶する（ステッ
プ１５０）。言い換えると、ｕ(i,j)行列とｖ(i,j)行列
が生成されたということができる。

【００２７】上述のようにランダムサンプリングを行う
のは、全てのデータをソートしていると時間がかかるか
らである。但し、ソートしてもよい場合もある。また、
ランダムサンプリングで取り出されるデータの数は、３
０Ｎから５０Ｎぐらいが好ましい。また、２軸ともＮ個
に分割する例を示したが、異なる数に分割することも可
能である。典型的な例で、Ｎは１００ぐらいである。

【００２８】以上述べたのは一例であって、他の方法を
用いてもよい。例えば、各バケットの境界数値について
は予め定めた値を用いても良い。また、データ値に対し
て均等に分割することも、また対数的に分割することも
可能である。

【００２９】また、後の処理のため以下のような処理
（図２）を行っておくと、さらに全体の処理が高速化さ
れる。すなわち、ｕ(i,j)とｖ(i,j)の行数（Ｎ_y）と列
数（Ｎ_x）を調べる（ステップ２１０）。そして、先に
求めたｕ(i,j)とｖ(i,j)を用いて、新たに以下のような
ｕ'(i,j)とｖ'(i,j)という行列を作成する（ステップ２
２０）。

【数２５】

【数２６】

【００３０】このｕ'(i,j)とｖ'(i,j)は、後々数多く計
算することとなる目的関数、

【数２７】 の和計算を以下のように簡単化するために用意する。

【数２８】

【００３１】さらに、

【数２９】

【数３０】 も後によく用いるので用意する。

【００３２】以上のような準備をすれば、以下の領域切
り出しステップが高速になる。なお、上述のように作成
された平面は、平面"画像"と考えることもできるので、
イメージという文言を用いる場合がある。同様に、バケ
ットはピクセルということもある。

【００３３】（２）領域切り出しステップ このステップにおいては許容イメージである領域を先に
作成した平面（平面画像）から切り出すものである。こ
の許容イメージは、先に述べたように１つの軸方向に凸
であるイメージを言う。より正確に言うと、Ｘ軸方向へ
単調な２本の曲線で囲まれる連結イメージを言う。この
ことは、図３に例を示す。左には、幅１のＹ軸方向に伸
びる帯で切ると必ず連結している例を示しており、この
ようなイメージを許容イメージという。また、右には、
先の帯で切ると連結していない例が示されており、この
ようなイメージを含めて切り出そうとすると、その問題
はＮＰ困難となってしまう。

【００３４】このような許容イメージに問題を限定する
と、Ｙ軸方向に伸びる帯は必ず連結しているので、ダイ
ナミックプログラミングを用いて、それらを順々に連結
していけばよい。但し、もう１つのパラメータを指定す
る必要がある。例えば、濃淡のみの画像の場合にはピク
セル数（バケット数）でもよい。例えばユーザにピクセ
ル数を指定させ、そのピクセル数で且つ濃淡度の総和が
最大になる許容イメージを取り出すことができる。

【００３５】全体の許容イメージの連結性は、以下の事
項を考えると分かる。すなわち、ｋ個のピクセル（バケ
ット）を含み、ｍ列より左のピクセルからなり、（ｍ，
ｔ）の位置を含むイメージ（図４参照のこと）を考え、
この時に濃淡値の総和をｆ（ｋ，ｍ，ｔ）とすると、こ
れは以下の数式を満たすものである。

【数３１】

【００３６】ここで、ＩはＸ軸上ｍ列目の連続区間（範
囲）であり、ｔ，ｌを含む。ｑ(i,j)は、座標(i,j)の濃
淡度を示す。また、ｆ（ｋ−｜Ｉ｜，ｍ−１，ｌ）を計
算する時に用いたＸ軸上ｍ−１列目の連続区間（範囲）
はｌを含むので、Ｉと連結している。従って、帰納法よ
りｆ（ｋ，ｍ，ｔ）を求めるまでに用いた連続区間全体
は連結していることが保証されている。

【００３７】このようにすると、Ｏ（Ｎ⁶）のオーダー
で計算が可能となり、Ｎ²＝ｎ（ｎはピクセル数）とす
るとＯ（ｎ³）となり、実時間で計算可能となる。

【００３８】以上濃淡のみの画像においてピクセル数
（バケット数）を特定する場合の例を説明したが、本発
明では濃淡のみではないので、他の方法を用いる。すな
わち、図５に示すような、横軸が切り出される領域Ｓに
含まれるデータ数Ｕ（Ｓ）、縦軸が切り出される領域Ｓ
に含まれ且つ真偽をとる属性が真であるデータの数Ｖ
（Ｓ）であるような平面を考える。データ数と真偽をと
る属性が真であるデータの数の組み合わせは多数存在す
るので、この平面には多数の点が存在することになる
が、この点のうち、凸包を構成する点を特に用いる。す
なわち、この凸包を構成する点をつなぐことにより曲線
を構成し、この曲線に対し傾きθを有する直線を上から
下ろして行き、最初にこの曲線と接する点を求め、この
時のイメージを出力するという方法を用いる。この時の
許容イメージをフォーカス・イメージ（focused imag
e）という。フォーカス・イメージを図５では黒丸で示
している。また、直線を下ろしていくような方法をハン
ドプローブという。このように、本発明では傾きθを入
力するような方法を用いる。

【００３９】このように凸包上の点のみ取り扱うのは、
コンフィデンス最大化ルール、サポート最大化ルール
は、凸包上に必ず存在するわけではないが、近似解とし
ては十分な点を出力することができ、また最適化エント
ロピ・ルール及び最適化インタクラスバリアンス・ルー
ルについては、この凸包上に必ず存在するからである。
もし、コンフィデンス最大化ルール及びサポート最大化
ルールの厳密解を解くとすると、実時間には計算が終了
しないので、近似解であっても十分に有効な結果を計算
できる。

【００４０】上記のように傾きθの直線を下ろしていく
ということは、直線ｙ＝θｘ＋ＱのＹ切片であるＱを減
少させることであり、言いかえれば、Ｑ＝Ｖ（Ｓ）−θ
Ｕ（Ｓ）を最大にするＵ（Ｓ）をＸ座標に有する点を求
める問題となる。よって、

【数３２】 と変形される。

【００４１】では、この数３２をどのように解くかを考
える。基本的には先に述べたダイナミック・プログラミ
ングを用いた手法を用いる。まず、ｍ列目より左のバケ
ットからなり、（ｍ，ｔ）の位置のバケットを含む領域
を考え、この中で目的関数である数２７を最大化したも
のをｆ（ｍ，ｔ）とすると、以下の条件を満たす。すな
わち、

【数３３】 この数３３のＡは、ｔ，ｌを含む連続区間（範囲）全体
で数３３のＢを最大化する連続区間（範囲）Ｉを見つけ
ることを意味する。

【００４２】このＩをｃｏｖｅｒ（ｔ，ｌ）と記述する
こととする。いま、ｔ≦ｌを仮定すると、次の定義され
るｌｏｗ（ｔ），ｈｉｇｈ（ｌ）を用いれば、

【数３４】 となる。但し、ｌｏｗ（ｔ）は連続区間［ｉ，ｔ］全体
で数３３のＢが最大となるｉであり、ｈｉｇｈ（ｌ）は
連続区間［ｌ，ｊ］全体で数３３のＢが最大となるｊを
言う。

【００４３】このｌｏｗ（ｔ）やｈｉｇｈ（ｌ）はダイ
ナミック・プログラミング中では何度も用いられるの
で、ｌｏｗ（ｔ）やｈｉｇｈ（ｌ）を高速に求めること
ができれば有効である。このため、連続区間［ｉ，ｊ］
中の数３３のＢが要素Ｋ（ｉ，ｊ）に入る行列Ｋを作
る。但し、ｉ＞ｊの場合にはＫ（ｉ，ｊ）＝（ｉ−ｊ）
ｘ（ｘは十分、その絶対値が大きい負の数。例えば、ｕ
（i,j)を全体について加算した値より絶対値が大きいな
らば十分である。）としておく。すると行番号ｌにおい
て最大値を有する列の列番号がｈｉｇｈ（ｌ）となる。
よって、すべてのｌ∈［１，Ｎ］についてｈｉｇｈ
（ｌ）を求める問題は、Ｋの各行の最大値の列番号を求
める問題となる。このような計算は、Ｏ（Ｎ）の計算量
で行える。

【００４４】最大値の列番号を求める場合に最大値かど
うかを判断するための行列の要素の比較を行う。この比
較は、先に数２５及び数２６にて求めたｕ'及びｖ'を用
いると簡単に済む。

【００４５】このＫで各行の最大値に注目すると、行番
号が大きくなるにつれて最大値の列番号は単調に増加す
る。但し、同じ行に最大値が複数個ある時には、左端の
みを考える。このような行列を「単調な行列」と呼ぶ。
証明は省略するがこの行列Ｋは「完全単調な行列」（任
意の部分行列が単調行列であるような行列。）でもあ
る。Ｋの一例を図６に示し、斜線部が各行の最大値であ
る。単調な行列の全ての行の最大値を有する列番号を計
算するにはＯ（ＮｌｏｇＮ）の計算量が必要である。こ
の完全単調な行列の各行の最大値の列番号を求めるアル
ゴリズムは周知であり、例えば、「計算幾何学」浅野哲
夫著，朝倉書店，１９９０年９月の第４章「計算幾何学
の基本的技法」に記載されている。

【００４６】同様にしてｌｏｗ（ｔ）を計算する場合に
は、連続区間［ｉ，ｊ］中の数３３のＢが要素Ｌ（ｊ，
ｉ）に入る行列Ｌを作り、行番号ｔにおける最大値を有
する列の列番号を求めれば、ｌｏｗ（ｔ）になる。今度
は上三角部分（ｉ＞ｊ）を−∞とする。このような行列
も完全単調な行列である。

【００４７】このようにして求めたｌｏｗ（ｔ）及びｈ
ｉｇｈ（ｌ）を用いれば、ｃｏｖｅｒ（ｔ，ｌ）が求ま
り、数３３の変形である以下の式が計算可能となる。

【数３５】

【００４８】ｆ（ｍ，ｔ）を最大にするような、イメー
ジを見い出すには、ｆ（ｍ，ｔ）の計算をＸ軸に垂直な
帯について順に行い、その帯を記憶しておき、それらを
連結すれば求まる。

【００４９】さらに高速化するには、

【数３６】 を要素として有する行列Ｍを作り、行番号ｔの最大値が
ｆ（ｍ，ｔ）となる。Ｍは先に説明した完全単調な行列
であり、すべてのｔについてｆ（ｍ，ｔ）はＯ（Ｎ）で
計算することができる。よって、すべてのｍについてｆ
（ｍ，ｔ）を計算するには、Ｏ（Ｎ²）の計算量が必要
となる。

【００５０】以上詳細を述べたが、必要なステップを以
下に示しておく。 （１）全てのＸ軸に垂直な帯についてｌｏｗ（ｔ），ｈ
ｉｇｈ（ｌ）を計算しておく。 （２）ｌｏｗ（ｔ），ｈｉｇｈ（ｌ）によりｃｏｖｅｒ
（ｔ，ｌ）が求まるので、数３６を要素とする行列Ｍを
計算する。 （３）行列Ｍの各行の最大値を求め、その値をｆ（ｍ，
ｔ）として記憶する。 （４）イメージ全体を把握するために、行列Ｍの各行の
列番号ｌをｓ（ｍ，ｔ）に入力する。 （５）ｆ（ｍ，ｔ）を最大にするｍ，ｔを求め、（４）
で作ったｓ（ｍ，ｔ）及びｓ（ｍ，ｔ）に記憶されてい
るｌを用いて前列のｌｏｗ（ｔ），ｈｉｇｈ（ｌ）でも
って、イメージを把握する。

【００５１】このステップを図７及び図８に示す。ステ
ップ６１０で開始した処理は、ステップ６２０において
ｍ＝１の初期化を行う。そしてｍ＝Ｎx＋１であるかを
判断する（ステップ６３０）。これはループをＮx回繰
り返すためであり、Ｎxはｕ(i,j)とｖ(i,j)の列数であ
る。

【００５２】この後に、

【数３７】 を計算しておき、この行列の各行の最大値を求め、その
列番号ｊをｈｉｇｈ（ｍ，ｉ）とする（ステップ６４
０）。これにより、前記平面（平面画像）のｍ列目のｈ
ｉｇｈ（ｉ）が求まった。

【００５３】また、

【数３８】 を計算しておき、この行列の各行の最大値を求め、その
列番号ｊをｌｏｗ（ｍ，ｉ）＝ｊとする（ステップ６５
０）。これにより、前記平面（平面画像）のｍ列目のｌ
ｏｗ（ｉ）が求まった。

【００５４】その後にｍを１インクメントして（ステッ
プ６６０）、ステップ６３０に戻る。このように、まず
ｌｏｗとｈｉｇｈを最初にすべて計算しておく。図８の
計算を実行するごとに必要なｌｏｗとｈｉｇｈを計算す
るようにしてもよいが、この例のように一度に計算して
しまってもよい。上述のように一度に計算した後に処理
はＸを介して図８に進む。

【００５５】図８においてＸから、ｆ（ｍ，ｔ）を計算
する。まず、図４のような前記平面の一番左の列につい
て処理する。すなわち、

【数３９】 をｔ＝１からＮyについて計算する（ステップ７１
０）。Ｎyはｕ(i,j)とｖ(i,j)の行数である。このよう
にすると、数３６の第１項の初期値となるものが計算さ
れたこととなる。

【００５６】また、ｓ（１，ｔ）＝−１としておく、こ
れは、最初の列であるから、これ以上前の列には連結が
あり得ないことを明示するためである。

【００５７】そして、ｍ＝２以降の値を計算するため
に、ｍ＝２とし（ステップ７２０）、以下のループをＮ
x−１回まわすため、ｍ＝Ｎx＋１かどうか判断する（ス
テップ７３０）。もし、ｍ＝Ｎx＋１でなければ、ｆ
（ｍ−１，ｉ）（１≦ｉ≦Ｎ_y）に負の値が一つでもあ
る場合には、ｔ＝１からＮ_yまで、

【数４０】 を計算する（ステップ７４２）。ここで、ｃｏｖｅｒ_m
（ｔ，ｔ）は、ｍ列目のｃｏｖｅｒ（ｔ，ｔ）の意味で
ある。そして、

【数４１】 この行列Ｍの各行の最大値の列番号を求める（ステップ
７４４）。但し、その列ｉの最大値とｆ'（ｍ，ｉ）と
比較して大きい方をｆ（ｍ，ｉ）とする。そして、ｓ
（ｍ，ｔ）には、ｆ'（ｍ，ｔ）がＭのｔ行の最大値よ
りも小さいときにはｌを、そうでなければ−１を入れ
る。これは、前列までの連結を保存した方が切り出され
る領域の目的関数の値が大きくなるか、それとも前列ま
での連結を放棄した方が目的関数の値が大きくなるかと
いう判断をしているのである。

【００５８】このようにｓ（ｍ，ｔ）は連結状態を保存
するためにあるので、ある（ｍ，ｔ）が決まれば、ｓ
（ｍ，ｔ）を手繰って遡り、領域がどのように連結する
ものかを後にみることができる。

【００５９】この後に、ｍを１インクリメントし（ステ
ップ７５０）、ステップ７３０に戻る。繰り返しが全て
終われば、ｆ（ｍ，ｔ）を最大とするｍ，ｔが求まる。
ｆ（ｍ，ｔ）を作りながら、常に最大となるｍ，ｔを保
持しておき、新たに作成された部分につき保持している
ｍ，ｔより大きな点を見い出した場合には更新するよう
にしていけばよい。このｍ，ｔを用いて、ｓ（ｍ，ｔ）
から、前列のｌが求まる。このｌとｔのうち小さい方を
ｌｏｗに大きい方をｈｉｇｈに入力する。例えば、ｔの
方が小さければ、ｌｏｗ（ｍ，ｔ），ｈｉｇｈ（ｍ，
ｌ）が求まる。また、ｓ（ｍ−１，ｌ）から、さらに前
列のｌ'が求まるので、ｌｏｗ（ｍ−１，ｌ），ｈｉｇ
ｈ（ｍ−１，ｌ'）を求める。（ここでは、ｌの方がｌ'
より小さい。）これを繰り返していくと、イメージＳの
全体が分かる（ステップ７６０）。あるｓ（ｍ，ｔ）に
て−１が得られれば、その領域は終了する。これにて、
傾きθを入力した場合に、そのθに対応する許容イメー
ジＳを得ることができたので、処理を終了する（ステッ
プ７７０）。

【００６０】以上説明したように、傾きθに対応する許
容イメージを得ることができた。この条件θは、ユーザ
が入力するようにしてもよいし、また例えばサポート最
大化ルールを求めるためにシステムにより設定された条
件であってもよい。

【００６１】（３）出力ステップ 以上のように求まった許容イメージたる領域Ｓは、前記
平面のどの部分を占めているかは、先のステップにより
わかっているので、そのイメージＳに属するデータを取
り出すことになる。通常各データは、真偽をとる属性及
び数値属性のみならず、他の属性も有しているから、例
えばダイレクトメールを送るのであれば、住所氏名とい
った属性を取り出すようになる。ここまでくると、取り
出すべきデータは特定されているから、通常のデータベ
ースの検索に過ぎないので、これ以上詳しく述べない。
当然、一旦フォーカス・イメージをその外形がよくわか
るようにして、ユーザに提示するようにしてもよい。

【００６２】以上のような各ステップを実施すれば、あ
る条件θに対する、データ間結合ルールの１つを求める
ことができる。しかし、この条件θをどのように設定す
るかということは、１つの問題である。通常、ある条件
θ１つでは、問題の解決にならない場合が多い。以上の
各ステップ、特に（１）平面構成ステップと（２）領域
切り出しステップとをエンジンとして用い、どのように
先に述べた４つの一般的なルール及び他のルール等を導
き出すかを以下に示す。

【００６３】Ａ．ある区間に存在するフォーカス・イメ
ージを求める場合 まず、幾つかのθに対応する許容イメージ（ここではフ
ォーカス・イメージ）たる領域Ｓを連続的に示し、動画
を作成することにより、切り出されるイメージの大きさ
及び形状をユーザの判断により決定させる場合を考え
る。

【００６４】この処理を図９に示す。ステップ８００に
て開始された処理は、まずθ１を入力することにより、
上述したプロセスにてフォーカス・イメージＳ１を見つ
け出す（ステップ８１０）。また、ユーザにθ２を入力
させ、同様にフォーカス・イメージＳ２を見つけ出す
（ステップ８２０）。このようにして２つのフォーカス
・イメージが求まると、それぞれに含まれるデータ数Ｕ
（Ｓ1），Ｕ（Ｓ2）及び真偽をとる属性が真であるデー
タの数Ｖ（Ｓ1），Ｖ（Ｓ2）とを用いて、その中間にあ
る、新たな傾きθ３を計算する（ステップ８３０）。

【００６５】このように新たなθ３が求まれば、さらに
このθ３に対応するフォーカス・イメージＳ３を求める
ことができる（ステップ８４０）。ここで、計算された
Ｓ３が既に求まっていれば、区間（θ１，θ２）にはこ
れ以上のフォーカス・イメージは存在しない。よって、
処理が終了する（ステップ８８０）。しかし、発見済み
でなければ、θ２の代わりにθ３を用いて、ステップ８
３０以降を実行する（ステップ８６０）。すなわち、区
間（θ１，θ３）の間にあるフォーカス・イメージを見
つけ出す。この場合、次々に中間の値を計算していくよ
うにすることも可能である。また、ある程度の個数フォ
ーカス・イメージが求まったところで計算を取り止める
こともできる。さらに、もう１つ残った区間（θ３，θ
２）についてフォーカス・イメージを計算するために、
θ３，θ２についてステップ８３０以降を実行する（ス
テップ８７０）。この場合も、この区間内に存在してい
るフォーカス・イメージを全て見つけ出すようにしても
よいし、所定の個数見つけ出したところで処理を終了し
てもよい。

【００６６】このようにして、１つ又は複数のフォーカ
ス・イメージを見つけ出すことができた。このように求
まった複数のフォーカス・イメージを図１０のように
（ａ），（ｂ），（ｃ）と連続してユーザに提示するよ
うなことも可能である。この図１０の各々の斜線部分が
切り出された領域（フォーカス・イメージ）である。

【００６７】Ｂ．コンフィデンス最大化ルールの場合
（図１１及び図１２） この場合には、ルールの定義より最小限度のサポートmi
nsup（全体のデータ数に対する包含されるデータ数の割
合）を入力することとなる（ステップ９１０）。ここ
で、Ｕmin＝Ｕsum*minsupを計算しておく。ここで図５
をみてみると、最小限度サポートと記された縦の点線が
この値に対応する。そして、θ＝Ｖsum／Ｕsumとしてフ
ォーカス・イメージＳ1を求める（ステップ９２０）。
このＳ1に含まれるデータ数Ｕ（Ｓ1）の値により３つの
場合に分けられる（ステップ９３０）。すなわち、
（１）Ｕ（Ｓ1）≒Ｕminであれば、当然Ｓ1が解として
出力され、処理は終了する（ステップ９９０）。（２）
Ｕ（Ｓ1）＜Ｕminであれば、θ＝０としてフォーカス・
イメージＳ2を計算する（ステップ９４０）。この結
果、Ｕ（Ｓ2)≒Ｕminであれば（ステップ９５０）、当
然Ｓ2が解として出力され、処理は終了する。ここで、
Ｓ1＝Ｓ2はminsupが１より小さければあり得ない。但
し、Ｓ1＝Ｓ2であれば解はないので、解なしを出力す
る。そうでなければ、ＸＸにて図１２に移動する。
（３）Ｕ（Ｓ1）＞Ｕminであれば、θ＝１としてフォー
カス・イメージＳ2を計算する（ステップ９６０）。Ｓ1
＝Ｓ2であるならば、Ｓ1より高いコンフィデンスを有す
るフォーカス・ポイントは存在しないので、Ｓ1（当然
Ｓ2も同様）を最良解として出力し、処理を終了する
（ステップ９７０）。同様に、Ｕ（Ｓ2）≒Ｕminであれ
ば、Ｓ2を出力して処理を終了する。ステップ９７０に
て、先に示した条件を満たさないとされた場合には、Ｘ
Ｘを介して図１２に移動する。

【００６８】図１２では、ＸＸから始まり、新たな条件
θを求め、このθに対するフォーカス・イメージＳを計
算する（ステップ１４００）。このθは θ＝（Ｖ（Ｓ2）ーＶ（Ｓ1））／（Ｕ（Ｓ2）−Ｕ（Ｓ
1）） にて計算される。そして、Ｓ1＝Ｓ又はＳ2＝Ｓであるな
らば、（Ｓ1，Ｓ2）の間にはこれ以上フォーカス・イメ
ージは存在しないので、コンフィデンスの高いＳ2が最
良解として出力され、処理を終了する（ステップ１４１
０）。また、Ｕ（Ｓ）≒Ｕminであるならば、Ｓを出力
し、処理を終了する。

【００６９】ところが、Ｕ（Ｓ）＜Ｕminであると（ス
テップ１４２０）、まだ処理が必要なので、Ｓ1＝Ｓと
して（ステップ１４３０）、ステップ１４００に戻る。
同様に、Ｕ（Ｓ）＞Ｕminであるならば、Ｓ2＝Ｓとして
（ステップ１４４０）、ステップ１４００に戻る。

【００７０】これを繰り返すことにより解が見つけられ
る。図５を参照すると、先に説明した最小限度のサポー
トの右側、濃く塗られた部分に解の存在する範囲があ
る。そして、この図５の場合には、凸包の内部の白丸の
点が厳密解となるが、本発明ではハンド・プローブにて
得られた近似解が出力される。見つけられた解は、ユー
ザに提示されるようにしてもよいし、そのフォーカス・
イメージに属するデータの必要な属性を出力するように
してもよい。

【００７１】Ｃ．サポート最大化ルールの場合（図１
３，図１４） このルールの場合、定義より、最小限度のコンフィデン
ス、すなわち含まれるデータ数に対する真偽をとる属性
が真である割合を入力する（ステップ１１１０）。図５
の場合、最小限度のコンフィデンスと示され、原点から
引かれた点線がこれに該当する。次に、minconf≦Ｖsum
／Ｕsumであるかを判断する（ステップ１１２０）。こ
の条件に合致する場合には、全ての凸包上の点は条件に
合致するので、θ＝０としてフォーカス・イメージを求
め、それを出力する。（ステップ１１３０）。これに対
し、ステップ１１２０でminconf＞Ｖsum／Ｕsumである
場合には、θ＝Ｖsum／Ｕsumとしてフォーカス・イメー
ジＳ1を求める（ステップ１１４０）。ここで、３つの
場合が考えられる（ステップ１１５０）。すなわち、
（１）minconf≒Ｖ（Ｓ）／Ｕ（Ｓ1）である場合には、
Ｓ1を出力して処理を終了する（ステップ１１９０）。
（２）minconf＜Ｖ（Ｓ1）／Ｕ（Ｓ1）である場合に
は、θ＝０のフォーカス・イメージＳ2を求める（ステ
ップ１１６０）。このＳ2は、Ｖ（Ｓ2）＝Ｖsumであ
り、且つＵ（Ｓ2）＝Ｕsumであるから、minconf≦Ｖ
（Ｓ2）／Ｕ（Ｓ2）とはなり得ない。同様に、Ｓ1＝Ｓ2
はあり得ない。よって、図１４への移動するためにＹに
移る（ステップ１１６０）。（３）minconf＞Ｖ（Ｓ1）
／Ｕ（Ｓ1）である場合には、θ＝minconfのフォーカス
・イメージＳ2を求める（ステップ１１７０）。このＳ2
に対し、minconf＝Ｖ（Ｓ2）／Ｕ（Ｓ2）が成り立て
ば、Ｓ2は厳密解であるから、これを出力して処理を終
了する。また、minconf＜Ｖ（Ｓ2）／Ｕ（Ｓ2）であれ
ば、解は存在しないので、解なしを返して処理を終了す
る。一方、minconf＞Ｖ（Ｓ2）／Ｕ（Ｓ2）であるなら
ば、図１４の処理に移行するためにＹに進む。

【００７２】図１４では、Ｙから処理が開始され、θ＝
（Ｖ（Ｓ2）−Ｖ（Ｓ1））／（Ｕ（Ｓ2）−Ｕ（Ｓ1））
としてフォーカス・イメージＳを求める（ステップ１２
００）。この求められたフォーカス・イメージＳに対
し、（１）minconf≒Ｖ（Ｓ）／Ｕ（Ｓ）が成立する場
合には、このＳを出力して処理を終了する（ステップ１
２１０）。また、Ｓ1＝Ｓ若しくはＳ2＝Ｓである場合に
は、これ以上Ｓ1とＳ2の間には解は無いので、Ｓ1を最
良解として出力し、処理を終了する（ステップ１２１
０）。これに対し、minconf＜Ｖ（Ｓ）／Ｕ（Ｓ）であ
る場合には（ステップ１２２０）、Ｓ1＝Ｓとしてステ
ップ１２００に戻る（ステップ１２３０）。また、minc
onf＞Ｖ（Ｓ）／Ｕ（Ｓ）である場合には、Ｓ2＝Ｓとし
てステップ１２００に戻る（ステップ１２４０）。

【００７３】以上のようにして、サポート最大化ルール
が求められる。もう一度図５に戻ると、先に説明した最
小限度のコンフィデンスとして示した点線より上の濃く
塗られた範囲に解が存在する。そして、この例では凸包
内の白丸の点が厳密解であるが、このように凸包内部の
点は見つけ出すのに膨大な計算量を必要とするので、凸
包上の点でサポートを最大にする近似解を出力するよう
にしている。先に述べたように、見出された近似解又は
厳密解は、ユーザに提示してもよいし、フォーカス・イ
メージ内に含まれるデータの必要な属性値を出力するよ
うにしてもよい。

【００７４】Ｄ．最適化エントロピ・ルールの場合 最適化エントロピ・ルールとは、領域の内部と外部との
分割を考えた時、分割前の情報量と比較した分割後の情
報量の増分を最大化するルールである。よって、切り出
された領域と平面全体のエントロピのゲイン（以下の
式）が最大となる領域を発見すればよい。

【数４２】 このｘはＵ（Ｓ）、ｙはＶ（Ｓ）、ａはＵsum、ｂはＶs
umである。このような条件においても、解は凸包上に存
在することが分かったので、上述のステップを用いるこ
とができる。よって、θを変化させ、数４２を最大化す
るフォーカス・イメージを求めればよい。

【００７５】Ｅ．最適化インタクラスバリアンス・ルー
ルの場合 先に述べたように最適化インタクラスバリアンス・ルー
ルとは、領域内外の分割を考えた時、内外の「標準化さ
れた真偽の割合の平均からのずれ」の二乗和を最大化す
るルールである。よって、切り出された領域と平面全体
のインタクラスバリアンス（以下の式）が最大となる領
域を発見すればよい。

【数４３】 ｘ，ｙ，ａ，ｂは上述したものと同じである。このよう
な条件においても、解は凸包上に存在することが分かっ
たので、上述のステップを用いることができる。よっ
て、θを変化させ、数４３を最大化するフォーカス・イ
メージを求めればよい。

【００７６】Ｆ．その他 以上述べたように、Ｕ（Ｓ）とＶ（Ｓ）上の凸包上の点
に存在する又は存在すると近似できる場合には、上述し
たステップを用いれば高速にルールに該当する領域を導
き出すことができる。

【００７７】Ｇ．二次的なルールの抽出 上述のプロセスを用いて１つのルールを見い出した後
に、二次的なルールを見つけ出すことができる。すなわ
ち、切り出した１のフォーカス・イメージに属するｖ
(i,j)を除去し、ｖ(i,j)／ｕ(i,j)＝Ｖsum／Ｕsumとな
るように、ｖ(i,j)を変更し、それから新たに領域切り
出しステップを行うのである。

【００７８】以上、本発明における処理のプロセスを説
明した。このような処理プロセスは、コンピュータ・プ
ログラムによって実現し、実行するようにしてもよい。
例えば、図１５のような通常のコンピュータ・システム
において実行できるようなプログラムにすることもでき
る。処理プログラムは、ＨＤＤ１０５０に格納され、実
行時にはメインメモリ１０２０にロードされ、ＣＰＵ１
０１０によって処理される。また、ＨＤＤ１０５０はデ
ータベースをも含んでおり、処理プログラムはそのデー
タベースに対するアクセスを行う。最初の平面やフォー
カス・イメージ（図１７）は、表示装置１０６０によっ
てユーザに提示される。ユーザは、入力装置１０７０に
てフォーカス・イメージの選択や、データ出力の命令を
入力する。このような入力装置には、キーボードやマウ
ス、ポインティング・デバイスやディジタイザを含む。
さらに、出力結果を補助記憶装置であるＦＤＤ１０３０
のフロッピー・ディスクに記憶したり、また新たなデー
タをＦＤＤ１０３０から入力することもできる。さら
に、ＣＤ−ＲＯＭドライブ１０４０を用いて、データを
入力することもできる。

【００７９】さらに、本発明の処理プロセスを実現した
コンピュータ・プログラムは、フロッピー・ディスクや
ＣＤ−ＲＯＭといった記憶媒体に記憶して、持ち運ぶこ
とができる。この場合、通常のデータベース検索プログ
ラムのデータ取り出し部分や、表示装置１０６０に表示
するだけの処理を行うプログラムは、すでにＨＤＤ１０
５０に記憶されている場合もある。よって、それ以外の
部分が、上記のような記憶媒体にて流通することは通常
行われる事項である。

【００８０】また、本発明の処理を専用に行うような装
置を設けてもよい。例えば、図１６のような装置が考え
られる。平面構成部１３１０は、データベース１３００
及び切出部１３２０に接続されており、制御部１３４０
からの命令を受付ける。また、切出部１３２０は、出力
部１３３０及び表示装置１３５０に接続されており、制
御部１３４０からの命令を受付ける。また、切出部１１
３０はデータベースにも接続を有している。制御部１３
４０は、入力部１３６０に接続され、入力部１３６０に
より指示された処理の種類により平面構成部１３１０及
び切出部１３２０を制御する。

【００８１】この装置の簡単な動作を説明する。平面構
成部１３１０は、先に説明した平面構成ステップを実行
する部分である。このように平面構成部１１１０は、デ
ータベースに記憶されたデータを用いて先に示した平面
を構成し、切出部１３２０に出力する。切出部１３２０
は、制御部１３４０からの命令に従って、切り出しのた
めのパラメータであるθをセットする。セットされたθ
に従って切出部１３２０は、先に述べた切出ステップを
行い、フォーカス・イメージを切り出す。そして、表示
装置１１４０に出力し、ユーザに命令されれば、切り出
されたフォーカス・イメージ内に属するデータをデータ
ベース１３００から取り出し、出力部１３３０に引き渡
す。出力部１３３０は、適当な形式でユーザ所望のデー
タを出力する。また、ユーザは、例えば入力部１３６０
からコンフィデンス最大化ルールを解くように命じ、最
小限度のサポートを入力する。すると、制御部１３４０
は先に示した処理Ｂを行うように、条件θを設定し、切
出部１３２０に出力する。そして、命じられたコンフィ
デンス最大化ルールに合致するような領域を解くべく、
条件θを変化させる等の処理を行う。先に述べたサポー
ト最大化ルール（処理Ｃ）や、最適化エントロピ・ルー
ル（処理Ｄ）、最適化インタクラスバリアンス・ルール
（処理Ｅ）、その他凸包上に位置する領域を切出す処理
Ｆに適した条件θを切出部１３２０に渡す処理を制御部
１３４０は行う。ユーザは入力部１３６０から処理の種
類や、先に述べたような条件（θのみならず、mincon
f，minsupも）を入力する。また、制御部１３４０は、
上述の処理Ｇを行うために平面構成部１３１０に、切り
出したフォーカス・イメージのＶ(i,j)を除去する等の
処理を命じる。

【００８２】以上、本発明を専用の装置にする一例を示
したが、本発明はこれに限定されるものではない。例え
ば、切出部１３２０の出力は、出力制御部を介して出力
部１１６０及び表示装置１１４０に出力されるようにし
てもよいし、この場合出力制御部からデータベースを参
照してデータを取り出すようにしてもよい。

【００８３】以上は、通常データが有するＫ個の数値属
性のうち２項を選択し、それらの数値属性間の壮観を見
つける処理であったが、数２７を目的関数とし、ｎ次元
空間の領域を切り出すことができれば、ｎ次元の探索に
拡張することができる。

【００８４】

【効果】以上述べたように、２項の数値属性と真偽をと
る属性を有するデータ間の相関を見い出すことができ
た。

【００８５】（１）サポート最大化ルール、（２）コン
フィデンス最大化ルール、（３）最適化エントロピ・ル
ール、（４）最適化インタクラスバリアンス・ルールを
満たすような範囲（領域）を導出可能とすることもでき
た。

【００８６】さらに、上記のようなデータ間の相関を実
時間内に行うこともできた。

【００８７】また、データ間の相関を人間に見やすい形
で提示することもできた。

【００８８】例えば、ある割合以上で、例えばアウトド
アスポーツに興味を示す（真偽をとる属性に相当す
る）、できるだけまとまった領域に入る顧客を知ること
ができるので、その条件に合致する多くの顧客に知って
もらいたいダイレクトメールの宛て先を知るのに用いる
ことができる。（サポート最大化ルール）

【００８９】一定数以上の顧客を含む、例えば定期預金
残高２００万円以上の顧客割合が最も高いところを知る
ことができるので、顧客を絞りこみつつ、有効な宣伝活
動等を行うことができる。（コンフィデンス最大化ルー
ル）

【図面の簡単な説明】

【図１】平面構成ステップのフローを示す図である。

【図２】領域切り出しステップのための前準備のフロー
を示す図である。

【図３】許容イメージを説明するための図である。

【図４】許容イメージの連結性を説めいするための図で
ある。

【図５】Ｕ（Ｓ），Ｖ（Ｓ）平面の説明をするための図
である。

【図６】完全単調な行列の説明をするための図である。

【図７】切出ステップの一部を示すフローチャートであ
る。

【図８】切出ステップの一部を示すフローチャートであ
る。

【図９】複数のフォーカス・イメージを見つけ出す処理
のフローを示す図である。

【図１０】フォーカス・イメージの一例を示した図であ
る。

【図１１】コンフィデンス最大化ルールを導出するため
の処理の一部を示すための図である。

【図１２】コンフィデンス最大化ルールの導出するため
の処理の一部を示すための図である。

【図１３】サポート最大化ルールの導出するための処理
の一部を示すための図である。

【図１４】サポート最大化ルールの導出するための処理
の一部を示すための図である。

【図１５】通常のコンピュータ・システムで本発明を実
施した場合の装置構成の一例を示す図である。

【図１６】本発明を専用の装置で実施した場合のブロッ
ク図である。

【図１７】図１５の表示装置の表示例を示す図である。

【符号の説明】

１０１０ ＣＰＵ １０２０ メインメモリ １０３０ ＦＤＤ １０４０ ＣＤ−ＲＯＭドライブ １０５０ ＨＤＤ １０６０ 表示装置 １０７０ 入力装置 １３１０ 濃淡画像構成部 １３００ データベース １３２０ 切出部 １３５０ 表示装置 １１３０ 入力部 １３３０ 出力部 １３４０ 制御部

───────────────────────────────────────────────────── フロントページの続き (72)発明者 森本 康彦 神奈川県大和市下鶴間1623番地14 日本 アイ・ビー・エム株式会社 東京基礎研 究所内 (72)発明者 森下 真一 神奈川県大和市下鶴間1623番地14 日本 アイ・ビー・エム株式会社 東京基礎研 究所内 (72)発明者 徳山 豪 神奈川県大和市下鶴間1623番地14 日本 アイ・ビー・エム株式会社 東京基礎研 究所内 (56)参考文献 福田，森下「相関ルールの可視化につ いて」電子情報通信学会技術研究報告 （ＤＥ95−６），Ｖｏｌ．95，Ｎｏ. 81，1995（平７−５−26) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 17/30 220 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (18)

(57)【特許請求の範囲】
1. 【請求項１】少なくとも平面構成手段と、入力手段と、
   領域切出手段と、データ出力手段とを有し、２種類の数
   値属性と、１種類の真偽をとる属性を含むデータを有す
   るデータベースにおいて、 データ間の結合ルールを導き出す方法であって、前記平面構成手段が、 前記２種類の数値属性に対応する
   ２つの軸を有し且つＮ×Ｍ個のバケットに分割されてい
   る平面の各バケットに対応して、当該バケット（座標
   (i,j)）に属するデータの数ｕ(i,j)及び前記真偽をとる
   属性が真であるデータの数ｖ(i,j)を記憶する平面構成
   ステップと、前記入力手段が、 条件θを入力するステップと、前記領域切出手段が、 【数１】 を最大にするような前記バケットの領域Ｓを前記平面か
   ら切り出す領域切出ステップと、前記データ出力手段が、 切り出された前記領域Ｓ内に含
   まれるデータを出力するステップとを含むデータ間結合
   ルール導出方法。
2. 【請求項２】前記データベースは、領域切出手段に出力
   する手段をさらに有し、 前記入力手段が、 入力された前記条件θとは異なる第２
   の条件θ₂を入力し、 前記領域切出手段が、 【数２】 を最大にするような前記バケットの第２の領域Ｓ₂を前
   記平面から切り出した場合に、 前記領域切出手段に出力する手段が、 【数３】 （前記領域Ｓ₂に含まれ且つ前記真偽をとる属性が真で
   あるデータの数をＶ（Ｓ₂）、前記領域Ｓに含まれ且つ
   前記真偽をとる属性が真であるデータの数をＶ（Ｓ）、
   前記領域Ｓ₂に含まれるデータ数をＵ（Ｓ₂）、前記領域
   Ｓに含まれるデータ数をＵ（Ｓ）とする。）を、第３の
   条件として前記領域切出手段に対して出力するステップ
   と、 前記領域切出手段が、 【数４】 を最大にするような前記バケットの第３の領域Ｓ₃を前
   記平面から切り出すステップをさらに含む請求項１記載
   のデータ間結合ルール導出方法。
3. 【請求項３】前記データベースは、ｖ(i,j)を変更する
   手段と、第１の命令手段とをさらに有し、 前記ｖ(i,j)を変更する手段が、 前記切り出された領域
   Ｓ内の各バケットのｖ(i,j)／ｕ(i,j)が、前記平面全体
   のデータ数に対する前記平面全体の前記真偽をとる属性
   が真であるデータ数の割合に等しくなるようｖ(i,j)を
   変更するステップと、前記第１の命令手段が、 当該変更されたｖ(i,j)を用い
   て、入力された条件θ₄に従い、 【数５】 を最大にするような前記バケットの第４の領域Ｓ₄を切
   り出す動作をするように前記領域切出手段に命ずるステ
   ップをさらに含む請求項１記載のデータ間結合ルール導
   出方法。
4. 【請求項４】前記平面構成ステップが、前記平面構成手段が、 複数の前記データから、Ｘ個のデ
   ータをランダムサンプリングするステップと、前記平面構成手段が、 サンプリングされたデータを各前
   記数値属性についてソートし、Ｘ・ｉ／Ｎ（ｉ＝１，
   ２，・・Ｎ）番目に該当する数値及びＸ・ｎ／Ｍ（ｎ＝
   １，２，・・Ｍ）番目に該当する数値を記憶するステッ
   プと、前記平面構成手段が、 記憶された前記数値を基準にし
   て、前記複数のデータをＮ×Ｍ個の前記バケットに入れ
   るステップとを含む請求項１乃至３記載のデータ間結合
   ルール導出方法。
5. 【請求項５】 【数６】 を評価値とし、 前記領域切出ステップが、前記領域切出手段が、 前記平面の各列において、少なく
   とも１のバケットを含み且つ前記評価値が最大となるバ
   ケットの範囲を求める列内範囲導出ステップと、前記領域切出手段が、 前記平面内の任意のバケット（座
   標(m,t)）の前列にあるもう１つのバケット（座標(m-1,
   l)）を含み且つ当該前列（第ｌ列）までで最大の評価値
   を有する領域と、前記列内範囲導出ステップにより導出
   される、前記任意のバケット（座標(m,t)）及び前記も
   う１つのバケットと同一行であって前記任意のバケット
   と同一列にあるバケット（座標(m,l)）を含む評価値が
   最大となる範囲とを加えた領域を加算領域とする時、各
   前記任意のバケットに対し、それ自身及び当該任意のバ
   ケットを含む前記加算領域全体として評価値を最大化す
   る前記もう１つのバケットを検出し、当該加算領域の評
   価値と共に記憶する検出記憶ステップと、前記領域切出手段が、 前記平面全体で前記加算領域の評
   価値が最大となる前記任意のバケットを検出し、前記検
   出記憶ステップで検出された前記もう１つのバケットを
   用いて、領域Ｓを導き出すステップとを含む請求項１記
   載のデータ間結合ルール導出方法。
6. 【請求項６】前記データベースは、最小サポート数Ｕmi
   nを入力する手段と、最小サポート 数Ｕminと比較する手
   段と、領域Ｓを出力する第１の手段と、第２の命令手段
   とをさらに有し、 最小サポート数Ｕminを入力する手段は、 前記切り出さ
   れるべき領域に含まれる最低限のデータ数である最小サ
   ポート数Ｕminを入力するステップと、前記最小サポート数Ｕminと比較する手段が、 前記切り
   出された領域Ｓに含まれるデータ数Ｕ（Ｓ）と前記最小
   サポート数Ｕminと比較するステップと、領域Ｓを出力する第１の手段が、 前記比較の結果、Ｕmi
   n≒Ｕ（Ｓ）であれば、当該領域Ｓを切り出されるべき
   領域として出力するステップと、前記第２の命令手段が、前記領域切出手段に対して、 前
   記比較の結果、Ｕmim＞Ｕ（Ｓ）又はＵmim＜Ｕ（Ｓ）の
   場合には、新たな条件θ₅にて、前記領域切出ステップ
   を実施するように命ずるステップとをさらに含む請求項
   １記載のデータ間結合ルール導出方法。
7. 【請求項７】前記データベースは、データの数の割合mi
   nconfを入力する手段と、領域Ｓを出力する第２の手段
   と、第３の命令手段とをさらに有し、 前記データの数の割合minconfを入力する手段が、 切り
   出されるべき領域における前記真偽をとる属性が真であ
   るデータの数の割合minconfを入力するステップと、領域Ｓを出力する第２の手段が、 前記切り出された領域
   Ｓが、minconf≒Ｖ（Ｓ）／Ｕ（Ｓ）（Ｕ（Ｓ）は前記
   領域Ｓに含まれるデータ数、Ｖ（Ｓ）は前記領域Ｓに含
   まれ且つ前記真偽をとる属性が真であるデータの数）で
   ある場合には、当該領域Ｓを出力するステップと、前記第３の命令手段が、前記領域切出し手段に対して、
   mimconf＜Ｖ（Ｓ）／Ｕ（Ｓ）又はminconf＞Ｖ（Ｓ）／
   Ｕ（Ｓ）である場合には、新たな条件θ₆にて前記領域
   切出ステップを実施するように命ずるステップとをさら
   に含む請求項１記載のデータ間結合ルール導出方法。
8. 【請求項８】前記データベースは、エントロピ計算手段
   と、第４の命令手段と、領域Ｓを出力する第３の手段と
   をさらに有し、 前記エントロピ計算手段が、 切り出された前記領域Ｓに
   対し、 【数７】 （Ｕsumは前記平面全体のデータ数、Ｖsumは前記平面全
   体に含まれる前記真偽をとる属性が真のデータの数）を
   計算し、その値を前記領域Ｓに対応して記憶するエント
   ロピ計算ステップと、前記第４の命令手段が、前記領域切出手段と前記エント
   ロピ計算手段に対して、 条件θを変更して前記領域切出
   ステップと前記エントロピ計算ステップを実行するよう
   に命ずるステップと、前記領域Ｓを出力する第３の手段が、 ｆ（Ｕ（Ｓ），Ｖ
   （Ｓ））を最大化する領域Ｓを出力するステップとをさ
   らに含む請求項１記載のデータ間結合ルール導出方法。
9. 【請求項９】前記データベースは、インタクラスバリア
   ンス計算手段と、第５の命令手段と、領域Ｓを出力する
   第４の手段とをさらに有し、 前記インタクラスバリアンス計算手段が、 切り出された
   前記領域Ｓに対し、 【数８】 （Ｕsumは前記平面全体のデータ数、Ｖsumは前記平面全
   体に含まれる前記真偽をとる属性が真のデータの数）を
   計算し、その値を前記領域に対応して記憶するインタク
   ラスバリアンス計算ステップと、前記第５の命令手段が、前記インタクラスバリアンス計
   算手段に対して、 条件θを変更して前記領域切出ステッ
   プと前記インタクラスバリアンス計算ステップとを実行
   するように命ずるステップと、前記領域Ｓを出力する第４の手段が、 ｆ（Ｕ（Ｓ），Ｖ
   （Ｓ））を最大化する領域Ｓを出力するステップとをさ
   らに含む請求項１記載のデータ間結合ルール導出方法。
10. 【請求項１０】２種類の数値属性と、１種類の真偽をと
    る属性を含むデータを有するデータベースにおいて、 データ間の結合ルールを導き出す装置であって、 前記２種類の数値属性に対応する２つの軸を有し且つＮ
    ×Ｍ個のバケットに分割されている平面の各バケットに
    対応して、当該バケット（座標(i,j)）に属するデータ
    の数ｕ(i,j)及び前記真偽をとる属性が真であるデータ
    の数ｖ(i,j)を記憶する平面構成手段と、 条件θを入力する入力手段と、 【数９】 を最大にするような前記バケットの領域Ｓを前記平面か
    ら切り出す領域切出手段と、 切り出された前記領域Ｓ内に含まれるデータを出力する
    手段と、 を有するデータ間結合ルール導出装置。
11. 【請求項１１】前記入力手段により、前記条件θとは異
    なる第２の条件θ₂を入力し、前記領域切出手段によ
    り、前記第２の条件θ₂に対応する第２の領域Ｓ₂を前記
    平面から切り出した場合に、 【数１０】 （前記領域Ｓ₂に含まれ且つ前記真偽をとる属性が真で
    あるデータの数をＶ（Ｓ₂）、前記領域Ｓに含まれ且つ
    前記真偽をとる属性が真であるデータの数をＶ（Ｓ）、
    前記領域Ｓ₂に含まれるデータ数をＵ（Ｓ₂）、前記領域
    Ｓに含まれるデータ数をＵ（Ｓ）とする。）を第３の条
    件として前記領域切出手段に出力する手段とをさらに有
    する請求項１０記載のデータ間結合ルール導出装置。
12. 【請求項１２】前記切り出された領域Ｓ内の各バケット
    のｖ(i,j)／ｕ(i,j)が、前記平面全体のデータ数に対す
    る前記平面全体の前記真偽をとる属性が真であるデータ
    数の割合に等しくなるようｖ(i,j)を変更する手段と、 当該変更されたｖ(i,j)及び入力された条件θ₄でもっ
    て、前記領域切出手段が動作するように命令する手段と
    を有する請求項１０記載のデータ間結合ルール導出装
    置。
13. 【請求項１３】前記平面構成手段が、 複数の前記データから、Ｘ個のデータをランダムサンプ
    リングする手段と、 サンプリングされたデータを各前記数値属性についてソ
    ートし、Ｘ・ｉ／Ｎ（ｉ＝１，２，・・Ｎ）番目に該当
    する数値及びＸ・ｎ／Ｍ（ｎ＝１，２，・・Ｍ）番目に
    該当する数値を記憶する手段と、 記憶された前記数値を基準にして、前記複数のデータを
    Ｎ×Ｍ個の前記バケットに入れる手段とを含む請求項１
    ０乃至１２記載のデータ間結合ルール導出装置。
14. 【請求項１４】 【数１１】 を評価値とし、 前記領域切出手段が、 前記平面の各列において、少なくとも１のバケットを含
    み且つ前記評価値が最大となるバケットの範囲を求める
    列内範囲導出手段と、 前記平面内の任意のバケット（座標(m,t)）の前列にあ
    るもう１つのバケット（座標(m-1,l)）を含み且つ当該
    前列（第ｌ列）までで最大の評価値を有する領域と、前
    記列内範囲導出手段により導出される、前記任意のバケ
    ット（座標(m,t)）及び前記もう１つのバケットと同一
    行であって前記任意のバケットと同一列にあるバケット
    （座標(m,l)）を含む評価値が最大となる範囲とを加え
    た領域を加算領域とする時、各前記任意のバケットに対
    し、それ自身及び当該任意のバケットを含む前記加算領
    域全体として評価値を最大化する前記もう１つのバケッ
    トを検出し、当該加算領域の評価値と共に記憶する検出
    記憶手段と、 前記平面全体で前記加算領域の評価値が最大となる前記
    任意のバケットを検出し、前記検出記憶手段により検出
    された前記もう１つのバケットを用いて、領域Ｓを導き
    出す手段とを含む請求項１０記載のデータ間結合ルール
    導出装置。
15. 【請求項１５】切り出されるべき領域に含まれる最低限
    のデータ数である最小サポート数Ｕminを入力する手段
    と、 前記切り出された領域Ｓに含まれるデータ数Ｕ（Ｓ）と
    前記最小サポート数Ｕminと比較する手段と、 前記比較の結果、Ｕmin≒Ｕ（Ｓ）であれば、当該領域
    Ｓを切り出されるべき領域として出力する手段と、 前記比較の結果、Ｕmim＞Ｕ（Ｓ）又はＵmim＜Ｕ（Ｓ）
    の場合には、新たな条件θ₅にて、前記領域切出手段が
    動作するように命ずる手段とを含む請求項１０記載のデ
    ータ間結合ルール導出装置。
16. 【請求項１６】切り出されるべき領域における前記真偽
    をとる属性が真であるデータの数の割合minconfを入力
    する手段と、 前記切り出された領域Ｓが、minconf≒Ｖ（Ｓ）／Ｕ
    （Ｓ）（Ｕ（Ｓ）は前記領域Ｓに含まれるデータ数、Ｖ
    （Ｓ）は前記領域Ｓに含まれ且つ前記真偽をとる属性が
    真であるデータの数）である場合には、当該領域Ｓを出
    力する手段と、 mimconf＜Ｖ（Ｓ）／Ｕ（Ｓ）又はminconf＞Ｖ（Ｓ）／
    Ｕ（Ｓ）である場合には、新たな条件θ₈にて前記領域
    切出手段が動作するよう命ずる手段とを含む請求項１０
    記載のデータ間結合ルール導出装置。
17. 【請求項１７】切り出された前記領域Ｓに対し、 【数１２】 （Ｕsumは前記平面全体のデータ数、Ｖsumは前記平面全
    体に含まれる前記真偽をとる属性が真のデータの数）を
    計算し、その値を前記領域Ｓに対応して記憶するエント
    ロピ計算手段と、 変更された条件θにて前記領域切出手段及び前記エント
    ロピ計算手段が動作するように命ずる手段と、 前記エントロピ計算手段に記憶されたｆ（Ｕ（Ｓ），Ｖ
    （Ｓ））を最大化する領域Ｓを出力する手段とを含む請
    求項１０記載のデータ間結合ルール導出装置。
18. 【請求項１８】切り出された前記領域Ｓに対し、 【数１３】 （Ｕsumは前記平面全体のデータ数、Ｖsumは前記平面全
    体に含まれる前記真偽をとる属性が真のデータの数）を
    計算し、その値を前記領域に対応して記憶するインタク
    ラスバリアンス計算手段と、 変更された条件θにて前記領域切出手段と前記インタク
    ラスバリアンス計算手段とを動作するように命ずる手段
    と、 前記インタクラスバリアンス計算手段に記憶されたｆ
    （Ｕ（Ｓ），Ｖ（Ｓ））を最大化する領域Ｓを出力する
    手段とを含む請求項１０記載のデータ間結合ルール導出
    装置。