EMD詳解及其應(yīng)用

EMD詳解及其應(yīng)用王駿一G20138497EMD，全稱EeathMovers'Distance，它是用來衡量兩個(gè)特征分布之間相似度的一個(gè)重要的度量，在我們的科研工作中起到了相當(dāng)重要的作用。EMD的前身——運(yùn)輸問題運(yùn)輸模型是指，設(shè)某種物資有m個(gè)產(chǎn)地A1,A2，…,Am，供應(yīng)量分別為a1，a2，…，am個(gè)單位；聯(lián)合供應(yīng)n個(gè)銷地B1，B2,…,Bn,需求量分別為b1，b2,…,bn個(gè)單位（總供應(yīng)量大于等于總需求量）。假設(shè)從產(chǎn)地Ai向銷地Bj運(yùn)輸一個(gè)單位物資的費(fèi)用為cij，怎樣調(diào)運(yùn)物資才能使運(yùn)輸費(fèi)用最少？記從產(chǎn)地Ai到銷地Bj的運(yùn)輸量為xij，則總的運(yùn)輸成本可記為：我們的目標(biāo)是求出S的最小值，即min（S）。運(yùn)輸問題表格EMD借用了運(yùn)輸問題求解的思路，它可以被理解為“從一種分布變換為另一種分布的最小代價(jià)”，它最早被Peleg，Werman和Rom介紹應(yīng)用于計(jì)算視覺問題。后來，人們將該流程移植到特征分布的比較中，把一個(gè)特征分布當(dāng)作“供貨商”，而另一個(gè)為“消費(fèi)商”。定義Cij為從第一個(gè)特征分布的第i個(gè)元素與第二個(gè)個(gè)特征分布的第j個(gè)元素之間的“距離”（Cij可以是任何距離的度量，應(yīng)根據(jù)當(dāng)前處理的問題靈活選擇）。再使用運(yùn)輸問題的算法找到最優(yōu)路徑矩陣，就得到兩個(gè)特征分布之間的EMD。設(shè)兩個(gè)區(qū)域RA和RB，可用區(qū)域內(nèi)某一特征信息的概率分布分別表征為:{(rA1,vA1),(rA2,vA2),...,(rAm,vAm)}{(rB1,vB1),(rB2,vB2),...,(rBn,vBn)}則區(qū)域RA和RB的EMD可以定義為:我們以這兩個(gè)集合為例：{'a','a','a','b','b','c','d','d','d','d'}和{'a','a','c','c','c','c','c','e','k','k'}，他們的概率密度分布圖依次為：根據(jù)概率密度分布圖，我們可以得到EMD轉(zhuǎn)化表格（如下圖）：EMD(str1,str2)=2*0+2*1+1*0+2*1+1*1+1*10+1*7=23我們稱EMD(str1,str2)=23為基本可行解，進(jìn)而，我們利用“表上作業(yè)法”求出最優(yōu)解：EMDmin(str1,str2)。EMD的優(yōu)點(diǎn)主要有以下幾個(gè)方面：(1)EMD度量巧妙地用“運(yùn)輸貨物”所需的最小代價(jià)表征特征分布之間的距離，而不是實(shí)際意義上的距離，因此避免了量化（連續(xù)值變?yōu)殡x散值）的過程，即避免了量化誤差的引入。(2)EMD是連續(xù)的，所以由特征分布的微小變化而引起的EMD的波動(dòng)也是微小的。因此，在保證可接受的性能的前提下，可在聚類后刪去權(quán)值很小的聚類中心，從而減少計(jì)算量，提高檢索效率。(3)根據(jù)EMD的定義，當(dāng)2個(gè)特征分布的總權(quán)重不相等時(shí)，為滿足可行性約束條件：總的需求量應(yīng)該小于總供貨商，將總權(quán)重較小的特征分布視為消費(fèi)商，將總權(quán)重較大的特征分布視為供貨商，再計(jì)算兩者之間的EMD。這樣便將EMD很自然地應(yīng)用于部分匹配，來比較不同階數(shù)或總權(quán)重不同的特征分布之間的相似性。由