2

Edit/Levenstein 距離を使用して、単語間の類似性を測定しています。最も単純な実装とは異なり、私の手紙にはタイム スタンプがあり、サンプル番号 N=0,1,2,... としましょう。

私が直面している問題は、コスト マトリックスに沿って、同じ (最小) コストで終わるさまざまなパスを取得できることです。これらのさまざまなパスは、さまざまなターゲット文字列に関連付けられています。たとえば、ソース文字列aaとターゲット文字列の間の距離を測定しbab、ソース文字列がタイム スタンプ N=0 で始まると仮定すると、同じコスト 2 (1 つの追加と 1 つの置換) を持つ 2 つのパスがあります。

  1. bN=-1 で加算し、1 番目はそのままにして、2 番目を にa置き換えます。ab
  2. 1 番目aをbに置き換え、2 番目はそのままにして、N=2 でa追加します。b

時系列で並べると、次の 2 つの結果は異なります。

Time:    ... -1 0 1 2 3 ...
Source:         a a
Target1:      b a b
Target2:        b a b

それがいつ起こるかを知る必要があるので、いくつかの基準に基づいて 2 つの可能なターゲットから選択できます。途中でパスをトレースし、最小コストにつながるすべての可能なパスを追跡する以外に他の方法はありますか?

そもそもタイムラインはモデルの一部であるため、代わりにダイナミック タイム ワープを使用することを検討しましたが、コスト マトリックスが無限に初期化されているため ([0,0] エントリを除く)、最初のステップは、常にターゲットの最初のフレームをソースの最初のフレームに一致させ、その結果、ターゲットはソースと同じタイムスタンプで開始されます。とにかく、DTW を使用して、同じ最小コストにつながるすべてのパスをトレースする必要があります。

どんな助けや洞察も歓迎します。

4

1 に答える 1

2

あなたの問題についてもう少し考えてみると、DTW や Levensthein について誤解しているように思えます。どちらのアルゴリズムも、シーケンスを圧縮および拡張して、互いに一致させようとします。したがって、DTW の場合、例には次の解決策があります。

Solution1:
  a a
 /| |
b a b

Solution2:
a a
| |\
b a b

Solution3:
a a
|\|\
b a b

これらのソリューションを見ると、これらすべてのコストが 2 であることがわかります。つまり、すべてのケースで 2bが as に割り当てられます。これらの例が意味することは、最初のシーケンスでは、1 つのタイムスタンプが 2 番目のシーケンスと比較して押しつぶされるということです。たとえば、最初のソリューションでは、 の最初の 2 つのタイムスタンプがb a押しつぶされて、2 番目のシーケンスの最初のシーケンスに対応する単一のタイムステップが形成されaます (2 番目のシーケンスは単に逆になり、3 番目のソリューションはより複雑になります)。DTW は、特定の部分で異なる速度で再生されるシーケンスを処理することを目的としているため、「タイム ワーピング」の類似性があります。

タイムステップが本当に固定されていて、実際のゆがみを考慮せずにそれらを調整するだけでよい場合は、すべての調整を試してコストを計算することができます。

このようなもの（str2が短いと仮定）：

for i = 0 to length( str1 ) - length( str2 ) do
  shift str2 by i to the left
  calculate number of different position between shifted str2 and str1
done
return i with lowest difference

シフトとワーピングの両方が必要であると仮定すると (最初に何かが追加され、タイムステップが一致しない可能性があります)、サブシーケンス DTW を検討してください。このためには、境界条件を緩和する必要があります。

文字列を 0 ではなく 1 でインデックス付けすると仮定すると、DTW は次のように記述できます。

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = infinity;
cost( *, 0 ) = infinity;
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

その場合、DTW-Cost がcost( length( str1 ), length( str2 ) )あり、そこからパスをたどることができます。サブシーケンス DTW の場合、これを変更するだけです。

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = 0;
cost( *, 0 ) = infinity; // yes this is correct and needed
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

次に、DTW コストを として選択し、min( cost( x, length( str2 ) )からトレース バックしargmin( cost( x, length( str2 ) )ます。これは、一方の文字列が他方の部分文字列であることがわかっていることを前提としています。あなたがこれを知らず、両方が共通の歪んだ中央しか持っていない場合は、部分一致を行う必要があります.定義されます。

于 2011-08-11T19:43:52.817 に答える