JPH10500511A - 多次元関連データをクラスタリングする方法 - Google Patents

Abstract

(57)【要約】 多次元関連データをクラスタリングする方法は、データの収集体から、各々頂点（３１、３２、３３、３４、３５）によって表される特徴を識別し、一緒にクラスタリングしたい特徴の対を選択し、各選択された特徴の対を表す頂点の対をエッジ（４０、４１、４２、４３）によって接続し、所定の規則にしたがって各エッジにスコアを割り当て、最も高いスコアを有するエッジを選択し、前記選択されたエッジ（１７）によって接続される頂点を合体することにより新しい頂点を形成し、その合体された頂点に前に接続していた頂点と新しい頂点との間の新しいエッジを形成し、各エッジが所定のスコアを有するまで、このような手順を繰り返すことによって、行われる。

Description

【発明の詳細な説明】 多次元関連データをクラスタリングする方法 発明の背景 発明の分野 本発明は、一般的には、データベースにデータを記憶するための方法に関し、 特に、クラスタリングすために必要とされるリソースおよびスペースの点で効率 的であって、且つデータベースから選択されたレコードまたはデータを検索する ために必要とされる時間を短くできるような仕方にて、データベースにおいて、 例えば、地図データの如き多次元関連データをクラスタリングする方法に関する ものである。関連技術の説明 コンピュータは、その出現以来、収集データを探索したり、さもなくば、処理 したりするのに使用されてきているが、その収集データの量は、多過ぎて、一度 にそれらの全体を主メモリに保持させることができない。したがって、種々なプ ログラムにより、チャンクのファイルのデータのアイテムを順次読み取ることに より、大量のデータを長い時間かけて取り扱っていた。各レコードを別々に順番 に取り扱うことにより、あるファイルを処理すべきときには、ファイルの組織は 、それほど重要ではない。問題の特定のアイテムを繰り返し見つけ出してそのア イテムについてオペレーティングすることにより、あるファイルを使用すべきと きには、そのファイルの組織は、そのオペレーションを効率良くする上で非常に 重要となる。 この目的のため、ファイルにおけるレコードは、特定の順番にしたがって分類 されていることがよくあり、それらの特定のレコードは、その順番におけるそれ らの位置によって探索することにより、見つけ出されうる。例えば、ある銀行は 、口座番号によって預金者についての情報のファイルを分類している。このとき には、特定の口座のためのレコードは、その口座番号によって容易に見つけ出す ことができる。あるファイルは、２つ以上のシーケンスによってインデックス付 け されている。この場合には、レーコドは、２つ以上のアトリビュートによって見 つけ出されうる。データのインデッキシング、ソーティングおよびサーチングを 取り扱う非常に多くのリテラチャーがある。 大抵のファイル組織方法では、データは、顧客名のようなあるアトリビュート によって分類されている。その分類順番におけるタイは、その他のオーダリング 基準によって切り離すことができるが、その分類は、依然として、本質的には、 一次元のものである。その組織は、どの２つのレコードをとっても、一方のレコ ードが他方のレコードの前に来るというものである。これは、コンピュータにデ ータを記憶させる場合には都合がよい。何故ならば、コンピュータのメモリ装置 もまた、本質的には一次元的なものであるからである。それらのレコードは、あ る固定シーケンスにて現れるもので、多くの記憶装置の場合、あるファイルのシ ーケンスにおける１つのポイントから別のポイントへと移動するのに相当な時間 が掛かる。（ディスクの表面が二次元であるとしても、ディスク上のデータは、 一次元的シーケンスにて記憶されている。） 記憶すべきデータが、本質的に、例えば、地図データの如き二次元的（または １より大きい次元）なものであるときには、このような組織は、便利なものでは ない。適当な多次元スペースにおいて互いに近くにあるオブジエクトのレコード を、ファイルにおいても互いに近いところに置きたいことがよくある。何故なら ば、そのファイルは、１つのオブジエクトのレコードからそれに近いオブジエク トのレコードへと行くようにして使用されることが多いからである。しかしなが ら、これをサポートするようにファイルを組織することは容易ではない。もし、 例えば、ある町における任意に選択された場所のリストを有している場合に、地 上において互いに近くにあるポイントのレコードをファイルにおいても必然的に 互いに近くに置くように、それらを配列する方法はない。最も望ましいのは、出 来るだけ多くの関連したレコードをファイルにおいても互いに近くに置くことで ある。 一つの座標によってソーティングし他の座標によってタイを分離することは、 良い解決法ではないようである。ある町の想像ポイントは、経度によって分類さ れ、タイは、緯度によるソーティングによって分離される。このときには、例え ば、地上において互いに近くにある問題のポイントのレコードは、ファイルにお いては、経度において問題のポイントの間にあるが、緯度においてその町の他方 の端にあるような多くのポイントのレコードによって分離されてしまうことがあ りうる。 したがって、本質的に多次元的であるスペースからのオブジエクトを表すデー タレコードをクラスタへと集めるための種々な技法が開発されてきている。それ らの多くは、純粋に地理学的（または幾何学的）なものであり、互いに近くにあ るが関連のないオブジエクトのレコードを一緒に集めるものである。また他の多 くのものは、クライアントに使用するリソースの点で、または、データファイル のスペースの使用の点で、効率の良くないものである。本発明は、多次元スペー スからの関連データをクラスタリングのための新規な方法である。 多次元データ、特に、地図データの如き二次元データをリテラチャーにクラス タリングするための多くの方法がある。それらのほとんどは、クラスタリングす べきデータを相続いて分割していき、その結果できるクラスタが必要な程度まで 小さくなるようにするクワッドトリー方法の如きトップダウン方法である。これ らの方法では、形成されるクラスタのサイズが相当に変化してしまいがちである か、または、データの種々な領域において種々な異なる数のレベルを有するよう なサブディビジョンが形成されてしまいがちであるか、またはそれらの両方のこ とが生じてしまいがちである。その他のボトムアップ方法では、局部的に動作し がちであり、すなわち、１つのクラスタを一杯にしてしまってから、次のクラス タの形成に移るように動作しがちであり、これでは、クラスタのサイズに相当の ばらつきが生じてしまい、クラスタの形も不揃いなものとなってしまいがちであ る。本発明の方法は、ボトムアップであるが、グローバルなものであり、データ ベース全体に旦ってバランスのとれた形のよいクラスタを形成することができる 。 発明の概要 前述したように、本発明の主たる目的は、従来の方法よりも速く且つデータ検 索および記憶の点でより効率のよい、コンピュータデータベースにおける、例え ば、地図データの如き多次元関連データをクラスタリングする方法を提供するこ とである。本発明の好ましい実施例においては、本発明の方法は、次のようなス テップを含む。 ａ．コンピュータデータベースにおける問題のオブジエクトの収集体のなかの全 てのオブジエクトについてグラフにおける頂点を確立して、複数の頂点からなる グラフを与えるステップ。 ｂ．前記複数の頂点の選択された対をエッジにて接続するステップ。 ｃ．抑制されていない頂点を接続するエッジの各々に、それに関連した頂点を組 み合わせることがいかに望まれているかの尺度であるスコアを与えるステップ。 ｄ．ベストスコアを有するエッジで接続された２つの頂点を選択するステップ。 ｅ．前記２つの頂点を組み合わせるステップ。 ｆ．あるスコアが与えられる新しい合体された頂点およびエッジを形成するステ ップ。 ｇ．所定の終端状態に達するまでステップ(d)から(f)を繰り返すステップ。 本発明の別の実施例では、前述した方法は、さらに、データベースにデータを 維持することが望まれていないオブジエクトを表す頂点およびそれに関連したエ ッジを抑制して、データがデータベースに存在する特徴を表す複数の頂点を残す ようにするステップを含む。 本発明のさらに別の実施例では、前述の方法は、さらに、各頂点について、そ の頂点に接続されるベストエッジのスコアおよびそのベストエッジが接続する他 の頂点をリストしている頂点のリストを形成し維持するステップを含む。 本発明のさらに別の実施例では、前述した頂点のリストを形成し維持するステ ップは、前記リストをベストエッジスコアによってソーティングするステップを 含む。 前述した種々な方法を容易に実施するために、常にそうであるというのではな いけれども、次のような手法が使用される。 ａ．頂点およびそれに付随したスコアのリストは、最も高いスコアがそのリスト の頂部にくるようにして編集される。 ｂ．クラスタ自体は、相互作用的なプロセスにてクラスタリングされ、各相互作 用の後で組み合わされたサイズに対してより大きなサイズ制限／制約が課され、 それにより、データレコードのサイズに特定の均一性が維持されうるようにす る。 本発明のさらに別の実施例によれば、新たに形成されたエッジの各々のスコア がその新たに形成されたエッジによって置き換えられるエッジの数に対応してい るようにクラスタを組み合わせる方法が提供される。最も高い値を有するエッジ によって接続されるクラスタを組み合わせることで始めて、その組み合わせられ たクラスタが所定のサイズに達するまで、その組合せステップを続ける。 図面の簡単な説明 本発明の前述したような、また、その他の目的、特徴および効果は、次の添付 図面に関してなされる詳細な説明から明らかになろう。 第１図は、ある町の地図の部分を表す図である。 第２図は、第１図の地図上の特徴に対応する各領域および線分の頂点を示すグ ラフである。 第３図は、第２図のグラフに、各領域の頂点をその領域を境界付ける各線分の 頂点に接続するエッジを加えて示す図である。 第４図から第６図は、ある選択された頂点の抑制を例示する一連の図である。 第７図は、選択した頂点を抑制した後の第３図のグラフを示す図である。 第８図は、別の頂点が抑制されている第７図の再現図である。 第９図は、本発明によるある領域の境界ボックスおよびある線分の境界ボック スを例示する図である。 第１０図は、本発明による２つの線分の境界ボックスを例示する図である。 第１１図は、本発明による対角線線分の境界ボックスを例示する図である。 第１２図は、本発明による選択されたエッジにスコアを付して示す第８図のグ ラフの再現図である。 第１３図は、本発明による第１２図の頂点のうちの２つの合体を例示する図で ある。 第１４図は、複数の頂点を含み、それら頂点の種々なエッジ接続対に隣接して 任意のスコアを付して示すグラフである。 第１５図は、頂点のうちの２つの頂点を合体させ且つそれに関連した新しいエ ッジを形成した第１４図のグラフの再現図である。 第１６図は、本発明の別の実施例によるデータ／クラスタグラフである。 第１７図は、一対の頂点をそれらに関連したエッジを合体させた後の第１７図 のグラフの再現図であるグラフである。 第１８図は、一対の頂点およびそれに関連したエッジを合体した後の第１７図 のグラフの再現図である。 第１９図は、一対の頂点およびそれに関連したエッジを合体した後の第１８図 のグラフの再現図である。 好ましい実施例の説明 本明細書において使用する用語「特徴」は、データベースによって記述される 単一の個々のオブジエクト、例えば、ある川の部分、街路のブロック、湖、政治 的境界のセグメント等を意味している。 用語「クラスタ」および「頂点」は、各々、１つまたはそれ以上の特徴の収集 体を意味している。用語「頂点」は、ここでは、特徴のその収集体がグラフにお けるあるエレメントとして使用されているときには、１つまたはそれ以上の特徴 の収集体に関して使用される。用語「クラスタ」は、ここでは、その収集体がデ ータファイルに一緒に記憶されるべき特徴の収集体として使用されているときに は、１つまたはそれ以上の特徴の収集体に関して使用される。本明細書において は、クラスタと頂点との間に差はない。 第１図を参照するに、二次元表面の部分が示されており、すなわち、全体的に 参照符号１００を付して示されたある町の地図は、道路／街路を表す複数の線分 １−１６と、これら線分１−１６によって境界付けされた５つの領域１７−２１ を含んでいる。これら線分のうちのあるもの、またはすべてが、後で検索するた めのデータベースにおいて表されるべき特徴、例えば、街路、政治的境界、川等 を表しうる。この例では、これらの線分の各々は、ある街路のセグメントを表し ている。また、それら領域のうちのあるもの、またはすべては、後での検索のた めにデータベースにおいて表されるべき特徴、例えば、公園、湖、オフィスコン プレックス等を表しうる。この例では、領域１８は、公園を表しており、一方、 他の領域１７、１９、２０および２１は、データベースに記憶されるべき特徴を 表していない。 第２図を参照するに、全体として参照符号１１０として地図１１０上のオブジ エクトのグラフが示されている。例えば、これらオブジエクトは、ある街路の部 分／長さ部分、ビルディング、公園、湖、ある領域の境界等でありうる。グラフ １１０において、ドットによって表される頂点が、各オブジエクト、すなわち、 各線分１−１６および各領域１７−２１に対して与えられている。例えば、領域 １７を境界付ける線分８、５、１および４に対して、それぞれ頂点３１−３４が あり、領域１７に対して、頂点３５がある。ここで注意すべきは、グラフ１１０ および以後のグラフに存在する水平および垂直線８、５、１および４等は、後述 するエッジとは区別される構造線であり、意味を有しておらず、単に、グラフ１ １０上の頂点の相対的位置付けを容易とするために与えられているものである。 第３図を参照するに、各領域の頂点は、その領域を境界付けている各線分の頂 点に接続、すなわち、関連付けられている。この接続を「エッジ」と称する。例 えば、反時計方向に数えて、領域１７の頂点３５を第１図の線分８、５、１およ び４の頂点３１−３４にそれぞれ接続する４つのエッジ４０−４３がある。 本発明によるデータをクラスタリングする方法における次のステップは、デー タベースから除かれるべき、すなわち、データベースからその後に検索したいデ ータとは対応していない各領域および各線分の頂点を抑制するステップである。 したがって、領域１７、１９、２０および２１がデータベースに記憶されるべき 特徴でないとして、これら領域に対応する頂点を抑制するために、これら領域の 各々の頂点をその領域を境界付ける線分上の隣接する頂点に接続するエッジが除 去され、それら境界付け線分の各々の隣接頂点を相互接続するエッジに置き換え て、抑制された頂点に隣接する抑制されたエッジによって接続される、抑制され ない隣接頂点自体が新たに形成されるエッジによって接続されるようにする。例 えば、第３図および第４図の両方に示されるように、頂点３５は、エッジ４０− ４３によって隣接頂点３１−３４に接続される。第５図に点線および中空ドット によって示すように、第３図および第４図の頂点３５およびエッジ４０−４３は 、それらを除去し、頂点３１−３４をエッジ５０−５３によって接続することに より、抑制されており、その結果として、第６図に示すようなグラフ部分となっ ている。同じ技法を使用して他の領域１９、２０および２１の頂点を抑制する点 を 第７図に示している。ここで注意すべき点は、いくつかのエッジは、曲線として 示され、他のエッジは、直線として示されているということである。この図は、 単に、頂点の間の接続を目に見えるようにするためだけのもである。描かれた線 の実際の路は、重要ではない。 第７図を参照するに、領域１８を表す頂点６４は、エッジ５４−５８によって 頂点６３、３２、６０および６１にそれぞれ接続される。領域１９に対応する頂 点は抑制されているが、領域１９を境界付ける線分は、頂点６２、６５、６６お よび６７によって表される。頂点６２は、それぞれエッジ５４、７０および６９ によってそれに隣接する頂点６４、６５および６７に接続されている。 第８図を参照するに、もし、第７図に示したような頂点６２およびそれに関連 したエッジ５４、６９および７０を抑制する必要がある場合には、その頂点６２ およびエッジ５４、６９および７０が除去され、それらが接続されていた隣接頂 点６４、６５および６７が、エッジ７１、７２および７３によって接続される。 データベースからその後に検索したい地図中の各特徴は、一つの頂点を有して おり、各頂点は、その地図内の一つの特徴を表している。その上、地図において 隣接している特徴は、グラフにおいても隣接しており、すなわち、それらは、一 つのエッジによって接続される。 本発明の以下の説明では、各頂点は、１つまたはそれ以上の特徴を含むクラス タを表している。初めに、クラスタを組み合わせる前に、各クラスタは、唯一の 特徴を含む。 ２つのクラスタ、例えば、第１のクラスタおよび第２のクラスタを組み合わせ るときにいつでも、その組合せ体に対して、あるスコア（必ずしも数値的なもの ではないが、メリット数またはその他の値）が与えられる。このスコアは、考慮 中のクラスタを組み合わせることがどの程度望ましいかを示す尺度である。 データが地理学的データであるような本発明の第１の実施例においては、スコ ア＝（第１のクラスタの境界ボックスの面積）＋（第２のクラスタの境界ボック スの面積）−（組み合わされたクラスタの境界ボックスの面積）である。 ここで理解すべき点は、この本発明の実施例では、あるクラスタの境界ボック スの領域は、そのクラスタ、すなわち、ある頂点によって表される実際の特徴を 包囲する北−南および東−西に走る境界線を有する最も小さな矩形の領域である 。 第９図を参照するに、公園クラスタ／頂点とその公園の東側（北は、その紙面 の上部にある）の街路クラスタ／頂点とを合体する場合、公園クラスタの境界ボ ックスの面積は、ＡＢに等しく、一方、公園の東に対する街路クラスタの境界ボ ックスの面積は、零である。街路クラスタの境界ボックスの面積は、零である。 何故ならば、境界ボックスの長さは、街路部分の長さ、すなわち、Ｂに等しいが 、境界ボックスの幅は、零であるからである。したがって、前述の式を適用して 、その合体のためのスコアは、ＡＢ＋０−ＡＢ＝０である。ここで注意すべき点 は、その境界ボックスを定める図における点線は、目に見えるようにするために 、その真の位置からわずかにずらされているということである。 第１０図を参照するに、その長さに対応する値は、その線分の各々に隣接して 与えられている。例えば、公園の東の線分Ｃには、２の値が割り当てられており 、そこから延長する線分Ｄには、４の値が割り当てられている。もし、線分Ｃお よび線分Ｄに関連したクラスタを組合せまたは合体する場合には、前述した式を 使用して、便宜上Ｃとされた第１のクラスタの境界ボックスの面積は零であり、 便宜上Ｄとされた第２のクラスタの境界ボックスの面積は零であり、両方のクラ スタを包囲する境界ボックスの面積はＣＤであるとして計算される。合体から生 ずるエッジのスコア＝（第１のクラスタの境界ボックスの面積）＋（第２のクラ スタの境界ボックスの面積）−（組み合わせられたクラスタの境界ボックスの面 積）であるので、線分ＣおよびＤに対応するクラスタＣおよびＤを合体するため のスコアは、次のように算出される。 ０＋０−ＣＤ＝−ＣＤ、または、 ０＋０−（２×４）＝−８ ここで注意すべき点は、ある線分のクラスタの境界ボックスは、必ずしも零で はないということである。例えば、第１１図を参照するに、頂点８１を有する対 角線線分８０が示されている。境界ボックスの境界は、北南方向においても東西 方向においても零でない広がりを有しているので、頂点８１の境界ボックスの面 積は、ＧＨであることが分かる。 第１２図に示すように、前述した技法を使用して、グラフ上の一対のクラスタ を接合する各エッジのスコアが算出される。例えば、クラスタＣおよびＤの合体 から生ずるクラスタＷおよびクラスタＭ１を接続するエッジのスコアは、前述し たように計算して、−８である。 グラフのエッジの各々にスコアを付したとき、最も大きなスコアを有するエッ ジが選択される。第１２図に例示されたエッジの中で、最も大きなスコアは、零 であり、他のすべてのスコアは、負の値、すなわち、零より小さい。ここで注意 すべき点は、もし、２つ以上のエッジが同じ最大スコアを有する場合には、それ らのエッジのうちのどちらでも任意に選定しうるということである。 前述した実施例では、スコアを付ける方法は、ベストエッジ、すなわち、組み 合わせるのが最も望ましいクラスタを接続するエッジが、最も大きなスコアを有 するようにするようなものである。その他のスコアリング方法を使用することも 可能であり、例えば、ベストエッジが最も低いスコアを有するようにするもので もよい。 最も大きなスコアを有するエッジが選択された後、そのエッジによって接続さ れるクラスタを組み合わせるタスクを開始する。これらクラスタを組み合わせる ためには、それらの頂点を合体し且つそれら頂点の各々に関連した特徴のリスト を組み合わせることが必要とされる。例えば、第１２図を再び参照するに、参照 符号９０とされたエッジによって接続される参照符号ＶおよびＷとされたクラス タを合体することが望まれているものとする。 便宜上、クラスタＶに接続される頂点は、反時計方向において、英数字符号Ｗ 、Ｎ₁、Ｎ₂、Ｎ₃およびＮ₄によって示されている。頂点Ｗに接続されるクラスタ は、反時計方向において、英数字符号Ｖ、Ｍ₁およびＭ₂によって示されている。 第１３図を参照するに、クラスタを組み合わせた結果、すなわち、頂点Ｖおよ びＷを合体した結果が示されており、ここでは、新しい頂点Ｘが形成されており 、頂点Ｎ₁−Ｎ₄を頂点Ｖに接続したエッジのすべて、および、頂点Ｍ₁およびＭ₂ を頂点Ｗに接続したエッジのすべては、この新しく形成された頂点Ｘに接続され ている。ここで気付くべきことは、新しい頂点Ｘのエッジは、古い頂点Ｖおよび Ｗのエッジと同じ順番にて接続されるということである。反時計方向に見て、 それらエッジは、Ｖに接続された頂点に同じ順番で、すなわち、Ｎ₁、Ｎ₂、Ｎ₃ およびＮ₄に接続し、それから、Ｗに接続された頂点に同じ順番で、すなわち、 Ｍ₁およびＭ₂に接続するということである。グラフにおけるその他のすべてのエ ッジおよび頂点は、乱されずにそのままである。 前述したように２つの頂点を合体した後、新たに形成されたエッジにスコアが 付けられる。この点に関し、新しい頂点Ｘに接続したエッジのみにスコアを付け 直せばよいことに気付くであろう。それらエッジにスコアを付け直した後、最も 高いスコアを有するエッジの一つが再び選択される。第１２図および第１３図に 関して前述したように、それによって接続されるクラスタが組み合わされ、それ らの頂点が合体される。 頂点のクラスタリングおよび合体は、このようにして、２つのクラスタを最早 や合体することができなくなるまで、続けられる。例えば、このようなことは、 クラスタに関連した特徴のリストが一つのレコードとしては大きすぎるようにな るとき、すなわち、組み合わされるクラスタの特徴を含むレコードが所定のバイ ト数、例えば、８１９２バイトを越えるとき、および／または、組み合わされる クラスタが、所定の地理学的面積、そこに含まれるデータアイテムの数等を越え るときに、起こる。このようなことが起きるとき、決定されたクラスタ間のエッ ジは、組み合わせることができず、前述したようなスコアリング方法を使用する 代わりに、マイナス無限大（−∞）のスコアが与えられる。マイナス無限大が使 用されるのは、それが、最も低いありうるスコアであるからである。このように して、クラスタの組合せは、各エッジに−∞のスコアが与えられたときに、終了 する。 実際に、エッジのすべてにスコアを付けて最も高いスコアのエッジを見つけだ すプロセスは、ゆっくりしたものである。スコアの付け直しを制限し且つそれに よりそのプロセスをスピードアップするために、頂点のリストが形成される。そ のリストの各頂点に対して、頂点のスコア（すなわち、その頂点に関連した最も 高いスコアのエッジのスコア）およびその最もスコアの高いエッジが接続する隣 接頂点がリストされる。もし、２つより多いエッジが同じ最も高いスコアを有す る場合には、それらのうちの一つの隣接頂点を任意に選択する。頂点のリストは 、 頂点のスコアにしたがって分類される。例えば、第１４図を参照するに、頂点の 対を接続する種々なエッジに隣接して任意のスコアを付した複数の頂点Ａ−Ｈの グラフが示されている。頂点Ｃからの最も高いスコアのエッジは、２のスコアを 有していることに気付くであろう。このような２つのエッジがある。一方のエッ ジは、頂点Ａに接続され、他方のエッジは、頂点Ｄに接続される。次のリストに おいて、頂点Ｄが選定される。その後、それら頂点は、最も高いスコアを有する 頂点が、そのリストの頂部に置かれ、最も低いスコアを有する頂点がそのリスト の底部にくるように、分類される。 最も高いスコアを有する頂点がリストの頂部に見出されるようなリストの場合 には、次の合体は、頂点ＥおよびＦを含むことが分かる。 頂点ＥおよびＦが合体されて、第１５図に示すような新しい頂点Ｚが形成され た後、その新たに形成されたエッジにスコアが付けられる。ここで注意すべきこ とは、頂点Ｚに接続されるその新たに形成されたエッジのスコアは、この例では 任意であるということである。また、影響を受けないエッジは同じままであり、 頂点Ｚに接続されるエッジについてスコアを付けるだけでよいことが分かろう。 例示のために、その新しい頂点Ｚに接続されるエッジのスコアは次のようである と仮定する。 Ｂ−Ｚ ３ Ｄ−Ｚ ２ Ｈ−Ｚ −∞ 前述した頂点のリストにおいて、ＥおよびＦに対するリスティングは削除される 。何故ならば、それら頂点ＥおよびＦは、消えてしまうからである。 次に、Ｚに対するリスティングが加えられ、その位置およびＺの隣接頂点の位 置、すなわち、Ｂ、およびＨが、それらのスコアの大きいさにしたがって必要に 応じて調整される。その新しいリスティングは、次のようであることが分かろう 。 ある応用においては、クラスタリングされるデータ用途としては、ヒエラルキ ー形式にてより大きなクラスタを形成するようにクラスタのセットを集合させた いような場合がある。すなわち、クラスタの一つのセットを形成し、それから、 第２のクラスタリングにおける各クラスタのエレメントのセットが第１のクラス タリングからのクラスタのある収集体のエレメントのセットのユニオンであるよ うにして別のクラスタのセットを形成したことがある。この場合には、頂点当た り一つのデータエレメントでなく、むしろ、第１のクラスタリングオペレーショ ンで残された状態にあるグラフでもって第２のクラスタリングオペレーションを 始め、もし、エッジスコアリング機構が変更された場合には、必要に応じてエッ ジの優先度キューを再構成する。 別な仕方として、ある応用においては、クラスタリングされるデータの用途と しては、より低いレベルのクラスタであるようなエレメントを有するより高いレ ベルのクラスタを形成したいような場合がある。この場合においては、本発明を 再び単に使用すればよい。第２のクラスタリングプロセスにおいて、データエレ メントは、第１のクラスタリングプロセスにてクラスタリングされたデータエレ メントではなく、むしろ、第１のクラスタリングプロセスからのクラスタである 。 他の応用においては、クラスタリングされるデータの性質は、前述したような 方法により、サイズが幅広く変化してしまうようなクラスタを形成してしまうか もしれないようなものである。このときには、だんだんと制限を大きくしていく ようにして相互作用的な方法を適用すると有効である。例えば、一つのクラスタ が、最大Ｎビットを含みうるとする。各クラスタのサイズをＮ／１６バイトに制 限して、データを一度クラスタリングし、それから、これらのクラスタを、Ｎ／ ４バイトにサイズを制限したより大きなクラスタを形成するように集合し、それ から、さらに、それらより大きなクラスタを、Ｎバイトにサイズを制限したさら に大きなクラスタを形成するように集合させる。このような相互作用的なプロセ スにより、より均一なサイズのクラスタが得られることが確認されている。 前述したように、２つのクラスタが組み合わせられるか否かの判断は、その結 果形成されるクラスタのサイズが大きすぎないか否かによってなされることがよ くある。これらの場合には、しばしば、データが記憶されているフォーマットは 、２つのクラスタを組み合わせることにより、その２つの元のクラスタのサイズ の和とは異なるサイズの新しいクラスタが形成されてしまうようなものである。 組み合わされたクラスタのサイズを計算するのは非常に費用が掛かるが、組み合 わされたクラスタのサイズの上限を予測するのは、はるかに容易である。このよ うな場合において、各頂点について、そのクラスタのサイズの予測上限を記憶さ せておくことができ、そのとき、クラスタの組合せ可能性を内輪に評価するのに それらを使用することができ、時には、その結果生ずるクラスタが大き過ぎるか もしれないことを、そのサイズの予測が誤って示しているので、２つのクラスタ を組み合わせることを拒否する。この結果、計算作業を相当に節約することがで きる。このような手法は、各クラスタの真の正確なサイズを時々計算することと 組み合わせて使用することができ、例えば、各相互作用またはヒエラルキーステ ップの開始時、または、クラスタリングプロセス中のランダムに選択された時間 にて、各クラスタの真の正確なサイズを時々計算することと組み合わせて使用す ることができる。 さらに他の応用においては、クラスタリングされるデータの性質は、クラスタ リングプロセスの途中でその組合せが望ましいクラスタを見出すようなものであ る。例えば、もし、クラスタリングされるデータが地理学的なものであり、クラ スタの重なり範囲を最少とするのが望ましい場合には、ある集合が行われた後に 、一方のクラスタの地理学的範囲が他方のクラスタの地理学的範囲を完全に含ん でしまうように、一つのエッジによって接続され得ないような２つのクラスタが あることを見出しうる。そのときには、それらクラスタの頂点の間にあるエッジ を加えることが必要となる。 このようなクラスタ対を探すステップを加えることができる。不都合なことに 、クラスタリンググラフの全体の各頂点対をチェックするのでは、このオペレー ションは、非常に費用の掛かるものとなってしまう。しかしながら、もし、その クラスタリンググラフを平面グラフとして維持する場合には、グラフの各フェー ス（平面グラフのフェースは、そのグラフのエッジによって境界付けされた平面 の領域である）を調べて、そのフェース内の非隣接頂点の各対をチェックするこ とにより、そのような頂点対の多くを素早く見つけだすことができる。さらに、 もし、あるエッジを加える場合には、クラスタリンググラフの平面性が保存され る。 本発明の別の実施例では、クラスタリングされるべきデータ自体は、あるグラ フの頂点を表している。一緒にクラスタリングすることが望まれる頂点は、元の グラフにおけるエッジによって接続される頂点である。この場合において、元の グラフ自体は、そのクラスタリンググラフの初期状態として使用されうる。 この実施例において、クラスタリングの最終目的は、異なるクラスタにおける 頂点を接続する元のグラフのエッジの総数を最少とすることである。このように するために、クラスタリンググラフにおける各エッジは、そのエッジによって表 される元のグラフに於けるエッジの数を、それに関連付けている。この数は、エ ッジの「重み」と称される。クラスタリンググラフを記憶する手段は、各エッジ と共にこの重みを記憶するように、変更される。このときには、その最終目的は 、クラスタリングが完了したときの、クラスタリンググラフのすべてのエッジの 重みの合計を最少とすることである。 先ず、クラスタリンググラフにおける各エッジのスコアは、その重みと同じと される。それから、２つのクラスタが組み合わされる。前にそれら２つのクラス タの間を走っていた元のグラフのエッジは、単一のクラスタ内に在る。クラスタ の間の他のクラスタは影響を受けない。共通の隣接クラスタを有する２つのクラ スタが組み合わされるとき、その隣接クラスタに対する新しい頂点のエッジの重 みは、前のエッジの重みの和に等しくされる。結果として、各ステップで、クラ スタの間のエッジの重みおよび元のエッジの数は、同期されたままである。 この実施例では、地理学的にコンパクトにする意向はないので、クラスタリン ググラフを平面グラフとして維持する必要はない。 第１６図から第１９図を参照するに、複数の水平線、垂直線および対角線、す なわち、エッジによって相互接続される６つの頂点１−６を含む組合せデータグ ラフおよびクラスタリンググラフが示されている。例示のため、頂点１および２ は、頂点１および２を取り囲む点線によって示されるように合体される。 第１７図を参照にするに、頂点１および２が合体された後、新しい頂点１，２ が、それから生ずる新しいエッジと一緒に形成される。この実施例では、新たに 形成されたエッジのスコアは、新たに形成されたエッジによって置き換えられる エッジのスコアの和に等しい。この和を決定するためには、前のグラフを参照す る必要がある。そこで分かるように、１，２および５の間に走る新たに形成され たエッジおよび１，２および６の間に走る新たに形成されたエッジは、それぞれ スコア２および１を有する。１，２から５へ走るエッジがスコア２を有する理由 は、第１６図から理解することができる。第１６図において、一方のエッジは、 ２から５へ走った１のスコアを有しており、別のエッジは、１から５へ走った１ のスコアを有しており、その和は、２である。その他の場合には、すなわち、１ ，２から４および１，２から３への場合には、１のスコアを有した一つのみのエ ッジが各頂点の間に走っている。 本発明のこの実施例の方法における次のステップは、最も大きなスコアを有し たエッジ、すなわち、１，２および５を接続するエッジによって相互接続される これらのクラスタを再び合体することである。 第１８図を参照するに、頂点１，２および５を合体するプロセスにおいて、１ ，２，５とされた新しい頂点が形成され、その結果、その新しい頂点１，２，５ と頂点６との間に新しいエッジが形成される。 第１７図を参照するに、第１８図のクラスタグラフにおけるエッジの新しいス コアを計算するために、頂点１，２，５と頂点４との間のエッジは２に等しいこ とが分かる。これは、合体前に、２つのエッジが頂点４を頂点１，２および頂点 ５に接続していた事実による。同様に、頂点１，２，５と頂点６との間の新たに 形成されたエッジは、２のスコアを有する。何故ならば、第１７図に示されるよ うに、頂点６は、１のスコアを有する１つのエッジによって５に接続され、且つ １のスコアを有する別のエッジによって頂点１に接続されていたからである。頂 点１，２，５および頂点３を接続するエッジのスコアおよび頂点３および頂点６ を接続するエッジのスコアは、１に等しいままである。 例示のために、組み合わされた頂点１，２，５が可能な最もおおきなクラスタ を形成し、他の頂点がそのクラスタ１，２，５とは組み合わされ得ないと仮定す る。この場合おいて、前述したように、頂点１，２，５を他の頂点に接続するエ ッジの各々には、その事実を反映するようにマイナス無限大（−∞）のスコアが 与えられる。この場合において、さらに組み合わせることのできる頂点は、頂点 ３および６だけである。 第１９図を参照するに、頂点３および６を合体すると、頂点１，２，５、頂点 ４および頂点３，６を含む３つの頂点が生ずる。前述したように、頂点１，２， ５は、最大サイズのクラスタを含むので、さらに組み合わせることは許されない 。したがって、頂点１，２，５から延長するエッジの各々には、−∞のスコアが 与えられ、データのクラスタリングが終わる。 本発明の好ましい実施例について前述したのであるが、本発明の精神および範 囲から逸脱せずに、特定の応用のために種々な変形がなされうるものである。例 えば、本発明は、地図特徴のクラスタリングに限定されるものでなく、例えば、 プリント回路上の構成部品、グラフのノード、共通の利害を有する人々、宇宙の 星等の如き二次元またはそれ以上の次元に分布されたものをクラスタリングする のに使用されうる。したがって、ここに説明した実施例は、本発明を例示するだ けのものであり、本発明の範囲は、それに限定されるものでなく、本請求の範囲 の記載によって判定されるべきである。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ダン リーニア エイ アメリカ合衆国 カリフォルニア州 94025 メンロ パーク リングウッド アベニュー 1030 (72)発明者 デローズ フランク ジェイ アメリカ合衆国 カリフォルニア州 94536 フリーモント ローラー アベニ ュー 5182

