(57)【特許請求の範囲】
【請求項１】
データベースにおいてドキュメントを検索、検出、および同定するためのコンピュータ・システムであって、前記データベース内の前記ドキュメントが、該ドキュメントに含まれるアトリビュートからドキュメント行列として構成され、前記コンピュータ・システムは、
少なくとも１つのアトリビュートを使用して前記ドキュメントから前記ドキュメント行列を生成する手段と、
所定の関数から前記ドキュメント行列に基づいてスケールされた残差行列を生成する手段と、
ベクトルのノルムを保存する特異値分解を実行して最大の特異値に対応する基底ベクトルを得る手段と、
前記最大の特異値に対応する基底ベクトルを使用して前記残差行列を再構築し、前記再構築された残差行列を動的にスケーリングして残差行列を得る手段と、
前記特異値分解から前記再構築までを前記残差行列に対して繰り返し適用して所定の基底ベクトルのセットを生成する手段と、
前記ドキュメント行列の次元削減を実行して、前記データベース内の前記ドキュメントの検出、検索および同定を行う手段と
を含み、前記スケールされた残差行列は、下記式
【数１】
0003870043.tif 000033
（上式中、Ｒｓは、スケールされた残差行列であり、ｒｉ（ｉは、ドキュメントの数Ｍ以下の整数である。）は、残差ベクトルであり、｜ｒｉ｜は、前記残差ベクトルのノルムであり、Ｔは、ベクトルに対して施される転置演算子であり、ｑは、前記所定の関数により動的に決定されるスケーリング・ファクタである。）により生成され、
前記所定の関数は、前記残差ベクトルの最大ノルムの関数であり、下記式
【数２】
0003870043.tif 000034
（上式中、ｐは、正の整数であり、ｔｍａｘは、前記残差ベクトルの最大ノルムである。）により与えられる、コンピュータ・システム。
【請求項２】
前記特異値分解は、ユーザにより潜在的意味解析法または共分散マトリックス法から択一的に選択される、請求項１に記載のコンピュータ・システム。
【請求項３】
前記コンピュータ・システムは、さらに、前記残差行列の再構築前に前記基底ベクトルを算出された基底ベクトルに対して直交化する手段含む、請求項１に記載のコンピュータ・システム。
【請求項４】
前記スケーリング・ステップは、前記基底ベクトルを得る各ステップごとに、異なるスケーリング・ファクタを使用する、請求項１に記載のコンピュータ・システム。
【請求項５】
前記ドキュメント行列は、前記アトリビュートに関連する複数のクラスタを含んでおり、前記クラスタは、少なくとも主要クラスタとミーディアム・クラスタとアウトライア・クラスタとに分類される、請求項１に記載のコンピュータ・システム。
【請求項６】
データベースにおいてドキュメントを検索、検出、および同定する方法を実行するためのコンピュータ・プログラムであって、前記データベース内の前記ドキュメントが、該ドキュメントに含まれるアトリビュートからドキュメント行列として構成され、前記コンピュータ・プログラムはコンピュータに、
少なくとも１つのアトリビュートを使用して前記ドキュメントから前記ドキュメント行列を生成するステップと、
前記所定の関数から前記ドキュメント行列に基づいてスケールされた残差行列を生成するステップと、
ベクトルのノルムを保存する特異値分解を実行して最大の特異値に対応する基底ベクトルを得るステップと、
前記最大の特異値に対応する基底ベクトルを使用して前記残差行列を再構築し、前記再構築された残差行列を動的にスケーリングして再構築した前記残差行列を得るステップと、
前記特異値分解ステップから前記再構築ステップまでを前記残差行列に対して繰り返して適用し、所定の基底ベクトルのセットを生成するステップと、
前記ドキュメント行列の次元削減を実行して、前記データベース内の前記ドキュメントの検出、検索および同定を行うステップと
を実行させ、
前記スケールされた残差行列は、下記式
【数３】
0003870043.tif 000035
（上式中、Ｒｓは、スケールされた残差行列であり、ｒｉ（ｉは、ドキュメントの数Ｍ以下の整数である。）は、残差ベクトルであり、｜ｒｉ｜は、前記残差ベクトルのノルムであり、Ｔは、ベクトルに対して施される転置演算子であり、ｑは、前記所定の関数により動的に決定されるスケーリング・ファクタである。）により生成され、
前記所定の関数は、前記残差ベクトルの最大ノルムの関数であり、下記式
【数４】
0003870043.tif 000036
（上式中、ｐは、正の整数であり、ｔｍａｘは、前記残差ベクトルの最大ノルムである。）により与えられる、コンピュータ・プログラム。
【請求項７】
前記特異値分解は、ユーザにより潜在的意味解析法または共分散マトリックス法から択一的に選択される、請求項６に記載のコンピュータ・プログラム。
【請求項８】
前記プログラムは、さらに、前記残差行列の再構築前に前記基底ベクトルを算出された基底ベクトルに対して直交化するステップを実行させる、請求項６に記載のコンピュータ・プログラム。
【請求項９】
前記スケーリング・ステップは、前記基底ベクトルを得る各ステップごとに、異なるスケーリング・ファクタを使用する、請求項６に記載のコンピュータ・プログラム。
【請求項１０】
前記ドキュメント行列は、前記アトリビュートに関連する複数のクラスタを含んでおり、前記クラスタは、少なくとも主要クラスタとミーディアム・クラスタとアウトライア・クラスタとに分類される、請求項６に記載のコンピュータ・プログラム。
【請求項１１】
データベースにおいてドキュメントを検索、検出、および同定するためのサーバであって、前記データベース内の前記ドキュメントが、該ドキュメントに含まれるアトリビュートからドキュメント行列として構成され、前記サーバは、ネットワークを通してクライアントと通信し、前記サーバは、
前記ネットワークを通して検索、検出、および同定のためのリクエストを受信する手段と、
前記クライアントからベクトルのノルムを保存した特異値分解のための方法を選択する別のリクエストを受信する手段と、
少なくとも１つのアトリビュートを使用して前記ドキュメントから前記ドキュメント行列を生成する手段と、
所定の関数から前記ドキュメント行列に基づいてスケールされた残差行列を生成する手段と、
前記別のリクエストに応じて前記特異値分解を実行して最大の特異値に対応する基底ベクトルを得る手段と、
前記最大の特異値に対応する基底ベクトルを使用して前記残差行列を再構築し、前記再構築された残差行列を動的にスケーリングして残差行列を得る手段と、
前記特異値分解から前記再構築までを前記残差行列に対して繰り返し適用して所定の基底ベクトルのセットを生成する手段と、
前記ドキュメント行列の次元削減を実行して、前記データベース内の前記ドキュメントの検出、検索および同定を行う手段と、
前記検索、同定および前記同定のうちの少なくとも１つの結果を前記クライアントに戻すための手段と
を含み、
前記スケールされた残差行列は、下記式
【数５】
0003870043.tif 000037
（上式中、Ｒｓは、スケールされた残差行列であり、ｒｉ（ｉは、ドキュメントの数Ｍ以下の整数である。）は、残差ベクトルであり、｜ｒｉ｜は、前記残差ベクトルのノルムであり、Ｔは、ベクトルに対して施される転置演算子であり、ｑは、前記所定の関数により動的に決定されるスケーリング・ファクタである。）により生成され、
前記所定の関数は、前記残差ベクトルの最大ノルムの関数であり、下記式
【数６】
0003870043.tif 000038
（上式中、ｐは、正の整数であり、ｔｍａｘは、前記残差ベクトルの最大ノルムである。）により与えられる、サーバ。
【請求項１２】
前記スケーリングするための手段は、前記基底ベクトルを得る各ステップごとに、異なるスケーリング・ファクタを使用する、請求項１１に記載のサーバ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、大きな行列の計算方法に関し、より詳細には、きわめて大きなデータベースにおける主要クラスタ、ミーディアム・クラスタおよびアウトライア・クラスタの効率的な検索、検出、同定を可能とする方法、コンピュータ・システム、コンピュータ可読な記録媒体およびサーバに関する。
【０００２】
【従来の技術】
近年におけるデータベース・システムは、ニュースデータ、顧客情報、在庫データなどの膨大な量のデータをますます取り扱うようになってきている。このようなデータベースのユーザは、充分な精度をもって迅速、かつ効果的に所望する情報を検索することが、ますます困難となっている。したがって、適時、かつ精度よく、さらには安価に大きなデータベースから新たなトピックスおよび／または新たな事項を検出することは、在庫管理、先物取引やオプション取引、世界中に多数のレポータを配置することなしにレポータへと迅速に指令を行うニュース
代理店、成功を収めるためには競合者についての主要、かつ新しい情報を知ることが必要なインターネットや、他の速いペースの行動に基づくビジネスといった、多くのタイプのビジネスに対し、きわめて価値ある情報を与えることになる。
【０００３】
従来ではデータベースの検索者は、検索をモニタするために別の要員を雇用する必要があるので、多くのデータベースにおけるドキュメントの検索、検出および同定は、コストが高く、労力を要し、時間を浪費する作業となっている。
【０００４】
検索エンジンにおける検索、検出、および同定方法は、近年ではデータベース内のデータをクラスタ化するためにベクトルモデルを用いている。この従来の方法は、概ねデータベース内のデータに対応したベクトルｆ（kwd1, kwd2,. . ., kwdn）を形成するものである。このベクトルｆは、kwd1, kwd2,. . ., kwdnといったデータに付されたアトリビュートの数に等しい次元を有するベクトルとして定義される。最も通常の場合には、アトリビュートは、単独のキーワード、フレーズ、人の名前、地名、日付などとされる。通常では数学的にベクトルｆを形成
するため、バイナリ・モデルが用いられ、このバイナリ・モデルにおいては、データがkwd1を含まない場合には、kwd1を０に設定し、データがkwd1を含む場合にはkwd1を１に設定する。ある場合には重み付け因子をバイナリ・モデルと組み合わせて、検索の精度が向上されている。このような重み付け因子としては、例えばデータ中におけるキーワードの出現回数を挙げることができる。
【０００５】
【発明が解決しようとする課題】
いくつかの統計的な手法が、ベクトル空間モデルに基づいた情報検索のためのアルゴリズムを用いて提案されてきている（例えば、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 DocumentProcessing）”, Prentice-Hall,Englewood Cliffs, NJ, 1971年において、ベクトル空間モデルを総説している。彼らは、ベクトルを用いてドキュメントをモデル化しており、ベクトルの各座標軸がベクトルのアトリビュート、例えばキーワードを表すものとされている。ベクトルのバイナリ・モデルにおいては、座標軸は、ドキュメントに当該アトリビュートが含まれていれば１の値とされ、当該アトリビュートがドキュメントに含まれていなければ０とされる。より高度化されたドキュメント・ベクトル・モデルでは、タイトル、セクションヘッダ、要約における出現回数および位置といったキーワードに対する重み付けが考慮される。
【０００７】
クエリーはまた、ドキュメントについて説明したと同一の方法により、ベクトルとしてモデル化される。所定のユーザ入力クエリーに対して、特定のドキュメントの類似度は、クエリーと、ドキュメント・ベクトルとのそれぞれの間の“距離”を決定することにより算出される。数多くの異なったノルムをクエリー・ベクトルとドキュメント・ベクトルとの間の“距離”計算するために用いることができるが、内積から得られるクエリー・ベクトルとドキュメント・ベクトルとの間の角度が、これらの間の距離を決定するため、最も普通に用いられるものであ
る。
【０００８】
Deerwester等に付与された米国特許第４，８３９，８５３号、名称“ラテント・セマンティック構造を用いたコンピュータ情報検索（Computer informationretrieval 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)により表されるｍ×ｎ行列ＭＮすなわち、
【００１０】
【数７】
0003870043.tif 000002
により表される。ここで、行列ＭＮの列は、データベースにおけるドキュメントそれぞれを表すベクトルである。
【００１１】
ステップ２：特異値分解によるランク付け問題の次元削減ＬＳＩ法の次のステップでは、特異値分解、すなわち行列ＭＮのＳＶＤ（Singular Value Decomposition）を実行する。行列ＭＮの次元は、特異値を大きい順に並べたときの１番目からｋ番目までの特異値σｉ、ｉ＝１，２，３，．．．，ｋを用いて行列を形成することにより削減され、これらの対応する特異ベクトルは、下記式から得られる。
【００１２】
【数８】
0003870043.tif 000003
上式中、Σｋは、σ１，σ２，σ３，．．．，σｋである対角要素が単調に減少する、対角行列である。行列ＵｋおよびＶｋは、行列ＭＮの大きい方からｋ番目までの特異値に対応する右側と左側の特異ベクトルの列を含む行列である。
【００１３】
ステップ３：クエリー処理
ＬＳＩ法に基づいた情報検索におけるクエリーの処理は、さらに２つのステップ、（１）クエリー射影ステップおよびそれに続いた（２）適合化ステップを含む。クエリー射影ステップでは、入力されたクエリーは、行列Ｖｋにより次元が削減されたクエリー−ドキュメント空間における擬ドキュメントへとマップされ、その後特異値σｉにより重み付けされる。
【００１４】
DeerwesterらのＬＳＩ法は、従来のベクトル空間モデルでは互いに検索されなかった類似するキーワード（例えば、“ムーン”、“ルナー”といった類義語の検索および同定を可能とすると共に、キーワードの意味づけの分析に基づいたクエリーに対するドキュメントの実時間検索を可能とし、許容される計算時間を可能とする。DeerwesterらのＬＳＩ法はまた、同一のスペリングを有しているが異なった意味を有する場合といった、いわゆる“ポリセミー”の問題を解決し、かつこの情報を検索の精度を向上させるために使用する。彼らの技術的なアイデアは、線形代数、具体的にはいかなる所定のサイズの矩形行列についての特異値分解(Singular Value Decomposition:SVD)を使用するものである。この特異値分解定理について図１にまとめて示す。また、特異値分解法のための３つの方法を概略的に図２〜図４に示す。
【００１５】
上述した特異値分解定理は、特異値分解法が行列Ａが正方行列である場合であっても実行することができる点で効果的である。特に行列Ａが実対称半正定値行列である場合には、行列Ａは、下記式のように変換できる。
【００１６】
【数９】
0003870043.tif 000004
【００１７】
上記式中、Ｓは、対角要素が特異値とされた対角化行列であり、上付きの文字“Ｔ”は、対応する行列の転置を示す。特異値分解の別の重要な特性は、図２〜図４に示した行列ＵとＶとが、直交行列なので、適切な次元のいかなるベクトルｘ，ｙでもノルムが保持できる、すなわち|ｘ|２＝Ｕ|ｘ|２および|ｙ|２＝Ｕ|ｙ|２となるということにある。この特異値分解の本質的な点は、図２〜図４に示すＳにより示される対角行列にある。この対角行列Ｓは、特異値である実数の対角要素を含んでおり、これらの特異値は、最大の特異値から降順で配列されている。
【００１８】
上述した特性を使用して、ドキュメント行列の次元削減が実行され、所定の数ｋの特異値が、最大の特異値から降順に選択され（通常では、ｋは、行列Aのランクよりも遙かに小さい。）、行列Ａを代表する対角行列が生成される。この次元削減方法は、概ね大きな特異値およびそれに対応する特異ベクトルに対応するドキュメントについては充分な結果を与える（Michael W. Berry, Susan T. Dumais, and Gavin W. O’ Brien, “Using Linear Algebra forIntelligent Information Retrieval”, SIAMReview, vol. 37, No. 4, pp. 573-595, 1995)。
【００１９】
小林らは、共分散行列を使用するドキュメント行列の次元を減少させるための別の効果的な方法を提案し出願を行っており、この方法を以下ＣＯＶ法という。この方法は、概ね下記のように説明することができる。
【００２０】
ステップ１：ドキュメントから上述したようにしてドキュメント行列を生成する。その後所定のＭ×Ｎのドキュメント行列について、下記式に従って、共分散行列を算出する。
【００２１】
【数１０】
0003870043.tif 000005
上式中、Ｋは、共分散行列を表し、ｄｉ、ｂａｒｄ、ｂａｒｄｉは、ドキュメント行列の要素ａｉ，ｊを使用して下記のように定義される。
【００２２】
【数１１】
0003870043.tif 000006
【００２３】
ステップ２：次いで、ＣＯＶ法においては、共分散行列の特異値ベクトルを算出する。共分散行列の特異値の算出は、Hausholder法、Lanczos法、またはニューラル・ネットワーク法といった当業界において周知の方法を使用して行うことができる。
【００２４】
ステップ３：さらにこの次に、ＣＯＶプロセスは、上述した行列Ｖに、上述した最大からｋ個の特異値ベクトルを含むようにして所望する次元がkとなるように、所定の数の特異値ベクトルを使用して共分散行列の次元削減を行う。その後、Ｍ×Ｎドキュメント行列の次元を、次元が削減された共分散行列を使用して削減し、データベース内に記録されたドキュメントの検索、検出、および同定を実行する。
【００２５】
上述した方法は、ＣＯＶ法において検索された結果の別の用途を与えるというＬＳＩ法に対して改善された結果を与えるが、共にデータベース中のドキュメントの検索および検出を行うために有効である。しかしながら、両方法は、上述したように次元減少プロセスを含んでおり、このため大規模データベースにおけるドキュメントの検索、検出、および同定においては本質的な不都合が生じる。
【００２６】
図５は、データベースから導かれるドキュメント空間の概略構成を示した図である。ドキュメント空間は、概ね主要（顕著）クラスタと、ミーディアム・クラスタと、アウトライア・クラスタと、ドキュメント内のキーワードの存在に関連してマッチング無しクラスタへと分類することができる。本明細書における用語、“主要クラスタ”とは、データベース内における全体のドキュメントの５％以上を占めるドキュメントを含むクラスタを意味する。本明細書における“ミーディアム・クラスタ”とは、データベース内において全体のドキュメントの概ね４％〜５％を占めるドキュメントを含むクラスタを意味する。本明細書における“アウトライア・クラスタ”とは、データベース内において全体のドキュメントの概ね３％〜４％を占めるドキュメントを含むクラスタを意味する。ドキュメント行列に対して次元減少が実行された場合には、通常では最大の特異値ベクトルまたは固有値ベクトルから、いくつかの固有値ベクトルまたは特異値ベクトルを考慮してクラスタの検索、検出、および同定の効率および精度を向上させるために次元の低減されたドキュメント行列を生成する。
【００２７】
このため、多くの場合では、アウトライア・クラスタは、次元の低減された行列では排除されてしまい、アウトライア・クラスタの上述したドキュメントは検索、検出、および同定ができないことになる。当然ながら、データベースの種類によっては上述したアウトライア・クラスタがドキュメントの検索において効果的に廃棄されることが好ましいものの、アウトライア・クラスタ内のドキュメントは、例えば新製品に関する問い合わせの情報を含むデータベースや、新製品の発売、または世界のどこかで発生した大地震といったように特定の時点で発生した後の時間経過で次第に蓄積される情報を含むような特定のデータベースでは、廃棄されるべきではない。上述したようなデータベースに含まれるドキュメントの検索では、アウトライア・クラスタは、上述した次元削減プロセスにおいて廃棄されないことが好ましい。
【００２８】
アウトライア・クラスタをドキュメント行列Ａの次元削減プロセスにおいて保持するいくつかの試みが提案されている。Ａｎｄｏは、”Latent Semantic Space: interactive scaling improves precision ofinter-document similarity measurement”, Proc. SIGIR 2000, pp. 216-223において、ドキュメント空間の次元を低下させる場合に、アウトライア・クラスタが廃棄されないように救済する方法を開示している。Ａｎｄｏのアルゴリズムは、擬似コードでは、図６のように説明することができる。
【００２９】
図６に示されるように、開示されたＡｎｄｏの方法は、まず、Ｍ×Ｎ行列として残差行列Ｒを定義する。ついで、このプロセスにおいては、残差ベクトルｒｉのノルム｜ｒｉ｜のｑ乗を乗じて残差行列Ｒをスケーリングし、スケーリングされた残差行列Ｒｓ（以下、本明細書においてはスケールド残差行列という。）を生成し、その後行列の積ＲｓＴＲｓの固有値ベクトルｂｉを算出する。さらにその後、Ａｎｄｏのプロセスは、算出された固有ベクトルｂｉを使用して行列Ｒを再構築する。
【００３０】
上述したプロセスの後、元々Ｎ次元であったドキュメント・ベクトルｄｉは、上述した図６に示したプロセスにより得られたこの基底ベクトルを使用するｋ次元へと低下されたｈａｔｄｉにより、下記式により近似される。
【００３１】
【数１２】
0003870043.tif 000007
【００３２】
図６に示した擬似コードにより示されるＡｎｄｏの方法は、スケーリング・ファクタとして定数を使用しており、ノルム｜ｒｉ｜のスケーリング・ファクタの累乗がそれぞれ対応する残差ベクトルｒｉに乗じられることとなる。Ａｎｄｏの方法は、スケーリング・ファクタｑが数値１よりも大きい場合には多くの場合に重大な問題を生じさせる。すなわち、ｑ＞１の場合には、基底ベクトルを決定する計算のための繰り返しサイクルが進行するにつれて、１よりも小さな残差行列の要素は、ますます小さくなり、１よりも大きな残差行列の要素はますます大きくなることである。
【００３３】
Ａｎｄｏの方法は、アウトライア・クラスタのうち小さなものを、次元削減プロセスにおいて廃棄してしまうという別の問題を生じさせることにもなる。本発明者らは、実験的にＡｎｄｏの方法はらさに、もともと１よりも小さなノルムのベクトルを数値計算の計算限界内としてしまって縮退させ、消滅させてしまうという重大な問題を生じさせてしまい、図６に示したステップ２の計算を実行不可能としてしまうことを見出した。
【００３４】
加えて、従来の方法は著しく大きなメモリ資源を必要とするとともに、きわめて高いＣＰＵ性能を要求し、ときとして残差行列を得るためのループが、上述した残差行列を固有値計算ができないような行列へと変貌させてしまうこととなる。上述した問題に加え、例えば１００万の実際のドキュメントが含まれ、キーワードが数万というきわめて大きなデータベースの固有値計算についてみれば、従来の計算方法では、汎用目的のコンピュータを使用して実質的に不可能となってしまうことになる。
【００３５】
したがって、これまで主要クラスタ、ミーディアム・クラスタ、アウトライア・クラスタを廃棄することなく、きわめて大きなデータベースにおいてドキュメントを検索、検出、および同定するための方法、コンピュータ・システム、プログラムおよびサーバが必要とされている。
【００３６】
また、いかなる所定のドキュメント行列においても計算機上の問題を生じさせずにきわめて大きなデータベースにおけるドキュメントの検索、検出、および同定を行うための方法、コンピュータ・システム、プログラムおよびサーバが必要とされている。
【００３７】
さらに、主要（顕著）クラスタに含まれるサブクラスタよりもアウトライア・クラスタまたは複数のアウトライア・クラスタに対して鋭敏で、きわめて大きなデータベースにおけるドキュメントの検索、検出および同定を行うための方法、コンピュータ・システム、プログラム、およびサーバが必要とされている。
【００３８】
さらにまた、許容可能な計算時間および計算機資源の下できわめて大きなデータベースに含まれるドキュメントの検索、検出、および同定を行うための方法、コンピュータ・システム、プログラム、およびサーバが必要とされている。
【００３９】
【課題を解決するための手段】
本発明は、上述したパラメータｑは、残差ベクトルのノルムを考慮して決定されるべきであり、その結果として特異値分解プロセスの繰り返しサイクルによる残差ベクトルの縮退を生じ無くさせることができるという認識の下になされたものである。
【００４０】
本発明のプロセスは、まずベクトル空間モデルに従ってドキュメントを含むきわめて大きなデータベースからＭ×Ｎの形態のドキュメント行列を形成する。特異値分解法における繰り返しにおいて、初期残差行列Ｒとしてドキュメント−キーワード行列Ａを選択する。生成された残差行列Ｒは、適切に下記式により表される。
【００４１】
【数１３】
0003870043.tif 000008
上式中、ｒｉ（ｉは、ドキュメントの数Ｍ以下の整数である。）を、以後トップからｉ番目の残差ベクトルとして定義し、Ｔを、その転置を意味するものとする。
【００４２】
本発明においては、残差行列はさらにスケーリング関数ｆｕｎｃによりスケーリングされ、このスケーリングは、下記式により定式化できる。
【００４３】
【数１４】
0003870043.tif 000009
【００４４】
次いで、スケールド残差行列Ｒｓについて、特異値分解を計算して最大の特異値ベクトルｂ１を得る。ついで、残差行列Ｒを下記式
【００４５】
【数１５】
0003870043.tif 000010
に従って再構築する。
【００４６】
再構築された残差行列Ｒは、ドキュメント行列Ａからの以前の最も大きな特異値ベクトルを含んでおらず、このため次の残差行列Ｒの最も大きな特異値ベクトルは、その方向を変化させ、アウトライア・クラスタの方へと向けられることになり、アウトライア・クラスタの検索、検出、および同定を改善することが可能となる。加えて、スケーリング関数ｆｕｎｃは、残差ベクトルの最大ノルムに依存し、スケーリング関数がアウタライア・クラスタの縮退を生じさせないように調整される。トップからｉ番目の特異値ベクトルが計算における重大な誤りを生じさせること無く導かれ、アウトライア・クラスタのドキュメント・ベクトルへとより近接するので、アウトライア・クラスタの検索、検出、および同定が相乗的に改善されることになる。
【００４７】
【００４８】
【００４９】
【００５０】
【００５１】
また、本発明においては、データベースにおいてドキュメントを検索、検出、および同定するためのコンピュータ・システムであって、前記データベース内の前記ドキュメントが、該ドキュメントに含まれるアトリビュートからドキュメント行列として構成され、前記コンピュータ・システムは、
少なくとも１つのアトリビュートを使用して前記ドキュメントから前記ドキュメント行列を生成する手段と、
所定の関数から前記ドキュメント行列に基づいてスケールされた残差行列を生成する手段と、
特異値分解を実行して最大の特異値に対応する基底ベクトルを得るステップと、
前記残差行列を再構築し、前記再構築された残差行列を動的にスケーリングして別の基底ベクトルを得る手段と、
前記特異値分解ステップから前記再構築ステップまでを繰り返して所定の基底ベクトルのセットを生成する手段と、
前記ドキュメント行列の次元削減を実行して、前記データベース内の前記ドキュメントの検出、検索および同定を行う手段と
を含むコンピュータ・システムが提供される。
【００５２】
本発明によれば、さらに、データベースにおいてドキュメントを検索、検出、および同定する方法を実行するためのコンピュータ・プログラムであって、
前記データベース内の前記ドキュメントが、該ドキュメントに含まれるアトリビュートからドキュメント行列として構成され、前記コンピュータ・プログラムはコンピュータに、
少なくとも１つのアトリビュートを使用して前記ドキュメントから前記ドキュメント行列を生成するステップと、
所定の関数から前記ドキュメント行列に基づいてスケールされた残差行列を生成するステップと、
特異値分解を実行して最大の特異値に対応する基底ベクトルを得るステップと、
前記残差行列を再構築し、前記再構築された残差行列を動的にスケーリングして別の基底ベクトルを得るステップと、
前記特異値分解ステップから前記再構築ステップまでを繰り返して所定の基底ベクトルのセットを生成するステップと、
前記ドキュメント行列の次元削減を実行して、前記データベース内の前記ドキュメントの検出、検索および同定を行うステップと
を実行させる、コンピュータ・プログラムが提供される。
【００５３】
本発明によれば、さらに、データベースにおいてドキュメントを検索、検出、および同定するためのサーバであって、前記データベース内の前記ドキュメントが、該ドキュメントに含まれるアトリビュートからドキュメント行列として構成され、ネットワークを通してクライアントと通信するサーバであって、前記サーバは、前記ネットワークを通して検索、検出および同定のためのリクエストを受信する手段と、
前記クライアントから特異値分解のための方法を選択する別のリクエストを受信する手段と、
少なくとも１つのアトリビュートを使用して前記ドキュメントから前記ドキュメント行列を生成する手段と、
所定の関数から前記ドキュメント行列に基づいてスケールされた残差行列を生成する手段と、
前記別のリクエストに応じて特異値分解を実行して最大の特異値に対応する基底ベクトルを得る手段と、
前記残差行列を再構築し、前記再構築された残差行列を動的にスケーリングして別の基底ベクトルを得る手段と、
前記特異値分解ステップから前記再構築ステップまでを繰り返して所定の基底ベクトルのセットを生成する手段と、
前記ドキュメント行列の次元削減を実行して、前記データベース内の前記ドキュメントの検出、検索および同定を行う手段と、
前記検索、同定および前記同定のうちの少なくとも１つの結果を前記クライアントに戻すための手段とを含むサーバが提供できる。
【００５４】
【発明の実施の形態】
以下、本発明を図面に示した態様をもって説明するが、本発明は、後述する実施の態様に制限されるものではない。
【００５５】
図７は、本発明の方法を実行するためのコンピュータ・システムを示した図である。図７に示したコンピュータ・システム１０は、概ねコンピュータ１２と、記憶デバイス１４と、キーボードといった入力デバイス１６と、マウスといったポインティング・デバイス１８とを含んで構成されている。コンピュータ１２は、中央処理ユニット（図示せず）と、ＲＡＭ、またはＲＯＭ、またはそれらの両方を含んでいて、本発明の方法を実行させる構成とされている。図７に示された記憶デバイス１４は、コンピュータ１２の外部に接続されているのが示されているが、記憶デバイス１４は、必要とされる記憶容量が保証される限り、ハード−ディスクといった形態においてコンピュータ１２の内部に含まれていてもよい。
【００５６】
記憶デバイス１４は、検索される、または検出または同定されるドキュメントを保持しており、記憶手段１４内のドキュメントは、当業界においてよく知られている適切なデータベース・ソフトウエアによりフォーマットすることができる。ドキュメント行列は、ドキュメントに含まれるアトリビュートを使用してバイナリ・モデルから生成され、コンピュータ・システム１０に含まれる適切な記憶領域に記憶されている。本発明においては、検索されるドキュメントとしては、テキスト・ドキュメント、オーディオ・ファイル、イメージ・ファイル、マルチメディア・ファイル、ビデオ・ファイル、ウエッブ・ページ、時間依存の検索および検出を行うためタイム・スタンプを含むいかなるドキュメントを挙げることができる。
【００５７】
コンピュータとしては、ＰＥＮＴＩＵＭシリーズ（ＩＮＴＥＬ・コーポレーションの商標）といったＣＰＵ、および／またはこれと互換性のあるＣＰＵを搭載したパーソナル・コンピュータおよび／またはＰＯＷＥＲ  ＰＣを搭載するＲＳ−６０００（インターナショナル・ビジネスマシーンズ・コーポレーションの商標）といったワークステーションおよび／またはこれに互換性のあるワークステーションであって、ＷＩＮＤＯＷＳ／ＭＥ（マイクロソフト・コーポレーションの商標）、ＷＩＮＤＯＷＳ  ２０００（マイクロソフト・コーポレーションの商標）、ＷＩＮＤＯＷＳ  ＮＴ（マイクロソフト・コーポレーションの商標）、ＯＳ／２（インターナショナル・ビジネスマシーンズ・コーポレーションの商標）、ＭＡＣ  ＯＳ（アップル・コンピュータコーポレーションの商標）を実行させることができるものを挙げることができるが、本発明においてはこれらに限定されるものではなく、いかなるコンピュータまたはワークステーションであっても用いることができる。本発明においては、本発明のコンピュータ・システム１０のユーザは、キーボード１６および／またはマウス１８により、コンピュータ・システム１０に対して自分でクエリーを入力することもできる。しかしながらクエリー入力の際のユーザ−コンピュータのインタフェイスは、上述したものに限定されず、クエリーをユーザが入力することができる、ペン、スタイラス、ジョイスティックといったデバイスなど、いかなる入力デバイスでも用いることができる。
【００５８】
ユーザからのリクエストを受け取ると、コンピュータ・システム１０は、ユーザのリクエストに応じて潜在的意味解析法：ラテント・セマンティック・インデキシング法（ＬＳＩ法）と共分散マトリックス法（ＣＯＶ法）との間において特異値分解プロセスを切り替えることができるように構成されていて、計算時間、システム資源、コンピュータ・システムのユーザにより要求される別の条件に応じて、ユーザが希望する計算方法が、システムにより提供されるようにされている。
【００５９】
図８は、本発明のコンピュータ・システム２２の別の実施の形態を示した図である。図８に示されるように、本発明のコンピュータ・システム２２は、サーバ・コンピュータ２４と、クライアント・コンピュータ２６との間においてトランザクションを可能とするネットワーク・システムとして構成することもできる。サーバ・コンピュータ２４は、ネットワーク２８を通してクライアント・コンピュータ２６と通信し、クライアントまたは複数のクライアント２６は、サーバ・コンピュータ２４に接続された記憶デバイス３０に保持されたドキュメントを検索、検出および同定することができる構成とされている。このサーバ・コンピュータ２４には、本発明の方法を実行するためのプログラムが搭載されていて、検索、検出、および同定の結果は、インターネット・インフラベースといったネットワーク２８を通して、クライアント・コンピュータ２６の要求に応じてクライアント・コンピュータ２６へと通信される。本発明において使用することができるネットワーク２８としては、これに限定されるものではなく、ＴＣＰ／ＩＰといったプロトコル、またはいかなる他の好適なプロトコルを使用するローカル・エリア・ネットワーク／ワイド・エリア・ネットワーク（ＬＡＮ／ＷＡＮ）および例えば、光通信、衛星通信、地上波通信など、いかなる別のネットワークであっても用いることができる。
【００６０】
図９は、コンピュータ・システム１０またはサーバ・コンピュータ２４により実行される本発明の方法の概略フローチャートを示す。本発明のプロセスは、ステップＳ１から開始し、ステップＳ２へと進んでＭ×Ｎのドキュメント行列Ａをベクトル空間モデルに従って生成する。本発明においては、バイナリ・ベクトル空間モデルと共にアトリビュートの頻度に応じた重み係数を使用して、結果の精度を向上させることもできる。ここで、Ｍは、データベースに保持されているドキュメントの数を表し、Ｎは、システムまたはユーザ入力により予め選択された検索、検出および同定のために使用されるアトリビュートの数を表す。
【００６１】
次いで、このプロセスは、ステップＳ３へと進んでデータベース中のドキュメントを均等に処理するためにドキュメント行列Ａの正規化を、例えばそれぞれのドキュメント・ベクトルのノルムを１とすることにより実行する。次いで、プロセスは、ステップＳ４へと進んで残差行列を定義する。残差行列の初期行列は、ドキュメント行列Ａとされるので、ドキュメント行列Ａの最大の特異値ベクトルは、後続する繰り返しにおいて取り除かれると共に決定することができる。
【００６２】
さらにその後、プロセスは、ステップＳ５へと進んで、残差ベクトルの最大のノルムのもの、ｔｍａｘを使用して残差行列ｒｉについてスケーリング・ファクタｑを算出する。スケーリング・ファクタｑは、ｉ−番目の基底ベクトルを得るための繰り返しサイクルが繰り返されるたびごとに決定され、所定の関数により与えられる。スケーリングのための関数（以下、スケーリング関数という。）については、詳細に後述する。残差行列および残差ベクトルは、下記式で定義される。
【００６３】
【数１６】
0003870043.tif 000011
【００６４】
上式中、Ｒは、残差行列であり、ｒｉは、ｉ−番目の残差ベクトルであり、“Ｔ”は、その転置を表す。スケーリング・ファクタｑは、上述した残差ベクトルｒｉへと結合されて、下記式によりスケールされた残差行列を生成する。
【００６５】
【数１７】
0003870043.tif 000012
【００６６】
図９を参照して、本発明のプロセスはさらにステップＳ６へと進んで、スケールド残差行列Ｒｓについて特異値分解計算を行ない、対象とされている残差行列Ｒｓの最大特異値を決定すると共に、対応する特異値ベクトルｂ１を決定する。本発明においては、特異値分解の手順は、ステップＳ６に示されているようにＬＳＩ法またはＣＯＶ法の間においてユーザ選択に基づいて選択することができる。本発明においてｉ番目の特異値ベクトルには、さらに修正型Gram-Schmidt直交化(Golub, G.and Van Loan, C., Matrix Computation, third ed., Johns Hopkins Univ. PressBaltimore, MD, 1983)が実行され、精度が改善される。
【００６７】
さらにこの後、プロセスは、次元削減に使用される基底ベクトルｂｉを、適切なメモリ手段へと出力し、次元削減のための基底ベクトルのセットが、繰り返しサイクルの後に与えられることになる。プロセスはさらにステップＳ９において整数ｉがｋ以下であるか否かを判断する。ｉがｋ以下である場合には（ｎｏ）、残差行列ＲをステップＳ１０において再構築する。ｉがｋよりも大きい場合には（ｙｅｓ）、プロセスはステップＳ１１へと進んで終了する。
【００６８】
ステップＳ４〜Ｓ１０の繰り返しは、ｉがｋより大きくなり、ドキュメント行列Ａのための次元削減のｋ個の基底ベクトル｛b1, b2, …, bk｝が図９に示したプロセスにおいて生成される。
【００６９】
図１０は、図９のステップＳ４−ステップＳ１０の詳細な擬似コードの実施の形態を示した図である。ここでは、ユーザは、特異値分解法のためにＬＳＩ法を選択している。図１０に示されるように、プロセスは、まず残差行列Ｒを、図９に示すようにＭ×Ｎのドキュメント行列Ａへと初期化し、かつドキュメント行列Ａの次元を低下するための整数ｋを決定する。ドキュメント行列Ａについて正規化ステップを導入し、ドキュメント・ベクトルが均等に処理できるようにすることも可能である。
【００７０】
次いでこのプロセスは、残差行列Ｒの残差ベクトルｒｉのノルムを計算し、その後スケーリング・ファクタｑが、残差ベクトルの最大ノルムを与える所定の関数ｔｍａｘを使用して以下のように決定される。
【００７１】
【数１８】
0003870043.tif 000013
【００７２】
本発明の手順においては、ｔｍａｘの値を使用してスケーリング・ファクタｑを決定する。これは我々本発明者らが、実験的にスケーリング・ファクタがアウトライア・クラスタについての従来の検索および検出において発生する問題を生じさせており、そのため最大ノルムが適切に調節されるべきであることを見出したことに基づくものである。
【００７３】
さらに、次いでプロセスは、Ｍ×Ｎ形式のスケールド残差行列Ｒｓを下記式により生成する。
【００７４】
【数１９】
0003870043.tif 000014
【００７５】
説明している実施の形態においては、スケーリング・ファクタｑおよび最大ノルムの残差ベクトルｒｍａｘは倍精度変数とされているが、これに限られることなく、必要とされる検索および検出の精度が得られる限り、いかなる精度レベルでも用いることができる。
【００７６】
その後、プロセスは、スケールド残差行列Ｒｓに対して特異値分解を実行して、ベクトルＶＴの第１行として基底ベクトルｂｉを得る。説明している擬似コードにおいては、基底ベクトルには、さらに修正型Gram-Schmidt直交化（ＭＧＳ）が適用されて精度が向上されているが、これに限定されず、いかなる直交化法であっても用いることができるし、上述した直交化は、直交性が担保できる限りにおいてはプロセスに含まれなくともよい。
【００７７】
プロセスは、さらに算出された基底ベクトルｂｉから下記式に従って残差ベクトルＲの再構築を行う。
【００７８】
【数２０】
0003870043.tif 000015
【００７９】
図１１は、本発明による可変スケーリング・ファクタｑの機能をグラフ的に表現した図である。本発明におけるスケーリング法を図１１（ａ）に示し、従来のスケーリング法を図１１（ｂ）に示す。
【００８０】
図１１（ａ）に示されるように本発明は、残差ベクトルの最大ノルムｔｍａｘに依存させて動的にスケーリング・ファクタｑを変更させるものである。スケーリング・ファクタｑを調節することで、各繰り返しサイクルごとに残差ベクトルのノルムの過剰な低減が避けられるので、上述した変更は、最初に見出されたアウトライア・クラスタ以外のアウトライア・クラスタのベクトルが縮退してしまうのを、図１１（ａ）に示すように防止することになる。本発明の特定の実施の形態においては、スケーリング・ファクタｑは、ｔｍａｘに依存する下記関数“ｆｕｎｃ”により決定される。
【００８１】
【数２１】
0003870043.tif 000016
上式中、ｐは、整数であり、好ましい実施の形態においては、１を選択することが好ましい。
【００８２】
上記式に示されるように、ｔｍａｘが１よりも大きい場合には、スケーリング・ファクタｑは、１／ｔｍａｘに設定され、ｔｍａｘが略１の場合には、スケーリング・ファクタｑは、ｐ＋ｔｍａｘに設定され、ｔｍａｘが１よりも小さい場合には、スケーリング・ファクタｑは、１／（１０２−ｔｍａｘ）に設定される。本発明のスケーリング・ファクタｑは、残差行列のスケーリング・ファクタを制御し、基底ベクトルが最大の残差ベクトルに著しく影響されないようにしつつ、スケーリングの効果を適切に保証するものであるが、本発明においてはこれに制限されず、スケーリング・ファクタｑは、上述したスケーリング関数ｆｕｎｃ以外にもスケーリング・ファクタｑが基底ベクトルの決定に関する繰り返しサイクルのそれぞれにおいて変更されるものである限り、いかなる関係に基づいても選択することができる。
【００８３】
一方で、図１１（ｂ）に示すように、残差ベクトルの従来のスケーリングにおいては、各残差ベクトルおよび各繰り返しサイクルごとに定数のスケーリング・ファクタが使用され、ノルムが１以下の残差ベクトルと、１よりも大きい整数ｑとが共に適用された場合には、ノルムが１未満の残差ベクトルは、ｋ個の基底ベクトルを算出する繰り返しサイクルの繰り返しに関連して小さくなり続け、図１１（ｂ）に示すようにノイズレベルの近傍で残差ベクトルが縮退してしまうことになる。
【００８４】
上述した実施の形態においては、ｔｍａｘが略１であるという条件は、本発明においては下記式で定義される。
【００８５】
【数２２】
0003870043.tif 000017
εの値は、特定の用途に応じて選択することができ、典型的には略０．０１に選択される。しかしながら、εの値が大きくなるとスケーリングは、従来の方法に近づいて行くこととなる。
【００８６】
さらなる本発明の効果は、次元削減のための基底ベクトルの算出方法の差に基づいて得られる。従来の方法においては、固有ベクトルは、直接ＲｓＴＲｓから算出されている。従来の方法とは対照的に、本発明の方法では、特異値分解を使用し、最大の特異値ベクトルに対応する右特異値ベクトルのみを算出する。
【００８７】
したがって、本発明の方法は、ＣＰＵ性能、メモリ資源といったコンピュータ資源を節約しつつ、アウトライア・クラスタの検索の精度を保証することに加え、高速、かつ実時間検索、または検出、またはそれら双方を提供することができる。
【００８８】
図１２は、特異値分解法の実行のために、ＣＯＶ法を使用する別の実施の形態を示した図である。それ以外の手順については図１０において説明した実施例と同一なので、ＣＯＶ法以外については、本明細書においては説明しない。上述したようにスケールド残差行列が計算された後、共分散行列Ｋが、下記のようにして生成される。
【００８９】
【数２３】
0003870043.tif 000018
上式中、ｄｉ、ｂａｒｄ、ｂａｒｄｉは、下記のように定義される。
【００９０】
【数２４】
0003870043.tif 000019
【００９１】
その後、生成された共分散行列の特異値分解を計算して、ドキュメント行列Ａの次元削減のための基底ベクトルを決定する。本発明者らは、以前にドキュメント行列の共分散ベクトルの主要な特異値ベクトルは、実質的にドキュメント行列の特異値ベクトルと同一の方向を有していることを見出し、ＣＯＶ法がきわめて大きなデータベースをモデルとするドキュメント行列の次元削減に特に有効であることを見出している。上述した別の実施の形態において、共分散行列は稠密な行列となるが、共分散行列Ｋは、Ｎ×Ｎの正方行列となり、ドキュメント数Ｍが多いので、アトリビュートの数が典型的にはドキュメント数よりも２桁少なく、特異値分解計算が、著しく短時間で実行できることになる。
【００９２】
図１２の手順は、図１０において説明したようにさらに残差行列Ｒの再構築および繰り返しサイクルへと進んで、ｋ個の基底ベクトルの決定されるまで繰り返されることになる。
【００９３】
以下に、本発明を特定の実施例を持って説明するが、実施例は、本発明を制限するものではなく、本発明を説明するためだけに与えられるものである。
【００９４】
【実施例】
１４０ドキュメントおよび４０キーワード・セットを含むサンプル・データベースを構成したドキュメントおよびキーワードは、以下のものとした。
【００９５】
＜１４０ドキュメントの内容＞
(1)キーワード“クリントン”に関連するドキュメント       25ドキュメント
“クリントン”＋“アル・ゴア”のみを含むドキュメント  10ドキュメント
“クリントン”＋“ヒラリー”のみを含むドキュメント     5ドキュメント
“クリントン”＋“アル・ゴア”＋“ヒラリー”の
すべてを含むドキュメント                              10ドキュメント
（ドキュメントＮｏ．１〜２５）
【００９６】
(2)キーワード“Ｊａｖａ”に関連するドキュメント         25ドキュメント
“Ｊａｖａ”＋“ＪＳＰ”のみを含むドキュメント        10ドキュメント
“Ｊａｖａ”＋“ａｐｐｌｅｔ”のみを含むドキュメント   5ドキュメント
“Ｊａｖａ”＋“ＪＳＰ”＋“ａｐｐｌｅｔ”の
すべてを含むドキュメント                              10ドキュメント
（ドキュメントＮｏ．２６〜５０）
【００９７】
以下のドキュメントは、アウトライア・クラスタとしてリストできる。
(3)キーワード“Bluetooth”に関連するドキュメント          5ドキュメント
（ドキュメントＮｏ．５１〜５５）
【００９８】
(4)キーワード“サッカー”に関連するドキュメント           5ドキュメント
（ドキュメントＮｏ．５６〜６０）
【００９９】
(5)キーワード“マトリックス”に関連するドキュメント       5ドキュメント
（ドキュメントＮｏ．６１〜６５）
【０１００】
(6)キーワード“ＤＮＡ”に関連するドキュメント             5ドキュメント
（ドキュメントＮｏ．６６〜７０）
【０１０１】
以下のドキュメントは、ノイズである。
(7)上述したクラスタには、分類されないドキュメント        70ドキュメント
（ドキュメントＮｏ．７０〜１４０）
【０１０２】
本明細書においては、主要クラスタを“クリントン”クラスタおよび“Ｊａｖａ”クラスタと呼ぶ。これらの主要（顕著）クラスタは、それぞれが５ドキュメントを含む“クリントン”＋“ヒラリー”サブクラスタおよび“Ｊａｖａ”＋“ａｐｐｌｅｔ”サブクラスタに区別されるサブクラスタを含んでいる。他方で、対象であるアウトライア・クラスタは、それぞれ５ドキュメントを含む孤立したクラスタである。クラスタ“クリントン”＋“ヒラリー”およびクラスタ“Ｊａｖａ”＋“ａｐｐｌｅｔ”は、それぞれ５つのドキュメントを含んでいるが、クラスタ“クリントン”＋“ヒラリー”およびクラスタ“Ｊａｖａ”＋“ａｐｐｌｅｔ”は、それぞれが５ドキュメントを含んでいるものの、主要クラスタ“クリントン”および“Ｊａｖａ”のサブクラスタであり、アウトライア・クラスタではない。サブクラスタとアウトライア・クラスタとは、それぞれ５ドキュメントを含んでいて、サブクラスタおよびアウトライア・クラスタの割合は、１４０ドキュメントのうち、それぞれ３．５％にすぎないものである。実施例において使用したキーワードを図１３に示す。
【０１０３】
実施例においては、本発明者らは、通常のベクトル空間モデルについて次元減少手順を使用してアウトライア・クラスタが検索されるか否かを検討した。元の１４０×４０次元の行列の要素を、アトリビュートの頻度に応じた重み係数を使用してドキュメントへのアトリビュート（すなわち、キーワード）の関連性に基づいて０または正の実数で構築した。
【０１０４】
図１４は、ドキュメント−キーワード空間の要素の典型的な構成を示した図である。図１４においては、ドキュメント００１についての要素は、“１  １．０  ２  １．０  ４  ０．４”で記述されている。ドキュメントの表現は、（非ゼロの要素の位置，ウエイト）のペアとされており、ゼロの要素の位置については、表現を簡略化するために省略している。アトリビュートの頻度に応じた重み係数の値は、キーワードへの関連性が高まるにつれて高くなるように設定されている。キーワードの順番は、図１４に示した順番とした。すなわち、位置１は、キーワード“クリントン”であり、位置４は、キーワード“チェルシー”などである。ドキュメントは、その次元を本発明のスケーリング法により得られた算出された基底ベクトルを使用して、６次元まで削減させた。サンプル・データベースにおけるそれぞれのドキュメントの要素を表１〜表６に示す。
【表１】
0003870043.tif 000020
【０１０５】
【表２】
0003870043.tif 000021
【０１０６】
【表３】
0003870043.tif 000022
【０１０７】
【表４】
0003870043.tif 000023
【０１０８】
【表５】
0003870043.tif 000024
【０１０９】
【表６】
0003870043.tif 000025
【０１１０】
（実施例１）
＜アルゴリズム１の結果＞
上述したように構成されたサンプル・データベースに本発明を適用して、アルゴリズム１に従ってその次元を削減させた。サンプル・ドキュメント行列の次元を、本発明のスケールド残差行列を使用して４０キーワード次元から６キーワード次元にまで削減させた。ｋ番目のクラスタについて関連性の尺度、すなわち“similarity average：ＳＡ”、Ωｋを下記式に従って算出して、キーワードのランダムな入力の影響を排除した。
【０１１１】
【数２５】
0003870043.tif 000026
【０１１２】
表７に、アルゴリズム１に従って検索および検出を行う本発明の方法の結果を示す。
【０１１３】
【表７】
0003870043.tif 000027
【０１１４】
表２に示されるように、アウトライア・クラスタは、本発明を使用した次元減少プロセスの間に保持されていると共に、アウトライア・クラスタは、良好に検出、検索および同定されているのが示される。
【０１１５】
（実施例２）
＜アルゴリズム２の結果＞
上述したように構成されたサンプル・データベースに本発明を適用して、アルゴリズム１に従ったことを除き、他の条件を同一にしてその次元を減少させた。
表３に、算出された結果を、similarityaverage (SA)として表現して示す。
【０１１６】
【表８】
0003870043.tif 000028
【０１１７】
表８に示されるように、アウトライア・クラスタのすべてが高い関連性スコアをもって検索および検出され、このため本発明の方法がアウトライア・クラスタの検出、検索、同定にきわめて効果的であることが示される。
【０１１８】
（比較例）
同一のサンプル・データベースおよび同一の評価方法を使用して従来の方法により得られる結果と比較することによって、本発明の方法の有効性を検討した。
【０１１９】
比較例においては、サンプル・データベースを、ＬＳＩ、ＣＯＶ、およびＡｎｄｏのスケーリング法（ｑ＝２と設定した。）により次元削減を行った。それぞれの結果を表９〜表１１に示す。表９に示されるＬＳＩを使用した結果は、アウトライア・クラスタの順位は低く、similarity averageは、ノイズレベル程度に低くなっている。ＣＯＶ法を使用する場合には、表１０に示されるように、similarity averageの値は、ノイズレベルの上にまで著しく高められているが、アウトライア・クラスタの順位は、依然として低いままである。
【０１２０】
表１１に示すＡｎｄｏのスケーリング法は、アウトライア・クラスタの順位を僅かに高めるものの、いくつかのアウトライア・クラスタは、依然として小さなsimilarity averageのままとされている。また、この方法は、計算に対する破壊的な影響およびコンピュータ資源の消耗を考慮した場合、大規模なデータベースにおけるアウトライア・クラスタの検出、検索、および同定には不向きである。
【０１２１】
【表９】
0003870043.tif 000029
【０１２２】
【表１０】
0003870043.tif 000030
【０１２３】
【表１１】
0003870043.tif 000031
【０１２４】
上述した結果を、表１２にまとめる。表１２中、ｂｉは、ｉ番目の基底ベクトルを示し、Ｃは、主要クラスタ・クリントンを示し、Ｊは、主要クラスタＪａｖａを示し、Ｎは、ノイズを示し、Ｏは、アウトライア・クラスタ（全部）を示し、Ｂは、Bluetoothアウトライア・クラスタを示し、Ｓは、サッカー・クラスタを示し、Ｍは、マトリックス・アウトライア・クラスタを示し、Ｄは、ＤＮＡクラスタを示す。表１２は、それぞれのクラスタが見出された基底ベクトルに対応してまとめている。表１２に示されるように、従来のスケーリング法は、最初のアウトライア・クラスタを基底ベクトルが４番目のｂ４において見出しているが、本発明の方法は、アウトライア・クラスタの検出をより高いｂ３またはアルゴリズム２においてはｂ２の基底ベクトルにおいて見出すことに成功しているのがわかる。
【０１２５】
【表１２】
0003870043.tif 000032
【０１２６】
上述したように、本発明は、複数のアウトライア・クラスタがドキュメントに含まれている場合にアウトライア・クラスタを検索、検出、および同定するための方法を提供することができる。本発明の方法は、新製品についての問い合わせ情報のように、所定の時点の後蓄積されるドキュメントの検索、検出、および同定に加え、アウトライア・クラスタの検索、検出、および同定に有効である。
【０１２７】
これまで、本発明を特定の態様をもって説明を行ってきた。しかしながら、当業者によれば、本発明の範囲を逸脱することなく、種々の除外、変更、および他の態様が可能であることは理解できよう。
【０１２８】
本発明は、これまで検索、検出および同定のための方法について詳細に説明してきたが、本発明はまた、本発明で説明した方法を実行するためのシステム、方法自体、本発明の方法を実行するためのプログラムが記録された、例えば光学的、磁気的、電気−磁気的記録媒体といったコンピュータ可読な記録媒体をも含むものである。
【図面の簡単な説明】
【図１】  特異値分解法を要約して示した図。
【図２】  特異値分解法の代表的な方法を示した図。
【図３】  特異値分解法の別の代表的な方法を示した図。
【図４】  特異値分解法のさらに別の代表的な方法を示した図。
【図５】  データベースから導かれるドキュメント空間の構成を示した図。それぞれのクラスタから出発するそれぞれの矢線は、それぞれのクラスタの最大の基底ベクトルを示す。
【図６】  残差ベクトルの従来のスケーリング法を示した擬似コード。
【図７】  本発明の方法を実行するためのコンピュータ・システムの実施の形態を示した図。
【図８】  本発明の方法を実行するための別のコンピュータ・システムの実施の形態を示した図。
【図９】  本発明の方法の概略的なフローチャート。
【図１０】  ユーザが特異値分解法のためにＬＳＩ法を選択した場合の図９のステップＳ４〜ステップＳ１０の詳細な擬似コードを示した図。
【図１１】  本発明による可変スケーリング・ファクタｑの機能をグラフ的に示した図。
【図１２】  特異値分解法のためにＣＯＶ法を使用する場合の擬似コードを示した図。
【図１３】  本発明の実施例において使用するキーワードを示した図。
【図１４】  ドキュメント−キーワード空間における要素の構成を示した図。
【符号の簡単な説明】
１０…コンピュータ・システム
１２…コンピュータ
１４…記憶デバイス
１６…キーボード
１８…マウス
２２…コンピュータ・システム
２４…サーバ・コンピュータ
２６…クライアント・コンピュータ
２８…ネットワーク
３０…記憶デバイス
【図１】
0003870043.tif 000039
【図２】
0003870043.tif 000040
【図３】
0003870043.tif 000041
【図４】
0003870043.tif 000042
【図５】
0003870043.tif 000043
【図６】
0003870043.tif 000044
【図７】
0003870043.tif 000045
【図８】
0003870043.tif 000046
【図９】
0003870043.tif 000047
【図１０】
0003870043.tif 000048
【図１１】
0003870043.tif 000049
【図１２】
0003870043.tif 000050
【図１３】
0003870043.tif 000051
【図１４】
0003870043.tif 000052