스파스 PCA

희소주성분 분석(Sparse PCA)은 통계적 분석과 특히 다변량 데이터 집합 분석에 사용되는 전문 기법이다.입력 변수에 sparity 구조를 도입하여 데이터의 치수 감소를 위한 주성분 분석(PCA)의 고전적 방법을 확장한다.

일반 PCA의 특별한 단점은 주성분이 일반적으로 모든 입력 변수의 선형 조합이라는 것이다.스파스 PCA는 몇 개의 입력 변수만 포함하는 선형 조합을 찾아 이러한 단점을 극복한다.

현대의 데이터 집합은 흔히 샘플 수(${\displaystyle }$ ${\$$displaystyle p$$}$$$)와 비교하거나 훨씬 더 큰 입력 변수(${\displaystyle }$ ${\$$displaystyle$p} )를 가진다.$$$p{\displaystyle }$/ ${\displaystyle n}$ ${\displaystyle p/n}$이(가) 0으로 수렴되지 않으면$$ 고전적인 PCA가 일관되지 않는 것으로 나타났다.그러나 희박한 PCA는 $p{\displaystyle }$ ${\displaystyle \gg n}$ .${\displaystyle p\g n.}$을(를) 하더라도 일관성을 유지할 수 있다.

수학적 공식화

각 $p{\displaystyle }$ ${\displaystyle p}$ 열이$$ 입력 변수를 나타내고 각 $n{\displaystyle }$ ${\displaystyle n}$ 행은$$ 데이터 모집단에서 독립된 표본을 나타내는 $데이터{\displaystyle }$ 행렬 X$${\$displaystyle$X$\}$을 고려하십시오.One assumes each column of ${\displaystyle X}$ has mean zero, otherwise one can subtract column-wise mean from each element of ${\displaystyle X}$. Let ${\displaystyle \Sigma ={\frac {1}{n-1}}X^{\top }X}$ be the empirical covariance matrix of ${\displaystyle X}$, which has dimension ${\displaystyle p\times }$${\displaystyle p}$ ${\displaystyle p\times$ p$\}.$ $1{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ $\$ p {\$displaystyle 1\leq$ k\$leq p$의$$정수$$$k$ {\$displaystyle$ vp ${\$in \$mathb {R}{p}}}}$을(를) 갖는 희박한 $PCA{\displaystyle }$ 문제는 그 카디널리티를 구속하면서$$ 벡터 v$$:

${\displaystyle {\begin{ligned}\max \quad &v^{T}\Sigma v\\\{\text}{{{\text}}}}}}{2}=1\\좌측\좌측\vert_{0}\leq.\end{정렬}}}$Eq. 1

첫 번째 제약조건은 v가 단위 벡터임을 명시한다.두 번째 제약조건에서 $\Vert {\displaystyle {}_{}}$ ${\displaystyle v_{}}$ ${\displaystyle {\Vert }_{}}$ ${\$는 0이 아닌 성분 수로 정의된 defined 0${\$ v의 의사정규범을 나타낸다$$.그래서 두 번째 제약조건은 v에서 0이 아닌 성분의 수가 k보다 작거나 같음을 명시하고 있는데, 일반적으로 치수 p보다 훨씬 작은 정수다.Eq. 1의 최적 값은 k-sparse 최대 고유값으로 알려져 있다.

k=p를 취하면 문제가 일반 PCA로 줄어들어 최적값이 공분산 행렬 Ⅱ의 가장 큰 고유값이 된다.

최적의 솔루션 v를 찾은 후 σ을 분해하여 새로운 매트릭스를 얻는다.

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

그리고 이 과정을 반복하여 주요 구성요소를 추가로 확보한다.그러나 PCA와 달리 희박한 PCA는 서로 다른 주성분이 직교한다고 보장할 수 없다.직교성 달성을 위해서는 추가적인 제약이 시행되어야 한다.

다음과 같은 등가 정의는 매트릭스 형태로 되어 있다.$V{\displaystyle }$ ${\displaystyle V}$을(를) p×p 대칭 행렬로 하고$$, 희박한 PCA 문제를 다음과 같이 다시 쓸 수 있다.

${\displaystyle {\begin{aigned}\max \quad &Tr(\Sigma V)\\\\\\text{{projected to}}}\}\{0}\leq k^{2}\&Lrank(V)=1,V\succeq 0.\end{정렬}}}$Eq. 2