Claims (1)

1. 【特許請求の範囲】 １．コンピュータデータベースにおいて多次元関連データをクラスタリングする 方法において、 ａ．コンピュータデータベースにおける問題のオブジエクトの収集体のなかの 全てのオブジエクトについてグラフにおける頂点を確立して、複数の頂点からな るグラフを与えるステップと、 ｂ．前記複数の頂点の選択された対をエッジにて接続するステップと、 ｃ．頂点を接続するエッジの各々に、それに関連した頂点を組み合わせること がいかに望まれているかの尺度であるスコアを与えるステップと、 ｄ．ベストスコアを有するエッジで接続された２つの頂点を選択するステップ と、 ｅ．前記２つの頂点を組み合わせるステップと、 ｆ．あるスコアが与えられる新しい合体された頂点およびエッジを形成するス テップと、 ｇ．所定の終端状態に達するまでステップ(d)から(f)を繰り返すステップと、 を含むことを特徴とする方法。 ２．前記オブジェクトを識別し且つ選択された頂点の対をエッジにて接続するス テップは、 (a) 二次元表面上の領域および線分に対応する特徴を識別するステップと、 (b) 各識別された領域および線分ついて別々の頂点を形成するステップと、 (c) 各識別された領域に対応する頂点から前記領域を境界付ける各識別された 線分に対応うる頂点へのエッジを形成するステップと、 を含む請求項１記載の方法。 ３．前記オブジェクトを識別し且つ選択された頂点の対をエッジにて接続するス テップは、 (a) 二次元表面上の領域および線分に対応する特徴を識別するステップを含み 、所定の規則にしたがって各エッジにスコアを割り当てる前記ステップは、 （ｉ）組み合わされるクラスタのレコードのサイズが所定の最大サイズ以下の 場合には、（第１のクラスタを境界付ける境界ボックスの面積）＋（第２のクラ スタを境界付ける境界ボックスの面積）−（その組み合わされるクラスタを境界 付ける境界ボックスの面積）に等しいか、または、 （ii）組み合わされるクラスタのレコードのサイズが前記所定の最大サイズに 等しいか、それより大きい場合には、負の無限大（−∞）に等しい、 ようなスコアを選択的に割り当てるステップを含む請求項１記載の方法。 ４．所定の規則に従って各エッジにスコアを割り当てる前記ステップは、新たに 形成されるエッジにより置き換えられるエッジの数に等しいスコアを選択的に割 り当てるステップを含む請求項１記載の方法。 ５．各頂点について、その頂点に接続されるベストエッジのスコアおよびそのベ ストエッジが接続する他の頂点をリスティングする頂点のリストを形成し維持す るステップを含む請求項１記載の方法。 ６．頂点のリストを形成し維持する前記ステップは、前記リストをベストエッジ スコアによって分類するステップを含む請求項５記載の方法。 ７．前記ステップ(c)からステップ(g)を繰り返すステップを含む請求項１記載の 方法。 ８．前記ステップ(c)およびステップ(f)の各繰り返しは、エッジにスコアを付け る異なる方法を使用するステップを含む請求項７記載の方法。 ９．前記ステップ(g)は、前記ステップ(c)からステップ(g)の繰り返し毎に異な るより大きな制限付ける請求項８記載の方法。 10．前記ステップ(a)からステップ(g)を、各後の繰り返しを行う際に前の繰り返 しの結果を使用して少なくとも２回繰り返すステップを含む請求項１記載の方法 。 11．前記ステップ(g)は、前記所定の状態に達したか否かを判定するのに、正確 な値でなく予測される上方境界を使用するステップを含む請求項１記載の方法。 12．前記ステップ(d)からステップ(f)の各繰り返し中に、組み合わせることが望 ましいエッジによってまだ接続されていない頂点の対を識別し、それら各頂点の 対をあるエッジで接続するステップを含む請求項１記載の方法。 13．組み合わせることが望ましいエッジによってまだ接続されていない頂点の対 を識別する前記ステップは、そのグラフの同じ面上の頂点を考慮に入れるだけ である請求項１２記載の方法。 14．クラスタリングされる前記データは、地図データである請求項１記載の方法 。 15．データベースにデータを維持する必要のないオブジェクトを表す頂点および それに関連したエッジを抑制し、データがデータベースに存在する特徴を表す複 数の頂点を残すステップを含む請求項１記載の方法。 16．前記ステップｇの所定の終端状態は、クラスタをそれ以上組み合わせると特 定の制限を越えてしまうようなポイントにて達成される請求項１記載の方法。