(57)【特許請求の範囲】
【請求項１】
アトリビュート・データを含むドキュメントが加えられるデータベースにおける前記ドキュメントをリトリーブおよびランク付けするための方法であって、該方法は、
コンピュータが前記アトリビュート・データから導かれる数値要素を含むドキュメント・マトリックスを前記ドキュメントから形成するステップと、
コンピュータが前記ドキュメント・マトリックスから共分散マトリックスを形成するステップと、
コンピュータが前記共分散マトリックスから下記式
【数１】
0003672234.tif 000030
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがって固有値分解したデータ構造を生成するステップと、
コンピュータが前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下するステップと、
コンピュータが次元が低下されたマトリックスＶを用いて前記ドキュメント・マトリックスのキーワード次元を低下するステップと、
コンピュータが前記キーワード次元が低下されたドキュメント・マトリックスとクエリー・ベクトルとの内積を計算させることにより、前記データベースの前記ドキュメントをリトリーブおよびランク付けするステップとを実行する、前記ドキュメントをリトリーブおよびランク付けするための方法。
【請求項２】
前記アトリビュート・データは、少なくとも１つのキーワードおよび／またはタイムスタンプを含む、請求項１に記載の方法。
【請求項３】
前記共分散マトリックスは、下記式
【数２】
0003672234.tif 000031
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）により算出される、請求項１に記載の方法。
【請求項４】
前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％である、請求項１に記載の方法。
【請求項５】
さらに、コンピュータが所定の計算時間に応じて前記ドキュメント・マトリックスを直接用いる次元低下から、前記共分散マトリックスを用いる次元低下へと切り換えるステップを含み、前記共分散マトリックスを用いる前記次元低下が、前記ドキュメント・マトリックスの固有ベクトルを用いる前記ドキュメント・マトリックスの前記次元低下が前記所定の計算時間内に終了しない場合に実行される、請求項１に記載の方法。
【請求項６】
アトリビュート・データを含むドキュメントが加えられるデータベースにおける前記ドキュメントをリトリーブおよびランク付けするためのコンピュータ・システムであって、前記コンピュータ・システムは、
前記アトリビュート・データから導かれる数値要素を含むドキュメント・マトリックスを前記ドキュメントから形成する手段と、
前記ドキュメント・マトリックスから共分散マトリックスを形成する手段と、
前記共分散マトリックスから下記式
【数３】
0003672234.tif 000032
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがって固有値分解したデータ構造を生成する手段と、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させる手段と、
次元が低下されたマトリックスＶを用いて前記ドキュメント・マトリックスのキーワード次元を低下させる手段と、
前記キーワード次元の低下されたドキュメント・マトリックスとクエリー・ベクトルとの内積を計算させることにより、前記データベースの前記ドキュメントをリトリーブおよびランク付けする手段とを含む、前記ドキュメントをリトリーブおよびランク付けするためのコンピュータ・システム。
【請求項７】
前記アトリビュート・データは、少なくとも１つのキーワードおよび／またはタイムスタンプを含む、請求項６に記載のコンピュータ・システム。
【請求項８】
前記共分散マトリックスは、下記式
【数４】
0003672234.tif 000033
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、マトリックスＸｂａｒの転置マトリックスを示す。）で算出される、請求項６に記載のコンピュータ・システム。
【請求項９】
前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％である、請求項６に記載のコンピュータ・システム。
【請求項１０】
さらに、所定の計算時間に応じて前記ドキュメント・マトリックスを直接用いる次元低下から、前記共分散マトリックスを用いる次元低下へと切り換える手段を含み、前記共分散マトリックスを用いる前記次元低下が、前記ドキュメント・マトリックスから算出される固有ベクトルを用いる前記ドキュメント・マトリックスの前記次元低下が前記所定の計算時間内に終了しない場合に実行される、請求項６に記載のコンピュータ・システム。
【請求項１１】
アトリビュート・データを含むドキュメントが加えられるデータベースにおける前記ドキュメントをリトリーブおよびランク付けするための方法を実行するためのコンピュータ実行可能なコンピュータ・プログラムを含むコンピュータ可読な記録媒体であって、該記録媒体は、コンピュータに対し、
前記アトリビュート・データから導かれる数値要素を含むドキュメント・マトリックスを前記ドキュメントから形成し、
前記ドキュメント・マトリックスから共分散マトリックスを形成し、
前記共分散マトリックスから下記式
【数５】
0003672234.tif 000034
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角行列であり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがって固有値分解されたデータ構造を生成し、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下し、
次元が低下されたマトリックスＶを用いて前記ドキュメント・マトリックスのキーワード次元を低下し、
前記キーワード次元の低下されたドキュメント・マトリックスとクエリー・ベクトルとの内積を計算させることにより、前記データベースの前記ドキュメントをリトリーブおよびランク付けすること含むを前記ドキュメントのリトリーブおよびランク付けする処理を実行させるコンピュータ可読なコンピュータ・プログラムを含む、記録媒体。
【請求項１２】
前記アトリビュート・データは、少なくとも１つのキーワードおよび／またはタイムスタンプを含む、請求項１１に記載の記録媒体。
【請求項１３】
前記共分散マトリックスは、下記式
【数６】
0003672234.tif 000035
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）により算出される、請求項１１に記載の記録媒体。
【請求項１４】
前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％である、請求項１１に記載の記録媒体。
【請求項１５】
さらに、所定の計算時間に応じて前記ドキュメント・マトリックスを直接用いる次元低下から、前記共分散マトリックスを用いる次元低下へと切り換えさせ、前記共分散マトリックスを用いる前記次元低下が、前記ドキュメント・マトリックスから算出される固有ベクトルを用いる前記ドキュメント・マトリックスの前記次元低下が前記所定の計算時間内に終了しない場合に実行される、請求項１１に記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、大きなデータベースにおけるドキュメントのリトリーブおよび／またはランク付け、すなわちドキュメントのリトリーブ、またはドキュメントのランク付け、またはドキュメントのリトリーブおよびランク付けに関し、より詳細にはきわめて大きなデータベースにおけるドキュメントのリトリーブおよびランク付けを、共分散マトリックスを用いてドキュメント・マトリックスの次元低下により行う方法、コンピュータ・システムおよび該方法を実施するためのソースコードが記録された記録媒体に関する。
【０００２】
【従来の技術】
近年におけるデータベース・システムは、ニュースデータ、顧客情報、在庫データなどの膨大な量のデータをますます取り扱うようになってきている。このようなデータベースのユーザは、充分な精度をもって迅速、かつ効果的に所望する情報を検索することが、ますます困難となっている。したがって、適時、かつ精度よく、さらには安価に大きなデータベースから新たなトピックスおよび／または新たな事項を検出することは、在庫管理、先物取引やオプション取引、世界中に多数のレポーターを配置することなしにレポータへと迅速に指令を行うニュース代理店、成功を収めるためには競合者についての主要、かつ新しい情報を知ることが必要なインターネットや、他の速いペースの行動に基づくビジネスといった、多くのタイプのビジネスに対し、きわめて価値ある情報を与えることになる。
【０００３】
従来ではデータベースの検索者は、検索をモニタするために別の要員を雇用する必要があるので、多くのデータベースにおける新規な事項の検出および追跡は、コストが高く、労力を要し、時間を浪費する作業となっている。
【０００４】
検索エンジンにおける検出および追跡方法は、近年ではデータベース内のデータをクラスタ化するためにベクトル・モデルを用いている。この従来の方法は、概ねデータベース内のデータに対応したベクトルｑ（kwd1, kwd2,. . ., kwdN)を形成するものである。このベクトルｑは、kwd1, kwd2,. . ., kwdNといったデータに付されたアトリビュートの数に等しい次元を有するベクトルとして定義される。最も通常の場合には、アトリビュートは、単独のキーワード、フレーズ、人の名前、地名などとされる。通常では数学的にベクトルｑを形成するため、バイナリ・モデルが用いられ、このバイナリ・モデルにおいては、データがkwd1を含まない場合には、kwd1を０に置換し、データがkwd1を含む場合にはkwd1を１へと置換する。ある場合には重み付け因子をバイナリ・モデルと組み合わせて、検索の精度が向上されている。このような重み付け因子としては、例えばデータ中におけるキーワードの出現回数を挙げることができる。
【０００５】
図１には、上述したベクトルから構成されるドキュメント・マトリックスＤの対角化のための典型的な方法を示す。このマトリックスＤは、ｎ×ｎの対称的な正のマトリックスであるものとする。図１に示されるように、ｎ×ｎマトリックスＤは、マトリックスＤのサイズに応じて、２つの代表的な対角化方法により対角化することができる。ｎ×ｎマトリックスＤにおいてｎが比較的小さな場合には、典型的に用いられる方法は、ハウスホルダー・２重対角化法であり、マトリックスＤは、図１（ａ）に示すような２重対角化形態へと変換され、ついで２重化された要素をゼロへと掃き出しを行い、マトリックスＤの固有ベクトルからなるマトリックスＶｒを得る。
【０００６】
図１（ｂ）には、対角化の別の方法が示されている。図１（ｂ）に示す対角化法は、ｎ×ｎマトリックスＤにおけるｎが、大きいかまたは中程度の場合に有効である。この対角化プロセスは、まず、図１（ｂ）に示すようにLanczos３重対角化を行い、ついでStrumシーケンス化を行って固有値、λ１、λ２．．．、λｒを決定する。ここで、“ｒ”は、次元が低下されたドキュメント・マトリックスのランクを表す。このプロセスは、ついで逆イタレーションを行い、図１（ｂ）に示されるように予め見出されている固有値に伴う１番目の固有ベクトルを決定する。
【０００７】
データベースのサイズが、ドキュメント・マトリックスＤの固有ベクトルの算出を完了させるため、正確ではあるが労力を要する方法の適用を依然として許容することができる限り、従来の方法は、データベース内のドキュメントをリトリーブし、ランク付けを行うためにきわめて有効である。しかしながら、きわめて大きなデータベースにおいては、ドキュメントのリトリーブやランク付けに要する計算時間は、多くの場合、検索エンジンのユーザにとっては長すぎることになりがちである。また、計算を完了させるためのＣＰＵ性能やメモリ容量といった資源についても限りがある。
【０００８】
したがって、低コストで自動的な方法により、許容可能な計算時間できわめて大きなデータベースにおけるドキュメントを安定的にリトリーブし、かつ安定的にランク付けするための新規な方法を含んだシステムを提供することが必要とされている。
【０００９】
＜先行技術の開示＞
いくつかの統計的な手法が、ベクトル空間モデルに基づいた情報リトリーブのためのアルゴリズムを用いて提案されてきている（例えば、Baeza-Yates, R., Riberio-Neo, B., “モダン・インフォメーション・リトリーブ（Modern Information Retrieval）”, Addition-Wesley, NY, 1999年、およびManning, C., Shutze, N., 統計的な自然言語処理の原理（“Foundations of Statistical Natural Language Processing）”, MIT Press, Cambridge, MA, 1999を参照されたい。）。
【００１０】
Salton, G.,等は、“スマート・リトリーブ・システム−自動化ドキュメント処理における実験（The SMART Retrieval System-Experiments in Automatic Document Processing）”, Prentice-Hall, Englewood Cliffs, NJ, 1971年において、ベクトル空間モデルを総説している。彼らは、ベクトルを用いてドキュメントをモデル化しており、ベクトルの各座標軸がベクトルのアトリビュート、例えばキーワードを表すものとされている。ベクトルのバイナリ・モデルにおいては、座標軸は、ドキュメントに当該アトリビュートが含まれていれば１の値とされ、当該アトリビュートがドキュメントに含まれていなければ０とされる。より高度化されたドキュメント・ベクトル・モデルでは、タイトル、セクションヘッダ、要約における出現回数および位置といったキーワードに対する重み付けが考慮される。
【００１１】
クエリーはまた、ドキュメントについて説明したと同一の方法により、ベクトルとしてモデル化される。所定のユーザ入力クエリーに対して、特定のドキュメントの信頼度は、クエリーと、ドキュメント・ベクトルとのそれぞれの間の“距離”を決定することにより算出される。数多くの異なったノルムをクエリー・ベクトルとドキュメント・ベクトルとの間の“距離”計算するために用いることができるが、内積から得られるクエリー・ベクトルとドキュメント・ベクトルとの間の角度が、これらの間の距離を決定するため、最も普通に用いられるものである。
【００１２】
Deerwester等に付与された米国特許第４，８３９，８５３号、名称“ラテント・セマンティック構造を用いたコンピュータ情報リトリーブ（Computer information retrieval using latent semantic structure）”、およびDeerwester等、“ラテント・セマンティック・アナリシスによるインデキシング（Indexing by latent semantic analysis）”, Journal of American Society for Information Science, Vol. 41, No. 6, 1990, pp. 391-407においては、データベースからドキュメントをリトリーブするためのユニークな方法が開示されている。開示された手順は、おおよそ以下のようなものである。
【００１３】
ステップ１：ドキュメントおよびそれらのアトリビュートのベクトル空間モデル化
ラテント・セマンティック・インデキシング（ＬＳＩ）においては、ドキュメントは、Saltonのベクトル空間モデルと同一の方法においてベクトル化されることにより、モデル化される。ＬＳＩ法においては、クエリーとデータベースのドキュメントとの間の関係は、要素がmn (i, j)により表されるｍ×ｎ行列ＭＮすなわち、
【００１４】
【数７】
0003672234.tif 000002
により表される。すなわち、マトリックスＭＮの列は、データベースにおけるドキュメントそれぞれを表すベクトルである。
【００１５】
ステップ２：固有値分解によるランク付け問題の次元低下
ＬＳＩ法の次のステップでは、固有値分解、すなわちマトリックスＭＮのＳＶＤ（Singular Value Decomposition）を実行する。マトリックスＭＮにおけるノイズは、ｋ番目に大きな固有値σｉ、ｉ＝１，２，３，．．．，ｋ，．．．から変更マトリックスＡｋを形成することにより低減され、これらの対応する固有ベクトルは、下記式から得られる。
【００１６】
【数８】
0003672234.tif 000003
上式中、Σｋは、σｉである対角要素が単調に減少する、対角化されたマトリックスである。マトリックスＵｋおよびＶｋは、マトリックスＭＮのｋ番目に大きな固有値に対応する右側と左側の固有ベクトルの列を含むマトリックスである。
【００１７】
ステップ３：クエリー処理
ＬＳＩ法に基づいた情報リトリーブにおけるクエリーの処理は、さらに２つのステップ、（１）クエリー射影ステップおよびそれに続いた（２）適合化ステップを含む。クエリー射影ステップでは、入力されたクエリーは、マトリックスＵｋにより次元が低減されたクエリー−ドキュメント空間における擬ドキュメントへとマップされ、その後ランクが低減された固有値マトリックスΣｋからの対応する固有値σｉにより重み付けされる。このプロセスは、数学的には以下のように記述される。
【００１８】
【数９】
0003672234.tif 000004
上式中、ｑは、元のクエリー・ベクトルであり、ｈａｔ｛ｑ｝は、擬ドキュメント・ベクトルであり、ｑＴは、ｑの転置ベクトルであり、｛−１｝は、逆数演算子である。第２のステップでは、擬ドキュメント・ベクトルｈａｔ｛ｑ｝と、次元が低減されたドキュメント空間ＶｋＴとは同様に、多くの類似する方法のいずれか１つを用いることによって算出される。
【００１９】
上述したように、ドキュメントをリトリーブし、ランク付けを行うため、多くの従来方法が存在するものの、本発明者等は、これまで充分な精度で効果的に、かつ迅速にきわめて大きなデータベースにおけるドキュメントのリトリーブ及びランク付けを行うための新規な方法を検討してきた。
【００２０】
【発明が解決しようとする課題】
本発明は、最も大きな固有値を有する共分散マトリックスＫの固有ベクトルは、最も主要な特徴に対応し、共分散マトリックスの２番目に大きな固有値の固有ベクトルが、２番目に主要な特徴に対応するということを見出すことによりなされたものである。したがって、共分散マトリックスの所定の小さなセットを、ドキュメント・マトリックスＤの次元低下のために用いることが有効である。
【００２１】
本発明においては、ユーザの入力したクエリーに適合させるため、ドキュメント・マトリックスＤの次元を以下のように低減させる。
（１）共分散マトリックスＫのｊ番目に大きな固有値と、それらに対応する固有ベクトルｖ（Ｄｊ）をまず算出し、
【００２２】
【数１０】
0003672234.tif 000005
（２）ｊ番目に大きなＤの固有値に対応するｋ個の固有ベクトルにより展開されたドキュメントｄ（ｉ）のｋ次元のサブスペースを算出し
【００２３】
【数１１】
0003672234.tif 000006
（上記式中、ｉおよびｊは、それぞれドキュメントおよび固有ベクトルの引数であり、ｃは、対応する係数である。）、
（３）ｊ番目に大きな固有値に対応する固有ベクトルにより規定されるｋ次元のサブスペースにユーザ入力クエリーを射影し、
（４）これらの間の距離を算出することにより、ユーザ入力クエリーとドキュメントとの、それぞれの間の信頼度のランク付けを行うことによるものである。
【００２４】
【課題を解決するための手段】
すなわち、本発明の第１の構成によれば、アトリビュート・データを含むドキュメントが加えられるデータベースにおける前記ドキュメントをリトリーブおよび／またはランク付けをするための方法が提供される。この方法は、
前記アトリビュート・データから導かれる数値要素を含むドキュメント・マトリックスを前記ドキュメントから形成するステップと、
前記ドキュメント・マトリックスから共分散マトリックスを形成するステップと、
前記共分散マトリックスを下記式
【００２５】
【数１２】
0003672234.tif 000007
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがって固有値分解するステップと、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させるステップと、
次元が低下されたマトリックスＶを用いて前記ドキュメント・マトリックスの次元を低下させるステップと、
前記次元低下されたドキュメント・マトリックスとクエリー・ベクトルとの内積を計算させることにより、前記データベースの前記ドキュメントをリトリーブおよび／またはランク付けするステップとを含む。
【００２６】
本発明の第１の構成においては、前記アトリビュート・データは、少なくとも１つのキーワードおよび／またはタイムスタンプを含むことができる。
【００２７】
本発明の第１の構成では、前記共分散マトリックスは、下記式
【００２８】
【数１３】
0003672234.tif 000008
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）により算出することができる。
【００２９】
本発明の第１の構成では、前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％とすることが好ましい。
【００３０】
本発明の第１の構成においては、さらに、所定の計算時間に応じて前記ドキュメント・マトリックスを直接用いる次元低下から、前記共分散マトリックスを用いる次元低下へと切り換えるステップを含み、前記共分散マトリックスを用いる前記次元低下が、前記ドキュメント・マトリックスの固有ベクトルを用いる前記ドキュメント・マトリックスの前記次元低下が前記所定の計算時間内に終了しない場合に実行されることが好ましい。
【００３１】
本発明の第２の構成によれば、アトリビュート・データを含むドキュメントが加えられるデータベースにおける前記ドキュメントをリトリーブおよび／またはランク付けをするためのコンピュータ・システムが提供される。このコンピュータシステムは、
前記アトリビュート・データから導かれる数値要素を含むドキュメント・マトリックスを前記ドキュメントから形成する手段と、
前記ドキュメント・マトリックスから共分散マトリックスを形成する手段と、
前記共分散マトリックスを下記式
【００３２】
【数１４】
0003672234.tif 000009
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがって固有値分解する手段と、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させる手段と、
次元が低下されたマトリックスＶを用いて前記ドキュメント・マトリックスの次元を低下させる手段と、
前記次元低下されたドキュメント・マトリックスとクエリー・ベクトルとの内積を計算させることにより、前記データベースの前記ドキュメントをリトリーブおよび／またはランク付けする手段とを含む。
【００３３】
本発明の第２の構成においては、前記アトリビュート・データは、少なくとも１つのキーワードおよび／またはタイムスタンプを含むことができる。
【００３４】
本発明の第２の構成においては、前記共分散マトリックスは、下記式
【００３５】
【数１５】
0003672234.tif 000010
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）で算出することができる。
【００３６】
本発明の第２の構成においては、前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％とすることができる。
【００３７】
本発明の第２の構成においては、さらに、所定の計算時間に応じて前記ドキュメント・マトリックスを直接用いる次元低下から、前記共分散マトリックスを用いる次元低下へと切り換える手段を含み、前記共分散マトリックスを用いる前記次元低下が、前記ドキュメント・マトリックスから算出される固有ベクトルを用いる前記ドキュメント・マトリックスの前記次元低下が前記所定の計算時間内に終了しない場合に実行することが好ましい。
【００３８】
本発明の第３の構成においては、アトリビュート・データを含むドキュメントが加えられるデータベースにおける前記ドキュメントをリトリーブおよび／またはランク付けをするための方法を実行するためのコンピュータ可読なコンピュータ・プログラムを含む記録媒体が提供される。該記録媒体は、
前記アトリビュート・データから導かれる数値要素を含むドキュメント・マトリックスを前記ドキュメントから形成するステップと、
前記ドキュメント・マトリックスから共分散マトリックスを形成し、
前記共分散マトリックスを下記式
【００３９】
【数１６】
0003672234.tif 000011
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがって固有値分解し、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させ、
次元が低下されたマトリックスＶを用いて前記ドキュメント・マトリックスの次元を低下させ、
前記次元低下されたドキュメント・マトリックスとクエリー・ベクトルとの内積を計算させることにより、前記データベースの前記ドキュメントをリトリーブおよび／またはランク付けするステップとを含む前記ドキュメントのリトリーブおよび／またはランク付けをするための方法を実行するためのコンピュータ可読なコンピュータ・プログラムを含む。
【００４０】
本発明の第３の構成においては、前記アトリビュート・データは、少なくとも１つのキーワードおよび／またはタイムスタンプを含んでいてもよい。
【００４１】
本発明の第３の構成においては、前記共分散マトリックスは、下記式
【００４２】
【数１７】
0003672234.tif 000012
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）により算出することができる。
【００４３】
本発明の第３の構成においては、前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％とすることができる。
【００４４】
本発明の製３の構成においては、さらに、所定の計算時間に応じて前記ドキュメント・マトリックスを直接用いる次元低下から、前記共分散マトリックスを用いる次元低下へと切り換え、前記共分散マトリックスを用いる前記次元低下が、前記ドキュメント・マトリックスから算出される固有ベクトルを用いる前記ドキュメント・マトリックスの前記次元低下が前記所定の計算時間内に終了しない場合に実行することが好ましい。
【００４５】
【発明の実施の形態】
以下、本発明を図面に示した態様をもって説明するが、本発明は、後述する態様に制限されるものではない。
【００４６】
１．  ドキュメントのリトリーブおよびランキングの概略的手順
図２は、本発明の方法を概略的に示したフローチャートである。本発明の方法は、ステップ２０１から開始し、ステップ２０２へと進んでドキュメント・マトリックスＤ（ｍ×ｎマトリックス）を、ドキュメントに含まれたキーワードから形成する。時間、日付、月、年、およびこれらのいかなる組み合わせにおいて、タイムスタンプを同時に用いることも可能である。
【００４７】
この方法は、その後ステップ２０３へと進んでドキュメント・ベクトルの平均ベクトルＸｂａｒを算出する。さらにこの方法は、ステップ２０４へと進んで能率マトリックスＢ＝ＤＴ・Ｄ／ｎを算出する。ここで、Ｂは、能率マトリックスであり、ＤＴは、ドキュメント・マトリックスＤの転置マトリックスである。ついで、本発明の方法は、ステップ２０５に進み、下記式を用いて共分散マトリックスＫを算出する。
【００４８】
【数１８】
0003672234.tif 000013
上式中、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。
【００４９】
本発明の方法は、その後ステップ２０６へと進んで、共分散マトリックスＫの固有値分解を下記式に示すように実行する。
【００５０】
【数１９】
0003672234.tif 000014
上式中、共分散マトリックスＫのランク、すなわちｒａｎｋ（Ｋ）は、ｒである。
【００５１】
本発明の方法は、ステップ２０７へと進んで、大きな方から１５〜２５％の固有値に対応する固有ベクトルの所定数ｋを含ませて、次元の低下したマトリックスＶｋを形成することにより、マトリックスＶの次元を減少させる。本発明の方法は、その後ステップ２０８へと進んで次元の低下したマトリックスＶｋを用いてドキュメント・マトリックスの次元を低下させ、ステップ２０９に示されているＤｏｃ／Ｋｗｄクエリー検索、新規事項検出、追跡といったクエリー・ベクトルについて、リトリーブおよびランク付けを行うために用いられるドキュメント・サブスペースである、次元が低下したドキュメント・マトリックスを形成する。以下、本発明の本質的なステップについて、詳細に説明する。
【００５２】
２．ドキュメントマトリックスの形成
図３は、ドキュメント・マトリックスＤを例示した図である。マトリックスＤは、ドキュメント１（doc 1）からドキュメントｎ（doc n）までの行から構成されており、各行は、特定のドキュメントに含まれるキーワード（kwd1,..., kwdn）から得られた要素を含んでいる。ドキュメントの数およびキーワードの数は、本発明においては制限されるものではなく、ドキュメントおよびデータベースのサイズに依存する。図３においては、ドキュメント・マトリックスＤの要素は、数値１により示されているが、他の正の実数は、ドキュメント・マトリックスＤを形成するために重み付け因子を用いる場合には用いることができる。
【００５３】
図４には、ドキュメント・マトリックスを形成する実際の手順を示す。図４（ａ）では、ドキュメントがＳＧＭＬフォーマットにおいて記述されているものとしている。本発明の方法は、ドキュメントに基づいて、リトリーブおよびランク付けを行うためのキーワードを発生させ、その後ドキュメントのフォーマットを、本発明の方法において好適に用いることができる図４（ｂ）に示すような別のフォーマットへと変換する。ドキュメントのフォーマットは、ＳＧＭＬに限定されるものではなく、別のフォーマットであっても本発明においては用いることができる。
【００５４】
図４（ａ）を用いて、アトリビュートの発生手順を説明する。例えば、アトリビュートは、キーワードとすることができる。キーワード発生は、以下のようにして行うことができる。
（１）キャピタル文字の単語を抽出する、
（２）順序付けする、
（３）出現回数を算出する、
（４）ｎ＞Ｍａｘまたはｎ＜Ｍｉｎであれば単語を削除する、
（５）単独の単語（例えばＴｈｅ、Ａ、Ａｎｄ、Ｔｈｅｒｅなど）を除去する、
などである。
【００５５】
ここで、Ｍａｘは、キーワードあたりの所定の最大出現回数であり、Ｍｉｎは、キーワードあたりの所定の最小出現回数である。（４）に示した手順は、精度を向上させるために多くの場合に有効である。上述の手順を実行する順序については実質的な制限はなく、上述した手順の順序は、用いるシステムの条件、プログラミングの便宜を考慮して決定することができる。上述した手順は、キーワード発生手順の１つの例を示したにすぎず、多くの別の手順も本発明において用いることができる。
【００５６】
キーワードを発生させ、ＳＧＭＬフォーマットを変換した後に構成されたのが、図３に示したドキュメント・マトリックスである。バイナリ・モデルを用い、重み付け因子および／または関数を用いない場合のドキュメント・ベクトル／マトリックスを形成させるための疑似コードを以下に示す。
【００５７】
REM:No Weighting factor and/or function
If kwd (j) appears in doc (i)
Then M (i, j) = 1
Otherwise M (i, j) = 0
同時にタイムスタンプを用いる場合には、タイムスタンプについても同様の手順を適用することができる。
【００５８】
本発明は、ドキュメント・マトリックスＤを形成する場合に、重み付け因子および／または重み付け関数をキーワードおよびタイムスタンプの双方について用いることができる。キーワードＷｋについての重み付け因子および／または重み付け関数としては、ドキュメントにおけるキーワードの出現回数、ドキュメントにおけるキーワードの位置、キーワードがキャピタルで記載されているか否か、を挙げることができるが、これらに制限されるものではない。タイムスタンプについての重み付け因子および／または重み付け関数ＷＴは、また本発明によればキーワードと同様に時間／日付スタンプを得る場合にも適用することができる。
【００５９】
３．共分散マトリックスの形成とＶの次元減少
共分散マトリックスの形成は、図５に示すように平均ベクトルＸｂａｒを算出するステップ５０２と、能率マトリックスを算出するステップ５０３と、共分散マトリックスを算出するステップ５０４といった概ね３つのステップを含んでいる。図６は、図５に示した手順の詳細を示す。平均ベクトルＸｂａｒは、図６（ａ）に示すようにドキュメント・マトリックスＤの転置マトリックスの各行の要素を加算し、ドキュメント数、すなわちｎにより要素の和を除算することにより得られる。平均ベクトルＸｂａｒの構成を図６（ｂ）に示す。ドキュメント・マトリックスの転置マトリックスＤＴは、ｎ×ｍ要素を含み、Ｘｂａｒは、ＡＴの同一の行における要素の平均値から構成される列ベクトルを１列だけから構成される。
【００６０】
ステップ５０３においては、能率マトリックスＢを、下記式により算出する。
【００６１】
【数２０】
0003672234.tif 000015
上式中、Ｄは、ドキュメント・マトリックスであり、ＤＴは、その転置マトリックスである。ついで、この手順では、ステップ５０４において共分散マトリックスＫを、平均ベクトルＸｂａｒおよび能率マトリックスＢから算出する。
【００６２】
【数２１】
0003672234.tif 000016
得られる共分散マトリックスＫは、ｍ×ｍの正の行列として構成され、その後、その固有値分解が、従来の方法により直接的に算出される。固有値分解後の共分散マトリックスＫの構造が、図７（ａ）に示されており、共分散マトリックスＫは、下記式により表される。
【００６３】
【数２２】
0003672234.tif 000017
上式中、Ｖは、固有値から構成されるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、マトリックスＶの転置マトリックスである。図７においては、固有ベクトルが破線で示されている。
【００６４】
マトリックスＶの次元低下は、図７（ｂ）に示されているように、最大の固有値に対応する固有ベクトルを含むように、固有値の所定数ｋを選択して、ｋ×ｍマトリックスＶｋを形成することにより行われる。本発明によれば、固有ベクトルの選択は、最も大きな固有値に対応する固有ベクトルが含まれる限り、種々の方法により行うことができる。ｋの数値については実質的な制限はないが、整数値ｋは、固有ベクトルの総数の約１５〜２５％に設定することが、データベース内のドキュメントのリトリーブおよびランク付けを顕著に改善するためには好ましい。整数値が小さすぎると、検索精度が低下し、整数値が大きすぎると、本発明の効果が損なわれる可能性があるためである。
【００６５】
４．ドキュメント・マトリックスの次元低下
ついで本発明の方法は、マトリックスＶｋを用いてドキュメント・マトリックスの次元低下を実行する。ドキュメント・マトリックスの次元低下を図８に示す。ドキュメント・マトリックスＤの次元を低減させたマトリックスｈａｔＤは、ドキュメント・マトリックスＤと、マトリックスＶｋの転置マトリックスとを、図８（ａ）に示すように単に乗算するだけで得られる。また、図８（ｂ）に示すように、次元低下を行ったマトリックスｈａｔＤに対して、ｋ×ｋ要素の重み付けマトリックスを用いて、ある種の重み付けを行うことも可能である。このようにして算出されたマトリックスｈａｔＤは、図８（ｂ）に示すようにｋ×ｎの要素を含み、キーワードに対して比較的特有の特徴を含んでいる。したがって、データベースにおけるドキュメントのリトリーブおよびランク付けは、検索エンジンのユーザにより入力されるクエリーに対して著しく向上することになる。
【００６６】
図９は、きわめて大きなデータベースにおけるドキュメントのリトリーブおよびランキングを行うための別の態様を示した図である。図９に示した態様においては、長時間の計算時間を要し、膨大なハードウエア資源を要求する直接的な次元低下方法をドキュメント・マトリックスＤに対して適用する従来法から、次元低下方法を切り換えるものである。図９に示した態様においては、次元低下に要する時間を判断するためのステップ９０４が与えられていて、対象とされているデータベースにおけるドキュメントに対し、本発明の次元低下が適切であるか否かを判断する。
【００６７】
図９に示されるように、本発明の第２の態様はステップ９０１から開始し、ステップ９０２へと進んでバイナリ・モデルを用いてドキュメント・マトリックスを発生させる。本発明の方法は、さらにステップ９０３へと進んで、ドキュメント・マトリックスを直接用いる従来の次元低下を実行する。この第２の態様においては、タイマといった好適な手段によりステップ９０４においてドキュメント・マトリックスの次元低下の計算時間を測定している。計算時間が所定の時間Ｔを超える場合（Ｎｏ）には、本発明の方法は、ステップ９０５へと分岐して、本発明の方法へと次元低下の方法を切り換え、さらにステップ９０６へと進んで、ＫＷＤ／クエリー検索などを実行する。この判断がＹｅｓである場合には、この方法は、ステップ９０６へと進んでKWD／クエリー検索などを実行させて検索結果を与える構成とされている。
【００６８】
５．コンピュータシステム
図１０を参照すると、本発明のコンピュータ・システムの代表的な態様が示されている。本発明のコンピュータ・システムは、スタンド・アローンのコンピュータ・システム、いかなる従来のプロトコルを用いてＬＡＮ／ＷＡＮを介して通信を行うクライアント・サーバ・システム、またはインターネット・インフラベースを通して通信を行うコンピュータ・システムとすることができる。図１０においては、本発明に有効な代表的なコンピュータ・システムを、クライアント・サーバ・システムを用いて示している。
【００６９】
図１０に示したコンピュータ・システムは、少なくとも１台のホスト・コンピュータと、サーバ・コンピュータとを含んでいる。クライアント・コンピュータと、サーバ・ホスト・コンピュータとは、通信プロトコルＴＣＰ／ＩＰを介して通信されている。しかしながら、本発明においては別のいかなる通信プロトコルであっても用いることができる。図１０において説明するように、クライアント・コンピュータは、サーバ・ホスト・コンピュータへとリクエストを送信し、サーバ・ホスト・コンピュータにおいてサーバ・ホスト・コンピュータの記憶手段内に記録されているドキュメントのリトリーブおよび／またはランク付けを行なう。
【００７０】
このサーバ・ホスト・コンピュータは、クライアント・コンピュータからのリクエストに応じてデータベース内のリトリーブおよび／またはランク付けを行なう。リトリーブおよび／またはランク付けの結果は、その後クライアント・コンピュータにより、サーバ・スタッブを介してサーバ・ホスト・コンピュータからダウンロードされて、クライアント・コンピュータのユーザにより用いられることになる。図１０においては、サーバ・ホスト・コンピュータは、ウエッブ・サーバとして記載しているが、これに限定されるものではなく、いかなる別のタイプのサーバ・ホストであっても、コンピュータ・システムが上述した機能を提供することができる限り、本発明において用いることができる。以下、本発明をさらに実施例をもって説明するが、後述する実施例は、本発明を制限するものではない。
【００７１】
【実施例】
本発明の方法を、:http://www.research.qtt.com/〜lewisからの、２０，０００を超える記事を利用することができるロイター２１５７８ニュース・データベースを用いて試験を行った。データベース内のドキュメントを、本発明の方法によりリトリーブを行った。キーワード・リストを、キーワードのいかなる位置にでもキャピタル文字を含む単語を検索することにより発生させた。本発明者等は、説明する実施例においては簡単なキーワード・モデルを用いたが、別の方法により発生される、さらによいモデルまたはキーワードセットがあり得る。しかしながら、後述するように、上述した簡単なモデルでも、データベース内のドキュメントのリトリーブおよびランク付けにおいて、良好な結果が得られた。キーワード発生においては、精度を向上させるべく、頻出する単語や希にしか出現しない単語をキーワード・リストから排除した。
【００７２】
実験は、各クエリーにつき、互いに異なる２つのセットについて本発明の方法に従いリトリーブおよびランク付けを行うもの（実施例）と、ＬＳＩ（ラテント・セマンテック・インデキシング）法によりリトリーブおよびランク付けを行うもの（比較例）として行った。上述した異なる２つのセットを以下に示す。
【００７３】
セット１；大きなロイターのデータベースから８３記事（ドキュメント）を含むミニ−データベースを構成して、本発明の方法を検討した。このミニ−データベースは、入力したクエリーによりリトリーブされるドキュメントを知ることができるだけ、充分に小さいものである。
セット２；本発明の方法を検討するためにロイター−２１５７８データベースを完全に使用した。
上述の８３ドキュメントを含むサンプルデータベースを表１に示す。
【００７４】
【表１】
0003672234.tif 000018
0003672234.tif 000019
0003672234.tif 000020
（実施例１）  セット１を使用：
実施例１においては、本発明による方法と、ＬＳＩによる方法とを比較した。検討を行うデータセットは、ロイター−２１５７８ニュースデータベースから構成した小データベースとした。この実験を、１５２次元空間から開始して、双方の方法において３０次元空間にまで次減数を減少させて行った。
【００７５】
この実験では、データベースに含まれる所定のドキュメントの１つを、リトリーブおよびランク付けのためのクエリーとして入力した。ドキュメントをリトリーブするために入力したクエリーは、したがって、各表にリストされる第１番目の結果に対応している。各クエリーについて、比較例であるＬＳＩ法により得られた結果を最初に示し、ついで実施例として、共分散マトリックスを用いる本発明の方法により得られた結果を示す。リトリーブされたドキュメントの前に配置された符号“ＸＸＸ”は、入力したクエリーに対して関連性のないドキュメントであることを示す。この結果は、次の順序に並べられたセットとしてリストしてある。エラーの表示；リトリーブされたドキュメントの順番；信頼度；ドキュメントの日付；ドキュメントＮｏ．；ドキュメントのタイトルである。結果を、精度についてのコメントと共に表２から表６に示す。
【００７６】
第２のクエリーを用いた実験においては、２つのドキュメントが本発明の方法によりエラーとしてリトリーブされたが、表３に示されるように、かっこ内に表示した信頼度は、明確なたち下がりを示している。したがって、さらによいキーワード・セットを用いることによって上述のエラーは排除できるものと考えられる。表４に示す第３のクエリーを用いた実験においては、ドキュメント４，７，１１は、上位ランクとしてリトリーブされている。ドキュメント４，７，１１は、ニュージーランドにおいて発生した地震に関連するものである。本発明の方法は、ニュージーランドにおける地震以外の別のドキュメントともにグループ化されているが、ＬＳＩ法と比較すれば、それらのランク付けと共に、より高い相対的信頼度（かっこ内に示す）が与えられているのが示されている。表６に示した実験においては、マクダネル製の飛行機と別のドキュメントの間は、本発明の方法では高い信頼度をもって明確に規定されたギャップを与えているが、表６に示された比較例では、信頼度のコリレーションがよくないために、互いに交錯した結果が得られているのが示されている。
（実施例２）：セット２を使用
実施例２においては、データベースを除いてドキュメントをリトリーブおよびランク付けするために同一の実験的手法を用いた。実施例２で用いたデータベースは、ロイター−２１５７８ニュース・データベースに含まれる全セットである。７１００のキーワードをドキュメント“19870304 1534 leaf disease hits sri lanka rubber”に含まれる単語から選択した。この結果を表７〜表１０に示す。各実験について入力したクエリーは、対応する表のそれぞれ第１番目にリストされたものである。
【００７７】
表７に示されるように、ＬＳＩ法を用いた比較例では、バヒア・ココアについて関連する１つのドキュメントを見出しているが、本発明の方法は、バヒア・ココアに関連する２ドキュメントをリトリーブしている。本発明の方法は、さらにココアに関連した別のドキュメントを発見することに成功している。
【００７８】
【表２】
0003672234.tif 000021
【００７９】
【表３】
0003672234.tif 000022
【００８０】
【表４】
0003672234.tif 000023
【００８１】
【表５】
0003672234.tif 000024
【００８２】
【表６】
0003672234.tif 000025
【００８３】
【表７】
0003672234.tif 000026
【００８４】
【表８】
0003672234.tif 000027
【００８５】
【表９】
0003672234.tif 000028
【００８６】
【表１０】
0003672234.tif 000029
表２から表１０に示すように、本発明の方法は、いくらかのエラーは観測されたものの、ＬＳＩ法により得られた結果よりもドキュメントのリトリーブおよびランク付けに対して良好な結果を示している。したがって、本発明は、新規、かつ効果的なデータベースの検索及び追跡方法に加え、リトリーブおよびランキング方法を提供することができる。本発明の方法はまた、ドキュメント・マトリックスの次元低下を、データベースへの新規なドキュメントの追加にそれほど依存しない大きな方から１５〜２５％に対応するｉ番目の固有ベクトルしか用いずに行うため、データベースに対する新たなドキュメントの追加に対して安定である。このため、一度共分散マトリックスを形成すると、検索結果の精度が維持できる限り、労力を要し、時間のかかる固有値分解を、検索を行うたびに行わずに多数の検索を実行できるため、性能を著しく改善することを可能とする。
【００８７】
これまで、本発明を特定の態様をもって説明を行ってきた。しかしながら、当業者によれば、本発明の範囲を逸脱することなく、種々の除外、変更、及び他の態様が可能であることは理解できよう。
【００８８】
本発明は、これまでリトリーブおよびランク付けのための方法について詳細に説明してきたが、本発明はまた、本発明で説明した方法を実行するためのシステム、方法自体、本発明の方法を実行するためのプログラムが記録された、例えば光学的、磁気的、電気−磁気的記録媒体といったプログラム製品をも含むものである。
【図面の簡単な説明】
【図１】マトリックスを対角化させるための従来の方法を示した図。
【図２】本発明の方法を示したフローチャート。
【図３】ドキュメント・マトリックスの構成を示した図。
【図４】ドキュメント・マトリックスの形成及びそのフォーマット化を示した図。
【図５】共分散マトリックスを算出するためのフローチャート。
【図６】ドキュメント・マトリックスの転置マトリックスおよび平均ベクトルの構成を示した図。
【図７】共分散マトリックスを用いる次元低下手順を示した概略図。
【図８】本発明による共分散マトリックスを用いる次元低下手順の詳細を示した図。
【図９】本発明の方法の別の態様を示した図。
【図１０】本発明のコンピュータ・システムを例示した図。
【図１】
0003672234.tif 000036
【図２】
0003672234.tif 000037
【図３】
0003672234.tif 000038
【図４】
0003672234.tif 000039
【図５】
0003672234.tif 000040
【図６】
0003672234.tif 000041
【図７】
0003672234.tif 000042
【図８】
0003672234.tif 000043
【図９】
0003672234.tif 000044
【図１０】
0003672234.tif 000045