Schaarse PCA

Schaarse principale componentanalyse (schaarse PCA) is een gespecialiseerde techniek die wordt gebruikt in statistische analyse en in het bijzonder bij de analyse van multivariate gegevenssets.Het breidt de klassieke methode van Hoofdcomponentanalyse (PCA) voor de vermindering van de dimensionaliteit van gegevens door het introduceren van sparsity -structuren in de invoervariabelen.

Een bijzonder nadeel van gewone PCA is dat de belangrijkste componenten meestal lineaire combinaties zijn van alle invoervariabelen.Sparse PCA overwint dit nadeel door lineaire combinaties te vinden die slechts enkele invoervariabelen bevatten.

Hedendaagse datasets hebben vaak het aantal invoervariabelen (${\ displaystyle p}$) vergelijkbaar met of zelfs veel groter dan het aantal monsters (${\ displaystyle n}$).Het is aangetoond dat als ${\ displaystyle p/n}$ convergeert niet naar nul, de klassieke PCA is dat niet consequent.Maar schaarse PCA kan consistentie behouden, zelfs als ${\ displaystyle p \ gg n.}$^[1]

Wiskundige formulering

Overweeg een gegevens Matrix, ${\ displaystyle x}$, waar elk van de ${\ displaystyle p}$ kolommen vertegenwoordigen een invoervariabele, en elk van de ${\ displaystyle n}$ Rijen vertegenwoordigt een onafhankelijke steekproef van de gegevenspopulatie.Men neemt elke kolom van ${\ displaystyle x}$ heeft gemiddelde nul, anders kan men kolomgewijs gemiddelde aftrekken van elk element van ${\ displaystyle x}$. Laten ${\ displayStyle \ sigma = {\ frac {1} {n-1}} x^{\ top} x}$ Wees het empirisch covariantiematrix van ${\ displaystyle x}$, die dimensie heeft ${\ displaystyle p \ maal p}$. Gegeven een geheel getal ${\ displaystyle k}$ met ${\ displaystyle 1 \ leq k \ leq p}$, het schaarse PCA -probleem kan worden geformuleerd als het maximaliseren van de variantie langs een richting die wordt weergegeven door vector ${\ displaystyle v \ in \ mathbb {r} ^{p}}$ Terwijl hij zijn kardinaliteit beperkt:

$\ & \ links \ vert v \ rechts \ vert _ {0} \ leq k. \ end {uitgelijnd}}}$Eq. 1

De eerste beperking geeft dat aan v is een eenheidsvector.In de tweede beperking, ${\ displaystyle \ links \ vert v \ rechts \ vert _ {0}}$ vertegenwoordigt de ${\ DisplayStyle \ ell _ {0}}$ pseudo-norm van v, die wordt gedefinieerd als het aantal niet-nulcomponenten.Dus de tweede beperking geeft aan dat het aantal niet-nulcomponenten in v is kleiner dan of gelijk aan k, wat meestal een geheel getal is dat veel kleiner is dan dimensie p.De optimale waarde van Eq. 1 staat bekend als de k-Sparse grootste eigenwaarde.

Als men neemt K = P, het probleem vermindert tot het gewone PCA, en de optimale waarde wordt de grootste eigenwaarde van covariantiematrix Σ.

Na het vinden van de optimale oplossing v, laat één leeglopen Σ Om een nieuwe matrix te verkrijgen

${\ displaystyle \ sigma _ {1} = \ sigma -(v^{t} \ sigma v) vv^{t},}$

en dit proces herhalen om verdere hoofdcomponenten te verkrijgen.In tegenstelling tot PCA kan schaarse PCA echter niet garanderen dat verschillende hoofdcomponenten dat zijn orthogonaal.Om orthogonaliteit te bereiken, moeten extra beperkingen worden afgedwongen.

De volgende equivalente definitie is in matrixvorm.Laten ${\ DisplayStyle v}$ wees een P × P symmetrische matrix, men kan het schaarse PCA -probleem herschrijven als

