(57)【特許請求の範囲】
【請求項１】
複数の文書を、階層的に組織化された複数のクラスタで構成される構造にクラスタリングする、コンピュータにより実施される方法であって、各文書は複数の単語を含み、かつ、（文書，単語）ペアのセットとして表現され、前記方法は、
入出力要素、ネットワークコネクタ、あるいはバスの少なくともいずれか１つによって文書コレクションにアクセスするステップと、
前記コレクションの文書の分類を反映するクラスタの階層を、文書に含まれる単語に基づき作成するクラスタリング処理をコンピュータのプロセッサにより実行するステップであって、前記コレクションの任意の文書は各文書の第１セグメントに基づき前記階層の第１クラスタに割当てることができ、各文書は該各文書の第２セグメントに基づき前記階層の第２クラスタに割当てることができ、前記第１及び第２のクラスタは前記階層の異なるパスに関連づけられているステップと、
クラスタの階層の表示をメモリに記憶するステップと、
ネットワークコネクタ、バス、あるいはディスプレイの少なくともいずれか１つによって前記表示を、前記文書コレクションに関連付けられた要求に応じて、エンティティに対して利用可能にするステップと、を含む方法。
【請求項２】
請求項１に記載の方法において、前記クラスタリング処理を実行するステップは、
前記文書コレクションを第１クラスに割当てるステップと、
確率パラメータを初期値に設定するステップと、
前記パラメータの値にある、前記コレクションの各文書に対し、前記コレクションの文書が前記階層のあるクラスタに割当てられる確率を、該文書に含まれる単語及び前記第１クラスに基づき決定するステップと、を含む方法。
【請求項３】
複数の画像を、その画像に関連するテキストに基づき、複数のサブノードに関連付けられたルートノードを含む階層的データ構造にクラスタリングする、コンピュータで実施される方法であって、各画像は（画像，テキスト特徴）ペアのセットとして表現され、各サブノードは異なるトピックを表し、前記方法は、
入出力要素、ネットワークコネクタ、あるいはバスの少なくともいずれか１つによって画像コレクションにアクセスするステップと、
前記階層的データ構造を作成するクラスタリング処理をコンピュータのプロセッサにより実行するステップと、を含み、前記クラスタリング処理は、
第１の画像を、該第１の画像に関連付けられたテキストの第１部分に基づき第１サブノードに関連付けるステップと、
前記第１の画像を、該第１の画像に関連付けられたテキストの第２部分に基づき第２サブノードに関連付けるステップと、を含み、
前記第１及び第２サブノードは前記階層的データ構造の異なる子孫パスに関連づけられ、
前記方法は、さらに、
前記階層的データ構造の表示をメモリに記憶するステップと、
ネットワークコネクタ、バス、あるいはディスプレイの少なくともいずれか１つによって前記表示を、前記画像コレクションに関連づけられた要求に応じてエンティティに対して利用可能にするステップと、を含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は対象の階層的クラスタリングに関し、より詳細には対象ペアの共起（co-occurrence）に基づく、対象の階層的ソフトクラスタリングのための製造の方法、装置及び製品に関する。
【０００２】
【従来の技術】
データ分類は依然としてその魅力が増しているが、これはほとんどその一部が、多数のアクセス媒体、例えばインターネットを通じてデータが利用できることによる。このような媒体の人気が高まるにつれ、データプロバイダがすばやくかつ効率的なデータアクセスを提供する責任も増す。したがって、これらのプロバイダは種々の技術を駆使して、効率的なデータアクセスを保証している。かかる技術の１つがクラスタリングを用いたデータ管理である。クラスタリングにより、データをその特性に基づいて階層的に分類する（クラスタリングする）ことができる。このようなクラスタリング技術の前提として、互いに類似する対象、例えば文書におけるテキストデータなどが、ある階層の共通クラスタに配置される。例えば、データプロバイダ、例えばＹａｈｏｏ（商標）が提供するサブジェクトカタログは、クラスタの階層を生成することによりデータを類別できる。このクラスタの階層においては、一般的なカテゴリクラスタは最上層レベルに位置し、より下層のクラスタリーフはより特定的なトピックに関連付けられている。
【０００３】
【発明が解決しようとする課題】
従来の管理技術、例えば階層的クラスタリングでは、共通する対象をまとめることはできるが、この結果得られる階層は一般に対象のクラスタへのハード（厳密な）割当て（hard assignment）を含んでいる。ここで、ハード割当てとは、対象を階層におけるただ１つのクラスタに割当てる手法を意味する。このような割当て形式では、対象、例えばテキスト文書を１つ以上のクラスタに関連付けることのできる潜在性が制限されてしまう。例えば、ある文書コレクションに対するトピックを生成するシステムにおいては、文書（対象）をクラスタ（トピック）にハード割当てすることにより、その文書が他のクラスタ（トピック）に含まれることは禁じられる。このように、テキストデータなどの対象をハード割当てする結果となる階層的クラスタリング技術では、特定の処理、例えばある文書コレクションに関するテキスト検索などにおいて、これらの対象が効率的に配置されることを妨げる可能性がある。
【０００４】
したがって、所与の任意の対象を階層における１つ以上のクラスタに割当てることができるように対象を階層的にクラスタリングする方法及び装置が望まれている。
【０００５】
【課題を解決するための手段】
本発明に関する特定の原理による製造の方法、装置および製品により、コンピュータ装置は、各文書が複数の単語を含む文書のコレクションを受信し、ある文書の部分を、各部分と該文書に含まれる１つ以上の単語との共起にもとづき、階層における１つ以上のクラスタに割当てることができる。本発明に関する特定の原理による製造の方法、装置及び製品は、コレクションの各文書を第１の対象（例えば「ｉ」）と定め、所与の文書の単語を第２の対象（例えば、「ｊ」）と定めることにより上述の割当て特性を実行することができる。まず始めに、コレクションを、階層の単一ルートクラスタを表すことのできる単一のクラスに割当てることできる。本発明に関する特定原理による、修正された期待値最大化（ＥＭ：Expectation-Maximization）法を、ルートクラスが２つの子クラスに分裂するまで、該クラスにおいて定められた各対象ペア（ｉ，ｊ）に基づき実行することができる。次に、各子クラスが再びさらに２つの子クラスに分裂するまで、各子クラスに対して同一の修正ＥＭ処理を行う。階層に関する選択された制約が満たされるまで、例えば階層が最大数のリーフクラスタに達するまで、この処理を繰り返す。生成される階層に含まれる各クラスタは、それぞれが互いに祖先（ancestors）ではないクラスタを含む、階層の他のクラスタに割当てられた対象を含んでもよい。
【０００６】
【発明の実施の形態】
本発明の特性及び原理による製造の方法、装置及び製品により、演算（コンピュータ）装置は、任意の文書が、該文書に含まれる単語に基づき、トピック階層における１つ以上のトピックに割当てられるように、文書コレクションの階層的ソフトクラスタリングを実行できる。
【０００７】
本発明の特性に係る方法、装置及び製品は、文書と単語のそれぞれを表す対象のペアに関して、修正された期待値最大化（ＥＭ）処理を実行し、対象の所与のクラスがトピック階層のすべてのノードにわたり、文書のトピックへの割当てが該所与のクラスのどの祖先にも基づくようにすることで上記の機能を実施することができる。さらに、階層の任意のトピックへの所与の文書の割当ては、その処理において考慮される特定の（文書、単語）ペアに基づいてもよい。本発明に関する特定原理による製造の方法、装置及び製品は、トピック階層に関連する選択された制約が満たされるまで、ある祖先クラスから生成されるすべての子クラスに対し、修正されたＥＭ処理を行ってもよい。結果的に生成されるトピッククラスタの階層表示が作成され、文書コレクションのトピックを要求するエンティティに対してこれを利用可能にすることができる。
【０００８】
図１には、本発明による特定の特性及び原理を実施できるコンピュータ装置環境の一例が示されている。図示されるように、演算装置環境はコンピュータ装置１００を含んでもよい。このコンピュータ装置１００は、デスクトップコンピュータ、ワークステーション、メインフレーム、クライアントサーバ、ラップトップ、パーソナルディジタルアシスタント、または当業界で知られる同様の汎用またはアプリケーション特定コンピュータシステムでもよい。例えば、コンピュータ１００は、プロセッサ１０２と、メインメモリ１０４と、補助メモリ１０６と、バス１０８と、コンピュータ装置において利用できる他の多くの要素及び機能を含んでもよい。これらの要素は、バス１０８を介して種々の入出力装置、例えばキーボード１１０、ディスプレイ１１２、ネットワークコネクタ１１４、及び大容量記憶装置１１６に関連付けることができる。
【０００９】
プロセッサ１０２は、本発明に関する特定の特性による論理的及び数学的演算を実行する、当業界で周知の任意の汎用または専用プロセッサでよい。さらに、プロセッサ１０２を、マルチタスク処理を行う複数のプロセッサに置換えても、これらで補ってもよい。
【００１０】
メインメモリ１０４及び補助メモリ１０６は、データを記憶する既知の任意のタイプの記憶装置でよい。メインメモリ１０４は及び補助メモリ１０６には、磁気、半導体、光学の少なくともいずれかのタイプの記憶装置を含んでもよいが、これらに限定されない。補助メモリ１０６は、さらに、プロセッサ１０２のデータに対する迅速なアクセスを可能にする記憶装置、例えばキャッシュメモリなどでもよい。本発明に関する選択された特性による１構成においては、メインメモリ１０４及び補助メモリ１０６は、クラスタリングするデータ、クラスタリングされたデータ、プログラム命令の少なくともいずれかを記憶し、本発明に関する特定の特性による方法を実施することができる。
【００１１】
バス１０８は、単一及び／または複数バス構成であり、コンピュータ１００の要素と外部要素、例えば、キーボード１１０、ディスプレイ１１２、ネットワークコネクタ１１４及び大容量記憶装置１１６を含む出入力装置などとの間のデータ転送を可能にする。キーボード１１０により、コンピュータ装置環境のユーザはコンピュータ１００と接続が可能になる。キーボード１１０は、他の入力装置、例えばマウス、タッチスクリーン要素などで置換えたり、これらで補ったりしてもよい。ディスプレイ１１２は、当業界で知られるように、ユーザに対して情報を表示することができる。ネットワークコネクタ１１４は、ローカルエリアネットワークなどのネットワークまたはインターネットに対してコンピュータ１００を接続したり、情報交換したりできるようにする。大容量記憶装置１１６は、コンピュータ１００の外部に設けられた、データを記憶する任意の既知の記憶装置でよい。この大容量記憶装置１１６は、磁気、半導体、光学、テープの少なくともいずれかのタイプの記憶装置でよく、クラスタリングするデータ、クラスタリングされたデータ、プロセッサ１０２により実行可能なプログラム命令の少なくともいずれかを記憶し、本発明に関する特定の特性による方法を実行することができる。
【００１２】
コンピュータ１００は、対象、例えばそれぞれが複数の単語を含むテキスト文書などの階層的ソフトクラスタリングを実行すべく構成することができる。階層的ソフトクラスタリングを実行する方法は、例えば、最大尤度及び期待値最大化（ＥＭ）アルゴリズムの確定的変型（deterministic variant）を使用する方法など複数の方法がある。最大尤度技術は、データ観測（observe）尤度を最大化するパラメータ値を求める技術であり、クラスタリング技術の自然なフレームワークである。ＥＭアルゴリズムは最大尤度内の確率的モデルのパラメータを知るために使用される既知のアルゴリズムである。ＥＭアルゴリズムについては、Ｇ．Ｊ．マクラクラン（G.J.McLachlan）及びＴ．クリシュナン（T.Krishnan）による”The EM Algorithm and Extensions”, Wiley, New York, 1997（その開示内容を本願明細書の一部として援用する）にさらなる記載がある。確定的アニーリングＥＭ（deterministic annealing EM）として知られる、ＥＭアルゴリズムの変型（variant）は、対象の階層的クラスタリングを実行する。しかしながら、特定の例では、このような階層的クラスタリングが対象のハード割当てを行う結果になることもある。確定的アニーリングＥＭについては、ローズ他（Rose et al.）による”Statistical Mechanics and Phase Transitions in Clustering”, Physical Review Letters, Vol. 65, No. 8, American Physical Society, August 20, 1990, pages 945-48（その開示内容を本願明細書の一部として援用する）にさらなる情報が記載されている。
【００１３】
確定的アニーリングＥＭは、標準ＥＭアルゴリズムに比して複数の利点がある。以下、このＥＭアルゴリズムの変型について簡単に説明する。
【００１４】
確定的アニーリングＥＭ
観測可能なデータサンプルｘ（∈Ｘ）が与えられ、密度がｐ（ｘ；Θ）（Θは推定される密度分布のパラメータ）である場合、Ｘに対応する観測不可能データの測度空間Ｙが存在する。
【００１５】
さらに、不完全データサンプル｛Ｘ＝ｘｒ｜ｒ＝１，．．．，Ｌ｝が与えられた場合、ＥＭアルゴリズムの目標は、尤度関数を最大化するΘの最尤推定値を算出することである。これは、Ｌｃで示される完全データ対数尤度関数の最大化に等しく、次式により定められる。
【００１６】
【数１】
0004384398.tif 000002
さらに、Θの初期推定値から始まり、次の２つのステップを交互にする反復手順が、（完全データ）対数尤度関数の局所最大値に収束することが示されている。この手順をＥＭアルゴリズムと呼ぶ。
【００１７】
Ｅステップ：Ｑ関数を下記のように計算する。
【００１８】
【数２】
0004384398.tif 000003
Ｍステップ：Θ（ｔ＋１）をΘと等しく設定し、Ｑβ（Θ；Θ（ｔ））を最大にする。
【００１９】
Ｌｃ（Θ；Ｘ）を置き換えることにより、Ｑβ（Θ；Θ（ｔ））を次式のように書き換えることができる。
【００２０】
【数３】
0004384398.tif 000004
さらに、次式により、
【数４】
0004384398.tif 000005
Ｑ（Θ；Θ（ｔ））が求められ、次式のように書くことができる。
【００２１】
【数５】
0004384398.tif 000006
ＥＭアルゴリズムの確定的アニーリング変型は、次式のように、ｐ（ｙｒ｜ｘｒ；Θ（ｔ））における事後確率のパラメータβによるパラメータ表示を含む。
【００２２】
【数６】
0004384398.tif 000007
このように、βが１であれば、ｆ（ｙｒ｜ｘｒ；Θ）＝ｐ（ｙｒ｜ｘｒ；Θ）である。したがって、Ｑ（Θ；Θ（ｔ））を求める式において定められる確率ｐ（ｙｒ｜ｘｒ；Θ（ｔ））を、ｆ（ｙｒ｜ｘｒ；Θ（ｔ））で置き換えると、関数Ｑβは、ＥＭアルゴリズムのＱ関数に一致する。これは確定的アニーリングＥＭアルゴリズムが示唆している。確定的アニーリングＥＭアルゴリズムの特性については、ウエダ他（Ueda et al.）による”Advances in Neural Information Processing Systems 7”, Chapter on Deterministic Annealing variant of the EM Algorithm, MIT Press, 1995に記載される。ここでは、処理を以下ように記載している。
１．β＝βｍｉｎに設定する。０＜βｍｉｎ＜＜１
２．初期推定値Θ（０）を任意に選択し、ｔ＝０に設定する。
【００２３】
３．収束するまで次の２つのステップを反復する。
【００２４】
Ｅステップ：次式を計算する。
【００２５】
【数７】
0004384398.tif 000008
Ｍステップ：Θ（ｔ＋１）をΘと等しく設定し、これによりＱβ（Θ；Θ（ｔ））を最大にする。
【００２６】
４．βを増加させる
５．β＜βｍａｘであれば、ｔ＝ｔ＋１に設定し、処理をステップ３から繰り返す。β＜βｍａｘでなければ、処理を停止する。
【００２７】
上記の確定的アニーリングＥＭ処理は、標準的なＥＭアルゴリズムに優る３つの主な利点を有する。すなわち、（１）標準ＥＭアルゴリズムに比べて、大域最大値（global maximum）に収束しやすく、（２）βｍａｘ＜１に設定することにより、オーバーフィッティング（over fitting）が回避され、（３）データを説明するために必要なクラスタの数がβに依存するので、クラスタ階層を誘導する。
【００２８】
対象の階層の誘導を助けるために確定的アニーリングＥＭのバリエーションが提案されている。階層的非対称クラスタリングモデル（ＨＡＣＭ：Hierarchical Asymmetric Clustering Model）と呼ばれるこのようなモデルの１つには、分布クラスタリング（distributional clustering）と呼ばれる技術が含まれる。ＨＡＣＭに関するさらなる情報が、ホフマン他（Hofmann et al.）による”Statistical Models for Co-Occurrence Data”, A.I. Memo No. 1625, Massachusetts Institute of Technology, 1998に記載されている。ＨＡＣＭは２つの隠れた変数に依拠している。第１の変数、Ｉｉαは、対象「ｉ」のクラスαへの割当てを示す。第２の変数Ｖｒανは、クラスαと対象ｉ及びｊが与えられた場合の階層におけるクラスνの選択を示す。（ｉ，ｊ）は、対象ｉが対象ｊと共に起きること（joint occurrence）を示す。ここで、（ｉ，ｊ）∈ＩＸＪであり、すべてのデータに番号が付けられ、サンプル集合Ｓ＝（ｉ（ｒ），ｊ（ｒ），ｒ）：１≦ｒ≦Ｌに収集される。２つの変数、Ｉｉα及びＶｒανを２値化することにより、尤度関数を簡素化することができる。
【００２９】
図２のブロック図は、ホフマン他による”Statistical Models for Co-Occurrence Data”, A.I. Memo No. 1625, Massachusetts Institute of Technology, 1998に示されるように、ＨＡＣＭがどのように機能するかを例示する。図２に示されるように、階層２００は、祖先ノード２１０−２２０及びリーフノード２２２−２２８を含む複数ノードを含む。ＨＡＣＭによれば、各対象ｉは、変数Ｉｉαを使用して、階層２００の１リーフノードに割当てられる。例えば、リーフノード２２６は、対象ｉが割当てられたとして黒で示されている。さらに、あるリーフノード、例えばノード２２６に割当てられた任意の対象ｉに対して対象ｊのレベルを生成するための選択は、割当てられたリーフノードから階層のルートまでのアクティブ垂直パスに限定されている。また、ｎｉで示される、ある対象ｉに関連するすべての対象が同一の垂直パスから生成され、変数Ｖｉｊανがその垂直パスにおけるノードの選択を制御する。例えば、図２に示されるように、対象ｊは、図において影をつけていないノード２１０から２１６を含むノードのパスからのみ、変数Ｖｉｊανに基づき選択可能である。
【００３０】
ＨＡＣＭをさらに説明するため、図３にこのモデルの例示的な表示を示す。ＨＡＣＭに対する依存（dependencies）には、観測及び非観測データを含む。ＨＡＣＭはサンプル集合Ｓｉの生成を直接モデリングし、サンプル集合Ｓｉは、Ｉ（対象ｉを含む集合）に関する経験分布ｎｊ｜ｉを表す。ここで、
0004384398.tif 000009
である。図示されるように、ＨＡＣＭにより、対象ｉを、ｉに依存する確率ｐ（ｉ）を介して生成することができる。さらに、ｉ（ｒ）＝ｉとなるよう、任意の組み合わせ（ｉ（ｒ），ｊ（ｒ））に対する対象ｊの生成は、Ｉｉαを使用しクラスαにより決定する。したがって、対象ｊの生成は、変換Ｖｒαｖにより、ｉ及びαの祖先の集合に依存することがわかる。
【００３１】
ＨＡＣＭは次の確率に基づく。
【００３２】
【数８】
0004384398.tif 000010
上式において、α（ｉ）は、所与のｉに対してＳｉを生成するのに使用するクラスを表し、ν（ｒ）は、α（ｉ）が与えられた場合にｊ（ｒ）を生成するために使用されるクラスを表している。
【００３３】
しかしながら、ｉ（ｒ）＝ｉであるのはちょうどｎｉの対象であり、さらに、Ｖｒανは二値化され、ｊ（ｒ）の生成に使用される（未知の）クラスν（ｒ）を除いて０に等しいので、ｐ（Ｓｉ｜α（ｉ））は次式のように書き換えることができる。
【００３４】
【数９】
0004384398.tif 000011
ｐ（Ｓｉ）に対する完全モデル式（complete model formula）は、α（ｉ）に関する加算（summing）により求められ、次式のように表すことができる。
【００３５】
【数１０】
0004384398.tif 000012
νがαとｉ（ｐ（ν｜α，ｉ）＝ｐ（ν｜α）によってではなく、αだけによって条件付けられているので、上記の確率ｐ（Ｓｉ）は、ＨＡＣＭの簡素化されたバージョンを表しているが、当業者であれば、ここに記載されたＨＡＣＭの特徴及び処理が複雑なバージョンにも同様に適用されることがわかるであろう。
【００３６】
なお、積は（ｉ，ｊ）のペアに関して求められ、ここで、ｉは固定値である。したがって、この積はｊにのみ関するものとして見ることができる。上記のモデルから、ｐ（Ｓｉ）を求める式は完全データ対数尤度Ｌｃであり、以下のように表すことができる。
【００３７】
確定的アニーリングＥＭの別の変形について、Ｌ．Ｄ．ベーカ他（L.D. Baker et al.）による”A Hierarchical Probabilistic Model for Novelty Detection in Text,” Neural Information Processing Systems, 1998に記載されている。ベーカ他に記載されるモデルは、階層的マルコフモデル（ＨＭＬＭ）と呼ぶことができる。ＨＡＣＭと同様に、ＨＭＬＭも次式に基づいてｐ（Ｓｉ）を直接モデリングする。
【００３８】
【数１１】
0004384398.tif 000013
完全データの対数尤度は、ｐ（Ｓｉ）からＨＭＬＭに対して求めることができ、以下のように表すことができる。
【００３９】
【数１２】
0004384398.tif 000014
図４には、ＨＭＬＭが例示的に示されている。図示されるように、ＨＡＣＭとＨＭＬＭの唯一の相違点は、ＨＭＬＭでは、集合Ｓｉを観測する事前確率ｐ（ｉ）を使用しない点である。しかしながら、当業者であれば、特定のアプリケーション、例えばトレーニング集合における文書に関して優先度が与えられないテキスト分類などでは、集合Ｓｉに対する均一の事前確率が望ましいことがわかるであろう。このような場合には、ＨＭＬＭとＨＡＣＭとの上記の差異は除去される。
【００４０】
ＨＡＣＭ及びＨＭＬＭは対象の階層的ソフトクラスタリングを提供できるが、これらのモデルは、モデルに関連する２つの特性のために、依然としてハード割当てとなる可能性があることに留意すべきである。２つの特性とは、第１に、クラスαが階層のリーフのみの範囲にわたり、クラスνがαの祖先にのみわたることである。第２に、対象ｊからの寄与（contributions）は直接、積（product）に収集される。第１の特性は、対象ｉが、誘導階層のリーフにのみ割当てられることを示している。例えば、図２を参照すると、ＨＡＣＭ及びＨＭＬＭでは、対象ｉをノード２２４から２２８にのみ割当てる。第２の特性は、対象ｉが与えられた場合、対象ｉに関連する全対象ｊが同一のリーフαの祖先により説明されなければならないことを示している。すなわち、ｉに関連する対象ｊをαのどの祖先によっても説明できない場合には、ｉをαに割当てることはできない。したがって、ｉの割当てに関するこのような制限の結果、一般に、対象ｉとｊのいずれかまたは両方が、誘導階層にハード割当てされることになる。よって、テキスト分類システムでは、ＨＡＣＭ及びＨＭＬＭを実施することにより、文書とその文書の単語の少なくともいずれかの特定クラスタへのハード割当てに基づき、粒度が限定されたトピックが形成される可能性がある。
【００４１】
本発明に関する特定の原理による製造の方法、装置及び製品は、リーフノードだけに対する依存を解消し、任意の集合Ｓｉを、誘導階層に含まれる任意のリーフノード及び／または祖先ノードの組み合わせにより説明可能にする。すなわち、対象ｉをブロックと考えるのではなく、それらと共起する任意の対象ｊに基づいて階層に割当てられるピースと考えることができる。例えば、本発明に関する特定の特性及び原理による１構成においては、コンピュータ１００により実行されるトピック的クラスタリングアプリケーションにより、ある文書ｉの部分を、その文書ｉに含まれる異なる単語ｊに対する誘導階層内の異なるノードに割当てることができる。これは、各文書ｉが、その文書ｉに含まれるすべての単語ｊに対する階層中の同一リーフノードに関連することが想定されるＨＡＣＭ及びＨＭＬＭとは対照的である。
【００４２】
本発明の１実施形態は、変数Ｉｒα（文書の階層への割当てを制御する）を、トピック的クラスタリング処理において考慮される特定の文書と単語のペア（ｉ，ｊ）に依存するように定義することにより、共起する任意の対象ペア、例えば文書と単語のペア（ｉ，ｊ）などを観測する確率を直接的にモデリングできる。本発明に関する特定の原理による１構成においては、クラスαは誘導階層における全ノードにわたり、文書（対象ｉ）をリーフノードだけでなく、その階層における任意のノードに割当てることができる。さらに、クラスνを階層におけるαの任意の祖先として定義してもよい。νに関する制約により、ノードが階層的に組織されていることが保証される。
【００４３】
図５は、本発明の１実施形態により実施されたモデルを例示的に示す図である。上述のモデルと本発明の１実施形態との１つの相違点は、本発明では、ＨＡＣＭ及びＨＭＬＭの場合のような確率ｐ（Ｓｉ）ではなく、確率ｐ（ｉ（ｒ），ｊ（ｒ））をモデリングする。
【００４４】
【数１３】
0004384398.tif 000015
式ｐ（ｉ（ｒ），ｊ（ｒ））の代替式は、ｐ（α）ｐ（ｉ（ｒ）｜α）をｐ（ｉ（ｒ））ｐ（α｜ｉ（ｒ）（いずれもｐ（α，ｉ（ｒ））に等しい）で置き換える。よって、代替式は次のようになる。
【００４５】
【数１４】
0004384398.tif 000016
ワークアラウンドにより、同等の代替式を使用して、ｐ（ｉ（ｒ），ｊ（ｒ））の本来の式と同じ結果を得ることができる。
【００４６】
前述のモデルと本発明との差をより明確に説明するために、ｐ（Ｓｉ）＝Пｒ：ｉ（ｒ）＝ｉｐ（ｉ（ｒ），ｊ（ｒ））により、ｐ（Ｓｉ）を本発明に対して求めることができる。したがって、ｐ（Ｓｉ）を次のように表すことができる。
【００４７】
【数１５】
0004384398.tif 000017
完全データ対数尤度は、次式により与えられる。
【００４８】
【数１６】
0004384398.tif 000018
ｐ（Ｓｉ）の上記求められた式からわかるように、所与のαに対し、対象ｊは、ＨＡＣＭ及びＨＭＬＭの場合のように積に収集されず、本発明では、積がすべてのクラスαにわたる混合の後にのみ得られるように確率ｐ（Ｓｉ）を決定する。よって、ある誘導階層の異なる垂直パスから異なる対象ｊが生成できる。すなわち、Ｉｉαの非ヌル値に関連する階層中のパスから生成できる。すべての対象ｊはある階層の同じ垂直パスから生成されなければならないという、ＨＡＣＭ及びＨＭＬＭにおける制約は、Ｉｉαが二値を有することを強いる。図５に示されるモデルを実施する製造方法、装置及び製品では、ＨＡＣＭ及びＨＭＬＭに共通するこの制約を除去し、隠れた変数Ｉｉαのすべての例が、以下に説明する修正版ＥＭ処理を使用した再推定の後に実際の値を求めることができる。さらに、αは階層におけるどのノードでもよいので、対象ｉを階層の異なるレベルに割当てることができる。したがって、図５に示す方法によってモデルを実施することにより、ｉ及びｊの対象のハード割当てを解消し、これらの対象のいずれにも純粋な階層的ソフトクラスタリングを行うことができる。
【００４９】
すでに述べたように、本発明の１実施形態では、修正された確定的アニーリングＥＭ処理を実行して、図５に示されるモデルを実施することができる。本発明に関する特定の原理による１構成においては、確率ｐ（ｘｒ，ｙｒ：Θ）におけるΘは、確率ｐ（ｉ（ｒ），ｊ（ｒ））により求められる現在の推定値の集合に関連付けられる。本発明の特性及び原理によるＱ関数は、次のように定義できる。
【００５０】
【数１７】
0004384398.tif 000019
ここで、
【数１８】
0004384398.tif 000020
本発明の特性による製造の方法、装置及び製品は、さらに、確定的アニーリングＥＭ処理の修正されたＥ及びＭステップを実施して、図５に示されるモデルに関する確率を決定することもできる。例えば、Ｅステップ処理はＱβから直接求められ、ｉが与えられれば、Ｉｉαは１つのαを除きすべてに対してゼロに等しく、ｉ，ｊ及びαが与えられれば、Ｖｉｊανは１つのνを除きすべてに対してゼロと等しいので、Ｑ関数Ｑβ（Θ；Θ（ｔ））＝Ａ＋Ｂである。ここで、
【数１９】
0004384398.tif 000021
及び
【数２０】
0004384398.tif 000022
しかしながら、
【数２１】
0004384398.tif 000023
これにより、上式におけるＡを次のように定義することができる。
【００５１】
【数２２】
0004384398.tif 000024
ここで、
【数２３】
0004384398.tif 000025
Ａの決定と同様に、Ｂは次の形式で求めることができる。
【００５２】
【数２４】
0004384398.tif 000026
ここで、
【数２５】
0004384398.tif 000027
上記のように、＜Ｉｉｊα＞β及び＜Ｉｉｊα  Ｖｉｊαν＞βは、本発明に関する特定の原理による修正された確定的アニーリングＥＭ処理のＥステップ処理に対応する。さらに、＜Ｉｉｊα  Ｖｉｊαν＞βは、αが与えられた場合の、誘導階層における任意の祖先への割当てに対応する。
【００５３】
本発明の１実施形態により実行される、修正されたＭステップ処理は、Ｑβ（Θ；Θ（ｔ））を最大にするパラメータΘを求めることを目的とする。このような確率分布において固有なのは、次の形式を有する制約に関連する制約された最適化限定（constrained optimization restriction）である。
【００５４】
【数２６】
Σｘｐ（ｘ；Θ）＝１
本発明に関する特定の原理による１構成においては、ラグランジェ乗数法を用いて対応する非制約最大値を検索することができる。例えば、図５に示されるモデルにおいて実施された確率ｐ（α）を求めるために、ラグランジェ乗数法が導入され、次のようにｐ（ｘ；Θ）を求める。
【００５５】
【数２７】
0004384398.tif 000028
これは、制約Σｘｐ（α；Θ）＝１を利用することにより、次に示す結果となる。
【００５６】
【数２８】
0004384398.tif 000029
上記と同じ原理を用いて、図５に示されるモデルで実施された残りの確率を求めることができる。結果は次の通りである。
【００５７】
【数２９】
0004384398.tif 000030
【数３０】
0004384398.tif 000031
【数３１】
0004384398.tif 000032
上記のように、確率ｐ（α；Θ），ｐ（ｉ｜α；Θ），ｐ（ν｜α；Θ），ｐ（ｊ｜ν；Θ）は、本発明により実施される修正された確定的アニーリングＥＭ処理において使用されるＭステップ再推定処理を定義する。
【００５８】
本発明に関する特定の原理による製造の方法、装置及び製品を、対象ｉ及びｊに与えられた意味によって、異なるアプリケーションに対し、図５に示されたモデルを実施すべく構成することもできる。このような１つ構成は、トピック検出に基づく文書クラスタリングに適用することが可能である。このような構成では、対象ｉが文書を表し、対象ｊが文書に含まれる単語を表し、文書のクラスタとトピックの少なくともいずれかが、誘導階層のリーフとノードの一方または両方により与えられる。文書コレクションに関連するトピックは、任意のクラスタを図５に示される単語確率分布ｐ（ｊ｜ν）により定められるトピックと解釈することにより得ることができる。本発明に関する特定原理による階層的ソフトモデルは、クラスタの解釈に際し、複数の特性を考慮することができる。複数の特性とは、例えば、（１）ある文書は複数のトピックをカバーすることができる（または複数のトピックにより説明できる）。（ｐ（ｉ｜α）により提供される対象ｉのソフト割当て）、（２）トピックは、多義性（複数の異なるが、関連のある意味を表す単語の特性）及び特殊性のために異なるトピックに属することができる単語の集合により最適に記述される（ｐ（ｊ｜ν）により提供される対象ｊのソフト割当て）、及び（３）トピックは階層的に組織でき、これはクラスタに関して誘導された階層に対応する。本発明に関する特定原理による１構成においては、階層に対する一般的な確率モデルが、トピックを階層的に組織できない文書コレクションを処理できる（すなわち、平坦な（flat）モデル）。この場合、確率ｐ（ν｜α）は、ν＝αに集中し、この結果、トピックは階層ではなく平坦な集合となる。
【００５９】
図６は、本発明の１実施形態により実行できる文書クラスタリング処理の例を表すフローチャートである。本発明に関する特定原理による１構成では、コンピュータ１００は、文書（対象ｉ）の集合またはコレクションによってカバーされるトピックを識別することにより文書をクラスタリングすべく構成できる。この場合、各文書は複数の単語（対象ｊ）を含むことができる。コンピュータ１００は、要求発行者（requesting entity）からの要求に基づき、本発明に関する特定原理によるクラスタリング特性を実行できる。要求発行者は、図１のコンピュータ装置に関連する入出力要素を介してコンピュータに接続するユーザでもよいし、コンピュータ１００から隔てて位置するユーザでもよい。遠隔ユーザは、遠隔位置、例えばネットワークに接続された別のコンピュータ装置から、ネットワークコネクタ１１４によりコンピュータ１００に接続できる。さらに、要求発行者は、コンピュータ１００のサービスを要求する方法（process）または演算者（computing entity）でもよい。例えば、要求発行者は、文書コレクションに関連するクラスタリング処理を要求する別のコンピュータ装置（ネットワークを介して遠隔配置される、またはバス１０８に局所的に接続される）に関連付けてもよい。例えば、文書コレクションに関連する検索処理を提供するサーバがコンピュータ１００に対し、特定の文書コレクションのトピックを決めるよう要求してもよい。この例では、コンピュータ１００は、文書コレクションのクラスタリングの要求を受け、クラスタリング処理の結果を要求発行者に対して利用可能にすることができる。なお、当業者であれば、異なるタイプの多数の要求発行者及び要求タイプを、本発明の範囲を逸脱することなく実施できることがわかるであろう。
【００６０】
文書コレクションは、メモリ１０４，１０６及び１１６のいずれにも配置することができる。また、文書コレクションを、図１に示されるコンピュータ環境から隔てて、例えばネットワークに接続されたサーバに配置してもよい。このような場合には、コンピュータ１００は、ネットワークコネクタ１１４を介して文書コレクションを受信するよう構成できる。当業者であれば、文書コレクションの位置は上記の例に限定されず、コンピュータ１００は、当業界で知られた方法及び装置を使用してこれらの位置に対してアクセスできるよう構成可能であることがわかるであろう。
【００６１】
図６を参照すると、本発明に関する特定原理による１構成においては、コンピュータ１００は、誘導可能な階層（ツリー）に関連する１つ以上の条件を定めることにより、本発明に関する特定原理によるクラスタリング技術を開始することができる（ステップ６０５）。この条件により、コンピュータ１００は、誘導階層がそこに定められるクラスタに関する所望の構造にいつ達するかを決定することが可能になる。例えば、（本発明の特性による階層的ソフトモデルを実施するための命令及び／またはプログラムコードを実行することのできる）プロセッサ１０２に、クラスタリングされている文書コレクションにおいて共起する対象（ｉ，ｊ）の検索の停止を命令するという条件を定めてもよい。このような条件は、所定数のリーフと誘導階層のレベルの少なくともいずれかに基づくことができる。本発明に関する特定原理による１構成においては、コンピュータ１００は、ユーザからキーボード１１０などの入出力装置を介してこれらの条件を受信してもよい。例えば、コンピュータ１００によりユーザに条件を提供するよう促してもよいし、文書コレクションのサイズに基づき、ユーザがコンピュータ１００に自発的に条件を決定するよう命令してもよい。当業者であれば、本発明の範囲を逸脱することなく、他の多数の条件を実施可能であることがわかるであろう。
【００６２】
図６を再び参照すると、１つ以上の条件が決定すると、コンピュータ１００は、クラスタリングの対象である文書コレクションを受信（または検索）することができる（ステップ６１０）。文書コレクションにコンピュータ１００がアクセス可能になると、プロセッサ１０２は文書コレクション全体をクラスαに割当てることができる（ステップ６１５）。まず、クラスαは、文書コレクションに関連する単数または複数のメイントピックを表すルートノードまたはクラスタを表すことができる。また、プロセッサ１０２は、パラメータβを初期値に設定することができる（ステップ６２０）。１実施形態においては、パラメータβは、目的関数の複雑性を制御してクラスタの数によって最適化を行い、かつパラメータ値自体の計算を制御する値であってもよい。βの初期値は、１までの非常に低い値で（すなわち、．０１）、これに対して、目的関数の一義的な（unique）最大値を求めるためには、１つのクラスタのみが要求される。βの値は、コレクションのサイズに基づき、プロセッサ１０２によって自発的に決定してもよいし、キーボード１１０などの入出力装置を介してユーザが提供してもよい。
【００６３】
次に、プロセッサ１０２は、本発明に関する特定原理による修正された確定的アニーリングＥＭ処理における修正されたＥステップを実行することができる（ステップ６２５）。よって、クラスα及び決定したパラメータβの値が与えられれば、Ｑβ（Θ；Θ（ｔ））を、本発明に関する特性及び原理による上記の式にしたがって計算することができる。（すなわち、Ｑβ（Θ；Θ（ｔ））＝Ａ＋Ｂ）
さらに、プロセッサ１０２は、クラスα及びパラメータβの決定値が与えられれば、本発明に関する特定の原理にしたがって、最大化処理を実行することができる（ステップ６３０）。すなわち、確率分布ｐ（α；Θ），ｐ（ｉ｜α；Θ），ｐ（ν｜α；Θ），ｐ（ｊ｜ν；Θ）を決定する。本発明に関する特定原理による修正された確定的アニーリングＥＭ処理が実行されると、プロセッサ１０２は、クラスαが２つの子クラスに分裂しているかを決定することができる（ステップ６３５）。
【００６４】
本発明に関する特定原理による１構成においては、プロセッサ１０２は、確率分布ｐ（ｉ｜α）に基づき、クラスαの分裂を認識することができる。まず、パラメータβが非常に低い値に設定された場合には、文書コレクションに含まれるすべての文書及び単語（ｉ及びｊ）は、クラスαに割当てられる同じ確率を有する。しかしながら、パラメータβの値が増すにつれ、異なる文書に関するこの同じ確率は、これらの文書に含まれる異なる単語に基づき互いに分岐し始める。この分岐の結果、文書の２つのクラス（またはクラスタ）が、ある祖先クラスから実現する。これにより各子クラスには、各文書に含まれる異なる単語に基づき同様の確率ｐ（ｉ｜α）を有する文書が含まれることになる。例えば、ステップ６１５において、まずクラスαに割当てられた文書コレクションが、単語Ｗ１，Ｗ２及びＷ３を含む文書ＤＯＣ１と、単語Ｗ４，Ｗ５及びＷ６を含む文書ＤＯＣ２とを含むと想定する。ＤＯＣ１及びＤＯＣ２を含むこの初期クラスαは、パラメータβの初期値においては、このコレクションの各文書の単語に基づき、該各文書に対して同じ確率ｐ（ｉ｜α）を生成することができる。しかしながら、βの値が高くなると、この同じクラスαでも、Ｗ１に基づいた場合にはＤＯＣ１に関して第１の確率ｐ（ｉ｜α）となり、Ｗ２の基づいた場合にはＤＯＣ１に対して第２の確率となる。同様に、より高いβの値では、ＤＯＣ２は、Ｗ４，Ｗ５，Ｗ６に基づき、第１の確率に関連付けることができる。ここで、本発明に関する特定原理によれば、単一の文書、例えばＤＯＣ１を、同一文書内に含まれる単語に基づいて２つのクラス（またはクラスタ）に割当てることができる。
【００６５】
ステップ６３５において、確率ｐ（ｉ｜α）がコレクションの各文書に関して同一であるか、またはコレクションの残りの文書に対応する、２つの確率値の一方にあたるかを決定すべく構成することができる。クラスαの分裂があったと判断すると（ステップ６３５；ＹＥＳ）、プロセッサ１０２は、ステップ６０５において決めた条件が満たされているかを決定することができる（ステップ６４０）。処理におけるこの段階において、階層が誘導されている（すなわち、クラスαの２つの子クラスへの分裂）。したがって、プロセッサ１０２が、条件（例えば、リーフの最大数など）が満たされていると判断すると（ステップ６４０；ＹＥＳ）、誘導階層が完成し、文書は、各文書に含まれる単語に関連するトピックに基づきクラスタリングされ、クラスタリング処理が終了する（ステップ６４５）。
【００６６】
一方、プロセッサ１０２が、現在のパラメータβの値では初期クラスαが分裂していないと判断すると（ステップ６３５；ＮＯ）、パラメータβの値を増加することができ（ステップ６５０）、処理はパラメータβの増加した値と共にステップ６２５に戻る。パラメータβを増加する方法は、ステップ値を用いて制御しもよい。このステップ値は、ユーザにより予め定めてもよいし、パラメータβの初期値及びユーザにより提供されるさらなるパラメータ（すなわち、クラスタの数、階層の深さなど）から計算してもよい。さらに、初期クラスαは２つのクラス（それぞれが個別のクラスαとして定義される）に分裂しているが（ステップ６３５；ＹＥＳ）、階層の条件が満たされていない場合（ステップ６４０；ＮＯ）には、プロセッサ１０２は、各新しい子クラスαに対するパラメータβを、初期クラスαを分裂させた値に設定する（ステップ６５５）。続いて、プロセッサ１０２は、階層の条件が満たされるまで（ステップ６４０；ＹＥＳ）、新しい子クラスαのそれぞれに対して同じステップを実行し（ステップ６２５−６５５）、クラスタリング処理を終了する（ステップ６４５）。
【００６７】
本発明に関する特定原理による１構成においては、クラスタ処理の終了（ステップ６４５）を、コンピュータ１００による、誘導階層に関連する表示を生成により行い、この表示をメモリ（すなわち、メモリ１０６，１０４及び／または１１６）に記憶してもよい。この表示は、クラスタリングされた文書コレクションに関するトピックを反映することができ、種々の形式、例えば、階層とクラスタの少なくともいずれかに関する１つ以上の表、リスト、チャート、グラフ、及び文書コレクションのトピックに関連する誘導階層及びクラスタを反映する他の任意のタイプの表示として生成できるが、これらの限定されるものではない。コンピュータ１００は、クラスタリング処理を実行する（すなわち、文書コレクションのトピックを決定する）ための要求に応じて、既に説明したように、記憶された表示を要求発行者が利用可能にすることができる。表示は、ネットワークコネクタ１１４またはバス１０８を介して発行者に利用できるようにしてもよい。さらに、表示をコンピュータ１００によって送信してもよいし、発行者が検索してもよい。さらに、階層の表示を、発行者による検索及び／または使用のためにメモリ（例えばデータベース）に送信するようにコンピュータ１００を構成してもよい。例えば、コンピュータ１００から隔てて位置するサーバが、コンピュータ１００により提供される１つ以上の階層に関する表示を１つ以上含むデータベースにアクセスすることもできる。階層は、１つ以上の文書コレクションに関連するトピックのクラスタを含んでもよい。例えば、サーバは、データベースにアクセスし、特定の文書コレクションに関して検索動作を処理することができる。本発明に関する特定原理による別の実施形態においては、コンピュータ１００はディスプレイ１１２を介して表示をユーザに対して利用可能にしてもよい。この構成では、コンピュータ１００は、誘導階層及び階層のクラスタが表すトピックを反映するグラフ表示を生成し、この表示を、ユーザが見られるようにディプレイ１１２に供給することができる。
【００６８】
本発明による特定の構成をさらに説明するために、図７には、本発明により生成できる、例示的な文書コレクションに対する例示的なトピック階層７００が示されている。階層７００は、オクラホマシティの爆破に関するニュース記事に関連付けられた特定数の文書（すなわち、２７３の別々の文書）を含む文書コレクションを反映することができる。この例では、文書は７６８４の異なる空でない（non-empty）単語を含んでもよい。空の単語とは、限定詞、前置詞などを表し、当業界で知られた技術、例えばストップリストなどを用いて、コレクションから省くことができる。階層７００の生成に先立ち、プロセッサ１０２は、誘導階層７００に対して最大４つのリーフという階層条件を定めていてもよい。
【００６９】
図示されるように、階層７００は７つのノード（７１０から７７０）と４つのリーフ（７４０から７７０）を含む。各ノードを、ｐ（ｊ｜ν）が最高である、コレクションの最初の５つの単語に関連付けることができる。本発明による階層７００の生成において、ノード７１０（パラメータβ１で、クラスα１に定義されている）に関連付けられた文書コレクションは、パラメータβ１の値の増加に続いてクラスα１の分裂を決定した際に、２つの子トピック／クラスタに分割されていてもよい。この例示的な階層７００においては、この２つの子トピック／クラスタは、クラスα１１及びα１２によってそれぞれ定められるノード７２０と７３０に関連付けられ、クラスα１の分裂がパラメータ値β２で発生している。
【００７０】
さらなる生成の間に、パラメータ値がβ２からβ３に増加した際に、α１１及びα１２の各クラスが、２つの子トピック／クラスタに分裂してる。図示されるように、クラスα１１で定められるノード７２０は、クラスα２１及びα２２によってそれぞれ定められるノード７４０と７５０とに分裂している。一方、クラスα１２で定められるノード７３０は、クラスα２３及びα２４によってそれぞれ定められるノード７６０と７７０とに分裂されている。
【００７１】
図７よりわかるように、本発明では、例示的な文書コレクションを、（文書、単語）のペアの共起に基づき、選択されたトピックにクラスタリングすることができる。例えば、階層７００においては、ノード７２０は爆破の調査に関するトピック／クラスタを反映することができ、ノード７３０は爆破事件そのものに関連するトピック／クラスタを反映してもよい。ノード７２０は、さらに２つのトピック、すなわち、調査自体に関連するトピック（７４０）と爆破に関する裁判に関連するトピック（７５０）とに分裂してもよい。一方、ノード７３０は、２つのトピック、すなわち爆破の説明及び死傷者に関するトピック（ノード７６０）と、爆破現場における救助チームの働きに関するトピック（７７０）とに分裂していてもよい。例示的な階層７００では、上位レベルのノードを用いて、ｐ（ν｜α）及びｐ（ｊ｜ν）により、所与のトピックを記載した。したがって、コレクションの全文書において頻繁に現れる単語、例えば「オクラホマ」は、これらを階層７００における多くのトピック／クラスタに割当てることにより最適に説明される。
【００７２】
なお、１実施形態においては、階層７００の各クラスタ／ノードに関連するトピックの「タイトル（名称）」をユーザが提供することもできる。例えば、ユーザに、各クラスタ／ノードに関するＮ個の最も確率の高い単語を与えることができる。ユーザはこれらの単語からあるトピックに関連するクラスタ／ノードに対する「タイトル」を推定することができる。あるいは、各クラスタ／ノードに対する「タイトル」をプロセッサ１０２が自動的に決めることもできる。この構成では、プロセッサ１０２は、特定のクラスタ／ノードに関連付けられた文書から最頻のｎグラムを抽出し、抽出したｎグラムに基づいて、そのクラスタ／ノードに対する「タイトル」を決定することができる。
【００７３】
本発明に関する特定原理による１構成においては、コンピュータ１００を、本発明の１実施形態により誘導されたトピック階層の妥当性を評価すべく構成してもよい。この構成においては、プロセッサ１０２は、テスト文書コレクションに基づく誘導階層に含まれるクラスタを、予めこのテストコレクションに割当てられたマニュアルラベルの集合と比較することを可能にする命令またはプログラムコードを実行できる。この評価を行うため、プロセッサ１０２は、誘導階層に含まれるラベル及びクラスタに関するＧｉｎｉ（ジニ）関数の平均を使用することができ、ジニ関数は次式のように定められる。
【００７４】
【数３２】
0004384398.tif 000033
及び
【数３３】
0004384398.tif 000034
上記のＧｉｎｉ関数において、Ｌは異なるラベルの数を表し、Λは異なるクラスタの数を表す。さらに、Ｇｌはラベルｌに関する、求められたクラスタαの純度を測定し、Ｇαに対しては相互的である。Ｇｉｎｉ関数Ｇｌ及びＧαの値が小さいほど、よい結果を表すが、これはクラスタとラベルがより密接に対応しているためである。すなわち、データクラスタとラベルクラスタが同じ重みの同じ文書を含む場合には、Ｇｉｎｉ指数は０である。Ｇｉｎｉ関数Ｇｌ及びＧαはそれぞれが、上限値１を有する。
【００７５】
したがって、コンピュータシステム１００が、本発明に関する特定原理による階層的ソフトクラスタリング動作の有効性を評価しようとする際には、テスト文書コレクションにアクセスし、図６に示される処理をこのコレクションに関して行い、トピック階層を生成することができる。クラスタに関するＧｉｎｉ関数の実施結果は、Ｇｉｎｉ指数の形で提供することができる。プロセッサ１０２は、Ｇｉｎｉ関数の結果を分析して、本発明の特性によるクラスタリング処理が適正なトピック結果を生み出しているかを決定するよう構成することができる。
【００７６】
本発明に関する特定原理による１構成においては、図６に示された処理に関するＧｉｎｉ指数を、他のクラスタリング処理、例えばＨＭＬＭや、分離混合モデル（ＳＭＭ；Separable Mixture Model）など、文書を誘導階層のリーフにのみ割当てる平坦なクラスタリングモデルに関するＧｉｎｉ指数と比較することができる。例えば、表１は、本発明の特性による階層的ソフトクラスタリング処理、ＨＭＬＭに基づくクラスタリング処理、及びＳＭＭクラスタリング処理を使用してプロセッサ１０２によりクラスタリングされたテスト文書コレクションに関する例示的なＧｉｎｉ指数テーブルを示すものである。表１に示されるように、本発明の特性による階層的ソフトクラスタリング処理に関するＧｉｎｉ指数は、他の２つのモデル（ＨＭＬＭ及びラベル）に関するＧｉｎｉ指数より小さい。このような結果は、コンピュータシステム１００に、他のクラスタリング処理に比べ、本発明に関する特定原理によるクラスタリング処理を実行して生成されたトピッククラスタがより効率的であることを示すことができる。
【００７７】
【表１】
0004384398.tif 000035
以上のように、本発明によれば、コンピュータシステムは、文書及び単語のコレクションからトピッククラスタを生成し、各クラスタを別のクラスタに割当てられた文書にも関連付づけることができる。しがって、誘導クラスタ階層における対象のハード割当てを回避することができる。
【００７８】
本発明は、上記の実施及び構成例に限定されるものではない。例えば、本発明により、ある文書コレクションに関連するトピッククラスタの階層を、このコレクションに追加される単数または複数の新しい文書に基づき更新することができる。この構成においては、コンピュータ１００は、１つ以上の新しい文書の追加時に文書コレクションを更新し、この修正されたコレクションに関して本発明に関する特定原理によるクラスタリング動作を実行することができる。したがって、本発明の実施により、新しい１文書（または文書の集合）が文書コレクションに追加されるたびごとに、その文書コレクションに関するトピック階層を修正することができる。
【００７９】
さらに、本発明を使用して、ある文書コレクションに関してそのユーザが実行する行動（例えば、書込み、プリント、ブラウジング）に基づきユーザをクラスタリングすることもできる。この構成では、対象「ｉ」がユーザを表し、対象「ｊ」が文書を表す。さらに、本発明を使用し、画像を、その画像に関連づけられたテキストに基づきクラスタリングすることもできる。例えば、関連付けられたテキストは画像のタイトルであってもよいし、例えばウェブページのように画像の周囲のテキストであってもよい。この構成では、対象「ｉ」は画像を表し、対象「ｊ」は各画像のタイトルに含まれる単語を表す。さらに、本発明を使用し、企業の活動領域または消費者関係に基づき企業をクラスタリングすることもできる。例えば、後者の例の場合、「ｉ」は企業を表し、「ｊ」は企業と消費者との関係（例えば、「販売（sells to）」）を表す。すなわち、１つ以上の企業には、それらの企業から異なるタイプの製品及び／またはサービスを購入した消費者の集合を有することができる。したがって、本発明の特定の態様によれば、階層のクラスタにより、これらの企業から類似するタイプの製品及び／またはサービスを購入した（例えば、ハードウェアの購入、コンピュータソフトウェアの購入、ルータ部品の購入など）消費者のグループを表すことができる。よって、この構成においては、「ｉ」が消費者を表すことができ、「ｊ」によって企業を表してもよい。あるいは、別の構成に、特定のタイプの企業から種々のタイプの製品及び／またはサービスを購入した消費者の集合を含んでもよい。この構成では、階層のクラスタが、製品及び／またはサービスのタイプ（ハードウェアの販売、コンピュータソフトウェアの販売、紙製品の販売など）のグループを表すことができる。この構成においては、「ｉ」により企業を表し、「ｊ」により消費者を表すことができる。このように、当業者であれば、本発明を任意のタイプの共起する対象のクラスタリングに適用できることが理解できるであろう。
【図面の簡単な説明】
【図１】  コンピュータ装置環境の例を示す図であり、これにより本発明の特定原理による製造の方法、装置及び製品を実施することができる。
【図２】  第１の階層的クラスタリングモデルの作用（behavior）を表す例示的なブロック図である。
【図３】  第２の階層的クラスタリングモデルに関連するモデルを表す例示的なブロック図である。
【図４】  第３の階層的クラスタリングモデルを表す例示的なブロック図である。
【図５】  本発明に関する特定の特性及び原理による、階層的クラスタリングモデルに関連する例示的なブロック図である。
【図６】  本発明に関する特定の特性及び原理による製造の方法、装置及び製品により実施可能な例示的な処理を表すフローチャートである。
【図７】  本発明に関する特定の特性による製造の方法、装置、及び製品により製造できる、文書コレクションに関連する例示的なトピック階層を示す図である。
【符号の説明】
１００  コンピュータ装置、１０２  プロセッサ、１０４  メインメモリ、１０６  補助メモリ、１０８  バス、１１０  キーボード、１１２  ディスプレイ、１１４  ネットワークコネクタ、１１６  大容量記憶装置。
【図１】
0004384398.tif 000036
【図２】
0004384398.tif 000037
【図３】
0004384398.tif 000038
【図４】
0004384398.tif 000039
【図５】
0004384398.tif 000040
【図６】
0004384398.tif 000041
【図７】
0004384398.tif 000042