Analýza hlavních komponent jádra - Kernel principal component analysis

V oblasti statistika s více proměnnými, analýza hlavních komponent jádra (PCA jádra)^[1]je příponou analýza hlavních komponent (PCA) pomocí technik metody jádra. Pomocí jádra se původně lineární operace PCA provádějí v a reprodukce jádra Hilbertova prostoru.

Pozadí: Lineární PCA

Připomeňme, že konvenční PCA pracuje na datech zaměřených na nulu; to je

{displaystyle {frac {1} {N}} součet _ {i = 1} ^ {N} mathbf {x} _ {i} = mathbf {0}}

,

kde ${displaystyle mathbf {x} _ {i}}$ je vektor jednoho z ${displaystyle N}$ vícerozměrná pozorování. Funguje diagonalizací kovarianční matice,

{displaystyle C = {frac {1} {N}} součet _ {i = 1} ^ {N} mathbf {x} _ {i} mathbf {x} _ {i} ^ {op}}

jinými slovy, dává vlastní složení kovarianční matice:

{displaystyle lambda mathbf {v} = Cmathbf {v}}

které lze přepsat jako

{displaystyle lambda mathbf {x} _ {i} ^ {op} mathbf {v} = mathbf {x} _ {i} ^ {op} Cmathbf {v} quad {extrm {for}} ~ i = 1, ldots, N}

.^[2]

(Viz také: Kovarianční matice jako lineární operátor )

Zavedení jádra do PCA

