Vzdálenost hybatelů Země - Earth movers distance - Wikipedia

Ve statistikách vzdálenost hybatelů Země (EMD) je míra vzdálenosti mezi dvěma rozdělení pravděpodobnosti přes regionD. V matematice se tomu říká „ Wassersteinova metrika. Neformálně, pokud jsou distribuce interpretovány jako dva různé způsoby hromadění určitého množství nečistot v celém regionu D, EMD jsou minimální náklady na přeměnu jedné hromádky na druhou; kde se předpokládá, že nákladem je množství nečistot přesunutých krát vzdálenost kterým se pohybuje.^[1]

Výše uvedená definice je platná pouze v případě, že obě distribuce mají stejný integrál (neformálně, pokud mají dvě hromady stejné množství nečistot), jako v normalizovaném histogramy nebo funkce hustoty pravděpodobnosti. V takovém případě je EMD ekvivalentní první Mallowsova vzdálenost nebo 1. Wassersteinova vzdálenost mezi oběma distribucemi.^[2][3]

Teorie

Předpokládejme, že máme řadu bodů ${ textstyle mathbb {R} ^ {d}}$ (dimenze ${ textstyle d}$). Namísto přiřazení jedné distribuce k sadě bodů je můžeme seskupit a reprezentovat množinu bodů z hlediska klastrů. Každý klastr je tedy jediným bodem ${ textstyle mathbb {R} ^ {d}}$ a o hmotnosti klastru rozhoduje zlomek distribuce přítomné v tomto klastru. Tato reprezentace distribuce sadou shluků se nazývá podpis. Dva podpisy mohou mít různé velikosti, například bimodální distribuce má kratší podpis (2 shluky) než složité. Jedna reprezentace klastru (průměr nebo režim v ${ textstyle mathbb {R} ^ {d}}$) lze v podpisu považovat za jeden prvek. Vzdálenost mezi každou z funkcí se nazývá jako pozemní vzdálenost.

Earth Mover's Distance lze formulovat a řešit jako a dopravní problém. Předpokládejme, že několik dodavatelů, z nichž každý má dané množství zboží, musí zásobovat několik spotřebitelů, z nichž každý má danou omezenou kapacitu. U každého páru dodavatel - spotřebitel jsou uvedeny náklady na přepravu jedné jednotky zboží. Přepravním problémem je pak najít nejméně nákladný tok zboží od dodavatelů ke spotřebitelům, který uspokojí poptávku spotřebitelů. Podobně zde problém transformuje jeden podpis (${ textový styl P}$) jinému(${ textstyle Q}$) s minimální odvedenou prací.

Předpokládejme ten podpis ${ textový styl P}$ má ${ textstyle m}$ klastry s ${ textstyle P = {(p_ {1}, w_ {p1}), (p_ {2}, w_ {p2}), ..., (p_ {m}, w_ {pm}) }}$, kde ${ textový styl p_ {i}}$ je zástupcem klastru a ${ textstyle w_ {pi}> 0}$ je hmotnost shluku. Podobně další podpis ${ textstyle Q = {(q_ {1}, w_ {q1}), (q_ {2}, w_ {q2}), ..., (q_ {n}, w_ {qn}) }}$ má ${ textstyle n}$ shluky. Nechat ${ textstyle D = [d_ {i, j}]}$ být pozemní vzdálenost mezi shluky ${ textový styl p_ {i}}$ a ${ textstyle q_ {j}}$.

Chceme najít tok ${ textstyle F = [f_ {i, j}]}$, s ${ textstyle f_ {i, j}}$ tok mezi ${ textový styl p_ {i}}$ a ${ textstyle q_ {j}}$, což minimalizuje celkové náklady.

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

s výhradou omezení:

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

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

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

${ displaystyle 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 }}$

Optimální průtok ${ textstyle F}$ je nalezen řešením tohoto problému lineární optimalizace. Vzdálenost zemského dopravce je definována jako práce normalizovaná celkovým tokem:

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

Rozšíření

Některé aplikace mohou vyžadovat srovnání distribucí s různými celkovými hmotnostmi. Jedním z přístupů je umožnit a částečná shoda, kde jsou nečistoty z nejhmotnější distribuce přeskupeny tak, aby byly nejméně masivní, a veškerá zbylá „špína“ je bez jakýchkoli nákladů zahozena. Podle tohoto přístupu EMD již není skutečnou vzdáleností mezi distribucemi.

Dalším přístupem je umožnit vytvoření nebo zničení hmoty na globální a / nebo místní úrovni jako alternativu k dopravě, avšak s nákladovou pokutou. V takovém případě je třeba určit skutečný parametr σ, poměr mezi náklady na vytvoření nebo zničení jedné jednotky „špíny“ a náklady na její dopravu o jednotku vzdálenosti. To odpovídá minimalizaci součtu nákladů na pohyb Země plus σ krát L¹ vzdálenost mezi přeskupenou hromádkou a druhým rozdělením.

Notačně, pokud ${ displaystyle pi: P až Q}$ je částečná funkce což je bijekce na podmnožiny ${ displaystyle P ' podmnožina P}$ a ${ displaystyle Q ' podmnožina Q}$, pak se člověk zajímá o funkci vzdálenosti

${ displaystyle | P-Q | _ { pi} = | P setminus P '| + | Q setminus Q' |}$

