(57)【特許請求の範囲】
【請求項１】
複数の公開用の情報の既存のクラスタを含むデータベース内で情報の収集体を動的に更新するための方法であって、
ａ）受信情報から前記受信情報を特徴付ける１組の特徴的特性を抽出するステップであって、前記受信情報は所与のタイプの複数の特性を含み、前記複数の特性は抽出されると重要度でランク付けされる、特徴的特性を抽出するステップと、
ｂ）前記受信情報を、前記収集体内で前記受信情報と共通の特徴的特性を有する１または複数の既存のクラスタにグループ化し、クラスタ近傍を生成するための共通の特徴を有する複数の既存のクラスタを一緒にグループ化することにより、前記情報の収集体を更新するステップであって、
１または複数の既存のクラスタの各々は前記クラスタを特徴付ける１組の特徴的特性を含み、
前記受信情報を特徴付ける特性および既存のクラスタを特徴付ける特性の内積が閾値を超える場合、前記受信情報は前記既存のクラスタにグループ化される、前記情報の収集体を更新するステップと、
ｃ）前記クラスタ近傍の情報の更新された収集体の少なくとも一部を顧客の情報要求に基づいて公開するステップとを備え、
前記受信情報はテキストを含む文書であり、前記文書が前記クラスタ近傍に割り当てられている時間に応じて変化する近傍の適合度を用いて、前記クラスタ近傍中の文書を顧客に公開するかどうか決定することを特徴とする方法。
【請求項２】
前記受信情報は、テキストデータ、画像データ、および映像データの１つまたは複数の組み合わせを含むことを特徴とする請求項１に記載の方法。
【請求項３】
新しい受信情報の項目のランクの複数の特性とクラスタの対応する数の特性とを比較して、前記情報をクラスタに追加するかどうかを決定することを特徴とする請求項１に記載の方法。
【請求項４】
各特性は、前記特性を測定するための適合率を有し、前記方法は、クラスタと前記新しい受信情報が、少なくとも複数の共通する適合率が０でない特性を有するかどうかを、前記受信情報をクラスタに追加する前に決定するステップをさらに備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記適合度は、情報要求中に含まれる情報に応じて変化することを特徴とする請求項１に記載の方法。
【請求項６】
受信情報の項目は、２以上のクラスタにグループ化されるが、１つの近傍としか一緒に公開できないことを特徴とする請求項１に記載の方法。
【請求項７】
ヌル近傍を保持するステップと、受信情報を最初に受信したときに前記情報を前記ヌル近傍に追加するステップとをさらに備えることを特徴とする請求項６に記載の方法。
【請求項８】
ヌル近傍を保持するステップと、近傍のコンテンツが前記近傍の再構成のため変化する場合、受信情報を前記ヌル近傍に追加するステップとをさらに備えることを特徴とする請求項６に記載の方法。
【請求項９】
ヌル近傍を保持するステップと、前記受信情報が近傍に対して不適合となる場合、受信情報を前記ヌル近傍に追加するステップとをさらに備えることを特徴とする請求項６に記載の方法。
【請求項１０】
複数の公開用の情報の既存のクラスタを含むデータベース内で情報の収集体を動的に更新する方法を実行ための命令を含むコンピュータ可読媒体であって、前記方法は、
ａ）受信情報から前記受信情報を特徴付ける１組の特徴的特性を抽出するステップであって、前記受信情報は所与のタイプの複数の特性を含み、前記複数の特性は抽出されると重要度でランク付けされる、特徴的特性を抽出するステップと、
ｂ）前記受信情報を、前記収集体内で前記受信情報と共通の特徴的特性を有する１または複数の既存のクラスタにグループ化し、クラスタ近傍を生成するための共通の特徴を有する複数の既存のクラスタを一緒にグループ化することにより、前記情報の収集体を更新するステップであって、
１または複数の既存のクラスタの各々は前記クラスタを特徴付ける１組の特徴的特性を含み、
前記受信情報を特徴付ける特性および既存のクラスタを特徴付ける特性の内積が閾値を超える場合、前記受信情報は前記既存のクラスタにグループ化される、前記情報の収集体を更新するステップと、
ｃ）前記クラスタ近傍の情報の更新された収集体の少なくとも一部を顧客の情報要求に基づいて公開するステップとを備え、
前記受信情報はテキストを含む文書であり、前記文書が前記クラスタ近傍に割り当てられている時間に応じて変化する近傍の適合度を用いて、前記クラスタ近傍中の文書を顧客に公開するかどうか決定することを特徴とするコンピュータ可読媒体。
【請求項１１】
前記受信情報は、テキストデータ、画像データ、および映像データの１つまたは複数の組み合わせを含むことを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１２】
新しい受信情報の項目のランクの複数の特性とクラスタのランクの対応する数の特性とを比較して、前記情報をクラスタに追加するかどうかを決定することを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１３】
各特性は、前記特性を測定するための適合率を有し、前記方法は、クラスタと前記新しい受信情報とが、少なくとも複数の共通する適合率が０でない特性を有するかどうかを、前記受信情報をクラスタに追加する前に決定するステップをさらに備えることを特徴とする請求項１２に記載のコンピュータ可読媒体。
【請求項１４】
前記適合度は、情報要求中に含まれる情報に応じて変化することを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１５】
ヌル近傍を保持するステップと、受信情報を最初に受信したときに前記情報を前記ヌル近傍に追加するステップとを備えることを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１６】
ヌル近傍を保持するステップと、近傍のコンテンツが前記近傍の再構成のため変化する場合、受信情報を前記ヌル近傍に追加するステップとをさらに備えることを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１７】
ヌル近傍を保持するステップと、前記受信情報が近傍に対して不適合となる場合、受信情報を前記ヌル近傍に追加するステップとをさらに備えることを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１８】
前記受信情報と共通の特徴的特性を有する既存のクラスタが前記収集体内にない場合、前記受信情報を含む新しいクラスタを形成することにより前記情報の収集体を更新するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１９】
前記受信情報と共通の特徴的特性を有する既存のクラスタが前記収集体内にない場合、前記受信情報を含む新しいクラスタを形成することにより前記情報の収集体を更新するステップをさらに備えることを特徴とする請求項１０に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書を自動的に類別し再公開するための文書解析に関する。
【背景技術】
【０００２】
インターネットなどのデータ発信源(sources of data)から関連した最新情報を見つけ出したいと望んでいるユーザは、新しいコンテンツが大量に発信され続けている状況に直面する。類似のコンテンツを一緒にグループ化することによって、そのような大量のデータから選別（sort）する作業が、簡素化され得る。
【０００３】
既存技術が、ウェブベースの原文書を自動的に分類するのに利用されている。Ｌｉｎ他の論文（非特許文献１）には、ウェブ上にテキストとして公開された意味あるコンテンツから冗長データを自動的に除去するプロセスが説明されている。同論文の目的は、冗長であり、繰り返し出現する、通常は関心がもたれないデータから、意味あるデータを選り分けることである。
【０００４】
【特許文献１】米国特許第６，０１２，０５８号明細書
【非特許文献１】Lin et al. "Discovering Informative Content Blocks from Web Documents"
【非特許文献２】Watters et al. "Rating News Documents for Similarity"
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ページから冗長データを取り除いた後、ウェブページのテキストコンテンツは、既知の索引付け技法を用いて分類することができる。索引付けされたウェブページは、次に、Ｇｏｏｇｌｅ、ＭＳＮ、またはＹａｈｏｏなどの既存のウェブ検索エンジンによって評価することができる。Ｌｉｎ他の論文は、冗長データを有すると見なされたウェブページの適合度の低い部分を排除するが、見つかった意味ある情報を有するテキストページの索引付けまたは評価を変更することはない。
【０００６】
Ｗａｔｔｅｒｓ他の文献（非特許文献２）は、ニュース文書の個人向け送達システムに関する。同文献には、特性的語句の抽出、特性的語句がどこで日付、場所、人物、および組織を識別しているかに基づいて、ニュース文書を関連付ける方法が説明されている。これらの特性的語句から、ニュース表示が生成されて、関連ニュース記事を見つけるために比較でき、ランク付けできるニュースオブジェクトを定義付ける。
【０００７】
さらに大規模な検索問題に関する局面では、本発明は、概念的に明瞭に異なるコンテンツだけを提示することによって、ユーザが大量の情報の収集体を素早くブラウズでき、関心のある個別情報を見つけ出せるようにする手段を提供する。
【課題を解決するための手段】
【０００８】
公開される情報を動的に更新するための方法およびシステムが開示される。意味あるコンテンツが、複数の情報源(source)から受信した情報から抽出される。情報は、テキスト、画像、および映像を含むことができる。受信した情報に関する１組の特徴的特性（characterizing features）が決定される。共通の特徴的特性を有する情報は、複数のクラスタにグループ化される。グループ化ステップで取得した情報を用い、顧客の情報要求に基づいてクラスタに含まれる情報をどのように公開するかが決定される。この顧客要求は、クエリまたは顧客に割り当てられた顧客プロフィールに基づくことができる。
【０００９】
本発明の使用の１つに、世界中のウェブベースのニュースサイトで提示されるニュース記事の収集体を継続的に識別し修正するのに動的コンテンツクラスタリング（ｄｙｎａｍｉｃ  ｃｏｎｔｅｎｔ  ｃｌｕｓｔｅｒｉｎｇ）を使用する、ニュースボット自動化ニュースポータル（Ｎｅｗｓｂｏｔ  ａｕｔｏｍａｔｅｄ  ｎｅｗｓ  ｐｏｒｔａｌ）とともに用いる例がある。記事は、ニュースボットシステムに取り込まれると、以前に報道された記事に類似したものがある場合は既存のクラスタに割り当てられ、類似したものがない場合は新しいクラスタに割り当てられる。ニュースボットシステム内のクラスタの状態は、様々なニュースボットウェブページを構築するのに使用されるカタログファイルに、数分おきに記録される。
【００１０】
本発明の上記およびその他の目的、利点、および特徴は、添付の図面と併せて説明される以下に示す例示的な実施形態から、より深く理解できるようになるであろう。
【発明を実施するための最良の形態】
【００１１】
本発明を実施するための例示的なシステム
図２に、ユーザからの情報要求に基づいて文書を評価し、その結果を返すための代表的なシステム１を示す。このシステムは、バックエンドサーバ５上に実装されるプリプロセッサを含み、バックエンドサーバ５は、複数の文書発信源４の１つから文書３を受け取るためのデータストレージを有する。バックエンドサーバ５は、後の公開のために文書を評価する。図１に、バックエンドサーバを実装するのに使用できる代表的なコンピュータの構成を示す。本発明はテキスト文書の評価に限定されるものではないが、例示的な一実施形態においては、受信した文書は、「ＸＭＬ」形式のテキストを含む。ニュース文書は、世界中で新しい出来事が起こるのに伴い、例えば、ＡＰ通信、ロイター、ニューヨークタイムズ、ＣＮＮなど（代表的な情報源４）によって準備され、定期的にシステム１で利用可能にされる。
【００１２】
例示的なプリプロセッサは、バックエンドサーバ５の一部であり、バックエンドサーバ５は、Ｗｉｎｄｏｗｓ（登録商標）Ｓｅｒｖｅｒソフトウェアなどのオペレーティングシステムを実行し、また評価され、分類される多数の文書を保存するストレージを含む。受信した各ＸＭＬ文書に含まれるテキストデータは、評価され、または分類される。受信した文書からなるデータベースが、ウェブサーバ７で保持される。文書データベースの分類は、（例えば、ユーザから）入力された文書要求に、以下で説明する基準に照らして最も適切と思われる文書を公開した最新の情報で応答できるように更新される。評価または分類は、バックエンドサーバ５によって、共通性を有する文書を、文書カタログと呼ばれる複数の文書クラスタにグループ化することによって達成される。
【００１３】
図２のウェブサーバ７は、バックエンドサーバ５からのクラスタデータの更新済カタログを利用する。ウェブサーバ７は、適合度が最も高いとウェブサーバが判断したクラスタに含まれる文書が、ユーザまたは消費者８から利用できるようにする。適合度（ｒｅｌｅｖａｎｃｅ）の判断は、いくつかの基準に基づいており、その中には、ウェブサーバから利用できる特定の消費者からの情報が含まれ得る。
【００１４】
コンピュータシステム
図１に、例示的なデータ処理システムを示す。図１に示すようなデータ処理システムは、バックエンドサーバ５としても、ウェブサーバ７としても動作することができる。このシステムは、従来型のコンピュータ２０の形態をとる汎用コンピューティング装置を含み、コンピュータ２０は、１つまたは複数のプロセッシングユニット２１、システムメモリ２２、およびシステムバス２３を含み、システムバス２３は、システムメモリを含む様々なシステム構成要素をプロセッシングユニット２１に結合する。システムバス２３は、様々なバスアーキテクチャのいずれかを使用する、メモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含む複数のタイプのバス構造のうちのいずれとすることもできる。
【００１５】
システムメモリは、ＲＯＭ（読み取り専用メモリ）２４およびＲＡＭ（ランダムアクセスメモリ）２５を含む。基本入出力システム（ＢＩＯＳ）２６は、起動処理中などにコンピュータ２０内の要素間の情報伝送を助ける基本ルーチンを含み、ＲＯＭ２４に記憶される。
【００１６】
コンピュータ２０はさらに、ハードディスク（図示せず）に対して読み書きを行うハードディスクドライブ２７、取り外し可能な磁気ディスク２９に対して読み書きを行う磁気ディスクドライブ２８、ＣＤ−ＲＯＭやその他の光媒体など取り外し可能な光ディスク３１に対して読み書きを行う光ディスクドライブ３０を含む。ハードディスクドライブ２７、磁気ディスクドライブ２８、および光ディスクドライブ３０はそれぞれ、ハードディスクドライブインタフェース３２、磁気ディスクドライブインタフェース３３、および光ドライブインタフェース３４によって、システムバス２３に接続される。ドライブおよびそれに関連するコンピュータ可読媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性ストレージを、コンピュータ２０に提供する。本明細書で説明する例示的な環境は、ハードディスク、取り外し可能な磁気ディスク２９、および取り外し可能な光ディスク３１を利用するが、コンピュータによってアクセス可能なデータを保存するその他のタイプのコンピュータ可読媒体、例えば、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌイカートリッジ、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読み取り専用メモリ）なども、例示的なオペレーティング環境で利用できることは、当業者であれば理解されよう。
【００１７】
オペレーティングシステム３５、１つまたは複数のアプリケーションプログラム３６、その他のプログラムモジュール３７、およびプログラムデータ３８を含む複数のプログラムモジュールは、ハードディスク、磁気ディスク２９、光ディスク３１、ＲＯＭ２４、またはＲＡＭ２５に保存することができる。ユーザは、キーボード４０およびポインティングデバイス４２などの入力装置を介して、コンピュータ２０にコマンドおよび情報を入力することができる。その他の入力装置（図示せず）として、マイクロホン、ジョイスティック、ゲームパッド、衛星放送用パラボラアンテナ、スキャナなどを挙げることができる。上記およびその他の入力装置は、システムバスに結合されたシリアルポートインタフェース４６を介して、しばしばプロセッシングユニット２１に接続されるが、パラレルポート、ゲームポート、またはＵＳＢ（ユニバーサルシリアルバス）など、その他のインタフェースによって接続することもできる。モニタ４７またはその他のタイプのディスプレイ装置も、ビデオアダプタ４８などのインタフェースを介して、システムバス２３に接続される。モニタに加えて、パーソナルコンピュータは一般に、スピーカやプリンタなど、その他の周辺出力装置（図示せず）も含むことができる。
【００１８】
コンピュータ２０は、リモートコンピュータ４９など、１つまたは複数のリモートコンピュータへの論理コネクションを使用して、ネットワーク接続環境で動作することができる。リモートコンピュータ４９は、別のパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置、またはその他の共通ネットワークノードとすることができ、コンピュータ２０に関連して上で説明した多くのまたはすべての要素を、一般に含むことができるが、図１にはメモリ記憶装置５０だけが示されている。図１に示す論理コネクションには、ＬＡＮ（ローカルエリアネットワーク）５１およびＷＡＮ（ワイドエリアネットワーク）５２が含まれる。そのようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットで一般的である。
【００１９】
ＬＡＮネットワーク環境で使用される場合、コンピュータ２０は、ネットワークインタフェースまたはアダプタ５３を介して、ＬＡＮ５１に接続される。ＷＡＮネットワーク環境で使用される場合、コンピュータ２０は一般に、モデム５４またはインターネットなどのワイドエリアネットワーク５２を介して通信を確立するための、その他の手段を含む。モデム５４は、内蔵とも外付けともすることができ、シリアルポートインタフェース４６を介して、システムバス２３に接続される。ネットワーク化された環境では、コンピュータ２０との関連で示したプログラムモジュールまたはその部分は、リモートメモリ記憶装置に保存することができる。図示のネットワーク接続は例示的なものであり、コンピュータ間の通信リンクを確立するその他の手段も使用できることは理解されよう。
【００２０】
図３〜図５に、情報入力時にバックエンドサーバ５によって実行されるプロセスを示す。このプロセスは、３つのフェーズ、すなわち、入力フェーズ１１０、合体（coalesce）フェーズ１４０、および割り当てフェーズ１６０に分割される。入力フェーズ１１０では、コンテンツを有するデータがシステムに入力される。合体フェーズでは、例示的なシステムが、共通性のあるデータをクラスタリングし、それをデータベースに保存することによって、そのようなデータをグループ化する。割り当てフェーズでは、システムが、コンテンツのクラスタ近傍（ｃｌｕｓｔｅｒ  ｎｅｉｇｈｂｏｒｈｏｏｄ）への割り当てを行う。この割り当ても、入力コンテンツの１つまたは複数のクラスタおよび近傍について記述した記録からなるデータベースに保持される。
【００２１】
本発明の３つのフェーズが分担する作業は、２つの主要なコンポーネント、すなわち、解析コンポーネントとクラスタリングコンポーネントによって実行される。解析コンポーネントは、コンテンツ中に存在する上位Ｎ個の最も重要なトークンからなる適合度選別リスト（ｒｅｌｅｖａｎｃｅ−ｓｏｒｔｅｄ  ｌｉｓｔ）にまで、コンテンツに含まれるデータを減らす作業を担当する。この解析は入力フェーズ１１０の間に行われる。コンテンツは、テキスト、映像、音声（audio）などとすることができる。データ削減のために使用される具体的な技法は、コンテンツのタイプに依存する。クラスタリングコンポーネントは、コンテンツをクラスタに割り当て、類似のクラスタをグループ化する作業を担当する。
【００２２】
入力フェーズ１１０
テキストコンテンツ用の解析コンポーネントについて考察する。そのような解析の適用例の１つに、適合度の高いニュース記事の一覧をユーザに提供するため、ニュース解析分野（ｎｅｗｓ  ａｎａｌｙｓｉｓ  ｄｏｍａｉｎ）に関連して使用される例がある。解析コンポーネントは、単語トークンレベルで機能する。
【００２３】
トークンとは、単一の概念を表す１つまたは複数の単語であるとする。例えば、「Ｂａｌｌ」、「Ｅｘｐｌｏｓｉｏｎ」、および「Ｓｐａｃｅ  Ｓｈｕｔｔｌｅ」はすべて、単一の概念を指し示している。与えられた記事の中のテキストは、以下の方式によって、適合度で選別されたトークンの配列にまで縮小される。  
・各トークンがテキスト中に出現する場所および頻度に着目する。  
・トークンがタイトルに出現する場合、そのトークンの単語カウントにＴ回の出現を加算するとともに、そのトークンの開始位置を０に設定する。  
・トークンｉの適合度をｅｘｐ（−ａ×ｐ０ｉ）×Ｎｉ×Ｒｉに設定する。ただし、ａは、テキスト先頭からの距離の関数であるトークン適合度の減衰率（ｄｅｃａｙ  ｒａｔｅ）、ｐ０ｉは、トークンｉがテキスト中で最初に出現した位置、Ｎｉは、与えられた記事中にトークンｉが出現した回数、Ｒｉは、トークンｉの文書頻度（ｄｏｃｕｍｅｎｔ  ｆｒｅｑｕｅｎｃｙ）の逆数の対数とする。ただし、頻度は、単語が文書に１回または複数回出現した回数を代表的なコーパスに含まれる文書の数で割った数として測定される。一般に、最近の記事の収集体が、代表的なコーパスとして使用される。  
・コンテンツ毎に上位Ｋ個のトークン／適合度ペア（ｔｏｋｅｎ−ｒｅｌｅｖａｎｃｅ  ｐａｉｒ）が、クラスタリングエンジンに送られる。適合度の和は１．０に正規化される（Ｌ１ノルム（Ｌ１  ｎｏｒｍ））。
【００２４】
以下の短いニュース記事について考察する。  
Shuttle Disintegrates On Re-Entry
At 12:08 this afternoon, NASA announced that the space shuttle Discovery disintegrated as it was re-entering the earth's atmosphere.  Witnesses in a remote area of Texas saw remnants of what was believed to be the doomed shuttle disintegrate in long white plumes that extended across the blue sky.  Discovery's mission had been plagued with difficulties for the entire two weeks it had been in space.  Just yesterday, Commander Smith of Discovery was quoted by communications specialists at NASA's mission control as saying "this has been a tough ride and on behalf of my crew I want to thank you guys for all the help you have given us."  Smith along with the seven other mission specialists are presumed dead and NASA has confirmed that it has contacted the families of all eight crew members.  In the post 9/11 sensitivity to terrorist activity, NASA made it clear there was no evidence of tampering or attacks on the space craft.  President Bush has already scheduled a news conference tomorrow evening (Wednesday 8:00PM EST) and it is speculated that by the time of the new conference NASA may have more information regarding the cause of this disaster.
【００２５】
この記事の中の単語「Ｓｈｕｔｔｌｅ」について考察する。例示的なシステムでは、単語中の文字の大文字／小文字の区別は重要とは見なされないので、Ｓｈｕｔｔｌｅとｓｈｕｔｔｌｅは等価である。上述したように、用語Ｓｈｕｔｔｌｅがタイトル中に出現しているため、テキスト本文中で見つかった通常の出現頻度（ｆｒｅｑｕｅｎｃｙ  ｏｃｃｕｒｒｅｎｃｅ）に加えて、さらに出現頻度が追加されることに留意されたい。Ｔ＝２であると仮定する。このニュース記事に、用語ｓｈｕｔｔｌｅは５回出現する（実際に出現する３回と、タイトルに出現することによる２回）。さらに、「ｓｈｕｔｔｌｅ」はタイトルに出現したので、その開始位置は０に設定され、ｅｘｐ（−ａ×ｐ０ｉ）の項は１に等しくなる。
【００２６】
文書は、受信されたときすでに、その発信源によって「ニュース」文書に分類されている。その他の分類には、「スポーツ」、「娯楽」、「旅行」などがあり、またはそれらの分類のサブカテゴリがある。バックエンドサーバ上で実行されるプリプロセッサのソフトウェアは、ニュースカテゴリの文書のためのデータベースを保持する。データベースは、現在カタログされているニュース文書に含まれる数千の単語に関する文書頻度データを有する。最新のニュース記事については、ある単語の頻度が最初は低く、時間とともに高くなることもある。最近受信したニュース記事については、カタログされたすべてのニュース文書の中でＳｈｕｔｔｌｅの出現は低く、そのため、逆数の対数関数は大きくなる。これらの係数に基づいて、この記事の中で最も適合度の高いＫ個のトークンの１つが単語「ｓｈｕｔｔｌｅ」であることはかなり確実である。
【００２７】
与えられたニュース記事について、この解析の結果を、（トークン、適合度）ペアからなるサイズがＫのベクトルとして表す。ただし、Ｋは、ベクトルに含まれる前記ペアの数である。
【００２８】
【数１】
0004627656.tif 000002
【００２９】
の形式のベクトルが形成される。適合度に関して上位Ｋ個の各トークンまたは単語Ｗが、ベクトルの形成に寄与し、トークンの値Ｘは、上記の適合度算出式によって決定される。ベクトルの値は、Ｎ個の用語またはトークンの適合率Ｘｉの値の和が１．０になるように正規化される。大まかに調べてみたところでは、上位Ｎ個の用語に含まれるその他のトークンは、「ＮＡＳＡ」、「ｓｐａｃｅ」、および「Ｄｉｓｃｏｖｅｒｙ」である。
【００３０】
プリプロセッサのクラスタリングコンポーネントは、修正された「ファジーＫ平均」クラスタリング技法（“ｆｕｚｚｙ  ｋ  ｍｅａｎｓ”ｃｌｕｓｔｅｒｉｎｇ  ｔｅｃｈｎｉｑｕｅ）を利用する。Ｋ平均クラスタリングは、データの類似性に基づいてデータをグループ化するための周知のプロセスである。Ｋ平均クラスタリングは、例えば、２０００年１月に公開されたＦａｙｙａｄ他の特許文献１で説明されている。この特許の開示内容も本明細書に参照として組み込まれる。
【００３１】
クラスタリングは、データマイニング、統計データ解析、データ圧縮を含む様々な分野のアプリケーションにおいて、重要な領域となっている。普及している多くのクラスタリング技法では、基本的Ｋ平均法（Ｋ−ｍｅａｎｓ  ａｐｐｒｏａｃｈ）が用いられており、基本的Ｋ平均法では、データクラスタは初期化され、データは初期化されたクラスタに厳格な方式で追加される。すなわち、各データ項目は、１つのクラスタにしか属すことができない。本発明の例示的な実施形態では、情報コンテンツ項目または文書は、２以上のクラスタに属すことができる。
【００３２】
本発明の例示的な一実施形態では、各クラスタは、以下の情報によって表される。  
・ウェブサーバで公開するための形式をとるクラスタに割り当てられるコンテンツ項目（例えば、テキスト文書）。  
・当該クラスタを表す（適合率の和が１．０になるように正規化された）上位Ｋ個のトークン／適合度ペア。これらペアからなる組は、クラスタ平均と呼ばれる。  
・当該クラスタの上位Ｌ個の必須トークン。テキスト文書などのコンテンツの一部をこのクラスタに追加するには、コンテンツは、その上位Ｋ個のトークン／適合度ペアの中に、Ｌ個の必須トークンをすべて含まなければならない。ＬはＫより小さな数値であり、例えば、すべてのクラスタで共通の所定の固定値とすることができる。本発明の例示的な一実施形態では、Ｌの値は、文書の言語およびカテゴリに応じた値に設定される。ニュース文書を類別するためのシステムでは、値３を用いた場合に良好な結果が得られている。
【００３３】
文書は、情報源４から最初に受信されたとき、評価され、既存クラスタに割り当てられる。クラスタに割り当てることができない場合、文書は、文書を１つ含む独自のクラスタを形成する。与えられたコンテンツのトークン／適合度ペアがクラスタリングコンポーネントに入力されると、図３に示すプロセス１１０に従って以下のように処理が行われる。
・現在のコンテンツの一部が属するかもしれない候補クラスタ、すなわち、そのＬ個の必須トークンが現在のコンテンツ中に存在するクラスタをすべて検索する。  
・コンテンツと候補クラスタの間でトークン／適合度ペアの内積を計算する。内積は、２つのベクトルのドット積としても知られている。この計算によって、バックエンドサーバは、コンテンツをクラスタに追加するかどうかの判断１１２を行うことができる。  
・上記の内積が所定の閾値Ｔを超えた場合、各クラスタへのコンテンツの追加１１４が行われる。例示的な一システムでは、内積が経験的に決定された値を超えた場合、追加するよう判断が下される。この値は、グループまたはクラスタ中に妥当な数の文書を保持しながら、文書のカテゴリをどのくらい厳しく狭めるべきかに基づいて決定され、動的に変化する値とすることができる。  
・コンテンツの一部がクラスタに追加された場合、クラスタ平均が、クラスタに割り当てられたすべてのコンテンツからのすべてのトークン／適合度ペアの和を取り、上位Ｋ個のトークン／適合度ペアを選択し、その結果の和を１．０に正規化することによって再計算される。上位Ｌ個のトークン／適合度ペアから取ったトークンが、クラスタの必須トークンとなる。  
・どのクラスタも入力コンテンツと一致しない場合、そのコンテンツのために新しいクラスタが生成される。文書が１つのクラスタの平均は、Ｋ個のトークン／適合度ペアである。上位Ｌ個のトークン／適合度ペアからのトークンが、そのクラスタの必須トークンとなる。
【００３４】
合体フェーズ１４０
定期的に（本発明のニュース収集実施形態では数分毎に）、公開サイクル（Ｐｕｂｌｉｃａｔｉｏｎ  Ｃｙｃｌｅ）と呼ばれる期間中に、それまで別個のクラスタだったクラスタ同士を近傍にグループ化すべきかどうかを調べるため、クラスタがチェックされる（図４）。このプロセスは、「合体フェーズ」１４０中に行われる。入力コンテンツが属するクラスタを見つけるために用いられる同様のプロセス、すなわち、クラスタ平均の内積を決定するプロセスも、このフェーズ中に用いられる。ただし、一致が検出された場合に何が行われるかは異なる。
【００３５】
２つまたはそれ以上のクラスタを合体させる場合、クラスタ平均（正規化されたトークン／適合度ペア）は変更されない。しかし、合体の原因となったクラスタが、ペアレントクラスタとして選択される。この「クラスタのクラスタ」は、近傍（ｎｅｉｇｈｂｏｒｈｏｏｄ）と呼ばれる。近傍は、１つまたは複数のクラスタを含むことができる。
【００３６】
クラスタＢがクラスタＡに合体させられる場合、すなわち、クラスタＢがそのペアレントとしてクラスタＡを有する場合、クラスタＢをそのペアレントとして有するすべてのクラスタは、クラスタＡをペアレントとして有し、Ａと同じ近傍に属する。
【００３７】
クラスタメンバシップが変化した場合、すなわち、新しいクラスタが近傍に追加されたり、あるいはより古い近傍が失効したりした場合、それまでその近傍に割り当てられていたコンテンツ（例えば、テキスト文書）は、ヌル近傍（ｎｕｌｌ  ｎｅｉｇｈｂｏｒｈｏｏｄ）に割り当てられる（コンテンツが最初にクラスタリングシステムに入力されたときも、コンテンツはヌル近傍に割り当てられる）。上記の例では、クラスタＢがクラスタＡに合体させられる場合、ＢとＡのすべてのコンテンツは、ヌル近傍に割り当てられる。同様に、時間の経過により、近傍が失効した場合、その近傍に属するすべてのクラスタのコンテンツは、ヌル近傍に割り当てられる。近傍の失効とは、以下で説明するように、その適合度がある閾値を下回るようになったことを意味する。
【００３８】
図６Ａに示す３つのクラスタ１４２、１４４、１４６について考察する。これらの３つのクラスタは、類似した内容をもつ文書を含んでいる。しかし、３つの文書は、近傍と呼ばれるそれらの平均の内積によって測定した場合、十分には類似していない。言い換えると、クラスタの内積は、クラスタをグループ化するために設けられた閾値を超えていない。この閾値は一般に、文書をクラスタに類別するために設けられた閾値と同じものである。今、クラスタ１４８が生成され、そのクラスタに他の文書と類似した文書が追加されたと仮定する。図４のフローチャートの実行中、クラスタ１４８の選択１４１が行われ、近傍クラスタ１４２、１４４、１４６（およびより距離の離れたクラスタ）の検査１４３が行われ（クラスタ同士は、互いの内積が小さい場合、距離が離れていると見なされることに留意されたい）、４つのクラスタ１４２、１４４、１４６、１４８が、近傍１５０の生成を妥当とする十分な類似性をもつと決定される（図６Ｂ）。図４のフローチャートから分かるように、その評価が近傍を設ける原因となったクラスタ１４８が、近傍１５０のペアレントに選ばれる。
【００３９】
割り当てフェーズ１６０
コンテンツ（文書）は、入力ステージの間に複数のクラスタに割り当てられるが、近傍にはまだ割り当てられていない。
【００４０】
各公開サイクルの間に、割り当てフェーズ１６０に入る。割り当てフェーズは、コンテンツの一部をどの近傍に属させるべきかを決定する。入力フェーズの間に、コンテンツを複数のクラスタに割り当てられることを思い出されたい。図７の状況について考察する。文書１６５は、クラスタ１４８と第２の近傍１７５中の第２のクラスタ１７０に割り当てられている。したがって、場合によっては、合体フェーズ１４０の間に、コンテンツまたは文書が割り当てられたクラスタが、近傍１５０、１７５など、別個の近傍に属することがある。したがって、ユーザへの公開の際、コンテンツが属するいずれかの近傍を選択する必要がある。
【００４１】
割り当てフェーズ１６０の間、ヌル近傍に割り当てられたすべてのコンテンツが選択される。コンテンツの各部分について、記事が割り当てられた各クラスタと記事の間の内積が計算される。記事とクラスタの内積が最も大きいクラスタが属する近傍が、記事が割り当てられる近傍となる（図５参照）。２つのタイプのクラスタがあり、１つのタイプが、記事が属することのできる低レベルのクラスタであることを思い出されたい。実際、記事は、複数のそうした低レベルのクラスタに属することができる。第２のタイプは、クラスタ群のクラスタである近傍である。記事は、１つの近傍にしか属することができない。記事がシステムに取り込まれたとき、または近傍が失効した場合、または近傍が分割もしくは結合された場合、近傍中のメンバシップは０に設定される。こうすることで、システムは、どのコンテンツを再割り当てする必要があるか、すなわち、変更された近傍の１つにそれまで属していた記事を再割り当てする必要がある場合を知ることができる。システムは、上記のプロセスを用いて、記事がどのクラスタに属するかを調べ、記事をどの近傍に再割り当てすべきかを決定する。近傍が失効した場合、再割り当ては不可欠である。近傍が変更された場合、近傍に対する変更が、１つの近傍中の記事が再割り当てされる原因となることがある。
【００４２】
ユーザまたは消費者８は、文書の近傍の形式で、ウェブサーバ７から情報を所得することを望んでいる。典型的な例では、文書のこのような近傍は、Ｉｎｔｅｒｎｅｔ  Ｅｘｐｌｏｒｅｒ（ＩＥ）などのウェブブラウザや、企業のイントラネットまたはインターネットなどのワイドエリアネットワークのいずれかによってネットワーク接続されたコンピュータ上に文書を提示するのに適したその他の複数のブラウザの１つ上に提示される。図２では、ウェブサーバ７と消費者８の間の情報交換は、要求によって行われる。サーバは、適合度が最も高い近傍に含まれる複数の文書を公開することによって、そうした要求に応答する。
【００４３】
消費者８は、個々の消費者についての詳しい情報、例えば、自分のコンピュータに．ＮＥＴパスポートを用いてログオンしたかどうかといった情報を、サーバ７に提供する。消費者８から入手可能な情報には、消費者が過去にブラウザでどのような操作を行ったかといった情報が含まれる。より具体的には、提供される情報は、異なるカテゴリの文書に関連する様々なリンク上で行ったマウス「クリック」形式の過去の操作である。したがって、消費者がスポーツファンである場合、文書のカテゴリはすべて、「野球」に関連することができる。消費者が投資家である場合、文書のカテゴリは主として、「株式ニュース」関連のカテゴリとすることができる。ウェブサーバが具体的な過去の操作を識別できる方法で、ユーザが自分のコンピュータにログオンしていない場合、消費者要求は、一般的な方法で処理され、すべてのそうした一般ユーザの過去の操作に割り当てられる。
【００４４】
その他の情報をウェブブラウザ７から自動的に利用可能にすることもできる。消費者の一意のインターネットアドレスの一部として、要求の発信源を符号化することができる。その場合、消費者に対応する言語および国が、要求とともに与えられる情報の一部となり得る。具体的なクエリを、要求に含めることも可能である。したがって、消費者が最近のスペースシャトル関連の出来事に関するすべての記事に関心があることを示す直接的な指示を、要求に含めることもできる。この要求はおそらく、ウェブサーバに、先に引用したサンプルのニュース記事をユーザに送り返させることであろう。ウェブサーバ７が利用可能な情報に基づき、要求に最も適合すると判断された近傍を公開することによって、サーバ７は要求に応答する。この適合率は、文書の近傍毎にウェブサーバによって保持される。
【００４５】
近傍の適合度は、時間とともに変化する。古いニュースは、最近の出来事に関する情報を探している者にとって、あまり興味がないであろう。しかし、時間的により古い文書は、歴史や事件、場所、または人物に関する出来事の年代学に関心がある者にとっては、きわめて適合度が高いかもしれない。近傍の適合数または適合率を決定するには、記事または文書の適合度を最初に考慮しなければならない。
【００４６】
記事の適合度Ａｒを次式で与える。  
Ａｒ＝（Ａ・Ｎ）×ｅｘｐ（−ｔｌａ）×ＩＣＢａ×ＰＲａ
Ａは、記事Ａのキーワードを表すベクトルであり、ベクトルの各成分は、１つの単語に対応し、成分の大きさは、単語の適合度に対応する。  
Ｎは、記事のペアレント近傍を表すベクトルである。このベクトルは、近傍を構成するすべての文書の平均に基づいている。ＡとＮの内積（Ａ・Ｎと書かれる）は、ＡとＮの類似性の測度となる。  
ｌａは、ｔで与えられる時間の関数である記事の減衰率である。  
ＩＣＢａは、代表的な市場からユーザに提示されている記事に加重する係数である。例えば、ある記事が英国でユーザまたは消費者８に公開されており、記事の公開元または発信源４も英国にある場合、ＩＣＢａには大きな値、すなわち、１０．０が設定され、それ以外の場合、ＩＣＢａは一般に、値１．０をとる。  
ＰＲａは、大事な発信源からの記事に加重する係数である。この値は、公開元の価値を表す。例えば、ＢＢＣからの記事は一般に、無作為に選択された公開元の平均的な閲覧率（click through rate）に比べて２倍以上の閲覧率を有する。したがって、ＢＢＣからの記事のＰＲａは、値２．０をとる。
【００４７】
記事の適合度は、文書の近傍の適合度を決定するために用いられる以下に提示する計算式の中で用いられる。
【００４８】
システムに入力された記事の中には、焦点を欠いているために、決して公開されないものもある。こうした記事は、様々なトピックに関する文書であるかもしれない。記事の焦点は、記事中で最も適合度の高いキーワードの適合値によって与えられる。この値があまりにも低い場合、それは、記事が唯一のトピックを中心に書かれているという仮定が誤りらしいことを示している。したがって、その記事は、近傍に含まれるものとは見なされない。現在、値０．１が用いられている。０．０５に近い値は、焦点がまったく存在しないことを示しており、必然的に、その他のすべてのキーワードの適合度も０．０５であり、したがって、記事は焦点をもたない。
【００４９】
また、２日後、焦点を欠いているために近傍に割り当てられていない記事は廃棄される。そのような記事は、決して公開されることがない。
【００５０】
近傍の適合度Ｎｒを次式で与える。  
Ｎｒ＝ｓｕｍ（Ａｒ）×ｅｘｐ（−ｔｌｎ）×Ｓｒｎ
ｓｕｍ（Ａｒ）は、そのペアレントとして近傍Ｎを有するすべての記事のＡｒを合計したものである。  
ｌｎは、ｔで与えられる時間の関数である近傍の減衰率である。  
Ｓｒｎは、文書の異なるカテゴリからの近傍に加重する係数である。例えば、スポーツ記事にはレート１．０をもたせ、ワールドニュースにはレート１０．０をもたせることができる。Ｓｒｎ係数は、近傍のデフォルト係数でもよく、具体的なユーザまたは消費者の過去の操作から判断したその消費者の関心に基づいて割り当てることもできる。
【００５１】
近傍の適合度が、例えば、時間の経過に伴って、またはウェブサーバが受信したユーザ要求に応じて、閾値を下回った場合、その近傍のメンバーは適合度テストにもはや合格することはなく、要求に対して応答を返すことはない。
【００５２】
本発明をある程度の具体性をもたせて説明してきたが、添付の特許請求の範囲の主旨および範囲に包含されるすべての修正および変更が、本発明には含まれることが意図されている。
【図面の簡単な説明】
【００５３】
【図１】本発明の例示的な一実施形態の構成要素を実施する際に使用される代表的なコンピュータシステムを示した図である。
【図２】要求者にデータを提示するためのインターネットベースの文書検索システムを示した概略図である。
【図３】要求者の効率的アクセスのための文書分類中に実行される文書処理ステップを示したフローチャートである。
【図４】要求者の効率的アクセスのための文書分類中に実行される文書処理ステップを示したフローチャートである。
【図５】要求者の効率的アクセスのための文書分類中に実行される文書処理ステップを示したフローチャートである。
【図６Ａ】互いに関係付けられてデータクラスタの近傍が形成される文書データクラスタの概略図である。
【図６Ｂ】互いに関係付けられてデータクラスタの近傍が形成される文書データクラスタの概略図である。
【図７】クラスタのオーバラップする近傍の概略図である。
【符号の説明】
【００５４】
３  ＸＭＬ文書
４  情報源
５  バックエンドサーバ
７  ウェブサーバ
８  消費者
２１  処理装置
２２  システムメモリ
２３  システムバス
２４  （ＲＯＭ）
２５  （ＲＡＭ）
２６  ＢＩＯＳ
３２  ハードディスクドライブインタフェース
３３  磁気ディスクドライブインタフェース
３４  光ドライブインタフェース
３５  オペレーティングシステム
３６  アプリケーションプログラム
３７  その他のプログラムモジュール
３８  プログラムデータ
４６  シリアルポートインタフェース
４８  ビデオアダプタ
４９  リモードコンピュータ
５１  ローカルエリアネットワーク
５２  ワイドエリアネットワーク
５３  ネットワークインタフェース
５４  モデム
【図１】
0004627656.tif 000003
【図２】
0004627656.tif 000004
【図３】
0004627656.tif 000005
【図４】
0004627656.tif 000006
【図５】
0004627656.tif 000007
【図６Ａ】
0004627656.tif 000008
【図６Ｂ】
0004627656.tif 000009
【図７】
0004627656.tif 000010