線文字列間の類似性

StackOverflow https://stackoverflow.com/questions/62496

  •  09-06-2019
  •  | 
  •  

質問

GPS によって記録された多数のトラックがあります。これは、より正式には多数の線ストリングとして説明できます。

記録されたトラックの一部は同じルートの記録である可能性がありますが、GPS システムの不正確さ、記録が別の機会に行われたこと、および異なる速度で移動して記録された可能性があるという事実により、それらは記録されません。完全に一致していますが、人間が地図上で見ると、実際に記録されているルートと同じであると判断できるほど十分に近くに見えます。

2 つの線ストリング間の類似性を計算するアルゴリズムを見つけたいと考えています。これを行うための自家製の方法をいくつか考え出しましたが、これが解決するための優れたアルゴリズムがすでに存在する問題であるかどうかを知りたいと思っています。

類似の平均が地図上の同じパスを表す場合、類似度をどのように計算しますか?

編集： 私が何のことを言っているのかよくわからない人は、このリンクで行文字列の定義を参照してください。 http://msdn.microsoft.com/en-us/library/bb895372.aspx - 私は ない 文字列について質問です。

役に立ちましたか？

解決

を計算します フレシェ距離 トラックの各ペアで。距離は、トラックの類似性を評価するために使用できます。

数学に関する警告: フレシェは、この分野の先駆者でした。 メートル空間 それはあなたの問題に関連しています。

他のヒント

推定される可能性のあるエラーに基づいて最初の行の周囲にバッファを追加し、2 番目の行がバッファ内に完全に収まるかどうかを判断します。

「同じルート」を決定するには、正規化されたパス ベクトルの最小セットを作成し、合計電力差を計算し、その合計を品質基準と比較します。

  1. GPS ウェイポイントを経路の全長で正規化します。
  2. パスのベクトルを一緒に歩き、各ウェイポイントでの最短ベクトルに基づいてパスごとに新しいパス ベクトルのセットを作成します。
  3. ベクトルの長さを重み付けする正規化されたパス内の各ベクトルのエンドポイント間の合計パワー差を計算し、
  4. 品質基準と比較します。

差の検出力 (たとえば、差の 2 乗から開始) と品質の尺度 (たとえば、総検出力の差のパーセントとして) を視覚的に調整します。このアルゴリズムは、パス一致の継続的な品質測定とバイナリ結果 (パスは同じですか?) を生成します。

ポール・トンブリンはこう語った。推定された可能性のあるエラーに基づいて、最初の行の周りにバッファを追加し、2番目の線がバッファ内に完全に適合するかどうかを判断します。

正規化されたベクトルのエンドポイントを比較するときにアルゴリズムを変更できます。エンドポイントの違いが特定のサイズを超えているかどうかを判断することもできます (Paul のバッファーのアイデアを実装)。あるいは、エンドポイントが「バッファー」の外側にある場合は、その事実を利用してそのエンドポイントの違いを無視し、比較できるようにすることもできます。 寄り道を無視する.

線分 A の各点 (Pa) に沿って歩き、Pa から線分 B の最も近い線分までの距離を測定し、これらの距離のそれぞれを平均することができます。

これは迅速または完璧な方法ではありませんが、有用な数値を提供できるはずであり、実装も非常に迅速です。

線ストリングは同じような点で始まり、終わりますか? それとも範囲が大きく異なりますか?

単一の線ストリングを [x,y] 点 (または [x,y,z] 点) のシーケンスであると考える場合、次の式を使用して、線ストリングの各ペア間の類似性を計算できます。 ニードルマン・ウンシュ アルゴリズム。参照されている Wikipedia の記事で説明されているように、Needleman-Wunsch アルゴリズムには、点のペア間の距離を定義する「類似度行列」が必要です。ただし、行列の代わりに関数を使用する方が簡単です。あなたの場合、単純に2Dを使用できます ユークリッド距離 関数 (または、ポイントに標高がある場合は 3D ユークリッド関数) を使用して、ポイントの各ペア間の距離を提供します。

実際、私はレーベンシュタイン距離問題に興味があるかもしれないと言っていた人 (アーロン F) の側にいます (そして引用しました) これ）。彼の答えはこれまでのところ最高のものであるように私には思えます。

具体的には、レーベンシュタイン距離 (編集距離とも呼ばれます) は、厳密には文字ごとの距離を測定しませんが、挿入や削除も実行できます。この距離測定に最適なアルゴリズムは二次時間で計算できます (文字列が長い場合はかなり時間がかかります)。しかし、計算生物学者はこれについて非常に優れたヒューリスティックを持っており、それはあなた自身にとって興味深いかもしれません。チェックアウト ブラスト そして ファスタ.

あなたの問題では、数値の文字列間の違いを扱っているようで、数値に注目しています。さらに詳しい情報を提供していただければ、目的に応じた BLAST/FASTA などの適切なバージョンをご案内できる可能性があります。いずれの場合も、ニーズに合わせて BLAST と FASTA を適応させることを検討してください。とてもシンプルです。

1: http://en.wikipedia.org/wiki/Levenshtein_ distance, http://www.nist.gov/dads/HTML/Levenshtein.html

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top