1

我目前有一个问题，我想比较两个一维分布。在我的情况下，我试图找出我必须将其中一个分布移动到另一个分布，所以我会使用推土机距离进行比较。但是，我也对将分布转变为另一个的实际方向感兴趣。

一维中是否存在有向版本的推土机距离？

更准确地说，我有两个分布f : {1...N} -> |R，g : {1...N} -> |R我必须互相转换。现在我还想乘以从 bins in 移动到 bins in 的污垢量f，g但我想考虑这个方向。即，如果“污垢”从一个垃圾箱移动到另一个x垃圾箱，y我想乘以我移动的数量，x-y而不是d(x,y)标准的推土机距离。然后我想找到移动地球的总量最小化的运动。

有没有我可以使用的已知算法？我想我应该能够为此修改原始的匈牙利算法，但我还不确定如何做到这一点，因为我以前从未使用过这个算法。

4

3 回答 3

2

因此，如果我正确理解了您的问题，那么我认为下面的代码（在 Go 中）可以解决。如果您可以假设每个分布的积分相等（这意味着可以将一个转换为另一个），那么只需移动通过你的分布，从左到右，并在每一点计算出需要从右侧移动多少污垢，或者需要从那里向左侧移动多少多余的污垢。在所有情况下，您都可以假设您需要的任何污垢都可以得到，因此暂时有“负面”污垢是可以的。

// Finds out how to move dirt to transform b into a.
// assumes that the integrals over a and b are equal
func earthMover(a, b []int) []int {
  r := make([]int, len(a))
  for i := 0; i < len(a); i++ {
    // if diff is positive it means that there is too much dirt here and it
    // must be moved to the right.  if it is negative it means some dirt
    // needs to be pulled in from the right.  In either case dirt can be
    // moved over multiple spaces.
    diff := b[i] - a[i]
    r[i] = diff
    b[i] -= diff
    if i < len(a) - 1 {
      b[i+1] += diff
    }
  }
  return r
}

这是一个例子。负数表示从右侧拉入污垢，正数表示从左侧推到右侧。我认为对于您的指标，您只需将移动数组中的所有数字相加，因此这种情况的解决方案是 5。

target: [ 3  0  1  0  2  6]
source: [ 1  1  5  0  1  4]
  move: [-2 -1  3  3  2  0]

现在我看到了，如果这确实是您想要的，那么您实际上是在寻找分布的加权平均值或质心（污垢）的差异。例如：

            0  1  2  3  4  5
  target: [ 3  0  1  0  2  6]
weighted:   0 +0 +2 +0 +8+30 = 40

  source: [ 1  1  5  0  1  4]
weighted:   0 +1+10 +0 +4+20 = 35

如您所见，目标的质心减去源的质心就是我们之前得到的数字，40 - 35 = 5。

于 2012-04-04T16:16:46.330 回答
1

你的“距离”是平均值（f） - 平均值（g）。为了最小化地球移动的总量，而不考虑它移动了多远，贪心算法实现了最优值，即分布之间的统计距离。

于 2012-04-04T15:21:00.660 回答
0

https://github.com/wihoho/VideoRecognition

  • 通过文件接口适配作者的C实现与python模块
  • 修改后的 C 代码在文件夹 EarthMoverDistance SourceCode 下
于 2013-12-10T09:27:19.240 回答