${\ DisplayStyle {\ begin {uitgelijnd} \ max \ quad & tr (\ sigma v) \\ {\ text {onderworpen aan}} \ quad & tr (v) = 1 \\ & \ vert v \ vert _ _ _ _ _} \leq k^{2} \\ & rank (v) = 1, v \ succeq 0. \ end {uitgelijnd}}}$Eq. 2

TR is de matrixspoor, en ${\ DisplayStyle \ Vert V \ Vert _ {0}}$ vertegenwoordigt de niet-nul elementen in matrix V.De laatste regel geeft dat aan V heeft matrixrang een en is Positieve semidefiniet.De laatste regel betekent dat men heeft ${\ displaystyle v = vv^{t}}$, dus Eq. 2 is gelijk aan Eq. 1.

Bovendien is de rangbeperking in deze formulering eigenlijk overbodig en daarom kan schaarse PCA worden gegoten als het volgende gemengd-integer semidefinietprogramma^[2]

${\ displayStyle {\ begin {uitgelijnd} \ max \ quad & tr (\ sigma v) \\ {\ text {onderworpen aan}} \ quad & tr (v) = 1 \\ & \ vert v_ {i, i} \ vert\ leq z_ {i}, \ forall i \ in \ {1, ..., p \}, \ vert v_ {i, j} \ vert \ leq {\ frac {1} {2}} z_ {i}, \ forall i, j \ in \ {1, ..., p \}: i \ neq j, \\ & v \ Succeq 0, z \ in \ {0,1 \}^{p}, \ sum _{i} z_ {i} \ leq k \ end {uitgelijnd}}}$Eq. 3

Vanwege de kardinaliteitsbeperking is het maximalisatieprobleem moeilijk op te lossen, vooral wanneer de dimensie p is hoog.In feite, het schaarse PCA -probleem in Eq. 1 is Np-hard In de sterke zin.^[3]

Algoritmen voor schaarse PCA

Verschillende alternatieve benaderingen (van Eq. 1) zijn voorgesteld, inclusief

• een regressiekader,^[4]
• Een geklamde matrixontledingskader,^[5]
• Een convexe ontspanning/semidefiniet programmeerkader,^[6]
• Een gegeneraliseerd kader voor de krachtmethode^[7]
• een afwisselend maximalisatiekader^[8]
• Voorwaarts-achterwaartse hebzuchtige zoekopdracht en exacte methoden met behulp van branch-and-bound-technieken,^[9]
• Een certificeerbaar optimale tak-en-gebonden aanpak^[10]
• Bayesiaans formuleringskader.^[11]
• Een certificeerbaar optimale semidefiniet tak-en-gesneden benadering van gemengd-integer ^[2]

De methodologische en theoretische ontwikkelingen van schaarse PCA en de toepassingen ervan in wetenschappelijke studies worden onlangs beoordeeld in een onderzoekspaper.^[12]

Opmerkingen over ontspanning van semidefiniet programmeren

Er is voorgesteld dat schaarse PCA kan worden benaderd door semidefinietprogrammering (SDP).^[6] Als men de rangbeperking laat vallen en de kardinaliteitsbeperking ontspant door een 1-norm convex Beperking, men krijgt een semidefinietprogrammeerrelaxing, die efficiënt kan worden opgelost in polynoomtijd:

${\ DisplayStyle {\ begin {uitgelijnd} \ max \ quad & tr (\ sigma v) \\ {\ text {onderworpen aan}} \ quad & tr (v) = 1 \\ & \ mathbf {1} ^{t} |V | \ mathbf {1} \ leq k \\ & v \ succeq 0. \ end {uitlijnd}}}$Eq. 3

In de tweede beperking, ${\ DisplayStyle \ Mathbf {1}}$ is een P × 1 vector van degenen, en | V | is de matrix waarvan de elementen de absolute waarden zijn van de elementen van V.

De optimale oplossing ${\ DisplayStyle v}$ naar het ontspannen probleem Eq. 3 is niet gegarandeerd rang één.In dat geval, ${\ DisplayStyle v}$ kan worden afgekapt om alleen de dominante eigenvector te behouden.

Hoewel het Semidefinite-programma niet verder schaalt dan n = 300 covariaten, is aangetoond dat een tweede-orde kegelrelaxatie van de semidefiniet-ontspanning bijna net zo strak is en met succes problemen oplost met n = 1000s van covariaten ^[13]

