密度が高い部分行列データをコンピュータによって抽出する方法、そのコンピュータシステム及びコンピュータプログラム
【課題】 抽出された密な部分行列が必要な行や列を含むことができるようにする。
【解決手段】 有意なデータ要素と非有意なデータ要素とが含まれる行列データＭから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、部分行列データを抽出するために基準となる単一又は複数の基準行ｒ＿ｂと単一又は複数の基準列ｃ＿ｂを決定し、前記行列データの各行ｒと前記基準行ｒ＿ｂとの間での類似性を示す数値を演算して前記基準行ｒ＿ｂとの類似性の低い行ｒを削除し、前記行列データの各列ｃと前記基準列ｃ＿ｂとの間での類似性を示す数値を演算して前記基準列ｃ＿ｂとの類似性の低い列ｃを削除する。
【解決手段】 有意なデータ要素と非有意なデータ要素とが含まれる行列データＭから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、部分行列データを抽出するために基準となる単一又は複数の基準行ｒ＿ｂと単一又は複数の基準列ｃ＿ｂを決定し、前記行列データの各行ｒと前記基準行ｒ＿ｂとの間での類似性を示す数値を演算して前記基準行ｒ＿ｂとの類似性の低い行ｒを削除し、前記行列データの各列ｃと前記基準列ｃ＿ｂとの間での類似性を示す数値を演算して前記基準列ｃ＿ｂとの類似性の低い列ｃを削除する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、密度が高い部分行列データをコンピュータによって抽出する方法、そのコンピュータシステム及びコンピュータプログラムに関するものである。
【背景技術】
【０００２】
大量のデータから特徴を抽出する手法として、データマイニングが広く用いられている。特に、インターネットの普及により、ＷＷＷから得られるデータにマイニングを行うことにより、有益な情報を得る応用はＷＷＷマイニングと呼ばれ、ＷＷＷ検索エンジンやマーケティングなどに幅広く応用されている。
データマイニングの対象となるデータの表現形式としては、２値行列による表現が用いられることがある。例えば、顧客の購買履歴は、縦軸（行）を顧客、横軸（列）を商品とし、特定の顧客が特定の商品を購入したとき、対応する行列の要素を「１」とし、購入していないときに行列の要素を「０」とすることにより、２値行列で表現することができる。
【０００３】
このような、行列データは、一般に大規模疎行列となる。すなわち、行列の行数（顧客数）、列数（商品）数は大きいが、値が「１」となる行列のデータ要素は、値が「０」となる行列のデータ要素に比べて圧倒的に少ない。
このような、大規模な疎行列のままでは、有益な情報を把握しにくいが、大規模疎行列から値が「１」となる要素を多く含む密な部分行列を抽出することができれば、マーケティング等において有用な情報となる。すなわち、上記の例では、密な部分行列が得られれば、購買傾向の似た顧客群と商品群を同時に得られるからである。
【０００４】
このように、大規模疎行列から密な部分行列を抽出する操作は、非特許文献１においては、マトリクスクラスタリングとよばれている。マトリクスクラスタリングは、ＷＷＷマイニングにおいても、ユーザとユーザが見たページの関係や、ページとページ内に含まれるキーワードの関係を同時に得ることに応用できるため、有効な手法である。
【０００５】
マトリクスクラスタリングのリアルタイムの応用例として、リコメンデーションシステムがある。例えば、ＷＷＷ上でのショッピングサイトにおいて、上記のようにユーザと購入した商品の履歴を２値行列で保持するものとする。
あるユーザが、そのショッピングサイトにログインしてきたとき、大規模疎行列から、そのユーザに関連する密な部分行列をリアルタイムで抽出することができれば、ログインしたユーザに対して、適切な商品をリコメンドすることができる。
すなわち、密な部分行列を得られれば、そのユーザと似た購買傾向を持つ他のユーザを抽出でき、密な部分行列において、そのユーザは購入していないが、他のユーザは購入している商品を見つけることができれば、その商品をそのユーザに奨めることができる。
このような、リコメンデーションシステムは、ＷＷＷのパーソナライズとして今後の発展が大いに期待されている分野である。
【０００６】
マトリクスクラスタリングの他の応用例として、文書検索システムがある。個々の文書を横軸（列）に、文書に含まれるキーワードを縦軸（行）にした行列表現をとる。特定の文書の中に特定のキーワードが含まれるときに、対応する行列要素を１とし、含まれないときに０とする。あるキーワードが止定されたとき、そのキーワードに関連する密な部分行列を抽出することができれば、指定されたキーワードに関連した文書群とキーワード群が得られる。この場合、通常の文書検索システムとは異なり、入力されたキーワードを直接含まない文書でも、含まれるキーワードが類似していれば検索結果に含まれるという特徴がある。
【０００７】
従来のマトリクスクラスタリングのアルゴリズムとして、非特許文献１には、行・列置換法とピンポン法が提示されている。
行・列置換法では、元の疎行列の行同士、あるいは列同士を入れ換える操作を繰り返す。例えば、行列の左上に１となる要素が集まるように、行同士、列同士を入れ替えることにより、密な部分行列を疎行列の左上に形成することができる。
【０００８】
ピンポン法では、初期値となる行より列方向にマーカ伝播を行い、各列では受信したマーカ数により枝刈りを行い、多くのマーカを受信した列のみを操作の対象とする。次に列から行方向にマーカを伝播し、各行では受信したマーカ数により枝刈りを行い、多くのマーカを受信した行のみを操作の対象とする。ピンポン法は、これらの操作を繰り返すことにより、密行列を生成する手法である。
【非特許文献１】小柳滋、久保田和人、仲瀬明彦：Matrix Clustering：ＣＲＭ向けの新しいデータマイニング手法、情報処理学会論文誌、Vol.42、No.8、pp.2156-2166、（２００１）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１では、ピンポン法が行・列置換法に比べて性能や、密行列の性質において優れていることが示されている。
しかし、上記のような応用にピンポン法を適用する場合には、初期値として指定された行あるいは列を含まない密な部分行列を出力する場合があることが、問題となる。例えば、ピンポン法を前記リコメンデーションシステムへ応用した場合に、初期値としてあるユーザが指定されたのに、密な部分行列がそのユーザを示す行を含まないということは、要求と全く異なる結果が出力されるおそれがある。
また、ピンポン法を文書検索システムに応用した場合にも、同様に、要求と関連のない結果が出力されるというおそれがある。
【００１０】
そこで、本発明は、抽出された密な部分行列が必要な行や列を含むことができる、新たな方法等を提供することを目的の一つとする。
【課題を解決するための手段】
【００１１】
本発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除するステップ、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除するステップ、
を有することを特徴とする方法である。
【００１２】
上記方法において、有意なデータ要素は、具体的な値としては、例えば「１」で表され、非有意なデータ要素は、具体的な値としては、例えば「０」で表されるものである。上記方法によって「１」などで表される有意なデータ要素の密度が高い部分行列データが得られる。
そして、上記方法によれば、基準行と基準列とが決定され、基準行・基準列との類似性の低い行・列から削除されるため、密な部分行列データを生成しても、当該部分行列データには基準行と基準列とが含まれることが保証される。
なお、上記（ｃ）のステップと（ｄ）のステップは、繰り返し行うことにより、行列データを次々に縮退させて、有意なデータ要素の密度を高めていくことができる。
【００１３】
前記（ｃ）のステップ、又は（ｄ）のステップにおいて、行又は列の削除を行う際に、指定された所定割合の数の行又は列を一括して削除するのが好ましい。
指定された所定割合の数の行又は列を一括して削除することにより、（ｃ）のステップや（ｄ）のステップを何度も繰り返し行わなくても、少ない回数で、大きな疎行列を小さくすることができ、効率が良くなる。
【００１４】
前記（ａ）のステップにおいて、複数の基準行が決定された場合には、前記（ｃ）のステップに代えて、下記（ｅ）のステップを実行するのが好ましい。
（ｅ）前記行列データの各行と前記各基準行との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準行と非基準行にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準行との類似性が低い行を削除するステップ。
基準行が複数ある場合、それぞれの基準行に含まれる有意なデータ要素の数が異なることがあり、この場合、ある行と各基準行との類似性の演算を行うと、有意なデータ要素の数が多い基準行との類似度の方が高くなってしまい、他の基準行との類似度が相対的に低くなることになる。このように、有意なデータ要素の数の差によって、それぞれの基準行の間に、不必要な差が生じてしまうが、有意なデータ要素の数を考慮して類似性の演算を行うことにより、この問題を解消できる。
【００１５】
また、複数基準列の場合も上記複数基準行の場合と同様にするのが好ましい。
すなわち、前記（ｂ）のステップにおいて、複数の基準列が決定された場合には、前記（ｄ）のステップに代えて、下記（ｆ）のステップを実行するのが好ましい。
（ｆ）前記行列データの各列と前記各基準列との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準列と非基準列にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準列との類似性が低い列を削除するステップ。
【００１６】
演算を高速化するため、前記第（ｃ）のステップ、又は（ｄ）のステップの実行前に、下記（ｇ）のステップを実行して初期部分行列データを生成し、その初期部分行列データに対して、前記（ｃ）のステップ、又は（ｄ）のステップを行うのが好ましい。
（ｇ）前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行と、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列と、からなる初期部分行列データを生成する。
【００１７】
上記初期部分行列データにおいては、基準行又は基準列と共通するデータ要素を持たない行又は列は存在しなくなる。共通するデータ要素を持たない行又は列は、類似性を演算すると、いずれ削除されるものであるから、（ｃ）のステップ、又は（ｄ）のステップの実行前に初期部分行列データを生成して、これに（ｃ）のステップ、又は（ｄ）のステップを実行することで、（ｃ）（ｄ）のステップを高速に行える。
【００１８】
前記（ｇ）のステップにおいて、前記初期部分行列データは、前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行のうち、前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素の数が多い所定数の行と、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列のうち、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素の数が多い所定数の列と、を取り出して生成されるのが好ましい。
基準行又は基準列と共通するデータ要素を持つ行又は列であっても、その共通する数が少ない場合には、類似性を演算するといずれ削除される可能性が高いため、そのような行又は列は、初期部分行列データから取り除くことで、その後の演算をより高速に行うことができる。
【００１９】
他の観点からみた本発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｈ）前記基準行において有意なデータ要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除するステップ、
（ｉ）前記基準列において有意なデータ要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除するステップ、
を有することを特徴とする方法である。
【００２０】
上記方法によれば、基準行と基準列とが決定され、基準行・基準列と共通の有意なデータ要素が存在しない行又は列を削除して部分行列データを生成することで、行列の密度を高めることができるとともに、密な部分行列データを生成しても、当該部分行列データには基準行と基準列とが含まれることが保証される。
なお、基準行・基準列と共通の有意なデータ要素が存在しない行又は列を削除するだけでは、行列の大きさを十分に小さくできない場合があるため、他の方法によって、行列をさらに小さくし、密度を上げるようにしてもよい。
【００２１】
コンピュータシステムに係る本発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するものであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除する手段、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除する手段、
を有することを特徴とするものである。
また、コンピュータプログラムに係る本発明は、コンピュータを、前記コンピュータシステムにおける（ａ）（ｂ）（ｃ）（ｄ）のそれぞれの手段として機能させるためのものである。
【００２２】
他の観点からみたコンピュータシステムに係る発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するものであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｈ）前記基準行において有意な要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除する手段、
（ｉ）前記基準列において有意な要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除する手段、
を有することを特徴とするものである。
また、他の観点からみたコンピュータプログラムに係る本発明は、コンピュータを、前記コンピュータシステムにおける（ａ）（ｂ）（ｈ）（ｉ）のそれぞれの手段として機能させるためのものである。
【発明の効果】
【００２３】
本発明によれば、必要な行や列を、基準行・基準列として決定し、これらの基準行・基準列が残るように密な部分行列データを抽出することができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の好ましい実施形態を図面に基づいて説明する。
［用語と標記法について］
ここでは、複数の行の間で共通して１となる列をそれらの行の共通要素とよぶ。また、列についても同様に、複数の列の間で共通して１となる行をそれらの列の共通要素とよぶ。
文中での行列の標記法は、行の集合と列の集合の間に×を置くか、行数と列数の間に×を置くものとする。行列の一つの要素は、行の名前と列の名前を並べ、（）で括ることで表記する。
【００２５】
［実施形態の方法で要求される事項］
ここで説明する実施形態に係る部分行列データの抽出方法は、行列中において、注目する行と列に関連する行と列を同時に発見する操作であり、マトリクスクラスタリングとよばれる。なお、以下では、マトリクスクラスタリングを、単に「ＭＣ」ということがある。
ここでのＭＣは、主に、有意なデータ要素である「１」と非有意なデータ要素である「０」の２値要素を対象にし、「１」要素が密に存在する部分行列を発見するために行われる。
このＭＣは、リコメンデーションシステムや文書検索システムへの応用をより適切に行うため、次の要求を満たすことが望ましいものである。
（要求１）部分行列が孤立した行又は列を含まない。
（要求２）部分行列の行数と列数の比を制御できる。
（要求３）部分行列が注目すべき行と列を同時に含むように制御できる。
（要求４）部分行列の特定の行又は列が０（非有意なデータ要素）を含むように制御できる。
【００２６】
上記（要求１）は、図１（ａ）の行ｄと列Ｆのように、他の行及び列との共通要素を持たない行又は列を含んでいる場合をいう。また、図１（ｂ）は、他の行と共通要素を持たない行の一種である空行ａを含んでいる。
図１（ａ）の孤立した行ｄと列Ｆや、図１（ｂ）の行ａは、他の行及び列との間に関連性がなく、部分行列が関連した行と列の集合を表すべきものと考えた場合、孤立した行と列を含むことは許されない。つまり、孤立した行と列を含む部分行列に基づいて、リコメンドや、文書検索における関連文献の出力を行うには不適切である。そこで、上記（要求１）が必要となる。
【００２７】
上記（要求２）のように、部分行列の行数と列数の比を制御できると、部分行列の使用目的等に応じて、部分行列に必要な行数と列数が異なる場合にも対応でき好ましい。
つまり、図２（ａ）から、密度（部分行列中の「１」の数／行列の全要素数）が１で、可能な限り大きい部分行列を取り出すと、横長の部分行列（図２（ｂ））と、縦長の部分行列（図２（ｃ））の２つが得られる。横長の部分行列は列の間よりも、行の間の共通要素数を多くすることを優先した結果であり、縦長の部分行列は行よりも列を優先した結果である。例えば、行を文書、列をそのキーワードとして類似文書を探すことを考えると、縦長の部分行列（図２（ｃ））が表すものは、頻繁に使われるキーワード、つまり大きな分野を示すキーワードで一致する文書の集合であり、横長の部分行列（図（ｂ））が表すものは、使用される頻度の低いキーワード、つまりより細分化された分野を示すキーワードまで一致する文書の集合である。このような使い分けをするには、上記（要求２）が必要となる。
【００２８】
上記（要求３）のように、部分行列が注目すべき行と列を同時に含むように制御できると、得られた部分行列に注目すべき行と列が含まれていることを保証でき、得られた部分行列の適切さが向上する。
例えば、複数の分野にまたがる文書の場合、どのキーワードに着目するかで、関連する文書の集合が異なってくる。このような区別をするには、ＭＣアルゴリズムが、注目すべき行（文書）だけでなく、列（キーワード）も取り扱えるようにして、部分行列が注目すべき行と列を同時に含むように制御できるようにすることが好ましく、上記（要求３）が必要となる。
【００２９】
上記（要求４）のように、部分行列の特定の行又は列が０を含むように制御できると、確実にリコメンドをすることができる。例えば、オンライン書店で、ユーザに書籍を推薦することを考える。ユーザを行、書籍を列とし、ユーザが購入した書籍に該当する要素を「１」とした行列を用いると、得られた密な部分行列において、指定されたユーザを示す行には、少なくとも一つの０が含まれていなければ、推薦すべき書籍が見つからないから、何も出力できないという問題が発生する。この場合、部分行列において、ユーザを示す行は、必ず０を含む必要がある。また、列についても同様である。そこで、上記（要求４）が必要となる。
【００３０】
［実施形態］
本実施形態で説明する方法は、リコメンデーションシステムの機能を有するＷＷＷサーバ、又は文書検索コンピュータシステムなどのコンピュータシステムにおいて、記憶装置に記憶されたコンピュータプログラムに基づき、当該コンピュータシステムによって実行されるものである。なお、後述の他の実施形態においても同様である。
【００３１】
図３は、有意なデータ要素である「１」の密度が疎である大規模行列データＭの一例を示している。この行列データＭは、行ａ〜ｊが顧客を示しており、列Ａ〜Ｏが商品を示す２次元行列である。行列の各データ要素としては、「１」（有意なデータ要素）と「０」（非有意なデータ要素）の２値をとるものであり、例えば、行列データＭの［ｅ，Ｇ］のデータ要素が「１」であるのは、顧客ｅは商品Ｇを購入したことがある、ということを示している。コンピュータには、その記憶手段に、図３と同様の２次元配列データ構造又は、図３の２次元データと実質的に同じデータ内容を示すデータ構造により記憶させることができる。
【００３２】
具体的には、行列データの構造は、図５に示すようなものとすることができる。行列Ｍの行エントリを配列データ：ｒｏｗＥｎｔｒｙ［ｒ］（ｒは行ａ〜ｊを表す）とし、列エントリを配列データ：ｃｏｌｕｍｎＥｎｔｒｙ［ｃ］（ｃは列Ａ〜Ｏを表す）とする。
図５のデータ構造は、図３の行列Ｍに対応しており、配列ｒｏｗＥｎｔｒｙ［ｒ］には、ｒで示される行において「１」の要素を持つ列が格納されている。例えば、ｒｏｗＥｎｔｒｙ［ａ］には、｛Ｃ，Ｆ，Ｊ，Ｎ，Ｏ｝が格納されている。
同様に、配列ｃｏｌｕｍｎＥｎｔｒｙ［ｃ］には、ｃで示される行において「１」の要素を持つ行が格納されている。例えば、ｃｏｌｕｍｎＥｎｔｒｙ［Ｆ］には、｛ａ，ｃ，ｄ，ｈ｝が格納されている。
なお、行列データＭは、顧客が商品を購入する度に、データが更新される。
【００３３】
図４は、実施形態に係る方法を示している。この方法は、基準行と基準列の決定（ステップＳ１）、初期部分行列データの生成（ステップＳ２）、部分行列データの縮退操作（ステップＳ３）とを含んでいる。
まず、行列データＭのデータ要素の中から一つの要素（後述の実施形態では複数のデータ要素の場合もある）を決定することで、基準行と基準列が決まる。以下では、基準行をｒ＿ｂといい、基準列をｃ＿ｂという。
基準要素の決定は、例えば、ＷＷＷ上でのショッピングサイトにおいて、ある「顧客ａ」がある「商品Ｆ」を購入、又はある「商品Ｆ」を購入検討のために見ること等によって、行われる。この場合、基準要素（ｒ＿ｂ，ｃ＿ｂ）＝（ａ，Ｆ）であり、基準行はａ、基準列はＦに決まったことになる。なお、基準行及び基準列を示す情報は、コンピュータの記憶手段に記憶される。
【００３４】
初期部分行列データＭ０の生成（ステップＳ２）は、行列データＭから、基準行ｒ＿ｂと基準列ｃ＿ｂを用いて作られる。
初期部分行列データＭ０の生成は、特許請求の範囲の（ｇ）のステップと同様の方法によって行われる。ここで、（ｇ）のステップは、「基準行ｒ＿ｂにおいて有意なデータ要素「１」が存在する列と同じ列に共通して存在する有意なデータ要素「１」を１個以上持つ行ｒと、前記基準列ｃ＿ｂにおいて有意なデータ要素「１」が存在する行と同じ行に共通して存在する有意なデータ要素「１」を１個以上持つ列ｃと、からなる初期部分行列データＭ０を生成する」というものである。
【００３５】
（ｇ）のステップの具体的な実行方法は、一つではない。初期部分行列データＭ０の行を示す行集合をＲ（０）、列を示す列集合をＣ（０）とすると、Ｒ（０）のデータとＣ（０）のデータを作る方法は、それぞれ、少なくとも２通りある。
［行集合Ｒ（０）の構成方法その１］
行列データＭの行のうち、ｒ＿ｂと共通要素を持つすべての行の集合Ｒ（０）を作る（以下、この場合のＲ（０）をＲＬという。なお、添え字の「Ｌ」は「loose」を示している。）。図３の行列データＭの場合、ＲＬは次のようになる。
ＲＬ＝｛ａ，ｃ，ｄ，ｅ，ｆ，ｈ，ｉ，ｊ｝
［行集合Ｒ（０）の構成方法その２］
行列データＭの行のうち、ｃ＿ｂに「１」の要素を持つ行のみからなる集合Ｒ（０）を作る（以下、この場合のＲ（０）をＲＳという。なお、添え字の「Ｓ」は「strict」を示している。）。図３の行列データＭの場合、ＲＳは次のようになる。
ＲＳ＝｛ａ，ｃ，ｄ，ｈ｝
【００３６】
［列集合Ｃ（０）の構成方法その１］
行列データＭの列のうち、ｃ＿ｂと共通要素を持つすべての列の集合Ｃ（０）を作る（以下、この場合のＣ（０）をＣＬという）。図３の行列データＭの場合、ＣＬは次のようになる。
ＣＬ＝｛Ｃ，Ｄ，Ｆ，Ｊ，Ｎ，Ｏ｝
［列集合Ｃ（０）の構成方法その２］
行列データＭの列のうち、ｒ＿ｂに「１」の要素を持つ行のみからなる集合Ｃ（０）を作る（以下、この場合のＣ（０）をＣＳという）。図３の行列データＭの場合、ＣＳは次のようになる。
ＣＳ＝｛Ｃ，Ｆ，Ｊ，Ｎ，Ｏ｝
【００３７】
上記２つの行集合ＲＬ，ＲＳと、２つの列集合ＣＬ，ＣＳとの組み合わせで、計４種類の初期部分行列データＭ０を作ることができる。すなわち、ＲＬ×ＣＬ，ＲＬ×ＣＳ，ＲＳ×ＣＬ，ＲＳ×ＣＳの４種類である。これらは、行列データの使用目的に応じて使い分けられるべきものである。例えば、基準行ｒ＿ｂや基準列ｃ＿ｂが前記（要求４）を満たすべきものであるなら、ＲＳやＣＳは使えない。なぜなら、ＲＳを使うときは、初期部分行列データ中の基準列ｃ＿ｂが、ＣＳなら基準行ｃ＿ｒが全て「１」要素で占められるからである。なお、ＲＳ⊆ＲＬ、ＣＳ⊆ＣＬが成立するため、４種類の初期部分行列データのうち、ＲＳ×ＣＳが最も小さい部分行列となり、ＲＬ×ＣＬが最も大きい部分行列となる。
図６（ａ）に示す初期部分行列データＭ０は、ＲＬ×ＣＬである。すなわち、行列データＭに対して、［行集合Ｒ（０）の構成方法その１］と［列集合Ｃ（０）の構成方法その２］の操作を行うことによって生成されたものである。
なお、最も小さい部分行列ＲＳ×ＣＳの場合Ｍ０＝｛ａ，ｃ，ｄ，ｈ｝×｛Ｃ，Ｆ，Ｊ，Ｎ，Ｏ｝となる。
【００３８】
ＲＬ×ＣＬの初期部分行列データＭ０の、より具体的な構成方法としては、次のようにすることができる。下記手順は、初期部分行列データＭ０の行集合を求める方法である。
（手順１）初期部分行列データＭ０の行番号を格納する配列データ：ｒｏｗｓを用意する。ｒｏｗｓは空で初期化する
（手順２）ｒｏｗＥｎｔｒｙ［ｒ＿ｂ］中の各要素ｃｉに対して、ｃｏｌｕｍｎＥｎｔｒｙ［ｃｉ］の全要素をｒｏｗｓにコピーする。
（手順３）ｒｏｗｓの各データをソートし、重複要素を削除する。
【００３９】
以上により、ｒｏｗｓに初期部分行列データを構成する行が存在することになる。
また、初期部分行列データＭ０の列集合を求める方法は下記手順のとおりである。
（手順１）初期部分行列データＭ０の行番号を格納する配列データ：ｃｏｌｕｍｕｓを用意する。ｃｏｌｕｍｕｓは空で初期化する。
（手順２）ｃｏｌｕｍｎＥｎｔｒｙ［ｃ＿ｂ］中の各要素ｒｉに対して、ｒｏｗＥｎｔｒｙ［ｒｉ］の全要素をｃｏｌｕｍｎｓにコピーする。
（手順３）ｃｏｌｕｍｎｓの各データをソートし、重複要素を削除する。
【００４０】
１つの行・列の平均「１」要素数をそれぞれｎｒ，ｎｃとすると、（手順２）のコピーは、ｎｒ回実行され、１回にコピーされる要素数はｎｃである。コピーが終了した時点で、ｒｏｗｓにはｎｒ・ｎｃ個の要素が格納されている。ｎｒ・ｎｃ＝Ｎとすると、コピーはＯ（Ｎ）となり、ソートをＯ（ＮｌｏｇＮ），重複要素の削除をＯ（Ｎ）とすると、この計算量はソートに支配され、Ｏ（ＮｌｏｇＮ）となる。
【００４１】
この初期部分行列データＭ０の生成処理は、本実施形態では、後述する部分行列データの縮退操作（ステップＳ３）の前処理として行われるが、初期部分行列データＭ０の生成処理は、他の方法による部分行列抽出アルゴリズムの前処理として行っても良い。
また、用途によっては、初期部分行列データＭ０の生成処理によって、十分に面積が小さく密な部分行列が得られる場合もあり、この場合は、初期部分行列データＭ０の生成処理に相当する処理だけで、処理を終了してもよい。
初期部分行列データＭ０の生成処理に相当する処理だけで部分行列データ抽出処理を終了してもよいことは、初期部分行列データＭ０の生成処理（ステップＳ２）と部分行列データの縮退操作（ステップＳ３）が基本的に共通していることを示している。
すなわち、初期部分行列データＭ０の生成処理（ステップＳ２）は、部分行列データの縮退操作（ステップＳ３）における「内積」をとったときに、その値が０又は小さい値となる行又は列に相当するものを初期の段階で一括して削除する処理と考えることができる。基準行又は基準列と内積とったときに値が小さくなる行又は列は、基準行又は基準列との類似性が低く、縮退操作を行えば、いずれ削除される可能性が高いものであるから、予め削除しておくことで、縮退操作を高速に行うことが可能となる。
【００４２】
部分行列データの縮退操作（ステップＳ３）は、主に、類似性演算（ステップＳ３４−１，Ｓ３４−２）と、削除操作（ステップＳ３５−１，Ｓ２５−２）とからなり、それぞれ、行方向の演算及び操作（ステップＳ３４−１，Ｓ３５−１）と、列方向の演算及び操作（ステップＳ３４−２，Ｓ３５−２）とがある。
行方向の類似性演算（ステップＳ３４−１）は、部分行列データの各行をベクトルとみなし、基準行との内積を求めることで、それらの行にスコアを付ける操作である。対象が２値行列であるため、２つの行の内積は、それらの行の共通要素数に等しい。共通要素数が大きければ行の間の類似性は高くなる。列方向の類似性演算（ステップＳ３４−２）も同様である。
行の削除操作（ステップＳ３５−１）は、類似性を示すスコアの最も小さい行を部分行列から排除するものである。列の削除操作（ステップＳ３５−２）も同様である。
【００４３】
図６の初期部分行列データＭ０に対して、まず、行縮退ｒを行うとすると、基準行ｒ＿ｂ＝ａであるから、各行の内積は、ｃとｈが５、ｄとｉが３、ｅとｆとｊが１となる。この結果に削除操作を行うと、内積最小の行ｅ，ｆ，ｊが取り除かれ、部分行列データＭ１（図６（ｂ））が作られる。
次に列縮退ｃを行う。基準列ｃ＿ｂ＝Ｆなので、各列の内積はＪとＮが４、ＣとＯが３、ＤとＬが１となり、内積最小のＤ，Ｌが削除され、部分行列データＭ２が得られる。さらに、行縮退ｒを行うと、密度１の部分行列データＭ３が得られる。
なお、部分行列データＭ３に対して、さらに行と列の縮退操作を１回ずつ適用でき、その結果、ａ×Ｆが得られる。
【００４４】
図６においては、行縮退ｒと列縮退ｃとが交互に行われているが、行と列のどちらを縮退するかは、縮退方向決定関数によって決定される（ステップＳ３２）。縮退方向の決定方法としては、交互とする他、行と列の比を用いてもよい。行と列の比を用いて縮退方向を決定する方法については後述する。また、縮退方向の順序は、出力に影響を与えるがこの点も後述する。
また、縮退方向決定関数は、縮退操作（ステップＳ３）を終了させる手段としても機能する。図６では、部分行列データの密度が１のＭ３が作られるまで処理が続いているが、縮退方向決定関数が適当な終了条件を持つことで、Ｍ３に至る前に縮退処理は終了する。
主な終了条件としては、部分行列データの最小密度がある。図６の処理を、最小密度０．８の終了条件で実行すれば、密度が０．８４となったＭ２で停止し、Ｍ２を出力とする。また、終了条件は、部分行列データの面積（データ要素数の数）であってもよいし、密度と面積の双方であってもよい。
【００４５】
ステップＳ３の縮退操作を図４に基づいて、詳細に説明すれば、次のとおりである。まず、カウンタ変数ｉを０に初期化し（ステップＳ３１）、ｉ＝０，１，２・・・に関して、終了条件を満たすまで次の処理を繰り返す（ステップＳ３８）。
（ａ）縮退方向決定関数が、その関数値Ｘ＝終了を出力すれば、部分行列データＭｉを出力して終了する。それ以外（Ｘ＝行縮退ｏｒＸ＝列縮退）なら、この関数が示す方向に縮退する（ステップＳ３２，Ｓ３３）。
（ｂ）行縮退出の場合：
（ｂ−１）部分行列データＭｉの各行に対して基準行ｒ＿ｂとの内積を求める（ステップＳ３４−１）。
（ｂ−２）内積の最も小さい行（複数存在するなら全て）を行集合Ｒ（ｉ）から取り除いたものを行集合Ｒ（ｉ＋１）とする（ステップＳ３５−１）。
（ｂ−３）列集合Ｃ（ｉ）を行集合Ｃ（ｉ＋１）とする（ステップＳ３６−１）。
（ｃ）列縮退出の場合：
（ｃ−１）部分行列データＭｉの各列に対して基準列ｃ＿ｂとの内積を求める（ステップＳ３４−２）。
（ｃ−２）内積の最も小さい列（複数存在するなら全て）を列集合Ｃ（ｉ）から取り除いたものを行集合Ｃ（ｉ＋１）とする（ステップＳ３５−２）。
（ｃ−３）行集合Ｒ（ｉ）を行集合Ｒ（ｉ＋１）とする（ステップＳ３６−２）。
（ｄ）Ｒ（ｉ＋１）×Ｃ（ｉ＋１）をＭ（ｉ＋１）とする。
【００４６】
また、部分行列Ｒ（ｉ）×Ｃ（ｉ）に対する１回の内積計算のアルゴリズムは、次のようになる。Ｒ（ｉ）の要素を格納した配列をｒｏｗｓ、Ｃ（ｉ）の要素を格納した配列をｃｏｌｕｍｎｓとする。以下は行縮退についてのものである。列についても同様である。
（手順１）ｒｏｗｓの各要素に対応する内積の配列ｉｐ［ｒ］を用意する。各要素の値は０とする（図７参照）。
（手順２）ｃｏｌｕｍｕｓとｒｏｗＥｎｔｒｙ［ｒ＿ｂ］の共通要素を求める。その結果を配列ｃｏｍｍｏｎに格納する（例えば、ｃｏｍｍｏｎ＝｛Ｃ，Ｆ，Ｊ，Ｎ．Ｏ｝）。
（手順３）ｒｏｗの各要素ｒについて、ｃｏｍｍｏｎとｒｏｗＥｎｔｒｙ［ｒ］の共通要素数を求め、配列ｉｐ［ｒ］の値とする。
【００４７】
ｒｏｗＥｎｔｒｙの１行あたりの平均要素数をｎｒ、集合ＡとＢの共通要素を列挙する計算量をＯ（｜Ａ｜＋｜Ｂ｜）とすると、（手順２）の計算量はＯ（｜Ｃ｜＋ｎｒ）となる。ｃｏｍｍｏｎの要素数をｍｉｎ（｜Ｃ｜，ｎｒ）とすると、（手順３）では、１つのｒに対してＯ（ｎｒ＋ｍｉｎ（｜Ｃ｜，ｎｒ））＝Ｏ（｜Ｃ｜＋ｎｒ）となる。これを｜Ｒ｜回繰り返すので、計算量はＯ（｜Ｒ｜｜Ｃ｜＋ｎｒ））＝Ｏ（｜Ｒ｜｜Ｃ｜＋｜Ｒ｜ｎｒ）となり、これが行の内積計算量を支配する。同様に、列の内積計算はＯ（｜Ｒ｜｜Ｃ｜＋｜Ｃ｜ｎｃ）となる。
なお、内積の計算が必要になるのは、縮退方向がその直前と入れ替わったときのみである。同じ方向の縮退方向が続くときは、その前の内積計算の結果をそのまま用いることができる。
削除操作ではｉｐの最小値を求める必要がある。行方向の場合、要素数｜Ｒ｜の配列を一つずつ見ていくことで実現できるため、Ｏ｜Ｒ｜、列ならＯ｜Ｃ｜となる。よって縮退操作の計算量は内積計算量に支配される。
【００４８】
部分行列データの縮退過程は、図８に示すように、部分行列を節点、１回の行縮退と列縮退を枝とした有向グラフで表現することができる。このグラフを縮退グラフとよぶ。図８の縮退グラフは、図６の行列Ｍ０を始点とする縮退グラフであり、Ｍ１，Ｍ２，Ｍ３は図６のＭ１，Ｍ２，Ｍ３に対応する。なお、図８では、０のデータ要素を白抜きで、１のデータ要素を網掛けで示している。また、各行列の下の数値は、密度を示している。
以下では、縮退グラフ中の部分行列をそれに相当する節点を同一視する。図８のｒとｃはそれぞれ行縮退と列縮退による節点の遷移を示し、以下ではそれぞれｒ遷移、ｃ遷移とよぶ。行列Ｍに行縮退を施した行列をｒ（Ｍ）、列縮退を施した行列をｃ（Ｍ）とする。縮退グラフの経路を縮退経路とよぶ。縮退グラフは必ず、始点が初期部分行列、終単が基準要素である束になる。このように表現すると、本方式の処理過程は、縮退グラフ上で望ましい部分行列を探索するグラフ探索と捉えることができる。縮退グラフ上のグラフ探索アルゴリズムは前記縮退方向決定関数によって実行される。この関数の構成は、応用によって変わる出力に対する要求や処理時間に対する制約などによって、異なるものとなる。
【００４９】
例えば、処理時間に対する制約が弱く、出力部分行列に対する要求が厳しい場合を考える。このときの縮退方向決定関数は、縮退グラフを全探索して、最善の部分行列を選択し、その部分行列への経路を順に返すものになる。さらに、要求間に矛盾が生じたとき、どの要求を優先して達成し、どの要求を緩めるかの方針が問題によって変わるが、その方針も前記関数に含めることができる。
反対に、処理時間に対する制約が強く、出力に対する要求が緩い場合を考える。このときの縮退方向決定関数は、可能な限り少数の部分行列のみを構成することで、要求をできるだけ満たす出力をする必要がある。部分行列の構成回数が最も少なくなる関数は、現在の部分行列のみから縮退方向を決定するものである。
この関数を用いると、縮退グラフ上での初期部分行列から出力部分行列までの経路上の部分行列しか構成されない。このような関数のうち最も単純なものは、現在の部分行列の行数と列の比を、要求として与えられる行数と列数の比と比較し、それらを近づける方向に縮退するものである。
すなわち、与えられた比に比べて現在の行が大きければ行を縮退し、列が大きければ列を縮退する。この関数に必要な処理時間は部分行列のサイズによらず一定であり、除算と減算１回ずつのみで実現することが可能である。この単純な縮退方向決定関数は、処理速度の点で望ましい上に、縮退グラフの単調変化する性質を利用する要求、すなわち最小行数、最小列数、最小面積、０要素の存在保証を必ず満たすことができる。しかし、最小密度と行列数比の制御に関しては、必ず満たすことを保証できない。
【００５０】
［処理の高速化１：初期部分行列データの縮小化］
処理の高速化は、例えば、初期部分行列データＭ０を小さくすることによって達成できる。初期部分行列データＭ０を小さくする方法は、少なくとも、２つある。１つは、ＲＬ×ＣＬではなくＲＳ×ＣＳを利用するものである。ただし、ＲＳ×ＣＳは、前述のように、応用目的によっては用いることができない場合がる。もう一つの方法は、ＲＬのうち、基準行ｒ＿ｂとの共通要素数の多い行を上から所定数を取り出して初期部分行列の行とし、列についても同様にするものである。これは、初期部分行列で内積の少ない行や列は早い段階の縮退で取り除かれる可能性が大きいので、これらを初期部分行列に含めずとも出力に大きな影響はないと考えられるからである。
【００５１】
この処理のためには、前述の初期部分行列データＭ０の行集合を求める方法（段落００３８参照）のアルゴリズムを次のように変更する。前記方法の（手順３）では、ｒｏｗｓの各データをソートし、重複要素を削除していたが、ｒｏｗｓから重複要素を削除する代わりに、各行番号ｒの重複回数を数え、行番号ｒを重複回数でソートし、ｒｏｗｓの端から一定の個数の行番号ｒを取り出す、というものである。列についても同様に行う。このときも計算量はＯ（ＮｌｏｇＮ）となる。
この方法は、高速化を達成するとともに、処理時間を一定に近づける効果を持つ。実施形態に係るＭＣにといて、計算時間を多く消費するのは初期部分行列データやそれに近い部分行列データである。そのため、初期部分行列データが行列中の「１」要素の分布によって決められるなら、計算時間も行列中の「１」要素の分布によって決められることになる。それに対してこの方法では、部分行列のサイズを常に一定以下に抑えることができるため、処理速度をアルゴリズムで制御することができる。
この方法は、空行や空列を含むことがあるため、縮退グラフの性質を保証するには、小さくなった初期部分行列の行と列の内積を計算し、内積０のものは排除した上で、それを初期部分行列データＭ０とする必要がある。この処理も、既に部分行列データが小さいため、計算時間を多く消費することはない。なお、上記２つの方法は組み合わせることができる。すなわち、ＲＳの中から、基準行と多くの共通要素を持つものを初期部分行列データＭ０の行として選ぶことも可能である。
【００５２】
［処理の高速化２：縮退回数の減少］
処理の高速化方法として、縮退回数を少なくすることが考えられる。縮退操作の回数を減らすためには、削除操作において、内積が採用の行・列だけでなく、内積の小さい行・列を所定の割合で取り除けばよい。この方法では、例えば、１０００×２０００お部分行列データに対して、８割を削除すると指定すれば、行ならは８００行が、列ならば１６００列が一度の操作で取り除かれる。８００番目の行と同じ内積の行があった場合、それらの行も同時に削除する。列についても同様である。
この方法を縮退グラフの上で考えると、１度にｒ遷移とｃ遷移を同じ方向にまとめて行うことに相当する。以下では、この縮退方法を割合縮退とよび、内積最小の行・列のみを削除する方法を最小値縮退とよぶ。割合縮退で一度に取り除かれる行数・列数の割合を縮退率とよぶ。
【００５３】
なお、割合縮退を用いる場合、終了条件を満たす部分行列を発見したとしても、より適切な部分行列が縮退前の部分行列との間に存在する可能性がある。そのため、ある部分行列が終了条件を満たした場合、直前の部分行列から最小値縮退、あるいは割合がより低い割合縮退を行うことで、より適切な部分行列を求めることができる。
また、縮退率は、各縮退操作において一定である必要がなく、縮退操作ごとに変化させてもよい。例えば、縮退率を徐々に小さくしていけば、高速化と部分行列の適切化の調和を図ることができる。
【００５４】
［類似性の演算の他の例］
上記説明では、類似性の演算にベクトルの内積を用いていたが、これは他の手段でもよい。例えば、ＩＵ比を用いた類似性演算でもよい。ここでは、２つの２値ベクトルのＩＵ比を、［ベクトルの共通部分の要素数÷ベクトルの和集合の要素数と定義する。例えば，Ａ＝（００１１００１１）、Ｂ＝（０１０１０１０１）とすると、ＡＢのＩＵ比は共通部分の要素数が２，和集合の要素数が６のため、１／３となる。このような演算方法は、１が非常に多いベクトルと１が少ないベクトルとの類似性を相対的に低くするために有効である。
なお、類似性の演算は、ＩＵ比以外にも様々な方法を採用することができる。
【００５５】
［基準行・列が複数の場合］
上記説明では、単一の基準行、単一の基準列を想定していたが、これらは複数でもよい。すなわち、基準要素は複数でもよい。本方法を文書検索システムに応用する場合、特定の文書に関連する文書群（行）とそれらに含まれる単語群（列）を抽出するには、基準行は単一でよいが、基準列はその文書に含まれる複数の単語となる。
ここでは、単一基準行、複数基準列のアルゴリズムについて説明するが、複数基準行・単一基準列でも、複数基準行・複数基準列でも同様である。
【００５６】
（手順１）基準行をｒ＿ｂ、基準列をｃ＿ｂをとする。ｒ＿ｂは単一、ｃ＿ｂは複数とする。
（手順２）ｒ＿ｂとｃ＿ｂを用いて初期部分行列Ｍ０を作る。ここで、Ｍ０は、ｃ＿ｂの中のどれか一つを含む行とする。Ｍ０の行集合をＲ（０）、列集合をＣ（０）とする。
（手順３）ｉ＝０，１，２，３・・・に関して、終了条件を満たすまで以下を繰り返す：
（手順３−１）縮退方向決定関数が停止を出力すればＭｉを返して終了する。それ以外なら、この関数が示す方向に縮退する。行縮退の場合は（手順３−２）へ、列縮退の場合は（手順３−６）へ続く。
（手順３−２）Ｍｉの各行に対して、基準行ｒ＿ｂとの内積を求める。
（手順３−３）内積の最も小さい行（複数存在するなら全て）をＲ（ｉ）から取り除いたものをＲ（ｉ＋１）とする。
（手順３−４）Ｃ（ｉ）をＣ（ｉ＋１）とする。
（手順３−５）Ｒ（ｉ＋１）×Ｃ（ｉ＋１）をＭ（ｉ＋１）とし、（３−１）に戻る。
（手順３−６）Ｍｉの各列を正規化（詳細は後述）し、ｃ＿ｂに含まれる各列との内積の平均値をとる。ただし、内積計算においてｒ＿ｂは含まない。
（手順３−７）内積の最も小さい列（複数存在するなら全て）をＣ（ｉ）から取り除いたものをＣ（ｉ＋１）とする
（手順３−８）Ｒ（ｉ）をＲ（ｉ＋１）とする
（手順３−９）Ｒ（ｉ＋１）×Ｃ（ｉ＋１）をＭ（ｉ＋１）とし、（手順３−１）に戻る。
【００５７】
基準行ｒ＿ｂが複数の場合には、上記（手順３−２）を次のようにすればよい。
（手順３−２’）Ｍｉの各行を正規化（詳細は後述）し、ｒ＿ｂに含まれる各行との内積の平均値をとる。ただし、内積計算においてｃ＿ｂは含まない。
【００５８】
［正規化について］
正規化とは、ベクトル（行又は列）の各要素間の比率を保ったまま、各要素の２乗の和が１になるように、数をかけて、ベクトルの値を変えることをいう。
ある列ｃと基準列ｃ＿ｂの内積を求める場合を考えると、具体的には、次のようになる。ここで、各列ベクトルは基準行ｒ＿ｂを除いて次のように成っているものとする。
ｃ：［１１１１１１１１０００００００］
ｃ＿ｂ：［００００１１１１１１１００００］
【００５９】
列ｃの有意なデータ要素数は８なので、各要素を√８で割って、[１／√８ １／√８ １／√８ １／√８ １／√８ １／√８ [１／√８ １／√８ ０００００００]とする。
同様に、ｃ＿ｂ（１要素数は７）も各要素を√７で割って、［００００ １／√７ １／√７ １／√７ １／√７ １／√７ １／√７ １／√７ ００００］とする。
以上により、正規化が終了する。
正規化したｃとｃ＿ｂの内積をとる。両方のベクトルで共通して０以外の値を持っている４つの要素だけを見ればいいので、（１／√８）×（１／√７）×４＝４√５６が得られる。
【００６０】
より具体的に、データ構造上での手順を説明すると次の通りである。
まず、列ｃ中の「１」要素が存在する行番号の配列をｖｅｃ＿ｃ、列ｃ＿ｂで「１」要素が存在する行の番号の配列をｖｅｃ＿ｃｂとする。どちらの配列もソート（昇順ソート）されている。
続いて、ｖｅｃ＿ｃとｖｅｃ＿ｃｂの共通要素を全て列挙して、配列ｖｅｃ＿ｉｎｔｅｒｓｅｃｔｉｏｎに格納する。
さらに、ｖｅｃ＿ｃの要素数の平行根（上記例だとＰ＝√８）、ｖｅｃ＿ｃｂの要素数の平方根をｑ（上記例だとｑ＝√７）、ｖｅｃ＿ｃの要素数をｒ（上記例だと４）とする。この結果、ｒ（ｐｑ）が正規化内積となる。
【００６１】
複数の基準列がある場合に、単に、各基準列との類似性を示す数値（類似度）の平均をとる等によって、列削除のための値を求めてもよいが、ｐやｑといった、要素数を考慮して類似性の演算を行うことで、各ベクトル中に含まれる１（有意なデータ要素）の数が異なる基準列が複数あっても、これによる類似度への影響を避けることができる。すなわち、正規化を行うことで、対比される列における有意な要素数が多くても、類似性を示す数値が大きくなりにくく、有意な要素数が少ない場合の類似度との比較をすることができるようになって、複数の基準列があっても問題が生じにくくなる。
また、正規化については、行についても全く同様に行うことができる。
【００６２】
実施形態に係る方法の応用としては、次のようなものがある。例えば、ＷＷＷでの検索システムその他の文書検索システムにおいて、ユーザがキーワード検索を行った結果、システムがキーワードを含む文書（ＷＷＷページ）リストを（画面）出力した後に、ユーザがそのリストの中からある文書を選択した場合に、選択された文書に関連する文書をシステムが抽出するのに実施形態に係る方法を使用することができる。
すなわち、例えば、文書を行、キーワード（単語）を列として持つ２次元行列データにおいて、基準行をユーザが選択した文書、基準列をユーザが入力したキーワードとして、実施形態に係る方法を使用することで、関連する文書を効率よく検索することが可能となる。
また、ＷＷＷ上のショッピングサイトにおいて、ユーザを行、ユーザが訪れた商品ページを列とする２次元行列データを具備しておき、ログインしてきたユーザを基準行、当該ユーザが訪れた商品のページを基準列として、実施形態に係る方法を使用することで、当該ユーザと似た傾向を有する他のユーザが訪れたページをリコメンドすることができる。
【００６３】
なお、本発明は、上記実施形態に限定されるものではない。本発明は、特許請求の範囲に記載した事項の範囲内で様々な変形が可能である。
【図面の簡単な説明】
【００６４】
【図１】孤立した行・列が存在する行列である。
【図２】横長部分行列と縦長部分行列である。
【図３】疎な大規模行列データＭである。
【図４】実施形態に係る方法を示すフローチャートである。
【図５】行列データＭのデータ構造である。
【図６】部分行列データの縮退を示す図である。
【図７】配列ｉｐである。
【図８】縮退グラフである。
【符号の説明】
【００６５】
ｒ＿ｂ 基準行
ｃ＿ｂ 基準列
【技術分野】
【０００１】
本発明は、密度が高い部分行列データをコンピュータによって抽出する方法、そのコンピュータシステム及びコンピュータプログラムに関するものである。
【背景技術】
【０００２】
大量のデータから特徴を抽出する手法として、データマイニングが広く用いられている。特に、インターネットの普及により、ＷＷＷから得られるデータにマイニングを行うことにより、有益な情報を得る応用はＷＷＷマイニングと呼ばれ、ＷＷＷ検索エンジンやマーケティングなどに幅広く応用されている。
データマイニングの対象となるデータの表現形式としては、２値行列による表現が用いられることがある。例えば、顧客の購買履歴は、縦軸（行）を顧客、横軸（列）を商品とし、特定の顧客が特定の商品を購入したとき、対応する行列の要素を「１」とし、購入していないときに行列の要素を「０」とすることにより、２値行列で表現することができる。
【０００３】
このような、行列データは、一般に大規模疎行列となる。すなわち、行列の行数（顧客数）、列数（商品）数は大きいが、値が「１」となる行列のデータ要素は、値が「０」となる行列のデータ要素に比べて圧倒的に少ない。
このような、大規模な疎行列のままでは、有益な情報を把握しにくいが、大規模疎行列から値が「１」となる要素を多く含む密な部分行列を抽出することができれば、マーケティング等において有用な情報となる。すなわち、上記の例では、密な部分行列が得られれば、購買傾向の似た顧客群と商品群を同時に得られるからである。
【０００４】
このように、大規模疎行列から密な部分行列を抽出する操作は、非特許文献１においては、マトリクスクラスタリングとよばれている。マトリクスクラスタリングは、ＷＷＷマイニングにおいても、ユーザとユーザが見たページの関係や、ページとページ内に含まれるキーワードの関係を同時に得ることに応用できるため、有効な手法である。
【０００５】
マトリクスクラスタリングのリアルタイムの応用例として、リコメンデーションシステムがある。例えば、ＷＷＷ上でのショッピングサイトにおいて、上記のようにユーザと購入した商品の履歴を２値行列で保持するものとする。
あるユーザが、そのショッピングサイトにログインしてきたとき、大規模疎行列から、そのユーザに関連する密な部分行列をリアルタイムで抽出することができれば、ログインしたユーザに対して、適切な商品をリコメンドすることができる。
すなわち、密な部分行列を得られれば、そのユーザと似た購買傾向を持つ他のユーザを抽出でき、密な部分行列において、そのユーザは購入していないが、他のユーザは購入している商品を見つけることができれば、その商品をそのユーザに奨めることができる。
このような、リコメンデーションシステムは、ＷＷＷのパーソナライズとして今後の発展が大いに期待されている分野である。
【０００６】
マトリクスクラスタリングの他の応用例として、文書検索システムがある。個々の文書を横軸（列）に、文書に含まれるキーワードを縦軸（行）にした行列表現をとる。特定の文書の中に特定のキーワードが含まれるときに、対応する行列要素を１とし、含まれないときに０とする。あるキーワードが止定されたとき、そのキーワードに関連する密な部分行列を抽出することができれば、指定されたキーワードに関連した文書群とキーワード群が得られる。この場合、通常の文書検索システムとは異なり、入力されたキーワードを直接含まない文書でも、含まれるキーワードが類似していれば検索結果に含まれるという特徴がある。
【０００７】
従来のマトリクスクラスタリングのアルゴリズムとして、非特許文献１には、行・列置換法とピンポン法が提示されている。
行・列置換法では、元の疎行列の行同士、あるいは列同士を入れ換える操作を繰り返す。例えば、行列の左上に１となる要素が集まるように、行同士、列同士を入れ替えることにより、密な部分行列を疎行列の左上に形成することができる。
【０００８】
ピンポン法では、初期値となる行より列方向にマーカ伝播を行い、各列では受信したマーカ数により枝刈りを行い、多くのマーカを受信した列のみを操作の対象とする。次に列から行方向にマーカを伝播し、各行では受信したマーカ数により枝刈りを行い、多くのマーカを受信した行のみを操作の対象とする。ピンポン法は、これらの操作を繰り返すことにより、密行列を生成する手法である。
【非特許文献１】小柳滋、久保田和人、仲瀬明彦：Matrix Clustering：ＣＲＭ向けの新しいデータマイニング手法、情報処理学会論文誌、Vol.42、No.8、pp.2156-2166、（２００１）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１では、ピンポン法が行・列置換法に比べて性能や、密行列の性質において優れていることが示されている。
しかし、上記のような応用にピンポン法を適用する場合には、初期値として指定された行あるいは列を含まない密な部分行列を出力する場合があることが、問題となる。例えば、ピンポン法を前記リコメンデーションシステムへ応用した場合に、初期値としてあるユーザが指定されたのに、密な部分行列がそのユーザを示す行を含まないということは、要求と全く異なる結果が出力されるおそれがある。
また、ピンポン法を文書検索システムに応用した場合にも、同様に、要求と関連のない結果が出力されるというおそれがある。
【００１０】
そこで、本発明は、抽出された密な部分行列が必要な行や列を含むことができる、新たな方法等を提供することを目的の一つとする。
【課題を解決するための手段】
【００１１】
本発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除するステップ、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除するステップ、
を有することを特徴とする方法である。
【００１２】
上記方法において、有意なデータ要素は、具体的な値としては、例えば「１」で表され、非有意なデータ要素は、具体的な値としては、例えば「０」で表されるものである。上記方法によって「１」などで表される有意なデータ要素の密度が高い部分行列データが得られる。
そして、上記方法によれば、基準行と基準列とが決定され、基準行・基準列との類似性の低い行・列から削除されるため、密な部分行列データを生成しても、当該部分行列データには基準行と基準列とが含まれることが保証される。
なお、上記（ｃ）のステップと（ｄ）のステップは、繰り返し行うことにより、行列データを次々に縮退させて、有意なデータ要素の密度を高めていくことができる。
【００１３】
前記（ｃ）のステップ、又は（ｄ）のステップにおいて、行又は列の削除を行う際に、指定された所定割合の数の行又は列を一括して削除するのが好ましい。
指定された所定割合の数の行又は列を一括して削除することにより、（ｃ）のステップや（ｄ）のステップを何度も繰り返し行わなくても、少ない回数で、大きな疎行列を小さくすることができ、効率が良くなる。
【００１４】
前記（ａ）のステップにおいて、複数の基準行が決定された場合には、前記（ｃ）のステップに代えて、下記（ｅ）のステップを実行するのが好ましい。
（ｅ）前記行列データの各行と前記各基準行との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準行と非基準行にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準行との類似性が低い行を削除するステップ。
基準行が複数ある場合、それぞれの基準行に含まれる有意なデータ要素の数が異なることがあり、この場合、ある行と各基準行との類似性の演算を行うと、有意なデータ要素の数が多い基準行との類似度の方が高くなってしまい、他の基準行との類似度が相対的に低くなることになる。このように、有意なデータ要素の数の差によって、それぞれの基準行の間に、不必要な差が生じてしまうが、有意なデータ要素の数を考慮して類似性の演算を行うことにより、この問題を解消できる。
【００１５】
また、複数基準列の場合も上記複数基準行の場合と同様にするのが好ましい。
すなわち、前記（ｂ）のステップにおいて、複数の基準列が決定された場合には、前記（ｄ）のステップに代えて、下記（ｆ）のステップを実行するのが好ましい。
（ｆ）前記行列データの各列と前記各基準列との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準列と非基準列にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準列との類似性が低い列を削除するステップ。
【００１６】
演算を高速化するため、前記第（ｃ）のステップ、又は（ｄ）のステップの実行前に、下記（ｇ）のステップを実行して初期部分行列データを生成し、その初期部分行列データに対して、前記（ｃ）のステップ、又は（ｄ）のステップを行うのが好ましい。
（ｇ）前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行と、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列と、からなる初期部分行列データを生成する。
【００１７】
上記初期部分行列データにおいては、基準行又は基準列と共通するデータ要素を持たない行又は列は存在しなくなる。共通するデータ要素を持たない行又は列は、類似性を演算すると、いずれ削除されるものであるから、（ｃ）のステップ、又は（ｄ）のステップの実行前に初期部分行列データを生成して、これに（ｃ）のステップ、又は（ｄ）のステップを実行することで、（ｃ）（ｄ）のステップを高速に行える。
【００１８】
前記（ｇ）のステップにおいて、前記初期部分行列データは、前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行のうち、前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素の数が多い所定数の行と、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列のうち、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素の数が多い所定数の列と、を取り出して生成されるのが好ましい。
基準行又は基準列と共通するデータ要素を持つ行又は列であっても、その共通する数が少ない場合には、類似性を演算するといずれ削除される可能性が高いため、そのような行又は列は、初期部分行列データから取り除くことで、その後の演算をより高速に行うことができる。
【００１９】
他の観点からみた本発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｈ）前記基準行において有意なデータ要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除するステップ、
（ｉ）前記基準列において有意なデータ要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除するステップ、
を有することを特徴とする方法である。
【００２０】
上記方法によれば、基準行と基準列とが決定され、基準行・基準列と共通の有意なデータ要素が存在しない行又は列を削除して部分行列データを生成することで、行列の密度を高めることができるとともに、密な部分行列データを生成しても、当該部分行列データには基準行と基準列とが含まれることが保証される。
なお、基準行・基準列と共通の有意なデータ要素が存在しない行又は列を削除するだけでは、行列の大きさを十分に小さくできない場合があるため、他の方法によって、行列をさらに小さくし、密度を上げるようにしてもよい。
【００２１】
コンピュータシステムに係る本発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するものであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除する手段、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除する手段、
を有することを特徴とするものである。
また、コンピュータプログラムに係る本発明は、コンピュータを、前記コンピュータシステムにおける（ａ）（ｂ）（ｃ）（ｄ）のそれぞれの手段として機能させるためのものである。
【００２２】
他の観点からみたコンピュータシステムに係る発明は、有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するものであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｈ）前記基準行において有意な要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除する手段、
（ｉ）前記基準列において有意な要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除する手段、
を有することを特徴とするものである。
また、他の観点からみたコンピュータプログラムに係る本発明は、コンピュータを、前記コンピュータシステムにおける（ａ）（ｂ）（ｈ）（ｉ）のそれぞれの手段として機能させるためのものである。
【発明の効果】
【００２３】
本発明によれば、必要な行や列を、基準行・基準列として決定し、これらの基準行・基準列が残るように密な部分行列データを抽出することができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の好ましい実施形態を図面に基づいて説明する。
［用語と標記法について］
ここでは、複数の行の間で共通して１となる列をそれらの行の共通要素とよぶ。また、列についても同様に、複数の列の間で共通して１となる行をそれらの列の共通要素とよぶ。
文中での行列の標記法は、行の集合と列の集合の間に×を置くか、行数と列数の間に×を置くものとする。行列の一つの要素は、行の名前と列の名前を並べ、（）で括ることで表記する。
【００２５】
［実施形態の方法で要求される事項］
ここで説明する実施形態に係る部分行列データの抽出方法は、行列中において、注目する行と列に関連する行と列を同時に発見する操作であり、マトリクスクラスタリングとよばれる。なお、以下では、マトリクスクラスタリングを、単に「ＭＣ」ということがある。
ここでのＭＣは、主に、有意なデータ要素である「１」と非有意なデータ要素である「０」の２値要素を対象にし、「１」要素が密に存在する部分行列を発見するために行われる。
このＭＣは、リコメンデーションシステムや文書検索システムへの応用をより適切に行うため、次の要求を満たすことが望ましいものである。
（要求１）部分行列が孤立した行又は列を含まない。
（要求２）部分行列の行数と列数の比を制御できる。
（要求３）部分行列が注目すべき行と列を同時に含むように制御できる。
（要求４）部分行列の特定の行又は列が０（非有意なデータ要素）を含むように制御できる。
【００２６】
上記（要求１）は、図１（ａ）の行ｄと列Ｆのように、他の行及び列との共通要素を持たない行又は列を含んでいる場合をいう。また、図１（ｂ）は、他の行と共通要素を持たない行の一種である空行ａを含んでいる。
図１（ａ）の孤立した行ｄと列Ｆや、図１（ｂ）の行ａは、他の行及び列との間に関連性がなく、部分行列が関連した行と列の集合を表すべきものと考えた場合、孤立した行と列を含むことは許されない。つまり、孤立した行と列を含む部分行列に基づいて、リコメンドや、文書検索における関連文献の出力を行うには不適切である。そこで、上記（要求１）が必要となる。
【００２７】
上記（要求２）のように、部分行列の行数と列数の比を制御できると、部分行列の使用目的等に応じて、部分行列に必要な行数と列数が異なる場合にも対応でき好ましい。
つまり、図２（ａ）から、密度（部分行列中の「１」の数／行列の全要素数）が１で、可能な限り大きい部分行列を取り出すと、横長の部分行列（図２（ｂ））と、縦長の部分行列（図２（ｃ））の２つが得られる。横長の部分行列は列の間よりも、行の間の共通要素数を多くすることを優先した結果であり、縦長の部分行列は行よりも列を優先した結果である。例えば、行を文書、列をそのキーワードとして類似文書を探すことを考えると、縦長の部分行列（図２（ｃ））が表すものは、頻繁に使われるキーワード、つまり大きな分野を示すキーワードで一致する文書の集合であり、横長の部分行列（図（ｂ））が表すものは、使用される頻度の低いキーワード、つまりより細分化された分野を示すキーワードまで一致する文書の集合である。このような使い分けをするには、上記（要求２）が必要となる。
【００２８】
上記（要求３）のように、部分行列が注目すべき行と列を同時に含むように制御できると、得られた部分行列に注目すべき行と列が含まれていることを保証でき、得られた部分行列の適切さが向上する。
例えば、複数の分野にまたがる文書の場合、どのキーワードに着目するかで、関連する文書の集合が異なってくる。このような区別をするには、ＭＣアルゴリズムが、注目すべき行（文書）だけでなく、列（キーワード）も取り扱えるようにして、部分行列が注目すべき行と列を同時に含むように制御できるようにすることが好ましく、上記（要求３）が必要となる。
【００２９】
上記（要求４）のように、部分行列の特定の行又は列が０を含むように制御できると、確実にリコメンドをすることができる。例えば、オンライン書店で、ユーザに書籍を推薦することを考える。ユーザを行、書籍を列とし、ユーザが購入した書籍に該当する要素を「１」とした行列を用いると、得られた密な部分行列において、指定されたユーザを示す行には、少なくとも一つの０が含まれていなければ、推薦すべき書籍が見つからないから、何も出力できないという問題が発生する。この場合、部分行列において、ユーザを示す行は、必ず０を含む必要がある。また、列についても同様である。そこで、上記（要求４）が必要となる。
【００３０】
［実施形態］
本実施形態で説明する方法は、リコメンデーションシステムの機能を有するＷＷＷサーバ、又は文書検索コンピュータシステムなどのコンピュータシステムにおいて、記憶装置に記憶されたコンピュータプログラムに基づき、当該コンピュータシステムによって実行されるものである。なお、後述の他の実施形態においても同様である。
【００３１】
図３は、有意なデータ要素である「１」の密度が疎である大規模行列データＭの一例を示している。この行列データＭは、行ａ〜ｊが顧客を示しており、列Ａ〜Ｏが商品を示す２次元行列である。行列の各データ要素としては、「１」（有意なデータ要素）と「０」（非有意なデータ要素）の２値をとるものであり、例えば、行列データＭの［ｅ，Ｇ］のデータ要素が「１」であるのは、顧客ｅは商品Ｇを購入したことがある、ということを示している。コンピュータには、その記憶手段に、図３と同様の２次元配列データ構造又は、図３の２次元データと実質的に同じデータ内容を示すデータ構造により記憶させることができる。
【００３２】
具体的には、行列データの構造は、図５に示すようなものとすることができる。行列Ｍの行エントリを配列データ：ｒｏｗＥｎｔｒｙ［ｒ］（ｒは行ａ〜ｊを表す）とし、列エントリを配列データ：ｃｏｌｕｍｎＥｎｔｒｙ［ｃ］（ｃは列Ａ〜Ｏを表す）とする。
図５のデータ構造は、図３の行列Ｍに対応しており、配列ｒｏｗＥｎｔｒｙ［ｒ］には、ｒで示される行において「１」の要素を持つ列が格納されている。例えば、ｒｏｗＥｎｔｒｙ［ａ］には、｛Ｃ，Ｆ，Ｊ，Ｎ，Ｏ｝が格納されている。
同様に、配列ｃｏｌｕｍｎＥｎｔｒｙ［ｃ］には、ｃで示される行において「１」の要素を持つ行が格納されている。例えば、ｃｏｌｕｍｎＥｎｔｒｙ［Ｆ］には、｛ａ，ｃ，ｄ，ｈ｝が格納されている。
なお、行列データＭは、顧客が商品を購入する度に、データが更新される。
【００３３】
図４は、実施形態に係る方法を示している。この方法は、基準行と基準列の決定（ステップＳ１）、初期部分行列データの生成（ステップＳ２）、部分行列データの縮退操作（ステップＳ３）とを含んでいる。
まず、行列データＭのデータ要素の中から一つの要素（後述の実施形態では複数のデータ要素の場合もある）を決定することで、基準行と基準列が決まる。以下では、基準行をｒ＿ｂといい、基準列をｃ＿ｂという。
基準要素の決定は、例えば、ＷＷＷ上でのショッピングサイトにおいて、ある「顧客ａ」がある「商品Ｆ」を購入、又はある「商品Ｆ」を購入検討のために見ること等によって、行われる。この場合、基準要素（ｒ＿ｂ，ｃ＿ｂ）＝（ａ，Ｆ）であり、基準行はａ、基準列はＦに決まったことになる。なお、基準行及び基準列を示す情報は、コンピュータの記憶手段に記憶される。
【００３４】
初期部分行列データＭ０の生成（ステップＳ２）は、行列データＭから、基準行ｒ＿ｂと基準列ｃ＿ｂを用いて作られる。
初期部分行列データＭ０の生成は、特許請求の範囲の（ｇ）のステップと同様の方法によって行われる。ここで、（ｇ）のステップは、「基準行ｒ＿ｂにおいて有意なデータ要素「１」が存在する列と同じ列に共通して存在する有意なデータ要素「１」を１個以上持つ行ｒと、前記基準列ｃ＿ｂにおいて有意なデータ要素「１」が存在する行と同じ行に共通して存在する有意なデータ要素「１」を１個以上持つ列ｃと、からなる初期部分行列データＭ０を生成する」というものである。
【００３５】
（ｇ）のステップの具体的な実行方法は、一つではない。初期部分行列データＭ０の行を示す行集合をＲ（０）、列を示す列集合をＣ（０）とすると、Ｒ（０）のデータとＣ（０）のデータを作る方法は、それぞれ、少なくとも２通りある。
［行集合Ｒ（０）の構成方法その１］
行列データＭの行のうち、ｒ＿ｂと共通要素を持つすべての行の集合Ｒ（０）を作る（以下、この場合のＲ（０）をＲＬという。なお、添え字の「Ｌ」は「loose」を示している。）。図３の行列データＭの場合、ＲＬは次のようになる。
ＲＬ＝｛ａ，ｃ，ｄ，ｅ，ｆ，ｈ，ｉ，ｊ｝
［行集合Ｒ（０）の構成方法その２］
行列データＭの行のうち、ｃ＿ｂに「１」の要素を持つ行のみからなる集合Ｒ（０）を作る（以下、この場合のＲ（０）をＲＳという。なお、添え字の「Ｓ」は「strict」を示している。）。図３の行列データＭの場合、ＲＳは次のようになる。
ＲＳ＝｛ａ，ｃ，ｄ，ｈ｝
【００３６】
［列集合Ｃ（０）の構成方法その１］
行列データＭの列のうち、ｃ＿ｂと共通要素を持つすべての列の集合Ｃ（０）を作る（以下、この場合のＣ（０）をＣＬという）。図３の行列データＭの場合、ＣＬは次のようになる。
ＣＬ＝｛Ｃ，Ｄ，Ｆ，Ｊ，Ｎ，Ｏ｝
［列集合Ｃ（０）の構成方法その２］
行列データＭの列のうち、ｒ＿ｂに「１」の要素を持つ行のみからなる集合Ｃ（０）を作る（以下、この場合のＣ（０）をＣＳという）。図３の行列データＭの場合、ＣＳは次のようになる。
ＣＳ＝｛Ｃ，Ｆ，Ｊ，Ｎ，Ｏ｝
【００３７】
上記２つの行集合ＲＬ，ＲＳと、２つの列集合ＣＬ，ＣＳとの組み合わせで、計４種類の初期部分行列データＭ０を作ることができる。すなわち、ＲＬ×ＣＬ，ＲＬ×ＣＳ，ＲＳ×ＣＬ，ＲＳ×ＣＳの４種類である。これらは、行列データの使用目的に応じて使い分けられるべきものである。例えば、基準行ｒ＿ｂや基準列ｃ＿ｂが前記（要求４）を満たすべきものであるなら、ＲＳやＣＳは使えない。なぜなら、ＲＳを使うときは、初期部分行列データ中の基準列ｃ＿ｂが、ＣＳなら基準行ｃ＿ｒが全て「１」要素で占められるからである。なお、ＲＳ⊆ＲＬ、ＣＳ⊆ＣＬが成立するため、４種類の初期部分行列データのうち、ＲＳ×ＣＳが最も小さい部分行列となり、ＲＬ×ＣＬが最も大きい部分行列となる。
図６（ａ）に示す初期部分行列データＭ０は、ＲＬ×ＣＬである。すなわち、行列データＭに対して、［行集合Ｒ（０）の構成方法その１］と［列集合Ｃ（０）の構成方法その２］の操作を行うことによって生成されたものである。
なお、最も小さい部分行列ＲＳ×ＣＳの場合Ｍ０＝｛ａ，ｃ，ｄ，ｈ｝×｛Ｃ，Ｆ，Ｊ，Ｎ，Ｏ｝となる。
【００３８】
ＲＬ×ＣＬの初期部分行列データＭ０の、より具体的な構成方法としては、次のようにすることができる。下記手順は、初期部分行列データＭ０の行集合を求める方法である。
（手順１）初期部分行列データＭ０の行番号を格納する配列データ：ｒｏｗｓを用意する。ｒｏｗｓは空で初期化する
（手順２）ｒｏｗＥｎｔｒｙ［ｒ＿ｂ］中の各要素ｃｉに対して、ｃｏｌｕｍｎＥｎｔｒｙ［ｃｉ］の全要素をｒｏｗｓにコピーする。
（手順３）ｒｏｗｓの各データをソートし、重複要素を削除する。
【００３９】
以上により、ｒｏｗｓに初期部分行列データを構成する行が存在することになる。
また、初期部分行列データＭ０の列集合を求める方法は下記手順のとおりである。
（手順１）初期部分行列データＭ０の行番号を格納する配列データ：ｃｏｌｕｍｕｓを用意する。ｃｏｌｕｍｕｓは空で初期化する。
（手順２）ｃｏｌｕｍｎＥｎｔｒｙ［ｃ＿ｂ］中の各要素ｒｉに対して、ｒｏｗＥｎｔｒｙ［ｒｉ］の全要素をｃｏｌｕｍｎｓにコピーする。
（手順３）ｃｏｌｕｍｎｓの各データをソートし、重複要素を削除する。
【００４０】
１つの行・列の平均「１」要素数をそれぞれｎｒ，ｎｃとすると、（手順２）のコピーは、ｎｒ回実行され、１回にコピーされる要素数はｎｃである。コピーが終了した時点で、ｒｏｗｓにはｎｒ・ｎｃ個の要素が格納されている。ｎｒ・ｎｃ＝Ｎとすると、コピーはＯ（Ｎ）となり、ソートをＯ（ＮｌｏｇＮ），重複要素の削除をＯ（Ｎ）とすると、この計算量はソートに支配され、Ｏ（ＮｌｏｇＮ）となる。
【００４１】
この初期部分行列データＭ０の生成処理は、本実施形態では、後述する部分行列データの縮退操作（ステップＳ３）の前処理として行われるが、初期部分行列データＭ０の生成処理は、他の方法による部分行列抽出アルゴリズムの前処理として行っても良い。
また、用途によっては、初期部分行列データＭ０の生成処理によって、十分に面積が小さく密な部分行列が得られる場合もあり、この場合は、初期部分行列データＭ０の生成処理に相当する処理だけで、処理を終了してもよい。
初期部分行列データＭ０の生成処理に相当する処理だけで部分行列データ抽出処理を終了してもよいことは、初期部分行列データＭ０の生成処理（ステップＳ２）と部分行列データの縮退操作（ステップＳ３）が基本的に共通していることを示している。
すなわち、初期部分行列データＭ０の生成処理（ステップＳ２）は、部分行列データの縮退操作（ステップＳ３）における「内積」をとったときに、その値が０又は小さい値となる行又は列に相当するものを初期の段階で一括して削除する処理と考えることができる。基準行又は基準列と内積とったときに値が小さくなる行又は列は、基準行又は基準列との類似性が低く、縮退操作を行えば、いずれ削除される可能性が高いものであるから、予め削除しておくことで、縮退操作を高速に行うことが可能となる。
【００４２】
部分行列データの縮退操作（ステップＳ３）は、主に、類似性演算（ステップＳ３４−１，Ｓ３４−２）と、削除操作（ステップＳ３５−１，Ｓ２５−２）とからなり、それぞれ、行方向の演算及び操作（ステップＳ３４−１，Ｓ３５−１）と、列方向の演算及び操作（ステップＳ３４−２，Ｓ３５−２）とがある。
行方向の類似性演算（ステップＳ３４−１）は、部分行列データの各行をベクトルとみなし、基準行との内積を求めることで、それらの行にスコアを付ける操作である。対象が２値行列であるため、２つの行の内積は、それらの行の共通要素数に等しい。共通要素数が大きければ行の間の類似性は高くなる。列方向の類似性演算（ステップＳ３４−２）も同様である。
行の削除操作（ステップＳ３５−１）は、類似性を示すスコアの最も小さい行を部分行列から排除するものである。列の削除操作（ステップＳ３５−２）も同様である。
【００４３】
図６の初期部分行列データＭ０に対して、まず、行縮退ｒを行うとすると、基準行ｒ＿ｂ＝ａであるから、各行の内積は、ｃとｈが５、ｄとｉが３、ｅとｆとｊが１となる。この結果に削除操作を行うと、内積最小の行ｅ，ｆ，ｊが取り除かれ、部分行列データＭ１（図６（ｂ））が作られる。
次に列縮退ｃを行う。基準列ｃ＿ｂ＝Ｆなので、各列の内積はＪとＮが４、ＣとＯが３、ＤとＬが１となり、内積最小のＤ，Ｌが削除され、部分行列データＭ２が得られる。さらに、行縮退ｒを行うと、密度１の部分行列データＭ３が得られる。
なお、部分行列データＭ３に対して、さらに行と列の縮退操作を１回ずつ適用でき、その結果、ａ×Ｆが得られる。
【００４４】
図６においては、行縮退ｒと列縮退ｃとが交互に行われているが、行と列のどちらを縮退するかは、縮退方向決定関数によって決定される（ステップＳ３２）。縮退方向の決定方法としては、交互とする他、行と列の比を用いてもよい。行と列の比を用いて縮退方向を決定する方法については後述する。また、縮退方向の順序は、出力に影響を与えるがこの点も後述する。
また、縮退方向決定関数は、縮退操作（ステップＳ３）を終了させる手段としても機能する。図６では、部分行列データの密度が１のＭ３が作られるまで処理が続いているが、縮退方向決定関数が適当な終了条件を持つことで、Ｍ３に至る前に縮退処理は終了する。
主な終了条件としては、部分行列データの最小密度がある。図６の処理を、最小密度０．８の終了条件で実行すれば、密度が０．８４となったＭ２で停止し、Ｍ２を出力とする。また、終了条件は、部分行列データの面積（データ要素数の数）であってもよいし、密度と面積の双方であってもよい。
【００４５】
ステップＳ３の縮退操作を図４に基づいて、詳細に説明すれば、次のとおりである。まず、カウンタ変数ｉを０に初期化し（ステップＳ３１）、ｉ＝０，１，２・・・に関して、終了条件を満たすまで次の処理を繰り返す（ステップＳ３８）。
（ａ）縮退方向決定関数が、その関数値Ｘ＝終了を出力すれば、部分行列データＭｉを出力して終了する。それ以外（Ｘ＝行縮退ｏｒＸ＝列縮退）なら、この関数が示す方向に縮退する（ステップＳ３２，Ｓ３３）。
（ｂ）行縮退出の場合：
（ｂ−１）部分行列データＭｉの各行に対して基準行ｒ＿ｂとの内積を求める（ステップＳ３４−１）。
（ｂ−２）内積の最も小さい行（複数存在するなら全て）を行集合Ｒ（ｉ）から取り除いたものを行集合Ｒ（ｉ＋１）とする（ステップＳ３５−１）。
（ｂ−３）列集合Ｃ（ｉ）を行集合Ｃ（ｉ＋１）とする（ステップＳ３６−１）。
（ｃ）列縮退出の場合：
（ｃ−１）部分行列データＭｉの各列に対して基準列ｃ＿ｂとの内積を求める（ステップＳ３４−２）。
（ｃ−２）内積の最も小さい列（複数存在するなら全て）を列集合Ｃ（ｉ）から取り除いたものを行集合Ｃ（ｉ＋１）とする（ステップＳ３５−２）。
（ｃ−３）行集合Ｒ（ｉ）を行集合Ｒ（ｉ＋１）とする（ステップＳ３６−２）。
（ｄ）Ｒ（ｉ＋１）×Ｃ（ｉ＋１）をＭ（ｉ＋１）とする。
【００４６】
また、部分行列Ｒ（ｉ）×Ｃ（ｉ）に対する１回の内積計算のアルゴリズムは、次のようになる。Ｒ（ｉ）の要素を格納した配列をｒｏｗｓ、Ｃ（ｉ）の要素を格納した配列をｃｏｌｕｍｎｓとする。以下は行縮退についてのものである。列についても同様である。
（手順１）ｒｏｗｓの各要素に対応する内積の配列ｉｐ［ｒ］を用意する。各要素の値は０とする（図７参照）。
（手順２）ｃｏｌｕｍｕｓとｒｏｗＥｎｔｒｙ［ｒ＿ｂ］の共通要素を求める。その結果を配列ｃｏｍｍｏｎに格納する（例えば、ｃｏｍｍｏｎ＝｛Ｃ，Ｆ，Ｊ，Ｎ．Ｏ｝）。
（手順３）ｒｏｗの各要素ｒについて、ｃｏｍｍｏｎとｒｏｗＥｎｔｒｙ［ｒ］の共通要素数を求め、配列ｉｐ［ｒ］の値とする。
【００４７】
ｒｏｗＥｎｔｒｙの１行あたりの平均要素数をｎｒ、集合ＡとＢの共通要素を列挙する計算量をＯ（｜Ａ｜＋｜Ｂ｜）とすると、（手順２）の計算量はＯ（｜Ｃ｜＋ｎｒ）となる。ｃｏｍｍｏｎの要素数をｍｉｎ（｜Ｃ｜，ｎｒ）とすると、（手順３）では、１つのｒに対してＯ（ｎｒ＋ｍｉｎ（｜Ｃ｜，ｎｒ））＝Ｏ（｜Ｃ｜＋ｎｒ）となる。これを｜Ｒ｜回繰り返すので、計算量はＯ（｜Ｒ｜｜Ｃ｜＋ｎｒ））＝Ｏ（｜Ｒ｜｜Ｃ｜＋｜Ｒ｜ｎｒ）となり、これが行の内積計算量を支配する。同様に、列の内積計算はＯ（｜Ｒ｜｜Ｃ｜＋｜Ｃ｜ｎｃ）となる。
なお、内積の計算が必要になるのは、縮退方向がその直前と入れ替わったときのみである。同じ方向の縮退方向が続くときは、その前の内積計算の結果をそのまま用いることができる。
削除操作ではｉｐの最小値を求める必要がある。行方向の場合、要素数｜Ｒ｜の配列を一つずつ見ていくことで実現できるため、Ｏ｜Ｒ｜、列ならＯ｜Ｃ｜となる。よって縮退操作の計算量は内積計算量に支配される。
【００４８】
部分行列データの縮退過程は、図８に示すように、部分行列を節点、１回の行縮退と列縮退を枝とした有向グラフで表現することができる。このグラフを縮退グラフとよぶ。図８の縮退グラフは、図６の行列Ｍ０を始点とする縮退グラフであり、Ｍ１，Ｍ２，Ｍ３は図６のＭ１，Ｍ２，Ｍ３に対応する。なお、図８では、０のデータ要素を白抜きで、１のデータ要素を網掛けで示している。また、各行列の下の数値は、密度を示している。
以下では、縮退グラフ中の部分行列をそれに相当する節点を同一視する。図８のｒとｃはそれぞれ行縮退と列縮退による節点の遷移を示し、以下ではそれぞれｒ遷移、ｃ遷移とよぶ。行列Ｍに行縮退を施した行列をｒ（Ｍ）、列縮退を施した行列をｃ（Ｍ）とする。縮退グラフの経路を縮退経路とよぶ。縮退グラフは必ず、始点が初期部分行列、終単が基準要素である束になる。このように表現すると、本方式の処理過程は、縮退グラフ上で望ましい部分行列を探索するグラフ探索と捉えることができる。縮退グラフ上のグラフ探索アルゴリズムは前記縮退方向決定関数によって実行される。この関数の構成は、応用によって変わる出力に対する要求や処理時間に対する制約などによって、異なるものとなる。
【００４９】
例えば、処理時間に対する制約が弱く、出力部分行列に対する要求が厳しい場合を考える。このときの縮退方向決定関数は、縮退グラフを全探索して、最善の部分行列を選択し、その部分行列への経路を順に返すものになる。さらに、要求間に矛盾が生じたとき、どの要求を優先して達成し、どの要求を緩めるかの方針が問題によって変わるが、その方針も前記関数に含めることができる。
反対に、処理時間に対する制約が強く、出力に対する要求が緩い場合を考える。このときの縮退方向決定関数は、可能な限り少数の部分行列のみを構成することで、要求をできるだけ満たす出力をする必要がある。部分行列の構成回数が最も少なくなる関数は、現在の部分行列のみから縮退方向を決定するものである。
この関数を用いると、縮退グラフ上での初期部分行列から出力部分行列までの経路上の部分行列しか構成されない。このような関数のうち最も単純なものは、現在の部分行列の行数と列の比を、要求として与えられる行数と列数の比と比較し、それらを近づける方向に縮退するものである。
すなわち、与えられた比に比べて現在の行が大きければ行を縮退し、列が大きければ列を縮退する。この関数に必要な処理時間は部分行列のサイズによらず一定であり、除算と減算１回ずつのみで実現することが可能である。この単純な縮退方向決定関数は、処理速度の点で望ましい上に、縮退グラフの単調変化する性質を利用する要求、すなわち最小行数、最小列数、最小面積、０要素の存在保証を必ず満たすことができる。しかし、最小密度と行列数比の制御に関しては、必ず満たすことを保証できない。
【００５０】
［処理の高速化１：初期部分行列データの縮小化］
処理の高速化は、例えば、初期部分行列データＭ０を小さくすることによって達成できる。初期部分行列データＭ０を小さくする方法は、少なくとも、２つある。１つは、ＲＬ×ＣＬではなくＲＳ×ＣＳを利用するものである。ただし、ＲＳ×ＣＳは、前述のように、応用目的によっては用いることができない場合がる。もう一つの方法は、ＲＬのうち、基準行ｒ＿ｂとの共通要素数の多い行を上から所定数を取り出して初期部分行列の行とし、列についても同様にするものである。これは、初期部分行列で内積の少ない行や列は早い段階の縮退で取り除かれる可能性が大きいので、これらを初期部分行列に含めずとも出力に大きな影響はないと考えられるからである。
【００５１】
この処理のためには、前述の初期部分行列データＭ０の行集合を求める方法（段落００３８参照）のアルゴリズムを次のように変更する。前記方法の（手順３）では、ｒｏｗｓの各データをソートし、重複要素を削除していたが、ｒｏｗｓから重複要素を削除する代わりに、各行番号ｒの重複回数を数え、行番号ｒを重複回数でソートし、ｒｏｗｓの端から一定の個数の行番号ｒを取り出す、というものである。列についても同様に行う。このときも計算量はＯ（ＮｌｏｇＮ）となる。
この方法は、高速化を達成するとともに、処理時間を一定に近づける効果を持つ。実施形態に係るＭＣにといて、計算時間を多く消費するのは初期部分行列データやそれに近い部分行列データである。そのため、初期部分行列データが行列中の「１」要素の分布によって決められるなら、計算時間も行列中の「１」要素の分布によって決められることになる。それに対してこの方法では、部分行列のサイズを常に一定以下に抑えることができるため、処理速度をアルゴリズムで制御することができる。
この方法は、空行や空列を含むことがあるため、縮退グラフの性質を保証するには、小さくなった初期部分行列の行と列の内積を計算し、内積０のものは排除した上で、それを初期部分行列データＭ０とする必要がある。この処理も、既に部分行列データが小さいため、計算時間を多く消費することはない。なお、上記２つの方法は組み合わせることができる。すなわち、ＲＳの中から、基準行と多くの共通要素を持つものを初期部分行列データＭ０の行として選ぶことも可能である。
【００５２】
［処理の高速化２：縮退回数の減少］
処理の高速化方法として、縮退回数を少なくすることが考えられる。縮退操作の回数を減らすためには、削除操作において、内積が採用の行・列だけでなく、内積の小さい行・列を所定の割合で取り除けばよい。この方法では、例えば、１０００×２０００お部分行列データに対して、８割を削除すると指定すれば、行ならは８００行が、列ならば１６００列が一度の操作で取り除かれる。８００番目の行と同じ内積の行があった場合、それらの行も同時に削除する。列についても同様である。
この方法を縮退グラフの上で考えると、１度にｒ遷移とｃ遷移を同じ方向にまとめて行うことに相当する。以下では、この縮退方法を割合縮退とよび、内積最小の行・列のみを削除する方法を最小値縮退とよぶ。割合縮退で一度に取り除かれる行数・列数の割合を縮退率とよぶ。
【００５３】
なお、割合縮退を用いる場合、終了条件を満たす部分行列を発見したとしても、より適切な部分行列が縮退前の部分行列との間に存在する可能性がある。そのため、ある部分行列が終了条件を満たした場合、直前の部分行列から最小値縮退、あるいは割合がより低い割合縮退を行うことで、より適切な部分行列を求めることができる。
また、縮退率は、各縮退操作において一定である必要がなく、縮退操作ごとに変化させてもよい。例えば、縮退率を徐々に小さくしていけば、高速化と部分行列の適切化の調和を図ることができる。
【００５４】
［類似性の演算の他の例］
上記説明では、類似性の演算にベクトルの内積を用いていたが、これは他の手段でもよい。例えば、ＩＵ比を用いた類似性演算でもよい。ここでは、２つの２値ベクトルのＩＵ比を、［ベクトルの共通部分の要素数÷ベクトルの和集合の要素数と定義する。例えば，Ａ＝（００１１００１１）、Ｂ＝（０１０１０１０１）とすると、ＡＢのＩＵ比は共通部分の要素数が２，和集合の要素数が６のため、１／３となる。このような演算方法は、１が非常に多いベクトルと１が少ないベクトルとの類似性を相対的に低くするために有効である。
なお、類似性の演算は、ＩＵ比以外にも様々な方法を採用することができる。
【００５５】
［基準行・列が複数の場合］
上記説明では、単一の基準行、単一の基準列を想定していたが、これらは複数でもよい。すなわち、基準要素は複数でもよい。本方法を文書検索システムに応用する場合、特定の文書に関連する文書群（行）とそれらに含まれる単語群（列）を抽出するには、基準行は単一でよいが、基準列はその文書に含まれる複数の単語となる。
ここでは、単一基準行、複数基準列のアルゴリズムについて説明するが、複数基準行・単一基準列でも、複数基準行・複数基準列でも同様である。
【００５６】
（手順１）基準行をｒ＿ｂ、基準列をｃ＿ｂをとする。ｒ＿ｂは単一、ｃ＿ｂは複数とする。
（手順２）ｒ＿ｂとｃ＿ｂを用いて初期部分行列Ｍ０を作る。ここで、Ｍ０は、ｃ＿ｂの中のどれか一つを含む行とする。Ｍ０の行集合をＲ（０）、列集合をＣ（０）とする。
（手順３）ｉ＝０，１，２，３・・・に関して、終了条件を満たすまで以下を繰り返す：
（手順３−１）縮退方向決定関数が停止を出力すればＭｉを返して終了する。それ以外なら、この関数が示す方向に縮退する。行縮退の場合は（手順３−２）へ、列縮退の場合は（手順３−６）へ続く。
（手順３−２）Ｍｉの各行に対して、基準行ｒ＿ｂとの内積を求める。
（手順３−３）内積の最も小さい行（複数存在するなら全て）をＲ（ｉ）から取り除いたものをＲ（ｉ＋１）とする。
（手順３−４）Ｃ（ｉ）をＣ（ｉ＋１）とする。
（手順３−５）Ｒ（ｉ＋１）×Ｃ（ｉ＋１）をＭ（ｉ＋１）とし、（３−１）に戻る。
（手順３−６）Ｍｉの各列を正規化（詳細は後述）し、ｃ＿ｂに含まれる各列との内積の平均値をとる。ただし、内積計算においてｒ＿ｂは含まない。
（手順３−７）内積の最も小さい列（複数存在するなら全て）をＣ（ｉ）から取り除いたものをＣ（ｉ＋１）とする
（手順３−８）Ｒ（ｉ）をＲ（ｉ＋１）とする
（手順３−９）Ｒ（ｉ＋１）×Ｃ（ｉ＋１）をＭ（ｉ＋１）とし、（手順３−１）に戻る。
【００５７】
基準行ｒ＿ｂが複数の場合には、上記（手順３−２）を次のようにすればよい。
（手順３−２’）Ｍｉの各行を正規化（詳細は後述）し、ｒ＿ｂに含まれる各行との内積の平均値をとる。ただし、内積計算においてｃ＿ｂは含まない。
【００５８】
［正規化について］
正規化とは、ベクトル（行又は列）の各要素間の比率を保ったまま、各要素の２乗の和が１になるように、数をかけて、ベクトルの値を変えることをいう。
ある列ｃと基準列ｃ＿ｂの内積を求める場合を考えると、具体的には、次のようになる。ここで、各列ベクトルは基準行ｒ＿ｂを除いて次のように成っているものとする。
ｃ：［１１１１１１１１０００００００］
ｃ＿ｂ：［００００１１１１１１１００００］
【００５９】
列ｃの有意なデータ要素数は８なので、各要素を√８で割って、[１／√８ １／√８ １／√８ １／√８ １／√８ １／√８ [１／√８ １／√８ ０００００００]とする。
同様に、ｃ＿ｂ（１要素数は７）も各要素を√７で割って、［００００ １／√７ １／√７ １／√７ １／√７ １／√７ １／√７ １／√７ ００００］とする。
以上により、正規化が終了する。
正規化したｃとｃ＿ｂの内積をとる。両方のベクトルで共通して０以外の値を持っている４つの要素だけを見ればいいので、（１／√８）×（１／√７）×４＝４√５６が得られる。
【００６０】
より具体的に、データ構造上での手順を説明すると次の通りである。
まず、列ｃ中の「１」要素が存在する行番号の配列をｖｅｃ＿ｃ、列ｃ＿ｂで「１」要素が存在する行の番号の配列をｖｅｃ＿ｃｂとする。どちらの配列もソート（昇順ソート）されている。
続いて、ｖｅｃ＿ｃとｖｅｃ＿ｃｂの共通要素を全て列挙して、配列ｖｅｃ＿ｉｎｔｅｒｓｅｃｔｉｏｎに格納する。
さらに、ｖｅｃ＿ｃの要素数の平行根（上記例だとＰ＝√８）、ｖｅｃ＿ｃｂの要素数の平方根をｑ（上記例だとｑ＝√７）、ｖｅｃ＿ｃの要素数をｒ（上記例だと４）とする。この結果、ｒ（ｐｑ）が正規化内積となる。
【００６１】
複数の基準列がある場合に、単に、各基準列との類似性を示す数値（類似度）の平均をとる等によって、列削除のための値を求めてもよいが、ｐやｑといった、要素数を考慮して類似性の演算を行うことで、各ベクトル中に含まれる１（有意なデータ要素）の数が異なる基準列が複数あっても、これによる類似度への影響を避けることができる。すなわち、正規化を行うことで、対比される列における有意な要素数が多くても、類似性を示す数値が大きくなりにくく、有意な要素数が少ない場合の類似度との比較をすることができるようになって、複数の基準列があっても問題が生じにくくなる。
また、正規化については、行についても全く同様に行うことができる。
【００６２】
実施形態に係る方法の応用としては、次のようなものがある。例えば、ＷＷＷでの検索システムその他の文書検索システムにおいて、ユーザがキーワード検索を行った結果、システムがキーワードを含む文書（ＷＷＷページ）リストを（画面）出力した後に、ユーザがそのリストの中からある文書を選択した場合に、選択された文書に関連する文書をシステムが抽出するのに実施形態に係る方法を使用することができる。
すなわち、例えば、文書を行、キーワード（単語）を列として持つ２次元行列データにおいて、基準行をユーザが選択した文書、基準列をユーザが入力したキーワードとして、実施形態に係る方法を使用することで、関連する文書を効率よく検索することが可能となる。
また、ＷＷＷ上のショッピングサイトにおいて、ユーザを行、ユーザが訪れた商品ページを列とする２次元行列データを具備しておき、ログインしてきたユーザを基準行、当該ユーザが訪れた商品のページを基準列として、実施形態に係る方法を使用することで、当該ユーザと似た傾向を有する他のユーザが訪れたページをリコメンドすることができる。
【００６３】
なお、本発明は、上記実施形態に限定されるものではない。本発明は、特許請求の範囲に記載した事項の範囲内で様々な変形が可能である。
【図面の簡単な説明】
【００６４】
【図１】孤立した行・列が存在する行列である。
【図２】横長部分行列と縦長部分行列である。
【図３】疎な大規模行列データＭである。
【図４】実施形態に係る方法を示すフローチャートである。
【図５】行列データＭのデータ構造である。
【図６】部分行列データの縮退を示す図である。
【図７】配列ｉｐである。
【図８】縮退グラフである。
【符号の説明】
【００６５】
ｒ＿ｂ 基準行
ｃ＿ｂ 基準列
【特許請求の範囲】
【請求項１】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除するステップ、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除するステップ、
を有することを特徴とする方法。
【請求項２】
請求項１における前記（ｃ）のステップ、又は（ｄ）のステップにおいて、
行又は列の削除を行う際に、指定された所定割合の数の行又は列を一括して削除することを特徴とする方法。
【請求項３】
請求項１における前記（ａ）のステップにおいて、複数の基準行が決定された場合には、請求項１における前記（ｃ）のステップに代えて、下記（ｅ）のステップを実行することを特徴とする方法。
（ｅ）前記行列データの各行と前記各基準行との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準行と非基準行にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準行との類似性が低い行を削除するステップ。
【請求項４】
請求項１における前記（ｂ）のステップにおいて、複数の基準列が決定された場合には、請求項１における前記（ｄ）のステップに代えて、下記（ｆ）のステップを実行することを特徴とする方法。
（ｆ）前記行列データの各列と前記各基準列との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準列と非基準列にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準列との類似性が低い列を削除するステップ。
【請求項５】
請求項１における前記第（ｃ）のステップ、又は（ｄ）のステップの実行前に、下記（ｇ）のステップを実行して初期部分行列データを生成し、その初期部分行列データに対して、請求項１における前記（ｃ）のステップ、又は（ｄ）のステップを行うことを特徴とする方法。
（ｇ）前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行と、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列と、からなる初期部分行列データを生成する。
【請求項６】
請求項５における（ｇ）のステップにおいて、
前記初期部分行列データは、
前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行のうち、前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素の数が多い所定数の行と、
前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列のうち、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素の数が多い所定数の列と、
を取り出して生成されることを特徴とする方法。
【請求項７】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｈ）前記基準行において有意な要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除するステップ、
（ｉ）前記基準列において有意な要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除するステップ、
を有することを特徴とする方法。
【請求項８】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するコンピュータシステムであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除する手段、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除する手段、
を有することを特徴とするコンピュータシステム。
【請求項９】
コンピュータを、請求項８記載のコンピュータシステムにおけるそれぞれの手段として機能させるためのコンピュータプログラム。
【請求項１０】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するコンピュータシステムであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｈ）前記基準行において有意な要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除する手段、
（ｉ）前記基準列において有意な要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除する手段、
を有することを特徴とするコンピュータシステム。
【請求項１１】
コンピュータを、請求項１０記載のコンピュータシステムにおけるそれぞれの手段として機能させるためのコンピュータプログラム。
【請求項１】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除するステップ、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除するステップ、
を有することを特徴とする方法。
【請求項２】
請求項１における前記（ｃ）のステップ、又は（ｄ）のステップにおいて、
行又は列の削除を行う際に、指定された所定割合の数の行又は列を一括して削除することを特徴とする方法。
【請求項３】
請求項１における前記（ａ）のステップにおいて、複数の基準行が決定された場合には、請求項１における前記（ｃ）のステップに代えて、下記（ｅ）のステップを実行することを特徴とする方法。
（ｅ）前記行列データの各行と前記各基準行との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準行と非基準行にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準行との類似性が低い行を削除するステップ。
【請求項４】
請求項１における前記（ｂ）のステップにおいて、複数の基準列が決定された場合には、請求項１における前記（ｄ）のステップに代えて、下記（ｆ）のステップを実行することを特徴とする方法。
（ｆ）前記行列データの各列と前記各基準列との間での類似性を示す数値を演算し、この際に、類似性の演算の対象となる基準列と非基準列にそれぞれ含まれる有意なデータ要素の数を考慮して類似性の演算を行い、前記各基準列との類似性が低い列を削除するステップ。
【請求項５】
請求項１における前記第（ｃ）のステップ、又は（ｄ）のステップの実行前に、下記（ｇ）のステップを実行して初期部分行列データを生成し、その初期部分行列データに対して、請求項１における前記（ｃ）のステップ、又は（ｄ）のステップを行うことを特徴とする方法。
（ｇ）前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行と、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列と、からなる初期部分行列データを生成する。
【請求項６】
請求項５における（ｇ）のステップにおいて、
前記初期部分行列データは、
前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素を１個以上持つ行のうち、前記基準行において有意なデータ要素が存在する列と同じ列に共通して存在する有意なデータ要素の数が多い所定数の行と、
前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素を１個以上持つ列のうち、前記基準列において有意なデータ要素が存在する行と同じ行に共通して存在する有意なデータ要素の数が多い所定数の列と、
を取り出して生成されることを特徴とする方法。
【請求項７】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データをコンピュータによって抽出する方法であって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定するステップ、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定するステップ、
（ｈ）前記基準行において有意な要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除するステップ、
（ｉ）前記基準列において有意な要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除するステップ、
を有することを特徴とする方法。
【請求項８】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するコンピュータシステムであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｃ）前記行列データの各行と前記基準行との間での類似性を示す数値を演算し、前記基準行との類似性の低い行を削除する手段、
（ｄ）前記行列データの各列と前記基準列との間での類似性を示す数値を演算し、前記基準列との類似性の低い列を削除する手段、
を有することを特徴とするコンピュータシステム。
【請求項９】
コンピュータを、請求項８記載のコンピュータシステムにおけるそれぞれの手段として機能させるためのコンピュータプログラム。
【請求項１０】
有意なデータ要素と非有意なデータ要素とが含まれる行列データから、有意なデータ要素の密度が高い部分行列データを抽出するコンピュータシステムであって、
（ａ）前記行列データの行の中から、部分行列データを抽出するために基準となる単一又は複数の基準行を決定する手段、
（ｂ）前記行列データの列の中から、部分行列データを抽出するために基準となる単一又は複数の基準列を決定する手段、
（ｈ）前記基準行において有意な要素が存在する列と同じ列に有意なデータ要素が存在しない行を削除する手段、
（ｉ）前記基準列において有意な要素が存在する行と同じ行に有意なデータ要素が存在しない行を削除する手段、
を有することを特徴とするコンピュータシステム。
【請求項１１】
コンピュータを、請求項１０記載のコンピュータシステムにおけるそれぞれの手段として機能させるためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００６−１３９６６３（Ｐ２００６−１３９６６３Ａ）
【公開日】平成１８年６月１日（２００６．６．１）
【国際特許分類】
【出願番号】特願２００４−３３０３４０（Ｐ２００４−３３０３４０）
【出願日】平成１６年１１月１５日（２００４．１１．１５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１６年６月１５日 社団法人情報処理学会発行の「情報処理学会論文誌 第４５巻 Ｎｏ．ＳＩＧ７（ＴＯＤ ２２）」に発表
【出願人】（５９３００６６３０）学校法人立命館 (359)
【Ｆターム（参考）】
【公開日】平成１８年６月１日（２００６．６．１）
【国際特許分類】
【出願日】平成１６年１１月１５日（２００４．１１．１５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１６年６月１５日 社団法人情報処理学会発行の「情報処理学会論文誌 第４５巻 Ｎｏ．ＳＩＧ７（ＴＯＤ ２２）」に発表
【出願人】（５９３００６６３０）学校法人立命館 (359)
【Ｆターム（参考）】
[ Back to top ]