Chcete-li pochopit užitečnost jádra PCA, zejména pro klastrování, pozorujte to, zatímco N body obecně nemohou být lineárně oddělené v ${displaystyle d$ rozměry, mohou Skoro pořád být lineárně odděleny v ${displaystyle dgeq N}$ rozměry. To je dané N body, ${displaystyle mathbf {x} _ {i}}$ , pokud je namapujeme na N-rozměrný prostor s

{displaystyle Phi (mathbf {x} _ {i})}

kde

{displaystyle Phi: mathbb {R} ^ {d} o mathbb {R} ^ {N}}

,

je snadné postavit a nadrovina který rozděluje body do libovolných shluků. Samozřejmě, tohle ${displaystyle Phi}$ vytváří lineárně nezávislé vektory, takže neexistuje kovariance, na které by bylo možné provést vlastní složení výslovně jako bychom to udělali v lineárním PCA.

Místo toho je v jádru PCA netriviální, libovolný ${displaystyle Phi}$ funkce je „zvolena“, která se nikdy výslovně nevypočítává, což umožňuje použít velmi vysoce dimenzionální ${displaystyle Phi}$ Pokud nikdy nebudeme muset skutečně vyhodnotit data v tomto prostoru. Protože se obecně snažíme vyhnout se práci v ${displaystyle Phi}$ -prostor, který budeme nazývat 'prostor funkcí', můžeme vytvořit jádro N-by-N

{displaystyle K = k (mathbf {x}, mathbf {y}) = (Phi (mathbf {x}), Phi (mathbf {y})) = Phi (mathbf {x}) ^ {T} Phi (mathbf { y})}

což představuje vnitřní produktový prostor (viz Gramianova matice ) jinak neřešitelného prostoru funkcí. Duální forma, která vzniká při vytváření jádra, nám umožňuje matematicky formulovat verzi PCA, ve které nikdy vlastně neřešíme vlastní vektory a vlastní hodnoty kovarianční matice v ${displaystyle Phi (mathbf {x})}$ -prostor (viz Jádrový trik ). N-prvky v každém sloupci K. představují bodový součin jednoho bodu transformovaných dat vzhledem ke všem transformovaným bodům (N bodů). V následujícím příkladu jsou uvedena některá známá jádra.

Protože nikdy nepracujeme přímo v prostoru funkcí, je formulace jádra PCA omezena tím, že nepočítá samotné hlavní komponenty, ale projekce našich dat na tyto komponenty. Vyhodnotit projekci z bodu v prostoru prvků ${displaystyle Phi (mathbf {x})}$ na k-tu hlavní složku ${displaystyle V ^ {k}}$ (kde horní index k znamená složku k, ne mocniny k)

{displaystyle {mathbf {V} ^ {k}} ^ {T} Phi (mathbf {x}) = vlevo (součet _ {i = 1} ^ {N} mathbf {a_ {i}} ^ {k} Phi ( mathbf {x_ {i}}) ight) ^ {T} Phi (mathbf {x})}

Poznamenáváme to ${displaystyle Phi (mathbf {x_ {i}}) ^ {T} Phi (mathbf {x})}$ označuje tečkovaný produkt, což jsou jednoduše prvky jádra ${displaystyle K}$ . Zdá se, že zbývá jen vypočítat a normalizovat ${displaystyle mathbf {a_ {i}} ^ {k}}$ , což lze provést řešením vlastní rovnice

{displaystyle Nlambda mathbf {a} = Kmathbf {a}}

kde N je počet datových bodů v sadě a ${displaystyle lambda}$ a ${displaystyle mathbf {a}}$ jsou vlastní hodnoty a vlastní vektory K. Pak normalizovat vlastní vektory ${displaystyle mathbf {a} ^ {k}}$ To požadujeme

{displaystyle 1 = (mathbf {V} ^ {k}) ^ {T} mathbf {V} ^ {k}}

Je třeba dávat pozor na to, zda, či nikoli ${displaystyle x}$ má v původním prostoru nulovou střední hodnotu, není zaručeno, že bude vystředěn v prostoru funkcí (který nikdy výslovně nepočítáme). Jelikož k provedení efektivní analýzy hlavních komponent jsou vyžadována data se středem,centralizovat „K stát se ${displaystyle K '}$

{displaystyle K '= K-mathbf {1_ {N}} K-Kmathbf {1_ {N}} + mathbf {1_ {N}} Kmathbf {1_ {N}}}

kde ${displaystyle mathbf {1_ {N}}}$ označuje matici N-by-N, pro kterou má každý prvek hodnotu ${displaystyle 1 / N}$ . Používáme ${displaystyle K '}$ provést výše popsaný algoritmus jádra PCA.

Zde by měla být znázorněna jedna výhrada jádra PCA. V lineárním PCA můžeme použít vlastní čísla k seřazení vlastních vektorů na základě toho, jak velká část variace dat je zachycena každou hlavní komponentou. To je užitečné pro snížení dimenze dat a mohlo by to být také aplikováno na KPCA. V praxi však existují případy, kdy jsou všechny varianty dat stejné. To je obvykle způsobeno nesprávnou volbou měřítka jádra.

Velké datové sady

V praxi vede velká sada dat k velkému K a ukládání K se může stát problémem. Jedním ze způsobů, jak to vyřešit, je provést klastrování na datové sadě a naplnit jádro prostředky těchto klastrů. Protože i tato metoda může přinést relativně velké K, je běžné vypočítat pouze horní P vlastních čísel a vlastní vektory vlastních čísel se počítají tímto způsobem.

Příklad

Vstupní body před jádrem PCA

Zvažte tři soustředná mračna bodů (zobrazeno); k identifikaci těchto skupin bychom chtěli použít jádro PCA. Barva bodů nepředstavuje informace zahrnuté v algoritmu, ale pouze ukazuje, jak transformace přemístí datové body.

Nejprve zvažte jádro

{displaystyle k ({oldsymbol {x}}, {oldsymbol {y}}) = ({oldsymbol {x}} ^ {mathrm {T}} {oldsymbol {y}} + 1) ^ {2}}

Aplikováním tohoto na jádro PCA získáte další obrázek.

Výstup po PCA jádra s

{displaystyle k ({oldsymbol {x}}, {oldsymbol {y}}) = ({oldsymbol {x}} ^ {mathrm {T}} {oldsymbol {y}} + 1) ^ {2}}

. Tyto tři skupiny lze odlišit pouze pomocí první komponenty.

Nyní zvažte Gaussovo jádro:

{displaystyle k ({oldsymbol {x}}, {oldsymbol {y}}) = e ^ {frac {- || {oldsymbol {x}} - {oldsymbol {y}} || ^ {2}} {2sigma ^ {2}}},}

To znamená, že toto jádro je míra blízkosti, rovná se 1, když se body shodují, a rovná se 0 v nekonečnu.

Výstup po jádře PCA, s a Gaussian jádro.

Zejména si všimněte, že první hlavní komponenta stačí k rozlišení tří různých skupin, což je nemožné pouze s lineárním PCA, protože lineární PCA pracuje pouze v daném (v tomto případě dvojrozměrném) prostoru, ve kterém jsou tyto soustředné mračna bodů není lineárně oddělitelné.

Aplikace

Bylo prokázáno, že jádro PCA je užitečné pro detekci novosti^[3] a odstranění šumu obrazu.^[4]

Viz také

Reference

^ Schölkopf, Bernhard (1998). Msgstr "Nelineární analýza komponent jako problém s vlastním číslem jádra". Neurální výpočet. 10 (5): 1299–1319. CiteSeerX 10.1.1.100.3636. doi:10.1162/089976698300017467. S2CID 6674407.
^ Nelineární analýza komponent jako problém s vlastním číslem jádra (technická zpráva)
^ Hoffmann, Heiko (2007). „PCA jádra pro detekci novinek“. Rozpoznávání vzorů. 40 (3): 863–874. doi:10.1016 / j.patcog.2006.07.009.
^ PCA jádra a odstranění šumu v prostorech funkcí. NIPS, 1999

[1] Schölkopf, Bernhard (1998). Msgstr "Nelineární analýza komponent jako problém s vlastním číslem jádra". Neurální výpočet. 10 (5): 1299–1319. CiteSeerX 10.1.1.100.3636. doi:10.1162/089976698300017467. S2CID 6674407.

[2] Nelineární analýza komponent jako problém s vlastním číslem jádra (technická zpráva)

[3] Hoffmann, Heiko (2007). „PCA jádra pro detekci novinek“. Rozpoznávání vzorů. 40 (3): 863–874. doi:10.1016 / j.patcog.2006.07.009.

[4] PCA jádra a odstranění šumu v prostorech funkcí. NIPS, 1999

[1]

[2]

[3]

[4]