アースムーバー距離

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

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

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

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

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



ここで  は、 および  を周辺分布とする結合分布全体の集合である。

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



ここで上限は全ての1-リプシッツ連続関数  にわたって取られる（すなわち .）

 シグネチャ間のEMD 
一部の応用では、分布を「シグネチャ」すなわち質量付きクラスタの集合として表現するのが便利である。たとえば：  . 

クラスタ   との距離を  とすると、全体のコストを最小化するようなフロー  を求めて次のように定義する：



制約条件は：









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



 拡張と変種 

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

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



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

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

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

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



 応用 
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

Category:統計的距離
Category:数学に関する記事