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

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

本站内容版权属于本人。转载须告知本人,写明出处,并在文首提供指向本站对应文章的链接。
本文链接: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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据