Gles PCA

Sparse principal component analysis ( sparse PCA ) är en specialiserad teknik som används vid statistisk analys och i synnerhet vid analys av multivariata datamängder. Den utökar den klassiska metoden för principal component analysis (PCA) för att reducera dimensionalitet av data genom att introducera sparsitetsstrukturer i indatavariablerna.

En speciell nackdel med vanlig PCA är att huvudkomponenterna vanligtvis är linjära kombinationer av alla indatavariabler. Sparse PCA övervinner denna nackdel genom att hitta linjära kombinationer som innehåller bara ett fåtal indatavariabler.

Samtida datamängder har ofta antalet indatavariabler ( $p$ ) jämförbart med eller till och med mycket större än antalet sampel ( $n$ ). Det har visat sig att om $p/n$ inte konvergerar till noll, är den klassiska PCA inte konsekvent . Men sparsam PCA kan behålla konsistensen även om $p\gg n.$

Matematisk formulering

Betrakta en datamatris , X $\displaystyle X}$ , där var och en av $p$ -kolumnerna representerar en indatavariabel, och var och en av de $n$ -raderna representerar ett oberoende urval från datapopulationen. Man antar att varje kolumn i $X$ har medelvärdet noll, annars kan man subtrahera kolumnvis medelvärde från varje element i $X$ . Låt $\Sigma ={\frac {1}{n-1}}X^{\top }X$ vara den empiriska kovariansmatrisen för $X$ , som har dimensionen $p\times p$ . Givet ett heltal $k$ med $1\leq k\leq p$ , kan det glesa PCA-problemet formuleras som att maximera variansen längs en riktning som representeras av vektorn ${\ displaystyle v\in \mathbb {R} ^{p}}$ samtidigt som man begränsar dess kardinalitet:

${\begin{aligned}\max \quad &v^{T}\Sigma v\\{\text{subject to}}\quad &\left\Vert v\right\Vert _{2}=1\ \&\left\Vert v\right\Vert _{0}\leq k.\end{aligned}}$

Den första begränsningen specificerar att v är en enhetsvektor. I den andra begränsningen representerar $\left\Vert v\right\Vert _{0}$$\ell _{0}$ pseudonormen för v , som definieras som talet av dess icke-nollkomponenter. Så den andra begränsningen specificerar att antalet komponenter som inte är noll i v är mindre än eller lika med k , vilket vanligtvis är ett heltal som är mycket mindre än dimensionen p . Det optimala värdet av ekv. 1 är känt som det k -glesa största egenvärdet .

Om man tar k=p minskar problemet till den vanliga PCA och det optimala värdet blir det största egenvärdet för kovariansmatrisen Σ .

Efter att ha hittat den optimala lösningen v tömmer man Σ för att få en ny matris

$\Sigma _{1}=\Sigma -(v^{T}\Sigma v)vv^{T},$

och upprepa denna process för att erhålla ytterligare huvudkomponenter. Men till skillnad från PCA kan sparse PCA inte garantera att olika huvudkomponenter är ortogonala . För att uppnå ortogonalitet måste ytterligare begränsningar upprätthållas.

Följande ekvivalenta definition är i matrisform. Låt $V$ vara en p×p symmetrisk matris, man kan skriva om det glesa PCA-problemet som

${\begin{aligned}\max \quad &Tr (\Sigma V)\\{\text{med förbehåll för}}\quad &Tr(V)=1\\&\Vert V\Vert _{0}\leq k^{2}\\&Rank(V)=1 ,V\succeq 0.\end{aligned}}$

Tr är matrisspåret och $\Vert V\Vert _{0}$ representerar elementen som inte är noll i matrisen V . Den sista raden anger att V har matrisrang 1 och är positiv semidefinit . Den sista raden betyder att man har $V=vv^{T}$ , så Ekv. 2 är ekvivalent med ekv. 1 .

Dessutom är rangbegränsningen i denna formulering faktiskt överflödig, och därför kan gles PCA gjutas som följande blandade heltals semidefinite program

${\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{ med förbehåll för}}\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{aligned}}$

På grund av kardinalitetsbegränsningen är maximeringsproblemet svårt att lösa exakt, speciellt när dimensionen p är hög. Faktum är att det glesa PCA-problemet i Eq. 1 är NP-hård i stark mening.

Algoritmer för sparsam PCA

Flera alternativa tillvägagångssätt (av ekv. 1 ) har föreslagits, inklusive

• ett regressionsramverk,
• en peneliserad matrisnedbrytningsram,
• en konvex avslappning/halvdefinierad programmeringsram,
• ett generaliserat ramverk för maktmetoder
• en alternerande maximeringsram
• framåt-bakåt girig sökning och exakta metoder med gren-och-bindningstekniker,
• ett certifierat optimalt gren-och-bundet tillvägagångssätt
• Bayesiansk formuleringsram.
• Ett certifierat optimalt blandat heltals semidefinite gren-och-klipp-metoden

