2

我正在使用Edit/Levenstein 距离来测量单词之间的相似性。与最简单的实现不同，我的信件有时间戳，比如说样本编号 N=0,1,2,...

我面临的问题是我可以沿着成本矩阵获得不同的路径，这些路径以相同的（最小）成本结尾，并且这些不同的路径与不同的目标字符串相关联。例如，如果我测量源字符串aa和目标字符串之间的距离bab，并假设源字符串从时间戳 N=0 开始，那么我有 2 条路径，成本相同为 2（一个加法和一个替换）：

  1. b在 N=-1 处添加，保持第一个a不变，并将第二个替换为aa b。
  2. 用 a代替第a一个b，保持第二个不变a，并b在 N=2 处添加。

在时间线上对齐，这两个结果是不同的：

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

我需要知道什么时候会发生这种情况，所以我可以根据一些标准在两个可能的目标之间进行选择。除了沿途跟踪路径并跟踪所有可能导致成本最小的路径之外，还有其他方法吗？

我考虑过使用动态时间扭曲，因为时间线首先是模型的一部分，但似乎由于成本矩阵被初始化为无穷大（除了 [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。这些例子的意思是，在第一个序列中，与第二个序列相比，一个时间戳被挤压在一起。例如，在第一个解决方案中，前两个时间戳b a被压缩以形成与第二个序列的第一个相对应的单个时间步长a（第二个序列正好相反，第三个解决方案更复杂）。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。为此，您只需要放松边界条件。

假设您将字符串索引为 1 而不是 0，您可以像这样编写 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 回答