重複の可能性:
マッピング アプリケーションのクラスタリング アルゴリズム
場所の順序付けられていないリスト (座標を含む) があります。2 点間の距離を計算するには、Haversine 式を使用することを知っています。しかし、私が調べたクラスタリングのソリューションでは、最初にリストを並べ替える必要があると言われています。場所の正しい順序は何ですか? 互いに 1 メートル以内にあるすべての場所をクラスター化 (つまり、すべての場所を単一の clusteredLocation オブジェクトに入れる) したいのですが、最初に並べ替えを行わなくても実行できますか?
実際、私が知っているクラスター分析アルゴリズムは、ポイントを順序付けする必要はありません。それは、クラスター分析の目的全体をいくぶん無効にします。しかし、web2.0マーカー クラスタラーのような集約について考えているのではないでしょうか?
k-means、シングルリンク、および DBSCAN を見てください。すべてがウィキペディアでよく説明されており、Hub の記事 Cluster Analysis で説明されています。これらのいずれも、ポイントを注文する必要はありません。
分散を最小化する平均を計算するスマートな方法を見つけない限り、Haversine 距離は k-means または平均リンケージ クラスタリングには適していないことに注意してください。緯度経度座標の -180/+180 ラップアラウンドがある場合は、算術平均を使用しないでください。シングルリンケージ、完全リンケージ、DBSCAN、OPTICS はすべて問題ありません。