14

アプリケーションに送信される結果の数を減らすために、データベースを使用して緯度/経度の結果をクラスター化する方法を誰かが知っているかどうかを確認しようとしています。

クライアント側またはサーバー（アプリケーション）側のいずれかでクラスタ化する方法に関する多くのリソースがあります..データベース側ではありません:(

これは、仲間の SO メンバーからの同様の質問です。ソリューションはサーバー側ベースです (つまり、C# コード ビハインド)。

これを解決する運や経験はありますが、データベースではありますか? ハンサムでセクシーな DB チャレンジを求めているデータベースの第一人者はいますか?

助けてください ：）

x編集 1: 明確化 - クラスタリングにより、エリアのポイント数を 1 つのポイントにグループ化することを望んでいます。したがって、すべてを 1 マイル / 1 km の正方形にクラスター化すると、その「正方形」内のすべての結果が 1 つの結果にグループ化されます (たとえば、正方形の中央)。

編集 2: 私は MS Sql 2008 を使用していますが、他の DB に他のソリューションがあるかどうかを聞くことができます。

4

7 に答える 7

12

私はおそらく、ポイントのデカルト (WGS-84 ECF など) 座標を使用したk平均法クラスタリングの修正* バージョンを使用するでしょう。実装が簡単で、すばやく収束し、データがどのように見えるかに関係なく適応します。さらに、帯域幅の要件に合わせてkを選ぶことができ、各クラスターには同じ数の関連するポイント (mod k) があります。

クラスター重心のテーブルを作成し、元のデータ テーブルにフィールドを追加して、それがどのクラスターに属しているかを示します。データがまったく動的である場合は、クラスタリングを定期的に更新する必要があることは明らかです。ストアドプロシージャとトリガーでそれができるかどうかはわかりませんが、おそらく。

*「変更」とは、計算された重心ベクトルの長さを調整して、地球の表面に配置することです。そうしないと、(LLH に戻すと) 高度が負のポイントがたくさんできてしまいます。

于 2008-12-01T05:23:11.477 に答える
6

地理的な場所でクラスター化していて、それが他のものであるとは想像できません:-)、「クラスターID」を緯度/経度座標とともにデータベースに保存できます。

つまり、世界地図を (たとえば) 100x100 マトリックス (10,000 クラスター) に分割し、各座標をそれらのクラスターの 1 つに割り当てるということです。

次に、同じ正方形内のものを選択することで非常に近い座標を検出し、隣接する正方形のものを選択することで適度に近い座標を検出できます。

正方形のサイズ (およびその数) は、必要なクラスタリングの精度によって決まります。明らかに、2x2 行列しかない場合は、かなり離れた座標のクラスタリングが得られる可能性があります。

2 つのポイントが近接しているが異なるクラスター (1 つのクラスターの最北端、別の最南端のクラスター) などのエッジ ケースは常に存在しますが、クラスター サイズを調整するか、クライアント側で結果を後処理することができます。

于 2008-12-01T04:48:13.577 に答える
5

ポイントセットを簡単にキャッシュできるようにするために、地理的アプリケーションにも同様のことを行いました。私のジオハッシュ コードは次のようになります。

def compute_chunk(latitude, longitude)
  (floor_lon(longitude) * 0x1000) | floor_lat(latitude)
end

def floor_lon(longitude)
  ((longitude + 180) * 10).to_i
end

def floor_lat(latitude)
  ((latitude + 90) * 10).to_i
end

そこからすべてが本当に簡単になりました。特定のポイントから特定の半径までのすべてのチャンクを取得して、単一の memcache multiget に変換するためのコードがいくつかありました (それが欠落している場合はそれを埋め戻すためのコードもありました)。

于 2008-12-01T04:52:19.060 に答える
2

movielandmarks.comでは、 Beginning Google Maps Applications with PHP and AJAXの著者の 1 人であるMike Purvisのクラスタリング コードを使用しました。PHP と MySQL を使用してさまざまなズーム レベルのクラスター/ポイントのツリーを構築し、それをデータベースに格納して、リコールが非常に高速になるようにします。別のデータベースを使用している場合でも、その一部が役立つ場合があります。

于 2008-12-01T05:38:49.743 に答える
1

複数のアプローチをテストしないのはなぜですか?

  1. IKVM.NETを使用して .NET CLI でwekaライブラリを翻訳する
  2. コードから生成されたアセンブリと weka.dll (ilmerge を使用) をデータベースに追加します。

つまり、いくつかのテストを行います。他の誰よりもうまく機能する特定のクラスタリングはありません。

于 2010-01-15T11:43:22.863 に答える
0

MSSQL の空間データ型を使用できると思います。それらが私が知っている他の空間データ型に似ている場合、それらはポイントを長方形のツリーに格納し、次に低解像度の長方形に移動して暗黙的なクラスターを取得できます。

于 2008-12-01T06:47:06.237 に答える