いくつかのメトリック空間（たとえば、 Jaccard Distanceを装備）に多数のポイント（n> 10000）があります。メトリックをエッジの重みとして使用して、それらを最小スパニング ツリーで接続したいと考えています。
前もって感謝します！
以下のポスターの編集: 最小スパニング ツリーを見つけるための従来のアルゴリズムは、ここでは機能しません。それらは実行時間に E ファクターを持っていますが、私の場合、完全なグラフを実際に考慮しているため、 E = n 2です。また、49995000 を超える可能性のあるすべてのエッジを保存するのに十分なメモリがありません。
どうやら、これによると:サブリニア時間でメトリック最小スパニング ツリーの重みを推定すると、決定論的な o(n^2) はありません (注: smallOh、これはおそらく O(n^2) 未満という意味です。 ) アルゴリズム。その論文は、メトリック最小重みスパニング ツリーの準線形ランダム化アルゴリズムも提供します。
この論文も見てください：最適なアルゴリズムを提供する最適な最小スパニングツリーアルゴリズム。この論文はまた、最適なアルゴリズムの複雑さはまだわかっていないと主張しています!
最初の論文の参考文献は役立つはずであり、その論文はおそらくあなたの質問に最も関連しています。
それが役立つことを願っています。
3 ～ 4 年前に非常によく似た問題を調べていたとき、私が見た文献には理想的な解決策が見つかりませんでした。
私が考える秘訣は、「おそらく良い」エッジの「小さな」サブセットを見つけて、それで普通の古いクラスカルを実行できるようにすることです。一般に、いくつかの小さなkについて、各頂点をそのk 個の最近傍に結合する一連のエッジの中で、多くの MST エッジが見つかる可能性があります。これらのエッジはグラフにまたがらない場合がありますが、そうでない場合は、各コンポーネントを 1 つの頂点 (ランダムに選択) に折りたたんで、プロセスを繰り返すことができます。(精度を高めるために、単一の代表を選択して新しい「スーパーバーテックス」にする代わりに、いくつかの少数rの代表を選択し、次のラウンドで 2 つのスーパーバーテックス間のすべてのr ^2 距離を調べて、最小値を選択します。)
k -最近傍アルゴリズムは、オブジェクトを有限次元のユークリッド空間でベクトルとして表現できる場合について非常によく研究されているため、オブジェクトをそれにマップする方法を見つけることができれば (たとえば、多次元スケーリングを使用して)、あなたはそこに運があるかもしれません。特に、2D へのマッピングによりボロノイ図を計算でき、MST エッジは常に隣接する面の間にあります。しかし、私が読んだ限りでは、このアプローチが常に良い結果をもたらすとは限りません。
それ以外の場合は、クラスター化アプローチが役立つ場合があります。任意のメトリック空間での大規模なデータセットのクラスター化は、ユークリッド空間の必ずしも有限次元ベクトルではないオブジェクトを明示的に扱っている数少ない論文の 1 つであり、次の可能性を考慮しています。計算コストの高い距離関数。