リストから近くの地点をフィルタリングする

Question

私 ビットマップ内の塊のクラスターの検索に関する質問に半分答えました. 。「半分答え」と言うのは、ビットマップ内のすべての点を質量でソートし、同じクラスターから点を削除してリストをフィルタリングするのはリーダーに任せた状態のままにしたからです。

その後、そのステップについて考えてみると、思ったほど解決策が思い浮かばないことがわかりました。そこで今、皆さんに助けを求めています。次のような質量を持つ点のリストがあります (Python のタプルのリストですが、任意の言語で適切と思われるように表現できます)。

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

各タプルの形式は次のとおりです。

(x, y, mass)

ここではリストがソートされていることに注意してください。ソリューションでそれらを並べ替えたくない場合でも、まったく問題ありません。

チャレンジ、 思い出したら, 、質量の主なクラスターを見つけることです。クラスターの数は不明です。ただし、ビットマップのサイズは知っています。場合によっては、クラスター内のいくつかの点の質量が、次の (サイズの) クラスターの中心よりも大きくなることがあります。そこで、私がやりたいのは、質量の高い点から移動して、同じクラスター内の点 (近くの点) を削除することです。

これを試してみると、結局リストの一部を何度も確認する必要がありました。私はそれについてただ愚かな気がします。どうやってやりますか？疑似コードまたは実際のコード。もちろん、その回答で私が残した部分を Python コードで削除していただければ、実験が簡単になります。

次のステップは、ビットマップ内に実際にいくつのクラスターがあるかを把握することです。私はまだその問題を定義するのに苦労しているので、それについての質問を返すかもしれません。

編集： この質問には「正しい」答えがないことを知っていることを明確にしておきます。そして、質問の名前が重要です。クラスタリングのフェーズ 1 が完了しました。 近くのポイントをフィルタリングして除去する、高速かつ正確な「十分な」方法を探しています。

質問をより明確にする方法がわかりましたら、お知らせください。

Answer 1

念のため言っておきますが、あなたは問題の解決策を求めています。 姿勢が悪い 問題：決定的な解決策は存在しません。それはいいです...それはただもっと楽しくなります。あなたの問題は、必要なクラスターの数がわからないことが主な原因で、不適切に設定されています。クラスタリングは機械学習の重要な分野の 1 つであり、長年にわたってかなりの数のアプローチが開発されてきました。

アラクニドが指摘したように、 K 平均法 アルゴリズムは優れている傾向があり、実装は非常に簡単です。結果は、最初に行われた推測と必要なクラスターの数に大きく依存します。初期推測の問題を克服するには、ランダムな初期化でアルゴリズムを何度も実行し、最良の結果を選択するのが一般的です。「最良」が何を意味するのかを定義する必要があります。1 つの尺度は、クラスターの中心までの各点の平均二乗距離です。クラスターの数を自動的に推測したい場合は、全範囲のクラスター数を使用してアルゴリズムを実行する必要があります。適切な「最良の」尺度を得るには、クラスターが少ないよりも多い方が常に優れているように見えるため、クラスターが多すぎることにペナルティを与える方法が必要になります。の MDL ウィキペディアでの議論は良い出発点です。

K 平均法クラスタリングは基本的に最も単純です 混合モデル. 。場合によっては、期待値の最大化によって学習されたガウスの混合にアップグレードすると便利です (先ほどのリンクで説明されています)。これは、k-means よりも堅牢である可能性があります。これを理解するにはもう少し努力が必要ですが、理解できれば、実装するのは K 平均法よりもそれほど難しくありません。

他にもたくさんあります クラスタリング手法 凝集クラスタリングやスペクトルクラスタリングなど。凝集クラスタリングの実装は非常に簡単ですが、クラスタの構築をいつ停止するかを選択するのは難しい場合があります。凝集クラスタリングを行う場合は、おそらく次のことを確認するとよいでしょう。 KDの木 最近傍検索を高速化します。smacl の回答では、ボロノイ図を使用して凝集クラスタリングを行う少し異なる方法が 1 つ説明されています。

に基づいてクラスターの数を自動的に選択できるモデルがあります。 潜在的なディリクレ配分, 、しかし、実装を正しく理解するのは非常に困難です。

こちらもご覧ください。 平均値シフト アルゴリズムを使用して、それが本当に望むものに近いかどうかを確認します。

Answer 2

K-means アルゴリズムを探しているようです。

Answer 3

あなたの質問へのコメントで述べたように、答えはこの文脈で質量をスカラーとみなすことができるかどうかに基づいています。もしそうなら、色はスカラーとして扱われないことが多いため、色ベースのソリューションはおそらく機能しません。

たとえば、1ポイントの高質量の特定の領域がある場合、1/10質量の10ポイントの同じ面積を持つのと同じですか？これが当てはまる場合、このコンテキストでは質量はスカラーではないため、同様のスケーラブルでない値を空間的に取得するために使用されるアルゴリズムを調べる傾向があります。 ボロノイ図。

この場合、隣接する2つのボロノイ領域の質量が一致し、距離が十分に近い場合、それらをクラスター化できます。これを繰り返して、すべてのクラスターを見つけることができます。

一方で、あなたの質量がスケーラブルである場合、または未知の位置の質量を周囲のポイントから補間できる場合、三角測量して入力データの輪郭を描き、輪郭間の領域を使用して類似の質量のクラスターを見つけます。

Answer 4

これは、画像の色数を減らす色の量子化のように聞こえます。 1つの方法は、色を空間にプロットし、クラスターをクラスターの中心（または加重平均）に結合することです。

このメモリをトリガーしたアルゴリズムの正確な名前は失敗しますが、ポップアップが表示されたら答えを編集しますが、その間に色の量子化を見て、いくつかのアルゴリズムが有用かどうかを確認する必要があります。

Answer 5

＆quot; 凸包＆quot;問題。また、いくつかの「凸包」のようなクラスターも探しています。

＆quot; clusters＆quot;あいまいです。分野全体で平均質量を持っています。一部のポイントは平均質量を上回り、一部は平均未満です。クラスターを見つけたということは、平均をどれくらい上回っていますか？クラスターまたは別のクラスターの一部であるために、ノードはどれくらい離れている必要がありますか？

2つの山頂と尾根の違いは何ですか？

「地形」を計算する必要があります; -等しい密度のすべてのポイントを領域に結合します。これには、スポットを選択し、放射状にポイントから放射状に動き、密度が等しい位置を見つける必要があります。これらのポイントをリージョンに接続できます。

初期ポイントを賢く選択した場合、領域はネストするはずです。地元の高値から始めるので、出発点を選ぶのは簡単です。

Answer 6

すでに質量について話しているので、なぜ重力ベースのソリューションではありませんか。単純なパーティクルシステムは非常に正確である必要はなく、クラスターの数をより正確に推測できるようになるまで、あまり長く実行する必要はありません。

クラスター番号についてのより良いアイデアがあれば、k-means最近傍が実現可能になります。