Kernel hoofdcomponentanalyse

Op het gebied van multivariate statistieken, Kernel Principal Component Analysis (Kernel PCA)^[1] is een uitbreiding van Hoofdcomponentanalyse (PCA) met behulp van technieken van kernelmethoden.Met behulp van een kernel worden de oorspronkelijk lineaire bewerkingen van PCA uitgevoerd in een Reproduceren van kernel Hilbert -ruimte.

Achtergrond: Lineaire PCA

Bedenk dat conventionele PCA werkt op nul-gecentreerde gegevens;dat is,

{\ displayStyle {\ frac {1} {n}} \ sum _ {i = 1}^{n} \ mathbf {x} _ {i} = \ mathbf {0}}

,

waar ${\ DisplayStyle \ Mathbf {x} _ {i}}$ is een van de ${\ displaystyle n}$ multivariate observaties.Het werkt door de covariantiematrix,,

{\ displaystyle c = {\ frac {1} {n}} \ sum _ {i = 1}^{n} \ mathbf {x} _ {i} \ mathbf {x} _ {i}^{\ top}}

Met andere woorden, het geeft een eigendecompositie van de covariantiematrix:

{\ DisplayStyle \ Lambda \ Mathbf {v} = C \ Mathbf {v}}

die kunnen worden herschreven als

{\ displaystyle \ lambda \ mathbf {x} _ {i}^{\ top} \ mathbf {v} = \ mathbf {x} _ {i}^{\ top} c \ mathbf {v} \ quad {\ textrm{voor}} ~ i = 1, \ ldots, n}

.^[2]

(Zie ook: Covariantiematrix als lineaire operator))

Introductie van de kernel tot PCA

Om het nut van kernel PCA te begrijpen, met name voor clustering, merken dat, terwijl N punten kunnen in het algemeen niet zijn lineair gescheiden in ${\ displaystyle d <n}$ afmetingen, ze kunnen bijna altijd lineair gescheiden zijn in ${\ displaystyle d \ geq n}$ dimensies.Dat wil zeggen, gegeven N punten, ${\ DisplayStyle \ Mathbf {x} _ {i}}$ , als we ze toewijzen aan een N-dimensionale ruimte met

{\ DisplayStyle \ Phi (\ Mathbf {x} _ {i})}

waar

{\ displaystyle \ phi: \ mathbb {r} ^{d} \ to \ mathbb {r} ^{n}}

,

het is gemakkelijk om een hyperplane Dat verdeelt de punten in willekeurige clusters.Natuurlijk dit ${\ DisplayStyle \ Phi}$ Creëert lineair onafhankelijke vectoren, dus er is geen covariantie om eigendecompositie uit te voeren uitdrukkelijk Zoals we zouden doen in lineaire PCA.

In plaats daarvan, in kernel PCA, een niet-triviaal, willekeurig ${\ DisplayStyle \ Phi}$ functie is 'gekozen' die nooit expliciet wordt berekend, waardoor de mogelijkheid kan worden gebruikt om zeer hoog-dimensionaal te gebruiken ${\ DisplayStyle \ Phi}$ als we de gegevens in die ruimte nooit daadwerkelijk hoeven te evalueren.Omdat we over het algemeen proberen te voorkomen dat we in de ${\ DisplayStyle \ Phi}$ -ruimte, die we de 'Feature Space' zullen noemen, kunnen we de n-n-n-kernel maken

{\ displaystyle k = k (\ mathbf {x}, \ mathbf {y}) = (\ phi (\ mathbf {x}), \ phi (\ mathbf {y})) = \ phi (\ mathbf {x})^{T} \ phi (\ mathbf {y})}

die de innerlijke productruimte vertegenwoordigt (zie Gramische matrix) van de anders onhandelbare kenmerkruimte.De dubbele vorm die ontstaat bij het creëren van een kernel stelt ons in staat om een versie van PCA wiskundig te formuleren waarin we de eigenvectoren en eigenwaarden van de covariantiematrix in de covariantiematrix nooit oplossen in de ${\ DisplayStyle \ Phi (\ Mathbf {x})}$ -ruimte (zie Kerneltruc).De N-elementen in elke kolom van K Vertegenwoordig het puntproduct van één punt van de getransformeerde gegevens met betrekking tot alle getransformeerde punten (n punten).Sommige bekende kernels worden in het onderstaande voorbeeld getoond.

