4

一連の地理的位置（緯度/経度の形式）が与えられた場合、最も人気のある場所を見つけるにはどうすればよいですか？

例として、さまざまなポイントを含むマップを作成しました。

マップリンク

1、4、6、9を除いて、すべてのポイントがほぼ1つの場所にグループ化されていることがわかります。このグループの平均位置を計算するにはどうすればよいですか？理想的には、地図の人口が増えるにつれて、2番目に人気のある場所、3番目に人気のある場所などを計算したいと思います。

どうすればこれに取り組むことができますか？

前もって感謝します。

4

2 に答える 2

5

あなたがあなたに良い見積もりを与えそしてあなたがコーディングするのが簡単である単純な解決策を必要とするならば...

  • 場所のサイズと見なす半径を選択してください（100mと言います）
  • あなたの場所を繰り返して、それらをあなたのサークルの中心にします
  • Point-in-Circleを使用して、円内にある他のポイントの数を数えます
  • 円内で最も多くのポイントがある場所が最も人気があります。次に、それらのポイントをすべてセットから削除し、2番目に人気のある場所からn番目に人気のある場所まで繰り返します。

距離を緯度と経度に変換する方法は？経度の緯度をメートルに変換します

たとえば、1度の緯度は110574〜111693メートルです。

于 2013-01-28T20:42:10.907 に答える
2

DBSCANアルゴリズムは、おそらくあなたが探しているものです。

これは、密度に基づいてポイントのクラスターを見つけるアルゴリズムです。あなたの場合、人気は密であることを意味するので、それを使用してこのタスクを解決できます。2つのパラメータが必要です。

  • eps、クラスターを形成するために他のポイントを探す各ポイントの周囲の半径、
  • minPts、ノードのグループをクラスターと見なすためにポイントの周囲の半径内に必要なポイントの数。

また、ポイント間の距離を測定する関数も必要です。（緯度、経度）カップル（通常はWGS84形式）があるため、Haversize距離が必要です。

アルゴリズムにはいくつかの実装があります。Javaを使用している場合、Apache Commons Mathは適切な実装を提供します（詳細といくつかのコードスニペットについては、ここを参照してください）。eps = 1.0（半径1 km）およびminPts = 0（クラスターには1つ以上のポイントがあります）でDBSCANClustererを呼び出します。ハバーシン距離の実装については、この回答を参照してください（ epsに使用されるのと同じ測定単位と一致していることを確認してください）。最後に、サイズを小さくしてクラスターを並べ替え、「人気」で並べ替えます。

Collections.sort(clusters, (o1, o2) -> 
    Integer.compare(o2.getSize(), o1.getSize());
Cluster<? extends Clusterable> mostPopular = clusters.get(0);

私の記憶が正しければ、この実装は、そのサイズ（ポイント数）に関して2次時間で問題を解決します。直面する問題のすべてのインスタンスが同じサイズの例である場合、問題はありません。

于 2015-12-04T16:12:28.167 に答える