python - リストから近くのポイントをフィルタリングする

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 つであり、長年にわたって開発されてきたかなりの数のアプローチがあります。

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

K-means クラスタリングは、基本的に最も単純な混合モデルです。期待値の最大化によって学習したガウス分布の混合物にアップグレードすると役立つ場合があります (直前のリンクで説明されています)。これは k-means よりもロバストです。それを理解するにはもう少し努力が必要ですが、理解できれば、実装は k-means よりも難しくありません。

凝集クラスタリングやスペクトル クラスタリングなど、他にも多くのクラスタリング手法があります。凝集型クラスタリングの実装は非常に簡単ですが、クラスターの構築をいつ停止するかを選択するのは難しい場合があります。凝集クラスタリングを行う場合は、最近傍検索を高速化するためにkd ツリーを調べた方がよいでしょう。smacl's answer は、ボロノイ図を使用して凝集クラスタリングを行うわずかに異なる方法を 1 つ説明しています。

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

平均シフトアルゴリズムを調べて、実際に必要なものに近いかどうかを確認することもできます。

Answer 2

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

たとえば、特定の領域に 1 つの高質量のポイントがある場合、それは同じ領域に 1/10 の質量の 10 ポイントがあることと同じですか? これが本当なら、この文脈では質量はスカラーではなく、ボロノイ図など、同様のスケーラブルでない値を空間的にグループ化するために使用されるアルゴリズムを見る傾向があります。

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

一方、質量がスケーリング可能である場合、または未知の位置の質量が周囲の点から補間できる場合、入力データを三角測量して輪郭を描き、輪郭間の領域を使用して同様の質量のクラスターを見つける傾向があります。

Answer 3

This sounds like color quantization, where you reduce the number of colors in an image. One way would be to plot the colors in space, and combine clusters into the center (or a weighted average) of a cluster.

The exact name of the algorithm that triggered this memory fails me, but I'll edit the answer if it pops up, but in the meantime, you should look at color quantization and see if some of the algorithms are useful.

Answer 4

Start with the "Convex Hull" problem. You're also looking for some "convex hull"-like clusters.

Note that "clusters" is vague. You have an average mass across your field. Some points have above average mass, and some below average. How far above average means you've found a cluster? How far apart do nodes have to be to be part of a cluster or a separate cluster?

What's the difference between two mountain peaks and a ridge?

You have to compute a "topography" - joining all points with equal density into regions. This requires that you pick a spot and work your want out from a point radially, locating positions where the densities are equal. You can connect those points into regions.

If you picked your initial point wisely, the regions should nest. Picking your starting point is easy because you start at local highs.

Answer 5

すでに質量について話しているので、重力ベースのソリューションではないでしょうか。単純なパーティクル システムは、それほど正確である必要はありません。また、クラスターの数をより適切に推測できるようになるまで、長時間実行する必要もありません。

クラスター数についてより良い考えがあれば、k-means Nearest Neighbor が実行可能になります。