Earth Mover's Distance —— 推土机距离

Earth Mover's Distance，推土机距离，简称EMD，用来表示两个分布的相似程度，在计算机中经常用到。下面以计算机中常见的离散分布举例。

在$k$维空间中，某个分布由向量集合给定：$\{<x_{i1},x_{i2},...,x_{ik},w_i>|1 \leq i \leq n\}$。其中$<x_{i1},x_{i2},...,x_{ik}>$代表空间中一个点，$w_i$代表这个点的权值，$n$可以是任意正整数，取决于这个离散分布的精确程度。在这个空间中定义两点间的距离$d(\textbf{x},\textbf{y})$，一般使用欧氏距离，即$d(\textbf{x},\textbf{y})=\sqrt{\sum_{i=1}^k(x_i-y_i)^2}$。

所谓“推土机距离”，就和“推土机”稍微有些联系。如果将分布看做空间中泥土的分布，那么两个分布间的距离就是将这些泥土从一个分布改变到另一个分布所需要消耗的最小能量。这里的能量是泥土重量（权值）和移动距离的乘积。

因为这里分布是离散的，可以看做$n$个点，并且每个点都自己的权值。当我们比较分布$X$和分布$Y$的时候，不妨将$X$中所有点放在左边，$Y$中所有点放在右边，点权值保持不变，对于$X$中的一点$\textbf{x}_i$（权值$w_{xi}$）和$Y$中一点$\textbf{y}_j$（权值$w_{yj}$），连接一条边，边权值为他们之间的距离$d(\textbf{x}_i,\textbf{y}_j)$。如此一来，这个问题就转化成了二分图上的流问题，假设$\textbf{x}_i$和$\textbf{y}_j$之间的流为$f_{ij}$，那么问题转化为：

$$emd(X,Y)=\min{\frac{\sum_{i,j}f_{ij}d(\textbf{x}_i,\textbf{y}_j)}{\sum_{j}w_{yj}}}, s.t. \sum_{i}f_{ij}=w_{yj}, \sum_{j}f_{ij}=w_{xi}.$$

这个问题是线性规划中的运输问题，可以用匈牙利算法迭代求解。最终求得的最小值就是EMD。

EMD的C语言实现：http://ai.stanford.edu/~rubner/emd/default.htm