アースムーバー距離

ウィキペディア

アースムーバー距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/03 06:21 UTC 版)

アースムーバー距離（アースムーバーきょり、英: Earth Mover's Distance, EMD）は、密度関数、度数分布、または測度の間の類似度を評価するための距離関数であり、計量空間 D 上に定義される。  

直感的には、分布を「土を積み上げた山」と見なすとき、一方の分布からもう一方を作るのに必要な最小の「労力」を表す。ここでの労力は、移動させた土の量と、それを動かした距離の積として定義される。

確率分布間におけるEMDは、ワッサースタイン距離 $W_{1}$、カントロヴィッチ-ルビンシュタイン距離、またはモローズ距離（Mallows distance）としても知られている。

これは最適輸送問題の解として定式化されており、モンジュ-カントロヴィッチ問題とも呼ばれる。また、離散的な要素の上で定義される場合、最小重み二部マッチング問題と等価である。

定義

確率分布 $P$, $Q$ に対し、EMDは以下のように定義される：

${\text{EMD}}(P,Q)=\inf \limits _{\gamma \in \Pi (P,Q)}\mathbb {E} _{(x,y)\sim \gamma }\left[d(x,y)\right]\,$

ここで $\Pi (P,Q)$ は、 $P$ および $Q$ を周辺分布とする結合分布全体の集合である。

カントロヴィッチ-ルビンシュタイン双対性を用いると、以下のようにも表せる：

${\text{EMD}}(P,Q)=\sup \limits _{\|f\|_{L}\leq 1}\,\mathbb {E} _{x\sim P}[f(x)]-\mathbb {E} _{y\sim Q}[f(y)]\,$

ここで上限は全ての1-リプシッツ連続関数 $f$ にわたって取られる（すなわち $\|\nabla f(x)\|\leq 1\quad \forall x$.）

シグネチャ間のEMD

一部の応用では、分布 ${\textstyle P}$を「シグネチャ」すなわち質量付きクラスタの集合として表現するのが便利である。たとえば： ${\textstyle P=\{(p_{1},w_{p1}),(p_{2},w_{p2}),...,(p_{m},w_{pm})\}}$ ${\textstyle Q=\{(q_{1},w_{q1}),(q_{2},w_{q2}),...,(q_{n},w_{qn})\}}$.

クラスタ ${\textstyle p_{i}}$ と ${\textstyle q_{j}}$の距離を ${\textstyle D=[d_{i,j}]}$ とすると、全体のコストを最小化するようなフロー ${\textstyle F=[f_{i,j}]}$ を求めて次のように定義する：

$\min \limits _{F}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}$

制約条件は：

$f_{i,j}\geq 0,1\leq i\leq m,1\leq j\leq n$

$\sum _{j=1}^{n}{f_{i,j}}\leq w_{pi},1\leq i\leq m$

$\sum _{i=1}^{m}{f_{i,j}}\leq w_{qj},1\leq j\leq n$

$\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}=\min \left\{\ \sum _{i=1}^{m}w_{pi},\quad \sum _{j=1}^{n}w_{qj}\ \right\}$

EMDは以下のように定義される：

${\text{EMD}}(P,Q)={\frac {\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}}}$

拡張と変種

質量が異なる場合

$P$ と $Q$ の全体質量が異なる場合、部分一致を許すことで対応できる。

以下のように定式化される：

${\text{EMD}}(P,Q)={\tfrac {1}{\min(w_{P},w_{Q})}}\inf \limits _{\gamma \in \Pi _{\geq }(P,Q)}\int d(x,y)\,\mathrm {d} \gamma (x,y)$

ここで $\Pi _{\geq }(P,Q)$ は、 $P$ および $Q$ 以上の測度を持つ結合測度全体。 また、土の「生成・消失」を許し、その際にペナルティコスト $\alpha$ を加えることで、真の距離関数を定義できる。

多分布間のEMD

EMDは2つ以上の分布に拡張することもできる。このとき、複数分布の「距離」は線形計画問題の最適解として定義され、Minkowski加法性と単調性を持つことが知られている。

EMDの計算

EMDは輸送問題として定式化され、最小費用流問題のアルゴリズム（たとえばネットワーク単体法）で解ける。

特別な場合として、1次元のヒストグラムにおけるEMDは以下のように効率的に計算できる：

${\begin{aligned}{\text{EMD}}_{0}&=0\\{\text{EMD}}_{i+1}&=P_{i}+{\text{EMD}}_{i}-Q_{i}\\{\text{Total Distance}}&=\sum _{i=0}^{n}|{\text{EMD}}_{i}|\end{aligned}}$

応用

EMDは画像検索における類似度計算や、パターン認識でのシグネチャ間の比較に用いられる。  

また、フローサイトメトリーなどのバイオマーカー比較にも応用されている。

外部リンク

• C code for the Earth Mover's Distance (archived here)
• Python implementation with references
• Python2 wrapper for the C implementation of the Earth Mover's Distance
• C++ and Matlab and Java wrappers code for the Earth Mover's Distance, especially efficient for thresholded ground distances
• Java implementation of a generic generator for evaluating large-scale Earth Mover's Distance based similarity analysis
• Demonstration of Minkowski additivity, convex monotonicity, and other properties of the Earth Movers distance