Omdat we nooit rechtstreeks in de speelruimte werken, is de kernelformulatie van PCA beperkt omdat het niet de belangrijkste componenten zelf berekent, maar de projecties van onze gegevens op die componenten.Om de projectie te evalueren vanuit een punt in de speelruimte ${\ DisplayStyle \ Phi (\ Mathbf {x})}$ op de KTH -hoofdcomponent ${\ displaystyle v^{k}}$ (waar SuperScript K de component K betekent, geen krachten van K)

{\ displayStyle {\ Mathbf {v}^{k}}^{t} \ phi (\ mathbf {x}) = \ left (\ sum _ {i = 1}^{n} \ mathbf {a_ {i}} ^{k} \ phi (\ mathbf {x_ {i}}) \ rechts) ^{t} \ phi (\ mathbf {x})}

We noteren dat ${\ displayStyle \ phi (\ mathbf {x_ {i}})^{t} \ phi (\ mathbf {x})}}$ geeft DOT -product aan, dat gewoon de elementen van de kernel is ${\ displaystyle k}$ .Het lijkt erop dat het enige dat overblijft is om de ${\ DisplayStyle \ Mathbf {a_ {i}} ^{k}}$ , wat kan worden gedaan door de eigenvectorvergelijking op te lossen

{\ displaystyle n \ lambda \ mathbf {a} = k \ mathbf {a}}

waarbij n het aantal gegevenspunten is in de set, en ${\ DisplayStyle \ Lambda}$ en ${\ DisplayStyle \ Mathbf {A}}$ zijn de eigenwaarden en eigenvectoren van ${\ displaystyle k}$ .Vervolgens om de eigenvectoren te normaliseren ${\ DisplayStyle \ Mathbf {a} ^{k}}$ , dat hebben we nodig

{\ DisplayStyle 1 = (\ Mathbf {v} ^{k}) ^{t} \ Mathbf {v} ^{k}}

Er moet voor worden gezet met betrekking tot het feit dat, of het nu wel of niet is ${\ displaystyle x}$ heeft nul-gemiddelde in zijn oorspronkelijke ruimte, het is niet gegarandeerd gecentreerd in de speelruimte (die we nooit expliciet berekenen).Omdat gecentreerde gegevens nodig zijn om een effectieve principale componentanalyse uit te voeren, wij 'centraliseren' ${\ displaystyle k}$ worden ${\ DisplayStyle K '}$

{\ displaystyle k '= k- \ mathbf {1_ {n}} k-k \ mathbf {1_ {n}} +\ mathbf {1_ {n}} k \ mathbf {1_ {n}}}}

waar ${\ DisplayStyle \ Mathbf {1_ {n}}}$ geeft een n-by-n matrix aan waarvoor elk element waarde neemt ${\ DisplayStyle 1/n}$ . We gebruiken ${\ DisplayStyle K '}$ om het hierboven beschreven kernel -algoritme uit te voeren.

Een voorbehoud van kernel PCA moet hier worden geïllustreerd.In lineaire PCA kunnen we de eigenwaarden gebruiken om de eigenvectoren te rangschikken op basis van hoeveel van de variatie van de gegevens wordt vastgelegd door elke hoofdcomponent.Dit is handig voor reductie van gegevensdimensionaliteit en het kan ook worden toegepast op KPCA.In de praktijk zijn er echter gevallen dat alle variaties van de gegevens hetzelfde zijn.Dit wordt meestal veroorzaakt door een verkeerde keuze van kernelschaal.

Grote datasets

In de praktijk leidt een grote gegevensset tot een grote K, en het opslaan van K kan een probleem worden.Een manier om hiermee om te gaan, is door clustering op de gegevensset uit te voeren en de kernel te vullen met de middelen van die clusters.Aangezien zelfs deze methode een relatief grote K kan opleveren, is het gebruikelijk om alleen de bovenste p eigenwaarden en eigenvectoren van de eigenwaarden te berekenen, op deze manier berekend.

Voorbeeld

Invoerpunten vóór kernel PCA

Beschouw drie concentrische punten van punten (getoond);We willen kernel PCA gebruiken om deze groepen te identificeren.De kleur van de punten vertegenwoordigt geen informatie die betrokken is bij het algoritme, maar laat alleen zien hoe de transformatie de gegevenspunten verplaatst.

Overweeg eerst de kernel

{\ displaystyle k ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = ({\ boldsymbol {x}}^{\ mathrm {t}} {\ boldsymbolbol {y}} {y}} {y}} {y}} {}} {}} {{y}} {} {}} {y}} {y}}} {{y}}} {{y}} {y}} {y}} {y}}} {{y}+2}}

