障害物とのクラスタリングの問題にどのように取り組むことができますか？

セットとそのクラスター中心間の距離を最小化するため、分割クラスタリング手法が望ましい。 k-means法を選択できる場合、障害物が存在するため、クラスターセンターを使用できません。

たとえば、クラスターが湖の中心にあることが判明する場合があります。つまり、k-medoidsメソッドは、クラスター内のオブジェクトを中心として選択するため、問題が発生しないことが保証されます。

新しいメドイドが選択されるたびに、各オブジェクトとその新しく選択されたクラスター中心の間の距離を再計算する必要があります。 2つのオブジェクト間に障害物が存在する可能性があるため、2つのオブジェクト間の距離は、幾何学的計算（たとえば、三角測量を含む）によって導き出すことができます。

膨大な数の物体や障害物が含まれていると、計算コストが高くなる可能性があります。障害物のあるクラスタリングの問題は、グラフィカルな説明を使用して定義できます。まず、pとqに隣接する直線がいくつかの障害物と交差しない場合、点pは、領域R内の別の点qから明らかです。

可視性グラフは、V G =（V、E）のグラフであり、障害物の各頂点には、Vに同等のノードと2つのノードv ₁があります。 およびv₂ 、Vは、それらが定義する同等の頂点が互いに見える場合にのみ、Eのエッジによって結合されます。

VG’=（V’、E’）を、V’に2つの追加ポイントpとqを挿入することによってVGから生成された可視グラフとします。 E’には、2つのポイントが一緒に表示されている場合、V0に2つのポイントを追加するエッジが含まれます。

これを使用して、任意の2セットのオブジェクトまたはポイント間の距離計算のコストを削減できます。複数の前処理および最適化アプローチを使用できます。マイクロクラスターに近接している1つのアプローチグループポイントがあります。これは、最初に領域Rを三角形に三角形分割し、次にBIRCHまたはDBSCANと同様のアプローチを使用して、同様の三角形内の近くのポイントをマイクロクラスターに結合することで完了できます。

単一のポイントの代わりにマイクロクラスターを処理することにより、完全な計算が削減されます。その後、最短経路の計算に応じて、2種類の結合インデックスを構築するための事前計算を実装できます-

• 障害物の頂点のいくつかのペアのVVインデックス。

• マイクロクラスターと障害物の頂点のペアのMVインデックス。インデックスを容易にし、全体的なパフォーマンスをさらに最適化するのに役立ちます。

このような事前計算と最適化により、任意の2点間の距離（マイクロクラスターの粒度アプローチで）を効果的に計算できます。したがって、クラスタリングプロセスは、CLARANSを含む一般的な効果的なk-medoidsアルゴリズムと同様の方法で実装でき、巨大なデータセットに対して最高のクラスタリング品質を実現します。