(57)【要約】【課題】不均質な情報源からの情報トラッキングのためのシステム、方法およびプログラムを提供すること。【解決手段】情報クラスタリング・システム１００は、ドキュメント間でゆるやかに相関するクラスタを含み、タイムスライスされたドキュメントをドキュメント格納部に蓄積するためのデータ蓄積部１０２と、ドキュメントに存在するキーワードに依存し、疎な数値からなるドキュメント−キーワードベクトルを生成するためのベクトル空間生成部１０４と、キーワードの次元を削減し、ドキュメント−キーワード行列の次元削減行列を生成するための次元削減部１０６と、次元削減行列の同一行内の主要コンポーネントを使用して、検索されたクラスタにわたるドキュメントのキーワードおよび重み付けから規定される重心ベクトルを生成するための重心ベクトル決定部１０８と、重心ベクトルのキーワードおよび重み付けを格納するため項目格納部１１２とを含む。【選択図】図２
2008181205.tif 000002
【特許請求の範囲】
【請求項１】
情報クラスタリングのためのシステムであって、前記システムは、
ドキュメント間でゆるやかに相関するクラスタを含み、前記ドキュメントのチャンクを規定するようにタイムスライスされた前記ドキュメントを、ドキュメント格納部に蓄積するためのデータ蓄積部と、
前記ドキュメントに存在するキーワードに依存し、疎な数値からなるドキュメント−キーワードベクトルを生成するためのベクトル空間生成部と、
前記キーワードの次元を削減し、ドキュメント−キーワード行列の次元削減行列を生成するための次元削減部と、
前記次元削減行列の同一行内の主要コンポーネントを使用して、前記ドキュメント−キーワードベクトルから検索されたクラスタについての、前記クラスタにわたるドキュメントのキーワードおよび重み付けから規定される重心ベクトルを生成するための重心ベクトル決定部と、
前記重心ベクトルを、前記重心ベクトルの前記キーワードおよび重み付けとともに格納するため項目格納部と
を含むシステム。
【請求項２】
前記重心ベクトル決定部は、主要コンポーネントを第１の検索クエリ・ベクトルとして前記ドキュメントのうちの主要ドキュメントを検索し、続いて、前記主要ドキュメントを第２検索クエリ・ベクトルとして使用して、前記クラスタを規定するドキュメントを検索する、請求項１に記載のシステム。
【請求項３】
前記ベクトル空間生成部は、各前記次元削減行列の前記チャンク毎に次元削減を実行し、前記重心ベクトル決定部は、各前記次元削減行列の前記チャンク毎にクラスタ生成を実行する、請求項１に記載のシステム。
【請求項４】
前記システムは、前記チャンクに応じた前記ドキュメントの項目の推移を分析して、情報トラッキングを行うための項目分析部をさらに含む、請求項１に記載のシステム。
【請求項５】
情報クラスタリングのためのコンピュータ実行可能な方法であって、前記方法は、
ドキュメント間でゆるやかに相関するクラスタを含み、前記ドキュメントのチャンクを規定するようにタイムスライスされた前記ドキュメントを、ドキュメント格納部に蓄積するステップと、
前記ドキュメントに存在するキーワードに依存し、疎な数値からなるドキュメント−キーワードベクトルを生成するステップと、
前記キーワードの次元を削減し、ドキュメント−キーワード行列の次元削減行列を生成するステップと、
前記次元削減行列の同一行内の主要コンポーネントを使用して、前記ドキュメント−キーワードベクトルから検索されたクラスタについての、前記クラスタにわたるドキュメントのキーワードおよび重み付けから規定される重心ベクトルを生成するステップと、
前記重心ベクトルを、前記重心ベクトルの前記キーワードおよび重み付けとともに格納するステップと
をコンピュータに実行させる方法。
【請求項６】
主要コンポーネントを第１検索クエリ・ベクトルとして前記ドキュメントのうちの主要ドキュメントを検索するステップと、
続いて、前記主要ドキュメントを第２検索クエリ・ベクトルとして使用して、前記クラスタを規定するドキュメントを検索するステップとをさらに含む、請求項５に記載の方法。
【請求項７】
各前記次元削減行列の前記チャンク毎に次元削減を実行するステップと、
各前記次元削減行列の前記チャンク毎にクラスタ生成を実行するステップとをさらに含む、請求項５に記載の方法。
【請求項８】
前記ドキュメントの前記チャンクに応じた項目の推移を分析し、情報トラッキングを行うステップをさらに含む、請求項５に記載の方法。
【請求項９】
情報トラッキングのためのシステムであって、前記システムは、
ドキュメント間でゆるやかに相関するクラスタを含み、前記ドキュメントのチャンクを規定するようにタイムスライスされた前記ドキュメントを、ドキュメント格納部に蓄積するためのデータ蓄積部と、
前記ドキュメントに存在するキーワードに依存し、疎な数値からなるドキュメント−キーワードベクトルを生成するためのベクトル空間生成部と、
前記キーワードの次元を削減し、ドキュメント−キーワード行列の次元削減行列を生成するための次元削減部と、
前記次元削減行列の同一行内の主要コンポーネントを使用して、前記ドキュメント−キーワードベクトルから検索されたクラスタについての、前記クラスタにわたるドキュメントのキーワードおよび重み付けから規定される重心ベクトルを生成するための重心ベクトル決定部と、
前記チャンクに応じた前記ドキュメントの項目の推移を分析して、情報トラッキングを行うための項目分析部と、
前記重心ベクトルを、前記重心ベクトルの前記キーワードおよび重み付けとともに格納するため項目格納部と
を含むシステム。
【請求項１０】
前記重心ベクトル決定部は、主要コンポーネントを第１の検索クエリ・ベクトルとして前記ドキュメントのうちの主要ドキュメントを検索し、続いて、前記主要ドキュメントを第２検索クエリ・ベクトルとして使用して、前記クラスタを規定するドキュメントを検索する、請求項９に記載のシステム。
【請求項１１】
情報トラッキングのためのコンピュータ実行可能な方法であって、前記方法は、
ドキュメント間でゆるやかに相関するクラスタを含み、前記ドキュメントのチャンクを規定するようにタイムスライスされた前記ドキュメントを、ドキュメント格納部に蓄積するステップと、
前記ドキュメントに存在するキーワードに依存し、疎な数値からなるドキュメント−キーワードベクトルを生成するステップと、
前記キーワードの次元を削減し、ドキュメント−キーワード行列の次元削減行列を生成するステップと、
前記次元削減行列の同一行内の主要コンポーネントを使用して、前記ドキュメント−キーワードベクトルから検索されたクラスタについての、前記クラスタにわたるドキュメントのキーワードおよび重み付けから規定される重心ベクトルを生成するステップと、
前記重心ベクトルを、前記重心ベクトルの前記キーワードおよび重み付けとともに格納するステップと、
前記ドキュメントの前記チャンクに応じた項目の推移を分析し、情報トラッキングを行うステップと
をコンピュータに実行させる方法。
【請求項１２】
主要コンポーネントを第１の検索クエリ・ベクトルとして前記ドキュメントのうちの主要ドキュメントを検索するステップと、
続いて、前記主要ドキュメントを第２検索クエリ・ベクトルとして使用して、前記クラスタを規定するドキュメントを検索するステップと
をさらに含む、請求項１１に記載の方法。
【請求項１３】
請求項５から８のいずれか１項に記載の方法をコンピュータに実行させるコンピュータ実行可能なプログラム。
【請求項１４】
請求項１１から１２のいずれか１項に記載の方法をコンピュータに実行させるコンピュータ実行可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いにゆるやかに相関する種々の表現および用語を含む情報源からの情報トラッキングに関し、より詳細には、互いにゆるやかに相関する種々の表現および用語を含む不均質な情報源からの情報トラッキングのためのシステム、方法およびプログラムに関する。
【背景技術】
【０００２】
データベースの情報検索は、近年、様々な分野で一般に利用されている。このような情報検索技術は、ツリーモデルやベクトル空間モデルなど種々のアルゴリズムを用いて実装することができる。種々の方法の中でも、ベクトル空間モデルは、大規模データベースからの情報検索、情報クラスタリング（情報分類）や情報トラッキング（情報追跡）に対して用いられてきている。
【０００３】
従来、ベクトル空間モデルに依存する情報検索は、通常、厳密に規定されたキーワードおよびドキュメント−キーワードベクトルを生成するための標準フォーマットを伴うドキュメントに対して適用されている。同一の内容または意味を指す異なる複数のキーワードを含むドキュメントに対しては、クラスタ形成に失敗する傾向がある。商用データベースや高性能データベースにおいては、ドキュメントがデータベースに蓄積される際に、適切な規則を用いてキーワードを厳密に決定または選択することができる。しかしながら、チャット、メール、特定の記事に対するフリーポスティングやオンライン・ディスカッションフローを蓄積するデータベースには、意味的、同義的、または多義的なキーワードを使用しながらも、同一記事、トピックス、または項目を示唆するドキュメントまたは情報から構成されがちである。
【０００４】
上述した情報においては、複数のキーワードは、同一項目に関連していながらも相違するので、典型的なクラスタ検索アルゴリズムではクラスタ形成に失敗することが多い。また、上述したような、自由、かつ管理されていないドキュメント群での情報トラッキングでは、時間推移に応じてドキュメントの焦点とされたトピックスや項目を特定する際にも同様の困難性に直面する。
【０００５】
加えて、典型的なベクトル空間モデル・アルゴリズムでは、膨大なＣＰＵ時間やメモリ・リソースなどのハードウェア資源が消費され、時には、次元削減の計算に長時間のＣＰＵ時間が消費される。にもかかわらず、ベクトル空間モデルを基礎としたクラスタ形成では、クラスタ生成のための余分なアルゴリズムが必要とされる。加えて、このようなクラスタ形成では、時間経過に応じて変化し、推移する項目に対しては、充分な妥当性が得られない可能性がある。
【０００６】
不均質な情報源から発生したドキュメントを時間推移に応じて蓄積するデータベースにおいても、ドキュメントが時間に依存して蓄積されるに従い、ドキュメントの中心的な項目や問題を情報検索、検索またはトラッキングすることは、有用であり、かつ必要とされている。上述した情報検索アルゴリズムは、ドキュメントに含まれる項目について、蓄積の時間経過に応じたある種の予測を与えることができる。例えば、このような分析は、株価予測、製品トレンド予測、市場調査、学術研究および特許公報の動向調査、蓄積されたドキュメントおよび集団間を伝達するテキストによって、次段階で中心となるであろう項目を予測するためにも有用である。しかしながら、特にこれらの用途に限定されるものではなく、本発明は、時間経過に応じてゆるやかに相関するドキュメントが蓄積されるような利用分野に対し、広く適用することができる。
【０００７】
本発明の基礎技術をサポートするベクトル空間モデルの詳細なアルゴリズムおよびこれらの特定の実装については、以下の特許文献および非特許文献に総説されている。
【特許文献１】特開２００１−３１２５０５号公報
【特許文献２】特開２００２−０２４２６８号公報
【特許文献３】特開２００２−０３０２２２号公報
【特許文献４】特開２００３−１４１１６０号公報
【非特許文献１】Mei Kobayashi, Masaki Aono and Michael E. Houle, Miningoverlapping major and minor clusters in massive databases, Invited Talk,Industry Day, Special Technologies Workshop #6, organized by Noel Barton,International Conference on Industrial and Applied Mathematics （ICIAM）, Sydney, Australia,2003.
【非特許文献２】Mei Kobayashi and Masaki Aono, Vector space models for search and cluster mining, inMichael Berry （ed.）, Survey of Text Mining: Clustering, Classification, andRetrieval, Springer, New York, USA, 2003, pp. 101−122.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述したように、当該技術分野において、ゆるやかに関連するキーワードを含むドキュメント群において、高い妥当性でクラスタ判定を可能とするシステム、方法およびコンピュータ実行可能プログラムが望まれていた。また、膨大なＣＰＵ時間やメモリ・リソースなどのハードウェア・リソースを消費することなく、このクラスタの計算を可能とし、続いて、商業サーバやハイエンド・マシンなどのハイパフォーマンス・コンピュータにおいて本方法およびプログラムを実装した場合に、効率的かつ実時間程度に高速に項目のトラッキングを計算することを可能とするシステム、そのための方法およびコンピュータ実行可能プログラムを提供することが当該技術分野において望まれていた。
【０００９】
すなわち、本発明の目的は、相互的にゆるやかに相関する種々の表現および用語を含む不均質な情報源から情報検索するためのシステム、方法およびコンピュータ実行可能プログラムを提供することにある。
【００１０】
本発明の他の目的は、データ蓄積の時間経過に応じてデータベースに蓄積されたドキュメントのクラスタにおける中心的な項目をトラッキングするためのシステム、方法およびコンピュータ実行可能プログラムを提供することにある。
【００１１】
本発明のさらに他の目的は、時間推移に応じて、特定のドキュメントのクラスタから得られるキーワード・セットとしての中心的な項目を、有効かつ適切にトラッキングするためのシステム、方法およびコンピュータ実行可能プログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明では、データベースに蓄積されたドキュメントのベクトル空間モデルを用いる。データベースに蓄積されたドキュメントには、複数のドキュメントを含むタイムスライスまたはチャンクが与えられる。このタイムスライスまたはチャンクは、所定の時間間隔毎または所定の蓄積ドキュメント数毎とすることができ、これによりベクトル空間モデルを生成する。
【００１３】
生成されたベクトル空間モデルは、特異値分解を含む次元削減処理が施され、続いて、次元削減されてドキュメント−キーワード行列の主要コンポーネントが得られる。主要コンポーネントは、次元削減行列のドキュメントにわたる行から形成され、特異値分解の結果に対応した順序とされたキーワードを集約する。このため、上述したように形成された主要コンポーネントは、タイムスライス間またはチャンク間のクラスタリングまたはトラッキングを行う場合に、優れた価値をもたらすことになる。
【００１４】
さらにその後、主要コンポーネントのキーワード・セットは、ドキュメント−キーワード行列および次元削減行列の少なくとも一方に対する第１検索クエリ・ベクトルとして用いられる。第１検索クエリ・ベクトルの射影によって、関連ドキュメント、すなわち主要コンポーネントに対する主要ドキュメントが検索される。主要ドキュメントのキーワードは再び、ドキュメント−キーワード行列および次元削減行列の少なくとも一方に対する第２検索クエリ・ベクトルとして用いられ、クラスタの候補となるドキュメントを検索させる。本発明では、特異的な距離を有するドキュメントを、主要ドキュメントとして参照する。また、第１検索クエリ・ベクトルから得られる高いランクの他の主要ドキュメントについても、第２検索クエリ・ベクトルとして用いることができる。
【００１５】
クラスタに含まれるキーワードおよび重み付けは、適切な平均化を施した後に、主要なクラスタの重心ベクトルを規定する。重心は、単純な計算による平均化アルゴリズムまたは移動平均などの他の既知の平均方法を適用し、特定のキーワードおよびコア・ドキュメントに出現するキーワードの重み付けすることにより決定することができる。
【００１６】
各タイムスライスまたは各チャンクの重心ベクトルは、時間経過に伴うクラスタの重心の時間依存推移を得るために計算される。
【００１７】
さらに他の実施形態では、連続するタイムスライスまたはチャンクと同様に、サブチャンクとして参照されるベクトル空間モデルを生成することができる。サブチャンクのドキュメントは、２つの連続するタイムスライスまたはチャンクと重なり合っている。サブチャンクを生成する場合、蓄積されたドキュメント群内で主要項目が急激に変化する場合であっても、追跡またはトラッキングすることが保証できる。
【００１８】
本発明によれば、ゆるやかに関連するドキュメントの情報トラッキングについて、以下に示すように改善することができる：
（１）高速なベクトル空間モデリング、続く主要コンポーネント分析を利用する次元削減を可能とするために、タイム・スタンプに基づいて扱い可能なサイズの重なり合うスライスにデータを縮小する；
（２）主要コンポーネントを検索クエリとして、主要クラスタのドキュメントを特定して、効果的かつ迅速にクラスタの検索を成し遂げる；
（３）ステップ２で検索したドキュメントを用いて、クラスタ内のコア・ドキュメントを見出す。複数のコア・ドキュメントの平均は、クラスタ重心を近似する。重心ベクトルにおけるキーワード重み付けは、クラスタ内のドキュメントにおいて扱われている主要なトピックスを記述する；
（４）重心ベクトルの修正を行うこともできる。この修正は、第１近似値としてクラスタのコア・ドキュメントの平均を採用し、その後、検索されるドキュメント・セットが安定化するか、所定の回数またはシステム終了するまでの間、新規なドキュメント・セットから重心ベクトルに対する改良値を算出させることによっておこなうことができる。
【００１９】
以下、図面に記載した特定の実施形態を参照して、本発明の詳細を説明する。
【発明を実施するための最良の形態】
【００２０】
セクションＩ：コンピュータ・システム
図１を参照して、システム１００の概略機能ブロックを説明する。システム１００は、中央演算ユニット（ＣＰＵ）と、キャッシュやＲＡＭやＲＯＭといったメモリと、ハードディスク・ドライブと、ハードウェア・モジュール間を相互接続するバス・ラインとを含む既存のコンピュータ・アーキテクチャによって構成することができる。システム１００は、ＷＩＮＤＯＷＳ（登録商標）、ＵＮＩＸ（登録商標）またはＬＩＮＵＸ（登録商標）など、周知のオペレーティング・システムによって動作され、Ｃ、Ｃ＋＋、ＪＡＶＡ（登録商標）ＲＵＢＹ、ＰＥＲＬなどのオブジェクト指向プログラミング言語、またはレガシープログラミング言語によって記述されたアプリケーション・プログラムを実行することができる。
【００２１】
システム１００は、データ蓄積部（ＤＡＰ）１０２と、ベクトル空間生成部（ＶＳＧＰ）１０４と、次元削減部（ＤＲＰ）１０６とを含んで構成される。ＤＡＰ１０２は、メーラ、チャット・アプリケーション、特定のサーバに実装されたアクセスログ分析ソフトウェアなど種々のアプリケーション・モジュールによって構成することができ、照会されたドキュメントを検索するためにＤＢ２（登録商標）、ＯＲＡＣＬＥ（登録商標）やＭｙＳＱＬ（登録商標）などのデータベース・ソフトウェアによってサポートされてもよい。
【００２２】
ＤＡＰ１０２は、インターネット、ＬＡＮ（ローカル・エリア・ネットワーク）またはＷＡＮ（ワイド・エリア・ネットワーク）などのネットワーク１２２からの情報を蓄積する。このような情報としては、メール、チャット・メッセージまたはログデータなどのテキスト・ドキュメント、適切なテキストデータを含むマルチメディア・ドキュメント、音声データを含むことができる。この蓄積される情報に音声データが含まれる場合、ベクトル空間モデルを生成するために、ＶＩＡ  ＶＯＩＣＥ（登録商標）のような適切なソフトウェアによって音声データをテキストデータに変換させることができる。
【００２３】
データ蓄積部１０２に蓄積される情報は、一般に、その情報に含まれるキーワードがゆるやかに相関し、健康、お金、食事、環境、ゲームや植物などの中心となる項目に関連しているという性質を有している。この情報は、特定の制約を受けずに生成され、そして、同一項目は、ゆるやかな関連性を有しながらも異なる複数のキーワードによって記述、または表現される可能性がある。
【００２４】
ＤＡＰ１０２は、時間経過に応じて情報をドキュメント格納部１１２に蓄積し、情報に対してタイムスライスまたはチャンクを規定する。本実施形態では、いかなる規則によっても、タイムスライスまたはチャンクを生成することができ、所定の時間スパン毎に生成させることができる。あるいは、所定の情報数毎にタイムスライスまたはチャンクを生成させることもできる。
【００２５】
ＶＳＧＰ１０４は、標準的な教科書（R.K. Belew, ”Finding Out About”, Cambridge Univ. Press, Cambridge, UK, 2001）に詳説されるキーワード抽出および語幹抽出のための標準的な手順によって構成することができる。ＶＳＧＰ１０４は、ＩＢＭ研究所によって開発された、キーワードを抽出し、共通のストップワードを消去し、品詞にタグ付け（ＰＯＳタグ）を行うパーサを含んで実装される。パーサについての詳細は、例えば（Mary S. Neff, Roy J. Byrd and Branimir K. Boguraev, The Talent system: TEXTRACT architecture and data model, Natural Language Engineering, Volume 10, 2004, pp. 307−326）を参照することができる。ＶＳＧＰ１０４は、一語品詞（名詞、動詞、形容詞）を取扱うように実装することができるが、特に限定されるものではなく、その他の規則や実装による実施形態とすることもできる。好適な実施形態では、ＶＳＧＰ１０４において、標準型のＴＦ−ＩＤＦ（term frequency inter document frequency）重み付け、およびその後の正規化（Christopher D. Manning and Hinrich Schuetze, Foundations of Statistical Natural Language Processing, MIT Press, Cambridge, Mass. USA, 1999）を実装することができる。
【００２６】
ＤＲＰ１０６は、特異値分解アルゴリズムを用いて、ドキュメント−キーワード行列の次元削減を実行し、ドキュメント−キーワード行列の次元削減行列を生成する。好適な実施形態では、マサチューセッツ工科大学からのLanczosアルゴリズムを基礎とした数値計算パッケージ（MIT: Doug Rohde, SVDLIBC, version 1.34: http://www.tedlab.mit.edu:16080/~dr/SVDLIBC/）の特異値分解アルゴリズムをドキュメント−キーワード行列の部分特異値分解を計算するために用いる。
【００２７】
結果として取得された次元削減行列は、ハードディスクなどの特定の格納部に格納される。次元削減行列は、それから、特定のタイムスライスまたはチャンクの重心ベクトルを決定するために、重心ベクトル（キーワード・セット）決定部（ＣＶＤＰ）１０８での情報検索に掛けられる。重心ベクトルの決定については、より詳細に後述する。結果として取得された各タイムスライスまたはチャンクおよびサブチャンクの重心ベクトルは、ドキュメントに関連する項目の時間推移をトラッキングするため、項目格納部１１４に格納される。項目分析部１１０は、キーボード１１８またはマウス１２０からの指令に応じて、各タイムスライスまたはチャンク毎の重心ベクトルを検索し、重心ベクトルの分析を行う。項目分析部１１０による分析の結果は、表示画面上に結果を表示させるために、表示装置１１６に伝送される。
【００２８】
セクションＩＩ：クラスタ発見およびトラッキングのアルゴリズム
図２を参照して、処理方法の好適な実施形態を説明する。本処理方法は、ステップＳ２００から開始し、ステップＳ２０１で、情報のタイムスライスまたはチャンクを決定する。ステップＳ２０２では、ベクトル空間モデルおよび次元削減アルゴリズムを使用して、タイムスライスまたはチャンクにおけるクラスタ判定を実行し、重心ベクトルを決定する。次元削減アルゴリズムの適用が好ましい理由としては、ドキュメント−キーワードベクトルが疎な要素を有しているので、マイナー・キーワードの排除は、計算効率を向上させるためである。ここで、重心ベクトルとは、タイムスライスまたはチャンク内のドキュメントにおいて規定された特定のクラスタについてのキーワード−重み付けベクトルを参照する。
【００２９】
ステップＳ２０３では、項目分析部１１０によるトラッキングのために、決定された重心ベクトルを項目格納部１１４に格納する。ステップＳ２０４では、項目格納部１１４から重心ベクトルを検索し、分析の結果を表示装置１１６に表示する。ステップＳ２０５では、処理しなければならない新規のタイムスライスまたはチャンクがあるか否かの判断を行う。新規のタイムスライスまたはチャンクがまだ残っている場合（ｙｅｓ）には、処理をステップＳ２０１へ分岐させて、処理すべきタイムスライスまたはチャンクがなくなるまで、つまり、ドキュメント格納部１１２のタイムスライスまたはチャンクの最後まで、ステップＳ２０２からステップＳ２０５の処理プロセスを繰り返させる。処理すべきタイムスライスまたはチャンクが無いと判定された場合（ｎｏ）には、ステップＳ２０６で処理を終了させる。
【００３０】
図３を参照して、重心ベクトル生成の実施形態の詳細を説明する。図３に示した処理は、ステップＳ３００から開始され、ステップＳ３０１で、現在のタイムスライスまたはチャンク内の所定数のドキュメント数をドキュメント格納部１１２から検索する。ステップＳ３０２では、ＶＳＧＰ１０４によって検索されたドキュメントからベクトル空間モデルが生成され、続いてセクションＩで説明したように、ＤＲＰ１０６により次元削減が実行される。
【００３１】
ステップＳ３０３では、次元削減行列の主要コンポーネントを判定する。ここで主要コンポーネントという用語は、次元削減行列における同一行に記録されたキーワードとして参照し、次元削減行列から主要ドキュメントを検索する際に使用する。タイムスライスまたはチャンクの好ましい実施形態、および本実施形態で規定される主要コンポーネントについては、より詳細に後述する。
【００３２】
ステップＳ３０４では、主要ドキュメントを次元削減行列への第２検索クエリとして用いて、クラスタを判定する：この処理ステップは、次元削減行列の行の主要コンポーネントを含む最も確からしいドキュメントを判定するために、また、主要ドキュメントに関連するクラスタを判定するために必須な処理である。簡単に言えば、クラスタ判定は、ドキュメント−キーワードベクトルの主要ドキュメントからの距離に依存し、クラスタは、特定用途およびドキュメントの特性を考慮して適切な規則またはアルゴリズムによって規定される。
【００３３】
多数のクラスタリング・アルゴリズムが、ランダム化アルゴリズムを採用して、クラスタに対する初期シードとしてのドキュメントを選択するのに対し（例えば、Ｋ−Ｍｅａｎｓアルゴリズムおよび多数提案されたその亜種）、本発明のアルゴリズムの実施形態は、より系統的かつ直接的なアプローチを採用し、当該アプローチでは、主要コンポーネントを検索クエリとして用いる。実際に本発明のシステムは、慣例的な方法よりも好適に類似ドキュメントの探索することができる。最大となる主要コンポーネントがデータベースについての最も多く含まれる情報の方向を与えるという、主要コンポーネント分析の本来的な特性のため、検索されたドキュメントは、主要なトピックスを指し示していることが期待される。また次に大きな主要コンポーネントに対応するベクトルは、データベースに関する２番目に多い情報の方向を示し、それ以後に続く主要コンポーネントについても同様である。
【００３４】
クラスタリング処理のひとつの好適な実施形態では、検索されたドキュメントを、最大の関連度を有するものから最小の関連度を有するものまで並び替える。第１近似のために用いる処理と類似する方法により、重心への改良値を計算する。クラスタについて近似の改良値の決定処理は、
（１）近似のために用いられるドキュメント・セットが固定化する（例えば、変化しなくなる、または設定された閾値を超えるドキュメントの割合が変動しなくなる）；または
（２）２つの連続するイタレーション間で、その値（更新される近似値）が変化しない、または変化しても非常に小さな値εで変化する；
までの間、数回反復を継続させる。
【００３５】
本処理方法では、ステップＳ３０５で、重心ベクトルを決定する。重心ベクトルは、平均的なドキュメント・ベクトルよりも密（非ゼロのエントリを有する）となる傾向がある。そして、結果の品質を損なわずにクラスタ判定の計算速度を高速化するために、より好ましい実施形態では：
第２検索クエリから上位３０の高ランク・ドキュメントのみを使用する；３０ドキュメント・ベクトルのコンポーネントについての平均（component−wise average）を計算する；すべてのワードのうち所定の閾値（例えば５％）以下のキーワードの重み付けをゼロにする：ワードを、最高値の重み付けから最低値の重み付けを有するものに並べ替える：各ワードについて、その重み付けを時間の関数でプロットし、第２検索クエリからのドキュメント・ランキングの傾きが３０ドキュメントとなる前に急激に変化する場合には、この変化以前のドキュメントのみをコンポーネント平均の計算のため使用する。
【００３６】
さらに、ステップＳ３０６では、重心ベクトルまたは異なる主要ドキュメントについての複数の重心ベクトルを、タイムスライスまたはチャンクの識別値とともに項目格納部１１４へ格納する。本方法では、さらにステップＳ３０７で、データベース内のすべてのドキュメント、つまりタイムスライスまたはチャンクに対して処理が行われたか否かの判定を行う。ステップＳ３０７の判定で、タイムスライスまたはチャンクがまだ残っていると判定される場合（ｎｏ）には、処理をステップＳ３０１に分岐させ、上記処理を繰り返させる。残っているタイムスライスまたはチャンクがない場合（ｙｅｓ）には、処理をステップＳ３０８へ進め、処理の実行を終了させる。
【００３７】
図３に示した実施形態は、ドキュメントをすでに蓄積し、同時に、ドキュメントに対してタイムスライスまたはチャンクを規定するようにドキュメントがタイムスタンプを含んでいる静的なデータベースに対して適用することができる。図４に示した実施形態では、ベクトル空間モデルの生成から項目格納部への格納するまでの処理と平行して、ドキュメントを蓄積する。図４に示した処理は、デーモン・プロセスまたはサービス・プロセスとして実装することができ、システムのシャットダウンやシステム終了によって完了させることができる。図４に示した方法は、ステップＳ４００で開始される。ステップＳ４０１では、ＶＳＧＰ１０４によって、ドキュメント・データベース内のドキュメントが次のタイムスライスまたはチャンクを規定できる程度に充分に蓄積されたか否かが判定される。ＶＳＧＰ１０４が、例えば、ＤＡＰ１０２からのプロセス間通信を通じて、新規なタイムスライスまたはチャンクの準備ができたと判定した場合、ＶＳＧＰ１０４は、処理するためのタイムスライスまたはチャンクに対する新規ベクトル空間モデルを生成する。そして処理は、ステップＳ４０２からステップＳ４０７までのステップを進め、図３に示した制御と同様の処理を実行する。図４に示した実施形態では、ステップＳ４０１において、新規タイムスライスまたはチャンクの準備が完了した旨の肯定的なアクノレッジメントをＶＳＧＰ１０４が受信するまで、ＤＡＰ１０２からのアクノレッジメントを定期的にモニタする。ステップＳ４０２からステップＳ４０７の処理は、図３に示した処理とほぼ同一の処理であるため、より詳細な説明については、ここでは省略する。
【００３８】
セクションＩＩＩ：情報処理の詳細な説明
図５は、本発明で導入されるタイムスライスまたはチャンクのデータ構造を示す。ドキュメント・データベースに格納されるドキュメントは、ＤＡＰ１０２によって受領されるタイムスタンプとともに記録され、タイムスライスまたはチャンクが規定される。他の実施形態では、タイムスタンプなしにドキュメントを格納し、所定数のドキュメントが蓄積される毎に、ドキュメント数が所定数に達した時のタイムスタンプとともにタイムスライスまたはチャンクを規定することができる。しかしながら、本発明では、特にこれに限定されるものではなく、その他、如何なるタイムスライスまたはチャンクの作成方法を採用することができる。
【００３９】
図５においては、ドキュメント群はチャンクに分割され、各チャンク５００−１〜５００−３は、同一数のドキュメントを含んでいる。図５に示した実施形態では、それぞれのチャンクに対する時間間隔は相違する可能性がある。これは、ＤＡＰ１０２によって情報が蓄積されている場合に好ましい実施形態である。チャンクに含まれるドキュメント数は、チャンク間で同一または相違させることができる：しかしながら、次元削減の統計的な信頼性を保証するために、チャンクが同一数ｍのドキュメントを含むようにすることができる。所定ドキュメント数を用いる場合の実施形態では、最後のチャンク５００−３には、ドキュメント・データベース内の総ドキュメント数に依存して、他のチャンクよりも少ない、または多いドキュメントを含ませることができる。
【００４０】
好適な実施形態では、さらに、サブチャンク５００−４、５００−５、５００−６を規定する。サブチャンク５００−４、５００−５および５００−６は、連続するチャンク５００−１、５００−２、５００−３のトラッキングを補助させるために用いられ、５００−１および５００−２といった隣接するチャンク内の両方のドキュメントを有するように規定される。隣接するチャンク間で特定のキーワードが消失した場合であっても、サブチャンクを使用して、隣接するチャンクのトラッキングを可能とすることができる。データベースにおいて連続して規定される前方チャンクと後方チャンクとの半分づつのドキュメントを共有するように、サブチャンクを形成することができる。
【００４１】
本発明の好適な実施形態では、次元削減は、小さなサイズのドキュメント−キーワード空間において実行され、ドキュメント格納部１１２の項目の推移を追跡することを可能としながらも、次元の呪い（curse of dimension）を引起こさずに、迅速かつ効率的に次元削減を実行する。
【００４２】
項目のトラッキングを対象とすると、サブチャンクとして参照される重なり合うタイムスライスまたはチャンクを使用することによって、簡単なトラッキング方法を提供することができる。ここで、Ｗ１を第１チャンク（または一時ウィンドウ）とし、Ｗ２を第２チャンク、Ｗiを第i番目のチャンク（または一時ウィンドウ）とする（ここで、ｉは正の整数を表す）。検索されるトピックスについて、ウィンドウＷ１およびＷ２内の関連するドキュメントは、重み付けは異なるにせよ、依然として主題となる項目として維持されている。ドキュメントは、投稿や蓄積の順序に従って番号付けされているので、図５に示されるように、Ｗ２内の類似するドキュメントを検索するためのシード（つまり、クエリ）として用いられるドキュメントをチェックすればよい。トピックスが継続してドキュメントについての活発な項目であった場合には、Ｗ２の後半期間に投稿されたドキュメント・セットの検索は、空ではないセットが抽出される。
【００４３】
Ｗ１からＷ２への項目の微小な変化を追跡するために、項目に関するＷ２内のドキュメント・セットを、シード・ベクトルの移動平均を計算することにより、重心ベクトルの近似値を計算するために使用する。本実施形態のベクトル平均は、重心ベクトルの推移を記述することができる。より高度な用途では、上記重心を、検索クエリ・ベクトルとしての重心ベクトルの第１近似値として設定し、関連ドキュメントのセットを検索させ、また重心近似値の改良値を計算させることができる。タイムスライスまたはチャンクＷｉからＷｉ＋１までの特定の項目に関するドキュメント・セットを追跡するために、また重心の近似値を追跡するために、残されたタイムスライスまたはチャンクに対しても類似の手順を適用することができる。
【００４４】
図６は、（ａ）ドキュメント−キーワードベクトルの実施形態および（ｂ）ドキュメント−キーワードベクトル間の距離の定義の実施形態を示す。図６を参照すると、ドキュメント内のキーワードがキーワード毎にカウントされて、ドキュメント−キーワードベクトル６０２として示される、重み付け−キーワードの整数値が与えられる。次のステップでは、ドキュメント−キーワードベクトル６０２に対してＴｆ−ｉｄ処理が施され、ドキュメント−キーワードベクトル６０４として示されるように、上述したアルゴリズムが用いられて各キーワードの重み付けが変更され、次に、ドキュメント−キーワードベクトル６０６として示されるように、変更された重み付けがベクトルのノルムが１となるように正規化される。
【００４５】
次に、ドキュメント−キーワードベクトルＸとＹとの距離は、図６（ｂ）に示すように、ドキュメント−キーワードベクトルＸとＹの内積として定義される：ここで｜Ｘ｜は、ベクトルＸのノルムであり、｜Ｙ｜は、ベクトルＹのノルムであり、これらのベクトルは、｜Ｘ｜＝｜Ｙ｜＝１となるように正規化されている。Θは、ベクトル間の角度を表し、ｘｉとｙｉは、それぞれ各ベクトルＸおよびＹの要素であり、i=1からｎまでのｎ要素からなる。
【００４６】
図７は、次元削減行列７００の主要コンポーネントの判定処理を示す。図７（ａ）は、次元削減行列７００の典型的な実施形態を示し、図７（ｂ）は、主要コンポーネントの典型的な実施形態を示す。次元削減行列７００は、一連のドキュメントについて、図６（ａ）に示すドキュメント−キーワードベクトルを列として構成するドキュメント−キーワード行列から計算される。ドキュメント−キーワードベクトル内の典型的なキーワード数は、数千以上とすることができる。キーワードの次元は、上述の方法を経て特異値分解により５００キーワード程度まで削減され、本実施形態の次元削減行列７００が得られる。
【００４７】
主要コンポーネントは、次元削減行列７００の行として定義され、主要コンポーネントは、図７（ａ）の次元削減を経て残されたキーワードの順序に応じて、第１主要コンポーネント、第２主要コンポーネント・・・第ｎ主要コンポーネントとして識別される。次元削減を経た後のキーワードの順序は、ドキュメント−キーワード行列におけるもとの順序と同一の配列とすることができるが、より好ましい実施形態では、代わりに、キーワードを特異値に応じて降順により再配列させることができる。特異値に応じてキーワードの順序を配列させた場合には、主要コンポーネントは、直ちにドキュメントにおける主要なキーワードを指し示し、ドキュメント内の主要な項目に対する良い関連性を与える。
【００４８】
図７（ｂ）を参照すると、第１主要コンポーネント７０２は、トップ・キーワードを一行に含み構成され、第２主要コンポーネント７０４が第二行目のコンポーネントを、第ｎ主要コンポーネント７０６がｎ行目のコンポーネントを含み構成される。本発明では、各主要コンポーネントを、最も関連度のあるドキュメント（また他の高ランクのドキュメント）を判定するための第１検索クエリとして使用することができる。以下、この高い関連度を有するドキュメントを主要ドキュメントとして参照する。
【００４９】
図８は、主要コンポーネントの詳細を示す。図８（ａ）に示された実施形態は、第２主要コンポーネント７０４に対応するものであり、ドキュメントのチャンクに対応する8,000のキーワード要素を含み構成されている。図８（ｂ）は、第２主要コンポーネントに含まれる「energy」、「solar」などのキーワード７０８を例示する。各キーワードに対する数値は、対応するキーワードについて正規化された重み付けである。主要コンポーネントは、主要コンポーネントに対して最も関連度のあるドキュメントを判定するための第１検索クエリとして用いられる。本実施形態では、クエリ処理は、主要コンポーネントと次元削減行列との距離の計算と、主要ドキュメント（または他の高ランクのドキュメント）の抽出とを含んでいる。他の実施形態では、検索クエリを元のドキュメント−キーワード行列に対しても適用することもできる。
【００５０】
図９は、第１検索クエリによる結果を示す。リスト９００として示すように、関連度を有するドキュメントがドキュメント群から抽出され、コンピュータシステムの適切なメモリ領域に一時的に格納される。リスト９００は、図８に示す検索クエリによって抽出された複数のドキュメントを含み構成され、フィールド９０２にエントリされている主要コンポーネントとの距離に対して、降順にドキュメントを格納している。第１検索クエリは、チャンクに含まれるドキュメントにわたって選択された主要コンポーネントなので、フィールド９０２に入力された距離は、このステップにおいては相対的に小さな値となる。リスト９００は、さらにフィールド９０４を含み、このフィールドには、ドキュメント番号のようなドキュメント識別値が記録される。ドキュメントがデータベースに格納された場合に、このドキュメント番号を付与するようにすることができ、または、特定の実装アーキテクチャに依存して、他の識別値を付与するようにすることもできる。リスト９００は、またフィールド９０６を含み、フィールド９０６には、ドキュメントの索引のためのドキュメント・タイトルが登録される。
【００５１】
図９に示した特定の実施形態によれば、第２検索クエリ・ベクトルは、最も関連度を有するドキュメント９０８（ドキュメント［＃ＩＤ：２１４１］に対応する）としている。第２検索クエリは、再び次元削減行列へ射影され、クラスタおよびクラスタ重心が決定される。第２検索クエリが次元削減行列に射影された場合、第２検索クエリ・ベクトルがクラスタ内の重要なキーワードを含んでいるため、関連するドキュメントとの距離がより大きな値となる。
【００５２】
図１０は、検索クエリの結果の実施形態を示す。図１０（ａ）は、チャンク全体にわたる結果を示し、図１０（ｂ）は、第２検索クエリ（これは主要コンポーネントのキーワード）に対して高い関連度を有する側の部分の結果の詳細を示す。図１０に示すように、縦軸で距離から得られる関連度を表し、横軸でドキュメント番号を表す。図１０（ａ）に示すように、ゼロで示される検索クエリのドキュメントから、8,000で示される最後のドキュメントまで、関連度が急速に減少する。この急速な減少により、クラスタ・サイズを示すことができる。図１０（ｂ）は、長方形１０００によって示された部分の関連度の減少挙動の拡大図を示す。関連度の減少の拡大図から、関連度が階段状に減少していることが示され、関連度での水平スライスに対応させて、クラスタの境界を示すことができる。
【００５３】
すなわち、これらの水平スライスで示された関連度のレベルによってクラスタを規定することができる。低いスライスのレベルを採用する場合には、より関連度の小さなドキュメントがクラスタに組入れられることとなり、高いスライスのレベルが採用される場合には、少数のドキュメントを含むクラスタとなる。そして、いくつかのクラスタ判定の基準があり、説明している実施形態では、いくつかの手法を採用することができる。クラスタの識別処理およびクラスタの近似処理を自動化するために、第１の方法では、図１０に示したグラフと類似するように、左から右へ最も関連度の高いものから少ないものへ整列させたグラフを用意する。
【００５４】
その後、関連するドキュメント内のキーワードおよび重み付けの平均を、クラスタの重心ベクトルの近似値を計算するために使用する。図１０に示した実施形態においては、例えば３０ドキュメントをクラスタとして考慮することができる。しかしながら、これに特に限定されるものではなく、本発明では、特定の用途および関連度の変化の特性に依存して、他の規則を採用することもできる。例えば、ドキュメント−関連度のプロットの傾きが３０ドキュメント前に急激に変化した場合（図１０（ｂ）に示したように）、最初の急激なスロープの変化前のドキュメントのみをクラスタ判定および重心ベクトルの計算に用いることができる。さらに他の実施形態では、単に例えば図１０（ｂ）で０．３といった関連度のレベルによって、または高い関連度のものからの所定ドキュメント数によって、決定することもできる。
【００５５】
図１１は、（次元削減された）ドキュメント−キーワード空間１１００内のクラスタおよび重心ベクトルの要素の概略図を示す。クラスタ１１０２−１１０６は、図１０に示した手順に従って、図１１（ａ）において●で示された異なる主要ドキュメントに対して、それぞれ規定される。ここで、クラスタ１１０６の重心ベクトル１１０８の要素１１１０を、これらの重み付けとともに図１１（ｂ）に示す。クラスタは、各主要ドキュメント毎、各タイムスライスまたはチャンク毎に判定され、つまり重心ベクトルは、図１２に示すリスト１２００のように各チャンク毎に格納することができる。図１２に示した実施形態には、第２主要ドキュメントに対応するクラスタの重心ベクトルが示されている。しかしながら、他の実施形態では、各クラスタについて、より多くの対応する重心ベクトルを含むことができる。リスト１２００は、ＣＶＳ形式やカンマ−スペース、またはコンピュータシステムの他アプリケーション形式のような適切なフォーマットで、項目分析部１１０における分析のために、項目格納部１１４のようなメモリ領域に格納される。
【００５６】
ＧＵＩ（グラフィカル・ユーザ・インタフェース）および結果のプロット表示のための手段としては、商業的に利用可能か種々のデータベース・アプリケーションや表計算アプリケーションを採用することができ、ここでは特に詳細を説明しない。
【００５７】
以上説明した実施形態の種々のバリエーションが考えられる。このようなバリエーションは、特に限定されるものではないが、例えば以下に示すようなものがある。
（１）チャンクのサイズ（例えば、より小さなものや、より大きなものや、不定サイズのもの）
（２）チャンクの重なりを拡大したもの（５０％よりも多くまたは少なくしたもの、不定サイズの重なりを有するもの）
（３）チャンク化するための代替基準（例えば、投稿期間の一時ウィンドウや発送元の国によるもの）
【００５８】
セクションＩＶ：実験
（ＩＶ−１）コンピュータにおける実装
クロック数１．５ＧＨｚのＰＥＮＴＩＵＭ（登録商標）Ｍプロセッサと１ＧＢのＲＡＭを備えるＴｈｉｎｋＰａｄ（登録商標）Ｔ４０を用いて、本発明のプログラムを実装するコンピュータ・システムを実装した。このコンピュータ・システムのオペレーティング・システムは、ＷＩＮＤＯＷＳ（登録商標）ＸＰとした。上記プログラムは、ＪＡＶＡ（登録商標）によって記述した。上記実装において、全ドキュメントに対する計算は、３０分間以内に完了した。
【００５９】
（ＩＶ−２）データベースの準備
２００６年ＩＢＭイノベーションＪＡＭ（Ｉ−Ｊａｍ）の第１フェーズにおいて、本発明のテキストデータを取扱ったクラスタおよび項目フローの特定およびトラッキング方法を検証するためのデータベースを生成した。データには、７８時間（２００６年７月２４日ＡＭ７：００（ＥＳＴ）から２００６年７月２７日ＡＭ１１：００（ＥＳＴ））にわたって、全世界の5,3000以上の参加者による37,037のポスティング（メール）が含まれていた。各ドキュメントは、ＩＢＭ研究所の社員またはその家族または６７の選択された外部機関によって入力された、自由な意見を表したものである。２００から３００の投稿された意見が英語以外の言語によるものであった。本分析においては、英語以外の言語によるポスティングの内容については省略した。
【００６０】
参加者は、以下に示す４つのカテゴリ：
１．Going Place（移動をもっと便利に）−旅行、交通、レクリエーション、エンターテインメントの変革；
２．Finance & Commerce（ファイナンスと商取引）−世界のビジネスと商取引の性質の変化；
３．Staying Healthy（健康・安全の維持）−健康のための科学とビジネス；
４．A Better Planet（よりよい地球）−経済と環境の優先順位のバランス；
についてポスティングを投稿するように要請された。
【００６１】
ポスティングのタイムスタンプに従って、ドキュメントを古いものから新しいものの順に格納した。データ・セットを、8,000の連続するドキュメント・ポスティングのタイムスライスにチャンクした。本実装においては、各タイムスライスが前方タイムスライスと4,000の重なり合うドキュメントを有するように、サブチャンクを規定した（従って4,000ドキュメントが連続するタイムスライスにおいて重なり合う）。
【００６２】
サンプル・データベースのベクトル空間モデルを構築するために、Ｉ−Ｊａｍのデータ・セットの各8,000ドキュメントを、標準的な教科書（例えば、Belew （op.cit.））に詳述されるキーワード抽出および語幹抽出の標準的な手順、より具体的には、ＩＢＭ研究所において開発されたTalent（Neff et al. （op. cit.））によってタイムスライスとしてチャンクした。なお、Talentは、キーワード抽出、共通のストップワードを消去し、品詞にタグ付け（ＰＯＳタグ）を行うパーサである。キーワードについては、一語品詞（名詞、動詞および形容詞）のみを考慮した。キーワード・セットについては、抽出されたキーワードがZipfian分布に従うことを確認した。次に、キーワードセットから、希少なキーワードおよび過剰頻度のキーワードを省略した。本実装においては、下限カットオフ点を１０ドキュメント以下（下限として）とし、（上限については）Zipfian両対数曲線の形状に依存して５−７％以上のドキュメントをカットオフを行った。標準型のｔｆｉｄｆ（Term frequency inter document frequency）重み付け、続く正規化（Manning and Schuetze (op.cit.））を適用した。ベクトル空間モデリングからの典型的な結果では、8,000ドキュメントを含むタイムスライスからの3,136キーワードが抽出され、１％−２％の密度を有する8,000×3,136のドキュメント−属性行列が得られた。
【００６３】
結果を検証するために、２つのトライアル・セットを選択した。ひとつは、「食事と健康」についての記事を扱うドキュメント・セットであり、他方は、「お金とセキュリティ」の記事を扱うドキュメント・セットである。第２タイムスライスでトピックスがどのように推移したかを追跡するために、第１タイムスライスまたはチャンクと第２タイムスライスまたはチャンクとの間で重なり合うドキュメントを使用した。最後のタイムスライスまたはチャンクを除いて、それぞれ8,000ドキュメントを含む１０のタイムスライスまたはチャンクに分割した。
【００６４】
Ｉ−Ｊａｍデータの１０タイムスライスから、重心ベクトルにある１２の顕著な項目（キーワード）：第１トライアル・セットの「junk」、「vegetable」、「cancer」、「diet」、「eat」、「calorie」、「healthy」、「cook」、「exercise」、「fat」、「nutritional」および「price」と、第２トライアル・セットの比較的高い重み付けの４つのキーワードの「cash」、「payment」、「security」、「signature」について考察した。トラッキングを検証した後、ドキュメントの原文（つまり、Ｉ−Ｊａｍポスティング）を参照し、キーワードの重み付けのシフトが実際にドキュメントにおける議論の変化に対応しているのか否かを確認した。
【００６５】
（ＩＶ−３）結果
図１３から図１５は、その結果を示し、図１３は、「食事と健康」についてのクラスタおよび全項目のトラッキングの結果を示し、図１４は、「食事と健康」についての結果のうち、項目（「eat」、「healthy」、「exercise」）のトラッキングの詳細な結果を示し、図１５は、「お金とセキュリティ」についてのクラスタの結果を示し、トラッキングでは、項目（「cash」、「payment」、「security」、「signature」）について焦点を当てた。ただし、図１５は、ポスティングの本文についても表示する。
【００６６】
図１３に示されるように、「食事と健康」についてのクラスタは、「junk」、「vegetable」、「cancer」などの顕著な１２項目を含んで構成されている。第１チャンクと第１０チャンクの間において、項目の時間に依存した明瞭な変化が示されている。それから、独立して項目（「eat」、「healthy」、「exercise」）を選択し、項目間の相互的な関連性を調査した。図１４は、その結果を示し、明瞭な関連性が認められた。つまり、「食事と健康」について投稿するユーザは、「exercise」より、むしろ「healthy」および「food」に強く興味を示し、項目（「healthy」、「exercise」）がポスティングにおける主要な関心事となっているとき、項目「eat」が反対の動向を示した。
【００６７】
図１５は、さらに別の結果を示し、項目（「cash」、「payment」、「security」、「signature」）を含むクラスタについての結果を示す。図１５に示された各ピークに対して、代表的なポスティングを共に図示する。項目（「security」および「payment」）が最初にピークを示し、そして第５チャンクにおいて、項目（「security」および「payment」）がマイナー項目となっている間に項目「signature」がさらに別のピークを示した。これは、項目（「payment」および「cash」）が、項目「signature」についてのポスティングまたは意見を誘発しているものと考えられる。それから、ポスティングの主要項目については、ポスティングが項目（「payment」、「cash」、「security」）を含むものへ推移したことを示している。
【００６８】
以上説明したように、本発明が、ゆるやかに関連し、様式への特定の規則を伴わずに蓄積されたドキュメントの情報検索を、効率的かつ高パフォーマンスなものに改良できることが理解されるであろう。本システム、方法およびプログラムは、リアルタイムまたは静的にデータベースに蓄積、格納されるドキュメントの迅速な意味解析を可能としている。
【００６９】
以上、本発明を図面に示した実施形態および実施例をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、他の実施形態、変更、本質的ではない事項の省略など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【図面の簡単な説明】
【００７０】
【図１】システム１００の機能ブロックを示す概略図。
【図２】処理方法の好適な実施形態を示した図。
【図３】重心ベクトルの生成について詳細な実施形態を示した図。
【図４】処理方法の好適な実施形態を示した図。
【図５】本発明で導入されるタイムスライスまたはチャンクのデータ構造を示した図。
【図６】（ａ）ドキュメント−キーワードベクトルの実施形態、および（ｂ）ドキュメント−キーワードベクトル間の距離の定義の実施形態を示した図。
【図７】次元削減行列７００における主要コンポーネントを判定するための処理を示した図。
【図８】主要コンポーネントの実施形態の詳細を示した図。
【図９】第１検索クエリによる結果を示した図。
【図１０】検索クエリによる結果の実施形態を示した図。
【図１１】（次元削減された）ドキュメント−キーワード空間におけるクラスタ、および重心ベクトルの要素を示した概略図。
【図１２】リスト１２００として各チャンク毎に格納することができる重心ベクトルを示した図。
【図１３】「食事と健康」についてのクラスタおよび全項目のトラッキングの結果を示した図。
【図１４】項目（「eat」、「healthy」、「exercise」）についてのトラッキングの詳細な結果を示した図。
【図１５】項目（「cash」、「payment」、「security」、「signature」）を含むクラスタについてのさらに別の結果を示した図。
【符号の説明】
【００７１】
１００…コンピュータ・システム、１０２…データ蓄積部、１０４…ベクトル空間生成部、１０６…次元削減部、１０８…重心ベクトル決定部、１１０…項目分析部、１１２…ドキュメント格納部、１１４…項目格納部、１１６…表示装置、１１８…キーボード、１２０…マウス、１２２…ネットワーク、５００…タイムスライスまたはチャンク、６００…ドキュメント−キーワードベクトル、７００…次元削減行列、７０２〜７０６…主要コンポーネント、９００…リスト、１１００…ドキュメント−キーワード空間、１１０２〜１１０６…クラスタ、１１０８…重心ベクトル、１１１０…重心ベクトルの要素、１２００…リスト
【図１】
2008181205.tif 000003
【図２】
2008181205.tif 000004
【図３】
2008181205.tif 000005
【図４】
2008181205.tif 000006
【図５】
2008181205.tif 000007
【図６】
2008181205.tif 000008
【図７】
2008181205.tif 000009
【図８】
2008181205.tif 000010
【図９】
2008181205.tif 000011
【図１０】
2008181205.tif 000012
【図１１】
2008181205.tif 000013
【図１２】
2008181205.tif 000014
【図１３】
2008181205.tif 000015
【図１４】
2008181205.tif 000016
【図１５】
2008181205.tif 000017
【外国語明細書】
【Title of Invention】
System, method and computer executable program for information tracking from heterogeneous sources
【Technical Field】
【０００１】
The present invention relates to information tracking from a data source comprising various expressions and terms being loosely related each other, and more particularly, the present invention relates to a system, a method and a program for information tracking from heterogeneous sources comprising various expressions and terms being loosely related each other.
【Background Art】
【０００２】
Recently, information retrieval of a database is popularly used in various fields.  Such information retrieval technique may be implemented using various algorithms such as a tree model or vector space model, etc.  Among various methods, the vector space model has been used for retrieving, clustering and tracking the information from very large database.
【０００３】
Conventionally, the information retrieval depend on the vector space model usually applied to document with rigidly determined keywords and with a standard format for generating keyword-document vectors; the documents including different keywords which refers the same contents or semantics tend to fail in forming clusters.  In the commercial database or sophisticated databases, keywords may be rigidly determined or selected using proper rules when the documents are accumulated in the database; however, the database accumulating chat, mail, free posting for particular issues, or on-line discussion flow may comprise documents or information with likely or different keywords while the keyword sets suggest the same issues, topics, or items by using semantics, synonymy, or polysemy of the keywords.
【０００４】
In such information, typical cluster search algorithms almost fail in the formation of clusters because the keywords are different while the keywords relate to the same items.  Also, information tracking in such loosely and uncontrolled documents suffers similar difficulty in identifying focused topics or items with respect to time evolution of the documents.
【０００５】
In addition, typical vector space model algorithms consume huge hardware resources such as CPU time and memory resources, and sometimes the computation of the dimension reduction consume long CPU time.  Even though, the cluster formation based on the vector space model further requires extra algorithms for generating clusters.  In addition, such cluster formation may not have sufficient relevancy to the items that change or evolve with respect to the time elapse.
【０００６】
Even in the database to which documents are accumulated with respect to the time evolution and the documents are originates from heterogeneous sources, it is also useful and necessary to retrieve, search, or track focused items or matters of the documents with respect to the time dependent accumulation of the documents.  Such information retrieval algorithm will provide some predictions of items included in the documents with respect to the time elapse of the accumulation.  For example, such analysis may be useful to predict stock price prediction, product-trend prediction, market research, trend search of academic or patent publication or item prediction which will be focused in the next stage depending on the accumulated document and/or text transmitted between some parties, but not limited thereto, the present invention may be widely applied to the field in which loosely related documents are accumulated with respect to the time elapse.
【０００７】
Detailed algorithms of the vector space model and their particular implementation, which supports basis technologies of the present invention, are reviewed in the following patent and non-patent literatures.
[Patent Literature 1] JP2001-312505
[Patent Literature 2] JP2002-024268
[Patent Literature 3] JP2002-030222
[Patent Literature 4] JP2003-141160
[NON-Patent Literature 1] Mei Kobayashi, Masaki Aono and Michael E. Houle, Mining overlapping major and minor clusters in massive databases, Invited Talk, Industry Day, Special Technologies Workshop #6, organized by Noel Barton, International Conference on Industrial and Applied Mathematics (ICIAM), Sydney, Australia, 2003.
[NON-Patent Literature 2] Mei Kobayashi and Masaki Aono, Vector space models for search and cluster mining, in Michael Berry (ed.), Survey of Text Mining: Clustering, Classification, and Retrieval, Springer, New York, USA, 2003, pp. 101-122.
【Disclosure of Invention】
【Problem to be Solved by Invention】
【０００８】
As described above, a system, a method and a computer executable program, which are able to determine clusters in the documents having loosely related keywords with high relevancy, are yet expected in the art.  Also it is expected in the art to provide a system, a method, and a computer executable program which are capable of computing such clusters without consuming huge hardware resources such as CPU time and memory resources; such system, in turn, makes the computation of the item tracking efficiently and high speed as fast as real time when the method and the program are implemented in a high performance computer such as commercial servers or high end machines.
【０００９】
Then, the object of the present invention is to provide a system, method, and a computer executable program for retrieving information from heterogeneous sources comprising various expressions and terms being loosely related to each other.
【００１０】
Another object of the present invention is to provide a system, method, and a computer executable program for tracking focused items in clusters of documents which are accumulated in a database with respect to time elapse of data accumulation.
【００１１】
Further another object of the present invention is to provide a system, method, and a computer executable program for tracking effectively and relevantly focused items as keyword sets derived from a particular cluster of documents with respect to the time evolution.
【Means for Solving Problem】
【００１２】
In order to address to the above object, the present invention uses vector space modeling of the documents accumulated in a database.  The documents accumulated in the database are provided with time slices or chunks containing plural documents.  Such time slices or chunk may be done per a predetermined time duration or per accumulation of predetermined numbers of the documents to generate the vector space model.
【００１３】
The generated vector space models are subjected to dimension reduction process including singular value decomposition and are subsequently subjected to the dimension reduction so as to obtain a principal component of the document-keyword matrix.  The principal component is formed from a line of the dimension reduction matrix across the documents and resumes keywords having the same order with respect to results of the singular value decomposition.  Then, so formed principal components provide excellent values in clustering and/or tracking between the time slices and/or chunks.
【００１４】
Further next, the keyword set in the principal component is used as a first query vector to the document-keyword matrix and/or dimension reduction matrix.  The projection of the first query retrieves a relevant document, i.e., a principal document to the principal component.  Keywords in the principal document again used as a second query to the document-keyword matrix and/or dimension reduction matrix to retrieve documents for candidates for a cluster; the document having the most significant distance is referred herein as a principal document.  Also any other high-ranking principal document from the first query may be used as a second query. 
【００１５】
Keywords and weights included in the cluster define centroid vectors of the major cluster after subjecting to appropriate averaging.  The centroid may be determined by weights of particular keywords and the keywords appeared in the core documents through a simple arithmetic average algorithm or any other known averaging method such as a moving average.
【００１６】
The centroid vectors of each of the time slices or chunks then computed to obtain the time dependent evolution of the centroid of the corresponding clusters with respect to the time elapse.
【００１７】
In another embodiment, the vector space model referred as sub-chunk may be generated as well as sequential time slice and/or sequential chunks.  The documents in sub-chunks overlap two subsequent time slices and/or chunks.  When the sub-chunks are prepared, the trace or tracking may be ensured when the major item suddenly changes in the accumulated documents.
【００１８】
According to the present invention, the information tracking of the loosely related documents may be improved as follows:
(1) Reduce data into manageable size overlapping slices, based on time stamp to enable fast vector space modeling followed by the principal component analysis-based dimensional reduction, and then the computation facilities are reduced;
(2) Use the principal components as the query to identify documents in major clusters such that effective and prompt search of the cluster are attained;
(3) Use retrieved documents (from step 2) to find core documents in the cluster. Their average approximates the cluster centroid. The keyword weights in the centroid vector describe the main topics addressed by documents in the cluster; and
(4) Refinement of the centroid vectors may be allowed; the first approximation is adopted as averages of documents in the cluster core, and then a refined approximation for the centroid vectors may be computed from the new document set until the set of retrieved documents stabilizes, a fixed number of times or system termination.
【００１９】
Now, the present invention will be explained in detail with referring to particular embodiments depicted as drawings.
【Best Mode for Practicing Invention】
【００２０】
SECTION I: COMPUTER SYSTEM
With referring to Fig. 1, general functional blocks of the system 100 are illustrated.  The system 100 may be constructed by well known computer architectures which comprise a central processing unit (CPU), memories such as cash, RAM and/or ROM, a hard-disk drive and bus lines interconnecting hardware modules.  The system 100 may also be operated by well known operating systems such as WINDOWS (trade mark), UNIX (trade mark), or LINUX (trade mark) and can execute application programs written by object oriented programming language and/or legacy programming languages such as C, C++, JAVA, RUBY, PERL, etc.
【００２１】
The system 100 comprises the data accumulation part (DAP) 102, the vector space generation part (VSGP)104, and dimension reduction part (DRP) 106.  The DAP102 may be constructed by various application modules such as a mailer, a chat application, an access-log analysis software implemented in a particular server and may be supported by database software such as DB2 (trade mark), ORACLE (trade mark), MySQL (trade mark), etc. so as to retrieve queried documents.
【００２２】
The DAP 102 accumulates information from the network 122 such as Internet, LAN (local area network), or WAN (wide area network).  The information may include text documents such as mails, chat transmissions, or log data, multimedia documents with appropriate text data, audio data.  When the information includes audio data, the audio data may be converted into text data by appropriate software such as VIA VOICE (trade mark), in order to generate the vector space model.
【００２３】
The information accumulated by the data accumulation part 102 generally has the character that the keywords included therein loosely relate to each other and relate to some focused items such as health, money, foods, environment, games, plans, etc.  The information is typically created without particular regulations and then, the same item may be described or expressed in different keywords while including loose relevancy.
【００２４】
The DAP 102 accumulates the information with respect to the time elapse in the document repository 112 and defines time slices or chunks to the information.  The time slice or chunk may be created by any rule in the present embodiment and the time slice or chunk may be created in a predetermined time span.  Alternatively, the time slice or chunk may be created in predetermined numbers of information.
【００２５】
The VSGP 104 may be constructed by the standard procedure for keyword extraction and stemming described in standard textbooks on the subject (R.K. Belew, “Finding Out About”, Cambridge Univ. Press, Cambridge, UK, 2001).  The VSGP 104 is implemented with a parser developed at the IBM Research that extracts keywords, deletes common stop-words, and conducts parts-of-speech tagging.  The detail of the parser can be referred by elsewhere (Mary S. Neff, Roy J. Byrd and Branimir K. Boguraev, The Talent system: TEXTRACT architecture and data model, Natural Language Engineering, Volume 10, 2004, pp. 307-326).  The VSGP 104 may be implemented to use single word tokens (nouns, verbs, and adjectives), but not limited thereto, any other rule or implementation embodiment may be possible.  In a preferred embodiment, a standard type of term frequency inter-document frequency (tf-idf) weighting may be implemented in the VSGP 104 followed by normalization (Christopher D. Manning and Hinrich Schuetze, Foundations of Statistical Natural Language Processing, MIT Press, Cambridge, Mass. USA, 1999).
【００２６】
The DRP 106 executes the dimension reduction of the document-keyword matrix using singular value decomposition algorithm to generate dimension reduction matrix of the document-keyword matrix.  In the preferred embodiment, the singular value decomposition algorithm of a numerical package from the Massachusetts Institute of Technology (MIT: Doug Rohde, SVDLIBC, version 1.34: http://www.tedlab.mit.edu:16080/~dr/SVDLIBC/) that is based on the Lanczos algorithm to compute the partial singular value decomposition of the document-keyword matrix.
【００２７】
The resulted dimension reduction matrix was stored in a particular repository such as the hard-disk drive.  The dimension reduction matrix is then retrieved to the centroid vector (keyword set) determination part (CVDP) 108 so as to determine centroid vectors of the particular time slice or chunk.  The detail of the determination of the centroid vector will be explained hereinafter.  The resulted centroid vectors of each time slice or chunk and also sub-chunks are stored in the item repository 114 for tracking the time evolution of the items being relevant to the documents.  The item analyzer part 110 retrieves the centroid vectors of each time slice or chunk in response to instructions from the keyboard 118 and/or a mouse 120 and performs the analysis of the centroid vectors.  The results of the analysis of the item analyzer part 110 are transmitted to the display device 116 for displaying the result on a display screen.
【００２８】
SECTION II: ALGORITHM of THE CLUSTER FINDING and TRACKING
With referring to Fig. 2, the preferred embodiment of the method is illustrated.  The method start from the step S200 and in the Step S201, the time slice or chunk of the information is determined.  In the step S202, the method executes the determination of cluster in the time slice or chunk using the vector space model and the dimension reduction algorithm so as to determine the centroid vectors.  The reason why the dimension reduction algorithm is preferred is that the document-keyword vector has sparse elements so that omission of minor keywords improves the computation efficiency.  The centroid vector refers herein the vector of keyword-weight for the particular cluster defined in the documents within the time slice or chunk.
【００２９】
In the Step S203, the determined centroid vectors are stored in the item repository 114 for tracking of the item analyzer part 110.  In the step S204, the centroid vectors are retrieved from the item repository 114 and the results of the analysis is displayed on the display device 116.  In the step S205, the method determines whether or not there is new time slice or chunk to be processed.  When new time slice or chunk is still remained, the method reverts to the step S201 and repeats the following processes from step S202 to the step S205 until there is no time slice or chunk to be processed, i.e. end of the time slice or chunk in the document repository 112.  When there is no the time slice or chunk to be processed, the method is terminated in the step S206.
【００３０】
With referring to Fig. 3, the detailed embodiment for generating the centroid vector is described.  The process of Fig. 3 starts from the step S300 and in the step S301, retrieves predetermined numbers of documents in the present time slice or chunk from the document repository 112.  In the step S302, the vector space model is generated from the retrieved documents by the VSGP 104 and subsequently executes the dimension reduction by the DRP 106 as described in SECTION I.
【００３１】
In the step S303, principal components of the dimension reduction matrix is determined.  The term “principal components”refers herein keywords recorded in the same line in the dimension reduction matrix and used to retrieve a principal document in the dimension reduction matrix. The preferred embodiment of the time slice or chunk and the principal components defined in the embodiment will be described in detail hereinafter.
【００３２】
In the step S304, the cluster is determined using the principal document as a second query to the dimension reduction matrix; the process step is essential to determine the most probable document including the principal components in the line of the dimension reduction matrix and to determine the cluster relevant to the principal document.  Briefly, the determination of the cluster depends on distances of the document-keyword vectors from the principal document and the cluster is defined by any appropriate rule or algorithm considering particular applications and properties of documents.
【００３３】
While many clustering algorithms use a randomized algorithm to select documents as initial seeds for clusters (e.g., the K-means algorithm and many proposed variations).  The algorithm of the present embodiment is a more systematic and straightforward approach in which the principal components serve as queries.  Indeed, the present system can succeeded in finding similar documents to the conventional methods.  The retrieved documents may be expected to address major topics because of the fundamental property of principal component analysis that the largest principal component points in the direction containing the most information about the database. The vector corresponding to the second largest principal component points in the direction containing the second most information about the database, and similarly for the subsequent principal components.
【００３４】
In one preferred embodiment of the clustering, the retrieved documents are sorted from the highest relevancy to the lowest relevancy.  An updated approximation for the centroid is computed in a manner analogous to the process used for first approximation.  The determination of the process of refining the approximation for the cluster may continue for several iterations until:
(1)the set of documents used for the approximation stabilizes (e.g., does not change or a percentage of the documents above a fixed threshold does not change) or
(2)its value does not change or changes very little value εbetween two consecutive iterations.
【００３５】
In the step S305, the method determines the centroid vectors; the centroid vector is likely to be more dense (have more non-zero entries) than the average document vector.  Then, the more preferred embodiment for speeding up computations of cluster determination, without compromising the quality of results are:
use only 30 highest ranked documents from the second query; compute the component-wise average of the 30 document vectors; set the weights of all words less than a fixed threshold (e.g., 5%) to zero; order words from highest to lowest weight; and for each word, plot its weight as a function of time. If the slope of the document rankings from the second query undergoes a sudden change before 30 documents, then use only those documents before the change to compute the component-wise average.
【００３６】
Further in the step S306, the centroid vector or centroid vectors for different principal documents are stored in the item storage 114 with an identifier of the time slice or chunk.  Further in the step S307, the method determined whether or not all of the documents in the database, i.e., the time slice and/or the chunk have been processed.  In the determination of the step S307, when the time slice or chunk is still remained, the method reverts to the step S301 and repeats the processes described above.  When no time slice or chunk is remained, the method proceeded to the step S308 to terminate the execution of the process.
【００３７】
The embodiment described in Fig. 3 may be applied to a static database in which the documents have been already stored therein while the documents include time stamps such that the time slice or chunk is defined to the documents.  In the embodiment illustrated in Fig. 4, the documents are accumulated parallel to processing from the generation of the vector space model to the storage in the item storage.  The process of Fig. 4 may be implemented as a daemon process or a service process and the process will be executed by the system shutdown or termination of the system.  The method of Fig. 4 starts from the step S400.  In the step S401, the method determined whether or not documents in the document database are accumulated enough to define next time slice or chunk by the VSGP 104.  When the VSGP 104 determines new time slice or chunk is prepared through, for example, inter-process communication from the DAP 102, the VSGP 104 start to generate new vector space model for the time slice or chunk to be processed.  Then the method goes to the steps from S402 to S407 so as to execute the similar processes described in Fig. 3.  The embodiment of Fig. 4 repeatedly monitors the acknowledgement from the DAP 102 until the VSGP 104 receives the affirmative acknowledgement for preparation of new time slice or chunk in the step S401.  The process steps from steps S402 to step S407 are almost same with the processes of Fig. 3, and then further detailed descriptions are omitted herein.
【００３８】
SECTION  III： DETAIL DESCRIPTION of INFORMATION PROCESSING
Fig. 5 shows the data structure of the time slice or chunk introduced in the present invention.  The documents stored in the document database are recorded together with timestamps received by the DAP 102 so as to define the time slice or chunk.  Alternatively, the documents may be stored without the timestamps and the time slice and/or chunk may be defined when predetermined numbers of the documents are accumulated with the timestamp when the numbers of the documents reach to the predetermined number, but not limited thereto, the present invention may adopt any other time slice or chunk creation method.
【００３９】
The documents are divided into the chunks in Fig. 5 and each of the chunks 500-1,...,500-3 includes the same numbers of the documents.  The embodiment of Fig. 5 is then time duration for the chunks may be different each other; the embodiment may be preferred when the information accumulated by the DAP 102.  The numbers of the document included in the chunk may be same or different between the chunks; however, in order to certify statistical reliability of the dimension reduction, the chunk may include the same number m of documents.  In the embodiment using the predetermined numbers of the documents, the last chunk 500-3 may be less or more numbers than the other chunks depending on the total numbers of the documents in the document database.
【００４０】
In the preferred embodiment, the sub-chunks 500-4, 500-5, and 500-6 are also defined.  The sub-chunks 500-4, 500-5, and 500-6 are used to support tracking of the sequential chunks 500-1, 500-2, and 500-3 and are defined to have the documents both of the adjacent chunks such as 500-1 and 500-2.  The sub-chunk may be used such that tracking between the adjacent chunks is made possible even if particular keywords disappear between the adjacent chunks.  The sub-chunks may be formed to share one half documents of the former chunk and one half of the latter chunk which are sequentially defined in the database.
【００４１】
The preferred embodiment of the present invention, the dimension reduction was executed in tiny document-keyword spaces and the dimension reduction is fast and efficiently executed without a curse of dimension while making it possible to track the item evolution of the document repository.
【００４２】
When tracking of the items is objected, a simple tracking method may be provided using the overlapping time slices or chunk referred as sub-chunks.  Now, let W1 denote the first chunk, or temporal window, let W2 denote the second chunk, and let Wi the i-th chunk or window (here i represents positive integer value).  For a retrieved topic, associated documents that are in the windows W1and W2 are still maintained as the subjected item though weights thereof may be different.  Since documents are numbered according to the order of their posting or accumulation, we only needed to check that the document used as “seeds” (i.e., queries) to find documents in similar documents in W2, as shown in Fig. 5.  When the topic continued to be an active item for the documents, then a non-empty set of documents posted during the latter half of W2 is retrieved.
【００４３】
To track small shifts in the item from W1 to W2, the set of documents in W2 on the item to compute an approximate centroid vector by computing the moving average of the seed vectors.  The vector average in the embodiment described may represent the evolution of the centroid vectors.  When more sophisticated application, the above centroid may be set as the first approximation to the centroid vectors as the query vector to retrieve a set of relevant documents and to compute an refinement for the approximate centroid. Analogous procedures may be applied to the time slices or chunks to track sets of documents on the specific item from time slices or chunks Wi to Wi+1, and to track the approximate centroids.
【００４４】
Fig. 6 shows embodiments of the document-keyword vectors (a) and the definition of the distance between the document-keyword vectors (b). Referring to Fig. 6, the keywords in the document are counted for every keyword to provide integer digital values of the keyword with weights as the document-keyword vector 602.  In the next step, the document-keyword vector 602 are subjected to Tf-idf process so as to modify the weights of each keyword using the algorithm described above as the document-keyword vector 604, and then the modified weights are normalized such that their norm is equal to be the unity as the document-keyword vector 606.
【００４５】
In turn, the distance between the document-keyword vectors X and Y is defined herein as the inner product of the document-keyword vectors X and Y as shown in Fig. 6 (b), wherein |X| is the norm of vector X, |Y| is the norm of the vector Y, the vectors have been normalized so that |X|＝|Y|＝1, θrepresents the angle between the vectors, xi and yi are elements of each of the vectors X and Y together consisting of n elements from i=1 to n.
【００４６】
Fig. 7 shows the process for determining the principal components in the dimension reduction matrix 700.  Fig. 7(a) shows the typical embodiment of the dimension reduction matrix 700 and Fig. 7(b) shows typical embodiments of principal components.  The dimension reduction matrix 700 is computed from the document-keyword matrix consisting of document-keyword vectors shown in Fig. 6 (a) as columns with respect to series of the documents.  Typical keyword numbers in the document-keyword vectors may range several thousands or more.  The dimensions of the keywords are reduced into 500 keywords by the singular value decomposition through the method described above as the dimension reduction matrix 700 in the described embodiment.
【００４７】
The principal components are defined as the line of the dimension reduction matrix 700 and the principal components are identified as the first component, the second component,..., the n-th component with respect to the order of the keywords remained through the dimension reduction in Fig. 7 (a).  The order of the keywords through the dimension reduction may be arranged in the original order in the document-keyword matrix, or in more preferred embodiment, the keywords may be re-arranged in the descendant order with respect to the singular values.  When the order of the keywords is arranged with respect to the singular values, the principal components readily refer major keywords in the documents so that the principal components provide good relevancy to the major item in the documents.
【００４８】
Referring to Fig. 7 (b), the first component 702 comprises the top keywords in the line, and the second principal component 704 comprises the second line components, and the n-th principal component 706 comprises the n-th line components.  In the present invention, each of the principal components may be used as a first query for determining the most relevant documents(and other high-ranking documents) which are referred herein as principal documents.
【００４９】
In Fig. 8, further detail of the principal component is illustrated.  The embodiment of Fig. 8 (a) corresponds to the second principal component 704 and comprises 8000 elements of the keywords which correspond to the chunk of the document.  Fig. 8 (b) shows exemplary keywords 708 included in the second principal component such as energy, solar, etc.  The numerals for each of the keywords are normalized weights for the corresponding keywords.  The principal component is used as the first query to the document for determining the most relevant document to the principal component.  The query process includes in the present embodiment the distance computation between the principal component and the dimension reduction matrix to extract the principal document(and other high-ranking documents).  In an alternative embodiment, the query may be applied to the original document-keyword matrix.
【００５０】
Fig. 9 shows the result of the first query.  The relevant documents are extracted from the documents as shown in the list 900 which may be tentatively stored in an adequate memory space in the computer system.  The list 900 comprises the documents extracted by the query shown in Fig. 8, and the documents are sorted in the descendant order with respect to the distance to the principal component filled in the field 902.  The distances filled in the field 902 are relatively low values in this step because the first query is the principal components selected across the documents included in the chunk.  The list 900 further entries the field 904 which lists document identifier such as document numbers; the document numbers may be provided when the documents are stored in the document database, or alternatively other identifiers may be provided depending on particular implementation architectures.  The list 900 also includes the field 906 in which the title of the documents for indexes of the documents.
【００５１】
According to the particular embodiment shown in Fig. 9, the second query vector is of the most relevant document 908(corresponding to the document [#ID:2141]).  The second query is again projected to the dimension reduction matrix so as to determine the clusters and the cluster centroids.  When the second query is projected to the dimension reduction matrix, the distances to the relevant documents become higher values because the second query includes the important keywords in the cluster.
【００５２】
Fig. 10 shows the embodiment of results of the query.  Fig. 10 (a) shows the global result within the chunk and Fig. 10 (b) shows the detailed results having higher relevancies to the second query, that is, keywords of the principal component.  As shown in Fig. 10, the ordinates represent the relevancy derived from the distance and the abscissas are document numbers.  As shown in Fig. 10 (a), the relevancy rapidly decrease from the query document referred as zero to the last document referred to 8000; the rapid decrement may present sizes of the clusters.  Fig. 10 (b) shows enlarged behavior of the decrement of the relevancy roughly indicated by the rectangular 1000.  The enlarged decrement of the relevancy shows stepwise decrements and may suggest borders of the clusters with respect to the horizontal slice of the relevancy.
【００５３】
Thus, the cluster may be defined depending on their sliced relevancy; when a low slice level is adopted, less relevant documents are incorporated in the cluster and a high slice level is adopted, clusters with few documents in the cluster.  Thence, there are some standards to determine the cluster.  In the described embodiment, several strategies may be possible.  In order to automate the process for identifying and approximating the cluster, the first strategy is to provide in a graph graphed similarity as shown in Fig. 10 from the most to the least relevancies which are aligned from left-to-right.
【００５４】
Then the average of the keywords and weights thereof in the relevant documents may be used to compute an approximation for the centroid vectors of the cluster; in the embodiment shown in Fig. 10, for example, 30 documents may be considered to be clusters, but not limited thereto, other rules may be adopted in the present invention depending on particular application or characteristics of the relevancy change.  For example, when the slope of the documents versus relevancy suddenly changes before 30 documents (as shown in Fig. 10 (b)), only the documents before the first sudden slope change may be used to determine the cluster and to compute the centroid vectors.  Further other embodiments, the cluster may be determined merely by the relevancy level such as 0.7 as shown in Fig. 10(b) or by document numbers from higher relevancies, etc.
【００５５】
Fig. 11 schematically illustrates clusters in the document-keyword space (dimension reduced) 1100 and the elements of the centroid vectors.  The clusters 1102-1106 are defined according to the procedure described in Fig. 10 for different principal documents which are indicated with filled circles as shown in Fig. 11 (a).  Here, the elements 1110 of the centroid vector 1108 of the cluster 1106 are shown in Fig. 11 (b) together with weights thereof.  The clusters may be determined for every principal document and every time slice or chunks and hence, the centroid vectors may be stored for each chunk as the list 1200 shown in Fig. 12.  In the embodiment of Fig. 12, centroid vectors for the cluster corresponding to the second principal documents are presented; however, another embodiment may include more centroid vectors corresponding to each of the clusters.  The list 1200 may be stored in memory spaces such as the item repository 114 with appropriate formats such as CVS, comma-space, or other application oriented formats in the computer system for the analysis of the item analyzer part 110.
【００５６】
GUIs and means of plotting results may be adopted among various database applications, spreadsheet application which are commercially available and then, further details will not be explained herein.
【００５７】
There may be various variations on the describe embodiment hereinabove.  Such variations are, for example, but not limited thereto,  listed as follows:
(1) chunk sizes (e.g., smaller, larger or non-uniform sizing); 
(2) extent of chunk overlap (less than or greater than 50%, non-uniform size overlaps); or
(3)alternative criteria for chunking (e.g., posting during temporal windows, country of origin).
【００５８】
SECTION  IV:EXPERIMENTAL
(IV-1) COMPUTER IMPLEMENTATION
The computer system implemented with the program of the present invention was ThinkPad (trade mark) T40 which mounted PENTIUM (trade mark) M processor with 1.5 GHz clock with a 1GB RAM.  The operating system thereof was WINDOWS (trade mark) XP.  The program was described in JAVA (trade mark).  In the above implementation, the computation of the entire documents was completed within 30 minutes.
【００５９】
(IV-2) DATABASE PREPARATION
The database used for examine the present method for identification and tracking of clusters and the flow of items using text data was generated during the first phase of the 2006 IBM Innovation Jam (I-Jam).  The data were comprised of 37,037 postings (mails) by more than 53,000 participants around the globe over a 78 hour period (from July 24, 2006 7:00 A.M. EST to July 27, 2006. 11:00 A.M. EST).  Each document represented an opinion freely input by an employee or family member of IBM Research or 67 selected external organizations. 200 to 300 of the posted opinions were in a language other than English.  The contents of postings other than English were omitted from the analysis.
【００６０】
Participants were requested to submit postings on the four categories as follows: 
1. Going Places - transforming travel, transportation, recreation and entertainment; 
2. Finance and Commerce - the changing nature of global business and commerce; 
3. Staying Healthy - the science and business of well-being; and 
4. A Better Planet - balancing economic and environmental priorities.
【００６１】
Documents were sorted from oldest to newest according to the timestamp of their posting.  The data set was chunked into time slices of 8,000 consecutive document postings.  In the implementation, sub-chunks were defined as each time slice to have a 4,000 document overlap with the previous time slice (and consequently, a 4,000 document overlap with the subsequent time slice).
【００６２】
To construct a vector space model for the sample database, each 8,000 documents of I-Jam dataset was chunked as time slices using the standard procedure for keyword extraction and stemming described in standard textbooks on the subject e.g., Belew (op. cit.) and more specifically, Talent (Neff et al. (op. cit.)) which is a parser developed at the IBM Research, that extracts keywords, deletes common stopwords, and conducts parts-of-speech tagging.  The keywords were only considered single word tokens (nouns, verbs, and adjectives).  The keywords set was confirmed that the set keywords extracted followed a Zipfian distribution.  Next, rare and overly frequent keywords were omitted from the keyword set.  In the implementations, the bottom cut-off points were less than 10 documents (for the lower bound), and more than 5%-7% of documents, depending on the shape of the log-log Zipfian curve (for the upper bound).  A standard type of term frequency inter-document frequency (tf-idf) weighting was applied, followed by normalization Manning and Schuetze (op. cit.). A typical result from vector space modeling of a 8,000 document time slice is 3136 keywords, leading to a 8000-by-3136 document-attribute matrix with density 1%-2%.
【００６３】
In order to examine the results, two trial sets were selected; one set was a set of documents that addresses food and health issues and another set was a set of documents that addresses money and security.  Documents in the overlap between the first and second time slice or chunks were used to track how the topic evolved in the second time slice.  The time slices or chunks were divided into 10 time slices or chunks in which each of the time slices or chunks included 8000 documents excepting for the last time slice or chunk.
【００６４】
The 12 prominent items (keywords) in the centroid vectors from the 10 time slices of I-Jam data: junk, vegetable, cancer, diet, eat, calorie, healthy, cook, exercise, fat, nutritional, and price, in the first trial set and four keywords with relatively high weight were considered: cash, payment, security, and signature, in the second trial set.  After the tracking experiments, the texts of the original documents (i.e., I-Jam postings) were referred to the results so as to check whether or not shifts in the keyword weights did indeed correspond to changes in the discussion within documents.
【００６５】
（IV-3) RESULTS
The results are shown in Figs. 13-15, and Fig. 13 shows the results for cluster on food and health and tracking of all of the items, Fig. 14 shows the results for detailed tracking of items on eat, healthy, and exercise in the food and health result, and Fig. 15 shows the result for cluster on money and security and tracking was focused on the items on cash, payment, security and signature.  Only in Fig. 15, the texts ob postings are displayed.
【００６６】
As shown in Fig. 13, the cluster on food and health comprises 12 prominent items such as junk, vegetable, cancer, etc.  The items clearly show time dependent weight changes between the first chunk and the 10-th chunk.  Then, the items eat, healthy and exercise are independently selected so as to examine the mutual relation there between.  The result is shown in Fig. 14 and clear relationship is presented; the users posting to the food and health are largely interested in healthy and eat rather than exercise, and the item “eat” is negative direction when the item “healthy”and the item“exercise” are major concerns of the postings.
【００６７】
Fig. 15 shows another result for the cluster including the items of cash, payment, security, and signature.  To each of the peaks in Fig. 15, representative postings are listed together.  The item ”security”and the item “payment” are first create the peaks and then in the 5-th chunk, the item “signature” creates another peak while the item “security”and the item “payment” become minor items; this is supposed that items of payment and cash induced the posting or opinions about the item “signature”.  Then the major items of the postings show the evolution to the postings including items “payment”,“cash”and “security”.
【００６８】
As described hereinabove, it has been understood that the present invention improves information retrieval of the documents loosely related and accumulated without particular regulations for formats with high efficiency and high performance.  The present system, method, and the program makes it possible to make prompt semantic analysis of documents which are accumulated or stored almost in real time as well as in static databases.
【００６９】
While the present invention described hereinabove by using the embodiments and examples illustrated in the drawings; however, it is appreciated for persons skilled in the art that true scope of the present invention should only be limited by appended claims and the present invention may be implemented with alternative embodiments, with modifications, and with omission of non-essential features.
【Brief Review of Drawings】
【００７０】
Fig. 1 shows general functional blocks of the system 100 are illustrated.
Fig. 2 shows the preferred embodiment of the method. 
Fig. 3 shows the detailed embodiment for generating the centroid vector is described.
Fig. 4 shows the preferred embodiment of the method.
Fig. 5 shows the data structure of the time slice or chunk introduced in the present invention. 
Fig. 6 shows embodiments of the document-keyword vectors (a) and the definition of the distance between the document-keyword vectors (b). 
Fig. 7 shows the process for determining the principal components in the dimension reduction matrix 700. 
Fig. 8 shows further detail of the embodiments of the principal component. 
Fig. 9 shows the result of the first query. 
Fig. 10 shows the embodiment of results of the query. 
Fig. 11 schematically illustrates clusters in the document-keyword space (dimension reduced) and the elements of the centroid vectors.
Fig. 12 shows the centroid vectors which may be stored for each chunks as the list 1200.
Fig. 13 shows the results for cluster on food and health and tracking of all of the items.
Fig. 14 shows the results for detailed tracking of items on eat, healthy and exercise. 
Fig. 15 shows another result for the cluster including the items of cash, payment, security, and signature.
【Brief Review of Numerals】
【００７１】
100-computer system, 102-data accumulation part, 104-vector space generation part, 106-dimension reduction part, 108-centroid vector determination part, 110-item analyzer part, 112-document repository, 114-item repository, 116-display device, 118-keyboard, 120-mouse, 122-network, 500-chunk (time slice), 600-document-keyword vector, 700-dimension reduction matrix, 702-706-principal component, 900-list, 1100-document-keyword space, 1102-1106-clusters, 1108-centroid vector, 1110-elements of centroid vector, 1200-list
【claim 1】
A system for information clustering, said system comprising;
a data accumulation part for accumulating documents in a document repository, said documents including loosely related clusters between said documents being time sliced so as to define chunks of said documents;
a vector space generation part for generating document-keyword vectors, said document-keyword vectors consisting of sparse numeral values depending on presence of keywords in said documents;
a dimension reduction part for reducing dimensions of said keywords to create a dimension reduction matrix of said document-keyword matrix;
a centroid vector determination part for generating a centroid vector of said cluster, said cluster being retrieved from said document-keyword vector using a principal component in a same line of said dimension reduction matrix, said centroid vectors being defined from keywords and weight of documents within said cluster; and 
an item repository for storing said centroid vectors together with said keywords and said weights of said centroid vector.
【claim 2】
The system of claim 1, wherein said centroid vector determination part retrieves a principal document in said document using said principal component as a first query vector and subsequently retrieves documents defining said clusters using said principal document as a second query vector.
【claim 3】
The system of claim 1, wherein said vector space generation part executes dimension reduction to each of said chunks of said dimension reduction matrix and said centroid vector generation part generates clusters for every chunk of said dimension reduction matrix.
【claim 4】
The system of claim 1, wherein said system further comprises an item analyzer part for analyzing evolution of items with respect to said chunk of said document and for information tracking.
【claim 5】
A computer executable method for information clustering, said method making said computer execute the steps of;
accumulating documents in a document repository, said documents including loosely related clusters between said documents being time sliced so as to define chunks of said documents;
generating document-keyword vectors, said document-keyword vectors consisting of sparse numeral values depending on presence of keywords in said documents;
reducing dimensions of said keywords to create a dimension reduction matrix of said document-keyword matrix; and 
generating a centroid vector of said cluster, said cluster being retrieved from said document-keyword vector using a principal component in a same line of said dimension reduction matrix, said centroid vectors being defined from keywords and weight of documents within said cluster; and 
storing said centroid vectors in an item repository together with said keywords and said weights of said centroid vector.
【claim 6】
The method of claim 5, said method further comprising the steps of;
retrieving a principal document in said document using said principal component as a first query vector and 
subsequently retrieving documents defining said clusters using said principal document as a second query vector.
【claim 7】
The method of claim 5, said method further comprising the steps of;
executing dimension reduction to each of said chunks of said dimension reduction matrix and 
generating clusters for every chunk of said dimension reduction matrix.
【claim 8】
The method of claim 5, said method further comprising the steps of;
analyzing evolution of items with respect to said chunk of said document and for information tracking.
【claim 9】
A system for information tracking, said system comprises;
a data accumulation part for accumulating documents in a document repository, said documents including loosely related clusters between said documents being time sliced so as to define chunks of said documents;
a vector space generation part for generating document-keyword vectors, said document-keyword vectors consisting of sparse numeral values depending on presence of keywords in said documents;
a dimension reduction part for reducing dimensions of said keywords to create a dimension reduction matrix of said document-keyword matrix;
a centroid vector determination part for generating a centroid vector of said cluster, said cluster being retrieved from said document-keyword vector using a principal component in a same line of said dimension reduction matrix, said centroid vectors being defined from keywords and weight of documents within said cluster;
an item analyzer part for analyzing evolution of items with respect to said chunk of said document and for information tracking; and
an item repository for storing said centroid vectors together with said keywords and said weights of said centroid vector.
【claim 10】
The system of claim 9, wherein said centroid vector determination part retrieves a principal document in said document using said principal component as a first query vector and subsequently retrieves documents defining said clusters using said principal document as a second query vector.
【claim 11】
A computer executable method for information tracking, said method making said computer execute the steps of;
accumulating documents in a document repository, said documents including loosely related clusters between said documents being time sliced so as to define chunks of said documents;
generating document-keyword vectors, said document-keyword vectors consisting of sparse numeral values depending on presence of keywords in said documents;
reducing dimensions of said keywords to create a dimension reduction matrix of said document-keyword matrix; and 
generating a centroid vector of said cluster, said cluster being retrieved from said document-keyword vector using a principal component in a same line of said dimension reduction matrix, said centroid vectors being defined from keywords and weight of documents within said cluster; 
storing said centroid vectors in an item repository together with said keywords and said weights of said centroid vector; and 
analyzing evolution of items with respect to said chunk of said document and for information tracking.
【claim 12】
The method of claim 11, said method further comprising the steps of;
retrieving a principal document in said document using said principal component as a first query vector and 
subsequently retrieving documents defining said clusters using said principal document as a second query vector.
【claim 13】
A computer executable program for making a computer execute any one of the methods from claim 5 to claim 8.
【claim 14】
A computer executable program for making a computer execute any one of the methods of claim 11 or claim 12.
【要約】
【課題】To provide System, method and computer executable program for information tracking from heterogeneous sources.
【解決手段】A system 100 for information clustering, the system comprising; a data accumulation part 102 for accumulating documents in a document repository, the documents including loosely related attributes and defining a cluster between the documents and time sliced so as to define chunks of the documents; a vector space generation part 104 for generating document-keyword vectors, the document-keyword vectors consisting of sparse numeral values depending on presence of keywords in the documents; a dimension reduction part 106 for reducing dimensions of the keywords to create a dimension reduction matrix of the document-keyword matrix; a centroid vector determination part 108 for generating a centroid vector of the cluster, the cluster being retrieved from the document-keyword vector using a principal component in a same line of the dimension reduction matrix, the centroid vectors being defined from keywords and weight of documents within the cluster; and an item repository 112 for storing the centroid vectors together with the keywords and the weights of the centroid vector.
【選択図】Fig. 2
2008181205.tif 000018
2008181205.tif 000019
2008181205.tif 000020
2008181205.tif 000021
2008181205.tif 000022
2008181205.tif 000023
2008181205.tif 000024
2008181205.tif 000025
2008181205.tif 000026
2008181205.tif 000027
2008181205.tif 000028
2008181205.tif 000029
2008181205.tif 000030
2008181205.tif 000031
2008181205.tif 000032