Toepassingen

Financiële gegevensanalyse

Stel dat gewone PCA wordt toegepast op een dataset waarbij elke invoervariabele een ander actief vertegenwoordigt, deze kan hoofdcomponenten genereren die gewogen combinatie van alle activa zijn.Spaarse PCA zou daarentegen hoofdcomponenten produceren die een gewogen combinatie van slechts enkele invoeractiva zijn, dus men kan de betekenis ervan gemakkelijk interpreteren.Bovendien, als men een handelsstrategie gebruikt op basis van deze hoofdcomponenten, impliceren minder activa minder transactiekosten.

Biologie

Overweeg een gegevensset waarbij elke invoervariabele overeenkomt met een specifiek gen.Sparse PCA kan een hoofdcomponent produceren die slechts enkele genen omvat, zodat onderzoekers zich kunnen concentreren op deze specifieke genen voor verdere analyse.

Hoogdimensionale hypothese-testen

Hedendaagse datasets hebben vaak het aantal invoervariabelen (${\ displaystyle p}$) vergelijkbaar met of zelfs veel groter dan het aantal monsters (${\ displaystyle n}$).Het is aangetoond dat als ${\ displaystyle p/n}$ convergeert niet naar nul, de klassieke PCA is dat niet consequent.Met andere woorden, als we het laten ${\ displaystyle k = p}$ in Eq. 1, dan convergeert de optimale waarde niet naar de grootste eigenwaarde van gegevenspopulatie wanneer de steekproefomvang ${\ displaystyle n \ rightarrow \ infty}$, en de optimale oplossing convergeert niet naar de richting van maximale variantie.Maar schaarse PCA kan consistentie behouden, zelfs als ${\ displaystyle p \ gg n.}$^[1]

De k-Sparse grootste eigenwaarde (de optimale waarde van Eq. 1) kan worden gebruikt om een isometrisch model te onderscheiden, waarbij elke richting dezelfde variantie heeft, van een puntig covariantiemodel in een hoge dimensionale setting.^[14] Overweeg een hypothesetest waarbij de nulhypothese dat gegevens aangeeft ${\ displaystyle x}$ worden gegenereerd uit een multivariate normale verdeling met gemiddelde 0 en covariantie gelijk aan een identiteitsmatrix, en de alternatieve hypothese geeft aan dat gegevens ${\ displaystyle x}$ wordt gegenereerd uit een puntig model met signaalsterkte ${\ DisplayStyle \ theta}$:

${\ displaystyle H_ {0}: x \ sim n (0, i_ {p}), \ quad h_ {1}: x \ sim n (0, i_ {p}+\ theta vv^{t}),}$

waar ${\ displaystyle v \ in \ mathbb {r} ^{p}}$ heeft alleen k niet-nul coördinaten.De grootste k-sparse eigenwaarde kan de twee hypothese discrimineren als en alleen als ${\ displayStyle \ theta> \ theta ({\ sqrt {k \ log (p)/n}})}$.

Sinds computing k-Sparse eigenwaarde is NP-Hard, men kan het benaderen door de optimale waarde van semidefinietprogrammeringsontspanning (Eq. 3).Als dat geval, kunnen we de twee hypothesen discrimineren als ${\ displayStyle \ theta> \ theta ({\ sqrt {k^{2} \ log (p)/n}})}$.De aanvullende ${\ DisplayStyle {\ sqrt {k}}}$ term kan niet worden verbeterd door een ander polynomiaal tijdsalgoritme als de geplant kliek vermoeden houdt vast.

Software/broncode

• AMANPG - R -pakket voor schaarse PCA met behulp van de alternerende verdeelstuk proximale gradiëntmethode ^[15]
• Elasticnet-R-pakket voor schaarse schatting en schaarse PCA met behulp van elastische netten ^[16]
• NSPRCOMP - R -pakket voor schaarse en/of niet -negatieve PCA op basis van drempelwaarde -iteraties^[17]
• Scikit-Learn - Python -bibliotheek voor machine learning die schaarse PCA en andere technieken in de ontledingsmodule bevat.^[18]

Referenties