Difúzní mapa - Diffusion map

Difúzní mapy je snížení rozměrů nebo extrakce funkcí algoritmus zavedený Coifman a Lafon[1][2][3][4] který počítá rodinu vložení souboru dat do euklidovského prostoru (často nízkodimenzionálního), jehož souřadnice lze vypočítat z vlastních vektorů a vlastních hodnot difuzního operátoru na datech. Euklidovská vzdálenost mezi body ve vloženém prostoru se rovná „difúzní vzdálenosti“ mezi distribucemi pravděpodobnosti se středem v těchto bodech. Liší se od lineárních metod redukce rozměrů, jako je analýza hlavních komponent (PCA) a vícerozměrné měřítko (MDS), difúzní mapy jsou součástí rodiny nelineární redukce rozměrů metody, které se zaměřují na objevování podkladů potrubí ze kterých byla data odebrána. Integrací místních podobností v různých měřítcích poskytují difúzní mapy globální popis datové sady. Ve srovnání s jinými metodami je algoritmus difuzní mapy robustní vůči rušení šumem a výpočetně levný.
Definice difúzních map
Následující [3] a,[5] difúzní mapy lze definovat ve čtyřech krocích.
Konektivita
Difúzní mapy využívají vztah mezi difúze tepla a náhodná procházka Markovův řetězec. Základní pozorování spočívá v tom, že pokud provedeme náhodnou procházku po datech, je pravděpodobnější chůze do blízkého datového bodu než chůze do jiného, který je daleko. Nechat být změřte prostor, kde je soubor dat a představuje rozdělení bodů na .
Na základě toho je konektivita mezi dvěma datovými body, a , lze definovat jako pravděpodobnost chůze od na v jednom kroku náhodné chůze. Tato pravděpodobnost je obvykle specifikována jako funkce jádra dvou bodů: . Například populární gaussovské jádro:
Obecněji, jádro funkce má následující vlastnosti
( je symetrický)
( je zachování pozitivity).
Jádro představuje předchozí definici místní geometrie souboru dat. Vzhledem k tomu, že dané jádro zachytí specifickou vlastnost datové sady, měla by se jeho volba řídit aplikací, kterou má člověk na mysli. To je zásadní rozdíl u metod, jako jsou analýza hlavních komponent, kde jsou zohledněny korelace mezi všemi datovými body najednou.
Dáno , pak můžeme postavit reverzibilní Markovův řetězec (proces známý jako normalizovaná grafová laplaciánská konstrukce):
a definovat:
Ačkoli nové normalizované jádro nedědí symetrickou vlastnost, dědí vlastnost zachovávající pozitivitu a získává vlastnost zachování:
Difúzní proces
Z můžeme zkonstruovat přechodovou matici Markovova řetězce () zapnuto . Jinými slovy, představuje jednostupňovou pravděpodobnost přechodu z na , a dává přechodovou matici t-kroku.
Definujeme difúzní matici (je to také verze grafu Laplaciánská matice )
Poté definujeme nové jádro
nebo ekvivalentně
kde D je diagonální matice a
Aplikujeme graf Laplacian normalizace na toto nové jádro:
kde je diagonální matice a
Jednou z hlavních myšlenek difúzního rámce je, že běh řetězce vpřed v čase (přičemž stále větší a větší pravomoci ) odhaluje geometrickou strukturu ve větším a větším měřítku (proces difúze). Konkrétně pojem a shluk v datovém souboru je kvantifikován jako region, ve kterém je pravděpodobnost úniku z této oblasti nízká (do určité doby t). Proto t slouží nejen jako časový parametr, ale má také dvojí roli parametru měřítka.
Vlastní složení matice výnosy
kde je posloupnost vlastních čísel a a jsou biortogonální pravé a levé vlastní vektory. Kvůli rozpadu vlastních čísel spektra je k dosažení dané relativní přesnosti v tomto součtu zapotřebí pouze několik výrazů.
Parametr a operátor šíření
Důvod zavedení normalizačního kroku zahrnuje je vyladit vliv hustoty datového bodu na nekonečně malý přechod difúze. V některých aplikacích vzorkování dat obecně nesouvisí s geometrií potrubí, které bychom chtěli popsat. V tomto případě můžeme nastavit a difúzní operátor aproximuje operátor Laplace – Beltrami. Poté obnovíme Riemannovu geometrii datové sady bez ohledu na rozdělení bodů. K popisu dlouhodobého chování bodového rozdělení soustavy stochastických diferenciálních rovnic můžeme použít a výsledný Markovův řetězec se blíží Fokker – Planckova difúze. S , redukuje se na klasický graf laplaciánské normalizace.
Difúzní vzdálenost
Difúzní vzdálenost v čase mezi dvěma body lze měřit jako podobnost dvou bodů v pozorovacím prostoru s konektivitou mezi nimi. Je to dáno
kde je stacionární distribuce Markovova řetězce, daná prvním levým vlastním vektorem z . Výslovně:
Intuitivně, je malé, pokud je spojeno velké množství krátkých cest a . Na základě naší předchozí diskuse je s difuzní vzdáleností spojeno několik zajímavých funkcí slouží také jako parametr měřítka:
- Body jsou blíže v daném měřítku (jak je uvedeno v ) pokud jsou v grafu vysoce propojené, zdůrazňují proto koncept shluku.
- Tato vzdálenost je odolná vůči šumu, protože vzdálenost mezi dvěma body závisí na všech možných délkových drahách mezi body.
- Z hlediska strojového učení vzdálenost zohledňuje všechny propojené důkazy na , což nám umožňuje dospět k závěru, že tato vzdálenost je vhodná pro návrh odvozovacích algoritmů na základě většiny převahy.[3]
Proces difúze a nízkodimenzionální vkládání
Difúzní vzdálenost lze vypočítat pomocí vlastních vektorů pomocí
Vlastní vektory lze tedy použít jako novou sadu souřadnic pro data. Difúzní mapa je definována jako:
Kvůli rozpadu spektra stačí použít pouze první k vlastní vektory a vlastní hodnoty. Dostaneme tedy difúzní mapu z původních dat do a k-dimenzionální prostor, který je vložen do původního prostoru.
v [6] je prokázáno, že
takže euklidovská vzdálenost v difuzních souřadnicích se blíží difuzní vzdálenosti.
Algoritmus
Základní rámec algoritmu difuzní mapy je následující:
Krok 1. Vzhledem k matici podobnosti L.
Krok 2. Normalizujte matici podle parametru : .
Krok 3. Vytvořte normalizovanou matici .
Krok 4. Vypočítejte k největší vlastní čísla a odpovídající vlastní vektory.
Krok 5. Použijte difúzní mapu k získání vložení .
aplikace
V novinách[6] Nadler et. al. ukázal, jak navrhnout jádro, které reprodukuje difúzi vyvolanou a Fokker-Planckova rovnice. Rovněž vysvětlili, že když se data přiblíží potrubí, lze obnovit geometrii tohoto potrubí výpočtem aproximace Operátor Laplace – Beltrami. Tento výpočet je zcela necitlivý na distribuci bodů, a proto poskytuje oddělení statistik a geometrie dat. Vzhledem k tomu, že difúzní mapy poskytují globální popis datové sady, může měřit vzdálenosti mezi dvojicí vzorkových bodů v potrubí, ve kterém jsou data vložena. Mezi aplikace založené na difúzních mapách patří rozpoznávání obličejů,[7] spektrální shlukování, nízkodimenzionální reprezentace obrazů, segmentace obrazů,[8] Segmentace 3D modelu,[9] ověření mluvčího[10] a identifikace,[11] vzorkování na rozdělovačích potrubí, detekce anomálií,[12][13] malování obrazu,[14] a tak dále.
Viz také
Reference
- ^ Coifman, R.R .; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, S W (2005). „Geometrické difúze jako nástroj pro harmonickou analýzu a definici struktury dat: Difúzní mapy“. PNAS. 102 (21): 7426–7431. Bibcode:2005PNAS..102,7426C. doi:10.1073 / pnas.0500334102. PMC 1140422. PMID 15899970.
- ^ Coifman, R.R .; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, S W (2005). „Geometrické difúze jako nástroj pro harmonickou analýzu a definici struktury dat: metody s více měřítky“. PNAS. 102 (21): 7432–7437. Bibcode:2005PNAS..102,7432C. doi:10.1073 / pnas.0500896102. PMC 1140426. PMID 15899969.
- ^ A b C Coifman, R.R .; S. Lafon. (2006). "Difúzní mapy". Aplikovaná a výpočetní harmonická analýza. 21: 5–30. doi:10.1016 / j.acha.2006.04.006.
- ^ Lafon, S. S. (2004). Difúzní mapy a geometrické harmonické (PDF) (PhD). Univerzita Yale.
- ^ De la Porte, J .; Herbst, B M; Hereman, W; Van der Walt, S J (2008). "Úvod do difúzních map". Sborník devatenáctého výročního sympozia Jihoafrické asociace pro rozpoznávání vzorů (PRASA). CiteSeerX 10.1.1.309.674.
- ^ A b Nadler, Boaz; Stéphane Lafon; Ronald R. Coifman; Ioannis G. Kevrekidis (2005). „Difúzní mapy, spektrální shlukování a vlastní funkce operátorů Fokker – Planck“ (PDF). Pokroky v systémech zpracování neurálních informací. 18. arXiv:matematika / 0506090. Bibcode:Matematika 2005 ... 6090N.
- ^ Barkan, Oren; Weill, Jonathan; Vlk, Lior; Aronowitz, Hagai. „Rychlé rozpoznávání tváře ve vysokém dimenzionálním vektoru“ (PDF). Sborník mezinárodní konference IEEE o počítačovém vidění 2013: 1960–1967.
- ^ Zeev, Farbman; Fattal Raanan; Lischinski Dani (2010). Msgstr "Difúzní mapy pro editaci obrazu podle hran". ACM Trans. Graf. 29 (6): 145:1–145:10. doi:10.1145/1882261.1866171.
- ^ Oana, Sidi; van Kaick, Oliver; Kleiman, Yanir; Zhang, Hao; Cohen-Or, Daniel (2011). Neregistrovaná společná segmentace sady tvarů pomocí spektrálního shlukování deskriptoru a prostoru (PDF). Transakce ACM v grafice.
- ^ Barkan, Oren; Aronowitz, Hagai (2013). „Difúzní mapy pro ověření reproduktorů na základě PLDA“ (PDF). Sborník mezinárodní konference IEEE o akustice, řeči a zpracování signálu (ICASSP): 7639–7643.
- ^ Michalevskij, Yan; Talmon, Ronen; Cohen, Izrael (2011). „Identifikace reproduktoru pomocí difúzních map“ (PDF). Citovat deník vyžaduje
| deník =
(Pomoc) - ^ Mishne, Gal; Cohen, Izrael (2013). "Detekce víceúrovňových anomálií pomocí difúzních map". Vybraná témata IEEE ve zpracování signálu. 7 (1): 111–123. Bibcode:2013ISTSP ... 7..111M. doi:10.1109 / jstsp.2012.2232279. S2CID 1954466.
- ^ Shabat, Gil; Segev, David; Averbuch, Amir (01.01.2018). „Odhalování neznámých neznámých ve velkých datech finančních služeb pomocí nekontrolovaných metodik: současné a budoucí trendy“. Workshop KDD 2017 o detekci anomálií ve financích. 71: 8–19.
- ^ Gepshtein, Shai; Keller, Yosi (2013). "Dokončení obrazu pomocí difúzních map a spektrální relaxace". Transakce IEEE na zpracování obrazu. 22 (8): 2983–2994. Bibcode:2013ITIP ... 22.2983G. doi:10.1109 / tip.2013.2237916. PMID 23322762. S2CID 14375333.