(57)【要約】本発明は、コンピュータシステムにおけるデータ管理の分野に関する。本発明は、データを自動的に整理し、当該データをコンピュータにおけるデータ構造に整える新たな方法を提案する。本発明は距離を、データセット間の類似度の尺度として使用する。データセットは、距離が距離値の密度におけるピークと関連づけられる限界値を上回るか下回るかに応じてクラスタ構造に割り当てられる。
2004503849.tif 000002
【特許請求の範囲】
【請求項１】
複数セットの電子データをデータ処理装置により自動的に整理する方法であって、該データ処理装置が行う以下のステップ、
少なくとも選択されたデータセットのグループについて任意の２つのデータセット間の距離Ｄを求めるステップであって、該距離は数値を与える２つのデータセットのペアの関数として定められ、該関数は同一データセットのペアの場合に定められる第１の値Ｄ０を有し、該値Ｄ０と任意のペアの距離Ｄの差が全てのペアについてゼロ以上、すなわちＤ−Ｄ０≧０であるか、あるいは全てのペアについてゼロ以下、すなわちＤ−Ｄ０≦０であると定められる、該距離Ｄを求めるステップと、
求めた距離値の範囲にわたって距離値の密度を求めるステップと、
１つまたは複数の限界値を求めるステップであって、前記差が全てのペアについてＤ−Ｄ０≧０であると定められた場合に、該限界値の少なくともいくつかは前記距離値の密度のピークの上限をそれぞれ定め、前記差が全てのペアについてＤ−Ｄ０≦０であると定められた場合に、該限界値の少なくともいくつかはピークの下限をそれぞれ定め、該限界値は複数の場合に増加列となる、該限界値を求めるステップと、
各データセットをクラスタの階層における１つのクラスタに関連づける相関データを作成するステップであって、該階層中のクラスタレベルの数が限界値の数に相当する、該相関データを作成するステップとを含み、
前記差が全てのペアについてＤ−Ｄ０≧０であると定められた場合に、
前記階層における第１レベルの各クラスタに含まれるデータセットが、各データセットについて該クラスタ中の他のデータセットに対する最小ペア間距離が最低限界値未満であるという点で互いに関係しており、
前記階層における各上位クラスタが、下位レベルの１つまたは複数のクラスタからなるグループのデータセットを含み、該グループが２つ以上のクラスタを含む場合、該グループの各クラスタは該グループにおける別のクラスタとペアを形成し、該ペアには、該ペアの一方のクラスタの少なくとも１つのデータセットであって、該ペアの他方のクラスタのデータセットからの距離が、前記限界値の増加列において、次に下位のレベルのクラスタを画定する限界値の次に高い限界値未満であるデータセットがあり、
前記差が全てのペアについてＤ−Ｄ０≦０であると定められた場合に、
前記階層における第１レベルの各クラスタに含まれるデータセットは、各データセットについて該クラスタ中の他のデータセットに対する最大ペア間距離が最高限界値よりも大きいという点で互いに関係しており、
前記階層における各上位クラスタが、下位レベルの１つまたは複数のクラスタからなるグループのデータセットを含み、該グループが２つ以上のクラスタを含む場合、該グループの各クラスタは該グループにおける別のクラスタとペアを形成し、該ペアには、該ペアの一方のクラスタの少なくとも１つのデータセットであって、該ペアの他方のクラスタのデータセットからの距離が、前記限界値の増加列において、次に下位のレベルのクラスタを画定する限界値の次に低い限界値よりも大きいデータセットがある
方法。
【請求項２】
各データセットをクラスタの階層における１つのクラスタに関連づける相関データを作成する前記ステップであって、該階層中のクラスタレベルの数が限界値の数に相当する、該相関データを作成するステップを含むことを特徴とし、
前記差が全てのペアについてＤ−Ｄ０≧０であると定められた場合に、
前記階層における第１レベルの各クラスタが少なくとも１つのデータセットを含み、該データセットに対して該クラスタの他の全てのデータセットは最低限界値未満の距離にあり、
前記階層における第２レベルの各クラスタが少なくとも１つのデータセットを含み、該データセットに対して該クラスタの他の全てのデータセットは２番目に最も低い限界値未満の距離にあり、
前記階層における各上位クラスタが少なくとも１つのデータセットを含み、該データセットに対して該クラスタの他の全てのデータセットは、前記限界値の増加列において、次に下位のレベルのクラスタを画定する限界値の次に高い限界値未満の距離にあり、
前記差が全てのペアについてＤ−Ｄ０≦０である場合に、
前記階層における第１レベルの各クラスタが少なくとも１つのデータセットを含み、該データセットに対して該クラスタの他の全てのデータセットは最高限界値よりも大きい距離にあり、
前記階層における第２レベルの各クラスタが少なくとも１つのデータセットを含み、該データセットに対して該クラスタの他の全てのデータセットは２番目に最も高い限界値よりも大きい距離にあり、
前記階層における各上位クラスタが少なくとも１つのデータセットを含み、該データセットに対して該クラスタの他の全てのデータセットは、前記限界値の増加列において、次に下位のレベルのクラスタを画定する限界値の次に低い限界値よりも大きい距離にある
請求項１に記載の方法。
【請求項３】
データセットをクラスタに関連づける前記相関データは、
各データセットを第１レベルの１つまたは複数のクラスタに関連づけるデータと、
最上位レベルよりも下位のレベルにおける各クラスタを上位レベルの１つのクラスタまたは複数のクラスタに関連づけるデータと
を含むことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記相関データに基づいて表示装置を制御するステップであって、それによって１つまたは複数のレベルのクラスタを記号によりグラフィック表示する、該制御するステップを特徴とする請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
前記相関データに基づいてディレクトリ構造を作成するステップであって、各クラスタが１つのディレクトリに対応し、各クラスタレベルが１つのディレクトリレベルに対応する、該ディレクトリ構造を作成するステップを特徴とする請求項１ないし４のいずれか一項に記載の方法。
【請求項６】
前記データセットおよび前記相関データからデータベースを作成するステップであって、該データベースのデータモデルが前記クラスタの階層によって定義される、該データベースを作成するステップを特徴とする請求項１ないし５のいずれか一項に記載の方法。
【請求項７】
前記データベースは、リレーショナルデータベースであることを特徴とし、キーがクラスタ名によって定められ、値が親クラスタの名前によって定められる請求項６に記載の方法。
【請求項８】
前記データベースは、オブジェクト指向データベースであることを特徴とし、キーがクラスタ名によって定められ、値が親ディレクトリの名前によって定められる請求項６に記載の方法。
【請求項９】
１つまたは複数の所定のデータ要素を含むデータセットのグループが選択され、前記限界値は該選択されたデータセットのグループに基づき求められることを特徴とする請求項１ないし８のいずれか一項に記載の方法。
【請求項１０】
前記距離値の全範囲が、一連の距離間隔に完全に分割され、前記距離値の密度は、各距離間隔における距離値の数または正規化数として求められることを特徴とする請求項１ないし９のいずれか一項に記載の方法。
【請求項１１】
間隔サイズが増加する前記距離の全範囲の複数の区画が確定され、前記密度は該区画のぞれぞれについて確定され、各区画について予備の限界値が求られ、該予備の限界値を平均することまたは当てはめることによって最適化された限界値が得られることを特徴とし、前記相関データは該最適化された限界値に基づき確定される請求項１０に記載の方法。
【請求項１２】
距離密度値の分布が前記区画から確定され、前記限界値は該分布から求められることを特徴とする請求項１０または１１に記載の方法。
【請求項１３】
１つまたは複数の限界値が、前記密度の最大値に隣接する密度の最小値またはゼロの点として求められることを特徴とする請求項１ないし１２に記載の方法。
【請求項１４】
密度値に曲線が当てはめられ、１つまたは複数の限界値が該曲線の最大値に隣接する最小値またはゼロの点として求められることを特徴とする請求項１ないし１３のいずれか一項に記載の方法。
【請求項１５】
前記曲線は、密度値の分布に当てはめられることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記曲線は、多項式または三角関数または複数の三角関数からなる関数であることを特徴とする請求項１４または１５のいずれか一項に記載の方法。
【請求項１７】
前記データセットはテキストデータを含み、前記距離は２つのデータセットに共通する単語の数の関数であることを特徴とする請求項１ないし１６のいずれか一項に記載の方法。
【請求項１８】
前記データセットは遺伝情報を含み、前記距離は該データセット中の２つの部分配列において引き続いて生じる同一データ要素の数の関数であることを特徴とする請求項１ないし１６のいずれか一項に記載の方法。
【請求項１９】
前記相関データを作成するステップは、
全てのデータセットについて距離行列を確定することと、
Ｄ≧Ｄ０である場合に最低限界値未満の値、Ｄ≦Ｄ０である場合に最高限界値よりも大きい値を有する行列要素によってリンクされたデータセットを第１レベルのクラスタに割り当てることと
を含むことを特徴とする請求項１ないし１８のいずれか一項に記載の方法。
【請求項２０】
前記データセットを、辺によって他のあらゆる頂点と接続された頂点としてグラフィカルに表示し、各辺の長さが２つのデータセット間の距離に相当し、最低限界値に相当する長さよりも短い長さを持つ辺は削除され、連続する残りのサブグラフによって表されるデータセットが最下位レベルの同じクラスタに割り当てられることを特徴とする請求項１ないし１９のいずれか一項に記載の方法。
【請求項２１】
請求項１ないし２０のいずれか一項に記載の方法によって得られるデータベース。
【請求項２２】
請求項１または請求項１に従属する請求項のいずれかに記載の方法のステップをすべて行うように適合されたコンピュータプログラム。
【請求項２３】
コンピュータ読み取り可能な媒体において具現される請求項２２に記載のコンピュータプログラム。
【請求項２４】
複数セットの電子データを類似度に応じて自動的に整理する装置であって、請求項１ないし２０のいずれか一項に記載の方法のステップを行うデータ処理手段を備える装置。
【請求項２５】
表示装置を備え、前記データ処理手段は請求項４に記載の方法に従って該表示装置を制御することを特徴とする請求項２４に記載の装置。
【請求項２６】
前記データセットをディレクトリ構造に格納するデータ記憶手段を備え、該ディレクトリ構造は請求項５に記載の方法に従って得られることを特徴とする請求項２４または２５のいずれか一項に記載の装置。
【請求項２７】
データセットを検索し、かつ／または整理する装置を操作する方法であって、請求項１ないし２０のいずれか一項に従って得られる相関データを含むか、該相関データを得ることが可能であり、以下のステップ、
データ要素を入力するステップと、
前記これらのデータ要素を含むデータセットを選択するステップと、
前記選択されたデータセットの、前記相関データによって確定される階層における最下位レベルのクラスタを選択するステップとを特徴とし、
前記装置は、前記選択されたクラスタの要素に関連するデータを出力する方法。
【請求項２８】
前記選択されたクラスタの要素に関連するデータを出力した前記装置は、該選択されたクラスタを含む次に上位のクラスタの要素に関連する、該選択されたクラスタには含まれないデータを出力することを特徴とする請求項２７に記載の方法。
【請求項２９】
前記装置は続いて、ユーザが関連する入力を行った時にのみ、少なくとも１つの上位クラスタの要素に関連するデータを出力することを特徴とする請求項２７または２８のいずれか一項に記載の方法。
【発明の詳細な説明】
【０００１】
本発明は、包括的にはデータ記憶の分野に関し、特にコンピュータ資源を効率的に利用するようなコンピュータシステムにおけるデータ管理に関する。本発明は特に、データベースの分野において、特にコンピュータがデータベースにおいて検索動作を行う方法に関して適用される。
【０００２】
データベースに関連する一般的な問題は、検索クエリ（ｓｅａｒｃｈ ｑｕｅｒｙ）に関連する全ての項目を可能な限り最小の手間と可能な限り最短の時間で見つけ出すことである。一般的な手法は、１つまたは複数のキーワードを入力し、これらのキーワードを含む全てのレコードについてデータベースを検索することである。多数のレコードを検索する場合、これはしばしば、返ってくる応答の数が大きすぎて妥当な労力とコンピュータ使用時間（ｃｏｍｐｕｔｅｒ ｔｉｍｅ）を費やしても関連するレコードを検討することができないか、あるいは返ってくる応答の数は処理可能であっても、クエリが非常に制限されるため関連するレコードがすべて見つけ出されたのかどうかは不確かであるという代償を払わねばならないことを意味する。
【０００３】
この問題を改善するため、多くのデータベースは特定のデータ構造を有し、データはグループ単位で「クラスタリング」され、各グループは特定の主題に関連するレコードを含む。一例としてはインターネット上の検索機構があり、様々なリンクが割り当てられた複数の検索カテゴリ（ビジネス、スポーツなど）およびサブカテゴリ（たとえばサッカー、テニスなど）を提供する。かかるクラスタリング方法の別の例には、国際特許分類（ＩＰＣ）に従ったデータベースにおける特許文書のクラスタリングがあり、全ての特許および特許出願が１つまたは複数のクラスに割り当てられている。この手法に関連する問題は、各レコードまたは文書を１つまたは複数のクラスまたはクラスタに割り当てねばならないことである。この割り当てを人間が行う場合には多大の手間がかかる。引き続き分類すべき文書の例に関して言えば、多くの場合に、あらゆる文書を詳細に検討し、それが関連し得る全ての可能なクラスを考え出すことは事実上不可能である。要約あるいは題名のみを基にざっと検討することしかできないことは多い。これは、特定の主題に関連する部分が一見したところでは明白でない文書、たとえば大量のテキスト中にわずかだが非常に関連性の高いテキスト部分がある文書が往々にして、関連するグループに分類されず、一見しては問題とされる主題にほとんどまたは全く関係のないクラスタまたはグループにしか分類されないことを意味する。
【０００４】
従来のクラスタリング構造に関連するさらなる問題は、柔軟性がないことである。大抵の場合に、クラスタリング構造は事前に構成され、通常のコンピュータ操作過程では変更することができない。これは時としてクラスタリング構造が特定のクエリ、たとえば異なる技術分野に関連する特許の処理に実際には適していないという結果を招く。
【０００５】
本発明に関連する別の問題は、類似した部分シーケンスがあるかどうかデータシーケンスを解析することである。この問題が大いに関係する一分野に、遺伝子配列に関連するデータの解析がある。
【０００６】
本発明の目的は、電子データセットをコンピュータにより自動的に整理して、関連するデータセットを、確定した順序によってより容易に見出すことができるようにする方法を提供することである。
【０００７】
さらなる目的は、関連する装置および関連するコンピュータプログラムを提供することである。上記方法の結果、本発明はまた、この方法の結果に従って構成されるデータベースも提供する。最後に、本発明の目的は、静的分類（ｓｔａｔｉｃ ｃｌａｓｓｉｆｉｃａｔｉｏｎ）の欠点を克服することである。
【０００８】
上記目的は、複数セットの電子データを類似度に応じてデータ処理装置により自動的に整理する（ｏｒｄｅｒｉｎｇ）方法によって達成される。本方法は、上記データ処理装置が行う以下のステップ、
少なくとも選択されたデータセットのグループについて任意の２つのデータセット間の距離Ｄを求めるステップであって、当該距離は数値を与える２つのデータセットのペアの関数として定められ、当該関数は同一データセットのペアの場合に定められる第１の値Ｄ０を有し、当該値Ｄ０と任意のペアの距離Ｄの差が全てのペアについてゼロ以上、すなわちＤ−Ｄ０≧０であるか、あるいは全てのペアについてゼロ以下、すなわちＤ−Ｄ０≦０であると定められる、当該距離Ｄを求めるステップと、
求めた距離値の範囲にわたって距離値の密度を求めるステップと、
１つまたは複数の限界値を求めるステップであって、上記差が全てのペアについてＤ−Ｄ０≧０であると定められた場合に、当該限界値の少なくともいくつか、好ましくは全てまたは１つを除く全ては上記距離値の密度のピークの上限を定め、上記差がＤ−Ｄ０≦０であると定められた場合に、当該限界値の少なくともいくつか、好ましくは全てまたは１つを除く全てはピークの下限を定め、当該限界値は複数の場合に増加列となる、当該限界値を求めるステップと、
各データセットをクラスタの階層における１つまたは複数のクラスタに関連づける相関データを作成するステップであって、当該階層中のクラスタレベルの数が限界値の数に相当する、当該相関データを作成するステップとを含み、
上記差が全てのペアについてＤ−Ｄ０≧０であると定められた場合に、
上記階層における第１レベルの各クラスタが、各データセットについて他のデータセットに対する最小ペア間距離が最低限界値未満であるという点で互いに関係したデータセットを含み、
上記階層における各上位クラスタが、下位レベルの１つまたは複数のクラスタからなるグループのデータセットを含み、当該グループが２つ以上のクラスタを含む場合、当該グループの各クラスタは当該グループにおける別のクラスタとペアを形成し、当該ペアには、当該ペアの一方のクラスタの少なくとも１つのデータセットであって、当該ペアの他方のクラスタのデータセットからの距離が、上記限界値の増加列において次に下位のレベルのクラスタを画定する限界値の次に高い限界値未満であるデータセットがあり、
上記差が全てのペアについてＤ−Ｄ０≦０であると定められた場合に、
上記階層における第１レベルの各クラスタが、各データセットについて他のデータセットに対する最小ペア間距離が最高限界値よりも大きいという点で互いに関係したデータセットを含み、
上記階層における各上位クラスタが、下位レベルの１つまたは複数のクラスタからなるグループのデータセットを含み、当該グループが２つ以上のクラスタを含む場合、当該グループの各クラスタは当該グループにおける別のクラスタとペアを形成し、当該ペアには、当該ペアの一方のクラスタの少なくとも１つのデータセットであって、当該ペアの他方のクラスタのデータセットからの距離が、上記限界値の増加列において次に下位のレベルのクラスタを画定する限界値の次に低い限界値よりも大きいデータセットがある。
【０００９】
本発明は、相関データを作成する上記ステップが、以下の規則のうちの１つまたは複数に従って行われることを規定し得る。
上記差が全てのペアについてＤ−Ｄ０≧０であると定められた場合に、
上記階層における第１レベルの各クラスタが少なくとも１つのデータセットを含み、当該データセットに対して当該クラスタの他の全てのデータセットは最低限界値未満の距離にあり、
上記階層における第２レベルの各クラスタが少なくとも１つのデータセットを含み、当該データセットに対して当該クラスタの他の全てのデータセットは２番目に最も低い限界値未満の距離にあり、
上記階層における各上位クラスタが少なくとも１つのデータセットを含み、当該データセットに対して当該クラスタの他の全てのデータセットは、上記限界値の増加列において次に下位のレベルのクラスタを画定する限界値の次に高い限界値未満の距離にあり、
上記差が全てのペアについてＤ−Ｄ０≦０であると定められた場合に、
上記階層における第１レベルの各クラスタが少なくとも１つのデータセットを含み、当該データセットに対して当該クラスタの他の全てのデータセットは最高限界値よりも大きい距離にあり、
上記階層における第２レベルの各クラスタが少なくとも１つのデータセットを含み、当該データセットに対して当該クラスタの他の全てのデータセットは２番目に最も高い限界値よりも大きい距離にあり、
上記階層における各上位クラスタが少なくとも１つのデータセットを含み、当該データセットに対して当該クラスタの他の全てのデータセットは、上記限界値の増加列において次に下位のレベルのクラスタを画定する限界値の次に低い限界値よりも大きい距離にある。
【００１０】
データセットをクラスタに割り当てる上記の基準は、２つ、３つまたはそれ以上のクラスタレベルがあることを必ずしも意味せず、単に、かかるレベルが存在する場合の割り当て基準を定めるに過ぎないことが留意されるべきである。クラスタは単一の要素からなっていてもよいことも留意されるべきである。これは、このデータセットに対する距離が関連する限界値を上回るか、あるいは下回る他のデータセットがない場合にそれぞれ当てはまる。別途に記載のない限り、以下で、距離は正であるものと仮定する。
【００１１】
第１レベルのクラスタのデータセットに関する最小ペア間距離の上記の基準（正の距離の場合はＤ≧Ｄ０）のみで多くの場合、たとえば緩和時間を基に代謝機能を求める場合に妥当な結果が得られるが、クラスタが、絶対値に換算して関連する閾値よりも大きい距離にあるデータセットを含むことを可能にする。いくつかの実施形態に関して、本発明は、クラスタ中の各データセットについて、他のデータセットに対する距離のグローバル関数または集約関数の値が各々の限界値未満、または場合に応じて、この限界値に適用された上記関数の値未満である（あるいはそれよりも高い）という点でより厳しい基準を提供することができる。かかる集約関数は特に、データセットの、クラスタ中の他の全てのデータセットに対する平均ペア間距離を含み、この平均距離は、算術平均距離、相乗平均距離、または別の方法で定めた平均距離であり得る。かかる集約関数のさらなる例に、データセットの、他の全てのデータセットに対する中間値距離、すなわち距離値の下側５０％を残りの５０％と分離する距離があり、この残りの５０％はこの値よりも上にある。ある割合、たとえば４０％または６０％の距離値が下にある距離値を各々の関数の値として選択することにより、この概念を一般化することも考えられる。さらに別の考え得る集約関数はモーダル距離、すなわち最も頻繁に現れる距離、あるいはより一般化すれば、距離値のほとんどを含む所定の長さの間隔における距離の平均である。
【００１２】
たとえば、ペア間距離の絶対値の最大値を選択基準として選択した場合、本発明は、各クラスタが、互いからの距離が常に、Ｄ−Ｄ０≧０である場合に各々の限界値未満であり、Ｄ−Ｄ０≦０である場合に各々の限界値よりも大きいデータセットからなることを規定する。したがって、データセットの任意のペアについて、このペアのデータセット間の距離はそれぞれ、各々の限界値よりも大きくないか、あるいは小さくない。この割り当てにより、同じデータセットが第１レベルの異なるクラスタに属することになり得る。たとえば、データセットＢおよびＣがそれぞれデータセットＡから、（距離が正として定められるとみなして）各々の限界値未満の距離にある場合、このことは、ＢおよびＣが互いから各々の限界値未満の距離にあることを必ずしも意味しない。これが当てはまらない場合、第１レベルにはデータセットＡを含むクラスタが２つ、すなわちペア（Ａ、Ｂ）を含む第１のクラスタと、ペア（Ａ、Ｃ）を含む第２のクラスタとが存在し得る。
【００１３】
さらに別のクラスタリング方法は、各クラスタが、１つまたは複数の選択された基準データセットに関して各々の限界値未満の（または限界値よりも大きい）距離にあるデータセットからなることを規定し得る。これらの基準データセットは、ランダムに選択されるか、あるいはユーザによって決定され得る。後者の例は特に、ユーザが特に関連性が高いと考えるレコードを既に見出しており、次に類似するデータレコードを見つけたい場合に有用である。この場合、ユーザは、このレコードを基準データセットとして指定し、本発明による方法をコンピュータに行わせ、この基準データセットを含む１つまたは複数の、好ましくは全てのクラスタを、クラスタの要素が持つこの基準データセットからの距離により定めた階層を返させることになる。
【００１４】
２つの最後に述べたクラスタリング基準について、第１レベルの各クラスタは互いから、または１つまたは複数の基準データセットからの距離が、同一データセットのペアの距離との差の絶対値、すなわち｜Ｄ−Ｄ０｜が所定の最下限未満であるような距離になっている全てのデータセットからなる。これは、最も類似したデータセットが最下位レベルの１クラスタに統合されることを意味する。クラスタが１つまたは複数の基準データセットによって確定される場合、クラスタは、一致に最も近い、よって上記基準データセットに最も類似した全てのデータセットを含む。上記クラスタの全てのデータセットの互いからの距離が各々の限界値未満である（または限界値よりも大きい）ことが要求される場合、第１レベルの各クラスタは、グループとして考えられる互いに最も類似したデータセットを含む。たとえば、データセットが文書である場合、文書は異なる分野に関連し、よって第１の分野の文書ならびに第２の分野の文書に関して各々の限界値未満の距離にあり得る。この場合、本発明の方法は、この文書を含む第１レベルのクラスタを２つ返すことになり、これら２つのクラスタの各々は、特定の技術分野に関連するとみなされ得る。これは、静的分類の問題のいくつかを克服するものである。
【００１５】
上位レベルのクラスタリング基準に関して、本発明は、第１レベルのクラスタの場合と同じクラスタリング基準が適用されること、特に上記上位レベルのクラスタに含まれる任意のデータセットについて、ペア間距離の最小絶対値またはこのデータセットの他のデータセットに対する距離の集約関数（距離の最大絶対値、平均距離など）は、このレベルの各々の限界値未満である（またはそれぞれ限界値よりも高い）ことを規定し得る。
【００１６】
たとえば、上位クラスタは、下位レベルの２つのクラスタの全ての要素を、互いから、あるいは与えられるかランダムに選択され得る基準データセットからの距離が各々の限界値未満である（またはＤ−Ｄ０≦０の場合に限界値よりも大きい）データセットを含む上記上位クラスタに割り当てることによって画定され得る。別の可能性は、各上位クラスタを、互いから、あるいは１つまたは複数の基準データセットからの距離が各々の限界値未満である（またはそれぞれ限界値よりも大きい）全てのデータセットをこのクラスタに割り当てることによって画定することである。
【００１７】
しかしながら本発明は、関連する基準として、要素が上位レベルのクラスタに含まれる、下位レベルのクラスタの距離が各々の限界値未満である（または限界値よりも大きい）ことも規定し得る。クラスタの距離は、任意の好適な方法で、たとえば比較する２つのクラスタからとった２つのデータセットの最小距離として、あるいは上述したように、第１レベルについて上述したクラスタリング方法と同様、２つのクラスタからとったデータセットのペアの最大距離、かかるペアの平均距離、または別の集約関数として定めることができる。同様に、第１レベルのクラスタリング方法について述べたことと同様、基準クラスタを選び出して、上位レベルのクラスタの要素のうち、基準クラスタに関して各々の限界値未満の（または限界値よりも大きい）距離にあるものを当該クラスタの要素として決定してもよい。この手法を用いると、下位レベルの単一のデータセットは、１つの要素からなるクラスタとして扱われる。さらなる代案として、本発明の方法は、クラスタ全体の割り当てによる上位レベルのクラスタへのデータセットの割り当てについて、下位レベルのクラスタを、その目的で作成した、成員（ｍｅｍｂｅｒ）の集合体からの情報を組み込んだ単一のサロゲート（ｓｕｒｒｏｇａｔｅ）データセットとして表すことを規定し得る。したがって、たとえばデータセットが文書に相当する場合に、クラスタ毎に単一のサロゲート文書を、クラスタ中の全ての文書のテキストを連結すること、クラスタ中の全ての文書中の固有の用語をリストにすること、それらの文書中の用語のうち、それらの文書をそのクラスタにない文書から最もよく区別する用語をリストにすることなどによって作成することができる。
【００１８】
本発明は、異なるクラスタレベルには異なるクラスタリング基準を適用することを規定し得るが、好ましい実施形態において、最下位レベルよりも上位のレベルでは基準は全てのクラスタレベルについて同一である。平均、中間値またはモーダル距離を示す場合、クラスタリングの結果はクラスタリングする項目を検討する順序に影響されやすい場合がある。別の項目を検討する前に所定の項目を追加すると、その項目は除外されるか、あるいは包含されるが、２つの項目を検討する順序を入れ替えると、逆の決定および異なるクラスタという結果がもたらされる。この順序に対する感受性は、サブサンプリング、特にブートストラップ・サンプリングのようなリサンプリング方法を適用することによって回避することができる。項目のランダムな選択を省いてプロセスを繰り返すことによってクラスタ構造の安定性を解析することもできる。別の手法としてモンテカルロ法もあり、この手法では、ランダムな順序が試験され、一定の限界、たとえば４０％よりも大きい発生可能性を持つクラスタまたはクラスタ構造が選択される。
【００１９】
通常、最上位レベルを除く各レベルは、距離密度におけるピークに相当する。階層は、検討するデータセット全体と一致する最上位レベルにはクラスタを１つだけ含むように定義され得る。この場合、最高限界値（正の距離の場合）は、無限大または任意の２つのデータセット間の最大距離よりも大きい数である。当然ながら、最上位レベルに２つ以上のクラスタがあるように階層を定義することもでき、これは、クラスタを上位レベルの２つ以上のクラスタにリンクすることが許可される場合に賢明であり得る。
【００２０】
本発明の方法に従って確定される階層は、大きな階層のサブ階層であってもよい、すなわち、一定の階層レベルより上のレベルは異なる基準によって判定される。同様に、たとえば最高限界値の場合は、一定の限界値をピークの限界として求めなくともよい。先行する規則に従って決定されたクラスタ階層の２つのレベル間に付加的なサブレベルを追加することを検討することもできる。これらのサブレベルは、異なる基準に従って判定することができる。これは、本発明に従って決定したクラスタの下部構造として考えることもできる。しかしこの場合でも、上記のように、距離に基づいて決定されるクラスタレベルの階層は依然として存在する。
【００２１】
本発明は、相関データが、下位レベルの１つまたは複数のクラスタを上位レベルのクラスタに関連づけるデータを含むことを規定し得る。したがって、各データセットに個別に相関データを設ける代わりに、下位レベルのクラスタ全体を上位レベルのクラスタに関連づける集合的な相関データをポインタ等によって提供し、個々のデータセットの、前記下位レベルのクラスタへの割り付けは、そのクラスタの各々の相関データによって決定する。
【００２２】
代替的または付加的に、本発明は、相関データが、少なくとも１つのデータセットおよび／または１つのクラスタを次に上位のレベルよりも上位のレベルのクラスタに関連づけるデータを含むことを規定し得る。
【００２３】
本発明は、データセットをクラスタに関連づける上記相関データが、
各データセットを第１レベルのクラスタに関連づけるデータと、
最上位レベルよりも下位のレベルにおける各クラスタを上位レベルの１つのクラスタまたは複数のクラスタに関連づけるデータと
を含むことを規定し得る。
【００２４】
本発明はまた、データセットをクラスタに関連づける上記相関データが、
各データセットを任意レベルの１つまたは複数のクラスタに関連づけるデータと、
最上位レベルよりも下位のレベルにおける各クラスタを上位レベルの１つのクラスタまたは複数のクラスタに関連づけるデータと
を含むことを規定し得る。
【００２５】
本発明に従って作成される相関データは、様々な方法で用いられ得る。相関データは、データベースまたは処理装置におけるデータ構造の基礎を築くことができ、表示されるか、他の方法で出力装置に出力されるか、あるいは別のシステムに伝達され得る。
【００２６】
本発明による方法は、上記相関データに基づいて表示装置を制御するステップであって、１つまたは複数のレベルのクラスタを記号によりグラフィック表示する、当該制御するステップを含み得る。
【００２７】
この実施形態において、本発明による方法は、対話手段を介した入力により上記表示においてクラスタを選択し、当該対話手段を介した入力に応答して以下の：
１つまたは複数の下位レベルにおける選択されたクラスタの要素を表示するステップと、
上記選択されたクラスタを含む上位レベルのクラスタ、特に次に上位のレベルのクラスタの要素を表示するステップと
のうちの１つまたは複数を実行するステップを含み得る。
【００２８】
本方法はまた、上記相関データに基づいてディレクトリ構造を作成するステップであって、各クラスタが１つのディレクトリに対応し、各クラスタレベルが１つのディレクトリレベルに対応する、該ディレクトリ構造を作成するステップも含み得る。
【００２９】
この実施形態において、上記データセットは、最下位ディレクトリレベルのディレクトリのファイルとして格納されることが規定され得る。
【００３０】
本発明による方法は、上記データセットおよび上記相関データからデータベースを作成するステップであって、該データベースのデータモデルが上記クラスタの階層によって定められる、該データベースを作成するステップを含み得る。
【００３１】
本発明は、上記データベースがリレーショナルデータベースであり、ここでキーはクラスタ名によって定められ、値は親クラスタの名前によって定められることを規定し得る。
【００３２】
本発明はまた、上記データベースがオブジェクト指向データベースであり、ここでキーはクラスタ名によって定められ、値は親ディレクトリの名前によって定められることを規定し得る。
【００３３】
上記オブジェクト指向データベースでは、さらなる値をクラスタ内のサブクラスタに対応するクラスタ名のセットよって定めることができる。
【００３４】
クラスタ構造を全てのデータセットに基づいて確定する代わりに、本発明は、データセットのグループがランダムに選択され、上記限界値が当該選択されたデータセットのグループに基づいて求められることを規定し得る。
【００３５】
本発明は、１つまたは複数の所定のデータ要素を含むデータセットのグループが選択され、上記限界値は当該選択されたデータセットのグループに基づき求められることを規定し得る。
【００３６】
本発明の一実施形態によれば、上記距離値の全範囲が、一連の距離間隔に完全に分割され、上記距離値の密度は、各距離間隔における距離値の数または正規化数として求められ、当該正規化数は、単位距離間隔当りの距離値の数として定められる。
【００３７】
本発明は、間隔サイズが増加する上記距離の全範囲の複数の区画が確定され、上記密度は当該区画のぞれぞれについて確定されることを規定し得る。
【００３８】
本発明はさらに、各区画について予備の限界値が求られ、当該予備の限界値を平均することまたは当てはめることによって最適化された限界値が得られ、ここで上記相関データは当該最適化された限界値に基づき確定されることを規定し得る。
【００３９】
距離密度値の分布が上記区画から確定され、上記限界値は当該分布から求められることがさらに規定され得る。
【００４０】
本発明は、複数の距離値について距離密度の平均を出し、上記限界値が当該平均化された密度から求められることを規定し得る。
【００４１】
本方法は、１つまたは複数の限界値が、上記密度の最大値に隣接する密度の最小値またはゼロの点として求められることを規定し得る。
【００４２】
上記密度は、上記の平均密度であってもよい。
【００４３】
一実施形態によると、密度値に曲線が当てはめられ、１つまたは複数の限界値が当該曲線の最大値に隣接する最小値またはゼロの点として求められる。
【００４４】
特に、上記曲線は密度値の分布に当てはめられ得る。
【００４５】
密度値の分布が確定された場合、本発明は、上記曲線が、各密度値の標準偏差内にあるように当該分布に当てはめられることを規定し得る。
【００４６】
本発明の好ましい実施形態によれば、限界値の数、よってクラスタレベルの数は、密度、あるいは密度関数または密度分布に当てはめられる曲線のピークの数によって決まる。特定の実施形態によれば、クラスタレベルの数は、ピーク数またはピーク数に１を足した数に等しい。
【００４７】
しかしながら、本発明は、クラスタレベルの数は一定数を超えないということも規定し得る。上記関数のピークが所定の最大数未満のレベル数を与える場合、この数はレベル数として選択されるが、この数が所定の最大数を超える場合、この所定の最大レベル数を持つ階層が選択される。特に、本発明は、所定の最大ピーク数のみを与える曲線のみが密度関数または密度分布の当てはめに用いられること、あるいは、所定の最大数よりも大きいピーク数を与える当てはめは拒絶されることを規定し得る。
【００４８】
本発明は、上記曲線が、多項式または三角関数または複数の三角関数からなる関数であることを規定し得る。
【００４９】
本発明の一実施形態において、上記データセットはテキストデータを含み、上記距離は共通する単語の数の関数である。
【００５０】
本発明の一実施形態において、上記データセットは遺伝情報を含み、上記距離は、２つの配列または部分配列において特定の位置にあるデータ要素の関数である。この関数は特に、上記データセット中の２つの部分配列において引き続いて生じる同一データ要素の数に左右される。
【００５１】
本発明はまた、上述したような方法によって得られるデータベースを提供する。本発明はまた、このデータベースが具現され、特に格納されるコンピュータ読み取り可能媒体を提供する。
【００５２】
本発明はまた、上述したような方法のステップをすべて行うように適合されたコンピュータプログラム、特にコンピュータ読み取り可能な媒体において具現されるようなコンピュータプログラムを提供する。
【００５３】
本発明はまた、複数セットの電子データを類似度に応じて自動的に整理する装置であって、上述したような方法のステップを行うデータ処理手段を備える装置を提供する。
【００５４】
本装置は表示装置を備えることができ、上記データ処理手段は上記のそれぞれの方法に従って当該表示装置を制御する。
【００５５】
本発明はまた、上記データセットをディレクトリ構造に格納するデータ記憶手段を備え、当該ディレクトリ構造は上述したような方法に従って得られることを規定し得る。
【００５６】
本発明はまた、データセットを検索し、かつ／または整理し、上述したような方法に従って得られる相関データを含むか、当該相関データを得ることが可能である装置を操作する方法を提供する。本方法は、以下のステップ、
データ要素を入力するステップと、
上記データ要素を含むデータセットを選択するステップと、
上記階層における１つのレベル、特に最下位レベルのクラスタを選択するステップとを特徴とし、
上記装置は、上記選択されたクラスタの要素に関連するデータを出力する。
【００５７】
本発明は、上記選択されたクラスタの要素に関連するデータを出力した上記装置は、当該選択されたクラスタを含む次に上位のクラスタの要素に関連する、当該選択されたクラスタには含まれないデータを出力することを規定し得る。
【００５８】
この手順は、第１のクラスタの要素に関連するデータを出力した上記装置が、当該第１のクラスタを含む次に上位のクラスタの要素に関連する、当該第１のクラスタには含まれないデータを出力するという点で繰り返され得る。
【００５９】
上記選択された最下位レベルのクラスタは、当該クラスタに含める１つまたは複数のデータセットを指定することによって選択され得る。
【００６０】
本発明は特に、上記装置が上記データセットに関連するデータを、下位レベルのクラスタの要素に関連するデータが上位クラスタ（単数または複数）の要素に関連するデータよりも前に出力されるような順序で出力することを規定し得る。
【００６１】
一実施形態によると、クラスタの要素に関連するデータは、当該要素を形成するデータセットである。
【００６２】
本発明は、クラスタの要素に関連するデータが、当該要素を形成するデータセットのリストを形成することを規定し得る。
【００６３】
本発明はまた、上記装置が続いて、ユーザが関連する入力を行った時にのみ、少なくとも１つの上位クラスタの要素に関連するデータを出力することを規定し得る。
【００６４】
本発明の好ましい実施形態によると、限界値は、各限界値が距離密度の２つのピークを分離するように、あるいは、さらなるピークがない場合は、ピークに上限を与えるように選択される。しかしながら、限界値のいくつかが他の基準によって確定されるために１つまたは複数の隣接する限界値のペアはピークを挟まない実施形態を考慮することもできる。これは、はっきりとしたピーク構造がない場合に妥当であり得る。同様に、ピークがごく小さい場合には、限界値のペアに２つまたはそれ以上のピークを挟ませるのが適切であり得る。いずれの場合にも、通常は少なくとも１つまたは２つ、好ましくは３つないし５つの限界値のペアが１つまたは複数のピークを挟むことになるが、これも当然ながら、所望のクラスタレベル数によって決まる。
【００６５】
限界値は通常、実際の距離密度がピーク後に初めてゼロに近づく点、あるいはゼロがない場合に、はっきりとした最小値に近いか、これに等しいように選択することになる。しかしながら、特定のデータセットのペアを下位レベルのクラスタまたは上位レベルのクラスタに割り当てるには、この限界値を前後にシフトするのが妥当であり得る。これはたとえば、小さな極大値がより大きなピーク構造の最小値に重なっている場合に妥当であり得る。
【００６６】
本発明の状況において、データセットは、データ読み取り装置によってアクセスされ得る任意の明確なビットまたはバイトシーケンスであり得る。データセットは特に、直接アクセス可能なデータユニットまたはデータシーケンスにおける部分シーケンスであり得る。データセットはたとえば、ファイルまたはレコードであり得る。データセットは通常いくつかの要素を含み、これらの要素はビットまたはバイトシーケンス（データワード、またはテキストファイルでは文章の単語など）であり得る。データセットは可変長であり得るため、時として、データセットのなかには上記データ要素のうち１つしか含まないものも出てくる。
【００６７】
本発明による方法は、距離と呼ばれるデータ要素の関数に従ってデータセットを自動的に整理する。
【００６８】
「距離」という用語は主に数学的意味で理解される。すなわち距離とは、全てのデータセットのペアについて２つの同一データセットの値Ｄ０を上回るか、または全てのデータセットのペアについて上記値Ｄ０を下回る数値Ｄを２つのデータセットに割り当てる対称関数または非対称関数である。これは、同一の引数（すなわち同一のデータセット）がゼロの値を持つという距離の狭義の数学的定義に従ってもよいが、この値は当然シフトされ得る。なぜなら、本発明の状況において問題とされるは、データセットについて距離が確定する順序のみであり、距離の数値ではないからである。通常、距離は正となるように選択するが、単にＤを負の値Ｄ’＝−Ｄに置き換えることによって負の距離の使用を想像することも可能である。以降、明記しない限り、距離は常に正であると仮定する。
【００６９】
本発明は、距離が、上記ペアを形成するデータセットのデータ要素に依存する関数として定められることを規定し得る。距離は特に、共通するデータ要素に依存する関数であり得る。この距離の定義は、距離を定める関数の引数が文章の単語であるテキストファイルの場合に特に有用である。
【００７０】
本発明の状況において、好ましい距離の尺度は、共通するデータ要素の数に関連する関数である。この関数は通常、同一のデータセットが距離ゼロを持ち、距離が大きくなるにつれて同一のデータ要素は少なくなり、最大距離は最大値または無限大によって定められるように定義される。
【００７１】
たとえば、データセットが文書またはテキストファイルである場合、距離は、当該テキスト中の単語数に依存するものとして定められ得る。２つのテキストファイルＡおよびＢを単に数学的な単語セットとして考えると、距離Ｄは次のように定められる。
【数１】
2004503849.tif 000003
ここで｜｜は、セット中の要素数を示す。この距離は、タニモト（Ｔａｎｉｍｏｔｏ）距離として知られる。２つの文書が同一である場合、距離は１となる。ファイル中に共通な単語がない場合（テキストファイルではまれである）、距離は無限大となる。２つのテキストファイルが異なっており、異なる単語を含む場合、距離は、１と無限大との間の何らかの値となる。文書Ａが文書Ｂに完全に含まれる場合でも、距離は１ではなく次のようになることが留意されるべきである。
【数２】
2004503849.tif 000004
【００７２】
引き続きテキストファイルの例に関して言えば、（１）によって定められる距離は、意味または内容の類似度に依存しないことが留意されるべきである。その代わりに、この距離を用いる本発明の方法は、文章の単語を表す全てのデータ要素を、それらが同一か否かについて機械的にチェックする。原則的に、単にあらゆるテキストには一定数の共通する単語（「ａｎｄ」、「ｉｆ」など）があるため、内容が完全に関係のない文書には無限大未満の距離が割り当てられ得る。距離を評価する際にかかる単語を無視するように選択してもよい。
【００７３】
２つのデータセット間の距離が対称である必要はない。文書Ａが文書Ｂに完全に含まれる上記の例では、距離を次のように、（この場合では）ＡからＢへの距離がＢからＡへの距離よりも遥かに小さいように定めることによって、ＡのＢに対する相対的類似度（ｒｅｌａｔｉｖｅ ｃｌｏｓｅｎｅｓｓ）を示したいと思うかもしれない。
【数３】
2004503849.tif 000005
【００７４】
実生活では、特定の主題に関連する任意の２つのテキストには、当該主題に特有のキーワードがあるだろう。かかる特有のキーワードの一定の組み合わせは、特定の主題にかなり固有である。このキーワードの組み合わせを持つテキストファイルは、このキーワードの組み合わせを含まないテキストファイルよりも距離が小さいため、同じ主題に関連するテキストファイルは、距離が一定レベルを下回ることにより認識することができる。しかしながら、ユーザまたはプログラマが、特定の主題に関連するキーワードが何であるのかを知っていたり、テキスト中でこれらのキーワードを識別したりする必要がないのは、本発明の美点の１つである。単に、同じ主題に関連する２つの文書には多数の共通する特定のキーワードがあるという事実のみで、これら２つの文書間の距離が縮小される。したがって、２つのテキストファイルは、内容が密接に関連する可能性が高くなるほど、距離は小さくなる。本発明の方法の改良は、距離を計算する際にある種の非固有の単語（「ｉｆ」、「ｗｈｅｎ」、「ａｎｄ」など）は考慮に入れないことを規定することができ、よって特定のキーワードが距離に及ぼす影響を高める。本方法のさらなる改良は、距離を計算する際に、データセット要素（または文書の場合には単語）の単なる有無の代わりに、それらの頻度を考慮に入れ得ることを規定することができ、それによって、要素が同様の頻度で現れる傾向のあるデータセットが、同じ要素が異なる頻度で現れるデータセットよりも近いものとして定められるようにする。
【００７５】
２つのデータ文字列間の類似度を評価する別の距離尺度は、いわゆる同一長の順序付けされたセットのハミング距離である。基本的に、ハミング距離は、データ要素が同一であるあらゆる位置にゼロを、データ要素が同一でない位置には１を割り当て、距離は、全ての位置にわたるこれらの値の合計として定められる。
【００７６】
たとえば、比較するデータ要素が書簡である場合、「ｐａｔｔｅｒｎ」および「ｗｅｓｔｅｒｎ」という単語は、最初の３文字が異なり、最後の４文字が同一であるため、３の距離を有する。比較される要素は文字である必要はなく、単語または音節、あるいは逆の方向ではビットまたはバイトであってもよいことが留意されるべきである。たとえば、比較する要素が単語である場合、「ｔｈｅ　ｗｅａｔｈｅｒ　ｉｓ　ｆｉｎｅ」および「ｔｈｅ　ｇｒａｓｓ　ｉｓ　ｇｒｅｅｎ」という文は、１番目および３番目の単語が同一で、２番目および４番目の単語が異なるため、２の距離を有する。当然ながら、ハミング距離は、短いほうの文字列に一致する位置がない長いほうの文字列の全ての位置に１の値を割り当てることによって、異なる長さの文字列もカバーするように拡張することができる。ハミング距離は、データ要素の順序が問題となる場合、たとえばデータセットが遺伝子配列を含む場合に適している。順序が重要でない場合には、他の距離尺度が好ましい。しかしながら、ハミング距離の適用はデータ要素のシーケンスに制限されないことが留意されるべきである。ハミング距離は、セット、すなわち不規則であるように見える要素の集合に対しても定めることができ、当該セットに対して明示的または暗示的に順序が定められる。たとえば、セットに暗示的であり得る順序に、単語のセットにおけるアルファベット順があるが、書いた場合の当該セットの表現における文字のシーケンスはアルファベット順である必要はない。
【００７７】
広範なデータタイプに適用可能な別の距離群（ｆａｍｉｌｙ ｏｆ ｄｉｓｔａｎｃｅｓ）は、編集距離として知られ、（必要に応じてかかるデータタイプ毎に）あるデータセットを別のデータセットに変換するために必要な変更の最小数として定められる。遺伝子配列の場合、これは、ある配列を別の配列に変化させるために必要な挿入、欠失、および置き換えの最小数に相当する。テキスト文書の場合、これは、必要とされるテキストの挿入、削除、置き換え、および移動回数（そしておそらくは長さ）である。ツリーまたはグラフなどの数学的構造の場合、これは、削除または追加すべきノードの数ならびに削除、追加、または移動すべき辺の数である。これらの編集タイプの各々（追加、削除、置き換え、移動など）は、距離の計算におけるその寄与を増大または低減させるために、さらに重み付けすることができる。
【００７８】
上記の例は、距離尺度の基礎を築くデータ要素として選択されるものは特定の用途によって異なることを示す。大抵の場合に、これらのデータ要素は個々のビットと同一でなく、その代わりに、複数のビットさらには多数のサブシーケンスからなるデータシーケンスを形成する。
【００７９】
本発明は距離の特定の定義に制限されないことが理解されるべきである。上記の例のほかに、Ｔ． Ｋｏｈｏｎｅｎ， Ｓｅｌｆ−Ｏｒｇａｎｉｓａｔｉｏｎ ａｎｄ Ａｓｓｏｃｉａｔｉｖｅ Ｍｅｍｏｒｙ， （１９８８）に記載されるものなど、他の距離の定義を用いることもできる。距離は、単語に関連せず、異なるデータ要素に関連する場合がある。たとえば、遺伝学において適用される距離尺度が、Ｌ． Ｃａｖａｌｌｉ−Ｓｆｏｒｚａ， Ｐ Ｍｅｎｏｚｚｉ， Ａ． Ｐｉｎｚｚａ， Ｈｉｓｔｏｒｙ ａｎｄ Ｇｅｏｇｒａｐｈｙ ｏｆ Ｈｕｍａｎ ｇｅｎｅｓ， （１９９４）に記載されている。
【００８０】
距離はまた、必ずしも共通のデータ要素だけに関連しない。テキストファイルの例に再び戻ると、同義語を同一の単語として扱うこともできる。同様に、特にドイツ語の屈折を説明するために、同じ語根を持つ単語を同一として扱うことができる。さらに踏み込めば、様々な言語のテキストファイルに対する本発明の適用を想像することもでき、その場合、異なる言語において同じ意味を持つ単語が同一言語の２つの文書の同一の単語のように扱われる。たとえば、引き続きハミング距離の例に関して言えば、ペア（ｔｈｅ、ｄａｓ）、（ｗｅａｔｈｅｒ、Ｗｅｔｔｅｒ）、（ｉｓ、ｉｓｔ）、（ｆｉｎｅ、ｓｃｈｏｎ）にゼロの値を割り当てることによって拡張ハミング距離を定めることができるため、「Ｔｈｅ　ｇｒａｓｓ　ｉｓ　ｇｒｅｅｎ」という文からの「Ｔｈｅ　ｗｅａｔｈｅｒ　ｉｓ　ｆｉｎｅ」および「Ｄａｓ　Ｗｅｔｔｅｒ　ｉｓｔ　ｓｃｈｏｎ」の距離はともに同じである。一方、２つの文「Ｔｈｅ　ｗｅａｔｈｅｒ　ｉｓ　ｆｉｎｅ」および「Ｄａｓ　Ｗｅｔｔｅｒ　ｉｓｔ　ｓｃｈｏｎ」は、距離ゼロを有することになる。ここでもまた、本発明は、最後に言及したこれらの文が２つの異なる言語において同じ意味であると誰かが認識することに左右されない。それどころか本発明は単に、データ要素間の所定の関数関係を使用するだけである。これらの例外または拡張関係はいずれも、所定の距離の定義に包含されることが理解されるべきである。
【００８１】
データセットの距離の概念は、本発明に従って、データ構造を作成するために用いられる。驚くべきことに、多くの場合、特定の距離値が発生する頻度はピークおよびバレーすなわちゼロを示すことが見出された。本発明によれば、これらのバレーすなわちゼロは、階層構造においてデータセットを分類するために用いられる。再びテキストファイルまたは文書の例をとると、距離の小さいファイルは、互いにより密接に関連するものとみなすことができる。
【００８２】
データセットをクラスタに割り当てる１つの方法は、以下の通りであり得る。１つの選択したファイルから始めて、このファイルを含む、１番目のバレー未満の最小ペア間距離にある全てのファイルが、最下位レベルの第１のクラスタに割り当てられる。残りのファイルから、別のファイルを選び出し、このファイルからの距離が１番目のバレーの値未満である全てのファイルが、最下位レベルの第２のクラスタに割り当てられ、以下同様となる。
【００８３】
好ましい実施形態では、項目を選択し、それらを各レベルで１つずつクラスタに割り当てる代わりに、データ項目を頂点とし、項目間距離を辺としたグラフを構築する。項目をクラスタリングするために、長さが限界値によって画定される全ての辺を用いて、部分的なサブグラフを抽出する。部分的なサブグラフは、連続する構成要素に分割され、これらの構成要素の各々は、そのレベルの１クラスタに対応する。部分的なサブグラフの抽出は、限界値よりも大きい長さを持つ全ての辺を取り除くことによって達成することができ、その結果、いくつかのグラフ部分が断続的になる。連続するサブグラフを得るためには、ある頂点から別の頂点への、長さが限界値未満である少なくとも１つの辺があって、このグラフィカルな手順が、最小ペア間距離は限界値未満であるという要件に合致すれば十分であることが容易に理解されるだろう。
【００８４】
他のクラスタリング方法を同様の方法で具現化することができる。たとえば、最大ペア間距離は限界値未満であるというのが要件である場合、本発明は、選択したファイルからの距離が１番目のバレーよりも小さい全てのファイルを判定した後で、全てのファイルを、そのように選択された他の全てのファイルからの距離が１番目のバレーの値未満であるかどうかについてチェックすることを規定し得る。この基準を満たさないファイルはクラスタから取り除かれ、最終的にクラスタは、ファイルのいずれのペアも１番目のバレーの値未満の距離にあるファイルのみからなるようにする。その後、クラスタから取り除いたファイルのうち１つを、次のクラスタを確定するための新たな基準ファイルとして選択し、プロセスを繰り返して次のクラスタを作成する。この次のクラスタは第１のクラスタのファイルも含み得ること、すなわち、この第２のクラスタを確定するために全てのファイルが検討されることが留意されるべきである。その後、別のファイルを選択し、以下同様として、１番目のバレーの距離未満の距離にあるファイルのいずれのペアに対しても、このペアを含むクラスタが１つあるようになるまでプロセスを繰り返す。
【００８５】
グラフィカルな手法を用いた好ましい実施形態では、最大ペア間距離は所定値未満であるという要件で所定レベルの項目をクラスタリングするために、そのレベルの上限未満の長さを持つ全ての辺を用いて、部分的なサブグラフを抽出する。次に、あらゆる項目が他の全ての項目に直接接続している小集団があるかどうか部分的なサブグラフを検索する。接続が完全ではない構成要素は、クラスタとしてそのレベルから除外されることになる。これは、小集団を完成する接続は必然的に、距離の大きな上位レベルでのみ見出されるためである。
【００８６】
クラスタリング方法により、データセットを複数のクラスタに割り当てることが可能である場合には、一実施形態に従って、この割り当てを２段階で行うことができる。第１段階では、高い同質性によって特徴付けられるクラスタのセットを生成するために、より厳しい（たとえば、項目間距離はそのレベルの上限を越えないという）基準を適用する。第２段階では、それほど厳しくない（たとえば、少なくとも１つの距離が上限未満であるという）基準を適用して、この基準を満たすデータセットを、基準が満たされた全てのクラスタに割り当てる。
【００８７】
次に上位のレベルのグループまたはクラスタを作成するために、距離の密度または頻度が次に高いバレーを判定する。上述したように、この上位クラスタに要素を割り当てるにはいくつかの可能性がある。具体的な一方法は、最下位レベルの１クラスタから１つのファイルを選び出し、最下位レベルの全てのクラスタを、距離が２番目のバレーの値未満であるデータファイルを含むかどうかについてチェックし、次にかかるクラスタすべての要素をこの第２レベルのクラスタに割り当てることである。たとえば、第１レベルのクラスタに対して第２レベルのクラスタからのリンクを確立することができる。別の方法は、第１レベルの場合とほぼ同じ方法で進めること、たとえば、１つのファイルを選び出して、他のどのファイルが２番目のバレーの値未満の距離にあるかを確定し、かかるファイルすべてを第２レベルのクラスタに割り当てることである。その際、第１レベルの１クラスタの特定の１ファイルから始めて、距離が上記２番目の値未満であるファイルが別の第１レベルのクラスタにあるということが起こる場合があり、一方で、同じクラスタ中の他のファイルが２番目のバレーの値よりも高い距離値を持つ場合がある。１つの代替案では、距離が部分的に限界値を上回るファイルを第２レベルのクラスタが含むことを容認することができる。あるいは、上記第１レベルのクラスタを、第２レベルの異なるクラスタに割り当てられる第１レベルの２つのクラスタに分割するか、この第１レベルのクラスタを第２レベルの２つの異なるクラスタに割り当てる。しかしながらこれは、複雑なクラスタリング構造をもたらし得る。
【００８８】
好ましいグラフィカルな手法では、第１レベルのクラスタについて上述したように進める、すなわち、各々の限界値よりも大きい長さを持つ辺をすべて取り除くことができる。別の例では、１つの頂点を基準頂点として選択し、この頂点を起点とする、各々の限界値よりも大きい長さを持つ辺をすべて取り除くことによって進めることができる。
【００８９】
好ましい手法は、上位レベルのクラスタにはクラスタ全体のみを割り当てることである。すなわち、上位レベルのクラスタに割り当てられた下位レベルのクラスタの全ての要素は自動的に、この上位レベルのクラスタの要素となる。そのためには、クラスタ間の好適な距離を上述のように、たとえば距離は２つのクラスタの２つの要素間の最小距離であるという意味で定めなければならない。当然ながら、この方法で定められる距離は、クラスタを構成する要素の距離に関する何らかの意味も同時に定めるように選択される。個々のファイルをクラスタ全体で置き換え、クラスタ間の好適な距離を定めてしまうと、最下位レベルのクラスタの設定に関して前述したような上位レベルのクラスタの確定に進むことができ、クラスタが前の例における個々のファイルの代わりとなる。
【００９０】
グラフィックでは、クラスタを表す新たな頂点で第１レベルの個々の頂点を置き換え、２つのクラスタ間で定められる距離を基にこれらの新たな頂点間の辺を再描画することによって進めることができる。あるいは、頂点が個々のファイルを表す元のグラフのままで、このレベルの限界値よりも大きいか、あるいは次に下位のレベルの限界値よりも小さい全ての辺を取り除くこともできる。下位レベルのクラスタを上位レベルのクラスタに帰属させることもでき、これは、例を２つ挙げれば、別の下位レベルクラスタに関連する要素または頂点につながる辺が少なくとも１つ残っている場合、または１つの下位レベルクラスタの頂点が別の下位レベルクラスタの頂点に完全に接続している（２つの異なるクラスタの要素間のいかなる辺も上記した２つの限界値の間にあることを意味する）場合である。
【００９１】
本発明は、即座に行うことができる、特に特定の検索主題に関連したデータファイルの分類を自動的に提供する。たとえば、本発明による装置またはデータベースを用いる者は、大量であるが処理可能な数のヒットにつながるある種の非常に一般的なキーワードを入力することができる。次にコンピュータは、本発明によるクラスタリング構造においてこれらのファイルを整理する。１つのレコードを特に関連性が高いことが分かった基準レコードとして選び出すと、コンピュータは検索者に、どのレコードが同等の関連性を持つと思われるかを、すなわち最下位レベルの同じクラスタにあるレコードを示すことができる。参照ファイルを含む第１レベルクラスタに含まれるファイルにユーザが満足しない場合、コンピュータはさらに、関連がある可能性のある多数のさらなるレコードが存在すること、すなわち、基準レコードを含む第２レベルの関連クラスタに含まれ、第１レベルのクラスタには含まれないファイルをユーザに示すことができる。これにユーザが満足しない場合、コンピュータは、第３レベルの各クラスタに含まれるレコードを提案し、以下同様となる。換言すればコンピュータは、ユーザが関連性の高いレコードを可能な限り最小の労力で見出す可能性が最も高いと思われるレコードの順序をユーザに提供する。キーワードを入力する代わりに、検索すべき情報を含む基準レコード（たとえば新規の方法の要約）をデータベースに一時レコードとして導入し、次に、この一時レコードを含む全てのレコードについてクラスタ構造を確定することもできる。その場合に、この一時レコードを含む最下位レベルのクラスタは、元のデータベースにおいて最も関連性の高いレコードを含むことになる。
【００９２】
本発明を実現することができる具体例を、次に図面を参照して記載する。これはかなり例示的であるので、この例は、テキストファイルまたは文書に関連するものとして記載するが、他の種類のデータセットにも適用することができる。
【００９３】
図５ないし図８において、文書を示すボックス間の線の長さは、対応する文書間の距離に関係ないことが留意されるべきである。
【００９４】
第１のステップ（Ｓ１）において、クラスタリングする文書が選択される。これらの文書は、データベースに、またはそのサブセット（たとえば特定のキーワードを含む文書のサブセット）のみに含まれる文書の全体を含み得る。
【００９５】
図３は、０〜４７の数字によって記号で表される４８件の文書のグラフィック表示を示す。これらの文書は、画面上の距離が文書間の距離Ｄ（たとえば式（１）によって定められる距離Ｄ）に相当するような方法で配置されている。それらの文書は肉眼には、それぞれがいくつかのより小さい、２つまたはそれ以上の文書のクラスタからなる３つあるいは４つの主要なクラスタとして分類されるように見える。
【００９６】
第２のステップ（Ｓ２）において、全文書の相互距離を確定する。
【００９７】
次のステップ（Ｓ３およびＳ４）において、距離値の密度を確定する。距離値の密度は、単位距離間隔当たりの特定の距離値の発生回数、すなわち
【数４】
2004503849.tif 000006
として定められ、ここで、ν（Ｄ）は、選択された文書の中での特定の距離値の発生頻度である。実際には、微分比（ｄｉｆｆｅｒｅｎｔｉａｌ ｒａｔｉｏ）を用いずに、差の比（ｄｉｆｆｅｒｅｎｃｅ ｒａｔｉｏ）、すなわち
【数５】
2004503849.tif 000007
を用いる。ここで、Δνは、幅間隔（ｉｎｔｅｒｖａｌ ｏｆ ｗｉｄｔｈ）ΔＤにおける距離がおよそＤである文書のペアの数である。
【００９８】
このステップを達成するために、距離値の範囲全体をビンに分割し、各ビンの密度を、距離がこのビンの範囲内に含まれる文書のペアの数として定める。この密度を各ビンに割り当てると、その密度のステップ関数またはヒストグラムが結果として得られる。通常、距離は正となるように選択し、同一文書の値を０または１とする。
【００９９】
図３に示す文書の分布から得られるヒストグラムを図４に示す。このヒストグラムは、検討中の４８件の項目について５０ビンのペア間距離を用いる。見た目には、３つまたは４つの大きなピークがあるように見える。深いバレーに分離された３つの大きな領域、そしてことによると一番右側に第４の小さな領域があることが分かる。しかしながら、２つまたは３つのビンのみを含む多数の高いバレーがあり、それらが本当のバレーなのか、小さなサンプルサイズによる見せかけの結果なのかははっきりしない。
【０１００】
次のステップ（Ｓ５）において、次数が増加する多項式をヒストグラムに当てはめ、当てはまり具合を評価する。たとえば、第１のステップでは、２次式をこのヒストグラムに可能な限り当てはめ、４次式を当てはめ、次に６次式、というように当てはめていく。各次数で可能な限り最もよい当てはまりを比較し、最もよく当てはまった多項式の次数を選択する（ステップＳ６）。好ましい実施形態では、これらの多項式が原点または原点付近を通るように制限する。図３のサンプルから得たヒストグラムへの２次式から１４次式までの偶数次数の多項式の当てはめを図４に示す。分布に当てはめた多項式は、ヒストグラムに重ねて示し、それらの次数を付した。１０次式が最もよく当てはまることが分かった。
【０１０１】
次のステップ（Ｓ７）において、最もよく当てはまる多項式の最小値を求める。距離密度において１番目の最大値に続く最小値は１番目のピークの上限を形成し、次の最小値（存在する場合）は２番目のピークの上限を形成し、以下同様となる。したがって、１番目の最小値は第１レベルのクラスタを画定する最小限界値すなわち切点となり、２番目の最小値は２番目の最小限界値すなわち切点となって第２レベルのクラスタを画定し、以下同様となる（ステップＳ８）。最後の切点は、正の無限大または大数に設定される。最上位のクラスタは、データセットの全体または本方法を適用する対象となるデータセットのサブセットである。しかしながら、最後の切点もまた、最高ピークの境界に設定することによって定めることもでき、その場合、最上位レベルには２つまたはそれ以上のクラスタが存在し得る。
【０１０２】
１０次式との最もよい当てはまりの結果として得られる有限の切点Ｃ１〜Ｃ４を図４に、そこに示されるヒストグラムに関して示す。最後の切点（無限大）は示していない。切点Ｃ４は、含むのが距離のうち５％未満であり、意味のあるレベルのクラスタリングを含み得ないことから、自動的に除かれる。肉眼での検査からの予測に反して、ヒストグラムの一番左側のかなり高いバレーは重要であることが分かった。
【０１０３】
次のステップ（Ｓ９）において、コンピュータは、たとえばポインタを作成すること、またはファイルを階層データ構造に入れることによって、各ファイルを各レベルのクラスタに割り当てる相関データを作成する。好ましい実施形態では、コンピュータは、あらゆる行および列がファイルに対応する距離行列を確定する。ここで、行列の要素は任意の２つのファイル間の距離である。次にコンピュータは、各々の限界値よりも大きい距離を示すあらゆるエントリを取り除いて、行列を、各行および列に少なくとも１つのゼロでない要素を持つ対角部分行列（ｄｉａｇｏｎａｌ ｓｕｂｍａｔｒｉｃｅｓ）からなる行列に置換によって変換できるかどうかについて解析する。当然この手順もまた、コンピュータが、頂点として表されるファイル間の辺を解析し、各々の限界値よりも長い辺を取り除き、連続するサブグラフの要素を最下位レベルのクラスタに割り当てるという点でグラフィカルに行うことができる。あるいは、上述したように、ステップＳ９において他の割り当て基準を用いることもできる。
【０１０４】
グラフィカルな手法を図５に示す。図５において文書は、０〜４７を付したボックスによって示され、ボックス間の距離は線によって示される。１番目の切点Ｃ１よりも長い文書間距離に相当する全ての線は削除されている。これは、図中左側の２つのスライダによって示される。左側のスライダ（最大スライダ）は、１番目の切点（ラベル０）よりも大きな距離は示されないことを示し、右側のスライダ（最小スライダ）は、１番目の切点よりも小さい全ての距離が示されることを示す。文書の記号は明確にするために再配置されている。しかしながら、図５に示す線の長さは文書間の距離に関係ないことが留意されるべきである。
【０１０５】
３つの文書を持つ１１個のクラスタと、６個の要素を持つ１つのクラスタと、９個の要素を持つ１つのクラスタとがあることが分かる。
【０１０６】
次のステップにおいて、次に上位のレベルのクラスタについて、２番目の限界値よりも大きい元の距離行列のエントリを削除し、連続するグラフまたは各々の部分行列を探すという点でプロセスを繰り返す。あるいは、元の距離行列を行列で置き換えることもでき、ここで、上の段落で言及した各部分行列は新たな行列の要素によって表されるので、行列の各要素は、検討中のレベルよりも次に下位のレベルのクラスタのペアに相当する。上述のように、この新たな行列の要素には、これから定められるクラスタの距離が与えられる。次にプロセスは、クラスタの連続するグラフまたはクラスタの対角部分行列を見出すために繰り返される。
【０１０７】
同じことを、上位クラスタについて繰り返す。最上位クラスタは、検討する文書の全体である。
【０１０８】
第２レベルのためのグラフィカルな手法を図６および図７に示す。図６は、やはり見やすさのために再配置した文書を示し、線は２番目の切点Ｃ２よりも小さい距離をすべて表す（最大スライダ＝１、最小スライダ＝０）。図７は、全ての線が１番目の切点よりも小さく２番目の切点よりも大きい距離に相当する図を示す。図７はもはや、個々の文書を示さない。その代わりに、ボックスは、図５に示されるクラスタを表す。図７では、クラスタの要素である文書を関連するボックスに示した。大きなクラスタでは、全ての要素を示すことはできなかった。図６および図７から、３つのクラスタが存在するようであることが一目で分かる。しかしながら、図６を参照すると、一番左および中央のクラスタにおける、互いからの距離が２番目の切点よりも小さい要素、たとえば文書３０および文書４４または文書４３および文書３０がある。他方で、一番右のクラスタは、残りのクラスタから完全に隔離されている。したがって、左側および中央のクラスタは単一のクラスタに結合されて、第２レベルのクラスタは２つになる。
【０１０９】
図８は、図３のサンプルから得たクラスタのグラフィック表示を示す。ここで、３番目の切点よりも大きく、２番目の切点よりも小さい距離に相当する全ての線は削除されている。ここでもまた、２番目の切点よりも小さい距離に相当する線が削除されているため、第２レベルのクラスタはもう一度、１つの記号にまとめられる。２つのクラスタを接続する線は１つしかないことが分かり、これは、第３レベルにクラスタは１つしかないことを意味する。
【０１１０】
この例において、クラスタは、クラスタの任意の要素について、距離が関連切点よりも小さい別の要素があるような方法で確定されていることが留意されるべきである。しかしながらこれは、距離が関連切点よりも大きい要素（たとえば図６の文書２５および４１）がクラスタにあり得ることを意味する。これは、図４において３番目の切点の右側に大きなピークがある理由を説明する。ただしこのピークは、さらなるクラスタレベルには相当しない。図３および図４を、本発明による方法から得られるクラスタレベルの数と比較すると、本発明に従って取られる手法、すなわちヒストグラムへの多項式（または他の好適な関数）の当てはめは、より客観的であり、図３におけるような要素のグラフィック表示、または図４におけるような距離密度のヒストグラムの目視検査から予測される結果とは異なる結果をもたらし得ることが明らかである。
【０１１１】
代替的な実施形態では、上位クラスタを決定する際、１番目のクラスタを決定した場合と同様に２番目のクラスタを決定することができる。すなわち、ランダムに選び出したファイルからの距離が２番目の切点よりも小さい全てのファイルを判定する。
【０１１２】
多数のファイルまたは文書がある場合、これらのファイルのランダムサンプルのみに基づいてクラスタ構造を定める限界値を確定すること、たとえばこのサンプルのみについて距離および距離密度を確定し、こうして得た密度から前述のように様々なクラスタの限界値を求め、次に全ての（すなわちランダムサンプルだけでない）文書を様々なレベルのクラスタに割り当てることができる。
【０１１３】
本方法は、最も好適な階層レベルの数を自動的に求めることが理解されるべきである。場合によっては、複雑すぎるデータ構造を回避するため、最大レベル数を制限することが賢明だろう。これらの場合には、所定の次数までの多項式のみを用い、これらの多項式の中で最もよい当てはまりを示すものを選択することになる。
【０１１４】
多項式による近似によっては、ピークの後に続く多項式のゼロが、鋭いピークの場合にピークの真の境界に対するよりよい近似であり得る。２つのピーク間には２つのゼロがあり得るため、ピークの実際の上限を最もよく近似するピークを注意して選び出さなければならない。一方で、近似を行うピークの幅がかなり広い場合には、ピークの後に続く１番目のゼロはピークの関連部分を切り離し、よってファイルを、それが当然属するはずの各々のレベルのクラスタから除外してしまう恐れがある。これらの場合には、最小値さらには２番目のゼロを切点として選択したほうが良いかもしれない。他の場合では、多項式の２つの最大値間にゼロがないかもしれない。これらの問題は、多項式の最小値およびゼロの両方を求め、このうち、多項式を当てはめた関数のピークを最もよく近似するのはどれかをチェックすることによって処理できる。
【０１１５】
距離密度に対する多項式の可能な限り最もよい当てはまりは、関連するビンの数、またはより具体的には各ビンの幅によって異なり得る。本発明は、特定のビンサイズに対して確立したヒストグラムに多項式を当てはめる代わりに、様々なビンサイズについて距離密度を確定し、これら全てのビンサイズにわたる平均を出すことを規定し得る。これにより、上述のように、様々な次数の多項式が当てはめられるステップ関数またはヒストグラムの平均がもたらされる。この変更形態のアルゴリズムを図２に示す。
【０１１６】
具体的なアルゴリズムは、以下の通りであり得る。
【０１１７】
まず、距離ベクトルｖｄを定める。ベクトルは、次の長さを持つ。
ｍ＝ｎ（ｎ−１）／２
ここで、ｎはクラスタ構造を確定するために検討するファイルの数である。これは、上記のように、ファイルの全体、またはランダムサンプルのみであり得る。ベクトルｖｄは、ファイルのペア毎の距離値を要素として含む。
【０１１８】
次のステップにおいて、最大レベル数ｍａｘｌｅｖｅｌｓを次のように定める。
ｍａｘｌｅｖｅｌｓ＝ｍｉｎ（ＭＡＸＬＥＶＥＬＳ，ｍ／２）
ここでＭＡＸＬＥＶＥＬＳは、システムまたはユーザが定める最大レベル数である。ｍａｘｌｅｖｅｌｓが２未満である場合、検討される全てのファイルを含むクラスタレベルは１つしかない。
【０１１９】
さらなるステップにおいて、最大ビン数ｍａｘｂｉｎｓを次のように定める。ｍａｘｂｉｎｓ＝ｍｉｎ（ＭＡＸＢＩＮＳ，（ｘｍａｘ−ｘｍｉｎ＋ｄｘ）／ｄｘ）
ここでＭＡＸＢＩＮＳはシステムまたはユーザによって予め決められた数（たとえば１００）であり、ｘｍｉｎおよびｘｍａｘはそれぞれ、距離ベクトルｖｄにおける最小および最大距離であり、ｄｘは距離ベクトルｖｄにおける２つの距離値間のゼロでない最小差である。
【０１２０】
複数のビニング方法を平均することによって切点を求めるには、サイズがｍａｘｂｉｎｓであるベクトルｘｖａｌｓ、ｘｍｅａｎｓおよびｙｓｄｓ、ならびにサイズがｍａｘｂｉｎｓ×ｍａｘｂｉｎｓである行列ｆｖａｌｓを定める。ｍａｘｂｉｎｓは、最小のビンを用いたビニング方法のためのビンの数である。ｍａｘｂｉｎｓ個のビンを用いた方法によるビンの各々に対して、各ビンの中心点として定められる距離値を割り当てる。ｘｖａｌｓの値は、最小のビンを用いたビニング方法のためのビンの各々の中心点となるように設定される。
【０１２１】
行列ｆｖａｌｓは、各ビニング方法について距離密度の値を保持するものである。この行列の各列は、様々なビニング方法のｘｖａｌｓにおける要素、すなわち最小のビンを用いる方法に関して各ビンに割り当てられる距離値に関連する密度の値を受け取る。より大きなビンを用いる方法の場合、密度関数はステップ関数としてみなされる。すなわち、ビニング方法の特定のビンに含まれるｘｖａｌｓのあらゆる要素について、同じ密度値が行列に入れられる。たとえば、第１の方法がｍａｘｂｉｎｓ個のビンを用い、次の方法がｍａｘｂｉｎｓ／２個のビンを用いるものである場合、ｘｂｉｎｓの２個の連続する要素毎に、第２のビニング方法のｆｖａｌｓにおける同じ密度値が与えられる。
【０１２２】
行列ｆｖａｌｓの全ての要素に値が与えられると、ｆｖａｌｓの各行の平均が出され、この平均は、ベクトルｙｍｅａｎｓの各々の要素の値となるように設定される。各々の標準偏差は、ｙｓｄｓの各々の要素に入れられる。
【０１２３】
この結果は、平均化された密度関数であり、その値はベクトルｙｍｅａｎｓの値であり、値の各々の標準偏差はｙｓｄｓの要素である。グラフィックではこれを、測定点の図として表すことができ、各点には誤差棒を付ける。
【０１２４】
次のステップにおいて、関数を実験測定値の点に当てはめるのと同じ方法で、次数ｌが増加する多項式をこの関数に当てはめる。基本的には、同じ当てはめ技法を使用することができる。最小二乗法による当てはめを用いることができるが、必要に応じて任意の他の当てはめ方法も用いることができる。多項式の各次数について、ベクトルｘｖａｌｓの要素ｉに対応するｌ次式の値ｙｌｉを計算し、この多項式の誤差を次のように計算する。
【数６】
2004503849.tif 000008
ここで、ｉはベクトルｙｍｅａｎｓの要素のインデックスである。
【０１２５】
多項式の次数ｌは、前に定めたｍａｘｌｅｖｅｌｓの値によって次の通り制限される。
ｌ≦２ｍａｘｌｅｖｅｌｓ
２ｌ次式のピークは多くてｌ個であるため、このことは、ピーク数ひいてはクラスタレベル数を事実上ｍａｘｌｅｖｅｌｓに制限することが留意されるべきである。
【０１２６】
次のステップにおいて、次数がｌ≦２ｍａｘｌｅｖｅｌｓである多項式のなかで最小誤差ｅｒｒｌを持つ多項式を求める。
【０１２７】
次のステップにおいて、この多項式の最小値を求め、距離の１番目、２番目およびさらなる限界値すなわち切点となるように設定する。最後の切点は、無限大またはベクトルｖｄにおける距離の最大値となるように設定される。クラスタレベルの数は、そのように見出された切点の数に相当する。
【０１２８】
アルゴリズムは、適切な場合に、クラスタレベルの数を所定の最大レベル数未満の値に自動的に低減させることが留意されるべきである。したがって、本発明によるクラスタリング構造は、階層レベルが所定数である静的構造を提供するのではなく、見出した文書の種類にレベル数を適合させるという点で真に動的である。
【０１２９】
そのように様々なクラスタレベルの切点を確定してしまえば、上記のように、文書の各々は、各レベルのクラスタに割り当てられる。対応するアルゴリズムは簡単なもので、さらなる説明を必要としない。
【０１３０】
分布関数に対する様々な次数の多項式の割り当てに代わるものとして、ｙｍｅａｎｓによって与えられる分布関数を、その最小値、または最小値の数が（ｍａｘｌｅｖｅｌｓ−１）よりも大きい場合に最初の（ｍａｘｌｅｖｅｌｓ−１）個の最小値について検索し、これらの値を、クラスタ構造を確定するための限界値として用いることもできる。多項式の最小値を検索し、次に分布関数ｙｍｅａｎｓをその最も近い最小値同士について検索することによって、２つの手法を組み合わせることもできる。実際にはこれが好適な方法である。
【０１３１】
上記の例は完全に非限定的かつ例示的であり、本発明の範囲から逸脱することなく様々な変更がなされ得ることが理解されるべきである。たとえば、距離密度に当てはめる関数が多項式である必要はなく、別の好適な関数、たとえば三角関数であってもよい。特に、フーリエ解析を用いることができる。多項式の代わりに、有理関数（たとえば２つの多項式の比）を用いることもでき、これは時として、関数におけるピークがより良好にモデリングされ得るという利点を持つ。有理関数または多項式は、最小値およびゼロの数が関数の次数に直接関連し、三角関数におけるように等間隔である必要がないが、各々の係数を調節することによって当てはめプロセス中にシフトできるという利点を持つ。したがってそれらは、様々な幅を持つピークとの密度関数の当てはめに特に適している。
【０１３２】
特に、本発明の状況で使用される距離尺度は、上記の具体例とは異なるものとすることができる。たとえばデータファイルが、全てのファイルが最下位レベルの要素である階層において既に整理されており、当該階層は、枝と、枝を接続するノードとによって表される場合、ある要素から別の要素に到達するために通過しなければならないノードの数によって距離を定めることができる。たとえば、２つの要素が２番目に最下位のレベルのノードによってリンクされている場合、距離は１となり、それらが２番目に最下位のレベルの異なるノードにリンクされているものの、３番目に最下位のレベルの同じノードにリンクされている場合、距離は３となり、一方が３番目に最下位のレベルのノードに直接リンクしており、他方がこの第３レベルのノードに第２レベルのノードを介してリンクしている場合、距離は２となる。同様に、ツリー（たとえばＵＰＧＭＡツリー）を定めることもでき、ここで、枝の長さは、枝の長さの合計が元の距離行列における項目間の総距離と等しくなるように異なり得る、すなわち、行および列は、クラスタリングする個々の項目に相当し、行列の要素はこれら２つの項目間の距離を示す。この場合に、２点の距離は、当該２点間で最も短い接続の枝の長さの合計である。
【０１３３】
上記明細書および特許請求の範囲に開示する本発明の特徴は、本発明を様々な実施形態で別個に、また任意に組み合わせて実現する材料とすることができる。
【図面の簡単な説明】
【図１】クラスタ構造を確定するアルゴリズムの本質的なステップを示す図である。
【図２】変更形態のアルゴリズムを示す図である。
【図３】サンプルを形成する文書のグラフィック表示である。
【図４】図３に示すサンプルから得た距離密度のヒストグラムである。
【図５】図３のサンプルを示す図であり、線は文書間の距離を示し、１番目の切点よりも大きい距離に相当する線は削除されている。
【図６】図５と同様のグラフィカルな図であり、２番目の切点よりも大きい距離に相当する線は削除されている。
【図７】図５および図６と同様の図であり、第１レベルの同じクラスタに相当する文書は１つの記号にまとめられ、２番目の切点よりも大きいか、あるいは１番目の切点よりも小さい距離に相当する線は削除されている。
【図８】図７と同様の図であり、３番目の切点よりも大きいか、あるいは２番目の切点よりも小さい距離に相当する線は削除されている。
【図１】
2004503849.tif 000009
【図２】
2004503849.tif 000010
【図３】
2004503849.tif 000011
【図４】
2004503849.tif 000012
【図５】
2004503849.tif 000013
【図６】
2004503849.tif 000014
【図７】
2004503849.tif 000015
【図８】
2004503849.tif 000016
【国際公開パンフレット】
2004503849.tif 000017
2004503849.tif 000018
2004503849.tif 000019
2004503849.tif 000020
2004503849.tif 000021
2004503849.tif 000022
2004503849.tif 000023
2004503849.tif 000024
2004503849.tif 000025
2004503849.tif 000026
2004503849.tif 000027
2004503849.tif 000028
2004503849.tif 000029
2004503849.tif 000030
2004503849.tif 000031
2004503849.tif 000032
2004503849.tif 000033
2004503849.tif 000034
2004503849.tif 000035
2004503849.tif 000036
2004503849.tif 000037
2004503849.tif 000038
2004503849.tif 000039
2004503849.tif 000040
2004503849.tif 000041
2004503849.tif 000042
2004503849.tif 000043
2004503849.tif 000044
2004503849.tif 000045
2004503849.tif 000046
2004503849.tif 000047
2004503849.tif 000048
2004503849.tif 000049
2004503849.tif 000050
2004503849.tif 000051
2004503849.tif 000052
2004503849.tif 000053
2004503849.tif 000054
2004503849.tif 000055
2004503849.tif 000056
2004503849.tif 000057
2004503849.tif 000058
2004503849.tif 000059
2004503849.tif 000060
2004503849.tif 000061
2004503849.tif 000062
【国際公開パンフレット（コレクトバージョン）】
2004503849.tif 000063
2004503849.tif 000064
【国際調査報告】
2004503849.tif 000065
2004503849.tif 000066