何千ものアドレスを含むセットがあります。各住所の経度と緯度を取得できる場合、セットを近接度別にグループに分割するにはどうすればよいですか?
さらに、さまざまなルールに従って「クラスタリング」を再試行することもできます。
- N グループ
- グループあたり M 個のアドレス
- グループ内の任意のアドレス間の最大距離
5839 次
5 に答える
11
k-means クラスタリングアルゴリズムを試すことができます。
于 2009-01-26T16:27:07.523 に答える
5
ベクトル量子化が必要な場合:
http://en.wikipedia.org/wiki/Vector_quantization
"これは、点 (ベクトル) の大きなセットを、それらに最も近い点の数がほぼ同じグループに分割することによって機能します。各グループは、k-means およびその他のクラスタリング アルゴリズムのように、重心点で表されます。 "
ここで、ベクトルは各住所の地理座標であり、制約 (近接性、グループ サイズ、グループ数など) に応じて、アルゴリズムに他のパラメーターを与えることができます。
k-means から始めることもできますが、私の経験から、ボロノイ ベースのアルゴリズムの方が柔軟です。ここで良い紹介です。
于 2009-01-26T16:28:11.703 に答える
2
クラスタ化するデータの規模によって多少異なります。力ずくのアプローチは、すべてのポイントの組み合わせ間の距離を距離配列に計算することです。結果の配列は N^2 であり、A から B までの距離は B から A までの距離と同じであるため、必要なのはその半分だけなので、結果のセットは N^2/2 になります。
比較的近い緯度経度座標の場合、緯度経度を x、y グリッドとして使用し、デカルト距離を計算することで回避できる場合があります。現実世界は平らではないため、デカルト距離には誤差が生じます。住所が全国にある場合に使用する必要がある、より正確な計算については、Mathforum.com のこのリンクを参照してください。
距離行列全体を処理するスケールがない場合は、効率を高めるために何らかのアルゴリズム プログラミングを行う必要があります。
于 2009-01-26T18:14:03.283 に答える
1
- すべてのアドレス間の距離のマトリックスを作成します。
- ランダムなアドレスから始めて、そのアドレスまでの距離を昇順に並べ替えます
- 作業中にマトリックスからアドレスを削除し、基準（グループのサイズまたは最大距離）に達するまで、開始アドレスに最も近いアドレスを新しいグループに配置します。
- グループがいっぱいになったら、別のランダムなアドレスを選択し、そのアドレスまでの距離でマトリックスを再分類します
- すべてのアドレスがマトリックスから削除されるまで、このように続けます。
アドレスが均等に分散されている場合、各グループは開始アドレスの周りに一種の円形になります。問題は、開始アドレスが既存のグループの近くにある場合に発生します。これが発生すると、新しいグループは古いグループをラップアラウンドし、停止基準がグループサイズのみの場合は完全に丸で囲むこともできます。max-distance制約を使用する場合、これは発生しません（他の制約がないと仮定します）。
これが良い方法かどうかはわかりませんが、それを試してみます。きっとたくさんの最適化が必要になるでしょう。特にエッジのアドレスの場合。
于 2009-01-26T17:03:02.410 に答える
1
「N グループ」と「グループごとの M アドレス」の制約は相互に排他的です。一方は他方を意味します。
于 2009-01-26T16:14:02.697 に答える