kde ${ displaystyle P setminus P '}$ označuje nastavit mínus. Tady, ${ displaystyle P '}$ bude částí Země, která byla přesunuta; tím pádem ${ displaystyle P setminus P '}$ bude část, která se nepohybuje, a ${ displaystyle | P setminus P '|}$ velikost hromádky se nepohnula. Podle symetrie jeden uvažuje ${ displaystyle Q ' podmnožina Q}$ jako hromada v cíli, ze které se tam „dostali“ P, ve srovnání s celkem Q že my chci tam být. Formálně tato vzdálenost udává, kolik injekční korespondence se liší od izomorfismus.

EMD lze přirozeně rozšířit na případ, kdy se porovnávají více než dvě distribuce. V tomto případě je „vzdálenost“ mezi mnoha distribucemi definována jako optimální hodnota lineárního programu. Tento zobecněný EMD může být vypočítán přesně pomocí chamtivého algoritmu a výsledná funkce se ukázala být Minkowského přísada a konvexní monotónní. ^[4]

Výpočet EMD

EMD lze vypočítat řešením instance dopravní problém pomocí libovolného algoritmu pro problém s minimálními náklady, např. the síťový simplexní algoritmus.

Maďarský algoritmus lze použít k získání řešení, pokud je doména D je množina {0, 1}. Pokud je doména integrální, lze ji přeložit pro stejný algoritmus reprezentací integrálních košů jako více binárních košů.

Jako zvláštní případ, pokud D je jednorozměrné pole „zásobníků“, EMD lze efektivně vypočítat skenováním pole a sledováním toho, kolik nečistot je třeba přepravit mezi po sobě následujícími zásobníky:

${ displaystyle { begin {array} {rl} { text {EMD}} _ {0} & = 0 { text {EMD}} _ {i + 1} & = P_ {i} + { text {EMD}} _ {i} -Q_ {i} { text {Celková vzdálenost}} & = sum | { text {EMD}} _ {i} | end {pole}}}$

Analýza podobnosti založená na EMD

Analýza podobnosti založená na EMD (EMDSA) je v mnoha případech důležitým a účinným nástrojem načítání multimediálních informací^[5] a rozpoznávání vzorů^[6] aplikace. Výpočtové náklady na EMD jsou však superkubické k počtu „zásobníků“, jimž je dán libovolný „D“. Efektivní a škálovatelné výpočetní techniky EMD pro data ve velkém měřítku byly zkoumány pomocí MapReduce,^[7][8] stejně jako hromadně synchronní paralelně a odolná distribuovaná datová sada.^[9]

Aplikace

Počáteční aplikací EMD v počítačové vědě bylo srovnání dvou stupně šedi obrázky, které se mohou lišit kvůli dithering, rozmazání nebo místní deformace.^[10] V tomto případě je oblast doménou obrazu a celkové množství světla (nebo inkoustu) je „špína“, kterou je třeba přeskupit.

EMD je široce používán v načítání obrázků podle obsahu vypočítat vzdálenosti mezi barevné histogramy ze dvou digitální obrázky.^{[Citace je zapotřebí ]} V tomto případě je region RGB barevná kostka a každý obrazový pixel je součástí „špíny“. Stejnou techniku ​​lze použít pro jakoukoli jinou kvantitativní pixel atribut, například jas, spád, zdánlivý pohyb v snímek videa, atd..

Obecněji se EMD používá v rozpoznávání vzorů porovnat obecné souhrny nebo náhradní datové záznamy s názvem podpisy. Typický podpis se skládá ze seznamu párů ((X₁,m₁), ... (X_n,m_n)), kde každý X_i je určitá „vlastnost“ (např. barva obrázku, písmeno v textu atd.) a m_i je „hromadný“ (kolikrát se tato vlastnost v záznamu vyskytne). Alternativně, X_i může být těžiště a datový klastr, a m_i počet entit v daném klastru. Chcete-li porovnat dva takové podpisy s EMD, musíte definovat vzdálenost mezi prvky, která se interpretuje jako cena přeměny jednotkové hmotnosti jednoho prvku na jednotkovou hmotnost druhého. EMD mezi dvěma podpisy je pak minimální cena přeměny jednoho z nich na druhý.

Analýza EMD byla použita pro kvantifikaci vícerozměrných změn v biomarkery měřeno průtoková cytometrie, s potenciálními aplikacemi na jiné technologie, které hlásí distribuce měření.^[11]

Dějiny

Koncept byl poprvé představen Gaspard Monge v roce 1781,^[12] v kontextu teorie dopravy. Použití EMD jako měřítka vzdálenosti pro monochromatické obrazy popsali v roce 1989 S. Peleg, M. Werman a H. Rom.^[10] Název „vzdálenost pohybujících se Země“ navrhl J. Stolfi v roce 1994,^[13] a byl použit v tisku v roce 1998 Y. Rubnerem, C. Tomasi a L. G. Guibas.^[14]

Reference

externí odkazy

• C kód pro vzdálenost pohybujícího se Země
• Implementace Pythonu s odkazy
• Obálka Python2 pro implementaci C Země Mover's Distance
• Obálky C ++ a Matlab a Java kódují vzdálenost Earth Mover's Distance, zvláště efektivní pro prahové pozemní vzdálenosti
• Implementace generického generátoru v jazyce Java pro vyhodnocení rozsáhlé podobnostní analýzy založené na vzdálenosti Země