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