(57)【要約】【課題】ドキュメント処理において確率的モデル化パラメータをリアルタイムでアップデートする。【解決手段】クラスタリングシステムのクラスを特徴付ける語数、比率又は頻度を示す確率的モデルパラメータにより少なくとも部分的に定義される、確率的クラスタリングシステムのアップデート方法。１つ以上のドキュメントの関連が１つ以上のソースクラスから１つ以上のデスティネーションクラスに変更される。変更された関連の影響を受けるクラスを特徴付ける確率的モデルパラメータが局部的にアップデートされ、当該変更された関連により影響を受けないクラスを特徴付ける確率的モデルパラメータはアップデートされない。【選択図】図２
2007272892.tif 000002
【特許請求の範囲】
【請求項１】
クラスタリングシステムのクラスを特徴付ける語数、比率又は頻度を示す確率的モデルパラメータにより少なくとも部分的に定義される、確率的クラスタリングシステムのアップデート方法であって、前記方法は、
１つ以上のドキュメントの関連を１つ以上のソースクラスから１つ以上のデスティネーションクラスに変更すること、及び
前記変更された関連により影響を受けないクラスを特徴付ける確率的モデルパラメータをアップデートせずに、前記変更された関連の影響を受けるクラスを特徴付ける確率的モデルパラメータを局部的にアップデートすること
を含む方法。
【請求項２】
前記変更すること及び前記局部的にアップデートすることは、
ドキュメントの前記関連をソースクラスからデスティネーションクラスに変更し、前記ドキュメントを前記ソースクラスから前記デスティネーションクラスに移動させると共に、前記ドキュメントの前記ソースクラスからの移動と、前記ドキュメントの前記デスティネーションクラスへの移動をそれぞれ反映させるべく、前記ソースクラス及び前記デスティネーションクラスを特徴付ける確率的モデルパラメータを前記移動されたドキュメントの語数に基づいて代数的にアップデートすること、及び
階層のリーフクラスにドキュメントが割り当てられたクラス階層を含む、確率的クラスタリングシステムにおいて、前記１つ以上のドキュメントを含むクラスを前記階層のソース先祖クラスから前記階層のデスティネーション先祖クラスへ直接的又は間接的に移動させ、前記ソース先祖クラスと前記デスティネーション先祖クラスとに共通の先祖である共通親クラスを識別し、前記ソース先祖クラスと前記共通親クラスとの間の前記階層、あるいは前記デスティネーション先祖クラスと前記共通親クラスとの間の階層に配置された少なくとも１つの中間先祖クラスを識別し、且つ、前記ソース先祖クラスから前記デスティネーション先祖クラスへの前記クラスの移動を反映させるべく、各中間先祖クラスを特徴付ける確率的モデルパラメータを前記移動されたクラスの語数に基づいて代数的にアップデートすること
のうち少なくとも１つを含む、請求項１に記載の方法。
【請求項３】
前記確率的クラスタリングシステムは、階層のリーフクラスにドキュメントが割り当てられたクラス階層を含み、
前記関連を変更することは、マージされたクラス又はマージしている先祖クラスを作成すること、及び、(i)１つ以上のドキュメント又は子孫クラスの前記関連を、直接の共通先祖クラスを有する２つ以上のソースクラスから前記マージされたクラスに変更し、且つ前記２つ以上のソースクラスを前記クラス階層の前記マージされたクラスで置き換えること、または(ii)前記マージしている先祖クラスを(a)各々が直接の共通先祖クラスを有する２つ以上のソースクラスと(b)前記直接の共通先祖クラスとの間の前記クラス階層に挿入することのうちいずれかを含み、
前記局部的にアップデートすることは、前記２つ以上のソースクラスを特徴付ける確率的モデルパラメータを組み合わせ、前記マージされたクラス又は前記マージしている先祖クラスを特徴付ける確率的モデルパラメータを生成することを含む、
請求項１に記載の方法。
【請求項４】
前記確率的クラスタリングシステムは、階層のリーフクラスにドキュメントが割り当てられたクラス階層を含み、前記関連を変更することは、
２つ以上のスプリットリーフクラスを作成すること、及び
既存のリーフクラスの各ドキュメントを２つ以上のスプリットリーフクラスのうちの１つに関連付けるためにクラスタリングトレーニングを実行することであって、前記クラスタリングトレーニングは前記既存のリーフクラスと関連付けられたドキュメントに限定して行われ、前記クラスタリングトレーニングにより前記既存のリーフクラスと関連付けられたドキュメントに対し前記スプリットリーフクラスを特徴付けるための局部的な確率的モデルパラメータが生成される、該実行すること
を含む、
請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ドキュメント処理技術に関する。ドキュメントを単語集合（bag-of-words）形式で表す、確率的階層的クラスタリングを用いた例示的実施形態を参照しながら本発明を説明する。なお、本発明は確率的非階層的クラスタリングや他のタイプのクラスタリングにも同様に適用できる。
【背景技術】
【０００２】
代表的なクラスタリングシステムでは、ドキュメントの類似性と相違性に基づいてドキュメントを様々なクラスに分類するトレーニングアルゴリズムによりドキュメントのセットを処理する。例えば、あるアプローチにおいて、ドキュメントは、頻度が高く且つ意味上の重要性が一般に低い一定のストップワード（例えば「the」、「an」、「and」など)を除いた重要語又は語の数を保存する単語集合形式で表される。ドキュメントの類似性及び相違性は、語数、比率又は頻度の観点から測定され、トレーニングによって、ドキュメントはこのような類似性及び相違性に基づいて様々なクラスに分割される。また、トレーニングにより、当該クラスを特徴付ける語数、比率又は頻度を表す確率的モデルパラメータが生成される。例えば、あるクラスのドキュメントの総語数に対する当該クラスのドキュメントの各語数の比率から、語の確率又は語の頻度をモデル化するパラメータが与えられる。必要に応じてクラスを組織化し、クラス階層を形成してもよい。クラス階層においてドキュメントはリーフクラスと関連付けられ、先祖クラスは意味上又は論理上関連のあるリーフクラスのグループ化を識別しあるいは関連付ける。トレーニングが終了すると、クラスタリングシステムを利用して、クラスタリングされたドキュメントへのユーザアクセスのための使いやすく直感的なインタフェースを提供できる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、最初のクラスタトレーニングで生成されるこの分類システムは概して静的であるという問題がある。確率的モデル化パラメータはドキュメント及びクラスの語数に基づいて最初のトレーニング中に計算される。クラスタリングシステムにおいてドキュメントがあるクラスから別のクラスに移動されたり、あるいはクラスがスプリットされたり既に存在するクラスがマージされたりすると、トレーニング中に計算された確率的モデル化パラメータは正確性を失う。
【０００４】
最新の確率的モデル化パラメータを維持するため、各アップデート後（例えば各ドキュメントやクラスの移動後、各クラスのスプリットやマージの後など）にクラスタリングシステムの再トレーニングを行うこともできる。しかし、大規模なクラスタリングシステムは、各々が数千語から数万語以上を含むドキュメントを数万から数十万以上を含んでいることがある。よって、クラスタリングシステムの再トレーニングを行うことは、概して速度の遅い案である。各々が数千語又は数万語を含む数千のドキュメントをドキュメントベースで再トレーニングするには数分もしくはそれ以上の時間を要する。このような長い時間枠はクラス階層のリアルタイムアップデートの実行に資するところがない。また、一般にこのような再トレーニングの影響は、移動されたドキュメントや既に移動、マージ、スプリットもしくは他のアップデートを行ったクラスに関して局在化されない。そればかりか、クラス階層の一領域のアップデートを反映させるべくクラスタリングシステムを再トレーニングすることで、例えば当該アップデートされた領域から遠く離れた別の領域に意図しない結果が生ずることもある。
【課題を解決するための手段】
【０００５】
本願明細書に示される一つの態様によれば、クラスタリングシステムのクラスを特徴付ける語数、比率又は頻度を示す確率的モデルパラメータにより少なくとも部分的に定義される、確率的クラスタリングシステムのアップデート方法が提供される。１つ以上のドキュメントの関連が１つ以上のソースクラスから１つ以上のデスティネーションクラスに変更される。変更された関連の影響を受けるクラスを特徴付ける確率的モデルパラメータが局部的（ローカル）にアップデートされ、当該変更された関連により影響を受けないクラスを特徴付ける確率的モデルパラメータはアップデートされない。
【発明を実施するための最良の形態】
【０００６】
図１を参照しながらクラスタリングシステムについて説明する。クラスタリングシステムは、ドキュメント１０のセットを組織化しクラス階層１２を生成する、確率的クラスタリングシステムである。実施形態によっては、クラスのフラットセットが生成される。クラス階層１２は、どのドキュメント１０がクラス階層１２のどのリーフクラスに関連付けられたかを示すドキュメント／リーフクラス関連１４を含む（当該技術では用語「クラス」が使用されているが、「クラスタ」や「カテゴリ」など実質的に同意義の用語も使用される。ここでは、用語「クラス」は用語「クラスタ」又は「カテゴリ」をも含むものと広義に解釈されたい）。実施形態によっては、ドキュメント／リーフクラス関連１４は注釈としてドキュメントに付けられる。ドキュメント１０のセットの各ドキュメントは単語集合形式で表示されるのが適切である。単語集合形式では、ドキュメントにおける語の位置は利用しない。代わりに、頻度が高く且つ意味上の重要性が一般に低い一定のストップワード（例えば「the」、「an」、「and」など）を除いた重要語又は語の数によってドキュメントを表示する単語頻度ベクトルや同様の形式が使用される。使用される特定の形式は様々である。例えば、単語集合表示は必要に応じてドキュメントの総語数、又はドキュメントにおける非ストップワードの総数により正規化された語数を有する。
【０００７】
クラス階層１２は、当該クラスを特徴付ける語数、比率又は頻度を示す確率的モデルパラメータ１６のセットを更に含む。例示されるクラスタリングシステムでは確率的モデルを利用する。クラス階層１２はドキュメントと直接関連付けられたリーフクラスを含む。必要に応じて、階層は、自身はドキュメントを含まないが、ドキュメントを含むリーフドキュメントの先祖である１つ以上の先祖クラスを更に含む。クラス階層１２は必要に応じて２つ以上のレベルの先祖クラスを含む。例示的な一実施形態では、クラスを特徴付ける確率的モデル化パラメータ１６は、各クラスCについて、ドキュメント１０のセットの総語数に対するクラスCのドキュメントの語数の比率を示すクラス確率P（C)と、クラスCの総語数に対するクラスCのドキュメントｄの語数の比率を示すドキュメント確率P（d|C）（ハードパーティショニングの場合、ドキュメントｄがクラスCと関連付けられていなければP（d|C）=０であり、ドキュメントｄがクラスCと関連付けられていれば、（d|C）はドキュメントｄのクラスCに対する影響を示す）と、クラスCの総語数に対するクラスCの語ｗの語数の比率を示す語確率P（w|C)と、を含む。この例示的実施形態ではハードパーティショニングを利用している。なお、所与のドキュメントが１つ以上のクラスと断片的な関連を有していてもよいソフトパーティショニングを利用することも考慮されている。
【０００８】
例示した確率的モデルパラメータP（C）、P（d|C）、P（w|C)はあくまで例であり、限定的なものではない。これらに代えてあるいはこれらに加えて他の適切な確率的モデルパラメータを定義してもよい。また、実施形態によっては、クラスタリングは、ｋ平均（k-means）法、潜在意味インデックス化(latent semantic indexing)、階層的集積的方法などの非確率的クラスタリング技術により行ってもよい。
【０００９】
クラス階層１２は、通常は適切なトレーニングアプローチによって最初に生成される。実施形態によっては、期待値最大化（expectation-maximization (EM))や勾配降下(gradient descent)などの最大尤度アプローチ(maximum likelihood approach)は確率的クラスタリングモデルのトレーニングに利用される。トレーニングにより、トレーニング段階で獲得されたドキュメント／リーフクラス関連１４に基づいて確率的モデル化パラメータ１６が生成される。階層のリーフクラスはドキュメントと直接関連付けられる。リーフクラスが直接もしくは間接的に依存する中間クラスも、例えば、例示的確率P（c）、P（d|c）、P（w|c）（小文字の「c」は非リーフクラスを表す）などの関連された確率的モデル化パラメータを有する。非リーフクラスに関する適切なアプローチでは、全ての非リーフクラスｃについてP（c）=０である。このことは、非リーフクラスcにはいずれのドキュメントも直接的に含まれていないことを示す。P（d|c）及びP（w|c)はその子もしくは孫の対応するパラメータの重み付き平均である。すなわち、下記式が成り立つ。
【００１０】
【数１】
2007272892.tif 000003
【００１１】
クラスタリングシステムがトレーニングされると、ユーザはクラスタリングシステムをナビゲートするためにクラスタナビゲータ２４を実行するプロセッサ２２と通信する目的でユーザインタフェース２０を利用できる。実施形態によっては、ユーザインタフェースは、必要に応じて対象領域に焦点を合わせるため様々な枝が拡張又は折畳み可能に構成されるクラス階層のツリー表示を示すウィンドウ、選択されたドキュメントを表示するためのドキュメントウィンドウなどを提供するグラフィカルユーザインタフェース（GUI)である。適切なメニューオプション、マウスによる選択、あるいはグラフィカルユーザインタフェースのユーザ入力メカニズムによって様々なウィンドウを必要に応じて開閉できる。ユーザが単にドキュメントの閲覧、ドキュメントの検索又はその他の読出し専用クラスタシステムナビゲーションオペレーションの実行を行っているだけではクラスタリングシステムは静的であり、クラス階層１２は変更されない。
【００１２】
但し、ユーザは１つ以上のドキュメントの関連を１つ以上のソースクラスから１つ以上のデスティネーションクラスへ変更することを決定してもよい。関連変更の一例では、ユーザは１つのドキュメントをあるクラスから別のクラスへ移動することを選択する（例えば、図２参照）。関連変更の別の例では、ユーザはリーフクラスをある先祖クラスから別の先祖クラスへ移動させ、このプロセスの間に当該移動されたリーフクラスと関連付けられたドキュメントを移動させる（例えば、図３参照）。関連変更の別の例では、ユーザは２つ以上のリーフクラスをマージすることでマージ済みリーフクラスを形成し、このプロセスの間に元のリーフクラスと関連付けられたドキュメントをマージ済みリーフクラスに移動させる（例えば、図４参照）。関連変更の別の例では、ユーザは新しい先祖クラスを挿入することで２つ以上のリーフクラスをマージし、これによりマージされる２つ以上のリーフクラスの直接先祖とし、このプロセスの間に当該ドキュメントを当該新しい先祖クラスから間接的に移動させる（例えば、図５参照）。関連変更の別の例では、ユーザは既存のリーフクラスを２つ以上のスプリットリーフクラスにスプリットし、既存のリーフクラスを置き換える。このプロセスの間に当該既存のリーフクラスと関連付けられたドキュメントを当該スプリットリーフクラスに移動させる（例えば、図６参照）。関連変更の別の例では、ユーザは既存のリーフクラスの直接の子孫として作成された既存のリーフクラスのドキュメントを２つ以上のスプリットリーフクラスに移動させることでスプリットを実行し、このプロセスの間に既存のリーフクラスと関連付けられたドキュメントを新たなスプリットリーフクラスへ移動させる（例えば、図７参照）。
【００１３】
これらの各例示的関連変更は、確率的モデル化パラメータ１６を含むクラス階層１２に影響を及ぼす。新しいクラスが作成されない場合（例えば、図２及び図３の移動オペレーション）、その影響は一定の確率的モデル化パラメータ１６の値の変更である。新しい又は異なるクラスが作成されると（例えば、図４乃至図７のマージ及びスプリットオペレーション）、現在の確率的モデル化パラメータ１６の値が変更され、新しい確率化モデル化パラメータが追加的に作成され及び／又は削除される。なお、図１のクラスタリングシステムは、クラスタナビゲータ２４のコンポーネントを実行又は包含するほか、変更された関連により影響を受けないクラスを特徴付ける確率的モデルパラメータをアップデートすることなく、変更された関連により影響されるクラスを特徴付ける確率的モデルパラメータを局部的にアップデートするコンポーネントを実行又は包含する、プロセッサ２２を含む点で有利である。本願明細書に記載されるように、移動及びマージオペレーションの際、プロセッサ２２により実行される確率的モデル化パラメータの代数的アップデータ３０はクラスタトレーニングを行うことなく確率的モデルパラメータ１２を代数的且つ局部的にアップデートできる。スプリットオペレーションの際、スプリットリーフクラス中のドキュメントをスプリットするため、プロセッサ２２により実行されるクラスタリングビルダ３２を利用できる。クラスタリングはスプリット対象の既存のクラスと関連付けられたドキュメントにのみ実行される。クラスタリングビルダ３２は限定されたクラスタトレーニングを実行するために例えば期待値最大化（EM)アルゴリズム、勾配降下アルゴリズムなどの最大尤度確率的クラスタリングアルゴリズムを利用してもよい。通常、クラスタリングビルダ３２は、クラスタリングシステムの作成のため、ドキュメント１０の完全なセットに対し最初のクラスタトレーニングを行うために用いられる同一のアルゴリズム又はコンポーネントである。なお、後続のスプリットオペレーションでは、クラスタリングビルダ３２はスプリット対象の既存のクラスと関連付けられたドキュメントにのみ適用される。
【００１４】
コンポーネント３０、３２によって局部的アップデートを行うことの利点は、例えば数分間もしくはそれ以下、より好ましくは数秒間もしくはそれ以下の当該ユーザが受諾できる処理時間において、これらのアップデートをリアルタイムで実施できる点にある。代数的アップデート３０は、ドキュメントのクラスタリング（又は再クラスタリング)を実施せずに局部的アップデートを行うため、高速である。また、通常、スプリット対象の既存のクラスタ内のドキュメント数はクラスタリングシステムにより組織化されたドキュメント１０の総数の小さいサブセットであるため、スプリットオペレーションの間にクラスタリングビルダ３２を適用すると一般に高速となる。例えば、スプリットオペレーション中にクラスタリングビルダ３２を利用する場合、数十、数百又は数千のドキュメントを含む既存のクラスタに関する実行時間は通常数秒もしくはそれ以下である。これとは対照的に、クラスタシステムの完全な再トレーニングにクラスタリングビルダ３２を利用する場合、通常はドキュメント１０のセットの数万あるいはそれ以上のドキュメントのクラスタリングを行う必要があり、従って処理時間は実質上長くなる。一般にこのような完全な再トレーニングをリアルタイムで行うことは実際的でない。
【００１５】
図１を参照し、図２から図８を簡単に参照しながらリアルタイムアップデートを行うクラスタリングシステムを全体的に説明した。以下、例えばドキュメント移動、クラス移動、いくつかのタイプのマージを含む関連変更などの処理並びにスプリットオペレーションについて、図２から図８を参照しながら詳述する。なお、これらの各種オペレーションはクラスタリングシステムの複雑なリアルタイムアップデートを実行するために各種方法で組み合わせることができる。例えば、クラスを階層の別の部分に移動し、スプリットし、次いで１つ以上のドキュメントを新たに作成された一スプリットクラスから別のスプリットクラスへ移動することができる。
【００１６】
2007272892.tif 000004
【００１７】
従って、プロセッサ２２の確率的モデル化パラメータの代数的アップデータ３０が確率的モデル化パラメータの局部的アップデートを行う。局部的アップデートは、ソース及びデスティネーションリーフクラス「L１」及び「LN」に影響を及ぼすほか、ソースリーフクラス「L１」とデスティネーションリーフクラス「LN」に共通の先祖クラスである、ソースリーフクラス「L１」と共通の親クラス「ルート」との間の中間クラス「H１」にも影響を及ぼす。一般に、確率的モデル化パラメータの代数的アップデータ３０は、ソース及びデスティネーションリーフクラスを特徴付ける確率的モデル化パラメータをアップデートするほか、ソースリーフクラスと共通の親クラスとの間の階層にある（１つ又は複数の）任意の中間先祖クラス、あるいはデスティネーションリーフクラスと共通の親クラスとの間の階層にある（１つ又は複数の）クラスをアップデートする。なお、「共通の親クラス」とは、階層の最も下に位置する共通の親クラス、すなわち階層においてソース及びデスティネーションリーフクラスに最も近い共通の親クラスを指す。共通の親クラス自身がソースリーフクラス及びデスティネーションリーフクラスの両方に共通の親クラスを有していることもある。
【００１８】
移動オペレーションに関する代数的アップデートは以下のように行うことが適当である。ソースリーフクラスをCs、デスティネーション又はターゲットリーフクラスをCtで表す。また、Dは移動対象のドキュメント、dはソースクラスCs又はターゲットクラスCtの任意の他のドキュメントを表す。アップデートは４つのオペレーションで行うことが適当である。すなわち、ソースクラスCsからドキュメントDを除去してソースクラスCsに関する確率的モデル化パラメータをアップデートするオペレーション、当該アップデートをソースクラスCsと、ソースクラスCs及びターゲットクラスCtに共通の親クラスとの間の階層の任意の中間クラスに伝搬するオペレーション、ドキュメントDをデスティネーションすなわちターゲットクラスタCtに追加し、ターゲットクラスCtに関する確率的モデル化パラメータをアップデートするオペレーション、及び当該アップデートをターゲットクラスCtと、ソースクラスCs及びターゲットクラスCtに共通の親クラスとの間の階層の任意の中間クラスに伝搬するオペレーションである。局部的クラス、すなわちCs、Ct、及びソースクラス又はターゲットクラスと、共通の親クラスとの間にある任意の中間クラスに関する確率的モデル化パラメータのみが変更される。
【００１９】
2007272892.tif 000005
【００２０】
【数２】
2007272892.tif 000006
【００２１】
式（６)中、NwDはドキュメントDの語ｗの語数である。式（３)から式（６)はソースクラスCsからのドキュメントDの除去の影響を代数的に反映する。また、ソースクラスCsと、ソースクラスCs及びターゲットクラスCtに共通の親クラスとの間の階層に中間先祖クラスが存在する場合、これらのクラスを特徴付ける確率的モデル化パラメータは下記式により代数的に調整される。CpはソースクラスCsとターゲットクラスCtとに共通の親クラスを表す。次いで、下記の反復処理が行われる。
【００２２】
【数３】
2007272892.tif 000007
【００２３】
式（７)から式（１０)はデスティネーションすなわちターゲットクラスCtへのドキュメントDの追加の影響を代数的に反映する。更に、ターゲットクラスCtと、ソースクラスCs及びターゲットクラスCtに共通の親クラスCpとの間の階層に中間先祖クラスが存在する場合、これらのクラスを特徴付ける確率的モデル化パラメータは以下のように代数的に調整される。
【００２４】
【数４】
2007272892.tif 000008
【００２５】
2007272892.tif 000009
【００２６】
2007272892.tif 000010
【００２７】
【数５】
2007272892.tif 000011
【００２８】
2007272892.tif 000012
【００２９】
【数６】
2007272892.tif 000013
【００３０】
2007272892.tif 000014
【００３１】
【数７】
2007272892.tif 000015
【００３２】
2007272892.tif 000016
【００３３】
【数８】
2007272892.tif 000017
【００３４】
図４を参照しながらフラットマージオペレーションについて説明する。共通の直接先祖クラス「ルート」をもつリーフクラス「L１」と「L２」がマージされ、リーフクラス「L１」及び「L２」に代わるマージ済みリーフクラス「L１&２」が作成される。すなわち、リーフクラス「L１」及び「L２」のドキュメントの関連が、クラス階層におけるクラス「L１」及び「L２」に代えて新たに作成されたマージ済みクラス「L１&２」に変更される。図４のクラス階層はフラット階層であるが、より複雑な階層を用いることもできる。例えば、マージ対象のクラスは、ルートクラスの直接の子孫とするのではなく、ルートクラスとマージ対象のリーフクラスの中間に共通の先祖クラスを有していてもよい。このようなマージオペレーションが意味をなすためには、共通の先祖クラスは当該マージオペレーションに含まれない少なくとも１つのさらなる子孫リーフクラスを有する必要がある。
【００３５】
2007272892.tif 000018
【００３６】
【数９】
2007272892.tif 000019
【００３７】
2007272892.tif 000020
【００３８】
2007272892.tif 000021
【００３９】
【数１０】
2007272892.tif 000022
【００４０】
2007272892.tif 000023
【００４１】
図６を参照しながらフラットスプリットオペレーションについて説明する。既存のリーフクラス「L２」が、クラス階層の既存のリーフクラスを置換する２つ以上のスプリットリーフクラス（図６では２つのスプリットリーフクラス「L２A及びL２B」）にスプリットされる。スプリット前、既存のリーフクラス「L２」は直接先祖クラスとしてクラス「H１」を有し、スプリット後、置換されたスプリットリーフクラス「L２A及びL２B」は直接の共通先祖クラス「H１」を有する。図６の例では共通の直接先祖クラス「H１」は中間クラスであるが、他の実施形態ではクラス階層はフラットであってもよく、既存のリーフクラスの直接の先祖クラスと置換スプリットリーフクラスはルートクラスであってもよい。
【００４２】
２つ以上の置換スプリットリーフクラスのうち既存のリーフクラスと関連付けられたドキュメントを分割するため、クラスタトレーニングが実行される。但し、リアルタイムオペレーションに資する高速処理を促進するため、プロセッサ２２のクラスタリングビルダ３２は既存のリーフクラス（図６の既存のリーフクラス「L２」)に関連付けられたドキュメントの処理のみに限定して用いられる。限定されたクラスタトレーニングにより、既存のリーフクラスに関連付けられたドキュメントに対しスプリットリーフクラス（図６に示す例示的スプリットリーフクラス「L２A」及び「L２B」)を特徴付けるための局部的な確率的モデルパラメータが生成される。通常、スプリット対象の既存のクラスの１つと関連付けられるドキュメントの数は該クラスタリングシステムが組織化するドキュメントの総数よりも大幅に少ないため、限定的且つ局部的なクラスタトレーニングは、クラスタリングシステム全体の再トレーニングと比べて大幅に高速で行うことができる。また、限定されたクラスタトレーニングは既存のリーフクラスのドキュメントに対し局部的に行われるため、その効果も局部的である。
【００４３】
2007272892.tif 000024
【００４４】
【数１１】
2007272892.tif 000025
【００４５】
上記式は、ドキュメントDCのセットにおけるあらゆるドキュメントがスプリットリーフクラスCnの１つに関連付けられていることを示す。他方、グローバルクラスタリングシステムのコンテキストでは、下記式が成り立つ。
【数１２】
2007272892.tif 000026
【００４６】
2007272892.tif 000027
【００４７】
【数１３】
2007272892.tif 000028
【００４８】
グローバルクラスタリングシステムコンテキストの場合と同様にこれらの確率的モデル化パラメータのための値が局部的コンテキストにおいて同一であるため、式（２６)と式（２７)は同一である。グローバル確率的モデル化パラメータが決定されると、既存のリーフクラスのドキュメントが局部的クラスタトレーニングの結果に従って様々なスプリットリーフクラスに関連付けられた状態で、既存のリーフクラス（図６の例ではリーフクラス「L２」)をスプリットリーフクラス（図６の例ではリーフクラス「L２A」及び「L２B」)で置き換えることにより、フラットスプリットが完了する。
【００４９】
なお、フラットマージはある意味でフラットスプリットへのリバースオペレーションである。既存のリーフクラスをスプリットし、得られたスプリットリーフクラスをマージすると元の既存のリーフクラスと同一のものが得られる。このリバースが当てはまらない場合もある。いくつかのリーフクラスをマージし、マージしたクラスを再度スプリットすると異なるリーフクラスが生成される。すなわち、例えば５つのリーフクラスをマージし、次いでマージしたリーフクラスを５つのリーフクラスにスプリットしても元の５つのリーフクラスと同一のものには戻らない。
【００５０】
2007272892.tif 000029
【００５１】
【数１４】
2007272892.tif 000030
【００５２】
P（w|C)及びP（d|C)は変化しない。既存のクラスCは保持され、追加されたスプリットリーフクラスタの直接の先祖クラスとして作用し、既存のクラスCと関連付けられていたドキュメントは、局部的クラスタトレーニングに従って、追加された各種スプリットリーフクラスタと関連付けられる。
【００５３】
フラットスプリットを行い、スプリットされたリーフクラスのフラットマージを更に行うと、元のリーフクラスが得られる。対照的に、階層的マージは階層的スプリットへの逆のオペレーションではない。これは、階層的マージと階層的スプリットの両方が追加的階層を作成するためである。
【００５４】
上で説明した例示的フラットスプリットオペレーション及び階層的スプリットオペレーションでは、スプリットの実行方法に関してユーザは嗜好をもたないものと仮定されていた。すなわち、ユーザはどのドキュメントがどのスプリットリーフクラスにグループ化されるかを決定するクラスタリングビルダ３２の手順に完全に依存している。しかし、場合によっては、ユーザはスプリットオペレーションの際にドキュメントの一定のサブセットをまとめておきたい場合がある。特に制約付きのスプリットの場合がそうである。従って、ドキュメントを語頻度ベクトル、又は頻度が高く且つ意味上の重要性が一般に低い一定のストップワード（例えば「the」、「an」、「and」など)を除いた重要語又は語の数を保存する他の形式で表す、ドキュメントを単語集合形式で表示するクラスタリングシステムにおいて（フラット又は階層的)スプリットを実行する技術について説明する。スプリットの際にドキュメントの選択されたサブセットをまとめておくための技術は、スプリットクラス内のドキュメントを分配するために単語集合形式でドキュメントに作用するクラスタリング技術を利用するほぼあらゆるスプリットオペレーションのコンテキストに適用できる。この技術は確率的クラスタリングシステムに限定されない。本願明細書で使用する記号の例を以下に示す。Cはスプリット対象のクラス、Lはスプリットにより生成されるスプリットクラス数（スプリットリーフクラスタはフラットスプリットの場合にクラスCを置き換えてもよく、階層的スプリットの場合にはクラスCに従属してもよい）。n>１のとき、G=[d1、…dn]はグループ化されるｎ個のドキュメントのサブセットを表す。
【００５５】
2007272892.tif 000031
【００５６】
【表１】
2007272892.tif 000032
【００５７】
2007272892.tif 000033
【００５８】
【数１５】
2007272892.tif 000034
（２９)
【００５９】
2007272892.tif 000035
【００６０】
2007272892.tif 000036
【００６１】
2007272892.tif 000037
【００６２】
【数１６】
2007272892.tif 000038
（３０)
【００６３】
2007272892.tif 000039
【００６４】
再び図１を参照すると、本願明細書で説明するドキュメント移動、リーフクラス移動、リーフクラスマージ、リーフクラススプリットオペレーションはユーザインタフェース２０から供給されるユーザ入力と共にリアルタイムで実行されることが適切である。「リアルタイム」とは、ユーザインタフェース２０と対話しているユーザが受諾できる時間枠で当該オペレーションが実行され得ることを意味する。このような時間枠は通常好ましくは数分間もしくはそれ以下、より好ましくは数秒間もしくはそれ以下である。実施形態により、ユーザインタフェース２０はグラフィカルユーザインタフェース（GUI)である。クラス階層１２はツリー又はツリー状構造で適切に表示され、該構造は必要に応じて拡張もしくは折畳み可能な枝を含む。ユーザは該構造においてマウス又は他のポインティングデバイスを用いてクラス、ドキュメントなどを選択できる。例えば、あるアプローチでは、ユーザはドキュメント又はリーフクラスを右クリックし、移動オペレーションのための選択肢を含むコンテキストセンシティブメニューを表示させることでドキュメント又はリーフクラスに対し移動オペレーションを行う。ユーザがコンテキストセンシティブメニューから移動オペレーションを選択すると、デスティネーションクラスに関するダイアログボックスが現れる。ユーザが例えばマウスポインタを用いてクリックすることでデスティネーションクラスを選択すると、ドキュメントもしくはリーフクラスの移動が本願明細書に示す方法で実行され、アップデートされたクラス階層１２のツリー表示が表示される。GUIは、例えばユーザがドキュメント又はリーフクラスを右クリックした場合にのみコンテキストセンシティブメニューに移動オペレーション選択オプションを表示するなど、オペレーションに対する適切なチェックを含むことが好ましい。実施形態により、ユーザは例えばドキュメント上で左クリックしながら<CONTROL>又は<ALT>を押下し、次いで選択されたグループ上で右クリックして移動オペレーション選択オプションを含むコンテキストセンシティブメニューを表示させることにより、移動対象のドキュメント又はリーフクラスを選択してもよい。
【００６５】
マージオペレーションを実行するには、ユーザは例えば、ドキュメント上で左クリックしながら<CONTROL>又は<ALT>キーを押下することでマージ対象の複数のリーフクラスを適切に選択し、次いで選択されたグループ上で右クリックするとコンテキストセンシティブメニューが現れる。GUIが、選択は全て共通の直接先祖クラス（例えばルートクラス)を有するリーフクラスであると判断すると、GUIはマージオプションをコンテキストセンシティブメニューに含める。ユーザがマージオプションを選択すると、GUIはフラットマージと階層的マージのいずれを意図しているのかを尋ねる（あるいは、コンテキストセンシティブメニューに「フラットマージ」と「階層的マージ」を別々にオプションとして含めてもよい)。次いで、本願明細書に記載されるように、選択されたリーフクラスが選択されたフラットマージ又は階層的マージによりマージされ、クラス階層１２のアップデートされたツリー表示が表示される。
【００６６】
スプリットオペレーションを行うためには、ユーザはスプリット対象のリーフクラスを選択し、右クリックしてコンテキストセンシティブメニューを表示させる。リーフクラスが選択されたことをGUIが判断すると、GUIはコンテキストセンシティブメニューにスプリットオプションを含める。ユーザがコンテキストセンシティブメニューからスプリットオプションを選択すると、GUIはフラットスプリットと階層的スプリットのいずれを意図しているのかを尋ねる形で応答する（あるいは、コンテキストセンシティブメニューに「フラットスプリット」と「階層的スプリット」を別々にオプションとして含めてもよい)。更に、GUIは作成するスプリットクラスの数を示す値を尋ねる。ユーザが与えたスプリットクラスの数が１より大きく、スプリット対象のクラス内のドキュメントの総数未満であることを確認するためのチェックをGUIに含めることが好適である。次いで、選択されたリーフクラスが本願明細書に示す方法でスプリットされ、アップデートされたクラス階層１２のツリー表示が表示される。
【００６７】
ドキュメントG(p)の１つ以上のサブセットがまとめられた、制約されたスプリットを実行するには、ユーザは例えばダブルクリックしてリーフクラスを開き、ドキュメントのサブセットに含まれる対象のドキュメント上でクリックしながら<CONTROL>、<ALT>、又は他のグループ化キーを押下することでサブセットを選択する。本願明細書に記載されるように、このプロセスを必要に応じて繰り返すことで、まとめる対象のドキュメントの２つ以上のサブセットを定義することができる。次いで、ユーザは既述の如くスプリットオプションを選択し、GUIは選択されたグループを取り消し、置き換えられたテンポラリドキュメントを用いてこれらをまとめる。必要に応じて、スプリットを行う前に、GUIはユーザに、グループを別々のスプリットリーフクラスにクラスタリングするのか否か（すなわち、クラスタリングが「排他的グループ制約」を採用すべきか否か)を尋ね、ユーザの応答に従って制約されたスプリットを実行する。
【００６８】
上記GUIオペレーションは例えばMicrosoft Windows（登録商標）コンピュータオペレーティングシステムなどの一般的なGUIシステムのユーザにはよく知られたマウス操作を用いた例である。本願明細書に記載するように、リアルタイムドキュメント移動、リーフクラス移動、クラスマージ、クラススプリットオペレーションの実行を促進するために他のGUI実行を利用してもよい。また、これらのオペレーションは例えばバッチ処理スクリプト、コマンドラインユーザインタフェースなどの非グラフィカルインタフェースを用いて、リアルタイムで、又は後続処理のための待ち列に入れられたプロセスとして実行されることを考慮している。
【００６９】
以上、リーフクラスタの移動、スプリット、マージに関してクラス移動、スプリット、マージオペレーションを説明した。なお、これらのオペレーションはクラス階層のより大きな枝の移動、スプリット、マージにも拡張できる。
【００７０】
2007272892.tif 000040
【００７１】
【数１７】
2007272892.tif 000041
【００７２】
2007272892.tif 000042
【００７３】
【数１８】
2007272892.tif 000043
【００７４】
2007272892.tif 000044
【００７５】
2007272892.tif 000045
【００７６】
【数１９】
2007272892.tif 000046
【００７７】
確率的モデル化パラメータの代数的アップデータ３０はマージされたクラスcについて下記のように式（１７)から式（１９)と類似の方法にてパラメータを計算する。
【数２０】
2007272892.tif 000047
【００７８】
方程式の結果が０であるのは、非リーフクラス自身がドキュメントを含まないことから、P（cn)=０であるためである。マージされたクラスcの語確率は下記式で与えられる。
【００７９】
【数２１】
2007272892.tif 000048
【００８０】
2007272892.tif 000049
【００８１】
リーフクラスの階層的マージについて図５及び式（２０）から式（２２）を参照しながら説明した。より一般的には、リーフクラスと非リーフクラスの別を問わず、同一の直接の先祖（すなわち、親）クラスCPを有するクラスの任意のセットはマージ可能である。
【００８２】
図８を参照すると、例えば、直接の先祖クラス「H１」を有し、且つ子孫リーフクラス「L２」及び「L３」を有する非リーフクラス「H２」は、直接先祖クラス「H１」を有するリーフクラス「L４」と階層的にマージされる。図８に示すように、階層的マージは、新たにマージされた非リーフクラス「c」を直接の先祖クラス「H１」とマージされたクラス「H２」及び「L４」との間に挿入することで行われる。
【００８３】
2007272892.tif 000050
【００８４】
【数２２】
2007272892.tif 000051
【００８５】
【数２３】
2007272892.tif 000052
【００８６】
確率的モデル化パラメータの代数的アップデータ３０は下記のように式（２０)から式（２２)と類似の方法で、挿入されたマージ済みクラスcに関するパラメータを計算する。
【００８７】
【数２４】
2007272892.tif 000053
（上記式は、挿入されたマージ済みクラスcがそれ自身ドキュメントを含まない非リーフクラスであることを示す)。
【００８８】
【数２５】
2007272892.tif 000054
【００８９】
式中、Nwcはマージされたクラスcに従属するリーフクラスと関連付けられたドキュメントにおける語ｗの総発生回数である。マージを完了するには、クラスcが共通の親Cpの下の階層的構造に挿入され、マージされたクラスcnが挿入されたクラスcに従属するよう構成される。
【図面の簡単な説明】
【００９０】
【図１】リアルタイム階層アップデートを含むクラスタリングシステムの概略図である。
【図２】ドキュメントをソースクラスからデスティネーションクラスへ移動するアップデートの概略図である。
【図３】リーフクラスをソース先祖クラスからデスティネーション先祖クラスへ移動するアップデートの概略図である。
【図４】共通の直接先祖クラスをもつ２つのリーフクラスをマージするアップデートの概略図である。
【図５】共通の直接先祖クラスを作成することにより共通の直接先祖クラスをもつ２つのリーフクラスをマージするアップデートの概略図である。
【図６】既存のリーフクラスをスプリットして、既存のリーフクラスと置き換えられる２つのスプリットリーフクラスとするアップデートの概略図である。
【図７】既存のリーフクラスのドキュメントを、既存のリーフクラスを共通の直接先祖クラスとしてもつ２つの新しいスプリットリーフクラスに移すことで既存のリーフクラスを２つのスプリットリーフクラスにスプリットするアップデートの概略図である。
【図８】共通の直接先祖クラスを作成することにより共通の直接先祖クラスをもつ非リーフクラスとリーフクラスをマージするアップデートの概略図である。
【図１】
2007272892.tif 000055
【図２】
2007272892.tif 000056
【図３】
2007272892.tif 000057
【図４】
2007272892.tif 000058
【図５】
2007272892.tif 000059
【図６】
2007272892.tif 000060
【図７】
2007272892.tif 000061
【図８】
2007272892.tif 000062