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

1、EMD詳解及其應(yīng)用王駿一G20138497EMD,全稱Eeath Movers Distance,它是用來衡量兩個(gè)特征分布 之間相似度的一個(gè)重要的度量，在我們的科研工作中起到了相當(dāng)重要 的作用。EMD的前身運(yùn)輸問題運(yùn)輸模型是指，設(shè)某種物資有m個(gè)產(chǎn)地A1,A2,Am，供應(yīng)量 分別為a，a，a個(gè)單位；聯(lián)合供應(yīng)n個(gè)銷地B，B ,B ,需求12m12 n量分別為服b2,bn個(gè)單位（總供應(yīng)量大于等于總需求量）。假設(shè)從 產(chǎn)地Ai向銷地Bj運(yùn)輸一個(gè)單位物資的費(fèi)用為c怎樣調(diào)運(yùn)物資才能 使運(yùn)輸費(fèi)用最少？記從產(chǎn)地Ai到銷地的運(yùn)輸量為x則總的運(yùn)輸成本可記為：S = c xxij iji=1，j=i我們的日標(biāo)是求出S

2、的最小值，即min （S）。產(chǎn)地（產(chǎn)量） 銷地、 （銷量）、AJ80）A2 （50）A3（30）BJ60）X11（C11）X21（C21）X31（C31）B2（40）x12（c12）X22（C22）X32（C32）B3（60）X13（C13）X23（C23）X33（C33）運(yùn)輸問題表格EMD借用了運(yùn)輸問題求解的思路，它可以被理解為“從一種分 布變換為另一種分布的最小代價(jià)，它最早被Peleg，Werman和Rom 介紹應(yīng)用于計(jì)算視覺問題。后來，人們將該流程移植到特征分布的比較中，把一個(gè)特征分布 當(dāng)作“供貨商”，而另一個(gè)為“消費(fèi)商”。供貨商一C1消費(fèi)商特征分布P1 CT特征分布?2定義Cy為從第一

3、個(gè)特征分布的第i個(gè)元素與第二個(gè)個(gè)特征分布 的第j個(gè)元素之間的“距離-(Cij可以是任何距離的度量，應(yīng)根據(jù)當(dāng)前 處理的問題靈活選擇)。再使用運(yùn)輸問題的算法找到最優(yōu)路徑矩陣， 就得到兩個(gè)特征分布之間的EMD。特征分布耳7供貨商特征分布P2 T消費(fèi)商概率分布直方圖T貨物設(shè)兩個(gè)區(qū)域RA和RB，可用區(qū)域內(nèi)某一特征信息的概率分布分別表征為：(rA1,vA1),(rA2,vA2),.,(rAm,vAm )(rB1,vB1),(rB2,vB2),.,(rBn ,vBn )則區(qū)域RA和RB的EMD可以定義為:EMD(Ra, Rb) = min /)d(八j) 旗m 2n f (i,j) i=1 j =1f (i

4、, j) 0,1 i m,1 j nS.T.qn 1 f (i, j) vAi,1 i m” f (i, j) vBj,1 j nZm Zn f (i, j) = min(Em v Zn vj i=1 jTi=1 , j=1 可我們以這兩個(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)化表格（如下圖）:strlstr2 J-a(3)b(2)c(l)da(2)xaa(0)、ba（1）XcaXdac(5)XacXbc(1 )Xcc(O)Xdc(1)e(l)、ae(4)Xbe(3)XceX

5、de(1)k(2)xak(10)Xbk(9)Xck(8)XdkEMD(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è)方面：EMD度量巧妙地用“運(yùn)輸貨物”所需的最小代價(jià)表征特征分 布之間的距離，而不是實(shí)際意義上的距離，因此避免了量化(連續(xù)值 變?yōu)殡x散值)的過程，即避免了量化誤差的引入。EMD是連續(xù)的，所以由特征分布的微小變化而引起的EMD 的波動(dòng)也是微小的。因此，在保證可接受的性能的前提下，可在聚類 后刪去權(quán)值很小的聚類中心，從而減少計(jì)算量，提高檢索效率。根據(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)重不同的特征分布之