分散潜在的意味インデキシングを使った情報検索およびテキストマイニングのための、方法、および、システム
情報検索およびテキストマイニング操作のための潜在的意味インデキシング（ＬＳＩ）の使用が、大規模な異種のものからなるデータ集合を、まず、データ集合を、類似の概念ドメインを持ついくつかのより小さい区分に区分化することによって処理するように適合される。その次に、問い合わせベクトルを拡張する際のみならず、どのドメインに問い合わせるか決定する際にも利用される、概念ドメイン間のリンクを顕在化させるために類似性グラフネットワークが生成される。ユーザ問い合わせまたはテキストマイニング操作に関連する情報を含む可能性が最も高い区分化されたデータ集合に対してＬＳＩが実行される。このようにして、ＬＳＩが、これまで拡張可能性の問題を提示したデータ集合に適用される。さらに、用語×文書行列の特異値分解の計算が、様々な分散コンピュータにおいて達成され、検索およびテキストマイニングシステムの頑強性が向上すると同時に、サーチ時間が短縮される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散アーキテクチャを使った概念に基づく情報の検索およびマイニングの方法、および、システムに関する。
【０００２】
より詳細には、本発明は、異種のものからなるデータオブジェクトのコレクションを、そこに見出される概念ドメインに関して区分化し、潜在的意味インデキシング（ＬＳＩ）を用いて区分化された各下位コレクションの内容に索引付けし、それによってこれらの分散ＬＳＩベクトル空間全体にわたって問い合わせを行うことを可能にする。これらのデータオブジェクトの下位コレクションのベクトル空間表現は、ユーザ問い合わせまたはマイニング操作に応答するのに必要とされる適当な情報源を選択するのに使用される。
【背景技術】
【０００３】
潜在的意味インデキシング（ＬＳＩ）は、用語間の依存関係または「意味類似性」を利用するベクトル検索方法の変形である高度な情報検索（ＩＲ）技術である。文書などのデータオブジェクト全体にわたる単語の用法のパターンには、何らかの基礎をなす、または「潜在的」な構造が存在し、この構造は統計的に発見されることが想定される。この手法の１つの大きな利点は、ある文書コレクションについて適当な縮小されたベクトル空間が計算されると、問い合わせは、その問い合わせと文書がマッチする用語を持たない場合でさえも、意味または概念において類似する文書を検索することができる。
【０００４】
１つのＬＳＩの情報検索手法は、各エントリが、ある用語がある文書中に出現する回数を与える、あるコレクションの用語／文書行列に特異値分解（ＳＶＤ）を適用するものであり、同一出願人により詳述されている（特許文献１参照）。大きな用語／文書行列は、通常、元の行列が１次結合によってそこから近似される、おおよそ１５０から３００の直交因子の集合に分解される。ＬＳＩで生成されるベクトル空間において、用語および文書は、これらの直交次元のそれぞれにおける連続値によって表され、したがって、用語および文書には、同じ空間において数値表現が与えられる。数学的には、用語をその行とし、文書をその列とするｎ×ｍ疎行列Ｅを一緒に形成する、ｎ個の一意の用語を持つｍ個の文書のコレクションを想定すると、Ｅ中の各エントリは、ある用語がある文書に出現する回数を与える。通常の場合、ＳＶＤを適用する前に、これらの未処理の度数カウントに対数／エントロピ重み付け（ｌｏｇ（ｔｆ＋ｌ）ｅｎｔｒｏｐｙ）が適用される。文書／文書および用語／用語の依存関係に帰属する構造は、数学的には、以下の式（１）で、ＥのＳＶＤとして表される。
Ｅ＝Ｕ（Ｅ）Σ（Ｅ）Ｖ（Ｅ）Ｔ （１）
【０００５】
式中、Ｕ（Ｅ）はＵ（Ｅ）ＴＵ（Ｅ）＝Ｉｎであるようなｎ×ｎ行列であり、Σ（Ｅ）は特異値のｎ×ｎ対角行列であり、Ｖ（Ｅ）はＶ（Ｅ）ＴＶ（Ｅ）＝Ｉｍであるようなｎ×ｍ行列であり、簡単にするために、Ｅは文書より少ない用語を持つものと想定する。
【０００６】
当然ながら、ＳＶＤの魅力は、それが、Ｅを、式（２）のランクｋの再構築で示されるより低次元のベクトル空間ｋに分解するのに使用されることである。
Ｅｋ＝Ｕｋ（Ｅ）Σｋ（Ｅ）Ｖｋ（Ｅ）Ｔ （２）
【０００７】
因子の数は、この空間を構築するのに使用される一意の用語の数よりはるかに小さくなり得るため、単語は独立でなくなる。意味の類似する単語、および、それらが含む単語に基づいて、類似の内容を持つ文書は、ＬＳＩ空間において互いの近くに位置することになる。これらの依存関係は、用語を用いて文書に問い合わせするだけでなく、文書を用いて用語に問い合わせし、用語を用いて用語に問い合わせし、他の文書を用いて文書に問い合わせすることも可能にする。実際、ＬＳＩ手法は、単に、問い合わせを、「擬似文書」、あるいはそれが含む単語に基づく加重ベクトル和として扱うにすぎない。ＬＳＩ空間において、用語または文書のベクトル間のコサインまたは内積は、それらの推定される類似性に対応し、この類似性の尺度は、文書に問い合わせし、それをフィルタにかけために興味深いやり方で利用される。この問い合わせベクトルｑと文書ベクトルｄの間の対応の尺度は式（３）によって与えられる。
ｓｉｍ（Ｕｋ（Ｅ）Ｔｑ，Ｕｋ（Ｅ）Ｔｄ） （３）
【０００８】
左特異ベクトルの行列Ｕｋ（Ｅ）をベクトル辞書として使用することの正式な正当化の根拠は提供されている（例えば、非特許文献１参照）。
【０００９】
ＬＳＩが普及した結果として、大量の異種のものからなる文書コレクションに問い合わせしようとするときにＬＳＩによって示される、いくつかの問題が識別されている。ＳＶＤは、極端に大きい用語×文書行列では計算するのが難しく、コレクションが非常に大きくなると適合率／再現率性能が低下する傾向にある。驚くべきことに、ＬＳＩを取り巻く技術的考察の多くは、これらを実施する線形代数方法およびアルゴリズム、特に、ＳＶＤを大量の、用語／文書疎行列に適用する問題に集中している。様々な用語重み付けやＳＶＤによって抽出される因子の数などのパラメータを変更することの、ＬＳＩの性能に対する影響の評価が行われている。ＬＳＩをより適切にスケーリングさせる手法の大部分は、ＬＳＩの索引付けおよびサーチアルゴリズムの複雑さを増大させることから見出されようとしている。
【００１０】
ＬＳＩは、文書コレクションが増大すると、情報検索およびテキストマイニング戦略として制限される。というのは、大規模なコレクションを用いれば、文書を異なる概念ドメインから引き出す確率がますます大きくなるからである。これは、単一のＬＳＩベクトル空間でモデル化される意味不均質性を増大させ、ゆえに、ノイズを導入し、ＬＳＩサーチアルゴリズムを「混乱させる」影響を及ぼす。あるコレクションにおいて多義性がより顕著になるにつれて、用語のベクトルは、その用語の一意の各意味ごとのすべてのベクトルの重心によって表される傾向があり、文書ベクトルは、文書が含む用語のベクトルの加重和から計算されるため、これらのセマンティクスもまた混乱する。
【００１１】
一般に、概念ドメインの数は、文書コレクションのサイズと共に増大する。これは、情報空間に新しい概念が導入されること、あるいは、既存の概念が、その下位概念のさらなる差異化に伴って（文書数が）極端に大きくなることから生じ得る。どちらの場合にも、任意のベクトル空間ベースの方法における圧縮係数が、この膨張に適応するように増大される必要がある。
【００１２】
大規模な概念的に差異化されていない文書コレクションに及ぼす訓練の有害な影響はおびただしいものがある。例えば、技術および食品という２つの概念ドメインから引き出された文書が、出典を明らかにせずに、単一の訓練集合に結合され、単一のベクトル空間を作成するためにこの集合にＬＳＩが適用されると想定する。これら２つのドメインのセマンティクスがいかに混乱し得るかは容易に想像される。「ｃｈｉｐ（チップ）」および「ｗａｆｅｒ（ウェーハ）」という用語を表すベクトルの場所を例にとる。技術ドメインにおいては、ｓｉｌｉｃｏｎ ｃｈｉｐ（シリコンチップ）、ｓｉｌｉｃｏｎ ｗａｆｅｒ（シリコンウェーハ）、ｓｉｌｉｃｏｎ ｖａｌｌｅｙ（シリコンバレー）、およびｃｏｐｐｅｒ ｗａｆｅｒ（銅ウェーハ）という関連が見出される。しかしながら、食品ドメインにおいては、ｃｈｉｐおよびｗａｆｅｒという用語は異なる意味を持ち、全く異なる意味関係、すなわち、ｐｏｔａｔｏ ｃｈｉｐ（ポテトチップ）、ｃｏｒｎ ｃｈｉｐ（コーンチップ）、ｃｏｒｎ ｓｕｇａｒ（コーンシュガ）、ｓｕｇａｒ ｗａｆｅｒ（シュガーウェハース）があり得る。しかし、これらの意味上の区別は、ＬＳＩベクトル空間では混乱する。この概念的に差異化されていないコーパスに対して訓練を行うことにより、「ｃｈｉｐ」および「ｗａｆｅｒ」という共通の用語について、これらの用語が２つの概念ドメインにおいて持つ別個の意味を実際にはあまりはっきりと区別しないベクトルが計算される。代わりに、２つのドメインにおける各用語の別個の意味の数値平均または「重心」を表すにすぎない２つの意味的に「希薄な」ベクトルが索引付けされる。
【００１３】
【特許文献１】米国特許第４８３９８５３号
【非特許文献１】"Using Linear Algebra for Intelligent Information Retrieval" by M. Berry et al., SIAM Review 37(4): pp. 573-595
【非特許文献２】"A Comparison of Document Clustering Techniques" by M. Steinbach et al., Technical Report 00-034, Department of Computer Science and Engineering, University of Minnesota
【発明の開示】
【発明が解決しようとする課題】
【００１４】
したがって、大規模な異種のものからなるデータ集合を操作するように効率よくスケーリングされる、ＬＳＩベースの情報検索およびテキストマイニング操作を実行する方法およびシステムを持つことが望まれる。
【００１５】
さらに、大規模なデータ集合に対して、迅速かつ正確にＬＳＩベースの情報検索およびテキストマイニング操作を実行する方法およびシステムを持つことも望まれる。
【００１６】
さらに、大規模なデータ集合に対して、概念的に差異化されるデータを混同する有害な影響を及ぼさずに、ＬＳＩベースの情報検索およびテキストマイニング操作を実行する方法およびシステムを持つことも望まれる。
【００１７】
また、大規模な文書コレクションを、関連する概念ドメインを持つ下位コレクションの類似性グラフネットワークの作成を可能にする構造に処理する方法およびシステムを持つことも望まれる。
【００１８】
さらに、ユーザが、サーチ結果で必要な類似性の度合いを指定することができるような、柔軟な方式で文書コレクションに問い合わせを行うことを可能にする方法およびシステムを持つことも望まれる。
【課題を解決するための手段】
【００１９】
本発明は、大量の異種のものからなるデータオブジェクトの集合またはコレクション（文書集合ともいう）を取り、それをより意味的に均質な概念空間または下位コレクションに区分化する方法およびシステムを提供する。これは、ＬＳＩが、これらの集合またはコレクションのそれぞれに計算された個々のベクトル空間においてより適切に振る舞うことを可能にする。数学的には、この手法は、用語／文書行列の近似的ブロック対角化およびこれらのブロックのそれぞれでのＳＶＤの獲得に等しい。その場合、問い合わせプロセスは、重なり合うブロックのネットワーク上へのマッピングであり、類似性メトリックを使ってこれらのブロックが実際にはどれほど重なり合うか示す。
【００２０】
異種のものからなる文書コレクションを、用語×文書行列を計算する前に、概念ドメインによってソートされた文書の下位コレクションに前処理することは、各ドメイン（下位コレクション）がＬＳＩを用いて独立に処理されることを可能にする。これは、記憶と計算両方のオーバーヘッドを低減し、より広いリソースネットワークにわたってベクトル空間（およびそれらのサーチ）を分散させる可能性を開く。この手法のさらなる利点は、より少ない次元から得られる任意の１つのベクトル空間でのより大きな意味解決であり、すなわち、ＬＳＩモデルがより大きな節減を示すことである。
【００２１】
大規模なデータコレクションまたは複数のデータコレクションは、グループ化またはクラスタ化効果の有無について選別される。データコレクションが同種のものからなることが知られている場合、そのコレクションについてはこの最初の選別／クラスタ化ステップがスキップされる。次いで、この情報を使って、それぞれにＳＶＤを適用する前に、文書がより意味的に均質な下位コレクションに分離される。ユーザの問い合わせが個々のＬＳＩベクトル空間に適していたかどうか、すなわち、問い合わせの意図されるセマンティクスが個々の文書コレクションのセマンティクスにマッチしたかどうか決定するために、すべてのＬＳＩベクトル空間の意味構造の間の対類似性が計算される。この距離尺度は、ベクトル空間の各対によって共用される単語から形成される意味グラフの類似性に基づくものである。ある問い合わせのセマンティクスは、複数の問い合わせ用語から、ユーザに、すべてのＬＳＩベクトル空間で表される問い合わせ用語の異なる意味文脈を提示することによって推論され、次いで、この情報を利用して適正に問い合わせに情報が提供され、ヒットリストが融合される。その主要な考え方は、大規模な文書コレクションを、互いに概念的に独立の（またはほぼ独立の）より小さい下位コレクションに区分化し、次いで、それらの下位コレクションのそれぞれについてＬＳＩベクトル空間を構築するというものである。
【００２２】
「概念的独立」とは、（後で定義する）その意味類似性尺度がおおよそゼロである、２つのＬＳＩ空間に共通のいくつかの用語の存在を意味し得る。この場合、共通の用語は、関与する概念ドメイン全体にわたる多義性（１つの用語についての複数の意味）を表す。結果として生じるＬＳＩベクトル空間のそれぞれにおいて多重解決概念分類が行われる。現実の状況においては、任意の２つの概念ドメイン間に相当数の共通用語があり得る。問い合わせにおける同義性および多義性の可能な問題に対処するために、共通用語によるリンクに基づく概念ドメインのネットワーク／グラフが生成される。次いで、ユーザの問い合わせ用語について文脈上適当な各ＬＳＩ空間が適正に対処されるように、このグラフが、問い合わせ時に、最も近く隣り合う用語を求めて検査される。問い合わせベクトル作成に際してのＬＳＩの使用は、ユーザが初期の問い合わせに類似性のレベルを選択することを可能にする。ユーザが、初期の問い合わせにより周辺的に関連し得る追加の文書を受け取る場合、システムは、ＬＳＩ技法を使って問い合わせベクトルを拡張する。
【発明を実施するための最良の形態】
【００２３】
図１を参照すると、本発明の文書コレクション処理の創意に富んだ方法が示されている。ステップ１１０で、本発明の方法は、文書コレクション（または集合）中の各文書における各用語ごとの度数カウントを生成する。この文脈における「データオブジェクト」という用語は、文書、ファイル、レコードなどの情報を指す。また、データオブジェクトは、本明細書では、文書とも呼ばれ得る。
【００２４】
任意選択の前処理ステップ１００において、各文書中の用語はその基準形式に還元され、所定の「ストップ」ワードの集合は無視される。ストップワードは、通常、「ａ」、「ａｒｅ」、「ｄｏ」、「ｆｏｒ」など、概念を接続するものとして使用されるが、実際の内容を提供しない単語である。一般的なストップワードのリストは当分野でよく知られている。また、類似の単語の集合をそれらの基準形式に還元する接尾辞ストリッパも当分野でよく知られている。そのようなストリッパまたはパーサは、ｃｏｍｐｕｔｅｄ、ｃｏｍｐｕｔｉｎｇおよびｃｏｍｐｕｔｅｒなどの単語の集合を、「ｃｏｍｐｕｔ」という語幹語に還元し、それによってそのような単語の度数カウントを結合し、用語集合の全体サイズを縮小する。
【００２５】
ステップ１２０で、異種のものからなるデータオブジェクトのコレクションは、概念ドメインによって類似の概念の下位コレクションに区分化される。より大きいデータコレクション内の１つまたは複数の別個の下位コレクションが、事実上同種のものからなることが知られている場合、それらの知られている同種のものからなるデータコレクションについて、初期の区分化は行う必要がない。データオブジェクトの、より概念的に均質な下位コレクションへの初期のソートでは、好ましくは、ｋ個のクラスタを獲得するために各段階においてｋ＝２とする再帰的な形の二分探索ｋ平均アルゴリズムが使用される。クラスタ化技法については考察されている（例えば、非特許文献２参照）。二分探索ｋ平均アルゴリズムが好ましいが、「標準」ｋ平均アルゴリズムや他の種類の空間クラスタ化アルゴリズムも利用される。階層的クラスタ化アルゴリズムを含む他の種類のクラスタ化アルゴリズムも使用される。
【００２６】
好ましくは、複数のデータオブジェクトクラスタは、二分探索ｋ平均アルゴリズムの一連の反復を実行することによってさらに洗練される。次いで、ステップ１３０で、これらｋ個の文書クラスタまたは下位コレクションのそれぞれを縮小して、おおよそ２００の直交次元を持つ縮小されたベクトル空間を生成するために、（以下で説明する）特異値分解が適用される。２００次元では、サイズが扱いやすく、しかも、下位コレクションの意味解決を獲得することもできる。利用可能な計算処理能力や時間といった制約条件に応じて、異なるサイズも使用される。
【００２７】
次いで、ステップ１４０で、ｋ平均またはその他の適当なアルゴリズムを使って、各下位コレクションごとに（中核概念を表す）ベクトルクラスタおよびそれらの重心ベクトルを発見するために、これら縮小されたベクトル空間のそれぞれにおいてクラスタ化が実行される。代替として、ベクトルクラスタおよび重心ベクトルは、縮小されたベクトル空間にクラスタ化アルゴリズムを適用するのではなく、ステップ１２０で獲得されたクラスタ化データからも獲得される。これらの重心ベクトルが獲得されると、ステップ１５０で、これらの重心ベクトルのそれぞれに最も近い所定数の用語が探し出される。本発明の好ましい実施形態では、キーワードの数は１クラスタ当たり１０に設定されるが、異なる状況では異なる数のキーワードも適当とし得る。これらは、この下位コレクションにラベル付けし、それによってそれらが含まれる概念クラスタを識別するためのキーワードとして使用される。ｋ個のベクトル空間のそれぞれは、データ中に存在する基礎をなす概念に異なる解決を提供し、それぞれの文脈は独自のキーワード集合によって表される。
【００２８】
文脈上関連する文書の下位コレクションごとにＬＳＩベクトル空間を計算し、それぞれにおいて中核概念を表すキーワードを抽出すると、次のステップ１６０は、これらの空間の間の文脈的類似性を確立することである。ステップ１６０は、問い合わせに応答して文脈的に適当なＬＳＩベクトル空間を選択し、サーチするのに必要である。類似性グラフネットワークを確立するために２つのグラフ／リンク尺度が作成される。ユーザ問い合わせが類似性グラフネットワークに渡され、そこで、各ＬＳＩベクトル空間ごとに適正な問い合わせが生成され、次いで、それぞれが独立に有用な文書を検索するように作用する。
【００２９】
この重要なステップ１６０を以下で詳細に説明する。下位コレクションＣ１、Ｃ２、．．．、Ｃｋは、ｋ平均クラスタ化アルゴリズムを使って文書クラスＣの区分として獲得されるｋ個の概念ドメインを表す。用語Ｔ１、Ｔ２、．．．、Ｔｋは、ｋ個の概念ドメインの対応する用語集合を表す。ｔｉが、ｉ＝１、２、．．．、ｋとしたときのＴｉの濃度を表し、Ｖ１、Ｖ２、．．．、Ｖｋが、ＳＶＤ表現でのｋ個の用語空間の固有行列に対応するとすれば、これらのＬＳＩ空間のそれぞれにはｆ個の因子があり、式（４）は、ｉ番目の概念ドメインのランクが低減された用語固有の基礎を形成する。
【００３０】
【数１】
【００３１】
文書集合Ｄ１、Ｄ２、．．．、Ｄｋは、ｋ個の概念ドメインの対応する文書集合である。ｄｉは、ｉ＝１、２、．．．、ｋとしたときのＤｉの濃度を表すものとする。さらに、Ｕ１、Ｕ２、．．．、Ｕｋは、ＳＶＤ表現でのｋ個の文書空間の対応する固有行列であるものとする。ここで、
【００３２】
【数２】
【００３３】
は、ｉ番目の概念ドメインのランクが低減された文書固有の基礎を形成する。Ｔｉｊ＝Ｔｉ∩Ｔｊは、概念ドメインＣｉとＣｊの共通用語の集合である。また、ｔｉｊはＴｉｊの濃度であり、ｍｉ＝ＶｉＶｉ’は、概念ドメインＣｉの用語類似性行列であり、ｍｉＱは、ｍｉの用語集合Ｑへの制限であり、Ｑにおいて出現する用語に対応するｍｉの行／列だけを選択することによって獲得される（例えば、Ｑ＝ＴｉではｍｉＱ＝ｍｉ）。用語ベクトルｖの、ＳＶＤによって生成される用語空間への投影は、ｉ番目の概念ドメインではＶｉ’ｖによって与えられる。
【００３４】
本発明の方法は２つの異なるやり方を利用し、それらにおいては、２つの概念ドメイン間の類似性が図２ａおよび２ｂに示すように求められ得る。第１の類似性尺度は、各概念ドメインに共通の用語の数である。共通の用語に関しては、任意の実際の意味を伝えるのではなく、文法上の構成として働く高度数の用語を除外することが必要である。これは、大部分、ステップ１００で、ストップワードリストを用いてそれらの用語をフィルタリングすることによって文書を前処理する間に達成されるが、そのような前処理が実行されなかった場合には、この操作が、次に、不要な高度数の用語を除外するために実行される。
【００３５】
第１の尺度は、任意の２つの概念ドメインの間の共通用語の出現度数を獲得する。この基礎をなす考え方は、多くの用語がそれらのベクトル空間に共通である場合、それらは、同じことを記述しているはずである、すなわち、それらは、類似の意味内容を持ち、類似の文脈を提供するというものである。このプロセスを、図２ａを参照して説明する。共通集合Ｔｉｊが空でない場合の概念ドメインＣｉおよびＣｊを考えると、これら２つの空間の間の近接性は、０次のものであると定義され、その度数尺度は、式（５）によって与えられる。
【００３６】
【数３】
【００３７】
図２ａのステップ２１０で、下位コレクションの各対ごとに、この度数尺度が求められる。Ｔｉｊが空であるとき、下位コレクションＣｉとＣｊの間に共通用語はない。しかしながら、ＣｉともＣｊとも共通の用語を持つ、すなわち、ＴｉｌおよびＴｊｌが両方とも空ではない、他の何らかの空間Ｃｌが存在し得る。その場合、概念空間ＣｉおよびＣｊは、中間の空間Ｃｌを介してリンクされる。図２ｂのステップ２２０で、これが求められる。この中間の空間にいくつかの選択肢がある場合には、ステップ２３０で、式（６）および（７）を使って「最強のリンク」が選択される。ここで、ＣｉとＣｊの間の近接性は１次のものであることが示され、その度数尺度は、ｐを２つの空間の間の近接性とする式（７）によって与えられる類似性尺度ｓ１を用いて、式（６）によって与えられる。
【００３８】
【数４】
【００３９】
前述の類似性尺度は、２つの概念空間の間に近接性を、共通用語の出現度数と共に考慮に入れる。ステップ２１０および２３０からのデータを使って、ステップ２４０で、直接に、またはリンクさせる下位コレクションを介して、下位コレクションの間の関係を示す類似性グラフネットワークがマップされる。
【００４０】
第２の類似性の尺度は、単に、２つの概念ドメインによっていくつが共用されるかだけでなく、共通用語のセマンティクスにより大きく影響を受ける。概念ドメインのそれぞれにおける共通用語（それがいくつあっても）の間の意味関係が、それらが同じように関連しているかどうか決定するために考察される。
【００４１】
図２ｂのステップ２５０で、（両方ともｍ×ｎ次元の）２つの行列ＸとＹの間の相関関係が、好ましくは、式（８）、（９）、（１０）および（１１）を使って求められる。
【００４２】
【数５】
【００４３】
式中、
【００４４】
【数６】
【００４５】
である。
【００４６】
ステップ２６０で、これらの行列の一方（例えばＸ）が固定したまま維持され、他方（Ｙ）が置換される（行／列）。そのような各置換ごとに、ステップ２６５で、マンテルの検定統計量が計算される。ステップ２７０で、獲得される統計量が、元のＸおよびＹを用いて獲得される検定統計量の値以上である回数（ＮＧＥ）がカウントされる。そのような置換の合計回数がＮｒｕｎｓで表される。普通、５％の有意水準には約１０００回の置換で十分であり、１％の有意水準には５０００回の置換で十分である。次いで、ステップ２７５で、式（１２）によって検定のｐ値が求められ、そのｐ値が、その有意水準を達成するのに使用された置換回数を考慮した所定の範囲内にある場合、マンテル検定の結果が許容できるとみなされる。１０００回の置換で、検定結果を許容可能とみなすには、ｐ値をおおよそ０．０５未満とする必要がある。
【００４７】
【数７】
【００４８】
第１の類似性尺度に対応して、ステップ２８０で、式（１３）によって、０次の近接性での意味尺度が求められる。
【００４９】
【数８】
【００５０】
同様に、ステップ２８５で、式（１４）によって、１次の近接性の尺度が求められる。
【００５１】
【数９】
【００５２】
次いで、ステップ２９０で、最終的な意味類似性尺度ｓ２が、やはりｐを２つの空間の間の近接性とする式（１５）によって与えられる。
【００５３】
【数１０】
【００５４】
本発明の好ましい一実施形態は、ＬＳＩベクトル空間のセマンティクスを比較するとき、第２の類似性尺度を使用する。しかし、その妥当性は第１の類似性尺度（共通用語の割合）によって与えられることに留意すべきである。第２の尺度が非常に高い値（強い意味関係）を持つが、各概念ドメイン中の合計１００用語のうち共通の用語は２つだけしかなかったことが判明していると仮定する。その場合、この尺度は大きな誤りを生じやすい。この状況において、第１の尺度は、この事実をはっきりと顕在化させ、意味尺度を検証するメトリックを提供する。２つの概念ドメインの間の意味類似性（またはその欠如）の明白な指示を獲得するには、両方の尺度が必要とされる。したがって、最も好ましい類似性の尺度は、これら２つの積である。
【００５５】
ベクトル空間の間の文脈的類似性を求めた後、この方法で生じる類似性グラフおよび「識別概念」用語が、情報検索またはデータマイニング操作において使用される。情報検索を実行するための、その中の有用な文書が検索されるような、問い合わせと概念ドメインのベクトル空間の間の類似性。
【００５６】
図３を参照すると、普通のユーザ問い合わせＱは、ステップ３１０でユーザによって入力される
【００５７】
【数１１】
【００５８】
における用語集合である。また、ユーザは、サーチ結果で求められる類似性の度合いを指定することもできる。より大きなサーチの自由度が求められる場合、システムは、以下で説明するように問い合わせベクトルを拡張する。次いで、ステップ３２０で、代表問い合わせベクトルが、ＬＳＩ空間中の投影された用語ベクトルのそれぞれの正規化された和として生成される。例えば、（１）Ｑ中の用語すべてが概念ドメイン用語集合Ｔｉに存在する、（２）いくつかの用語が存在する、または（３）全く存在しないなど、いくつかの可能な場合が考えられることに留意されたい。
【００５９】
ステップ３３０で、概念ドメイン（すなわち下位コレクション）の用語集合に問い合わせ用語すべてが存在する下位コレクションが識別される。ステップ３４０で、そのような複数のドメインが存在する場合、それぞれが伝える「意味」を伴った、それらのドメインのランク付けが、どれに問い合わせするか決定するのに役立つ。ユーザが、自分が何を探しているか知っている場合、（前述のように）提供される「識別概念」用語が役に立つ。他方、決まった目標を持たない探索ユーザにとっては、このランク付けが、偶然の発見をサポートする。
【００６０】
「識別概念」用語は、必然的に、問い合わせベクトルに対して（コサイン尺度が）最も近く投影された用語ベクトルに関連付けられた用語である。また、意味上、これらの用語は、問い合わせ用語にも最も近い。この概念ドメインのメンバとして、この用語集合は、ユーザがその問い合わせで何を意図したか発見しようとする際にそのドメインを表すのに最適な候補である。そのランク付けは、まさに、「識別概念」用語ベクトルと問い合わせベクトルの間のコサイン尺度の値である。ユーザが、マッチする文書を求めてどのドメインをサーチすべきか決定することができるように、ユーザにリストが提示される。図１のステップ３５０で、各概念ドメイン（下位コレクション）ごとに別個のリストでユーザに結果が返される。ステップ３６０で、ユーザが、ランク付けされた下位コレクションのリストに基づき、どの下位コレクションに問い合わせるべきか決定した後、ステップ３７０で、情報検索ソフトウェアは、コサインベースのベクトル空間類似性の標準ＬＳＩ手法を使って、文書マッチを検索し、次いで、ステップ３８０で、それらがユーザに提示される。代替として、問い合わせに最適な下位コレクションの選択は、最高のランクを持つものを先に選択することにより自動的にも行われ得る。これは、より対話式のテキストマイニング環境においてよりも、厳密な情報検索システムにおいてより多く使用される傾向にあるはずである。より複雑な場合には、問い合わせ用語のいくつかが、概念ドメインの用語集合に欠けている。この場合もやはり、２つの手法が使用される。第１の手法において、プロセスは、それらの欠けている用語を無視することを選択し、単に、存在する用語だけを用いて前と同様に進む。代替の手法において、プロセスは、概念ドメイン中の既存の用語と、問い合わせに存在する存在しない用語との関係を調べる。
【００６１】
前と同様に、単に、欠けている用語が無視されるだけの場合、「識別概念」用語およびランクがユーザに提示されるが、よりいっそうの注意が払われねばならない。というのは、この場合、問い合わせ用語すべてがマッチするとは限らないからである。１つの可能な解決方法は、概念用語を探し出すのに実際に使用された問い合わせ用語の割合だけそのランクを縮小することである。その場合、概念用語は、前と同様に正しく獲得される。存在しない問い合わせ用語が使用されるもう一方の場合は、実際には、次の場合の１つの具体例である。
【００６２】
最悪のシナリオでは、問い合わせ用語のいずれも概念ドメインの用語集合に存在しない。ユーザが本当にこのドメインに問い合わせしようとするかどうかの疑問が生じる。１つのことは確かである。すなわち、前述の２つの場合に該当する概念ドメインがある場合、それらは、この場合に該当する任意のドメインの前に、間違いなく利用されるはずである。このドメインが問い合わせされる１つのやり方は、問い合わせ用語から開始して、このドメインに存在する同義語を発見するために、概念ドメイン全体にわたって用語の関連を調べることである。言い換えると、問い合わせ用語自体のみならず、それらに意味的に強く関連する用語も獲得するために情報空間全体が探索される。この方法を制御するには、サーチを制限するように１次関連（次数１）が課される（この場合０次は、前述の第１の場合を示唆する）。
【００６３】
流れ図３に示すこの方法のこのバージョンは、ステップ３２０で、概念ドメインの問い合わせベクトルが、実際にそれらの問い合わせ用語を含む他の何らかの概念ドメインに類似した概念ドメインにおけるその投影された用語ベクトルの加重和として計算される点においてのみ、前述の考察と異なる。この他の概念ドメインの選択は、前述のドメイン類似性尺度に基づくものである（積尺度は、これについて適切に機能する）。問い合わせベクトルを含むと共に、問い合わせられるものに意味的にも最も近い概念ドメインが選択されると、その問い合わせドメインに拡張された問い合わせベクトルが構築される。この拡張された問い合わせベクトルを用いれば、前述のステップ３３０から３７０と同様に、「識別概念」用語を生成するのは容易である。
【００６４】
分散ＬＳＩ空間の計算および問い合わせにおいては、２つの主要な機能が実行される。第１の機能は、複数のＬＳＩベクトル空間を指定する分類体系を作成することからなり、図１のステップ１１０から１６０、および任意選択で、ステップ１００、ならびに使用される類似性技法に応じて、図２ａまたは２ｂのステップで構成される。第２の機能は、図３のステップ３１０から３７０で示すように、この空間の分散ネットワークに実際に問い合わせることからなる。しかしながら、機能的観点から見れば、これら２つの機能は互いに独立であり、第１の機能は、図４に示す分散ネットワークの様々な場所で実行される。図４には、ＬＳＩハブプロセッサ４１０を使って様々なデータオブジェクトクラスタ化および情報問い合わせ要求が制御される、分散ＬＳＩネットワークのネットワーク構成が示されている。ＬＳＩハブプロセッサ４１０は、問い合わせを仲介し、類似性グラフネットワークを生成し、新着の文書に索引付けする（またはその索引を付け直す）という３つの機能を持つ。それぞれが、関連付けられたデータベース４３１〜４３３中の複数のデータオブジェクトにアクセスすることのできる、１つまたは複数のサーバ４２１〜４２３がネットワークに追加される際に、ＬＳＩハブプロセッサ４１０は、すべてのサーバおよびデータベース中のすべてのデータオブジェクトの包括的ネットワークグラフを作成するために、図１ならびに図２ａおよび／または２ｂの本発明の方法に従ってデータオブジェクトの分散処理を制御する。ＬＳＩハブプロセッサ４１０は、前述の区分化および類似性処理方法で示すステップの一部または全部を実行することもでき、ただ単に、サーバ４２１〜４２３の１つまたは複数における処理を制御することもできることを理解すべきである。次いで、ＬＳＩハブプロセッサ４１０は、ユーザ端末４４０からの情報検索またはデータマイニング問い合わせに応答することができる。ユーザ端末４４０からの問い合わせに応答して、ＬＳＩハブプロセッサは、図２に示す本発明の方法を実行し、１つまたは複数のデータベース４３１〜４３３からそれらのデータオブジェクトを抽出することによってユーザ端末４４０に問い合わせ結果を返す。ユーザ端末４４０から、ユーザは、ＬＳＩハブプロセッサ４１０に、ユーザにさらなる柔軟性を提供する前述の拡張問い合わせを使用するよう要求することができる。
【００６５】
このように、ＬＳＩハブプロセッサ４１０は、計算集約的なクラスタ化操作、分解操作および重心ベクトルの生成を管理する。また、ＬＳＩハブプロセッサ４１０は、より多数のデータオブジェクトを持つ概念ドメインを作成し、それによってその後の検索またはテキストマイニング操作をより効率的にするために、同じデータベース中の類似のクラスタの配置を指定変更することによって、データベースの間でデータをより効率よく物理的に区分化するのにも使用される。また、ＬＳＩハブプロセッサ４１０は、類似の意味属性を持つ文書を同じ概念ドメインに配置するために、新しい文書を、物理的または仮想的に、関連性のある区分として索引付けするのにも使用される。ユーザに結果を提示する際に、ＬＳＩハブプロセッサは、ユーザの選択に応じて、概念ドメインでグループ化された結果のランク付けリスト、または問い合わせられたドメインすべてにわたる結果のランク付けリストを提示するよう、ユーザによって要求される。
【００６６】
本発明の一実施形態が、１９８９年以来ＮＳＦ（米国立科学財団）によって資金提供された提案の要約を含むＮＳＦ賞データベースを区分化し、問い合わせるのに使用された。１９８９年以前に作成された賞に関する情報は、その賞がその後修正されている場合に限り利用可能である。３７８の異なるＮＳＦプログラムから選択された合計２２，８７７件の要約が、合計カウント１１４，５６９個の一意の用語と共に使用された。
【００６７】
本発明の分散ＬＳＩ方法は、その数が解決（またな類似性）のレベルに左右される概念クラスの集合を、各クラスにラベル付けするキーワードの集合と共に提供する。最終的な概念クラス集合の実際の選択は、ユーザが自分の目的に合わせて解決のレベルを調整するために対話プロセスである。ユーザを支援するために、アルゴリズムは、現在のクラスタのいくつかのメトリックを提供する。例えば、そのような２つの解決レベルでの（それらのキーワードによって表される）概念クラスを以下に列挙する。
【００６８】
【表１】
【００６９】
【表２】
【００７０】
【表３】
【００７１】
本発明を使って獲得された予備のクラスタおよび概念ラベルは、このアルゴリズムが、解決のレベルが上げられるときに、新しい（または隠された）概念をうまく探し出すように見えることを示している。さらに、アルゴリズムによって返される概念ラベルは、正確であり、解決のレベルが上がるにつれて洗練される。
【００７２】
この場合には、分散ＬＳＩの問い合わせアルゴリズムの単純な実装が使用された。問い合わせ（用語集合）が与えられると、アルゴリズムは、分散環境において各ＬＳＩ空間ごとに問い合わせ用語集合を作成し、それがさらに、カットオフスコアによって洗練される。アルゴリズムは、前述のように、類似性メトリックの集合を使用する。個々のＬＳＩ問い合わせからの結果が収集され、閾値処理されてユーザに提示され、概念で類別される。以下のＮＳＦ理事会コードのそれぞれから、２５０文書を含むＮＳＦ賞データベースの一部が選択された。
１． ＥＮＧ 工学
２． ＧＥＯ 地球科学
３． ＳＢＥ 社会科学、行動科学および経済科学
４． ＨＥＲ 教育および人的資源
５． ＭＰＳ 数理科学および物理科学
６． ＣＳＥ コンピュータおよび情報科学／工学
７． ＢＩＯ 生物科学
【００７３】
これらの選択を通して、１７５０文書のコレクション全体が、意味的に不均質であることが確認された。次に、８つの異なるＬＳＩ空間、すなわち、各理事会コードに属するすべての文書に１つずつ、およびコレクション全体に最後の１つが計算された。分散問い合わせアルゴリズムが、７つのＬＳＩ空間に対して実行され、通常の問い合わせが包括的空間に対して実行された。比較のために、返される実際の文書が最終的なベンチマークを提供した。というのは、分散ＬＳＩ問い合わせ機構が、より適切に働くと期待されたからである。
【００７４】
主要な問い合わせは、用語｛ｂｒａｉｎ（脳），ｓｉｍｕｌａｔｉｏｎ（シミュレーション）｝からなり、これが問い合わせアルゴリズムに供給された。さらに、システム全体で０．５のカットオフ（類似性）が設定された。アルゴリズムによって生成された（このカットオフを使用する）拡張された問い合わせ集合を以下に列挙する。
【００７５】
【表４】
【００７６】
最終的な問い合わせ結果は以下の通りであった。より大きいＬＳＩ空間に対する問い合わせは、０．５より大きい類似性スコアを持つ結果を返さなかった。しかしながら、上位１０件は、低いスコアではあるが、脳シミュレーションに関連する２つの文書を含んでいた。これら２つの文書は、ＢＩＯおよびＳＢＥからの結果において、０．５より大きい類似性スコアと共に報告された。（先には見つからなかった）別の文書が、０．５を上回るスコアと共にＣＳＥ空間から報告された。この文書は、本当は、この問い合わせに関連する、ニューラルネットワークアルゴリズムに関する要約であることが判明した。その他の空間は、０．５を上回る類似性スコアを持つ文書を返さなかった。
【００７７】
以上の記述は、本発明を図示し、説明するために提示されたものにすぎない。網羅的であることも、本発明を開示通りのどんな形に限定することも意図されていない。前述の教示に照らして、多くの変更および変形が可能である。前述の適用例は、当分野の技術者が、様々な適用に関して、企図される個々の用途に適する様々な変更と共に、本発明を最も適切に利用することができるように、本発明の原理およびその実際の適用を最も適切に説明するために選択され、記述されたものである。
【図面の簡単な説明】
【００７８】
【図１】本発明による文書コレクションを処理する方法を示す流れ図である。
【図２ａ】本発明による文書コレクションを処理する方法、特に、下位コレクションの類似性に関するデータの生成を示す流れ図である。
【図２ｂ】本発明による文書コレクションを処理する方法、特に、下位コレクションの類似性に関するデータの生成を示す流れ図である。
【図３】本発明の方法により処理される文書コレクションに問い合わせする方法を示す流れ図である。
【図４】本発明による分散ＬＳＩシステムの一実施形態を示す概略図である。
【技術分野】
【０００１】
本発明は、分散アーキテクチャを使った概念に基づく情報の検索およびマイニングの方法、および、システムに関する。
【０００２】
より詳細には、本発明は、異種のものからなるデータオブジェクトのコレクションを、そこに見出される概念ドメインに関して区分化し、潜在的意味インデキシング（ＬＳＩ）を用いて区分化された各下位コレクションの内容に索引付けし、それによってこれらの分散ＬＳＩベクトル空間全体にわたって問い合わせを行うことを可能にする。これらのデータオブジェクトの下位コレクションのベクトル空間表現は、ユーザ問い合わせまたはマイニング操作に応答するのに必要とされる適当な情報源を選択するのに使用される。
【背景技術】
【０００３】
潜在的意味インデキシング（ＬＳＩ）は、用語間の依存関係または「意味類似性」を利用するベクトル検索方法の変形である高度な情報検索（ＩＲ）技術である。文書などのデータオブジェクト全体にわたる単語の用法のパターンには、何らかの基礎をなす、または「潜在的」な構造が存在し、この構造は統計的に発見されることが想定される。この手法の１つの大きな利点は、ある文書コレクションについて適当な縮小されたベクトル空間が計算されると、問い合わせは、その問い合わせと文書がマッチする用語を持たない場合でさえも、意味または概念において類似する文書を検索することができる。
【０００４】
１つのＬＳＩの情報検索手法は、各エントリが、ある用語がある文書中に出現する回数を与える、あるコレクションの用語／文書行列に特異値分解（ＳＶＤ）を適用するものであり、同一出願人により詳述されている（特許文献１参照）。大きな用語／文書行列は、通常、元の行列が１次結合によってそこから近似される、おおよそ１５０から３００の直交因子の集合に分解される。ＬＳＩで生成されるベクトル空間において、用語および文書は、これらの直交次元のそれぞれにおける連続値によって表され、したがって、用語および文書には、同じ空間において数値表現が与えられる。数学的には、用語をその行とし、文書をその列とするｎ×ｍ疎行列Ｅを一緒に形成する、ｎ個の一意の用語を持つｍ個の文書のコレクションを想定すると、Ｅ中の各エントリは、ある用語がある文書に出現する回数を与える。通常の場合、ＳＶＤを適用する前に、これらの未処理の度数カウントに対数／エントロピ重み付け（ｌｏｇ（ｔｆ＋ｌ）ｅｎｔｒｏｐｙ）が適用される。文書／文書および用語／用語の依存関係に帰属する構造は、数学的には、以下の式（１）で、ＥのＳＶＤとして表される。
Ｅ＝Ｕ（Ｅ）Σ（Ｅ）Ｖ（Ｅ）Ｔ （１）
【０００５】
式中、Ｕ（Ｅ）はＵ（Ｅ）ＴＵ（Ｅ）＝Ｉｎであるようなｎ×ｎ行列であり、Σ（Ｅ）は特異値のｎ×ｎ対角行列であり、Ｖ（Ｅ）はＶ（Ｅ）ＴＶ（Ｅ）＝Ｉｍであるようなｎ×ｍ行列であり、簡単にするために、Ｅは文書より少ない用語を持つものと想定する。
【０００６】
当然ながら、ＳＶＤの魅力は、それが、Ｅを、式（２）のランクｋの再構築で示されるより低次元のベクトル空間ｋに分解するのに使用されることである。
Ｅｋ＝Ｕｋ（Ｅ）Σｋ（Ｅ）Ｖｋ（Ｅ）Ｔ （２）
【０００７】
因子の数は、この空間を構築するのに使用される一意の用語の数よりはるかに小さくなり得るため、単語は独立でなくなる。意味の類似する単語、および、それらが含む単語に基づいて、類似の内容を持つ文書は、ＬＳＩ空間において互いの近くに位置することになる。これらの依存関係は、用語を用いて文書に問い合わせするだけでなく、文書を用いて用語に問い合わせし、用語を用いて用語に問い合わせし、他の文書を用いて文書に問い合わせすることも可能にする。実際、ＬＳＩ手法は、単に、問い合わせを、「擬似文書」、あるいはそれが含む単語に基づく加重ベクトル和として扱うにすぎない。ＬＳＩ空間において、用語または文書のベクトル間のコサインまたは内積は、それらの推定される類似性に対応し、この類似性の尺度は、文書に問い合わせし、それをフィルタにかけために興味深いやり方で利用される。この問い合わせベクトルｑと文書ベクトルｄの間の対応の尺度は式（３）によって与えられる。
ｓｉｍ（Ｕｋ（Ｅ）Ｔｑ，Ｕｋ（Ｅ）Ｔｄ） （３）
【０００８】
左特異ベクトルの行列Ｕｋ（Ｅ）をベクトル辞書として使用することの正式な正当化の根拠は提供されている（例えば、非特許文献１参照）。
【０００９】
ＬＳＩが普及した結果として、大量の異種のものからなる文書コレクションに問い合わせしようとするときにＬＳＩによって示される、いくつかの問題が識別されている。ＳＶＤは、極端に大きい用語×文書行列では計算するのが難しく、コレクションが非常に大きくなると適合率／再現率性能が低下する傾向にある。驚くべきことに、ＬＳＩを取り巻く技術的考察の多くは、これらを実施する線形代数方法およびアルゴリズム、特に、ＳＶＤを大量の、用語／文書疎行列に適用する問題に集中している。様々な用語重み付けやＳＶＤによって抽出される因子の数などのパラメータを変更することの、ＬＳＩの性能に対する影響の評価が行われている。ＬＳＩをより適切にスケーリングさせる手法の大部分は、ＬＳＩの索引付けおよびサーチアルゴリズムの複雑さを増大させることから見出されようとしている。
【００１０】
ＬＳＩは、文書コレクションが増大すると、情報検索およびテキストマイニング戦略として制限される。というのは、大規模なコレクションを用いれば、文書を異なる概念ドメインから引き出す確率がますます大きくなるからである。これは、単一のＬＳＩベクトル空間でモデル化される意味不均質性を増大させ、ゆえに、ノイズを導入し、ＬＳＩサーチアルゴリズムを「混乱させる」影響を及ぼす。あるコレクションにおいて多義性がより顕著になるにつれて、用語のベクトルは、その用語の一意の各意味ごとのすべてのベクトルの重心によって表される傾向があり、文書ベクトルは、文書が含む用語のベクトルの加重和から計算されるため、これらのセマンティクスもまた混乱する。
【００１１】
一般に、概念ドメインの数は、文書コレクションのサイズと共に増大する。これは、情報空間に新しい概念が導入されること、あるいは、既存の概念が、その下位概念のさらなる差異化に伴って（文書数が）極端に大きくなることから生じ得る。どちらの場合にも、任意のベクトル空間ベースの方法における圧縮係数が、この膨張に適応するように増大される必要がある。
【００１２】
大規模な概念的に差異化されていない文書コレクションに及ぼす訓練の有害な影響はおびただしいものがある。例えば、技術および食品という２つの概念ドメインから引き出された文書が、出典を明らかにせずに、単一の訓練集合に結合され、単一のベクトル空間を作成するためにこの集合にＬＳＩが適用されると想定する。これら２つのドメインのセマンティクスがいかに混乱し得るかは容易に想像される。「ｃｈｉｐ（チップ）」および「ｗａｆｅｒ（ウェーハ）」という用語を表すベクトルの場所を例にとる。技術ドメインにおいては、ｓｉｌｉｃｏｎ ｃｈｉｐ（シリコンチップ）、ｓｉｌｉｃｏｎ ｗａｆｅｒ（シリコンウェーハ）、ｓｉｌｉｃｏｎ ｖａｌｌｅｙ（シリコンバレー）、およびｃｏｐｐｅｒ ｗａｆｅｒ（銅ウェーハ）という関連が見出される。しかしながら、食品ドメインにおいては、ｃｈｉｐおよびｗａｆｅｒという用語は異なる意味を持ち、全く異なる意味関係、すなわち、ｐｏｔａｔｏ ｃｈｉｐ（ポテトチップ）、ｃｏｒｎ ｃｈｉｐ（コーンチップ）、ｃｏｒｎ ｓｕｇａｒ（コーンシュガ）、ｓｕｇａｒ ｗａｆｅｒ（シュガーウェハース）があり得る。しかし、これらの意味上の区別は、ＬＳＩベクトル空間では混乱する。この概念的に差異化されていないコーパスに対して訓練を行うことにより、「ｃｈｉｐ」および「ｗａｆｅｒ」という共通の用語について、これらの用語が２つの概念ドメインにおいて持つ別個の意味を実際にはあまりはっきりと区別しないベクトルが計算される。代わりに、２つのドメインにおける各用語の別個の意味の数値平均または「重心」を表すにすぎない２つの意味的に「希薄な」ベクトルが索引付けされる。
【００１３】
【特許文献１】米国特許第４８３９８５３号
【非特許文献１】"Using Linear Algebra for Intelligent Information Retrieval" by M. Berry et al., SIAM Review 37(4): pp. 573-595
【非特許文献２】"A Comparison of Document Clustering Techniques" by M. Steinbach et al., Technical Report 00-034, Department of Computer Science and Engineering, University of Minnesota
【発明の開示】
【発明が解決しようとする課題】
【００１４】
したがって、大規模な異種のものからなるデータ集合を操作するように効率よくスケーリングされる、ＬＳＩベースの情報検索およびテキストマイニング操作を実行する方法およびシステムを持つことが望まれる。
【００１５】
さらに、大規模なデータ集合に対して、迅速かつ正確にＬＳＩベースの情報検索およびテキストマイニング操作を実行する方法およびシステムを持つことも望まれる。
【００１６】
さらに、大規模なデータ集合に対して、概念的に差異化されるデータを混同する有害な影響を及ぼさずに、ＬＳＩベースの情報検索およびテキストマイニング操作を実行する方法およびシステムを持つことも望まれる。
【００１７】
また、大規模な文書コレクションを、関連する概念ドメインを持つ下位コレクションの類似性グラフネットワークの作成を可能にする構造に処理する方法およびシステムを持つことも望まれる。
【００１８】
さらに、ユーザが、サーチ結果で必要な類似性の度合いを指定することができるような、柔軟な方式で文書コレクションに問い合わせを行うことを可能にする方法およびシステムを持つことも望まれる。
【課題を解決するための手段】
【００１９】
本発明は、大量の異種のものからなるデータオブジェクトの集合またはコレクション（文書集合ともいう）を取り、それをより意味的に均質な概念空間または下位コレクションに区分化する方法およびシステムを提供する。これは、ＬＳＩが、これらの集合またはコレクションのそれぞれに計算された個々のベクトル空間においてより適切に振る舞うことを可能にする。数学的には、この手法は、用語／文書行列の近似的ブロック対角化およびこれらのブロックのそれぞれでのＳＶＤの獲得に等しい。その場合、問い合わせプロセスは、重なり合うブロックのネットワーク上へのマッピングであり、類似性メトリックを使ってこれらのブロックが実際にはどれほど重なり合うか示す。
【００２０】
異種のものからなる文書コレクションを、用語×文書行列を計算する前に、概念ドメインによってソートされた文書の下位コレクションに前処理することは、各ドメイン（下位コレクション）がＬＳＩを用いて独立に処理されることを可能にする。これは、記憶と計算両方のオーバーヘッドを低減し、より広いリソースネットワークにわたってベクトル空間（およびそれらのサーチ）を分散させる可能性を開く。この手法のさらなる利点は、より少ない次元から得られる任意の１つのベクトル空間でのより大きな意味解決であり、すなわち、ＬＳＩモデルがより大きな節減を示すことである。
【００２１】
大規模なデータコレクションまたは複数のデータコレクションは、グループ化またはクラスタ化効果の有無について選別される。データコレクションが同種のものからなることが知られている場合、そのコレクションについてはこの最初の選別／クラスタ化ステップがスキップされる。次いで、この情報を使って、それぞれにＳＶＤを適用する前に、文書がより意味的に均質な下位コレクションに分離される。ユーザの問い合わせが個々のＬＳＩベクトル空間に適していたかどうか、すなわち、問い合わせの意図されるセマンティクスが個々の文書コレクションのセマンティクスにマッチしたかどうか決定するために、すべてのＬＳＩベクトル空間の意味構造の間の対類似性が計算される。この距離尺度は、ベクトル空間の各対によって共用される単語から形成される意味グラフの類似性に基づくものである。ある問い合わせのセマンティクスは、複数の問い合わせ用語から、ユーザに、すべてのＬＳＩベクトル空間で表される問い合わせ用語の異なる意味文脈を提示することによって推論され、次いで、この情報を利用して適正に問い合わせに情報が提供され、ヒットリストが融合される。その主要な考え方は、大規模な文書コレクションを、互いに概念的に独立の（またはほぼ独立の）より小さい下位コレクションに区分化し、次いで、それらの下位コレクションのそれぞれについてＬＳＩベクトル空間を構築するというものである。
【００２２】
「概念的独立」とは、（後で定義する）その意味類似性尺度がおおよそゼロである、２つのＬＳＩ空間に共通のいくつかの用語の存在を意味し得る。この場合、共通の用語は、関与する概念ドメイン全体にわたる多義性（１つの用語についての複数の意味）を表す。結果として生じるＬＳＩベクトル空間のそれぞれにおいて多重解決概念分類が行われる。現実の状況においては、任意の２つの概念ドメイン間に相当数の共通用語があり得る。問い合わせにおける同義性および多義性の可能な問題に対処するために、共通用語によるリンクに基づく概念ドメインのネットワーク／グラフが生成される。次いで、ユーザの問い合わせ用語について文脈上適当な各ＬＳＩ空間が適正に対処されるように、このグラフが、問い合わせ時に、最も近く隣り合う用語を求めて検査される。問い合わせベクトル作成に際してのＬＳＩの使用は、ユーザが初期の問い合わせに類似性のレベルを選択することを可能にする。ユーザが、初期の問い合わせにより周辺的に関連し得る追加の文書を受け取る場合、システムは、ＬＳＩ技法を使って問い合わせベクトルを拡張する。
【発明を実施するための最良の形態】
【００２３】
図１を参照すると、本発明の文書コレクション処理の創意に富んだ方法が示されている。ステップ１１０で、本発明の方法は、文書コレクション（または集合）中の各文書における各用語ごとの度数カウントを生成する。この文脈における「データオブジェクト」という用語は、文書、ファイル、レコードなどの情報を指す。また、データオブジェクトは、本明細書では、文書とも呼ばれ得る。
【００２４】
任意選択の前処理ステップ１００において、各文書中の用語はその基準形式に還元され、所定の「ストップ」ワードの集合は無視される。ストップワードは、通常、「ａ」、「ａｒｅ」、「ｄｏ」、「ｆｏｒ」など、概念を接続するものとして使用されるが、実際の内容を提供しない単語である。一般的なストップワードのリストは当分野でよく知られている。また、類似の単語の集合をそれらの基準形式に還元する接尾辞ストリッパも当分野でよく知られている。そのようなストリッパまたはパーサは、ｃｏｍｐｕｔｅｄ、ｃｏｍｐｕｔｉｎｇおよびｃｏｍｐｕｔｅｒなどの単語の集合を、「ｃｏｍｐｕｔ」という語幹語に還元し、それによってそのような単語の度数カウントを結合し、用語集合の全体サイズを縮小する。
【００２５】
ステップ１２０で、異種のものからなるデータオブジェクトのコレクションは、概念ドメインによって類似の概念の下位コレクションに区分化される。より大きいデータコレクション内の１つまたは複数の別個の下位コレクションが、事実上同種のものからなることが知られている場合、それらの知られている同種のものからなるデータコレクションについて、初期の区分化は行う必要がない。データオブジェクトの、より概念的に均質な下位コレクションへの初期のソートでは、好ましくは、ｋ個のクラスタを獲得するために各段階においてｋ＝２とする再帰的な形の二分探索ｋ平均アルゴリズムが使用される。クラスタ化技法については考察されている（例えば、非特許文献２参照）。二分探索ｋ平均アルゴリズムが好ましいが、「標準」ｋ平均アルゴリズムや他の種類の空間クラスタ化アルゴリズムも利用される。階層的クラスタ化アルゴリズムを含む他の種類のクラスタ化アルゴリズムも使用される。
【００２６】
好ましくは、複数のデータオブジェクトクラスタは、二分探索ｋ平均アルゴリズムの一連の反復を実行することによってさらに洗練される。次いで、ステップ１３０で、これらｋ個の文書クラスタまたは下位コレクションのそれぞれを縮小して、おおよそ２００の直交次元を持つ縮小されたベクトル空間を生成するために、（以下で説明する）特異値分解が適用される。２００次元では、サイズが扱いやすく、しかも、下位コレクションの意味解決を獲得することもできる。利用可能な計算処理能力や時間といった制約条件に応じて、異なるサイズも使用される。
【００２７】
次いで、ステップ１４０で、ｋ平均またはその他の適当なアルゴリズムを使って、各下位コレクションごとに（中核概念を表す）ベクトルクラスタおよびそれらの重心ベクトルを発見するために、これら縮小されたベクトル空間のそれぞれにおいてクラスタ化が実行される。代替として、ベクトルクラスタおよび重心ベクトルは、縮小されたベクトル空間にクラスタ化アルゴリズムを適用するのではなく、ステップ１２０で獲得されたクラスタ化データからも獲得される。これらの重心ベクトルが獲得されると、ステップ１５０で、これらの重心ベクトルのそれぞれに最も近い所定数の用語が探し出される。本発明の好ましい実施形態では、キーワードの数は１クラスタ当たり１０に設定されるが、異なる状況では異なる数のキーワードも適当とし得る。これらは、この下位コレクションにラベル付けし、それによってそれらが含まれる概念クラスタを識別するためのキーワードとして使用される。ｋ個のベクトル空間のそれぞれは、データ中に存在する基礎をなす概念に異なる解決を提供し、それぞれの文脈は独自のキーワード集合によって表される。
【００２８】
文脈上関連する文書の下位コレクションごとにＬＳＩベクトル空間を計算し、それぞれにおいて中核概念を表すキーワードを抽出すると、次のステップ１６０は、これらの空間の間の文脈的類似性を確立することである。ステップ１６０は、問い合わせに応答して文脈的に適当なＬＳＩベクトル空間を選択し、サーチするのに必要である。類似性グラフネットワークを確立するために２つのグラフ／リンク尺度が作成される。ユーザ問い合わせが類似性グラフネットワークに渡され、そこで、各ＬＳＩベクトル空間ごとに適正な問い合わせが生成され、次いで、それぞれが独立に有用な文書を検索するように作用する。
【００２９】
この重要なステップ１６０を以下で詳細に説明する。下位コレクションＣ１、Ｃ２、．．．、Ｃｋは、ｋ平均クラスタ化アルゴリズムを使って文書クラスＣの区分として獲得されるｋ個の概念ドメインを表す。用語Ｔ１、Ｔ２、．．．、Ｔｋは、ｋ個の概念ドメインの対応する用語集合を表す。ｔｉが、ｉ＝１、２、．．．、ｋとしたときのＴｉの濃度を表し、Ｖ１、Ｖ２、．．．、Ｖｋが、ＳＶＤ表現でのｋ個の用語空間の固有行列に対応するとすれば、これらのＬＳＩ空間のそれぞれにはｆ個の因子があり、式（４）は、ｉ番目の概念ドメインのランクが低減された用語固有の基礎を形成する。
【００３０】
【数１】
【００３１】
文書集合Ｄ１、Ｄ２、．．．、Ｄｋは、ｋ個の概念ドメインの対応する文書集合である。ｄｉは、ｉ＝１、２、．．．、ｋとしたときのＤｉの濃度を表すものとする。さらに、Ｕ１、Ｕ２、．．．、Ｕｋは、ＳＶＤ表現でのｋ個の文書空間の対応する固有行列であるものとする。ここで、
【００３２】
【数２】
【００３３】
は、ｉ番目の概念ドメインのランクが低減された文書固有の基礎を形成する。Ｔｉｊ＝Ｔｉ∩Ｔｊは、概念ドメインＣｉとＣｊの共通用語の集合である。また、ｔｉｊはＴｉｊの濃度であり、ｍｉ＝ＶｉＶｉ’は、概念ドメインＣｉの用語類似性行列であり、ｍｉＱは、ｍｉの用語集合Ｑへの制限であり、Ｑにおいて出現する用語に対応するｍｉの行／列だけを選択することによって獲得される（例えば、Ｑ＝ＴｉではｍｉＱ＝ｍｉ）。用語ベクトルｖの、ＳＶＤによって生成される用語空間への投影は、ｉ番目の概念ドメインではＶｉ’ｖによって与えられる。
【００３４】
本発明の方法は２つの異なるやり方を利用し、それらにおいては、２つの概念ドメイン間の類似性が図２ａおよび２ｂに示すように求められ得る。第１の類似性尺度は、各概念ドメインに共通の用語の数である。共通の用語に関しては、任意の実際の意味を伝えるのではなく、文法上の構成として働く高度数の用語を除外することが必要である。これは、大部分、ステップ１００で、ストップワードリストを用いてそれらの用語をフィルタリングすることによって文書を前処理する間に達成されるが、そのような前処理が実行されなかった場合には、この操作が、次に、不要な高度数の用語を除外するために実行される。
【００３５】
第１の尺度は、任意の２つの概念ドメインの間の共通用語の出現度数を獲得する。この基礎をなす考え方は、多くの用語がそれらのベクトル空間に共通である場合、それらは、同じことを記述しているはずである、すなわち、それらは、類似の意味内容を持ち、類似の文脈を提供するというものである。このプロセスを、図２ａを参照して説明する。共通集合Ｔｉｊが空でない場合の概念ドメインＣｉおよびＣｊを考えると、これら２つの空間の間の近接性は、０次のものであると定義され、その度数尺度は、式（５）によって与えられる。
【００３６】
【数３】
【００３７】
図２ａのステップ２１０で、下位コレクションの各対ごとに、この度数尺度が求められる。Ｔｉｊが空であるとき、下位コレクションＣｉとＣｊの間に共通用語はない。しかしながら、ＣｉともＣｊとも共通の用語を持つ、すなわち、ＴｉｌおよびＴｊｌが両方とも空ではない、他の何らかの空間Ｃｌが存在し得る。その場合、概念空間ＣｉおよびＣｊは、中間の空間Ｃｌを介してリンクされる。図２ｂのステップ２２０で、これが求められる。この中間の空間にいくつかの選択肢がある場合には、ステップ２３０で、式（６）および（７）を使って「最強のリンク」が選択される。ここで、ＣｉとＣｊの間の近接性は１次のものであることが示され、その度数尺度は、ｐを２つの空間の間の近接性とする式（７）によって与えられる類似性尺度ｓ１を用いて、式（６）によって与えられる。
【００３８】
【数４】
【００３９】
前述の類似性尺度は、２つの概念空間の間に近接性を、共通用語の出現度数と共に考慮に入れる。ステップ２１０および２３０からのデータを使って、ステップ２４０で、直接に、またはリンクさせる下位コレクションを介して、下位コレクションの間の関係を示す類似性グラフネットワークがマップされる。
【００４０】
第２の類似性の尺度は、単に、２つの概念ドメインによっていくつが共用されるかだけでなく、共通用語のセマンティクスにより大きく影響を受ける。概念ドメインのそれぞれにおける共通用語（それがいくつあっても）の間の意味関係が、それらが同じように関連しているかどうか決定するために考察される。
【００４１】
図２ｂのステップ２５０で、（両方ともｍ×ｎ次元の）２つの行列ＸとＹの間の相関関係が、好ましくは、式（８）、（９）、（１０）および（１１）を使って求められる。
【００４２】
【数５】
【００４３】
式中、
【００４４】
【数６】
【００４５】
である。
【００４６】
ステップ２６０で、これらの行列の一方（例えばＸ）が固定したまま維持され、他方（Ｙ）が置換される（行／列）。そのような各置換ごとに、ステップ２６５で、マンテルの検定統計量が計算される。ステップ２７０で、獲得される統計量が、元のＸおよびＹを用いて獲得される検定統計量の値以上である回数（ＮＧＥ）がカウントされる。そのような置換の合計回数がＮｒｕｎｓで表される。普通、５％の有意水準には約１０００回の置換で十分であり、１％の有意水準には５０００回の置換で十分である。次いで、ステップ２７５で、式（１２）によって検定のｐ値が求められ、そのｐ値が、その有意水準を達成するのに使用された置換回数を考慮した所定の範囲内にある場合、マンテル検定の結果が許容できるとみなされる。１０００回の置換で、検定結果を許容可能とみなすには、ｐ値をおおよそ０．０５未満とする必要がある。
【００４７】
【数７】
【００４８】
第１の類似性尺度に対応して、ステップ２８０で、式（１３）によって、０次の近接性での意味尺度が求められる。
【００４９】
【数８】
【００５０】
同様に、ステップ２８５で、式（１４）によって、１次の近接性の尺度が求められる。
【００５１】
【数９】
【００５２】
次いで、ステップ２９０で、最終的な意味類似性尺度ｓ２が、やはりｐを２つの空間の間の近接性とする式（１５）によって与えられる。
【００５３】
【数１０】
【００５４】
本発明の好ましい一実施形態は、ＬＳＩベクトル空間のセマンティクスを比較するとき、第２の類似性尺度を使用する。しかし、その妥当性は第１の類似性尺度（共通用語の割合）によって与えられることに留意すべきである。第２の尺度が非常に高い値（強い意味関係）を持つが、各概念ドメイン中の合計１００用語のうち共通の用語は２つだけしかなかったことが判明していると仮定する。その場合、この尺度は大きな誤りを生じやすい。この状況において、第１の尺度は、この事実をはっきりと顕在化させ、意味尺度を検証するメトリックを提供する。２つの概念ドメインの間の意味類似性（またはその欠如）の明白な指示を獲得するには、両方の尺度が必要とされる。したがって、最も好ましい類似性の尺度は、これら２つの積である。
【００５５】
ベクトル空間の間の文脈的類似性を求めた後、この方法で生じる類似性グラフおよび「識別概念」用語が、情報検索またはデータマイニング操作において使用される。情報検索を実行するための、その中の有用な文書が検索されるような、問い合わせと概念ドメインのベクトル空間の間の類似性。
【００５６】
図３を参照すると、普通のユーザ問い合わせＱは、ステップ３１０でユーザによって入力される
【００５７】
【数１１】
【００５８】
における用語集合である。また、ユーザは、サーチ結果で求められる類似性の度合いを指定することもできる。より大きなサーチの自由度が求められる場合、システムは、以下で説明するように問い合わせベクトルを拡張する。次いで、ステップ３２０で、代表問い合わせベクトルが、ＬＳＩ空間中の投影された用語ベクトルのそれぞれの正規化された和として生成される。例えば、（１）Ｑ中の用語すべてが概念ドメイン用語集合Ｔｉに存在する、（２）いくつかの用語が存在する、または（３）全く存在しないなど、いくつかの可能な場合が考えられることに留意されたい。
【００５９】
ステップ３３０で、概念ドメイン（すなわち下位コレクション）の用語集合に問い合わせ用語すべてが存在する下位コレクションが識別される。ステップ３４０で、そのような複数のドメインが存在する場合、それぞれが伝える「意味」を伴った、それらのドメインのランク付けが、どれに問い合わせするか決定するのに役立つ。ユーザが、自分が何を探しているか知っている場合、（前述のように）提供される「識別概念」用語が役に立つ。他方、決まった目標を持たない探索ユーザにとっては、このランク付けが、偶然の発見をサポートする。
【００６０】
「識別概念」用語は、必然的に、問い合わせベクトルに対して（コサイン尺度が）最も近く投影された用語ベクトルに関連付けられた用語である。また、意味上、これらの用語は、問い合わせ用語にも最も近い。この概念ドメインのメンバとして、この用語集合は、ユーザがその問い合わせで何を意図したか発見しようとする際にそのドメインを表すのに最適な候補である。そのランク付けは、まさに、「識別概念」用語ベクトルと問い合わせベクトルの間のコサイン尺度の値である。ユーザが、マッチする文書を求めてどのドメインをサーチすべきか決定することができるように、ユーザにリストが提示される。図１のステップ３５０で、各概念ドメイン（下位コレクション）ごとに別個のリストでユーザに結果が返される。ステップ３６０で、ユーザが、ランク付けされた下位コレクションのリストに基づき、どの下位コレクションに問い合わせるべきか決定した後、ステップ３７０で、情報検索ソフトウェアは、コサインベースのベクトル空間類似性の標準ＬＳＩ手法を使って、文書マッチを検索し、次いで、ステップ３８０で、それらがユーザに提示される。代替として、問い合わせに最適な下位コレクションの選択は、最高のランクを持つものを先に選択することにより自動的にも行われ得る。これは、より対話式のテキストマイニング環境においてよりも、厳密な情報検索システムにおいてより多く使用される傾向にあるはずである。より複雑な場合には、問い合わせ用語のいくつかが、概念ドメインの用語集合に欠けている。この場合もやはり、２つの手法が使用される。第１の手法において、プロセスは、それらの欠けている用語を無視することを選択し、単に、存在する用語だけを用いて前と同様に進む。代替の手法において、プロセスは、概念ドメイン中の既存の用語と、問い合わせに存在する存在しない用語との関係を調べる。
【００６１】
前と同様に、単に、欠けている用語が無視されるだけの場合、「識別概念」用語およびランクがユーザに提示されるが、よりいっそうの注意が払われねばならない。というのは、この場合、問い合わせ用語すべてがマッチするとは限らないからである。１つの可能な解決方法は、概念用語を探し出すのに実際に使用された問い合わせ用語の割合だけそのランクを縮小することである。その場合、概念用語は、前と同様に正しく獲得される。存在しない問い合わせ用語が使用されるもう一方の場合は、実際には、次の場合の１つの具体例である。
【００６２】
最悪のシナリオでは、問い合わせ用語のいずれも概念ドメインの用語集合に存在しない。ユーザが本当にこのドメインに問い合わせしようとするかどうかの疑問が生じる。１つのことは確かである。すなわち、前述の２つの場合に該当する概念ドメインがある場合、それらは、この場合に該当する任意のドメインの前に、間違いなく利用されるはずである。このドメインが問い合わせされる１つのやり方は、問い合わせ用語から開始して、このドメインに存在する同義語を発見するために、概念ドメイン全体にわたって用語の関連を調べることである。言い換えると、問い合わせ用語自体のみならず、それらに意味的に強く関連する用語も獲得するために情報空間全体が探索される。この方法を制御するには、サーチを制限するように１次関連（次数１）が課される（この場合０次は、前述の第１の場合を示唆する）。
【００６３】
流れ図３に示すこの方法のこのバージョンは、ステップ３２０で、概念ドメインの問い合わせベクトルが、実際にそれらの問い合わせ用語を含む他の何らかの概念ドメインに類似した概念ドメインにおけるその投影された用語ベクトルの加重和として計算される点においてのみ、前述の考察と異なる。この他の概念ドメインの選択は、前述のドメイン類似性尺度に基づくものである（積尺度は、これについて適切に機能する）。問い合わせベクトルを含むと共に、問い合わせられるものに意味的にも最も近い概念ドメインが選択されると、その問い合わせドメインに拡張された問い合わせベクトルが構築される。この拡張された問い合わせベクトルを用いれば、前述のステップ３３０から３７０と同様に、「識別概念」用語を生成するのは容易である。
【００６４】
分散ＬＳＩ空間の計算および問い合わせにおいては、２つの主要な機能が実行される。第１の機能は、複数のＬＳＩベクトル空間を指定する分類体系を作成することからなり、図１のステップ１１０から１６０、および任意選択で、ステップ１００、ならびに使用される類似性技法に応じて、図２ａまたは２ｂのステップで構成される。第２の機能は、図３のステップ３１０から３７０で示すように、この空間の分散ネットワークに実際に問い合わせることからなる。しかしながら、機能的観点から見れば、これら２つの機能は互いに独立であり、第１の機能は、図４に示す分散ネットワークの様々な場所で実行される。図４には、ＬＳＩハブプロセッサ４１０を使って様々なデータオブジェクトクラスタ化および情報問い合わせ要求が制御される、分散ＬＳＩネットワークのネットワーク構成が示されている。ＬＳＩハブプロセッサ４１０は、問い合わせを仲介し、類似性グラフネットワークを生成し、新着の文書に索引付けする（またはその索引を付け直す）という３つの機能を持つ。それぞれが、関連付けられたデータベース４３１〜４３３中の複数のデータオブジェクトにアクセスすることのできる、１つまたは複数のサーバ４２１〜４２３がネットワークに追加される際に、ＬＳＩハブプロセッサ４１０は、すべてのサーバおよびデータベース中のすべてのデータオブジェクトの包括的ネットワークグラフを作成するために、図１ならびに図２ａおよび／または２ｂの本発明の方法に従ってデータオブジェクトの分散処理を制御する。ＬＳＩハブプロセッサ４１０は、前述の区分化および類似性処理方法で示すステップの一部または全部を実行することもでき、ただ単に、サーバ４２１〜４２３の１つまたは複数における処理を制御することもできることを理解すべきである。次いで、ＬＳＩハブプロセッサ４１０は、ユーザ端末４４０からの情報検索またはデータマイニング問い合わせに応答することができる。ユーザ端末４４０からの問い合わせに応答して、ＬＳＩハブプロセッサは、図２に示す本発明の方法を実行し、１つまたは複数のデータベース４３１〜４３３からそれらのデータオブジェクトを抽出することによってユーザ端末４４０に問い合わせ結果を返す。ユーザ端末４４０から、ユーザは、ＬＳＩハブプロセッサ４１０に、ユーザにさらなる柔軟性を提供する前述の拡張問い合わせを使用するよう要求することができる。
【００６５】
このように、ＬＳＩハブプロセッサ４１０は、計算集約的なクラスタ化操作、分解操作および重心ベクトルの生成を管理する。また、ＬＳＩハブプロセッサ４１０は、より多数のデータオブジェクトを持つ概念ドメインを作成し、それによってその後の検索またはテキストマイニング操作をより効率的にするために、同じデータベース中の類似のクラスタの配置を指定変更することによって、データベースの間でデータをより効率よく物理的に区分化するのにも使用される。また、ＬＳＩハブプロセッサ４１０は、類似の意味属性を持つ文書を同じ概念ドメインに配置するために、新しい文書を、物理的または仮想的に、関連性のある区分として索引付けするのにも使用される。ユーザに結果を提示する際に、ＬＳＩハブプロセッサは、ユーザの選択に応じて、概念ドメインでグループ化された結果のランク付けリスト、または問い合わせられたドメインすべてにわたる結果のランク付けリストを提示するよう、ユーザによって要求される。
【００６６】
本発明の一実施形態が、１９８９年以来ＮＳＦ（米国立科学財団）によって資金提供された提案の要約を含むＮＳＦ賞データベースを区分化し、問い合わせるのに使用された。１９８９年以前に作成された賞に関する情報は、その賞がその後修正されている場合に限り利用可能である。３７８の異なるＮＳＦプログラムから選択された合計２２，８７７件の要約が、合計カウント１１４，５６９個の一意の用語と共に使用された。
【００６７】
本発明の分散ＬＳＩ方法は、その数が解決（またな類似性）のレベルに左右される概念クラスの集合を、各クラスにラベル付けするキーワードの集合と共に提供する。最終的な概念クラス集合の実際の選択は、ユーザが自分の目的に合わせて解決のレベルを調整するために対話プロセスである。ユーザを支援するために、アルゴリズムは、現在のクラスタのいくつかのメトリックを提供する。例えば、そのような２つの解決レベルでの（それらのキーワードによって表される）概念クラスを以下に列挙する。
【００６８】
【表１】
【００６９】
【表２】
【００７０】
【表３】
【００７１】
本発明を使って獲得された予備のクラスタおよび概念ラベルは、このアルゴリズムが、解決のレベルが上げられるときに、新しい（または隠された）概念をうまく探し出すように見えることを示している。さらに、アルゴリズムによって返される概念ラベルは、正確であり、解決のレベルが上がるにつれて洗練される。
【００７２】
この場合には、分散ＬＳＩの問い合わせアルゴリズムの単純な実装が使用された。問い合わせ（用語集合）が与えられると、アルゴリズムは、分散環境において各ＬＳＩ空間ごとに問い合わせ用語集合を作成し、それがさらに、カットオフスコアによって洗練される。アルゴリズムは、前述のように、類似性メトリックの集合を使用する。個々のＬＳＩ問い合わせからの結果が収集され、閾値処理されてユーザに提示され、概念で類別される。以下のＮＳＦ理事会コードのそれぞれから、２５０文書を含むＮＳＦ賞データベースの一部が選択された。
１． ＥＮＧ 工学
２． ＧＥＯ 地球科学
３． ＳＢＥ 社会科学、行動科学および経済科学
４． ＨＥＲ 教育および人的資源
５． ＭＰＳ 数理科学および物理科学
６． ＣＳＥ コンピュータおよび情報科学／工学
７． ＢＩＯ 生物科学
【００７３】
これらの選択を通して、１７５０文書のコレクション全体が、意味的に不均質であることが確認された。次に、８つの異なるＬＳＩ空間、すなわち、各理事会コードに属するすべての文書に１つずつ、およびコレクション全体に最後の１つが計算された。分散問い合わせアルゴリズムが、７つのＬＳＩ空間に対して実行され、通常の問い合わせが包括的空間に対して実行された。比較のために、返される実際の文書が最終的なベンチマークを提供した。というのは、分散ＬＳＩ問い合わせ機構が、より適切に働くと期待されたからである。
【００７４】
主要な問い合わせは、用語｛ｂｒａｉｎ（脳），ｓｉｍｕｌａｔｉｏｎ（シミュレーション）｝からなり、これが問い合わせアルゴリズムに供給された。さらに、システム全体で０．５のカットオフ（類似性）が設定された。アルゴリズムによって生成された（このカットオフを使用する）拡張された問い合わせ集合を以下に列挙する。
【００７５】
【表４】
【００７６】
最終的な問い合わせ結果は以下の通りであった。より大きいＬＳＩ空間に対する問い合わせは、０．５より大きい類似性スコアを持つ結果を返さなかった。しかしながら、上位１０件は、低いスコアではあるが、脳シミュレーションに関連する２つの文書を含んでいた。これら２つの文書は、ＢＩＯおよびＳＢＥからの結果において、０．５より大きい類似性スコアと共に報告された。（先には見つからなかった）別の文書が、０．５を上回るスコアと共にＣＳＥ空間から報告された。この文書は、本当は、この問い合わせに関連する、ニューラルネットワークアルゴリズムに関する要約であることが判明した。その他の空間は、０．５を上回る類似性スコアを持つ文書を返さなかった。
【００７７】
以上の記述は、本発明を図示し、説明するために提示されたものにすぎない。網羅的であることも、本発明を開示通りのどんな形に限定することも意図されていない。前述の教示に照らして、多くの変更および変形が可能である。前述の適用例は、当分野の技術者が、様々な適用に関して、企図される個々の用途に適する様々な変更と共に、本発明を最も適切に利用することができるように、本発明の原理およびその実際の適用を最も適切に説明するために選択され、記述されたものである。
【図面の簡単な説明】
【００７８】
【図１】本発明による文書コレクションを処理する方法を示す流れ図である。
【図２ａ】本発明による文書コレクションを処理する方法、特に、下位コレクションの類似性に関するデータの生成を示す流れ図である。
【図２ｂ】本発明による文書コレクションを処理する方法、特に、下位コレクションの類似性に関するデータの生成を示す流れ図である。
【図３】本発明の方法により処理される文書コレクションに問い合わせする方法を示す流れ図である。
【図４】本発明による分散ＬＳＩシステムの一実施形態を示す概略図である。
【特許請求の範囲】
【請求項１】
情報検索およびデータマイニング操作で使用するためにデータオブジェクトのコレクションを処理する方法であって、
前記コレクション中の各データオブジェクトの各用語ごとに度数カウントを生成するステップと、
用語／データオブジェクト情報を使って、前記データオブジェクトのコレクションを、それぞれがその内に含まれる前記データオブジェクトの概念的依存関係に基づくものである、複数の下位コレクションに区分化するステップと、
各下位コレクションごとに用語／データオブジェクト行列を生成するステップと、
前記用語／データオブジェクト行列を縮小された特異値表現に分解するステップと、
各下位コレクションの重心ベクトルを決定するステップと、
各下位コレクションにおいて重心ベクトルに最も近い所定数の用語を見つけるステップと、
下位コレクション間の類似性を確立するために類似性グラフネットワークを作成するステップと
を具えたことを特徴とする方法。
【請求項２】
各データオブジェクトごとに前記用語度数カウントを生成する前に、事前選択されたストップワードの集合を除去するために文書を前処理するステップをさらに具えたことを特徴とする請求項１記載の方法。
【請求項３】
前記前処理するステップは、様々な用語の基準形式への還元をさらに具えたことを特徴とする請求項２記載の方法。
【請求項４】
前記コレクションを区分化するステップは、二分探索ｋ平均クラスタ化アルゴリズムを使って行われることを特徴とする請求項１記載の方法。
【請求項５】
前記コレクションを区分化するステップは、ｋ平均クラスタ化アルゴリズムを使って行われることを特徴とする請求項１記載の方法。
【請求項６】
前記コレクションを区分化するステップは、階層的クラスタ化を使って行われることを特徴とする請求項１に記載の方法。
【請求項７】
前記所定数の用語は１０個であることを特徴とする請求項１に記載の方法。
【請求項８】
各下位コレクションの重心ベクトルを決定するステップは、前記下位コレクションの前記用語／データオブジェクト行列の還元された特異値表現にクラスタ化アルゴリズムを使用することを特徴とする請求項１記載の方法。
【請求項９】
各下位コレクションの重心ベクトルを決定するステップは、前記区分化するステップの結果に基づくものであることを特徴とする請求項１記載の方法。
【請求項１０】
各下位コレクションごとの前記用語／データオブジェクトの前記還元された特異値表現は、おおよそ２００の直交次元を持つことを特徴とする請求項１記載の方法。
【請求項１１】
下位コレクション間の類似性を確立するステップは、下位コレクション間の共通用語の出現度数に基づくものであることを特徴とする請求項１記載の方法。
【請求項１２】
前記類似性グラフネットワークを作成するステップは、前記下位コレクションのそれぞれにおける前記共通用語の間の意味関係に基づくものであることを特徴とする請求項１記載の方法。
【請求項１３】
前記類似性グラフネットワークを作成するステップは、前記下位コレクションのそれぞれにおける、下位コレクション間の共通用語の前記出現度数と、前記共通用語間の前記意味関係との積に基づくものであることを特徴とする請求項１記載の方法。
【請求項１４】
前記類似性グラフネットワークを作成するステップは、
共通用語を持たない第１の下位コレクションと第２の下位コレクションが、両方とも、１つまたは複数のリンク下位コレクションと共通の用語を持つかどうか決定するステップと、
最強のリンクを持つ前記リンク下位コレクションを選択するステップと
をさらに具えたことを特徴とする請求項１１記載の方法。
【請求項１５】
前記類似性グラフネットワークを作成するステップは、
第１の下位コレクションと第２の下位コレクションの間の相関関係を決定するステップと、
前記第１の下位コレクションを前記第２の下位コレクションに対して置換するステップと、
各置換ごとのマンテルの検定統計量を計算するステップと、
前記マンテルの検定統計量が、前記第１の下位コレクションと前記第２の下位コレクションの間の前記相関関係以上である回数をカウントするステップと、
前記カウントからｐ値を決定するステップと、
０次の近接性での尺度を計算するステップと、
１次の近接性での尺度を計算するステップと、
【数１】
である類似性尺度ｓ２に基づいて意味関係を決定するステップと
をさらに具えたことを特徴とする請求項１２記載の方法。
【請求項１６】
ユーザからのユーザ問い合わせに応答した情報検索の方法であって、
データオブジェクトの概念的依存関係に基づいて、データオブジェクトのコレクションを、下位コレクション間の関係が類似性グラフネットワークによって表される複数の下位コレクションに区分化するステップと、
前記ユーザ問い合わせに基づいて問い合わせベクトルを生成するステップと、
前記類似性グラフネットワークを使って前記ユーザ問い合わせに応答する可能性の高いすべての下位コレクションを識別するステップと、
識別された各下位コレクションにおいて問い合わせベクトルに類似したデータオブジェクトを識別するステップと
を具えたことを特徴とする方法。
【請求項１７】
前記データオブジェクトのコレクションを区分化するステップは、
前記コレクション中の各データオブジェクトの各用語ごとに度数カウントを生成するステップと、
用語／データオブジェクト情報を使って、前記データオブジェクトのコレクションを、複数の下位コレクションに区分化するステップと、
各下位コレクションごとに用語／データオブジェクト行列を生成するステップと、
前記用語／データオブジェクト行列を、還元された特異値表現に分解するステップと、
各下位コレクションの重心ベクトルを決定するステップと、
各下位コレクションにおいて重心ベクトルに最も近い所定数の用語を見つけるステップと、
下位コレクション間の類似性を確立するために類似性グラフネットワークを作成するステップと
をさらに具えたことを特徴とする請求項１６記載の方法。
【請求項１８】
前記重心ベクトルを決定するステップは、前記下位コレクションの前記用語×データオブジェクト行列の前記還元された特異値表現にクラスタ化アルゴリズムを使用することを特徴とする請求項１７記載の方法。
【請求項１９】
各下位コレクションの重心ベクトルを決定するステップは、前記区分化するステップの結果に基づくものであることを特徴とする請求項１７記載の方法。
【請求項２０】
前記類似性グラフネットワークを作成するステップは、
共通用語を持たない第１の下位コレクションと第２の下位コレクションが、両方とも、１つまたは複数のリンク下位コレクションと共通の用語を持つかどうか決定するステップと、
最強のリンクを持つ前記リンク下位コレクションを選択するステップと
をさらに具えたことを特徴とする請求項１７記載の方法。
【請求項２１】
前記類似性グラフネットワークを作成するステップは、
第１の下位コレクションと第２の下位コレクションの間の相関関係を決定するステップと、
前記第１の下位コレクションを前記第２の下位コレクションに対して置換するステップと、
各置換ごとのマンテルの検定統計量を計算するステップと、
前記マンテルの検定統計量が、前記第１の下位コレクションと前記第２の下位コレクションの間の前記相関関係以上である回数をカウントするステップと、
前記カウントからｐ値を決定するステップと、
０次の近接性での尺度を計算するステップと、
１次の近接性での尺度を計算するステップと、
【数２】
である類似性尺度ｓ２に基づいて意味関係を決定するステップと
をさらに具えたことを特徴とする請求項１７記載の方法。
【請求項２２】
各データオブジェクトごとに前記用語度数カウントを生成する前に、事前選択されたストップワードの集合を除去するために文書を前処理するステップをさらに具えたことを特徴とする請求項１７記載の方法。
【請求項２３】
前記コレクションを区分化するステップは、二分探索ｋ平均クラスタ化アルゴリズムを使って実行されることを特徴とする請求項１６記載の方法。
【請求項２４】
それぞれが前記ユーザ問い合わせに応答するデータオブジェクトを含む可能性に基づいて前記識別された下位コレクションをランク付けするステップと、
前記ランク付けされた下位コレクションのどれに問い合わせるか選択するステップと、
前記ランク付けされた下位コレクションを前記ユーザに提示するステップと、
問い合わせられる前記ランク付けされた下位コレクションのユーザ選択を入力するステップと
をさらに具えたことを特徴とする請求項１６記載の方法。
【請求項２５】
前記ユーザ問い合わせに基づいて問い合わせベクトルを生成するステップは、前記問い合わせ用語を実際に含む別の概念ドメインに類似した１つまたは複数の概念ドメインにおけるその投影された用語ベクトルの加重和を計算することによって前記ユーザ問い合わせを拡張することをさらに具えたことを特徴とする請求項１６記載の方法。
【請求項２６】
前記ユーザに、概念ドメインでランク付けされた前記識別されたデータオブジェクトを提示するステップをさらに具えたことを特徴とする請求項１６記載の方法。
【請求項２７】
ユーザ問い合わせに応答したデータオブジェクトのコレクションからの情報検索のシステムであって、
ユーザ問い合わせを入力する手段と、
前記データオブジェクトのコレクションを格納し、前記データオブジェクトのコレクションを、その内に含まれるデータオブジェクトの概念的依存関係に基づいて複数の下位コレクションに区分化する１つまたは複数のデータサーバと、
（ｉ）前記複数の区分化された下位コレクションの類似性に基づいて類似性グラフネットワークを作成し、（ｉｉ）前記ユーザ問い合わせに基づいて問い合わせベクトルを生成し、（ｉｉｉ）前記類似性グラフネットワークに基づいて前記ユーザ問い合わせに応答する可能性が高い下位コレクションを識別し、（ｉｖ）選択された各下位コレクションにおける問い合わせベクトルに類似したデータオブジェクトの識別を調整するために各データサーバとやりとりするＬＳＩプロセッサハブと
を具えたことを特徴とするシステム。
【請求項２８】
前記識別されたデータオブジェクトを前記ユーザに提示する手段をさらに具えたことを特徴とする請求項２７記載のシステム。
【請求項２９】
情報検索およびデータマイニング操作で使用するためにデータオブジェクトのコレクションを処理するシステムであって、
前記コレクション中の各データオブジェクトの各用語ごとに度数カウントを生成する手段と、
用語／データオブジェクト情報を使って前記データオブジェクトのコレクションを複数の下位コレクションに区分化する手段と、
各下位コレクションごとに用語／データオブジェクト行列を生成する手段と、
前記用語／データオブジェクト行列を還元された特異値表現に分解する手段と、
各下位コレクションの重心ベクトルを決定する手段と、
各下位コレクションにおいて、重心ベクトルに最も近い所定数の用語を見つける手段と、
下位コレクション間の類似性を確立するために類似性グラフネットワークを作成する手段と
を具えたことを特徴とするシステム。
【請求項１】
情報検索およびデータマイニング操作で使用するためにデータオブジェクトのコレクションを処理する方法であって、
前記コレクション中の各データオブジェクトの各用語ごとに度数カウントを生成するステップと、
用語／データオブジェクト情報を使って、前記データオブジェクトのコレクションを、それぞれがその内に含まれる前記データオブジェクトの概念的依存関係に基づくものである、複数の下位コレクションに区分化するステップと、
各下位コレクションごとに用語／データオブジェクト行列を生成するステップと、
前記用語／データオブジェクト行列を縮小された特異値表現に分解するステップと、
各下位コレクションの重心ベクトルを決定するステップと、
各下位コレクションにおいて重心ベクトルに最も近い所定数の用語を見つけるステップと、
下位コレクション間の類似性を確立するために類似性グラフネットワークを作成するステップと
を具えたことを特徴とする方法。
【請求項２】
各データオブジェクトごとに前記用語度数カウントを生成する前に、事前選択されたストップワードの集合を除去するために文書を前処理するステップをさらに具えたことを特徴とする請求項１記載の方法。
【請求項３】
前記前処理するステップは、様々な用語の基準形式への還元をさらに具えたことを特徴とする請求項２記載の方法。
【請求項４】
前記コレクションを区分化するステップは、二分探索ｋ平均クラスタ化アルゴリズムを使って行われることを特徴とする請求項１記載の方法。
【請求項５】
前記コレクションを区分化するステップは、ｋ平均クラスタ化アルゴリズムを使って行われることを特徴とする請求項１記載の方法。
【請求項６】
前記コレクションを区分化するステップは、階層的クラスタ化を使って行われることを特徴とする請求項１に記載の方法。
【請求項７】
前記所定数の用語は１０個であることを特徴とする請求項１に記載の方法。
【請求項８】
各下位コレクションの重心ベクトルを決定するステップは、前記下位コレクションの前記用語／データオブジェクト行列の還元された特異値表現にクラスタ化アルゴリズムを使用することを特徴とする請求項１記載の方法。
【請求項９】
各下位コレクションの重心ベクトルを決定するステップは、前記区分化するステップの結果に基づくものであることを特徴とする請求項１記載の方法。
【請求項１０】
各下位コレクションごとの前記用語／データオブジェクトの前記還元された特異値表現は、おおよそ２００の直交次元を持つことを特徴とする請求項１記載の方法。
【請求項１１】
下位コレクション間の類似性を確立するステップは、下位コレクション間の共通用語の出現度数に基づくものであることを特徴とする請求項１記載の方法。
【請求項１２】
前記類似性グラフネットワークを作成するステップは、前記下位コレクションのそれぞれにおける前記共通用語の間の意味関係に基づくものであることを特徴とする請求項１記載の方法。
【請求項１３】
前記類似性グラフネットワークを作成するステップは、前記下位コレクションのそれぞれにおける、下位コレクション間の共通用語の前記出現度数と、前記共通用語間の前記意味関係との積に基づくものであることを特徴とする請求項１記載の方法。
【請求項１４】
前記類似性グラフネットワークを作成するステップは、
共通用語を持たない第１の下位コレクションと第２の下位コレクションが、両方とも、１つまたは複数のリンク下位コレクションと共通の用語を持つかどうか決定するステップと、
最強のリンクを持つ前記リンク下位コレクションを選択するステップと
をさらに具えたことを特徴とする請求項１１記載の方法。
【請求項１５】
前記類似性グラフネットワークを作成するステップは、
第１の下位コレクションと第２の下位コレクションの間の相関関係を決定するステップと、
前記第１の下位コレクションを前記第２の下位コレクションに対して置換するステップと、
各置換ごとのマンテルの検定統計量を計算するステップと、
前記マンテルの検定統計量が、前記第１の下位コレクションと前記第２の下位コレクションの間の前記相関関係以上である回数をカウントするステップと、
前記カウントからｐ値を決定するステップと、
０次の近接性での尺度を計算するステップと、
１次の近接性での尺度を計算するステップと、
【数１】
である類似性尺度ｓ２に基づいて意味関係を決定するステップと
をさらに具えたことを特徴とする請求項１２記載の方法。
【請求項１６】
ユーザからのユーザ問い合わせに応答した情報検索の方法であって、
データオブジェクトの概念的依存関係に基づいて、データオブジェクトのコレクションを、下位コレクション間の関係が類似性グラフネットワークによって表される複数の下位コレクションに区分化するステップと、
前記ユーザ問い合わせに基づいて問い合わせベクトルを生成するステップと、
前記類似性グラフネットワークを使って前記ユーザ問い合わせに応答する可能性の高いすべての下位コレクションを識別するステップと、
識別された各下位コレクションにおいて問い合わせベクトルに類似したデータオブジェクトを識別するステップと
を具えたことを特徴とする方法。
【請求項１７】
前記データオブジェクトのコレクションを区分化するステップは、
前記コレクション中の各データオブジェクトの各用語ごとに度数カウントを生成するステップと、
用語／データオブジェクト情報を使って、前記データオブジェクトのコレクションを、複数の下位コレクションに区分化するステップと、
各下位コレクションごとに用語／データオブジェクト行列を生成するステップと、
前記用語／データオブジェクト行列を、還元された特異値表現に分解するステップと、
各下位コレクションの重心ベクトルを決定するステップと、
各下位コレクションにおいて重心ベクトルに最も近い所定数の用語を見つけるステップと、
下位コレクション間の類似性を確立するために類似性グラフネットワークを作成するステップと
をさらに具えたことを特徴とする請求項１６記載の方法。
【請求項１８】
前記重心ベクトルを決定するステップは、前記下位コレクションの前記用語×データオブジェクト行列の前記還元された特異値表現にクラスタ化アルゴリズムを使用することを特徴とする請求項１７記載の方法。
【請求項１９】
各下位コレクションの重心ベクトルを決定するステップは、前記区分化するステップの結果に基づくものであることを特徴とする請求項１７記載の方法。
【請求項２０】
前記類似性グラフネットワークを作成するステップは、
共通用語を持たない第１の下位コレクションと第２の下位コレクションが、両方とも、１つまたは複数のリンク下位コレクションと共通の用語を持つかどうか決定するステップと、
最強のリンクを持つ前記リンク下位コレクションを選択するステップと
をさらに具えたことを特徴とする請求項１７記載の方法。
【請求項２１】
前記類似性グラフネットワークを作成するステップは、
第１の下位コレクションと第２の下位コレクションの間の相関関係を決定するステップと、
前記第１の下位コレクションを前記第２の下位コレクションに対して置換するステップと、
各置換ごとのマンテルの検定統計量を計算するステップと、
前記マンテルの検定統計量が、前記第１の下位コレクションと前記第２の下位コレクションの間の前記相関関係以上である回数をカウントするステップと、
前記カウントからｐ値を決定するステップと、
０次の近接性での尺度を計算するステップと、
１次の近接性での尺度を計算するステップと、
【数２】
である類似性尺度ｓ２に基づいて意味関係を決定するステップと
をさらに具えたことを特徴とする請求項１７記載の方法。
【請求項２２】
各データオブジェクトごとに前記用語度数カウントを生成する前に、事前選択されたストップワードの集合を除去するために文書を前処理するステップをさらに具えたことを特徴とする請求項１７記載の方法。
【請求項２３】
前記コレクションを区分化するステップは、二分探索ｋ平均クラスタ化アルゴリズムを使って実行されることを特徴とする請求項１６記載の方法。
【請求項２４】
それぞれが前記ユーザ問い合わせに応答するデータオブジェクトを含む可能性に基づいて前記識別された下位コレクションをランク付けするステップと、
前記ランク付けされた下位コレクションのどれに問い合わせるか選択するステップと、
前記ランク付けされた下位コレクションを前記ユーザに提示するステップと、
問い合わせられる前記ランク付けされた下位コレクションのユーザ選択を入力するステップと
をさらに具えたことを特徴とする請求項１６記載の方法。
【請求項２５】
前記ユーザ問い合わせに基づいて問い合わせベクトルを生成するステップは、前記問い合わせ用語を実際に含む別の概念ドメインに類似した１つまたは複数の概念ドメインにおけるその投影された用語ベクトルの加重和を計算することによって前記ユーザ問い合わせを拡張することをさらに具えたことを特徴とする請求項１６記載の方法。
【請求項２６】
前記ユーザに、概念ドメインでランク付けされた前記識別されたデータオブジェクトを提示するステップをさらに具えたことを特徴とする請求項１６記載の方法。
【請求項２７】
ユーザ問い合わせに応答したデータオブジェクトのコレクションからの情報検索のシステムであって、
ユーザ問い合わせを入力する手段と、
前記データオブジェクトのコレクションを格納し、前記データオブジェクトのコレクションを、その内に含まれるデータオブジェクトの概念的依存関係に基づいて複数の下位コレクションに区分化する１つまたは複数のデータサーバと、
（ｉ）前記複数の区分化された下位コレクションの類似性に基づいて類似性グラフネットワークを作成し、（ｉｉ）前記ユーザ問い合わせに基づいて問い合わせベクトルを生成し、（ｉｉｉ）前記類似性グラフネットワークに基づいて前記ユーザ問い合わせに応答する可能性が高い下位コレクションを識別し、（ｉｖ）選択された各下位コレクションにおける問い合わせベクトルに類似したデータオブジェクトの識別を調整するために各データサーバとやりとりするＬＳＩプロセッサハブと
を具えたことを特徴とするシステム。
【請求項２８】
前記識別されたデータオブジェクトを前記ユーザに提示する手段をさらに具えたことを特徴とする請求項２７記載のシステム。
【請求項２９】
情報検索およびデータマイニング操作で使用するためにデータオブジェクトのコレクションを処理するシステムであって、
前記コレクション中の各データオブジェクトの各用語ごとに度数カウントを生成する手段と、
用語／データオブジェクト情報を使って前記データオブジェクトのコレクションを複数の下位コレクションに区分化する手段と、
各下位コレクションごとに用語／データオブジェクト行列を生成する手段と、
前記用語／データオブジェクト行列を還元された特異値表現に分解する手段と、
各下位コレクションの重心ベクトルを決定する手段と、
各下位コレクションにおいて、重心ベクトルに最も近い所定数の用語を見つける手段と、
下位コレクション間の類似性を確立するために類似性グラフネットワークを作成する手段と
を具えたことを特徴とするシステム。
【図１】
【図２ａ】
【図２ｂ】
【図３】
【図４】
【図２ａ】
【図２ｂ】
【図３】
【図４】
【公表番号】特表２００６−５２５６０２（Ｐ２００６−５２５６０２Ａ）
【公表日】平成１８年１１月９日（２００６．１１．９）
【国際特許分類】
【出願番号】特願２００６−５１３２２８（Ｐ２００６−５１３２２８）
【出願日】平成１６年４月２３日（２００４．４．２３）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１２４６２
【国際公開番号】ＷＯ２００４／１００１３０
【国際公開日】平成１６年１１月１８日（２００４．１１．１８）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
【公表日】平成１８年１１月９日（２００６．１１．９）
【国際特許分類】
【出願日】平成１６年４月２３日（２００４．４．２３）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１２４６２
【国際公開番号】ＷＯ２００４／１００１３０
【国際公開日】平成１６年１１月１８日（２００４．１１．１８）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
[ Back to top ]