Dit toepassen op kernel PCA levert de volgende afbeelding op.

Output na kernel pca met

{\ displaystyle k ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = ({\ boldsymbol {x}}^{\ mathrm {t}} {\ boldsymbolbol {y}} {y}} {y}} {y}} {}} {}} {{y}} {} {}} {y}} {y}}} {{y}}} {{y}} {y}} {y}} {y}}} {{y}+2}}

.De drie groepen zijn alleen te onderscheiden met alleen de eerste component.

Overweeg nu een Gaussiaanse kernel:

{\ displayStyle k ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = e^{\ frac {-|| {\ boldsymbol {x}}-{\ boldsymbol {y}} ||^{{{}} ||^{}2}} {2 \ sigma ^{2}}},}

Dat wil zeggen, deze kernel is een maat voor nabijheid, gelijk aan 1 wanneer de punten samenvallen en gelijk zijn aan 0 bij oneindig.

Output na kernel PCA, met een Gaussiaans kernel.

Merk met name op dat de eerste hoofdcomponent voldoende is om de drie verschillende groepen te onderscheiden, wat onmogelijk is met het gebruik van alleen lineaire PCA, omdat lineaire PCA alleen werkt in de gegeven (in dit geval tweedimensionale) ruimte, waarin deze concentrische puntwolken zijnNiet lineair scheidbaar.

Toepassingen

Kernel PCA is aangetoond dat het nuttig is voor nieuwheidsdetectie^[3] en afbeelding de-noising.^[4]

Zie ook

Referenties

^ Schölklopf, Bernhard;Smola, Alex; Müller, Klaus-Robert (1998)."Niet -lineaire componentanalyse als een kernel -eigenwaardeprobleem". Neurale berekening. 10 (5): 1299–1319. Citeseerx 10.1.1.100.3636. doen:10.1162/089976698300017467. S2CID 6674407.
^ Niet -lineaire componentanalyse als een kernel -eigenwaardeprobleem (technisch rapport)
^ Hoffmann, Heiko (2007). "Kernel PCA voor nieuwigheidsdetectie". Patroonherkenning. 40 (3): 863–874. doen:10.1016/j.patcog.2006.07.009.
^ Kernel PCA en de-noising in functieruimtes.Nips, 1999

[1] Schölklopf, Bernhard;Smola, Alex; Müller, Klaus-Robert (1998)."Niet -lineaire componentanalyse als een kernel -eigenwaardeprobleem". Neurale berekening. 10 (5): 1299–1319. Citeseerx 10.1.1.100.3636. doen:10.1162/089976698300017467. S2CID 6674407.

[2] Niet -lineaire componentanalyse als een kernel -eigenwaardeprobleem (technisch rapport)

[3] Hoffmann, Heiko (2007). "Kernel PCA voor nieuwigheidsdetectie". Patroonherkenning. 40 (3): 863–874. doen:10.1016/j.patcog.2006.07.009.

[4] Kernel PCA en de-noising in functieruimtes.Nips, 1999

[1]

[2]

[3]

[4]