問題タブ [euclidean-distance]

したがって、3Dポイントの参照セット（Rと呼びましょう）と他の多くの3Dポイントのセット（データポイントのセットのセットPとそのPi内の各データセットと呼びましょう）があります。

タスクは、いくつかのPiとRのデータポイントのユークリッド距離を最小化するPiを返すことです。私が見る方法は次のとおりです。

1. Piの各ポイントについて、Rの各ポイントと比較し、2つのポイント間の最小の差を見つけます。
2. これらの最小距離を合計して、PiとRの間の最小の合計「差」に到達します。
3. 答えの円周率は、差が最も小さいものです。

しかし、これは本質的にRのすべてのポイントとPのすべてのポイントの間の距離を調べることを意味するため、かなりクレイジーです。これは数千または数百万になる可能性があります。きっと私はそれよりもうまくやれる。

私は慣れていないMatlabで働いています。

使用するのに適したアルゴリズムは何ですか？これに最適なデータ構造はありますか？（たとえば、KDツリー？）

2 つのメッシュに対してハウスドルフ距離を実装する必要があります。メッシュは人間の臓器のさまざまなセグメンテーション結果であり、それらを比較する必要があります.1つのメッシュはゴールドセグです. 2 つ目はセグメンテーション アルゴリズムの結果です。

ハウスドルフ距離を使用しますが、正確に何をしなければならないかを理解するのにいくつか問題があります。メッシュ A の各ポイントの最も近いポイントをメッシュ B で計算する必要があること、およびその逆が必要であることを理解しました。これらは私の相対距離です。セット内の 2 つの対応する点については、最大の相対距離 => hausdorff を取ります。(私はそこまで)

今私の問題: 1 つのメッシュには ~100,000 ポイントがあり、もう 1 つのメッシュには ~2,000 ポイントがあります。したがって、n:1 の関係になります。ハウスドルフを計算するためにどのポイントを使用しますか? ヒントをいただければ幸いです。どうも！

R、G、B の 3 つの列に数千のデータ ポイントが格納された MySQL テーブルがあります。ユークリッド距離を使用して、特定のポイント (a、b、c) に最も近いデータ ポイントを見つけるにはどうすればよいですか?

色の RGB 値をテーブルに個別に保存しているため、値は各列で 0 ～ 255 に制限されています。私がやろうとしているのは、ユークリッド距離が最小の色を見つけることによって、最も近い色の一致を見つけることです。

距離を計算するためにテーブル内のすべてのポイントを実行することはもちろんできますが、スケーリングするには効率的ではありません。何か案は？

N 行 M 列の行列Xがあり、N 行 N 列の行列を計算する必要がありますY。

今のところ、ネストされたループを使用して O(n ² ) で実行する必要があります。行列演算を使用するなど、より良い方法があるかどうかを知りたいです。

より一般的にsum(....)は、関数にすることができ、fun(x1,x 2)そのうちx1のx2は M 行 1 列のベクトルです。

各行pが特定の点の座標を与える最初の場所のセットの行列とします。同様に、q各行が特定の点の座標を与える2番目の場所のセットの行列とします。

次に、ペアワイズ二乗ユークリッド距離の式は次のとおりです。

ここで、は行列の-番目の行をp(i,:)示し、はの転置を示します。ipp'p

kC ++のCUDA対応GPU（NVidia Tesla）で行列を計算したいと思います。GPUをサポートするOpenCVv.2.4.1を使用していますが、Thrustライブラリなどの他の代替手段を利用できます。しかし、私はGPUプログラミングにあまり精通していません。このタスクを実行するための効率的な方法を提案できますか？どのC++ライブラリを使用する必要がありますか？

Java で Apache Commons RealVector および ArrayRealVector クラスを使用しています。2 つのベクトル v1 と v2 の間のユークリッド距離を次のように計算できます。

ただし、二乗ユークリッド距離を取得しようとしています。Apache Commons Vector3D でこれを行う方法があることは知っています。distanceSq 関数を使用するだけです。私は高次元のベクトルで最近傍検索を行っているので、平方根を取る意味がありません。私のニーズに対して計算が無駄になるだけです。

私はそれをできた

もちろん、これには回避したい中間の ArrayRealVector を返すことが含まれます。二乗ユークリッド距離を取得するコードを簡単に作成できますが、Apache Commons 数学のソリューションを使用したいと考えています。組み込みのソリューションはどれも素晴らしいものです。他の Apache Math クラスからのソリューションでさえ、おそらく問題ありません。

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

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

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

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

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

古いデータ ビジュアライゼーションを新しいプラットフォームに変換していますが、コミュニティの並べ替え機能に少し固執しています。元のコードでは、作成者がコサイン類似度計算機で凝集クラスタリングを使用しているようです。Javascript でこれにアプローチする最善の方法は、カスタム コサイン類似度関数をメトリックとして使用して、clusterfck でツリーを作成することだと考えました。ツリーは、渡すデータのセットごとにほぼ正しくソートされます。(ただし、プロジェクトの仕様上、「ほぼ」では十分ではありません)。アルゴリズムをチェックしたところ、すべてが正しく見えましたが、コサイン類似度とユークリッド距離を使用して結果を比較すると、同じ並べ替え結果が得られます。

何が原因でしょうか? 何かを間違って渡している可能性があり、clusterfck はデフォルトで euclidean を渡していると思います。以下は私のコードの一部です。誰かが確認できますか？(また、コサイン類似度を計算する簡単な方法はありますか? JS にはドット積が組み込まれているとは思いません)。

N 次元空間の 2 点間のユークリッド距離を計算する必要があり、速度が重要です。N 次元空間の 2 つのポイントを表す 2 つの C スタイルの float 配列があります。

それらの間の距離の式は次のとおりです (^ は XOR ではなく、べき乗を意味します): sqrt(sum((p1-q1)^2 + (p2-q1)^2 + .... (pn-qn) ^2))

私の現在のコードは次のようになります。

このコードはかなり遅いので、これを高速化するライブラリがあるかどうか疑問に思っていましたか? 誰かが c で配列に対して数学演算を実行するための簡単なライブラリを作成したと想像します。これにより、配列に対して要素ごとの演算をすばやく実行できます。

編集: nevsan への回答として、約 10 または 20 の小さな N で多くの計算を行っています。

私はSimilarity Measureを読ん でいて、突然私の全世界がバラバラになりました。Clustering Technique を使用して検索エンジンを実装しました。Clustering には、ユークリッド距離としての距離測定値を持つ K Means を使用しました。また、コサイン類似度を使用して結果を表示しました。私は驚くほど正確な結果を得ていました.しかし、これを読んだ今、私​​がしたことは、ドキュメントベクトルを正規化し、2つのベクトル間のユークリッド距離を計算したため、マグニチュードをどこにも考慮していません.

私は何か間違っていますか？

ターム頻度が高いほど、tf-idf 値が高くなり、正規化された tf-idf 値が高くなるため、適切にランク付けされると思いますが。ありがとう

結果（正規化されていないベクトルを使用、数字はユークリッド距離）

結果(ベクトルは正規化、数値はユークリッド距離)

結果（数値はコサイン類似度）

結果 1 と 2 は一致しませんが、2 と 3 は一致しています。より多くの類似性、より少ない距離。距離は、クラスター重心ベクトルと各ドキュメントのドキュメント ベクトルとの間で取得されます。

実際、最も奇妙な結果は、ユークリッド距離が 418 で、最も類似度が 0.87 のドキュメントです。正規化された距離は 0.49 になり、類似度と一致します。