(57)【要約】【課題】  コンピュータ実行可能な次元削減方法、コンピュータをして該次元削減方法を実行させるためのプログラム、次元削減装置および該次元削減装置を使用した検索エンジンを提供する。【解決手段】  コンピュータにより数値行列を次元削減して、情報を提供するための次元削減行列とする次元削減装置は、ランダム平均行列RAVを使用して次元削減行列、あるいは次元削減するためのインデックス・データを生成して格納させる処理部３２を含んでいる。処理部３２は、さらに、シャッフル情報として使用されるシャッフル・ベクトルを生成させるシャッフル・ベクトル生成部４４と、シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素から非正規基底ベクトルを生成し、格納する非正規基底ベクトル生成部４６とを含んでいる。【選択図】  図９
2005050197.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより数値行列を次元削減して、情報を提供するための次元削減方法であって、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成し、メモリに格納させるステップと、
前記シャッフル情報を使用して直交化された基底ベクトルにより前記数値行列の次元削減を実行させるステップと
を含む次元削減方法。
【請求項２】
前記シャッフル情報の生成は、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させるステップと、シャッフル・ベクトルを生成するステップとを含み、前記次元削減を実行させるステップは、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、メモリに格納させるステップと、
非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列としてメモリに格納させるステップと、
前記ランダム平均行列を、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成し、格納部に格納させるステップと
を含む、請求項１に記載の方法。
【請求項３】
前記チャンクの数が、基底ベクトルの数に対応する、請求項１に記載の方法。
【請求項４】
前記平均値を算出するステップは、前記データ・ベクトルの要素を、データ・ベクトルの数(M)と基底ベクトル数(k)とから、floor(M/k)で与えられるごとに平均するステップを含む、請求項２に記載の方法。
【請求項５】
コンピュータにより数値行列を次元削減して、次元削減行列、または次元削減のためのインデックス・データとする方法を実行させるコンピュータ実行可能なプログラムであって、該プログラムは、コンピュータに対して、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成し、メモリに格納させるステップと、
前記シャッフル情報を使用して直交化された正規基底ベクトルにより前記数値行列の次元削減を実行させるステップと
を実行させる、プログラム。
【請求項６】
前記シャッフル情報の生成は、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させるステップを含み、前記次元削減を実行させるステップは、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、メモリに格納させるステップと、
非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列としてメモリに格納させるステップと、
前記ランダム平均行列を、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成し、格納部に格納させるステップと
を含む、請求項５に記載のプログラム。
【請求項７】
前記チャンクの数が、基底ベクトルの数に対応する、請求項６に記載のプログラム。
【請求項８】
前記平均値を算出するステップは、前記データ・ベクトルの要素を、データ・ベクトルの数(M)と基底ベクトル数(k)とから、floor(M/k)で与えられるごとに平均するステップを含む、請求項６に記載のプログラム。
【請求項９】
コンピュータにより数値行列を次元削減して、次元削減行列、または次元削減するためのインデックス・データとする次元削減装置であって、前記装置は、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成しメモリに読み込ませ、前記シャッフル情報を使用して、直交化された正規基底ベクトルを生成させてランダム平均行列を生成し、前記ランダム平均行列を使用して次元削減行列、または次元削減するためのインデックス・データを生成して格納させる処理部
を含む次元削減装置。
【請求項１０】
前記処理部は、前記シャッフル情報を、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させて、シャッフル・ベクトルとして生成させるシャッフル・ベクトル生成部と、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、格納する非正規基底ベクトル生成部とを含む、請求項９に記載の次元削減装置。
【請求項１１】
前記処理部は、非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列を生成するランダム平均行列生成部と、
前記ランダム平均行列を読み出して、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成して、格納する次元削減データ格納部と
を含む、請求項１０に記載の次元削減装置。
【請求項１２】
コンピュータにより情報を提供するための検索エンジンであって、前記検索エンジンは、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成し、メモリに読み込ませ、前記シャッフル情報を使用して、直交化された正規基底ベクトルを生成させてランダム平均行列を生成し、前記ランダム平均行列を使用して次元削減行列を生成して格納させる処理部と、
クエリー・ベクトルを生成して格納するクエリー・ベクトル格納部と、
前記次元削減行列と前記クエリー・ベクトルとの内積を計算する内積算出部と、
前記計算された内積のスコアを格納する検索結果格納部と、
を含む検索エンジン。
【請求項１３】
前記処理部は、前記シャッフル情報を、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させて、シャッフル・ベクトルとして生成させるシャッフル・ベクトル生成部と、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、格納する非正規基底ベクトル生成部とを含む、請求項１２に記載の検索エンジン。
【請求項１４】
前記処理部は、非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列を生成するランダム平均行列生成部と、
前記ランダム平均行列を読み出して、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成して、格納する次元削減データ格納部と
を含む、請求項１３に記載の検索エンジン。
【請求項１５】
前記データ・ベクトルは、文書をキーワードを使用して数値化した数ベクトルを含む、請求項１２に記載の検索エンジン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模データベースからの情報取得に関し、より詳細には、高い効率で、データベースに格納された文書などのデータに依存した次元削減を可能とし、かつコンピュータ・ハードウエアの省資源化を可能とするコンピュータ実行可能な次元削減方法、コンピュータをして該次元削減方法を実行させるためのプログラム、次元削減装置および該次元削減装置を使用した情報検索エンジンに関する。
【背景技術】
【０００２】
近年のめざましい計算機環境の発達と共に、インターネットやイントラネットを介する大規模データから必要とする知識情報を発見すること、いわゆる情報検索、クラスタリング、データ・マイニングといった技術の重要性がますます高まっている。大規模文書データのコーパスが与えられたとき、これに対する情報検索やクラスタリング(文書分類)を効率よく、かつ高精度に行うことを可能とする方法は、ネットワークの拡大と共に蓄積されるデータがますます増大するデータベースにおける知識検索技術において、多大な貢献を与えるものと考えられる。
【０００３】
情報検索についてまず考えると、種々のモデルが提案されており、例えば、いわゆるQuery-by-Terms方式の情報検索が想定される。また、クエリーと完全に一致する表現を含む文書を検索する場合は、全文検索型のモデルが適切となるものと考えられる（非特許文献１）。一方、情報検索でも、類似検索とか概念検索の場合には、いわゆるQuery-by-Exampleが想定されるし、同じモデルが同時にクラスタリングに適用できるのであれば、内容検索型のモデルを採用することが有効である。どのモデルについても、共通して使用することができる解析的に使用しやすいモデルとして、ベクトル空間モデルが有効である（非特許文献２）。以下、本発明において参照または使用することができる従来技術について概説する。
【０００４】
（１）ベクトル空間モデル
ベクトル空間モデル(Vector Space Model: VSM)は、文書コーパスに含まれる各文書をキーワードの集合のベクトルでモデル化する。このモデル化に際して適用されるキーワードの重み付け方法には、キーワードが含まれるかどうかを、１ビットで表現する単純なブーリアン法や、キーワードの文書内および全文書での出現頻度に基づく、TF-IDF法などが知られている（非特許文献２）。VSMでは、文書数をM、キーワード数をNとして、文書コーパスを、M×Nの数値行列である、いわゆる文書−キーワード行列として表現することができる（非特許文献３）。
【０００５】
（２）次元削減技術
より検索効率を高めるために、通常では、上述した文書コーパスのM×N行列（以下、Aとして参照する。）のうち、キーワード・ベクトルの次元をNよりも遙かに小さな次元kへと削減することが行われている、このための方法としては、Deerwesterら（非特許文献４）により提案された潜在的意味インデキシング法(Latent Semantic Indexing; LSI法)および本発明者ら（非特許文献５、非特許文献１、非特許文献６、非特許文献７、非特許文献８）などにより提案された共分散行列法(Covariance Matrix Method; COV法）を挙げることができる。
【０００６】
LSI法では、与えられた通常では矩形の行列Aを特異値分解し、特異値の大きな順からk個の特異ベクトルを選択して次元削減を実行させる。また、COV法では、行列Aから共分散行列Cを生成する。共分散行列Cは、N×Nの対称行列として与えられ、固有値分解を使用して容易に、かつ高精度に計算を行うことができる。この場合でも次元削減は、固有ベクトルの値の大きなものから順にk個を選択することにより、次元削減が行われることになる。このCOV法では、共分散行列C自体がすでにキーワード間の相関をある程度反映しているので、相関度合いの高いデータが比較的クラスターを形成させやすい、という特徴を有している。
【０００７】
また、これ以外にも、膨大な数値行列の次元削減を行う方法としては、ランダム・プロジェクション法（以下RP法として参照する。）を挙げることができる。RP法（非特許文献９、非特許文献１０）は、本来VLSIの設計や、画像のノイズ除去などの分野において使用されてきた技術であり、N×k次元のランダム行列Rをまず生成させ、行列Aに対して右から乗算させることにより次元削減を実行する。この場合、膨大な数値行列の特異値分解や、固有値分解を実行する必要がないので、次元削減計算は必然的に高速化し、かつコンピュータ・ハードウエア資源の容量も小さくすることができる。しかしながら、RP法は、データベース内に蓄積されたデータに無関係にランダム行列Rを生成させてしまうので、文書内のクラスター分布を反映できないという問題がある。すなわち、次元削減行列Aが、クラスターの大小を反映しないものとなる可能性が著しく高いことになる。
【０００８】
多くの場合、それほど高度専用化されていない検索エンジンを使用しても、主要クラスターは検索できる。加えて、主要クラスターではない存在割合が小さなデータのクラスター（以下、マイナー・クラスターとして参照する。）の方が、情報検索を行う者が興味を持つ対象とされることも多い。この点で言えば、RP法は、高速かつ省資源での計算を可能とするものの、生成された次元削減のデータは、文書データを参照しないで次元削減するため、文書内のクラスター分布情報を捨て去っており、主要クラスターもマイナー・クラスターも共に分布に応じて検出できることに対して何ら保証を与えない、という不都合があった。このため、RP法は、キーワード検索を行うには使用することができるものの、意味解析や類似検索に代表される情報検索を行う場合には、充分な情報を与えることができないという不都合があった。
【非特許文献１】北研二、津田和彦、獅子堀正幹、情報検索アルゴリズム、共立出版社、２００２年
【非特許文献２】Richard K. Below, Findings Out About, Cambridge University Press, Cambridge, UK, 2000.
【非特許文献３】G. Salton and M. Mcgill, Introduction to Modern Information Retrieval, McGraw-Hill, 1983.
【非特許文献４】Scott Deerwester, et. al., “Indexing by Latent Semantic Analysis”, Journal of the American Society for Information Science, Vol. 41, (6), 391-407, 1990.
【非特許文献５】青野雅樹、小林メイ、“ベクトル空間モデルに基づく次元削減による大規模文書データの検索と可視化”、情報処理学会、マルチメディアと分散処理研究会、2002-DPS-108, pp.79-84, June, 2002.
【非特許文献６】佐々木稔、北研二、“ランダム・プロジェクションによるベクトル空間情報検索モデルの次元削減”、自然言語処理、第８巻、第１号、pp.5-19, 2001.
【非特許文献７】Mei  Kobayashi，  Masaki  Aono，“Covariance matrix analysis for mining major and minor clusters”, 5-th International Congress on Industrial and Applied Mathematics(ICIAM), Sydney, Australia, p.188, July 2003.
【非特許文献８】K. V. Mardia, J. T. Kent and J. M. Bibby, Multivariate Analysis, Academic Press, London, 1979.
【非特許文献９】Dimitris Achilioptas, “Database-friendly Random Projections”, In Proc. ACM Symposium on the Principles of Database Systems, pp.274-281. 2001.
【非特許文献１０】Ella Bingham and Heikki Mannila, “Random projections in dimensionality reduction:Applications to image and text data”, Proc. ACM SIGKDD, pp. 245-250, San Francisco, CA, USA, 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
これまで、精度および高速性、省資源性を同時に満足することが可能な情報取得に適用する方法、次元削減装置、次元削減装置を含む検索エンジン、およびコンピュータ・プログラムが存在せず、精度および高速性、省資源性を同時に満足することが可能な情報取得を可能とさせる方法、そのための検索エンジン、およびコンピュータ・プログラムが必要とされていた。
【課題を解決するための手段】
【００１０】
本発明は、上述した従来技術の不都合に鑑みてなされたものであり、本発明は、従来技術の不都合(inconvenience)が、データベースに蓄積されたデータのサイズに依存することなく、k次元の次元削減のために使用する基底ベクトルをランダムに生成できることに着目した。そこで、本発明者らは、より大規模なデータベースに蓄積されたデータから、データ内部に潜在するクラスター分布を保持しつつデータ・ベクトルのランダム化を行うことができれば、高速かつ高効率に主要およびマイナー・クラスターの情報の検索精度を保つことができ、かつ、信頼性の高い知識取得を可能とすることができる、という着想に基づき本発明を完成させたのである。
【００１１】
より具体的には、本発明は、データベースに格納されたデータからM×Nの数値行列を作成させた後、M個のデータ・ベクトルをランダムにシャッフルさせる。その後、M個のデータについて、概ね均等な個数のベクトルからなるk個のチャンクを与える。１つのチャンクに含まれるベクトルについて、それらの要素の非正規基底ベクトルを算出し、これをチャンクの数kだけ繰り返し、k個の非正規基底ベクトルを生成させる。
【００１２】
文書数M、キーワード総数Nの文書―キーワード数値行列Aに対して、チャンク内の文書ベクトルを平均化して生成されたk個の非正規基底ベクトルは、直交化処理が行われ、k x N次元のランダム平均(Random Average: RAV)行列を与える。このランダム平均行列RAVは、次元がN x kの転置行列tRAVとして数値行列Aに対して乗算されて、キーワード次元が削減されたM x k次元の次元削減行列A’を生成する。本発明の検索エンジンは、ユーザにより入力される検索クエリーからクエリー・ベクトルを算出し、生成された次元削減行列A’との内積を算出する。内積の値は、クエリー・ベクトルと文書の間の類似度に対応するので、大きな順にソーティングされ、トップ１０、トップ１００などのランキングの値と共に検索結果として、コンピュータ装置に格納される。
【００１３】
本発明は、大規模な数値行列に対して固有値計算や特異値計算を実行させることなく、データベースに格納されたデータ・ベクトルに基づいたランダム平均行列RAVを生成することができる。このため、計算速度および処理装置の能力、メモリ容量などを含む計算効率を、著しく改善することができる。加えて、ランダム平均行列RAVは、データベースに格納された文書といったデータに基づいて計算されるので、データベース内の文書の自動分類や、類似検索およびクラスタリングなどの計算にも適用することが可能となる。
【００１４】
すなわち、コンピュータにより数値行列を次元削減して、情報を提供するための次元削減方法であって、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成し、メモリに格納させるステップと、
前記シャッフル情報を使用して直交化された基底ベクトルにより前記数値行列の次元削減を実行させるステップと
を含む次元削減方法が提供される。
【００１５】
本発明の前記シャッフル情報の生成は、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させるステップと、シャッフル・ベクトルを生成するステップとを含み、前記次元削減を実行させるステップは、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、メモリに格納させるステップと、
非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列としてメモリに格納させるステップと、
前記ランダム平均行列を、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成し、格納部に格納させるステップとを含むことができる。本発明では、前記チャンクの数が、基底ベクトルの数に対応することができる。本発明では、前記平均値を算出するステップは、前記データ・ベクトルの要素を、データ・ベクトルの数(M)と基底ベクトル数(k)とから、floor(M/k)で与えられるごとに平均するステップを含むことができる。
【００１６】
本発明によれば、コンピュータにより数値行列を次元削減して、次元削減行列、または次元削減のためのインデックス・データとする方法を実行させるコンピュータ実行可能なプログラムであって、該プログラムは、コンピュータに対して、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成し、メモリに格納させるステップと、
前記シャッフル情報を使用して直交化された正規基底ベクトルにより前記数値行列の次元削減を実行させるステップと
を実行させる、プログラムが提供される。
【００１７】
本発明によれば、コンピュータにより数値行列を次元削減して、次元削減行列、または次元削減するためのインデックス・データとする次元削減装置であって、前記装置は、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成しメモリに読み込ませ、前記シャッフル情報を使用して、直交化された正規基底ベクトルを生成させてランダム平均行列を生成し、前記ランダム平均行列を使用して次元削減行列、または次元削減するためのインデックス・データを生成して格納させる処理部
を含む次元削減装置が提供される。
【００１８】
本発明の次元削減装置の前記処理部は、前記シャッフル情報を、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させて、シャッフル・ベクトルとして生成させるシャッフル・ベクトル生成部と、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、格納する非正規基底ベクトル生成部とを含むことができる。
【００１９】
本発明の前記処理部は、非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列を生成するランダム平均行列生成部と、
前記ランダム平均行列を読み出して、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成して、格納する次元削減データ格納部と
を含むことができる。
【００２０】
本発明によれば、コンピュータにより情報を提供するための検索エンジンであって、前記検索エンジンは、
データベースに格納されたデータ・ベクトルをランダムに選択してシャッフル情報を生成し、メモリに読み込ませ、前記シャッフル情報を使用して、直交化された正規基底ベクトルを生成させてランダム平均行列を生成し、前記ランダム平均行列を使用して次元削減行列を生成して格納させる処理部と、
クエリー・ベクトルを生成して格納するクエリー・ベクトル格納部と、
前記次元削減行列と前記クエリー・ベクトルとの内積を計算する内積算出部と、
前記計算された内積のスコアを格納する検索結果格納部と、
を含む検索エンジンが提供できる。
【００２１】
本発明における前記処理部は、前記シャッフル情報を、ランダムに選択された前記データ・ベクトルの識別値をメモリに選択された順に格納させて、シャッフル・ベクトルとして生成させるシャッフル・ベクトル生成部と、前記シャッフル・ベクトルにより指定された前記データ・ベクトルの数値要素をデータベースから読み出して、割り当てられたチャンクごとに平均値を算出して非正規基底ベクトルを生成し、格納する非正規基底ベクトル生成部とを含むことができる。
【００２２】
本発明においては、前記処理部は、非正規基底ベクトルを直交化させて正規基底ベクトルを生成させ、ランダム平均行列を生成するランダム平均行列生成部と、
前記ランダム平均行列を読み出して、前記データ・ベクトルに乗算して次元削減された次元削減行列、または次元削減するためのインデックス・データを生成して、格納する次元削減データ格納部と
を含むことができる。
【００２３】
本発明の好ましい実施の形態では、前記データ・ベクトルは、文書をキーワードを使用して数値化した数ベクトルを含むことができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明を図面に示した具体的な実施の形態をもって説明するが、本発明は、図面に示した実施の形態に限定されるものではない。図１には、本発明においてデータベース内に格納された文書から文書−キーワード行列を生成する際の処理を概略的に示した図である。図１（ａ）が、文書データベースの構成を示し、図１（ｂ）が文書−キーワード行列である。図１に示されるように、データベースの例えば文書データ“DOC”は、文書整理番号や、データベースに固有の識別値を伴っており、識別値により適切に呼出を行うことができる構成とされている。また、図１（ａ）に示された文書データは、通常では、見出し語や、タイトルが付されており、これらのキーワードがキーワード・リストを参照して、上述したVSM法や、TF-IDF法により数値化される。
【００２５】
この結果、図１（ｂ）に示されるように、文書データに対しては、例えばそのタイトル、見出し語などが数値化された要素からなる数ベクトルが生成される。以下、このベクトルをデータ・ベクトルとして参照する。なお、本発明は、文書データだけではなく、テキストを含むいかなるデータに対しても適用することができる。このデータ・ベクトルは、例えばデータベースの適切な領域に、または別に構成されたデータベースに格納され、文書−キーワード行列として格納されている。図１に示された文書−キーワード行列は、データ・ベクトル数は、文書データと同数のMであり、キーワード数はNとされている。
【００２６】
図１（ａ）に示されるように、データ・ベクトルにも、対応する文書データと同一のまたは参照可能に関連づけられた識別値“Id”が付されている。図１（ｂ）に示した文書−キーワード行列にも、説明している実施の形態では、同一の識別値が付されている。この識別値は、多くの場合、ニュース記事や、論説などでは、当該文書データがデータベースに登録された時系列順または発生した時系列順に識別値“Id”が付されることが多い。このため、識別値とデータ・ベクトルに含まれるキーワードとの間には、例えば地震、天候などの場合のように所定の地域や日時のデータ・ベクトルが文書−キーワード行列の列方向の特定領域に集中している可能性もある。
【００２７】
本発明においては、このような場合、特定の基底ベクトルがデータの格納履歴や発生履歴に依存することになる。そこで、本発明においては、図１に示される文書−キーワード行列を構成するデータ・ベクトルを、列方向に対してランダムにシャッフル(shuffle)させ、シャッフル情報を作成し、データベースやメモリといった記憶手段に格納させ、後の処理において参照させる。シャッフルされた情報を使用することによりデータベース内における履歴が基底ベクトルの算出に影響を与えないようにすると共に、各基底ベクトルに潜在的に含まれる主要クラスター、メディアム・クラスター、マイナー・クラスターの分布を概ね均等に配分させることが可能となる。すなわち、クラスターの分布に忠実な次元削減手法を与えることが可能となる。
【００２８】
図２には、本発明においてデータ・ベクトルをランダムにシャッフルする方法の好適な実施の形態を概略的に示す。本発明においては、データ・ベクトルをランダムにシャッフルさせる手法は、データ・ベクトルをランダムに並べ替えて、行列を陽に生成させて使用することもできるし、文書の識別値や、データベースにおけるデータ識別値などをランダムに配列したシャッフル・ベクトルとして生成することもできる。本発明においては、シャッフル情報とは、データ・ベクトルをランダムに並べ替えた行列データまたはデータ・ベクトルをランダムに並べ替え、さらにデータ・ベクトルを参照させるためにのみ使用する情報を意味する。本発明においては、シャッフル情報として、文書−キーワード行列のM×Nの要素を含むシャッフル情報を使用する方法を排除するわけではないものの、本発明のより好適な実施の形態では、ハードウエア資源の省力化および計算効率を考慮して、図２に示すようにデータ・ベクトルの数Mに対応したメモリ・アドレスを確保するだけで生成させることができるシャッフル・ベクトルを使用することが望ましい。シャッフルの方法は、種々の方法を使用することができるが、例えばM個の１次元配列Bを用意して、データ・ベクトルの識別値“Id”を整数1,…,Mに対応させてB[i]=i (1 <= i <= M)で初期化する。そして、区間[1,M]からランダムに1個の整数を選択して、これをSとしたとき、B[M]とB[S]を交換する。次に、区間[1,M-1]からランダムに１個の整数を選択して、これをまたSとし、B[M-1]とB[S]を交換する。このように区間を狭めながらB[1]まで同様の処理を繰り返すことで、ランダムな整数配列Bが得られる。これをシャッフル・ベクトルとして利用することができる。
【００２９】
計算処理において、シャッフル・ベクトルを参照する場合には、シャッフル・ベクトルを先頭または最後尾から順に読み出し、該当するデータ・ベクトルを参照して、その要素に対して後述する平均化処理を実行させることができる。また、本発明においては、シャッフル・ベクトルの要素には、概ね所定数ごとのチャンクが設定されており、シャッフル・ベクトルの参照は、チャンクに割り当てられたデータ・ベクトルの数ごとに行われる。このチャンク数は、本発明において基底ベクトルの数kに対応する。
【００３０】
図３には、本発明のランダム平均行列RAVを生成するための本質的な処理の好適な実施の経緯のフローチャートを示す。
【００３１】
図３に示されるように、本発明のランダム平均行列の生成方法は、ステップＳ１０において、文書−キーワード行列にアクセスして、ランダムにデータ・ベクトルの識別値などを取得する。ステップＳ１２において、読み出された識別値を、RAMといった適切な記憶装置により形成されたメモリに格納させてゆき、シャッフル・ベクトルとして保持させる。ステップＳ１４では、シャッフル・ベクトルのデータ数Mに対して、例えばfloor(M/k)でチャンクを定義して、所望する基底ベクトルの数のチャンクへと割り当てる。この場合、各チャンクの数は、概ね等しくなるようにすることが、各基底ベクトルの重みを均等化させる点では好ましいものの、本発明においては、各チャンクに含まれるデータの数およびチャンクごとの数の一致性には、特に制限はない。
【００３２】
ステップＳ１６では、チャンクごとに、データ・ベクトルの要素を読み出し、適切なメモリにおいて積算して、平均値を算出する。この処理をキーワード数N分繰り返し実行させ、チャンクごとに非正規基底ベクトル(non-normalized basis vector) di (1 <= i <= k)を算出させ、メモリに格納する。ステップＳ１８では、格納された非正規基底ベクトルdiを読み出して、直交化処理を実行させ、基底ベクトルb1,…,bkを算出して、適切なメモリに格納させる。
【００３３】
さらにステップＳ２０では、計算された基底ベクトルbiを読み出して、適切なメモリに順に配置させて、k x N 次元のランダム平均行列RAVとして格納させる。RAVは、このようにデータ・ベクトルをチャンクごとに参照し平均化するというプロセスを施しているため、統計的に見れば、主要クラスターからマイナー・クラスターの比率が得られる基底ベクトルの中に概ね元の文書−キーワード行列に含まれる比率と同等の割合で反映されることになる。
【００３４】
このため、本発明において次元削減した場合、主要クラスターからマイナー・クラスターまでの検出性は、著しく低下することがない。また、ステップＳ１８の直交化処理は、例えば、モディファイド・グラム・シュミット(MGS)法を使用して逐次的に直交化することができる。
【００３５】
図４には、図３に説明した処理を、より具体的にベクトル要素についての演算処理を用いて示した図である。図４において、floor(M/k)は、所定のチャンクに含まれるベクトルの数であり、“floor()”は、括弧内の値の小数点以下を切り捨てる演算子を表す。sij (1 <= i <= k, 1 <= j <= N)は、所定のチャンク内に含まれるベクトルのj番目の要素の総和を表す。図４に示すブロックＢ２０では、データ行列を読み込み、乱数発生手段を使用して、シャッフル・ベクトルを生成させ、そのシーケンスにより指定されるデータ・ベクトルをπ(p) ( 1 <= p <= M)として表現している。
【００３６】
ブロックＢ２２では、与えられたシャッフル・ベクトルに対して、floor(M/k)個ごとにチャンクを割り当て、データ・ベクトルのj番目の要素の平均を算出させる。図４のブロックＢ２２に示されたａπ(p),jは、π(p)番目のデータ・ベクトルのj番目の要素を示す。ブロックＢ２２で要素の平均が完了した時点で、非正規基底ベクトルが生成される。この非正規基底ベクトルdiは、適切なメモリに格納される。
【００３７】
ブロックＢ２４におけるMGS法では、特定の実施の形態において最初の時点で少なくとも３つの非正規基底ベクトルが蓄積されるまで算出された非正規基底ベクトルの数をカウントする。ブロックＢ２４では、所定数の非正規基底ベクトルが蓄積した時点で、MGS法を適用して非正規基底ベクトルdiを直交化させ、正規基底ベクトル (normalized basis vector)を算出して、メモリに格納させる。その後、ブロックＢ２６では、i=i+floor(M/k)として、処理チャンクをインクリメントさせ、ブロックＢ２２での非正規基底ベクトルの計算およびブロックＢ２４での逐次的な直交化を再度実行させ、最終的にすべてのチャンクに対応するk個の正規基底ベクトルを生成した時点で処理を終了させる。
【００３８】
なお、チャンク数kは、データ数に応じてシステムが適切に自動設定することもできるし、ユーザが基底ベクトルの数をシステムに対して入力させることで設定することもでき、ユーザの希望または装置の環境に応じて適宜選択することができる。
【００３９】
図５には、本発明において生成される基底ベクトルにおける主要クラスターとマイナー・クラスターの貢献度、およびRP法により与えられる基底ベクトルにおける主要クラスターおよびマイナー・クラスターの貢献度を概略的に示した図である。図５（ａ）が、本発明のRAV法により生成される基底ベクトルにおける貢献度を示し、図５（ｂ）が、RP法により生成される基底ベクトルの貢献度を示す。図５（ａ）に示されるように、本発明の基底ベクトルは、概ね統計的に、元のデータ・ベクトル中に潜在的に含まれる割合とほぼ同等な割合で主要クラスターからマイナー・クラスターまでの要素が含まれることがわかる。
【００４０】
一方で、本発明のRAV法では、主要クラスターからマイナー・クラスターまでのデータを漏れなく基底ベクトルの決定時に使用している。このため、どの基底ベクトルにおいても各クラスターの要素が、統計的に含まれていることが保証されるので、高速な次元削減にもかかわらず、データ・マイニングや類似検索などに適用することが可能な次元削減行列、あるいは次元削減のためのインデックス・データを与えることができる。本発明において、インデックス・データとは、次元削減に必要とされるデータ・ベクトルおよび対応するRAVを処理において適切に呼び出すための複数の識別値セットを意味し、インデックス・データを使用して内積計算処理が呼出された場合に、オンザフライで、次元削減されたデータ・ベクトルを生成するためのデータを意味する。
【００４１】
一方、図５（ｂ）に示したRP法の場合には、基底ベクトルは、本質的にデータ・ベクトルに依存せずに生成され、特に現実的な実装時には、マイナー・クラスターが誇張されて主要クラスターが埋没してしまうデータ・ベクトルや、逆に主要クラスター情報しか含まれないようなデータ・ベクトルを生成する可能性がある。このため、キーワード検索での精度は低く、実用的なデータ・マイニングや類似検索などの分野への適用ができない。
【００４２】
図６は、本発明の検索データ構造を使用する検索エンジンの実行する処理を示したフローチャートである。本発明の検索エンジンは、ステップＳ３０において、検索クエリーを受信し、適切なバッファ・メモリに格納させる。検索クエリーの入力は、ユーザがキーボードから直接入力することもできるし、本発明の別の態様においては、ネットワークを経由して送信される検索クエリー・データを含むHTTPリクエストに代表されるウェブサービス・プロトコル・リクエストとすることができる。その後ステップＳ３２では、入力された検索クエリーを、検索エンジンに格納したキーワード・リストを使用して数値化処理して、バッファ・メモリといった適切なメモリに格納する。
【００４３】
ステップＳ３４では、本発明のRAV法により生成される次元削減行列に含まれる次元削減されたデータ・ベクトルまたはインデックス・データとして参照される次元削減データをバッファ・メモリに読み出して、検索クエリーとの内積を計算させる。ステップＳ３６では、生成されたスコアを、適切なメモリに作成したハッシュ・テーブルにデータ・ベクトルの識別値と対応させて格納させる。ステップＳ３８では、スコアの大きな順に結果をソーティングして、検索結果として例えば、ディスプレイ・スクリーン上に表示させる。このとき表示のさせ方としては、種々の方法を使用することができ、例えばグラフィカル・ユーザ・インタフェースを使用してグラフィカルに表示させることもできるし、検索されたデータ・ベクトルを、識別値を使用してハイパーリンクさせた、ハイパー・テキスト・マークアップ・ランゲージ(HTML)や拡張マークアップ・ランゲージ(XML)などとしてスクリーン表示させることもできる。
【００４４】
図７は、本発明のRAV法を使用した検索エンジンの概略的な構成を示した図である。図７に示した検索エンジン１０は、概ねコンピュータ装置１２と、コンピュータ装置１２により管理されたデータベース１４と、コンピュータ装置１２に対して入出力を可能とする入出力装置１６と、表示スクリーンを含んだ表示装置１８とを含んで構成されている。検索エンジン１０は、ユーザからの検索クエリーを受け取ると、検索エンジン１０の適切な記憶領域に格納された次元削減行列からデータ・ベクトルを読み出すかまたは次元削減のためのインデックス・データを読み出して検索を実行させ、その結果を、表示スクリーンに数値データまたはグラフィカル・ユーザ・インタフェースを使用して表示させる。本発明においては、検索エンジン１０は、cgiシステムまたはウェブ・ソフトウエアとして構成させることもでき、この場合には、検索クエリーは、ネットワーク２６を介して遠隔的に配置されたユーザ・コンピュータから送信されることができる。
【００４５】
図８には、本発明の検索エンジンにおいて使用することができるコンピュータ装置１２のハードウエア構成を示した図である。コンピュータ装置１２には、概ねメモリ２０と、中央処理装置（CPU)２２と、入出力制御装置２４と、ネットワークを介して検索サービスを提供する場合には、ネットワーク２６からの検索要求を処理するための外部通信装置２８とを含んで構成されている。メモリ２０、中央処理装置２２、入出力制御装置２４、外部通信装置２８は、それぞれ内部バス３０を介して相互接続されていて、データの伝送を行うことが可能とされている。また、コンピュータ装置１２は、スタンドアローンのシステムとして実装することもできるし、本発明の別の実施の形態では、コンピュータ１２を、インターネットといったネットワーク２６に接続して、検索サービスを提供するサーバとして構成させることもできる。
【００４６】
コンピュータ装置１２が、スタンドアローンの検索エンジンとして使用される場合には、ユーザは、キーボードや、マウスといった入出力装置１６を使用して、所定のグラフィカル・ユーザ・インタフェース（GUI)を使用して検索クエリーの入力を行う。検索クエリーを受け取ると、コンピュータ装置１２は、検索クエリーからクエリー・ベクトルを生成して、次元削減行列のデータ・ベクトルとの内積を計算させることにより、検索を実行させる。
【００４７】
また、コンピュータ装置１２がサーバとして提供される場合には、コンピュータ１２は、ネットワーク２６を介して検索を要求するHTTPリクエストを受け取り、外部通信装置２８などのバッファ・メモリに一旦格納させる。その後、検索のためのアプリケーションを起動または呼出し、続いてユーザから送信される検索クエリーから、クエリー・ベクトルを生成させる。さらにクエリー・ベクトルを使用して、図６に示した処理を実行させて、検索結果を生成させ、メモリ２０に格納する。格納された検索結果は、外部通信装置２８を介してネットワークへとHTTPレスポンスとしてユーザに返される。
【００４８】
図９は、本発明において、RAV法を実行するためにコンピュータ装置１２にソフトウエア的またはハードウエア的に構成される機能ブロックおよびコンピュータ装置１２が外部制御を行う機能ブロックを示した図である。図９に示されるように、コンピュータ装置１２には、RAV処理部３２と、ランダム平均行列格納部３４と、次元削減データ格納部３６と、内積算出部３８と、クエリー・ベクトル格納部４０と、検索結果格納部４２とが機能的に構成または接続されている。
【００４９】
RAV処理部３２の機能を説明すると、RAV処理部３２は、図示しないデータベースのデータに関連したシャッフル情報として、シャッフル・ベクトルを生成させ、本発明に従い基底ベクトルを算出させている。算出された基底ベクトルは、ランダム平均行列格納部３４へと送られて、ランダム平均行列RAVの所定のフォーマットで格納されている。さらに、ランダム平均行列RAVと、文書−キーワード行列を乗算させて、次元削減行列ARAVが算出される。このARAV行列は、検索クエリーが直接内積計算される対象とするべく、例えばハードディスクといった記憶装置として構成されて次元削減データ格納部３６に格納される。
【００５０】
また、本発明においては、次元削減行列ARAVを陽に作成しておくのではなく、インデックス・データとして文書−キーワード行列の識別値と基底ベクトルに対応するランダム平均行列RAVの所定の列ベクトル識別値とをペアとしたデータとして、次元削減データとして次元削減データ格納部３６に格納させておくこともできる。一方で、クエリー・ベクトル格納部４０に格納されたクエリー・ベクトルおよび次元削減データ格納部３６から次元削減されたデータ・ベクトルまたはインデックス・データは、それぞれ内積算出部３８へと読み出されて内積計算が実行され、計算された内積スコアは、検索結果格納部４２へと格納される。なお、インデックス・データを使用する場合には、内積算出部３８は、インデックス・データから直接次元削減されたデータ・ベクトルをオンザフライで作成させ、内積計算に使用することができる。また、本発明においては、図９において、内積算出部３８の入力側であって、次元削減データ格納部の下流側に相当する機能的部位に、次元削減ベクトル生成部を設けておき、生成された次元削減ベクトルを内積算出部３８の入力とすることができる。
【００５１】
また図９には、本発明のRAV処理部３２が含む機能ブロックも同時に示されている。図９に示されるように、RAV処理部３２は、シャッフル・ベクトル生成部４４と、非正規基底ベクトル生成部４６と、直交化処理部４８とを含んで構成されている。シャッフル・ベクトル生成部４４は、データベース１４からデータ・ベクトルまたはデータ・ベクトルの識別値を読み出して、データ・ベクトルをランダムに配列するためのシャッフル情報であるシャッフル・ベクトルを生成し、バッファ・メモリなどの適切なメモリに格納させる。非正規基底ベクトル生成部４６は、シャッフル・ベクトルを参照してチャンクごとにデータ・ベクトルの各数値要素を平均させることにより、非正規基底ベクトルを算出させ、算出された非正規基底ベクトルをメモリに格納させている。直交処理部４８は、メモリに格納された非正規基底ベクトルを読み出して、本発明の特定の実施の形態ではMGS法を使用して直交化処理を実行させ、生成された正規基底ベクトルb1,…,bkを、ランダム平均行列格納部３４へと適切な形式の行列（配列データ）として格納させている。
【００５２】
その後、上述したように次元削減行列を算出させ、クエリー・ベクトルとの内積を計算させ検索結果を格納させ、ユーザへと適切な形式で検索結果を表示させる。
【００５３】
本発明の上述した機能ブロックは、コンピュータが実行可能なプログラムをコンピュータ装置に読み取らせ、実行させることによりソフトウェア・ブロックとして構成することができる。コンピュータが実行可能なプログラムは、種々のプログラミング言語を使用して記述することができ、例えばC言語、C++言語、FORTRAN、JAVA（登録商標）を使用して記述することができる。
【実施例】
【００５４】
以下、本発明について具体的に実施例をもってより詳細に説明する。
（実験例１）
従来法との比較検討
（１）実験に使用したデータベース
実験に使用したデータベースは、データサイズが、332,918文書、で、キーワードを、56,300とし、次元削減は、300次元まで行った。
【００５５】
（２）実験に使用したハードウエア環境
コンピュータ装置としては、CPUをPentinum4、1.7GHZ、オペレーティング・システムをWindows（登録商標）XPとした、IntelliStation（IBM社製）を使用した。
【００５６】
（３）計算時間
上述した条件の下でRAV法およびCOV法の計算時間を比較した。その結果を表１に示す。
【００５７】
【表１】
2005050197.tif 000003
表１に示されるように、本発明のRAV法は、COV法の約３０倍程度高速化されていることが示された。また、計算時間のスケーラビリティについては、RAV法については、Mに比例するのみであったが、COV法では、概ねキーワード数(N)の３乗に比例した計算時間が必要であった。すなわち、RAV法は、従来の次元削減法に比較して、計算時間に対するスケーラビリティに優れると言う結果が得られた。
【００５８】
（４）精度
本発明のRAV法の精度を、検索された文書のうちトップ10、トップ20のドキュメントがdf=49、29のごく少ないクエリー・キーワードを含むか否かの尺度を使用して検討した。その結果、df=49のキーワードに対してはトップ10では、100%、トップ20では、75%以上の精度（precision値）が得られた。なお、精度（precision値）および後述する再現度（recall値）は、下記式（１）により与えられる。
【００５９】
【数１】
2005050197.tif 000004
（実験例２）
【００６０】
（１）RAV法とRP法の比較検討
同一のクエリーについて、Text Research Collection Volume 5, April 1997, http://trec.nist.gov/に規定される手法を使用し、再現度-精度曲線（recall−precision curve）を本発明のRAV法およびRP法により計算させた。この際、RP法における次元削減行列Rは、下記式（２）により与えた。
【００６１】
【数２】
2005050197.tif 000005
【００６２】
（２）結果
RAV法と、RP法について得られた代表的な結果を図１０に示す。図１０に示されるように、本発明のRAV法は、RP法による値よりも概ね高い精度（precision値）を与えていることが示される。また計算時間の点に関して言えば、RP法の方が僅かに速いと言う結果が得られたものの、本発明のRAV法においても５〜１０分程度の時間で計算が終了し、充分な高速性が保たれていた。これは、基底ベクトルの直交化処理を行う処理が本発明では含まれるためであると考えられる。
【００６３】
（実験例３）
コンピュータ資源消費性
同一の条件下で計算機実験を行い、ランタイムでのメモリ消費量を比較した。下記表１に、それぞれの方法と、メモリ消費量との実測データを示す。
【００６４】
【表２】
2005050197.tif 000006
表２に示されるように、本発明の方法は、大規模な特異値分解または固有値分解を実行させないので、コンピュータ装置に実装される記憶空間を著しく低下させることができる。また、RP法と比較しても、ランタイムにおける記憶空間の必要量が低減されており、良好な結果が得られた。
（実験例４）
【００６５】
マイナー・クラスター検出性
（１）実験内容
本発明のRAV法と、RP法とを、マイナー・クラスターの検出性の観点から比較するための実験を、実験例２と同様のデータベースおよび条件を使用して行った。次元削減処理は、300次元とし、検索クエリーは、マイナー・クラスターに含まれることが確認されているquery1=<Michael Jordan, basketball>およびquery2=<McEnroe, tennis>を使用し、上位のドキュメントのうち検索クエリーquery1、query2を含むものの存在割合を、RAV法およびRP法について比較した。
【００６６】
（２）実験結果
得られた実験結果を下記表３に示す。
【００６７】
【表３】
2005050197.tif 000007
上記表３にも示されるように、RAV法は、RP法に比較してもマイナー・クラスターを高い精度で良好に検出することができることが示された。
【００６８】
上述したように、本発明によれば、高い効率で、かつコンピュータ資源の浪費を防止すると共に、主要クラスターから、マイナー・クラスターまで安定した検出精度を示す情報取得を可能とする。
【図面の簡単な説明】
【００６９】
【図１】本発明において、データベース内に格納された文書から文書−キーワード行列を生成する際の処理を概略的に示した図。
【図２】本発明においてデータ・ベクトルをランダムにシャッフルする方法を概略的に示した図。
【図３】本発明のランダム平均行列を生成するための本質的な処理の好適な実施の形態のフローチャートを示した図。
【図４】図３に説明した処理を、より具体的にベクトル要素についての演算処理を用いて示した図。
【図５】本発明において生成される基底ベクトルにおける主要クラスターとマイナー・クラスターの貢献度、およびRP法により与えられる基底ベクトルにおける主要クラスターおよびマイナー・クラスターの貢献度を概略的に示した図。
【図６】本発明の検索データ構造を使用する検索エンジンの実行する処理を示したフローチャート。
【図７】本発明のRAV法を使用した検索エンジンの概略的な構成を示した図。
【図８】本発明の検索エンジンにおいて使用することができるコンピュータ装置のハードウエア構成を示した図。
【図９】RAV法を実行するためにコンピュータ装置１２にソフトウエア的またはハードウエア的に構成される機能ブロックおよびコンピュータ装置１２が外部制御を行う機能ブロックを示した図。
【図１０】RAV法と、RP法について得られた代表的な結果を示した図。
【符号の説明】
【００７０】
１０…検索エンジン、１２…コンピュータ装置、１４…データベース、１６…入出力装置、１８…表示装置、２０…メモリ、２２…中央処理装置、２４…入出力制御装置、２６…ネットワーク、２８…外部通信装置、３２…RAV処理部、３４…ランダム平均行列格納部、３６…次元削減データ格納部、３８…内積算出部、４０…クエリー・ベクトル格納部、４２…検索結果格納部、４４…シャッフル・ベクトル生成部、４６…非正規基底ベクトル生成部、４８…直交処理部
【図１】
2005050197.tif 000008
【図２】
2005050197.tif 000009
【図３】
2005050197.tif 000010
【図４】
2005050197.tif 000011
【図５】
2005050197.tif 000012
【図６】
2005050197.tif 000013
【図７】
2005050197.tif 000014
【図８】
2005050197.tif 000015
【図９】
2005050197.tif 000016
【図１０】
2005050197.tif 000017