(57)【特許請求の範囲】
【請求項１】
（ａ）２つの異なる属性のデータを１組とする複数の処理対象データを記憶手段に記憶する第１のステップと、
（ｂ）前記記憶手段に記憶された前記複数の処理対象データのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素に変換する第２のステップと、
（ｃ）前記行列から任意の１つの行を選択する第３のステップと、
（ｄ）前記第３のステップで選択された行に含まれる各処理対象データをそれぞれ含む複数の列を選択する第４のステップと、
（ｅ）選択された各列に含まれる各処理対象データをそれぞれ含む複数の行を得る第５のステップと、
（ｆ）前記第５のステップで得られた複数の行のそれぞれに対応して設けられた複数の第１のカウンタのそれぞれで、当該第５のステップで得られた各行について、前記選択された各列のうち当該行に含まれる前記処理対象データを含む列の数を計数する第６のステップと、
（ｇ）前記複数の第１のカウンタのそれぞれの値を基に、前記第５のステップで得られた複数の行から１つまたは複数の行を選択する第７のステップと、
（ｈ）前記第７のステップで選択された各行に含まれる各処理対象データをそれぞれ含む複数の列を得る第８のステップと、
（ｉ）前記第８のステップで得られた複数の列のそれぞれに対応して設けられた複数の第２のカウンタのそれぞれで、当該第８のステップで得られた各列について、前記第７のステップで選択された各行のうち当該列に含まれる前記処理対象データを含む行の数を計数する第９のステップと、
（ｊ）前記複数の第２のカウンタのそれぞれの値を基に、前記第８のステップで得られた複数の列から１つまたは複数の列を選択する第１０のステップと、
（ｋ）前記第１０のステップで選択された列および前記第７のステップで選択された行が所定の収束条件を満たすまで、前記第５のステップ乃至前記第１０のステップの処理を繰り返す第１１のステップと、
（ｌ）前記収束条件を満たしたときに前記第１０のステップで選択された列および前記第７のステップで選択された行からなる前記処理対象データの密集した部分行列を、前記行列から抽出する第１２のステップと、
を有することを特徴とするデータ抽出方法。
【請求項２】
（ａ）２つの異なる属性のデータを１組とする複数の処理対象データを記憶手段に記憶する第１のステップと、
（ｂ）前記記憶手段に記憶された前記複数の処理対象データのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素に変換する第２のステップと、
（ｃ）前記行列から任意の１つの列を選択する第３のステップと、
（ｄ）前記第３のステップで選択された列に含まれる各処理対象データをそれぞれ含む複数の行を選択する第４のステップと、
（ｅ）選択された各行に含まれる各処理対象データをそれぞれ含む複数の列を得る第５のステップと、
（ｆ）前記第５のステップで得られた複数の列のそれぞれに対応して設けられた複数の第１のカウンタのそれぞれで、当該第５のステップで得られた各列について、前記選択された各行のうち当該列に含まれる前記処理対象データを含む行の数を計数する第６のステップと、
（ｇ）前記複数の第１のカウンタのそれぞれの値を基に、前記第５のステップで得られた複数の列から１つまたは複数の列を選択する第７のステップと、
（ｈ）前記第７のステップで選択された各列に含まれる各処理対象データをそれぞれ含む複数の行を得る第８のステップと、
（ｉ）前記第８のステップで得られた複数の行のそれぞれに対応して設けられた複数の第２のカウンタのそれぞれで、当該第８のステップで得られた各行について、前記第７のステップで選択された各列のうち当該行に含まれる前記処理対象データを含む列の数を計数する第９のステップと、
（ｊ）前記複数の第２のカウンタのそれぞれの値を基に、前記第８のステップで得られた複数の行から１つまたは複数の行を選択する第１０のステップと、
（ｋ）前記第１０のステップで選択された行および前記第７のステップで選択された列が所定の収束条件を満たすまで、前記第５のステップ乃至前記第１０のステップの処理を繰り返す第１１のステップと、
（ｌ）前記収束条件を満たしたときに前記第１０のステップで選択された行および前記第７のステップで選択された列からなる前記処理対象データの密集した部分行列を、前記行列から抽出する第１２のステップと、
を有することを特徴とするデータ抽出方法。
【請求項３】
前記第７のステップは、
前記１つまたは複数の行を選択する度に、当該選択された行と前記選択された列を含む前記部分行列の大きさと、当該部分行列の大きさに対する当該部分行列に含まれる前記処理対象データの数の割合とに基づき、前記複数の第１のカウンタのそれぞれの値に、前記１つまたは複数の行を選択するための第１の閾値をそれぞれ設定することを特徴とする請求項１記載のデータ抽出方法。
【請求項４】
前記部分行列の大きさが予め定められた大きさ以上となり、かつ前記割合が最大となるように前記第１の閾値を設定することを特徴とする請求項３記載のデータ抽出方法。
【請求項５】
前記割合が予め定められた値以上となり、かつ前記部分行列の大きさが最大となるように前記第１の閾値を設定することを特徴とする請求項３記載のデータ抽出方法。
【請求項６】
前記部分行列に含まれる行と列の数が予め定められた値以上であり、かつ前記割合が最大となるように前記第１の閾値を設定することを特徴とする請求項３記載のデータ抽出方法。
【請求項７】
前記第１０のステップは、
前記１つまたは複数の列を選択する度に、当該選択された列と前記選択された行を含む前記部分行列の大きさと、当該部分行列の大きさに対する当該部分行列に含まれる前記処理対象データの数の割合とに基づき、前記複数の第２のカウンタのそれぞれの値に、前記１つまたは複数の列を選択するための第２の閾値をそれぞれ設定することを特徴とする請求項１記載のデータ抽出方法。
【請求項８】
前記部分行列の大きさが予め定められた大きさ以上となり、かつ前記割合が最大となるように前記第２の閾値を設定することを特徴とする請求項７記載のデータ抽出方法。
【請求項９】
前記割合が予め定められた値以上となり、かつ前記部分行列の大きさが最大となるように前記第２の閾値を設定することを特徴とする請求項７記載のデータ抽出方法。
【請求項１０】
前記部分行列に含まれる行と列の数が予め定められた値以上であり、かつ前記割合が最大となるように前記第２の閾値を設定することを特徴とする請求項７記載のデータ抽出方法。
【請求項１１】
２つの異なる属性のデータを１組とする複数の処理対象データを記憶する記憶手段と、
前記記憶手段で記憶された前記複数の処理対象データのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素に変換する変換手段と、
前記行列の各列にそれぞれ対応する複数の第１のカウンタと、
前記行列の各行にそれぞれ対応する複数の第２のカウンタと、
前記行列から任意の１つの行を選択する手段と、
選択された各行に含まれる各処理対象データをそれぞれ含む複数の列を求め、求めた複数の列のそれぞれに対応して設けられた複数の前記第１のカウンタのそれぞれで、当該求めた各列について、前記選択された各行のうち当該列に含まれる前記処理対象データを含む行の数を計数し、前記複数の第１のカウンタのそれぞれの値を基に、前記求めた複数の列から１つまたは複数の列を選択する第１の処理と、選択された各列に含まれる各処理対象データをそれぞれ含む複数の行を求め、求めた複数の行のそれぞれに対応して設けられた複数の前記第２のカウンタのそれぞれで、当該求めた各行について、前記選択された各列のうち当該行に含まれる前記処理対象データを含む列の数を計数し、前記複数の第２のカウンタのそれぞれの値を基に、前記求めた複数の行から１つまたは複数の行を選択する第２の処理とを、前記第１の処理により選択された列と前記第２の処理により選択された行とが所定の収束条件を満たすまで交互に行う手段と、
前記収束条件を満たしたときに前記第１の処理により選択された列および前記第２の処理により選択された行からなる前記処理対象データの密集した部分行列を、前記行列から抽出する手段と、
を具備したことを特徴とするデータ抽出装置。
【請求項１２】
（ａ）２つの異なる属性のデータを１組とする複数の処理対象データを記憶手段に記憶する第１のステップと、
（ｂ）前記記憶手段に記憶された前記複数の処理対象データのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素に変換する第２のステップと、
（ｃ）前記行列から任意の１つの行を選択する第３のステップと、
（ｄ）前記第３のステップで選択された行に含まれる各処理対象データをそれぞれ含む複数の列を選択する第４のステップと、
（ｅ）選択された各列に含まれる各処理対象データをそれぞれ含む複数の行を得る第５のステップと、
（ｆ）前記第５のステップで得られた複数の行のそれぞれに対応して設けられた複数の第１のカウンタのそれぞれで、当該第５のステップで得られた各行について、前記選択された各列のうち当該行に含まれる前記処理対象データを含む列の数を計数する第６のステップと、
（ｇ）前記複数の第１のカウンタのそれぞれの値を基に、前記第５のステップで得られた複数の行から１つまたは複数の行を選択する第７のステップと、
（ｈ）前記第７のステップで選択された各行に含まれる各処理対象データをそれぞれ含む複数の列を得る第８のステップと、
（ｉ）前記第８のステップで得られた複数の列のそれぞれに対応して設けられた複数の第２のカウンタのそれぞれで、当該第８のステップで得られた各列について、前記第７のステップで選択された各行のうち当該列に含まれる前記処理対象データを含む行の数を計数する第９のステップと、
（ｊ）前記複数の第２のカウンタのそれぞれの値を基に、前記第８のステップで得られた複数の列から１つまたは複数の列を選択する第１０のステップと、
（ｋ）前記第１０のステップで選択された列および前記第７のステップで選択された行が所定の収束条件を満たすまで、前記第５のステップ乃至前記第１０のステップの処理を繰り返す第１１のステップと、
（ｌ）前記収束条件を満たしたときに前記第１０のステップで選択された列および前記第７のステップで選択された行からなる前記処理対象データの密集した部分行列を、前記行列から抽出する第１２のステップと、
をコンピュータに実行させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、クレジットカードの利用履歴等の膨大な処理対象としてのレコードの中からマーケティングなどに有用な情報を抽出するためのデータ抽出方法に関する。
【０００２】
【従来の技術】
大規模データベースから知識を抽出する技術としてデータマイニングが注目されている。データマイニングの手法としては、決定木、ニューラルネット、相関規則発見、クラスタリングなど様々な手法が提案されている。これらの手法によりデータベースの中に隠されている特徴を抽出し、マーケテイングなどのさまざまな分野への応用が期待されている。
【０００３】
クラスタリングとはデータベースの中から互いに類似したレコードを抽出する方法である。従来の代表的なクラスタリング手法として、Ｋ−ｍｅａｎ法や凝縮法が用いられている。これらのクラスタリング手法ではレコードをその属性空間上の点ととらえ、レコード間の距離を予め定義することにより、距離の近いレコードをまとめてクラスタを形成する手法である。例えばＫ−ｍｅａｎｓ法は初期値としてＫ個のレコードを核とし、他のレコードとこれらの核との距離を計算してもっとも近い核の形成するクラスタにそのレコードを格納する。全レコードがクラスタに格納されると各クラスタ内で中心の位置を計算して核とし、上記の処理を繰り返すことにより、最終的にＫ個のクラスタを生成する方法である。
【０００４】
スーパーマーケット等の小売業では、カードを用いた顧客管理が行われている。カードを用いることにより、どの顧客がどの商品を購入したかという販売情報が電子的に得られる。この販売情報を分析することにより、顧客の特性や商品の特性を知ることができ、マーケティング情報として有効に活用することが可能となる。クラスタリング手法はこのような場面に適用される手法であり、類似した購買傾向の顧客や商品をクラスタ化するのに用いられている。
【０００５】
ここでは小売店を例としてとりあげ、従来のクラスタリング手法の適用について説明する。ある小売店で取り扱う商品を（ｘ、ｙ、ｚ）の３点とし、Ａ、Ｂ、Ｃ、Ｄの４人の顧客について過去の購買履歴が図１のようにデータベースに格納されているとする。生データのままで顧客のクラスタリングを行うには、３点の商品に対応して３次元の空間を想定し、４人の顧客をその空間上の点と捉える。すなわち、各次元の値は「０」と「１」の２値とし、ある顧客がある商品を購入した場合は対応する次元の値を「１」とし、購入していない場合は「０」とする。本例の場合は図２に示すように、ｘ−ｙ−ｚ空間においてＡの座標は（１、０、０）、Ｂの座標は（０、１、１）、Ｃの座標は（０、１、０）、Ｄの座標は（１、０、１）となる。次に顧客間の距離を定義する。本例では顧客間の距離は３次元のベクトル間のハミング距離とする。このように定義すると、商品全体の購買状況について傾向の似通った顧客間の距離が小さくなり、クラスタを形成する。図２の場合、ＢとＣのハミング距離は「１」、ＡとＤのハミング距離は「１」となり、他の組み合わせより小さくなるので、（Ｂ、Ｃ）と（Ａ、Ｄ）の２つのクラスタを形成する。同様に、商品間のクラスタリングでは各商品を顧客の張る４次元の空間上の点と捉え、商品間の距離を４次元のベクトル間のハミング距離とすれば、顧客全体について販売動向の似通った商品間の距離が小さくなり、クラスタを形成する。
【０００６】
しかし、このようなクラスタリングでは次元数が膨大になると、特定の商品群に関する顧客の購買傾向の類似性や、特定の顧客層に関する商品の購買傾向の類似性を抽出することが困難になる。大規模な小売店では商品数、顧客数とも数万以上となり、例えばＡさんとＢさんがカーオーディオ商品に関して共通の購買傾向をもっていても、他のジャンルの購買傾向が異なるならばＡさんとＢさんの間の距離は大きくなり、同一クラスタに属さないことがある。同様に、Ｘ商品とＹ商品は高校生に関して共通の購買傾向をもっていても、他の年代の顧客の購買傾向が異なるならば同一クラスタに属さないことがある。このため、カーオーディオ商品に関する顧客のクラスタリングを行うには、カーオーディオ商品のみを予め選択した空間において顧客のクラスタリングを行う必要があり、高校生の好みに関する商品のクラスタリングを行うには、高校生のみを予め選択した空間において商品のクラスタリングを行う必要がある。
【０００７】
このように、例えば、多数の顧客、多数の商品を扱う小売業において、顧客と商品といった、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係のクラスタリングを行うには、予めクラスタリングを行う商品や顧客を選択して指定する必要があり、予め想定できないような顧客と商品のデータ間の関係をクラスタリングにより抽出することはできない。
【０００８】
【発明が解決しようとする課題】
以上のように、従来ではクラスタリングを行うときに、対象となる属性を事前に指定する必要がある。従って、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係をクラスタリングにより抽出することはできないという問題点があった。
【０００９】
そこで、本発明は、上記問題点に鑑み、例えば、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係を容易に抽出できるデータ抽出方法を提供することを目的とする。
【００１０】
【課題を解決する手段】
本発明は、少なくとも２つの異なる属性のデータを１組とする複数の処理対象のそれぞれを前記各属性を軸とする多次元空間上に表現し、各軸方向のデータ列の順序を入れ替えて、前記処理対象の密集した部分空間を抽出することにより、例えば、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係を容易に抽出できる。
【００１１】
本発明は、２つの異なる属性のデータを１組とする複数の処理対象のそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素として表現し、この行列の行と列の順序を入れ替えて、前記処理対象の密集した部分行列を抽出することにより、例えば、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係を容易にしかも高速に抽出できる。
【００１２】
本発明は、２つの異なる属性のデータを１組とする複数の処理対象のそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素として表現し、前記行列から操作対象として行が選択されたときは、前記選択された行の行成分をもつ処理対象を有する列のうち所定の条件を満たす列を次の操作対象として選択し、前記操作対象として列が選択されたときは、前記選択された列の列成分をもつ処理対象を有する行のうち所定の条件を満たす行を次の操作対象として選択する処理を所定の収束条件を満たすまで繰り返して、最終的に選択された行と列とで構成される部分行列を抽出することにより、例えば、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係を容易にしかも高速に抽出できる。
【００１３】
特に、前記列あるいは行を選択する度に、前記列あるいは行を選択することにより抽出される部分行列の大きさが所定値以上で、この部分行列に占める前記処理対象の割合が最大となるように、あるいは、前記列あるいは行を選択することにより抽出される部分行列に占める前記処理対象の割合が所定値以上で、この部分行列の大きさが最大となるように、あるいは、前記列あるいは行を選択することにより抽出される部分行列を構成する行と列の数がそれぞれ所定値以上の形状で、この部分行列に占める前記処理対象の割合が最大となるように、前記列あるいは行を選択するための閾値を設定することにより、最終的に所望の大きさの所望の密度の所望の形状の部分行列が容易にしかも高速に抽出できる。
【００１４】
本発明によれば、例えば、顧客と商品とで構成される複数の処理対象から、一部の顧客と一部の商品の間に存在する特徴を抽出することが可能となり、マーケティングなどに有用な情報を膨大な処理対象の中から容易にしかも高速に抽出することができる。
【００１５】
また、例えば、顧客と商品を枝刈りしながら処理を進めることにより、膨大な量の処理対象群に対しても効率よく特徴を抽出することができる。
【００１６】
さらに、同一アルゴリズムで面積最大化、密度最大化、部分行列の形状指定などに対応することが可能であるため、簡潔なソフトウェアで広い用途に適用できる。
【００１７】
【発明の実施の形態】
以下、本発明の実施形態について図面を参照して説明する。
【００１８】
図１１は、本発明の実施形態に係る情報処理装置の主要部の構成例を示したもので、主に、ＣＰＵ１０１、主記憶１０２、キャッシュメモリ１０３、表示部１０４、ハードディスク１０５、キーボードやマウス等の入力部１０８、フロッピーディスクドライブ１０９、ＣＤ−ＲＯＭドライブ１１０等から構成され、上記各構成要素はバスを用いて接続されている。ＣＰＵ１０１と主記憶１０２とキャッシュメモリ１０３は超高速バス（プロセッサバス）にて接続され、ハードディスク１０５や表示部１０４の高速性が要求される周辺装置を高速バス（例えば、ＰＣＩバス）にて接続され、この高速バスとブリッジ回路１０６にて接続される低速バスには、キーボードやマウス等の入力部１０８、フロッピディスクドライブ１０９、ＣＤ−ＲＯＭドライブ１１０、シリアル／パラレルインタフェース部１０７などの低速な周辺装置が接続されている。
【００１９】
このような構成において、ＣＰＵ１０１は、ハードディスク１０５に記憶されたプログラムやデータを読み出して、主記憶１０２上にロードしたり、主記憶１０２上に置かれたプログラムやデータを読み出して処理し、その処理結果を主記憶１０２に記憶したり、表示部１０４に表示させたり、また、主記憶１０２上のデータをハードディスク１０５に書き込む。
【００２０】
例えば、本実施形態に係る処理対象の顧客とその顧客が購入した商品とを１組とする複数のレコードは、所定の端末装置から入力され、所定の通信回線を介して、図１１の情報処理装置のシリアル／パラレルインタフェース部１０７に入力されたり、直接、図１１の情報処理装置の入力部１０８から入力されるなどして、ハードディスク１０５にデータベースとして格納されているとする。このレコードを処理対象として、図１１の情報処理装置は、以下の第１〜第３の実施形態に記載した処理を実行する。
【００２１】
（第１の実施形態）
まず、例えば、顧客とその顧客が購入した商品とを１組とする複数のレコードを処理対象とした場合を例にとり、本発明のデータ抽出方法の概念を説明する。
【００２２】
図３に顧客と商品を軸とする２値行列表現を示す。行は顧客を表し、ここでは、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆの６人の顧客を表す。列は商品を表し、ここではａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇの７つの商品を表す。この行列の要素Ａｉｊ＝１とは、顧客ｉが商品ｊを購入したことを表す。すなわち、データベース中に（顧客＝ｉ、商品＝ｊ）となるレコードが存在することを表す。Ａｉｊ＝０とは（顧客＝ｉ、商品＝ｊ）となるレコードが存在しないことを表す。なお、（顧客＝ｉ、商品＝ｊ）となるレコードが複数個存在しても行列の要素の値は「１」とする。一般に図３は疎行列である。なお、Ａｉｊの解釈として、（顧客＝ｉ、商品＝ｊ）となる同じレコードが予め定めた個数以上のときのみに、その行列要素を「１」として表してもよい。
【００２３】
図３において、行や列の並び方は任意であるため、順序を入れ替えてもよい。図４では図３に示した行列の行、列を入れ替えることにより、密な部分行列を抽出する過程を示している。まず、図４（ａ）において、行Ｃと行Ｆを入替え（図４（ｂ）参照）、次に、図４（ｂ）において、列ｄと列ｇを入れ替えることにより、図４（ｃ）の点線で囲まれた部分、すなわち顧客Ｂ、Ｆ、Ｄと商品ｃ、ｇ、ｅより成る密な部分行列が抽出される。
【００２４】
この密な部分行列の表す意味は次のように解釈できる。「顧客Ｂ、Ｆ、Ｄは商品ｃ、ｇ、ｅに関して共通の性質をもつ」、あるいは、「商品ｃ、ｇ、ｅは顧客Ｂ、Ｆ、Ｄに関して共通の性質をもつ」。また、密な部分行列内に「０」となる要素は、将来「１」となる可能性が高いと解釈する。例えば、「顧客Ｂは商品ｇを購入する可能性が高い」という解釈が可能である。このように密な部分行列を抽出することは、顧客と商品の両方を同時に抽出することに相当する。
【００２５】
次に、図５に示すフローチャートを参照して、図１１の情報処理対象の処理動作について説明する。ここでは、行列の左上に密な部分行列を形成するための操作を行うものである。すなわち、「１」となる行列要素が上に行くように行を入替え、「１」となる行列要素が左に行くように列を入替える。また、図３に示した行列に対する図５に基づいた処理過程を図６に示す。以下、図６を参照しながら図５に示すフローチャートに基づき説明する。
【００２６】
まず、データベースにある複数のレコードを前述同様、顧客と商品を軸とする２値行列に変換する（図３参照）。
【００２７】
操作対象の２つの行Ｘ、Ｙを選択する（ステップＳ１、ステップＳ２）。選択方法としてはランダムに選択する、あるいは上から順に選択するなどがあるが。ステップＳ１７における収束条件を簡単にするためには、上から順に２つ選択するのが望ましい。
【００２８】
ステップＳ１、Ｓ２で選択された行Ｘ、Ｙの評価値を計算する（ステップＳ３．ステップＳ４）。評価値の計算方法としては各種の方法があるが、ここでは「１」となる要素と下端あるいは右端からの距離の総和とする。例えば、図６（ａ）において、行Ｃと行Ｆが選択されたとする。ＸおよびＹは行番号とし、ここではＸ＝３、Ｙ＝６となる。行Ｃは要素ｆのみが「１」であり、右端からの距離は「２」となる。行Ｆは要素ｅとｇが「１」であり、右端からの距離はそれぞれ「３」と「１」となるので総和は「４」となる。従って、行Ｘの評価値ＸＸ＝２、行Ｙの評価値ＹＹ＝４となる。
【００２９】
次に、行番号、評価値を比較する（ステップＳ５〜ステップＳ７）。この場合、ステップＳ５において、Ｘ＝３、Ｙ＝６であるので、ステップＳ６へ進み、ステップＳ６において、ＸＸ＝２、ＹＹ＝４であるので、ステップＳ８へ進み、行Ｃと行Ｆが入替えられる（図６（ｂ）参照）。
【００３０】
次に、ステップＳ９、ステップＳ１０において、２つの列を選択する。ここでは列ｄと列ｇが選択されたとする。選択方法としてはランダムに選択する、あるいは左端から順に選択するなどがあるが。ステップＳ１７における収束条件を簡単にするためには、左端から順に２つ選択するのが望ましい。
【００３１】
ステップＳ１１、Ｓ１２では、選択された列Ｚ、列Ｗの評価値を計算する。行の場合と同様にして、ＺおよびＷは列番号とし、図６（ｂ）に示すように、ここではＺ＝４、Ｗ＝７となる。列ｄは要素Ａのみが「１」であり、下端からの距離は「６」となる。列ｇは要素Ｆ、Ｄが「１」であるので、下端からの距離はそれぞれ「４」と「３」となり、総和は「７」となる。すなわち、ＺＺ＝６、ＷＷ＝７となる。
【００３２】
次に、列番号、評価値を比較する（ステップＳ１３〜ステップＳ１５）。この場合、ステップＳ１３において、Ｚ＝４、Ｗ＝７であるので、ステップＳ１４へ進み、ステップＳ１４において、ＺＺ＝６、ＷＷ＝７であるので、ステップＳ１６へ進み、列ｄと列ｇが入替えられる（図６（ｃ）参照）。
【００３３】
以下同様にして、図６（ｃ）において行Ａと行Ｄを選択して、ステップＳ８で行Ａと行Ｄを入れ替え、図６（ｄ）において列ａと列ｅを選択して、ステップＳ１６で列ａと列ｅを入れ替える。また、図６（ｅ）において行を選択してもステップＳ８での行の入れ替えが発生しないため、次に、列ｂと列ｇを選択して、ステップＳ１６で列ｂと列ｇを入れ替えて、図６（ｆ）に示すような行列を得る。このような処理を収束するまで（ステップＳ１７）繰り返すと、図６（ｆ）に示すように最終的に左上に密な部分行列（行Ｄ、Ｂ、Ｆと列ｅ、ｇ、ｃより構成される部分行列）が生成される。この最終的に得られた密な部分行列（点線で囲まれた部分）を表示部１０４に表示する。
【００３４】
なお、ステップＳ１７の収束性の判定は行や列の選択方法により異なる。行や列の選択方法をランダムとした場合は、入替えが一定回数生じないことを検出して収束性を判定すればよい。また、他の選択方法においては、すべての行あるいは列の対について入替えが生じないことが判定できれば、その時点を収束状態とすればよい。
【００３５】
以上説明したように、上記第１の実施形態によれば、例えば、顧客と商品といった２つの異なる属性のデータを１組とする複数のレコードのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素として表現し、この行列の行と列の順序を入れ替えて、レコードの密集した部分行列を抽出することにより、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係であっても容易に抽出できる。
【００３６】
なお、上記第１の実施形態では、評価値の大きい方の行を上に、列を左に持っていくように入替えを行い、左上に密な部分行列を生成したが、この方向を変えれば、左下、右上、右下に部分行列を生成できることは明らかである。例えば、右下に密な部分行列を生成する場合は、ステップＳ３〜ステップＳ８において、評価値の大きい方の行を下にいくように入れ替え、ステップＳ１３〜ステップＳ１６において、評価値の大きい列を右にいくように入れ替えればよい。
【００３７】
また、上記第１の実施形態では、顧客と商品といった２つの異なる属性のデータを１組とするレコードを行列という２次元空間上に表現した場合を例にとり説明したが、本発明は、２次元空間に限らず、レコードに３つ以上の属性がある場合でも、それれら各属性を軸とする多次元空間上に該レコードを表現し、その多次元空間上のある１カ所にレコードが密集するように、上記同様、各軸方向のデータ列の順序を入れ替える操作を行えば、該多次元空間から密な部分空間を抽出できる。
【００３８】
なお、上記説明において、収束した状態とは、それ以上の入替えが生じない状態ではあるが、これが最適解ではないことが多い。このため、シミュレーテッドアニーリング（Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ）の手法を適用し、確率的に状態遷移を起こすことにより、よりよい解を求めることも可能である。
【００３９】
（第２の実施形態）
第１の実施形態では、全ての行・列を比較対象として入れ替えを行うため、行列のサイズが大きくなると実行時間が膨大となる。そこで、第２の実施形態として、操作対象となる行・列を実行時に枝刈りすることにより小さく抑えて高速化を図ったデータ抽出方法について説明する。図７は、第２の実施形態に係る図１１の情報処理装置の処理動作を説明するためのフローチャートで、図３に示した行列に対する処理過程を図８に示す。以下、図７に示すフローチャートに従って、図８を参照しながら説明する。なお、本発明は、行から列、列から行へのマーカ伝搬により、操作対象の行、列を探索する手法を用いていて、このマーカ伝搬の様子を、概念的に、行（列）は、値が「１」の行列要素にて接続されている列（行）へマーカを送信し、列（行）は、値が「１」の行列要素にて接続されている行（列）からマーカを受信すると表現している。
【００４０】
まず、データベースにある複数のレコードを前述同様、顧客と商品を軸とする２値行列に変換する（図３参照）。
【００４１】
次に、操作開始行を指定する（ステップＳ２１）。ここではＢを開始行とする（図８のステップＳ５１）。図３に示すように、行Ｂから、値が「１」の行列要素を介して接続される列へマーカを送信する。ここでは、図３、図８に示すように、行Ｂにおいて、列ｃと列ｅの要素が「１」なので、列ｃと列ｅにマーカが送信される（ステップＳ２２、図８のステップＳ５２）。
【００４２】
マーカ伝搬は、具体的には、例えば、次のような処理により実現される。すなわち、例えば、各行Ａ〜Ｆ、各列ａ〜ｇにはそれぞれマーカビットと呼ぶ１ビットのフラグを複数個（好ましくは、各行には列の要素と同じ個数、各列には行の要素と同じ個数）持たせておく。ここでは、行Ｂにおいて、列ｃと列ｅの要素が「１」なので、列ｃと列ｅの１番目のマーカビットをセットする（例えば、「１」とする）。
【００４３】
次に、列毎にマーカを集計する。すなわち、列ｃと列ｅのマーカビットは１番目のみセットされているので、集計結果は列ｃ、列ｅとも「１」となる。なお、最初の１往復のマーカ伝搬においては、枝刈りは行わないこととし、枝刈りは集計されたマーカ数が「１」以下のものを除去するものとする（ステップＳ２３）。なお、マーカの集計、枝刈りが終了するたびに各行、各列のマーカビットをリセットする（例えば、「０」とする）。
【００４４】
列ｃ、列ｅから、値が「１」の行列要素を介して接続される行へマーカを送信する。ここでは、図３、図８に示すように、列ｃにおいて、行Ｂ、行Ｄの要素が「１」なので、行Ｂ、行Ｄにマーカが送信され、また、列ｅにおいて、行Ｂ、行Ｆの要素が「１」なので、行Ｂ、行Ｆにマーカが送信される（図８のステップＳ５３）。すなわち、行Ｂの１番目と２番目のマーカビットをセットし、行Ｄの１番目のマーカビットをセットし、行Ｆの１番目のマーカビットをセットする。
【００４５】
次に、行毎にマーカを集計する。すなわち、行Ｂのマーカビットは１番目と２番目がセットされ、行Ｄと行Ｆはそれぞれ１番目のマーカビットのみがセットされているので、集計結果は行Ｂが「２」、行Ｄと行Ｆが「１」となる。この場合も最初の１往復の範囲なので枝刈りは行わない（図８のステップＳ５４）。
【００４６】
ステップＳ２６へ進み、状態変化を調べる。この場合、活性化されている行Ｂ、Ｄ、Ｆは直前の状態（すなわち、行Ｂのみが活性化されている状態）と異なるので、処理が継続され、ステップＳ２２へ戻る。
【００４７】
ステップＳ２２では、行Ｂ、Ｄ、Ｆから、値が「１」の行列要素を介して接続される列へマーカを送信する。ここでは、図３、図８に示すように、行Ｂにおいて、列ｃ、ｅの要素が「１」なので、列ｃ、ｅにマーカが送信され、また、行Ｄにおいて、列ａ、ｃ、ｇの要素が「１」なので、列ａ、ｃ、ｇにマーカが送信され、行Ｆにおいて、列ｅ、ｇの要素が「１」なので列ｅ、ｇにマーカが送信される（図８のステップＳ５５）。すなわち、列ａの１番目のマーカビットをセットし、列ｃ、ｅ、ｇのそれぞれの１番目と２番目のマーカビットをセットする。
【００４８】
ステップＳ２３で、列毎にマーカを集計する。すなわち、列ａのマーカビットは１番目のみがセットされ、列ｃ、ｅ、ｇはそれぞれ１番目と２番目のマーカビットがセットされているので、集計結果は列ａが「１」、列ｃ、ｅ、ｇがそれぞれ「２」となる。この場合、２往復目であるので、枝刈りが行われてマーカ数が少ない列ａが削除され、列ｃ、ｅ、ｇが活性化される（図８のステップＳ５６）。
【００４９】
次に、ステップＳ２４へ進み、列ｃ、ｅ、ｇのそれぞれから、値が「１」の行列要素を介して接続される行へマーカを送信する。ここでは、図３、図８に示すように、列ｃにおいて、行Ｂ、行Ｄの要素が「１」なので、行Ｂ、行Ｄにマーカが送信され、また、列ｅにおいて、行Ｂ、行Ｆの要素が「１」なので、行Ｂ、行Ｆにマーカが送信され、また、列ｇにおいて、行Ｄ、行Ｆの要素が「１」なので、行Ｄ、行Ｆにマーカが送信される（図８のステップＳ５７）。すなわち、行Ｂ、行Ｄ、行Ｆのそれぞれの１番目と２番目のマーカビットをセットする。
【００５０】
ステップＳ２５で、行毎にマーカを集計する。すなわち、行Ｂ、行Ｄ、行Ｆのそれぞれのマーカビットは１番目と２番目がセットされているので、集計結果は、行Ｂと行Ｄと行Ｆはそれぞれ「２」となる。この場合は、集計結果が各行で等しいので枝刈りされず、行Ｂ、Ｄ、Ｆが活性化される（図８のステップＳ５８）。
【００５１】
ステップＳ２６へ進み、状態変化を調べる。活性化された行は直前の状態と同じであるため、これ以上繰り返しても状態は変化しないことが分かり、処理は終了する。
【００５２】
結果として、最後に活性化された行Ｂ、Ｄ、Ｆと列ｃ、ｅ、ｇより構成される部分行列が得られる。これは、第１の実施形態における結果（図６参照）と一致している。
【００５３】
以上説明したように、上記第２の実施形態によれば、２つの異なる属性のデータを１組とする複数のレコードのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素として表現し、この行列から選択された操作対象の行の行成分をもつレコードを有する列のうち、その列に含まれる操作対象の行の行成分をもつレコードの数（すなわち、マーカ数）が２以上の列を次の操作対象として選択し（活性化し）、次に、この選択された操作対象の列の列成分をもつレコードを有する行のうち、その行に含まれる前記操作対象の列の列成分をもつレコードの数（すなわち、マーカ数）が２以上の行を次の操作対象として選択する（活性化する）処理を所定の収束条件を満たすまで（すなわち、列（あるいは行）を選択した際に、その選択された列（あるいは行）と、その直前に選択された列（あるいは行）とが同じになるまで）繰り返して、最終的に選択された行と列とで構成される部分行列を抽出することにより、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係であっても容易にしかも高速に抽出できる。
【００５４】
なお、上記第２の実施形態では、例えば、図７のステップＳ２１で、操作対象として行をまず選択しているが、この場合に限らず、操作対象の列をます選択して、列から行へのマーカ送信、行毎のマーカの集計および枝刈りによる操作対処の行の選択、行から列へのマーカ送信、列毎のマーカ集計および枝刈りによる操作対象の列の選択と実行しても、上記同様の効果を得ることは明らかである。
【００５５】
（第３の実施形態）
上記第２の実施形態の枝刈りのアルゴリズムについては、各行、列において受信したマーカ数が閾値より少ないものを枝刈りする（第２の実施形態では、受信したマーカ数が「１」以下のものを枝刈りしている）と説明したが、閾値をあらかじめ設定するのではなく、枝刈りの時点で部分行列の面積や密度を計算し、これらを用いて閾値を設定することにより、有効な枝刈りが可能となる。すなわち、図７のステップＳ２３、ステップＳ２５において枝刈りを行うた度に、枝刈りのための閾値を求めて枝刈りを行う場合について、以下、説明する。
【００５６】
部分行列の面積は、活性化されている行数および列数を乗ずることにより計算できる。また、部分行列の密度は、枝刈りを行う時点で、各行、列で受信したマーカ数の合計を面積で除することにより計算できる。
【００５７】
例えば、図８のステップＳ５５〜ステップＳ５６における枝刈りに関しては、（ａ、ｃ、ｅ、ｇ）の４つの列から（ｃ、ｅ、ｇ）の３つの列へと枝刈りしている。この直前に活性化されている行数は（Ｂ、Ｄ、Ｆ）の３行であり、（ａ、ｃ、ｅ、ｇ）の４列を活性化すると、部分行列の面積は３×４＝１２で、（ａ、ｃ、ｅ、ｇ）の４列が受信したマーカ数は合計で「７」なので、密度は７÷１２＝０．５８となる。一方、受信マーカ数の少ない列ａを枝刈りして（ｃ、ｅ、ｇ）の３列を活性化すると、部分行列の面積は３×３＝９、（ｃ、ｅ、ｇ）の３列が受信したマーカ数は合計で「６」なので、密度は６÷９＝０．６７となる。このように枝刈りすることにより、部分行列の面積は小さくなるが密度は大きくなる。
【００５８】
一般に、できるだけ大きい面積で、でるだけ密度の高い部分行列が抽出できることが望ましい。
【００５９】
そこで、ここでは、以下の３つの閾値設定のための基準を用いて、求めたい部分行列の面積や密度に基づく枝刈りの閾値を決める方法について説明する。
【００６０】
（基準１）与えられた面積以上で密度が最大の部分行列を求める
（基準２）与えられた密度以上で面積が最大の部分行列を求める
（基準３）与えられた行数、列数以上で密度が最大の部分行列を求める
以上のような基準を閾値の設定時に用いるということ以外は、図７のフローチャートに示したアルゴリズムで対処することができる。なお、ここでは列から行へのマーカ伝播について説明するが、行から列に関しても同様である。現在、活性化されている列数は「５」とし、この５つの列から伝搬されたマーカを受信した行（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｊ）とそれらの受信マーカ数が、図９に示すような場合を例にとり説明する。
【００６１】
枝刈りの閾値が「１」から「５」のそれぞれの場合について、求まる部分行列の面積と密度を図１０に示す。図１０において、例えば、閾値が「３」の場合、図９から、マーカを受信した行のうち、受信したマーカ数が２以下のものを枝刈りして、行（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ）の６行が活性化される。この６行が受信したマーカ数の合計は、「２４」である。よって、現在活性化されている列数「５」とともに面積を求めると６×５＝３０となり、密度は、２４／３０＝０．８となる。
【００６２】
ここで、（基準１）の例として、例えば、面積が「２５」以上で密度最大となる部分行列を求める場合について説明する。図１０より、面積が「２５」という条件を満たすには閾値は「３」、「２」、「１」のいづれかである必要がある。その中で密度を最大にする閾値は「３」であるので、枝刈りの閾値が「３」と決まる。
【００６３】
（基準２）の例として、例えば、密度７５％以上で面積最大となる部分行列を求める場合について説明する。図１０より、密度が７５％以上となる閾値は「３」、「４」、「５」のいづれかである必要がある。その中で面積を最大にする閾値として「３」と決まる。
【００６４】
（基準３）の例として、例えば、行数・列数とも「５」以上で密度最大となる部分行列を求める場合について説明する。図１０より、行数・列数とも「５」以上となるのは閾値が「３」、「２」、「１」のいづれかである必要がある。その中で密度を最大にする閾値として、「３」と決まる。
【００６５】
以上説明したように、上記第３の実施形態によれば、２つの異なる属性のデータを１組とする複数のレコードのそれぞれを、一方の属性のデータを行成分、他方の属性のデータを列成分とした行列の要素として表現し、この行列から選択された操作対象の行の行成分をもつレコードを有する列の中から、その列を選択することにより抽出される部分行列の大きさ（すなわち、面積）と、この部分行列に占めるレコードの割合（すなわち、密度）と、その列に含まれる操作対象の行の行成分をもつレコードの数（すなわち、マーカ数）とに基づき、次の操作対象としての列を選択し（活性化し）、次に、この選択された操作対象の列の列成分をもつレコードを有する行の中から、その行を選択することにより抽出される部分行列の大きさ（すなわち、面積）と、この部分行列に占めるレコードの割合（すなわち、密度）と、その行に含まれる操作対象の列の列成分をもつレコードの数（すなわち、マーカ数）とに基づき、次の操作対象としての行を選択する（活性化する）処理を所定の収束条件を満たすまで（すなわち、列（あるいは行）を選択した際に、その選択された列（あるいは行）と、その直前に選択された列（あるいは行）とが同じになるまで）繰り返して、最終的に選択された行と列とで構成される部分行列を抽出することにより、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係であっても容易にしかも高速に抽出できる。
【００６６】
特に、列あるいは行を選択する度に、その列あるいは行を選択することにより抽出される部分行列の面積が所定値以上で、この部分行列の密度が最大となるように、枝刈りする列あるいは行の受信マーカ数の閾値を設定したり、あるいは、その列あるいは行を選択することにより抽出される部分行列の密度が所定値以上で、この部分行列の面積が最大となるように、枝刈りする列あるいは行の受信マーカ数の閾値を設定したり、あるいは、その列あるいは行を選択することにより抽出される部分行列を構成する行と列の数がそれぞれ所定値以上の形状で、この部分行列の密度が最大となるように、枝刈りする列あるいは行の受信マーカ数の閾値を設定したりすることにより、最終的に所望の大きさの所望の密度の所望の形状の部分行列が容易にしかも高速に抽出できる。
【００６７】
なお、上記第２〜第３の実施形態では、各行、各列に対応するマーカビットを用いて受信マーカ数を集計する場合を示したが、この場合に限らず、各行、各列のそれぞれにカウンタを設けても上記説明と同様である。すなわち、活性化されている行あるい列に接続されている列あるいは行のカウンタをそれぞれ「１」だけインクリメントして、マーカの集計時には、この各列あるいは行のカウンタ値をチェックする。カウンタ値が上記説明の受信マーカ数（値が「１」のマーカビットの数）に対応する。マーカの集計、枝刈りが終了するたびに各行、各列のカウンタ値をリセットすればよい（例えば、「０」とする）。
【００６８】
また、上記第１〜第３の実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、ＤＶＤ、ＣＤ−ＲＯＭ、フロッピディスク、個体メモリ、光ディスクなどの記録媒体に格納して頒布することもできる。
【００６９】
本発明の処理手順を記述したプログラムを格納した記録媒体（例えば、ＣＤ−ＲＯＭ）を、例えば、ＣＤ−ＲＯＭドライブ１１０にセットして、所定の操作を行うことにより、ハードディスク１０５にインストールすれば、上記第１〜第３の実施形態に記載した手法を図１１の情報処理装置にて実行させることができる。すなわち、ハードディスク１０５に顧客とその顧客が購入した商品とを１組とする複数のレコードがデータベースとして格納されているとする。このレコードに対し、上記第１〜第３の実施形態に記載した手法を図１１の情報処理装置にて実行させると、例えば、図３に示したような行列から抽出された部分行列が、図１２に示すように、表示部１０４に表示される。また、図６に示したような処理過程も表示してもよい。
【００７０】
また、上記第１〜第３の実施形態では、顧客とその顧客の購入した商品との関係を抽出する場合を例にとり説明しているが、この場合に限るものではなく、例えば、アンケートの集計・ＷＷＷページアクセスの解析等にも適用可能である。
【００７１】
また、本発明は、上記第１〜第３の実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。さらに、上記第１〜第３の実施形態には種々の段階の発明は含まれており、開示される複数の構成用件における適宜な組み合わせにより、種々の発明が抽出され得る。例えば、実施形態に示される全構成要件から幾つかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題（の少なくとも１つ）が解決でき、発明の効果の欄で述べられている効果（のなくとも１つ）が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【００７２】
【発明の効果】
以上説明したように、本発明によれば、例えば、顧客と商品の関係のように、データ自体に、もともと順序や距離という概念を持たない複数の属性のデータ間の予め想定できないような関係を容易に抽出できる。
【図面の簡単な説明】
【図１】従来のクラスタリング方法を説明するための処理対象のレコードの一例を示した図。
【図２】図１に示したレコードに対する従来のクラスタリング方法を説明するための図。
【図３】複数のレコードの行列形式の表現例を示した図。
【図４】本発明の第１の実施形態にかかるデータ抽出方法の概念を説明するための図。
【図５】第１の実施形態にかかるデータ抽出方法を説明するためのフローチャート。
【図６】図５に示したフローチャートに従った、図５の行列の処理過程を説明するための図。
【図７】本発明の第２の実施形態にかかるデータ抽出方法を説明するためのフローチャート。
【図８】図７に示したフローチャートに従った、図５の行列の処理過程を説明するための図。
【図９】本発明の第３の実施形態にかかる枝刈りのための受信マーカ数の閾値を設定するための手順を説明するための図。
【図１０】本発明の第３の実施形態にかかる枝刈りのための受信マーカ数の閾値を設定するための手順を説明するための図。
【図１１】本発明の実施形態に係る情報処理装置の主要部の構成例を示した図。
【図１２】図１１の情報処理装置による処理結果の表示例を示した図。
【符号の説明】
１０１…ＣＰＵ
１０２…主記憶
１０３…キャッシュメモリ
１０４…表示部
１０５…ハードディスク
１０６…キーボードやマウス等の入力部
１０９…フロッピーディスクドライブ
１１０…ＣＤ−ＲＯＭドライブ
【図１】
0003557162.tif 000002
【図２】
0003557162.tif 000003
【図３】
0003557162.tif 000004
【図４】
0003557162.tif 000005
【図５】
0003557162.tif 000006
【図６】
0003557162.tif 000007
【図７】
0003557162.tif 000008
【図８】
0003557162.tif 000009
【図９】
0003557162.tif 000010
【図１０】
0003557162.tif 000011
【図１１】
0003557162.tif 000012
【図１２】
0003557162.tif 000013