Tr은 매트릭스 트레이스(${\displaystyle \mathrm{matrix}}$ trace)이고, $\Vert {\displaystyle }$ V ${\displaystyle {}_{}}$ 0 ${\$은 매트릭스 V에서 0이 아닌 원소를 나타낸다.마지막 줄은 V가 매트릭스 순위 1을 가지며 양의 세미데마인임을 명시한다.마지막 줄은 $V{\displaystyle }$= ${\displaystyle V}$ ${\displaystyle T^{}}$ ${\$ 따라서 Eq. 2는 Eq. 1과 같다.

더욱이, 이 공식의 순위 제약은 실제로 중복적이므로, 희소성 PCA는 다음과 같은 혼합-정수자 세미더파인 프로그램으로^[2] 주조될 수 있다.

${\displaystyle {\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{subject to}}\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}}}$Eq. 3

카디널리티 제약 때문에 특히 치수 p가 높을 때 최대화 문제는 정확히 해결하기 어렵다.사실 Eq. 1의 희박한 PCA 문제는 강한 의미에서 NP-hard이다.^[3]

스파스 PCA 알고리즘

(Eq.1의) 다음과 같은 몇 가지 대안적 접근법이 제안되었다.

• 회귀 프레임워크,^[4]
• 볼록한 이완/^[5]강화 피니티 프로그래밍 프레임워크
• 일반화된 권력 방식^[6] 틀
• 교대로 최대화하는^[7] 틀
• 전방 주시 탐욕스러운 검색 및 분기와 바인딩 기법을 사용한 정확한 ^[8]방법
• 증명할 수 있는 최적의 분기 및 바인딩^[9]
• 베이지안 공식 프레임워크.^[10]
• 인증적으로 최적의 혼합-정수자 세미-피니트 분기-컷 접근 방식

스파스 PCA의 방법론적, 이론적 발전뿐만 아니라 과학 연구에서의 응용도 최근 조사 논문에서 검토되고 있다.^[11]

라소를 통한 회귀 접근법(탄성망)

Semidefinite 프로그래밍 완화

희소성 PCA는 세미데드파인프로그래밍(SDP)으로 근사치를 산출할 수 있다는 제안이 나왔다.^[5]순위 구속조건을 떨어뜨리고 카디널리티 구속조건을 1노멀 볼록 구속조건으로 완화할 경우 다항 시간 내에 효율적으로 해결할 수 있는 세미더피니트 프로그래밍 완화를 얻게 된다.

${\displaystyle {\begin{aigned}\max \quad &Tr(\Sigma V)\\\\\\text{{}}}}}\quad &Tr(V)=1\&\\mathbf {1}{T}V \leq k\&V\sucq.\end{정렬}}}$Eq. 3

