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