(57)【要約】  １組のドキュメントの中から類似ドキュメントのクラスタを識別する方法が記載されている。ランク付きの１組のドキュメントの中から、ランクに基づいて、特定のドキュメントが選択され、ランク付きの１組のドキュメントは、１組のドキュメントのうちの使用可能なドキュメントの中に含まれる。特定のドキュメントに基づいて、プローブが生成される。プローブは、１つまたは複数の特徴を含む。使用可能なドキュメントの中から、プローブに基づく検索を使用して、類似条件を満たすドキュメントが見つけ出される。見つけ出された一部またはすべてのドキュメントが、ドキュメントの特定のクラスタに関連付けられる。さらにクラスタを生成するために、プロセスを繰り返すことができる。この方法は、コンピュータで実施することができ、関連するプログラミング命令は、コンピュータ可読媒体内に含めることができる。【選択図】図１
2009516307.tif 000002
【特許請求の範囲】
【請求項１】
１組のドキュメントの中から類似ドキュメントのクラスタを識別する方法であって、
（ａ）ランク付きの１組のドキュメントの中から、ランクに基づいて、特定のドキュメントを選択することと、
（ｂ）前記特定のドキュメントに基づいて、１つまたは複数の特徴を含むプローブを生成することと、
（ｃ）前記プローブに基づく検索を使用して、前記１組のドキュメントの使用可能なドキュメントの中から類似条件を満たすドキュメントを見つけ出すことと、
（ｄ）見つけ出された一部またはすべてのドキュメントを、ドキュメントの特定のクラスタに関連付けることと、
（ｅ）別のプローブを前記プローブとして使用し、別の類似条件を前記類似条件として使用して、停止条件が満たされるまでステップ（ａ）〜（ｄ）を繰り返して、ドキュメントの少なくとも１つの他のクラスタを識別することと
を含み、前記１組のドキュメントのうちの、ドキュメントのクラスタに以前に関連付けられたドキュメントが、前記使用可能なドキュメントの中に含まれない
方法。
【請求項２】
ランクに基づいて前記特定のドキュメントを選択することが、前記ランク付きの１組のドキュメントの最高位のランク付きのドキュメントを選択することを含む請求項１に記載の方法。
【請求項３】
前記特定のドキュメントに基づいて前記プローブを生成することが、前記特定のドキュメントに基づいて、および前記ランク付きの１組のドキュメントの生成に使用された特徴ベクトルに基づいて、前記プローブを生成することを含む請求項１に記載の方法。
【請求項４】
前記プローブに基づいて、および前記ランク付きの１組のドキュメントの生成に使用された特徴ベクトルに基づいて、追加プローブを生成し、ステップ（ｃ）におけるドキュメントを見つけ出すことが、前記プローブおよび前記追加プローブに基づくようにすることを含む請求項１に記載の方法。
【請求項５】
ステップ（ｃ）で見つけ出された前記ドキュメントのサブセットに基づいて新しいプローブを生成することと、
前記新しいプローブに基づく検索を使用して、前記使用可能なドキュメントの中からドキュメントを見つけ出すことと
をさらに含み、ステップ（ｄ）における前記関連付けることが、前記新しいプローブに基づく前記検索を使用して見つけ出されるドキュメントに基づく
請求項１に記載の方法。
【請求項６】
前記別の類似条件が前記類似条件と同じである請求項１に記載の方法。
【請求項７】
前記プローブが前記特定のドキュメントを含む請求項１に記載の方法。
【請求項８】
前記プローブが前記特定のドキュメントから選択された特徴のサブセットを含む請求項１に記載の方法。
【請求項９】
前記プローブが、前記１組のドキュメントのうちの複数のドキュメントから選択された特徴のサブセットを含み、前記特徴のサブセットが、前記特定のドキュメントの特徴を含む請求項１に記載の方法。
【請求項１０】
前記特定のクラスタの前記ドキュメントをランク付けし、前記少なくとも１つの他のクラスタの前記ドキュメントをランク付けすることを含む請求項１に記載の方法。
【請求項１１】
ドキュメントの前記特定のクラスタの内容を記述するプローブを使用する識別子を生成することを含む請求項１に記載の方法。
【請求項１２】
前記１組のドキュメントからの少なくとも１つの新しいドキュメントを使用して、前記プローブを修正することによって、前記プローブを改良することを含む請求項１に記載の方法。
【請求項１３】
１組のドキュメントの中から類似ドキュメントのクラスタを識別する装置であって、
メモリと、
（ａ）ランク付きの１組のドキュメントの中から、ランクに基づいて、特定のドキュメントを選択するステップと、
（ｂ）前記特定のドキュメントに基づいて、１つまたは複数の特徴を含むプローブを生成するステップと、
（ｃ）前記プローブに基づく検索を使用して、前記１組のドキュメントの使用可能なドキュメントの中から類似条件を満たすドキュメントを見つけ出すステップと、
（ｄ）見つけ出された一部またはすべてのドキュメントを、ドキュメントの特定のクラスタに関連付けるステップと、
（ｅ）別のプローブを前記プローブとして使用し、別の類似条件を前記類似条件として使用して、停止条件が満たされるまでステップ（ａ）〜（ｄ）を繰り返して、ドキュメントの少なくとも１つの他のクラスタを識別するステップと
を実行するように構成されている、前記メモリに結合されているプロセッサと
を含み、前記１組のドキュメントのうちの、ドキュメントのクラスタに以前に関連付けられたドキュメントが、前記使用可能なドキュメントの中に含まれない
装置。
【請求項１４】
ランクに基づいて前記特定のドキュメントを選択することが、前記ランク付きの１組のドキュメントの最高位のランク付きのドキュメントを選択することを含む請求項１３に記載の装置。
【請求項１５】
前記特定のドキュメントに基づいて前記プローブを生成することが、前記特定のドキュメントに基づいて、および前記ランク付きの１組のドキュメントの生成に使用された特徴ベクトルに基づいて、前記プローブを生成することを含む請求項１３に記載の装置。
【請求項１６】
前記プローブに基づいて、および前記ランク付きの１組のドキュメントの生成に使用された特徴ベクトルに基づいて、追加プローブを生成し、ステップ（ｃ）におけるドキュメントを見つけ出すことが、前記プローブおよび前記追加プローブに基づくようにすることを含む請求項１３に記載の装置。
【請求項１７】
ステップ（ｃ）で見つけ出された前記ドキュメントのサブセットに基づいて新しいプローブを生成することと、
前記新しいプローブに基づく検索を使用して、前記使用可能なドキュメントの中からドキュメントを見つけ出すことと
をさらに含み、ステップ（ｄ）における前記関連付けることが、前記新しいプローブに基づく前記検索を使用して見つけ出されるドキュメントに基づく
請求項１３に記載の装置。
【請求項１８】
前記別の類似条件が前記類似条件と同じである請求項１３に記載の装置。
【請求項１９】
前記プローブが前記特定のドキュメントを含む請求項１３に記載の装置。
【請求項２０】
前記プローブが前記特定のドキュメントから選択された特徴のサブセットを含む請求項１３に記載の装置。
【請求項２１】
前記プローブが、前記１組のドキュメントのうちの複数のドキュメントから選択された特徴のサブセットを含み、前記特徴のサブセットが、前記特定のドキュメントの特徴を含む請求項１３に記載の装置。
【請求項２２】
前記特定のクラスタの前記ドキュメントをランク付けし、前記少なくとも１つの他のクラスタの前記ドキュメントをランク付けすることを含む請求項１３に記載の装置。
【請求項２３】
ドキュメントの前記特定のクラスタの内容を記述する前記プローブを使用する識別子を生成することを含む請求項１３に記載の装置。
【請求項２４】
前記１組のドキュメントからの少なくとも１つの新しいドキュメントを使用して、前記プローブを修正することによって、前記プローブを改良することを含む請求項１３に記載の装置。
【請求項２５】
プロセッサに請求項１の方法を実行させるように構成されている処理命令を含むコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ドキュメントのコンピュータ分析に関し、より詳細には、１組のドキュメント中から類似ドキュメントのクラスタを識別することに関する。
【背景技術】
【０００２】
構造化されていない電子テキストの量が急速に増加することによって、効率的で正確なドキュメントのクラスタ化の重要性が増している。類似のドキュメントのクラスタ化によって、ユーザは、多数のドキュメントを読むことなく、大量のドキュメントの中からトピックを探ることができる。検索結果を意味のあるフラットデータまたは階層的構造にまとめることは、ユーザが、そうでなければ計り知れないデータの山となるものをナビゲートし、視覚化し、要約するのを助けることができる。
【０００３】
階層的（凝集型および分割型）クラスタリング法が知られている。階層的凝集型クラスタリング（Ｈｉｅｒａｒｃｈｉｃａｌ  ａｇｇｌｏｍｅｒａｔｉｖｅ  ｃｌｕｓｔｅｒｉｎｇ：ＨＡＣ）は、個々のクラスタとしてのドキュメントで開始し、クラスタの最も似た対を連続的にマージする。階層的分割型クラスタリング（Ｈｉｅｒａｒｃｈｉｃａｌ  ｄｉｖｉｓｉｖｅ  ｃｌｕｓｔｅｒｉｎｇ：ＨＤＣ）は、すべてのドキュメントの１つのクラスタで開始し、最小の一様なクラスタを連続的に分割する。計算の複雑度が高く（Ｏ（ｎ２）、さらにはＯ（ｎ３））、実用上拡張不可であることは、すべてのＨＡＣおよびＨＤＣ方法の問題である。
【０００４】
反復再配置に基づく区分化クラスタニング（Ｐａｒｔｉｔｉｏｎａｌ  ｃｌｕｓｔｅｒｉｎｇ）法も知られている。Ｋ個のクラスタを構築するために、区分化法は、Ｋ個すべてのグループを一度に作成し、次いで、ドキュメントをあるグループから別のグループに移動して選択された基準関数を最適化することによって、区分化を反復的に向上させる。こうした方法の主な欠点には、前もってクラスタの数を指定することの必要性、不変となる一様なクラスタ・サイズの想定、およびノイズに対する感度などがある。
【０００５】
クラスタ化のための密度ベースの区分化法（Ｄｅｎｓｉｔｙ−ｂａｓｅｄ  ｐａｒｔｉｔｉｏｎｉｎｇ  ｍｅｔｈｏｄ）も知られている。こうした方法は、クラスタを、ノイズ、すなわちどんなクラスタにも含まれていないデータ・ポイントによって囲まれた属性のスペースにおける高密度に埋められた領域として定義する。これらの方法は、主に低次元データを対象とする。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
これらおよび文献から知られている他のクラスタ化手法にもかかわらず、大量ドキュメントの効率的で正確なクラスタ化は、依然として難しい作業である。
【課題を解決するための手段】
【０００７】
本発明の１つの目的は、正確で意味のある類似ドキュメントのクラスタを生成することである。
【０００８】
本発明の別の目的は、大量ドキュメントのクラスタ化が、許容できる時間でできることである。
【０００９】
本発明の別の目的は、意味のあるラベル、要約、または他のタイプのクラスタ内容識別子を生成することができることである。
【００１０】
一態様によれば、１組のドキュメントの中から類似ドキュメントのクラスタを識別する方法は、（ａ）ランク付きの１組のドキュメントの中から、ランクに基づいて、特定のドキュメントを選択することと、（ｂ）特定のドキュメントに基づいて、１つまたは複数の特徴を含むプローブを生成することと、（ｃ）プローブに基づく検索を使用して、１組のドキュメントの使用可能なドキュメントの中から類似条件を満たすドキュメントを見つけ出すことと、（ｄ）見つけ出された一部またはすべてのドキュメントを、ドキュメントの特定のクラスタに関連付けることとを含む。また、この方法は、別のプローブを前記プローブとして使用し、別の類似条件を前記類似条件として使用して、停止条件が満たされるまでステップ（ａ）〜（ｄ）を繰り返して、ドキュメントの少なくとも１つの他のクラスタを識別することを含む。１組のドキュメントのうちの、一度別のドキュメントのクラスタに関連付けられたドキュメントは、使用可能なドキュメントの中には含まれない。
【００１１】
別の態様によれば、装置は、メモリ、およびメモリに結合されているプロセッサを含み、プロセッサは、上記の方法を実行するように構成されている。
【００１２】
別の態様によれば、コンピュータ可読媒体は、プロセッサに上記の方法を実行させるように構成されている処理命令を含む。
【発明を実施するための最良の形態】
【００１３】
図１は、１組のドキュメントの中から類似ドキュメントのクラスタを識別する例示的な方法１００を示す。クラスタは、類似性の尺度に基づいて、一緒に関連付けられるドキュメントの集まりと考えることができ、また、クラスタは、これらのドキュメントを指定する１組の識別子と考えることもできる。例示的な方法１００、および本明細書に記載されている別の例示的な方法は、図４との関連で後述されるような、プロセッサおよびメモリを含む任意の適したコンピュータ・システムを使用して実施することができる。
【００１４】
本明細書で言及されるドキュメントは、１つまたは複数の文字列を含むテキスト、および／またはそれだけには限定されないが、画像、グラフィックス、ハイパーリンク、表、チャート、スプレッドシート、または他のタイプの視覚情報、数値情報、テキスト情報など、オブジェクトに組み込まれている別個の特徴を含む。例えば、文字列は、単語、句、文、段落を形成することができる。ドキュメントに含まれる構文は、任意の特定の言語に関連付けられている構文または形式に限定されない。特徴例には、ドキュメントにおけるフィールド、節、段落または表の数などの構造的な特徴、ドキュメントの画像における「暗い」領域に対する「白い」領域の比率やカラー・パターンなどの物理的な特徴、注釈の特徴、すなわち注釈の有無や、ドキュメントの特定のフィールドに記録された、または人間または機械による処理の結果としての注釈の値、潜在意味解析および他の特徴の組合せなど、変換関数から生じたものなどの派生した特徴、および当業者には明らかな他の多くの特徴などがある。
【００１５】
また、処理の目的のドキュメントは、システムがソース・ドキュメントとして使用できる文字ドキュメント（例えば全ドキュメント）、任意のサイズのサブドキュメント、単一のソース・ドキュメントから導出されたか、多くのソース・ドキュメントから導出されたかにかかわらず、単一のエンティティ（ドキュメント）として処理されるサブドキュメントの集まり、およびサブドキュメントと混合される場合があり、単一のエンティティ（ドキュメント）として処理されるドキュメントの集まりまたはグループ、および上記の任意の組合せとして定義することができる。サブドキュメントは、例えば、個々の段落、所定の行数のテキスト、または全ドキュメントの他の適した部分とすることができる。サブドキュメントに関する説明は、例えば、米国特許第５，９０７，８４０号および米国特許第５，９９９，９２５号で見つけることができ、そのそれぞれの全内容は、この参照により、本明細書に組み込まれる。
【００１６】
図１の例では、ステップ１０２で、ランク付きの１組のドキュメントから、ランクに基づいて、特定のドキュメント（便宜上、「ドキュメントＳ」と呼ぶ）が選択される。ランク付きの１組のドキュメント（例えばランク付きリスト）は、任意の適した方法で取得することができる。例えば、ランク付きの組は、対応するドキュメントについての得点を生成する、ドキュメントの任意のソースに対する任意の適したクエリから生成することができる。ランク付きの１組のドキュメントは、例えば１組のドキュメントに対する任意の適したクエリに基づいて、クラスタを生成するための１組のドキュメントから選択する、または（クラスタ化されるべき１組のドキュメントの中に、ランク付きの１組のドキュメントがないように）クラスタ化されるべき１組のドキュメント以外のドキュメントのソースから選択することができる。クエリは、単一のデータベースまたは複数のデータベースに対して行うことができ、また、任意の適した検索エンジンを使用して、インターネットを介するなどして、分散されたドキュメントのソースに対して行うことができる。あるいは、ランク付きの組は、人の手によって選択され、最も関連があるものから最も関連がないものまで、何らかの選好の順にランク付けされた１組のドキュメントとすることができる。特定のドキュメントＳは、これらのドキュメントのうちの最高位のものとして、または例えばランク順における別の位置から（例えば平均を中心とした、または平均を上回る所定のスコア範囲から）選択することができる。
【００１７】
ステップ１０４で、特定のドキュメントＳに基づいて、プローブＰが生成される。プローブは、１つまたは複数の特徴を含むことができ、任意の適した方法で生成することができる。例えば、プローブはドキュメントＳのテキストからの用語が、本明細書の他の場所に記載されているように、ドキュメントＳの任意の特徴に結合されることにより、ドキュメントＳ自体を含むことができる。別の例として、プローブは、特定のドキュメントＳの特徴（用語など）の重み付けされた（または重み付けされていない）組合せなど、特定のドキュメントＳから選択された特徴のサブセットを含むことができる。別の例として、プローブは、複数のドキュメントの特徴（用語など）の重み付けされた（または重み付けされていない）組合せなど、複数のドキュメント（特定のドキュメントＳを含む）から選択された特徴のサブセットを含むことができる。
【００１８】
また、ステップ１０４で、プローブＰは、任意選択で、ドキュメントＳ、およびランク付きの組の形成に使用された特徴ベクトルの両方に基づいて形成することができるように考慮される。特徴ベクトルは、例えば、ランク付きの１組のドキュメントの生成に使用されたクエリの特徴（例えば用語）の一部またはすべてとすることができる。例えば、プローブＰは、ドキュメントＳの特徴（例えば用語）の一部またはすべて、および特徴ベクトルの特徴（例えば用語）の一部またはすべての組合せ（例えば重み付きの組合せ）とすることができる。ドキュメントＳに基づいた、およびランク付きの組の形成に使用された特徴ベクトルに基づいたプローブＰの形成に、多くの手法を使用することができることを、当業者であれば理解されたい。
【００１９】
一般に、１つまたは複数のドキュメントに基づいて適したプローブを形成することは、ドキュメントの特徴を識別し、特徴を採点し、得点に基づいていくつか（場合によってはすべて）の特徴を選択することによって、達成することができる。別の言い方をすれば、プローブの形成は、ドキュメント内の特徴をどのように識別するか、およびこうした用語または特徴をどのように採点するか、または重み付けするかを指定する方法Ｍを使用してドキュメントの組｛Ｄ｝（１つまたは複数のドキュメント）からプローブＰを作成するプロセスとみなすことができ、この場合、プローブは、プローブが本当に形成されるべきか、そうである場合、どの特徴または用語をプローブが含むべきかを決定するテストＴを満たす。プローブを形成するために、１つのドキュメント（または複数のドキュメント）の個別の特徴を識別し、こうした特徴のすべてまたは一部を選択することは、当業者が適宜なし得ることである。例えば、ドキュメント・テキストを構文解析して、指定された言語タイプの句（名詞句など）を識別すること、構造的な特徴（ドキュメント内のフィールド、節、段落、または表の数など）を識別すること、物理的な特徴（ドキュメントの画像における「暗い」領域に対する「白い」領域の比率やカラー・パターンなど）を識別すること、注釈の有無や値を含む注釈の特徴を識別することは既知である。こうした特徴は、識別されると、既知の方法を使用して採点され得る。一例は、単に、所与の識別された特徴の出現数を数え、各出現数を識別されたすべての特徴の総出現数に正規化し、正規化された値をその特徴の得点になるように設定することである。所与のドキュメントに対し、識別された特徴の得点に応じプローブをまったく形成しないことが決定されてもよい（例えば、得点のすべてまたは得点の組合せが閾値を割り込むため）。特徴のサブセットの選択は、例えば、所与の閾値を上回る（例えば識別された特徴の平均得点を上回る）得点を取る特徴を選択することによって、または所定の数（１０、２０、５０、１００など）の最高得点の特徴を選択することによって行うことができる。この場合、他の例を使用することができることは、当業者によって理解される。特徴のサブセットが選択されると、必要に応じて、所与の特徴の出現数をサブセットの特徴についての総出現数に再度正規化することによって、これらの特徴に重み付けすることができ、それによってプローブを提供する。
【００２０】
上記で示唆したように、プローブとして使用する（１つのドキュメントまたは複数のドキュメントからの）特徴のサブセットの一例は、その全内容が参照により本明細書に組み込まれる、例えばＥｖａｎｓらの２００３年１１月１４出願の米国特許出願公開第２００４／０１５８５６９号に記載されているものなど、テキストの用語の用語プロファイル（ｔｅｒｍ  ｐｒｏｆｉｌｅ）とすることができる。用語プロファイルを生成する１つの典型的な方法は、テキストを構文解析し、指定された言語タイプ（名詞句など）の任意の句、または句における任意の単語を特徴として扱うことである。こうした特徴または検索語に、当業者に知られている様々な代替方法の１つによって重みを割り当てることができる。例えば、１つの方法は、処理されたテキストの１単位においてｔの観察された頻度（「ＴＦ」）と、処理された使用可能なすべての単位にわたるｔの分布数の逆数の対数（「ＩＤＦ」）とを掛けたものを反映する重みを用語「ｔ」に割り当てる。こうした「ＴＦ−ＩＤＦ」得点は、ドキュメントを処理単位とし、用語ｔが少なくとも一度出現するデータベース内のドキュメントの数に基づいた分布数を使用することによって算出することができる。プロファイルの特徴を提供するために使用され得る（例えば、１つのドキュメントまたは複数のドキュメントからの）任意の組のテキストに対して、抽出された特徴は、その所与のテキスト自体において観察される統計（頻度および分布など）を使用することによって重みを導出することができる。あるいは、テキストの組の用語に対する重みは、ドキュメントの参照コーパス（ｒｅｆｅｒｅｎｃｅ  ｃｏｒｐｕｓ）からの統計に基づき得る。言い換えれば、その所与のテキストからの観察された頻度および分布数を使用する代わりに、テキストの組における各特徴は、その頻度を参照コーパスにおける同じ特徴の頻度に設定し、その分布数を参照コーパスにおける同じ特徴の分布数に設定してもよい。あるいは、テキストの組において観察された頻度を使用し、しかし分布数を参照コーパスから取るなど、テキストの組に観察される統計を、様々な組合せにおける参照コーパスからの統計と共に使用してもよい。ドキュメント例からの特徴の最後の選択は、用語をランク付けする、特徴により採点する機能によって決定することができる。多くの可能な採点機能または用語選択機能が使用されてもよく、これらは当業者には知られている。一例では、よく知られている「Ｒｏｃｃｈｉｏ」採点手法から導出された以下の採点機能を使用することができる。
【００２１】
【数１】
2009516307.tif 000003
【００２２】
ここで、ドキュメントの組における用語「ｔ」の得点Ｗ（ｔ）は、ドキュメント（またはサブドキュメント）の組、または参照コーパスにおける用語ｔの逆文書頻度（ｉｎｖｅｒｓｅ  ｄｏｃｕｍｅｎｔ  ｆｒｅｑｕｅｎｃｙ：ＩＤＦ）、プローブ形成のために選択された所与のドキュメントＤにおけるｔの頻度数ＴＦＤ、およびプローブの形成のために選択されたドキュメント（またはサブドキュメント）の総数Ｎｐに応じて決まり、プローブを形成するために選択されたすべてのドキュメント（またはサブドキュメント）に対して総和がとられる。ＩＤＦは、以下のように定義され、
ＩＤＦ（ｔ）＝ｌｏｇ２（Ｎ／ｎｔ）＋１
式中、Ｎは、その組におけるドキュメントの数、ｎｔは、ｔが出現するドキュメント（またはサブドキュメント）の数である。
【００２３】
得点がドキュメントの組における特徴に割り当てられると、特徴をランク付けすることができ、特徴のすべてまたは一部を、その組についての特徴プロファイルに使用するために選択することができる。例えば、最高位の用語が特徴プロファイルに使用されるように、特徴プロファイルについての所定の数（１０、２０、５０、１００など）の特徴を、得点の降順に選択することができる。
【００２４】
任意選択であるステップ１０５では、例えば上述したように、プローブＰに基づいて、およびランク付きの１組のドキュメントの形成に使用された特徴ベクトルに基づいて、追加プローブＰ’を生成することができる。例えば、追加プローブＰ’は、プローブＰの特徴の一部またはすべて、および特徴ベクトルの特徴の一部またはすべての組合せ（例えば重み付きの組合せ）とすることができる。次いで、追加プローブＰ’を、使用可能なドキュメントに対するクエリとして使用することができる。追加プローブＰ’は、前のプローブＰに基づいているため、こうした検索は、両方のプローブに「基づく」ことを理解されたい。
【００２５】
ステップ１０６で、プローブ（Ｐ，Ｐ’）に基づく検索を使用して、使用可能なドキュメントの中から、類似条件を満たすドキュメントを見つけ出す。一度別のドキュメントのクラスタに以前に関連付けられたドキュメントは、使用可能なドキュメントの中には含まれない。例えば、プローブ自体（例えば、用語のプロファイル）を、使用可能なドキュメントに対するクエリとして使用することができる。類似条件を満たすドキュメントは、便宜上「類似ドキュメント」と呼ぶことができる。この関連で、適したプロセス（便宜上、類似性プロセス（ｓｉｍｉｌａｒｉｔｙ  ｐｒｏｃｅｓｓ）と呼ぶ）を使用して、プローブと別のドキュメントとの間の近さまたは類似性の尺度（類似性得点（ｓｉｍｉｌａｒｉｔｙ  ｓｃｏｒｅ））を生成することができ、近さの尺度を評価して、それが類似条件を満たすか、例えば所定の閾値を満たすか、または超えるかを決定することができる。必要な場合、ゼロ以外の任意の類似性得点を有するドキュメントが類似とみなされるように、閾値をゼロに設定する、または閾値をより高い値に設定することができる。一般に、本明細書に記載されている他の閾値と同様に、類似性得点に適した閾値を決定することは、当業者が適宜なし得る事であり、例えば、サンプルまたは参照ドキュメントの組において類似性プロセスを実行して、どの閾値が許容できる結果を生成するかを評価することによって、類似性の実行中に得られた結果を評価し、必要な任意の調整を行う（例えば、識別された類似ドキュメントの数が十分であるかに基づきフィードバックが使用される）ことによって、または経験に基づいて行うことができる。本明細書で言及されるように、類似性は、ある参照ドキュメントまたはプローブと別のドキュメントまたはプローブとの間の近さまたは類似性の尺度とみなすことができる。類似性プロセスは、２つのベクトルの類似性を測定するプロセスとみなすことができる。さらに、対応するドキュメントの類似性得点を、例えば対応するドキュメントの最高得点のドキュメントの類似性得点に、当業者には明らかに適した他の方法によって正規化することができる。
【００２６】
ドキュメントＳがステップ１０６でプローブを使用して「検索された」ものの中にあり得るように、ドキュメントＳは、使用可能なドキュメントのうちの１つとすることができることを理解されたい。あるいは、プローブが少なくとも部分的にドキュメントＳに基づいているため、（ドキュメントＳが使用可能なドキュメントのうちの１つである場合において）プローブを使用した検索にドキュメントＳを含める必要はない。というのは、ドキュメントＳは、形成される特定のクラスタ内のドキュメントのうちの１つであると想定することができるからである。ドキュメントＳが使用可能なドキュメントのうちの１つである場合、これらの可能性はいずれも、本明細書において、「使用可能なドキュメントの中からプローブを使用して類似条件を満たすドキュメントを見つけ出す」という言い回し、または類似の言い回しによって包含されるものとする。但しもちろん、上述したように、ドキュメントＳが使用可能なドキュメントのうちの１つである必要はない。
【００２７】
２つのベクトル（プローブとドキュメントなど）の間の類似性を評価する様々な方法が当業者に知られている。一例では、米国特許出願公開第２００４／０１５８５６９号に記載されている、ベクトル空間型採点手法（ｖｅｃｔｏｒ−ｓｐａｃｅ−ｔｙｐｅ  ｓｃｏｒｉｎｇ  ａｐｐｒｏａｃｈ）が使用され得る。ベクトル空間型採点手法では、得点は、プロファイル（またはクエリ）ＱとドキュメントＤとの間の類似性を比較し、すべての用語の直交空間にわたるその共有および互いに共有されない用語を評価することによって生成される。こうしたプロファイルは、上記のプローブに似ている。例えば、類似性得点は、（当業者に知られている多くの代替の類似度関数を使用することもできるが）以下の式によって算出することができる。
【００２８】
【数２】
2009516307.tif 000004
式中、Ｑｉは、プロファイルにおける用語を指し、Ｄｊは、ドキュメントにおける用語を指す。上記の式（または当分野で知られている同様の式）を評価することによって、類似性の数値的尺度（例えば、小数として表される）を提供する。次いで、上述したように、それが類似条件を満たすか、例えば所定の閾値を満たすか、または超えるかを決定するために、類似性のこうした尺度を評価することができる。したがって、ステップ２０６で見つけ出された類似ドキュメントが、プローブＰに対する類似性に関して、類似ドキュメントをランク付けすることができる得点を有することができることを理解されたい。
【００２９】
ステップ１０８で、類似条件（類似性ドキュメント）を満たすドキュメントの一部またはすべてが、ドキュメントの特定のクラスタに関連付けられる。関連付けは、例えば、適切なポインタ、マーク、フラグ、または他の適したインジケータなどを使用して、ドキュメントの組を格納する同じデータベース、または異なるデータベースに、類似条件を満たすドキュメントの状況を記録することによって行うことができる。例えば、ドキュメントの組のタイトルおよび／または適した識別コードのリストを任意の適した方法（リストなど）で格納することができ、所与のドキュメントについて、データベース内の適切なフィールドをマークして、それが属するクラスタを識別することができる。それは、例えば、クラスタ番号、および／またはクラスタに適した記述的タイトルまたはラベルなどによって識別される。また、クラスタのドキュメントを、必要に応じて、データベース内のそれ自体のリストに記録することができる。クラスタとの関連付けの目的で、ドキュメント自体の内容のすべてを記録または格納する必要はなく、むしろ、特定のドキュメントを特定のクラスタに関連付けるために使用される情報は、例えば、それが関連付けられるクラスタと同様に、所与のドキュメント自体を識別するに適した識別子を含むことができることを理解されたい。特定のクラスタは、類似ドキュメントのみを含むことができる、または、特定のクラスタは、類似ドキュメント以外に追加のドキュメントを含むこともできる（例えば、方法１００を開始する前に、少なくともいくつかの他のドキュメントを、クラスタに関連付けるべきであることがわかっている場合において）。この態様は、本明細書に開示された任意の方法によって識別されるクラスタに適用可能である。
【００３０】
上述したように、ステップ１０６で識別された類似ドキュメントのすべてではなく、ステップ１０８で一部のみをクラスタに関連付けることができる。類似ドキュメントのすべてではなく、一部を識別することは、様々な手法を使用して達成することができる。例えば、所定の割合の最高位の類似ドキュメントを識別する（例えば、上位８０％、上位７０％、上位６０％、上位５０％、上位４０％、上位３０％、上位２０％など）ことができ、類似ドキュメントの得点をステップ１０６で決定することができることを理解されたい。別の例として、別のより厳しい類似条件（例えば、ステップ１０６で言及したものより高い閾値）を課すことによって、すべてより少ない類似ドキュメントを選択することができる。また、例えば、境界をクラスタの質（クラスタ内のドキュメントの類似性）および指定された所望のクラスタ精度に応じて定義することによって、類似ドキュメントの「クラスタ境界」が生成される場合、境界内の類似ドキュメントのみがクラスタ内にあるように選択することができる。クラスタとの関連付けのために類似ドキュメントのすべてより少ない数で識別する他の手法を使用することもできることを理解されたい。
【００３１】
ステップ１１０で、停止条件が満たされるかどうかが決定される。例えば、ドキュメントの組全体がクラスタ化された後、所定の数のクラスタが作成された後、ドキュメントの組の中の所定の割合のドキュメントがクラスタ化された後、最低限の所定のサイズの所定の数のクラスタが作成された後、または所定の時間間隔を超えた後、方法１００を停止することができる。当業者によって理解されるように、他の条件を使用することもできる。停止条件が満たされない場合（すなわち、クラスタ化は続行するはずである）、ステップ１０２〜１０８が繰り返されて、少なくとも１つの他のクラスタを形成する。この場合には、異なるドキュメントＳから別のプローブが生成され、新しいクラスタについて類似ドキュメントを見つけ出すために、別の類似条件が使用される。次の反復の他の類似条件は、前の類似条件と同じであってもよく、または、前の類似条件と異なっていてもよい。クラスタ化の前の反復に関連するドキュメントの削除を補うために、反復が進むにつれて、類似条件を変更する（例えば上げるまたは下げる）ことが望ましい場合がある。クラスタに関連付けられているドキュメントが、もはや使用可能なドキュメントであるとみなされないように、クラスタ形成の各反復で、どのドキュメントが「使用可能であるか」の状況を更新することができる。ランク付きの１組のドキュメントのうちのドキュメントが、クラスタ化される１組のドキュメントのうちのドキュメントの中にある場合、クラスタに関連付けられている任意のドキュメントを、ランク付きの１組のドキュメントから削除することができる。ランク付きの組のドキュメントが、１組のドキュメントの中にない場合、ドキュメントＳは、クラスタ形成の別の反復において、ランク付きの組から選択されないように、「使用済み」とマーク付けすることができる。任意選択として、ランク付きの１組のドキュメントが、クラスタ化される１組のドキュメントの中にない場合においても、クラスタが生成されることのよるランク付きの組の所与のドキュメントＳを、そのクラスタに追加することができる。
【００３２】
必要に応じて、ある所与のクラスタが識別されると、その所与のクラスタの類似ドキュメントをランク付けすることができる（例えば、データベースにおいてランク順で列挙されるなど）。上述したように、得点または重みを生成する方法を使用して類似ドキュメントを見つけ出すことによって、自動的にランキング情報を提供することができる。また、方法１００は、所与のクラスタの内容を記述する識別子（便宜上、「内容識別子」と呼ぶ）を提供することを含み得る。例えば、所与のクラスタの最高位のドキュメントのタイトルを、内容識別子として使用することができる。別の例として、プローブのすべてまたは一部の用語（または特徴の記述）を内容識別子として使用することができ、または別の類似条件を満たす複数の似通ったドキュメントから生成された新しいプローブのすべてまたは一部の用語を内容識別子として使用することができる。これらの態様は、本明細書に開示されている他の例示的な方法にも適用される。
【００３３】
上述したように、ドキュメントＳは、ランク付きの１組のドキュメントから選択され、上述したものや、当業者に理解できるものなどを含めて、こうしたランク付きの組を生成する様々な方法が使用され得る。こうしたランク付きの組（ランク付きリストなど）を生成する別の例示的な方法は、ドキュメントの組に対する複数のクエリに基づき得る。特に、ドキュメントの組におけるドキュメントのすべてまたは一部について、ドキュメントの組に対して、そのドキュメントから形成されたプローブを使用して、クエリを実行することができ、その類似性得点に従ってランク付けされた対応するドキュメントのリストが得られる。対応するドキュメントの組ごとに、例えば、対応する各ドキュメントの得点を合計する、または平均応答得点（ａｖｅｒａｇｅ  ｒｅｓｐｏｎｓｅ  ｓｃｏｒｅ）を計算することなどによって、対応するドキュメントの総得点を生成することができる。次いで、この総得点を、そのプローブが対応するドキュメントの所与の組を生成した特定のドキュメントに関連付けることができる。次いで、これらの総得点を、ランク付けし、最高の総得点に対して正規化することができる。次いで、関連の総得点が所定の閾値を上回るドキュメントを、ドキュメントのクラスタを形成するためのランク付きの１組のドキュメントとして選択することができ、この場合、ランク付きの１組のドキュメントの最高位から始まり、より低い順位のランク付きの１組のドキュメントに進むように、ランク付きの１組のドキュメントから、個々のドキュメントＳを選択することができる。
【００３４】
本発明の別の態様によれば、図２は、類似ドキュメントのクラスタを識別する例示的な方法２００を示す。ステップ２０２〜２０６は、上述したステップ１０２〜１０６に似ており、これらのステップをさらに説明する必要はない。ステップ２０６の時点で、１組の類似ドキュメントが、プローブ（ＰまたはＰ’であり、この場合、Ｐ’はＰに基づく）を使用して識別されている。
【００３５】
プロセスは、ステップ２０６からステップ２１２に進み、一般にドキュメントＳを含む類似ドキュメント（類似ドキュメントのサブセット）の似通ったドキュメントに基づいて、新しいプローブが形成される。プローブを形成するための本明細書に上述した任意の方法（または他の適した手法）を、ステップ２１２で使用することができる。新しいプローブＰの形成に使用される「似通ったドキュメント」（本明細書で便宜上使用されるラベル）は、類似ドキュメント（ステップ２０６で見つけ出された）のうちの、別の類似条件（例えば類似ドキュメントの識別に使用されるものより厳しい閾値、所定の数または割合の最高位の類似ドキュメントなど）を満たすドキュメントとすることができる。ステップ２０６で見つけ出された類似ドキュメントは、すでにランク・スコアを有することができるので、これらの得点を考慮して、似通ったドキュメントを、単にそういうものとして指定することができる。言い換えれば、個別のクエリまたは他のタイプの検索は、似通ったドキュメントを識別するのに必要ない。
【００３６】
ステップ２１４で、新しいＰを使用して、使用可能なドキュメントの中から、類似条件を満たすドキュメントを見つけ出す。新しい類似ドキュメントは、新しいプローブＰを使用して見つけ出されることを考慮に入れて、ステップ２０６で見つけ出された「類似ドキュメント」との混乱を避けるために、これらのドキュメントを、便宜上「新しい類似ドキュメント」と呼ぶことができる。ステップ２１４は、例えば図１および図２のステップ１０６および２０６との関連で示したように行うことができる。
【００３７】
本明細書に記載された他の例示的な方法に当てはまることだが、クラスタ形成の反復が進むにつれて、ステップ２０６および２１４の類似条件が変わり得る。例えば、ステップ２１４の類似条件の初期値は、ドキュメントＳの近傍におけるオブジェクト密度、および任意選択で、指定された最小クラスタ・サイズに応じて決まり得る。効果は、プローブに似たいくつかのドキュメントを選択することである。例えば、類似条件の閾値は、フィードバック（例えば、クラスタ形成が予想を満たしているかどうかなど）に基づいて調整したり、反復に応じて所定の量だけ変更したりすることができる。例えば、クラスタ化の進行に伴う類似ドキュメントの除去を補うために、反復が進むにつれて、類似条件を上げる、または下げることができる。類似条件を上げることは、クラスタ化が進むにつれて、より正確なクラスタを達成するために行うことができ、類似条件を下げることは、いくつかのクラスタが得られた後、またはいくつかの割合のドキュメントの組がクラスタ化された後、完了までのプロセスを速めるために行うことができる。また、ステップ２０６および２１４は、それぞれ類似条件について言及しているが、これらの類似条件は、同じであってもよく、または同じでなくてもよいことも理解されたい。これらのコメントは、本明細書に記載されている他の例示的な方法にも適用可能である。
【００３８】
ステップ２０８で、ステップ２１４で識別された類似ドキュメントの一部またはすべてがクラスタと関連付けられる。このステップは、図１のステップ１０８との関連で説明したように実行することができる。類似ドキュメントのすべてではなく一部を識別または選択するためのステップ１０８との関連で説明した方法に加えて、「似通ったドキュメント」を識別するための上記の任意の手法を使用して、クラスタに関連付けるための類似ドキュメントの一部を選択することができる。
【００３９】
ステップ２１０で、停止条件が満たされるかどうかに関する決定が行われる。このステップは、図１のステップ１１０に似ており、さらに説明する必要はない。停止条件が満たされる（すなわち、それ以上のクラスタ化は必要とされない、または望まれない）場合、プロセスは終了する。停止条件が満たされない場合、プロセスは、図２のステップ２０２に戻り、上述したようにステップ２０２〜２１４が繰り返される。
【００４０】
図３は、類似ドキュメントのクラスタを識別するための例示的な方法３００を示す。ステップ３０２〜３１４は、それぞれ図２のステップ２０２〜２１４に似ており、初めての事柄としてこれらのステップをさらに説明する必要はない。図３は、ステップ３１６〜３２６を追加する。
【００４１】
ステップ３１６で、必要に応じて、新しい類似ドキュメントの類似性得点が適切に記録または更新される（例えばデータベースにおいて保存／更新され、これは、ドキュメントの組に関するクラスタ化情報を維持する同じデータベース、または異なるデータベースとすることができる）。これらの類似性得点は、上述したように、類似ドキュメントを見つけ出すプロセス例によって提供することができる。任意選択で、新しい類似ドキュメントを、その類似性得点に従ってソートすることができる。これらのドキュメントは、便宜上「得点付きドキュメント」と呼ぶことができるが、上述したように、新しい類似ドキュメントであるとも考えられることを理解されたい。ステップ３１２と３２６との間のループを考慮すると、類似ドキュメント（または新しい類似ドキュメント）として見つけ出された所与のドキュメントが数回採点される可能性がある。所与のドキュメントがすでに採点されており、ループの任意の反復において、新しい得点を受信する場合、新しい得点を追加することができ、そうでない場合、そのドキュメントについての古い得点に累積することができ、そのドキュメントに関連付けられた累積された得点は、累積された得点を記録することによって、更新することができる。
【００４２】
ステップ３１８で、実質的にこの段階における候補クラスタである所与の組の得点付きドキュメントがクラスタ条件を満たすかどうかを決定する。クラスタ条件が満たされる場合、プロセスは、ステップ３０８に進み、ここで、本明細書に上述したように、得点付きドキュメント（新しい類似ドキュメント）の一部またはすべてがクラスタに関連付けられる。次いでプロセスは、ステップ３１０に進んで、クラスタを停止するかどうかを決定する。
【００４３】
ステップ３１８でクラスタ条件が満たされていない場合、プロセスは、ステップ３１８からステップ３２０に進む。ステップ３２０で、ドキュメントがプローブを形成するために以前使用されていないことを意味する「使用済み」とマーク付けされていない限り、ステップ３１４で識別された新しい類似ドキュメントから、新しいドキュメントＳが選択される（例えば、新しいドキュメントＳは、新しい類似ドキュメントの最高位のもの、または例えば本明細書の別の場所に記載されている別の条件を満たすドキュメントとすることができる）。ステップ３２２で、本明細書に記載したものなど、プローブ形成のための任意の適した方法を使用して、新しいドキュメントＳに基づいて、新しいプローブＰが形成される。ステップ３２４で、類似条件を満たすドキュメントが、例えば本明細書の別の場所に記載されているように、使用可能なドキュメントの中から、Ｐを使用して見つけ出される。ステップ３２６で、新しいドキュメントＳは、「使用済み」としてマーク付けされるか、ステップ３１２〜３２６のその後の反復で再度使用されないように、ドキュメントＳがプローブの形成に以前使用されたことを示すための任意の他の適した方法でフラグが立てられる（ステップ３２６は、ステップの順序における異なる場所で行うことができる）。次いで、これらの結果として得られた類似ドキュメントは、ステップ３１２への入力として使用され、すなわち、これらを、ステップ３１２で言及される「似通ったドキュメント」として使用することができる、または、ステップ３２４で見つけ出された類似ドキュメントのサブセットを、ステップ３１２の「似通ったドキュメント」として使用することができる。ステップ３１２で、ステップ３２４から新しく見つけ出された類似のまたは似通ったドキュメントに基づいて、別の新しいプローブＰが形成される。次いで、ステップ３１２〜３１８が上述したように実行され、クラスタ条件が依然として満たされない場合、プロセスは、ステップ３１２に再度入力を提供するために、ステップ３２０〜３２６に再度進む。ステップ３１２〜３２６間のループは、改良されたプローブを形成するために少なくとも１つの新しいドキュメント（一般に１つを超える）を使用してプローブが繰り返して改良され、新生クラスタが改良されるプロセスとみなすことができる。
【００４４】
このプロセスにおけるステップ３１８で、任意の様々なクラスタ条件を使用することができる。例えば、新生クラスタのドキュメントのすべて（すなわちステップ３１４で見つけ出されたもの）が、ステップ３２０で新しいドキュメントＳとして使用されているかどうかという１つのクラスタ条件が可能である。ｙｅｓの場合、プロセスは、ステップ３０８に進み、ステップ３１２〜３２６にわたるループが終了する。別の例として、ステップ３１２〜３２６のループにわたる所定の数の反復の後、新生クラスタのサイズが飽和した（例えばＮ個の連続したループは、ステップ３１４で新しいドキュメントを見つけ出さない）かどうかというクラスタ条件が可能である。別の例として、ステップ３１２〜３２６のループにわたる所定の数の反復が起こったかどうかというクラスタ条件が可能である。当業者によって理解されるように、他の条件を使用することもできる。
【００４５】
さらに、ステップ３１４の類似条件は、例えば本明細書の他の場所に記載されているように、変更することができる（例えば、条件の閾値は、フィードバックに基づいて調整したり、クラスタ化操作の反復に応じて、所定の量だけ変更したりすることができる）。さらに、ステップ３１２〜３２６のプローブ／クラスタ改良ループを考慮して、ステップ３１４での類似条件をさらに調整することが望ましい場合がある。特に、ステップ３１４〜３２６のプローブ／クラスタ改良ループの所与の反復における得点付きドキュメントの得点プロファイルに応じて、ステップ３１２で使用される類似条件をさらに調整することが望ましい場合がある（例えば、クラスタ条件の閾値を、得点付きドキュメントの得点プロファイルに応じて、正または負の量だけ増分することができる）。
【００４６】
ステップ３０８に関して、クラスタに含めるための得点付きまたは類似ドキュメントのすべてではなく、一部のみを選択するための様々な手法を説明してきた。上述した１つの手法は、得点付きドキュメントの「クラスタ境界」にあるドキュメント（新生クラスタであると考えることができる）を検出し、これらがクラスタに関連付けられないように、こうしたドキュメントを取り除くことを伴う。図３の情況において、クラスタ境界にあるドキュメントを、例えばステップ３１２〜３２６の反復にわたるクラスタ改良プローブ応答（ｃｌｕｓｔｅｒ  ｒｅｆｉｎｉｎｇ  ｐｒｏｂｅ  ｒｅｓｐｏｎｓｅ）のある割合未満にみられるドキュメントとして識別することができる。これらの境界ドキュメントは、クラスタに関連付けられないように、取り除くことができる。
【００４７】
本明細書に記載された例示的な方法は、既知のクラスタ化手法に比べて顕著な利点があり得る。例えば、クラスタ化のためにプローブを生成するドキュメントの選択に、無作為な選択が使用される場合、無作為に選択されるドキュメントは、ドキュメントの組のより大きい主題グループの１つのメンバーである可能性があるため、最も整合性のある最大のクラスタが最初に生成される傾向がある。シード・リストが確立された場合、プローブを生成するための最高の（または高順位の）シード・ドキュメントを選択することも、最初に最大で最も整合性のあるクラスタを生成する傾向がある。クラスタごとに、本明細書に記載した方法は、クラスタにとっての重要度に従って、ドキュメントをランク付けすることができる。所与のクラスタについてのクラスタの内容の意味のあるラベルまたは識別子は、クラスタを作成したプローブからの特徴の用語または説明から生成することができる。例示的な方法は、最後のクラスタを生成するために、ドキュメントの組全体を処理する必要はなく、むしろ、クラスタ形成の各反復中に、最後の完全なクラスタが生成される。したがって、プロセスが早く中止された場合でさえ、最も重要なクラスタと思われるものについての最終結果を取得することができる。各クラスタが単一パスで削除され、クラスタ形成の次の反復中に処理すべきドキュメントがより少なくなるので、この方法は、計算上効率的で速い。
【００４８】
ハードウェアの概要
図４は、本発明の一実施形態を実施することができるコンピュータ・システム例のブロック図を示している。コンピュータ・システム１３００は、バス１３０２、または情報を伝えるための他の通信機構、および情報を処理するための、バス１３０２に結合されたプロセッサ１３０４を含む。また、コンピュータ・システム１３００は、ランダム・アクセス・メモリ（ＲＡＭ）や他の動的記憶装置など、プロセッサ１３０４によって実行されるべき情報および命令を格納するためのバス１３０２に結合されているメイン・メモリ１３０６も含む。メイン・メモリ１３０６は、プロセッサ１３０４によって実行されるべき命令の実行中に、一時変数または他の中間情報を格納するために使用することもできる。コンピュータ・システム１３００は、プロセッサ１３０４のための静的情報および命令を格納するためのバス１３０２に結合されている読み取り専用メモリ（ＲＯＭ）１３０８または他の静的記憶装置をさらに含む。磁気ディスクまたは光ディスクなどの記憶装置１３１０は、情報および命令を格納するために設けられ、バス１３０２に結合される。
【００４９】
コンピュータ・システム１３００は、コンピュータ・ユーザに情報を表示するために、バス１３０２を介してディスプレイ１３１２に結合することができる。入力装置１３１４は、英数字および他のキーを含み、情報およびコマンド選択をプロセッサ１３０４に伝えるために、バス１３０２に結合されている。別のタイプのユーザ入力装置は、方向情報およびコマンド選択をプロセッサ１３０４に伝え、ディスプレイ１３１２上のカーソルの動きを制御するためのマウス、トラックボール、またはカーソル方向指示キーなどのカーソル・コントロール１３１５である。
【００５０】
本明細書に記載された例示的な方法は、ドキュメントのクラスタ化を実行するために、コンピュータ・システム１３００により実施することができる。クラスタ化プロセスは、命令のシーケンスを実行し、メモリ１３０６および／または記憶装置１３１０など、ドキュメントの組、およびそれに関連するクラスタ化情報を、例えば任意の適したデータベースに格納し、取り出すことができる１つまたは複数のメモリまたは記憶装置と適切に通信することによって、プロセッサ１３０４によって実行することができる。処理命令は、記憶装置１３１０など別のコンピュータ可読媒体からメイン・メモリ１３０６に読み込むことができる。しかし、コンピュータ可読媒体は、記憶装置１３１０などの装置に限定されない。例えば、コンピュータ可読媒体は、フロッピー（登録商標）・ディスク、フレキシブル・ディスク、ハード・ディスク、磁気テープ、または他の任意の磁気媒体、ＣＤ−ＲＯＭ、他の任意の光媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、他の任意のメモリ・チップまたはカートリッジ、またはプロセッサ１３０４に本明細書に記載された技術を実行させる適切な組のコンピュータ命令を含む任意の変調波／信号（無線周波数、音声周波数、または光周波数の変調波／信号）を含めて、コンピュータがそこから読み取ることができる他の任意の媒体を含み得る。命令のシーケンスの実行によって、プロセッサ１３０４は、本明細書に上述したプロセス・ステップを実行する。他の実施形態として、本明細書に記載された例示的な方法を実施するために、ソフトウェア命令の代わりに、またはそれとの組合せで、配線で接続された回路を使用することができる。したがって、本発明の実施形態は、ハードウェア回路およびソフトウェアの任意の特定の組合せに限定されない。
【００５１】
コンピュータ・システム１３００は、バス１３０２に結合されている通信インターフェース１３１６を含むこともできる。通信インターフェース１３１６は、ローカル・ネットワーク１３２２およびインターネット１３２８に接続されるネットワーク・リンク１３２０に結合する双方向データ通信を提供する。クラスタ化されるドキュメントの組は、ネットワーク・リンク１３２０を介して、インターネット１３２８とコンピュータ・システム１３００との間で通信することができ、この場合、クラスタ化されるドキュメントは、１つのソースまたは複数のソースから取得できることを理解されたい。通信インターフェース１３１６は、総合サービス・デジタル通信網（ＩＳＤＮ）カードまたはデータ通信接続を対応するタイプの電話線に提供するためのモデムとすることができる。別の例として、通信インターフェース１３１６は、互換性のあるＬＡＮにデータ通信接続を提供するローカル・エリア・ネットワーク（ＬＡＮ）カードとすることができる。無線リンクを実装することもできる。こうした任意の実装では、通信インターフェース１３１６は、様々なタイプの情報を表すデジタル・データ・ストリームを運ぶ電子、電磁、または光信号を送受信する。
【００５２】
ネットワーク・リンク１３２０は、一般に、１つまたは複数のネットワークを介して、他のデータ装置にデータ通信を提供する。例えば、ネットワーク・リンク１３２０は、ローカル・ネットワーク１３２２を介して、ホスト・コンピュータ１３２４、またはインターネット・サービス・プロバイダ（ＩＳＰ）１３２６によって操作されるデータ機器に接続を提供することができる。次にＩＳＰ１３２６は、「インターネット」１３２８を介してデータ通信サービスを提供する。ローカル・ネットワーク１３２２およびインターネット１３２８は、デジタル・データ・ストリームを運ぶ電子、電磁、または光信号を使用する。様々なネットワークを通る信号、およびネットワーク・リンク１３２０上のおよび通信インターフェース１３１６を通る信号は、コンピュータ・システム１３００との間でデジタル・データを運び、情報を運ぶ代表的な形の変調波である。
【００５３】
コンピュータ・システム１３００は、ネットワーク、ネットワーク・リンク１３２０、および通信インターフェース１３１６を介して、メッセージを送信したり、プログラム・コードを含めたデータを受信したりすることができる。例えば、インターネット１３２８では、サーバ１３３０は、アプリケーション・プログラムのために要求されたコードを、インターネット１３２８、ＩＳＰ１３２６、ローカル・ネットワーク１３２２、および通信インターフェース１３１６を介して送信することができる。本発明によれば、こうした１つのダウンロード可能なアプリケーションによって、本明細書に記載したように、ドキュメントのクラスタ化の実行に備えることができる。ネットワークを介して受信されたプログラム・コードは、受信されると、プロセッサ１３０４によって実行し、かつ／または後で実行するために記憶装置１３１０または他の不揮発性記憶装置に格納することができる。このように、コンピュータ・システム１３００は、変調波の形でアプリケーション・コードを取得することができ、これは、コンピュータ可読媒体の範囲内に含まれるものとする。
【００５４】
本発明の構成要素は、メモリまたはディスクの複数の場所に、全部または一部として格納することができ、アプリケーションによって同期または非同期にアクセスすることができ、構成要素型で形成された場合、ドキュメントの取り出しまたはフィルタリングのために必要な情報を提供するために、メモリにおいて再構築することができる。
【００５５】
本発明は、その特定の実施形態を参照して特に説明され、示されているが、本発明の意図または範囲から逸脱することなく、形態または詳細に関して、上記の説明または例示における変更が加えられてもよいことを、当業者であれば理解されたい。例えば、図面中、フロー図は、処理ステップが例示された順序で行われるように示しているが、すべてのステップは、必ずしも例示された順序で行われる必要はないことを理解されたい。
【図面の簡単な説明】
【００５６】
【図１】本発明の一態様による類似ドキュメントのクラスタを識別する例示的なフロー図である。
【図２】本発明の一態様による類似ドキュメントのクラスタを識別する別の例示的なフロー図である。
【図３】本発明の一態様による類似ドキュメントのクラスタを識別する別の例示的なフロー図である。
【図４】本発明の別の態様による、類似ドキュメントのクラスタを識別する方法を実施することができるコンピュータ・システムの例示的なブロック図である。
【図１】
2009516307.tif 000005
【図２】
2009516307.tif 000006
【図３】
2009516307.tif 000007
【図４】
2009516307.tif 000008
【国際調査報告】
2009516307.tif 000009