두 번째 제약조건에서 $1{\displaystyle \mathbf{}}$ ${\$은(는) 하나의 p×1 벡터$$, V는 원소가 V 원소의 절대값인 행렬이다.

완화 문제 Eq. 3에 대한$$ 최적의 솔루션 $V{\displaystyle }$ ${\displaystyle$ V$}$은(는) 1위를 보장받지 못한다.이 경우 $V{\displaystyle }$ ${\displaystyle V}$을(를) 잘라 지배적인 고유 벡터만 유지할 수 있다$$.

세미더파인 프로그램은 n=300 공변량을 넘어서는 스케일이 되지 않지만, 세미더파인 휴식의 2차 원뿔 이완은 거의 그만큼 빡빡하고 n=1000s 공변량으로 문제를 성공적으로 해결하는 것으로 나타났다.

적용들

재무 데이터 분석

일반적인 PCA가 각 입력 변수가 서로 다른 자산을 나타내는 데이터 집합에 적용된다고 가정하면, 모든 자산의 가중 조합인 주요 구성요소를 생성할 수 있다.이와는 대조적으로 희소 PCA는 소수의 투입자산만을 가중 조합한 주요 구성요소를 생산하므로 그 의미를 쉽게 해석할 수 있다.더욱이 이러한 주요 구성요소에 기초한 거래전략을 사용하는 경우, 거래원가를 감소시킬 수 있는 자산이 줄어든다.

생물학

각 입력 변수가 특정 유전자에 해당하는 데이터 집합을 고려하십시오.희소성 PCA는 몇 개의 유전자만 관여하는 주요 성분을 생산할 수 있기 때문에 연구자들은 이러한 특정 유전자에 초점을 맞춰 추가 분석을 할 수 있다.

고차원 가설 검정

현대의 데이터 집합은 흔히 샘플 수(${\displaystyle }$ ${\$$displaystyle p$$}$$$)와 비교하거나 훨씬 더 큰 입력 변수(${\displaystyle }$ ${\$$displaystyle$p} )를 가진다.$$$p{\displaystyle }$/ ${\displaystyle n}$ ${\displaystyle p/n}$이(가) 0으로 수렴되지 않으면$$ 고전적인 PCA가 일관되지 않는 것으로 나타났다.즉, Eq. 1에서 $k{\displaystyle }$= p ${\displaystyle k=p}$을(를) 그대로 두면, 표본 $크기{\displaystyle }$n → ${\displaystyle \mathrm{\infty }}$ ${\displaystyle n\rightarrow \inft }$ $,$ 그리고 최적 솔루션이 최대 분산 방향으로 수렴되지 않을 때 최적 값은 데이터 모집단의 가장 큰 고유값으로 수렴되지 않는다.그러나 희박한 PCA는 $p{\displaystyle }$ ${\displaystyle \gg n}$ .${\displaystyle p\g n.}$을(를) 하더라도 일관성을 유지할 수 있다.

k-sparse 최대 고유값(Eq. 1)은 모든 방향의 분산이 동일한 등축 모델을 고차원 설정의 스파이크 공분산 모델과 구별하기 위해 사용할 수 있다.^[13]귀무 가설에서 데이터 $X{\displaystyle }$ ${\displaystyle$ X$}$이(가) 평균 0과 공분산이 ID 행렬과 같은 다변량 정규 분포에서 생성되고, 대립 가설에서는 $데이터{\displaystyle }$ X$${\$displaystyle$ X$}$이(가) 신호 $강도$가 with인 스파이크 모델에서 생성된다고$$ 명시하는 가설 검정을 고려하십시오.${\displaystyle }\{\backslash$$displaystyle \theta}:$

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

여기서 $v{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$에는 0이 아닌 좌표가 k개만 있다.가장 큰 k-sparse 고유값은 > ( k ( ) /n ) {\$displaystyle \theta >\theta$({\$sqrt {k\log($p)/$n$인 경우에만 두 가설을 구별할 수 있다.

k-sparse 고유값을 계산하는 것은 NP-hard이기 때문에 세미데마인파 프로그래밍 완화의 최적값(Eq 3)으로 근사치를 구할 수 있다.만일 그렇다면 > ( 2 / n) ${\displaystyle \theta >\theta ({k^{2}\log(p)/n})}}}}$이가) 된다면 두 가설을 구별할 수 있다.심어진 clique 추측이 유지된다면 추가 $k$ ${\$ 항은 다른 다항 시간 알고리즘으로 개선할 수 없다.

소프트웨어/소스 코드

• amanpg - 교류 다지관 근위부 그라데이션 방법을 사용한 스파스 PCA용 R 패키지
• 탄성넷 – 탄성넷을 사용한 희소추정 및 희소 PCA용 R 패키지
• nsprcomp - 임계값 전원 반복에^[16] 기반한 희소성 및/또는 비음성 PCA용 R 패키지
• Scikit-learn – Python 라이브러리(분해 모듈의 스파스 PCA 및 기타 기법 포함)^[17]

참조