Den metodologiska och teoretiska utvecklingen av Sparse PCA såväl som dess tillämpningar i vetenskapliga studier har nyligen granskats i en enkätrapport.

Anmärkningar om Semidefinite Programmering Relaxation

Det har föreslagits att sparsam PCA kan approximeras genom semidefinite programmering (SDP). Om man tappar rangbegränsningen och slappnar av kardinalitetsbegränsningen med en 1-norm konvex begränsning, får man en semidefinitiv programmeringsrelaxation, som kan lösas effektivt i polynomtid:

${\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{subject to}}\quad &Tr(V)=1\\&\mathbf { 1} ^{T}|V|\mathbf {1} \leq k\\&V\succeq 0.\end{aligned}}$

I den andra begränsningen är $\mathbf {1}$ en p×1 vektor av ettor, och |V| är matrisen vars element är absolutvärdena för elementen i V .

Den optimala lösningen $V$ på det avslappnade problemet Ekv. 3 är inte garanterat att ha plats ett. I så fall $V$ trunkeras för att bara behålla den dominanta egenvektorn.

Även om det semidefinita programmet inte skalar över n=300 kovariater, har det visat sig att en andra ordningens konrelaxation av den semidefinita relaxationen är nästan lika snäv och framgångsrikt löser problem med n=1000s av kovariater

Ansökningar

Finansiell dataanalys

Anta att vanlig PCA tillämpas på en datauppsättning där varje indatavariabel representerar en annan tillgång, kan den generera huvudkomponenter som är en viktad kombination av alla tillgångar. Däremot skulle sparsam PCA producera huvudkomponenter som är viktade kombinationer av endast ett fåtal ingående tillgångar, så man kan enkelt tolka dess innebörd. Dessutom, om man använder en handelsstrategi baserad på dessa huvudkomponenter, innebär färre tillgångar mindre transaktionskostnader.

Biologi

Betrakta ett dataset där varje indatavariabel motsvarar en specifik gen. Gles PCA kan producera en huvudkomponent som bara involverar ett fåtal gener, så forskare kan fokusera på dessa specifika gener för vidare analys.

Högdimensionell hypotestestning

Samtida datamängder har ofta antalet indatavariabler ( $p$ ) jämförbart med eller till och med mycket större än antalet sampel ( $n$ ). Det har visat sig att om $p/n$ inte konvergerar till noll, är den klassiska PCA inte konsekvent . Med andra ord, om vi låter $k=p$ i ekv. 1 , då konvergerar inte det optimala värdet till det största egenvärdet för datapopulationen när urvalsstorleken $n\rightarrow \infty$ , och den optimala lösningen inte konvergerar till riktningen för maximal varians. Men sparsam PCA kan behålla konsistensen även om $p\gg n.$

Det k -glesa största egenvärdet (det optimala värdet av ekv. 1 ) kan användas för att skilja en isometrisk modell, där varje riktning har samma varians, från en spikad kovariansmodell i högdimensionell miljö. Betrakta ett hypotestest där nollhypotesen anger att data $X$ genereras från en multivariat normalfördelning med medelvärde 0 och kovarians lika med en identitetsmatris, och den alternativa hypotesen anger att data $X$ genereras från en spetsad modell med signalstyrka $\theta$ :

$H_{0}:X\sim N(0,I_{p}),\ quad H_{1}:X\sim N(0,I_{p}+\theta vv^{T}),$

där $v\in \mathbb {R} ^{p}$ endast har k koordinater som inte är noll. Det största k -glesa egenvärdet kan särskilja de två hypoteserna om och endast om $\theta >\Theta ({\sqrt {k\log(p)/n} })$ .

Eftersom beräkning av k -glesa egenvärde är NP-hård, kan man approximera det med det optimala värdet av semidefinite programmeringsrelaxation ( Ekv. 3 ). I så fall kan vi särskilja de två hypoteserna om $\theta >\Theta ({\sqrt {k^{2}\log(p)/n }})$ . Den ytterligare ${\sqrt {k}}$ termen kan inte förbättras med någon annan polynomisk tidsalgoritm om den planterade klickförmodan håller.

Programvara/källkod

• amanpg - R-paket för sparsam PCA med användning av den alternerande grenrörets proximala gradientmetoden
• elasticnet – R-paket för Sparse Estimation och Sparse PCA med Elastic-Nets
• nsprcomp - R-paket för sparsam och/eller icke-negativ PCA baserat på tröskelvärde effekt iterationer
• scikit-learn – Python-bibliotek för maskininlärning som innehåller Sparse PCA och andra tekniker i nedbrytningsmodulen.