cluster-analysis - ユークリッド空間で「最もタイトな」部分集合を見つける

Question

ポイント x_1、x_2、... x_n \in R^d で与えられます。これらのk点間の距離の合計が最小になるように、k点のサブセットを見つけたいと思います。単純にこれは O(n choose k) 問題ですが、より高速なアルゴリズムを探しています。

2 つの代替の同等の定式化を考えることができます。

1. 最小エッジ ウェイト クリークの問題: ポイントをグラフと考えてください。エッジ ウェイトは距離であり、最小ウェイト クリークを見つけます。これは、NP 完全であることが知られている最大辺重み問題 と同等です。ただし、グラフが R^d に埋め込まれていること、およびすべての重みが正であることを知っているという利点があるので、おそらく役立つでしょうか?

2. 制約のない最小部分行列の問題: 対称距離行列が与えられ、最小和の kXk マイナーを見つけたいと考えています。

これで何か助けていただければ幸いです。

Answer 1

最も明白な最適化では、実際には別の式は必要ありません。

最初に、ほぼ最適な候補を貪欲に見つけてください。メンバーを交換して、線形時間で改良してみてください。次に、徹底的な検索を行いますが、新しい候補が貪欲な候補よりも悪いときはいつでも停止して、検索スペースを刈り込みます。

例えば

1. 平均を計算する
2. 平均からの二乗距離でオブジェクトを並べ替える
3. 長さ k のすべての nk 間隔をこの順序でテストし、最適なものを選択します
4. 選択されていないオブジェクトについては、スコアが改善される場合は、選択されたオブジェクトのいずれかと交換してみてください

これで、剪定に適した候補が得られました。

次に、徹底的な検索を行い、この候補よりも悪い場合はいつでも停止します。

注: ステップ 1 ～ 3 は、高速な凸包アルゴリズムから着想を得たものです。