障害物を考慮したクラスタリング問題への効果的なアプローチ

障害物を考慮したクラスタリングの課題

データ集合とクラスタ中心との距離を最小化できるという点で、分割型クラスタリング手法は理想的です。しかし、k-means法を採用した場合、障害物の存在によってクラスタ中心を適切な位置に配置できないという問題が生じます。

例えば、クラスタ中心が湖の中央に置かれてしまうようなケースが考えられます。そこで有効なのがk-medoids法です。この手法では、クラスタ内に実際に存在するオブジェクトを中心（medoid）として選択するため、こうした問題の発生を防ぐことができます。

距離再計算の必要性と幾何学的計算

新しいmedoidが選ばれるたびに、各オブジェクトと新しく選択されたクラスタ中心との距離を再計算する必要があります。2つのオブジェクトの間に障害物が存在する可能性があるため、オブジェクト間の距離は幾何学的な計算（例：三角測量を用いた手法）によって求めなければなりません。

ただし、オブジェクトや障害物の数が膨大になると、計算コストが非常に高くなるという課題があります。

可視性グラフによる問題の定式化

障害物を含むクラスタリング問題は、グラフ理論を用いて定式化できます。まず、領域R内の点pが別の点qから「可視」であるとは、pとqを結ぶ直線がどの障害物とも交差しないことを指します。

可視性グラフ（visibility graph）VG = (V, E) は、以下のように定義されます。

• 障害物の各頂点に対応するノードがVに含まれる。
• V内の2つのノード v₁ と v₂ は、それらが対応する頂点同士が互いに可視である場合に限り、E内のエッジで結ばれる。

さらに、VGに2つの追加点pとqを挿入して生成される可視性グラフを VG’ = (V’, E’) とします。E’には、V’内の2点が互いに可視であるとき、その2点を結ぶエッジが含まれます。

計算コスト削減のための前処理と最適化

任意の2つのオブジェクト集合（点）間の距離計算コストを削減するには、複数の前処理・最適化手法を組み合わせることが有効です。

その一つが、近接する点群をマイクロクラスタへグループ化するアプローチです。具体的には、まず領域Rを三角分割し、同じ三角形内に属する近接点を、BIRCHやDBSCANに類似した手法を用いてマイクロクラスタにまとめます。個々の点ではなくマイクロクラスタ単位で処理することで、全体の計算量を大幅に抑えられます。

さらに、最短経路の計算結果に基づき、次の2種類の結合インデックス（join index）を事前に構築しておくことも可能です。

• VVインデックス：障害物の頂点ペアごとに作成されるインデックス。
• MVインデックス：マイクロクラスタと障害物の頂点のペアごとに作成されるインデックス。これらのインデックスを活用することで、全体的なパフォーマンスをさらに最適化できます。

高品質なクラスタリングの実現

以上のような事前計算と最適化を施すことで、任意の2点間（マイクロクラスタ粒度）の距離を効率的に計算できるようになります。その結果、クラスタリング処理をCLARANSに代表されるような高性能なk-medoidsアルゴリズムと同様の方式で実装でき、大規模データセットに対しても優れたクラスタリング品質を達成することが可能になります。