スパースPCA
統計分析技術

スパース主成分分析（SPCAまたはスパースPCA）は、統計分析、特に多変量データセットの分析において用いられる手法です。これは、入力変数にスパース構造を導入することで、データの次元を削減する古典的な主成分分析（PCA） 手法を拡張したものです。

通常のPCAの欠点の一つは、主成分が通常、すべての入力変数の線形結合となることです。SPCAは、少数の入力変数（SPC）の線形結合である成分を見つけることでこの欠点を克服します。これは、SPCを定義する線形結合の係数の一部（負荷量[注1]と呼ばれる）がゼロになることを意味します。非ゼロの負荷量の数は、SPCの カーディナリティ と呼ばれます。

数学的定式化

データ行列を考える。ここで、各列は入力変数を表し、各行はデータ母集団からの独立標本を表す。 の各列の平均はゼロであると仮定する。そうでない場合は、 の各要素から列ごとの平均を減算する。を の経験的共分散行列とし、その次元はとする。 X {\displaystyle X} p {\displaystyle p} n {\displaystyle n} X {\displaystyle X} X {\displaystyle X} Σ ＝ 1 n − 1 X ⊤ X {\displaystyle \Sigma ={\frac {1}{n-1}}X^{\top }X} X {\displaystyle X} p × p {\displaystyle p\times p}

の整数が与えられた場合、スパースPCA問題は、その基数を制約しながらベクトルで表される方向に沿って分散を最大化するものとして定式化できます。 け {\displaystyle k} 1 ≤ け ≤ p {\displaystyle 1\leq k\leq p} v ∈ R p {\displaystyle v\in \mathbb {R} ^{p}}

最大 v T Σ v 対象となる ‖ v ‖ 2 ＝ 1 ‖ v ‖ 0 ≤ け 。 {\displaystyle {\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}}} 式1

最初の制約は、vが単位ベクトルであることを指定します。2番目の制約では、はvの擬似ノルムを表し、これは v の非ゼロ成分の数として定義されます。したがって、2番目の制約は、vの非ゼロ成分の数がk以下であることを指定します。k は通常、次元pよりもはるかに小さい整数です。式1の最適値は、k疎最大固有値として知られています。 ‖ v ‖ 0 {\displaystyle \left\Vert v\right\Vert _{0}} ℓ 0 {\displaystyle \ell_{0}}

k=pとすると、問題は通常のPCAに簡略化され、最適値は共分散行列Σの最大固有値になります。

最適解vを見つけた後、Σを縮小して新しい行列を得る。

Σ 1 ＝ Σ − （ v T Σ v ） v v T 、 {\displaystyle \Sigma _{1}=\Sigma -(v^{T}\Sigma v)vv^{T},}

このプロセスを繰り返して、さらなる主成分を取得します。ただし、PCAとは異なり、スパースPCAでは異なる主成分が直交していることを保証できません。直交性を達成するには、追加の制約を適用する必要があります。

次式は行列形式で同等の定義である。p ×p対称行列を とすると、疎PCA問題は次のように書き直すことができる。 V {\displaystyle V}

最大 T r （ Σ V ） 対象となる T r （ V ） ＝ 1 ‖ V ‖ 0 ≤ け 2 R 1つの n け （ V ） ＝ 1 、 V ⪰ 0。 {\displaystyle {\begin{aligned}\max \quad &Tr(\Sigma V)\\{\text{subject to}}\quad &Tr(V)=1\\&\Vert V\Vert _{0}\leq k^{2}\\&Rank(V)=1,V\succeq 0.\end{aligned}}} 式2

Trは行列トレースであり、行列Vの非零要素を表します。最後の行は、Vが行列ランク1で半正定値であることを指定します。最後の行は が成り立つことを意味し、したがって式2は式1と等価です。 ‖ V ‖ 0 {\displaystyle \Vert V\Vert _{0}} V ＝ v v T {\displaystyle V=vv^{T}}

さらに、この定式化におけるランク制約は実際には冗長であり、したがってスパースPCAは次の混合整数半正定値計画法として表すことができる[1]

最大 T r （ Σ V ） 対象となる T r （ V ） ＝ 1 | V 私 、 私 | ≤ z 私 、 た 私 ∈ { 1 、 。 。 。 、 p } 、 | V 私 、 j | ≤ 1 2 z 私 、 た 私 、 j ∈ { 1 、 。 。 。 、 p } : 私 ≠ j 、 V ⪰ 0 、 z ∈ { 0 、 1 } p 、 ∑ 私 z 私 ≤ け {\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}}} 式3

基数制約のため、最大化問題は厳密に解くことが困難であり、特に次元pが大きい場合は困難です。実際、式1のスパースPCA問題は強い意味でNP困難です。 [2]

計算上の考慮事項

ほとんどのスパース問題と同様に、SPCAにおける変数選択は計算的に扱いにくい非凸NP困難問題であるため、[3]、解決策を見つけるために貪欲な準最適アルゴリズムがよく使用されます。

また、SPCAは、大きなパラメータ値がどの程度ペナルティを受けるかを定量化するハイパーパラメータを導入することにも注意してください。[4]これらのハイパーパラメータは、満足のいくパフォーマンスを得るために調整する必要があり、それによって全体の計算コストが増加する可能性があります。

SPCAのアルゴリズム

（式1の）いくつかの代替アプローチが提案されており、その中には

  • 回帰フレームワーク[5]
  • ペナルティ付き行列分解フレームワーク[6]
  • 凸緩和/半正定値計画フレームワーク、[7]
  • 一般化されたべき乗法フレームワーク[8]
  • 交互最大化フレームワーク[9]
  • 前方後方貪欲探索と分岐限定法を用いた正確な方法、[10]
  • 証明可能な最適な分岐限定法[11]
  • ベイズ定式化の枠組み。[12]
  • 証明可能に最適な混合整数半正定値分岐カットアプローチ[1]

スパースPCAの方法論的・理論的発展と科学的研究への応用については、最近、調査論文でレビューされています。[13]

半正定値計画法の緩和に関する注釈

スパースPCAは半正定値計画法（SDP）によって近似できることが提案されている。[7]ランク制約を削除し、カーディナリティ制約を1ノルムの凸制約で緩和すると、半正定値計画法の緩和が得られ、これは多項式時間で効率的に解くことができる。

最大 T r （ Σ V ） 対象となる T r （ V ） ＝ 1 1 T | V | 1 ≤ け V ⪰ 0。 {\displaystyle {\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}}} 式3

2番目の制約では、はp×1のベクトルであり、|V|はVの要素の絶対値を要素とする行列です。 1 {\displaystyle \mathbf {1} }

緩和問題式3の最適解は必ずしもランク1であるとは限りません。その場合、支配的な固有ベクトルのみを残すように切り捨てることができます。 V {\displaystyle V} V {\displaystyle V}

半正定値計画法はn=300以上の共変量ではスケールしないが、半正定値緩和法の2次円錐緩和法はほぼ同程度にタイトであり、n=1000の共変量を持つ問題をうまく解くことが示されている[14]。

アプリケーション

財務データ分析

通常のPCAを、各入力変数が異なる資産を表すデータセットに適用すると、すべての資産の重み付けされた組み合わせである主成分が生成される場合があります。これに対し、スパースPCAでは、少数の入力資産の重み付けされた組み合わせである主成分が生成されるため、その意味を容易に解釈できます。さらに、これらの主成分に基づく取引戦略を用いると、資産数が少なければ少ないほど取引コストが低くなります。

生物学

各入力変数が特定の遺伝子に対応するデータセットを考えてみましょう。スパースPCAは、少数の遺伝子のみを含む主成分を生成できるため、研究者はこれらの特定の遺伝子に焦点を当ててさらなる分析を行うことができます。

高次元仮説検定

現代のデータセットでは、入力変数の数（）がサンプル数（ ）と同程度、あるいはそれよりもはるかに多い場合がよくあります。がゼロに収束しない場合、古典的なPCAは一貫性がないことが示されている。言い換えれば、式1をとすると、サンプルサイズが のときに最適値はデータ母集団の最大固有値に収束せず、最適解は最大分散の方向に収束しない。しかし、スパースPCAは、 の場合でも一貫性を保つことができる。 p {\displaystyle p} n {\displaystyle n} p / n {\displaystyle p/n} け ＝ p {\displaystyle k=p} n → ∞ {\displaystyle n\rightarrow\infty} p ≫ n 。 {\displaystyle p\gg n.}

kスパースの最大固有値（式1の最適値）は、すべての方向が同じ分散を持つ等尺性モデルと、高次元設定でのスパイク共分散モデルを区別するために使用できます。[15]帰無仮説では、データは平均0で共分散が単位行列に等しい多変量正規分布から生成され、対立仮説では、データは信号強度のスパイクモデルから生成されていると指定する仮説検定を考えます。 X {\displaystyle X} X {\displaystyle X} θ {\displaystyle \theta}

H 0 : X 〜 北 （ 0 、 私 p ） 、 H 1 : X 〜 北 （ 0 、 私 p + θ v v T ） 、 {\displaystyle H_{0}:X\sim N(0,I_{p}),\quad H_{1}:X\sim N(0,I_{p}+\theta vv^{T}),}

ここで、はk 個の非ゼロ座標のみを持ちます。最大のk疎な固有値は、 の場合にのみ、2つの仮説を区別できます。 v ∈ R p {\displaystyle v\in \mathbb {R} ^{p}} θ > Θ （ け ログ ⁡ （ p ） / n ） {\displaystyle \theta >\Theta ({\sqrt {k\log(p)/n}})}

kスパース固有値の計算はNP困難であるため、半正定値計画緩和法（式3）の最適値で近似することができます。その場合、 であれば2つの仮説を区別することができます。植え付けクリーク予想が成立する場合、追加の項は他の多項式時間アルゴリズムでは改善できません。 θ > Θ （ け 2 ログ ⁡ （ p ） / n ） {\displaystyle \theta >\Theta ({\sqrt {k^{2}\log(p)/n}})} け {\displaystyle {\sqrt {k}}}

ソフトウェア/ソースコード

  • amanpg - 交代多様体近位勾配法を用いたスパースPCA用のRパッケージ[16]
  • elasticnet – Elastic-Netを用いたスパース推定とスパースPCAのためのRパッケージ[17]
  • epca – 大規模データセットの探索的主成分分析のためのRパッケージ。スパース主成分分析とスパース行列近似を含む。[18]
  • nsprcomp - 閾値付き累乗反復に基づくスパースおよび/または非負PCA用のRパッケージ[19]
  • scikit-learn – 分解モジュールにスパースPCAやその他の技術を含む機械学習用のPythonライブラリ。[20]


注記

  1. ^ これらのベクトルには「ローディング」という用語が不適切に使用されています。これらのベクトルは「係数」と呼ぶべきです。この名称は、因子分析において共通共分散行列を生成する値を設計する際に用いられる「ローディング」という用語に由来しています。標準的な主成分分析（PCA）ではローディングは係数と等しいため、「ローディング」という用語が係数に使用されています。これは非常に残念なことです。なぜなら、SPCAでは係数はローディングと等しくないからです。


参考文献

  1. ^ ab Dimitris Bertsimas、Ryan Cory-Wright、Jean Pauphilet (2020). 「大規模スパースPCAを証明可能な（近似）最適性へと解く」arXiv : 2005.05195 [math.OC].
  2. ^ Andreas M. Tillmann; Marc E. Pfetsch (2013). 「圧縮センシングにおける制限等長性、ヌル空間特性、および関連概念の計算複雑性」IEEE Transactions on Information Theory . 60 (2): 1248–1259. arXiv : 1205.2081 . CiteSeerX 10.1.1.760.2559 . doi :10.1109/TIT.2013.2290112. S2CID  2788088.  
  3. ^ Moghaddam, Baback; Weiss, Yair; Avidan, Shai (2007-09-07). Schölkopf, Bernhard; Platt, John; Hofmann, Thomas (編). Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference. The MIT Press. pp.  915– 922. doi :10.7551/mitpress/7503.001.0001. ISBN 978-0-262-25691-9。
  4. ^ Zou, Hui; Trevor, Hastie; Tibshirani, Robert (2006-06-01). 「スパース主成分分析」 . Journal of Computational and Graphical Statistics . 15 (2): 265– 286. doi :10.1198/106186006X113430. ISSN  1061-8600.
  5. ^ Hui Zou; Trevor Hastie; Robert Tibshirani (2006). 「スパース主成分分析」（PDF） . Journal of Computational and Graphical Statistics . 15 (2): 262– 286. CiteSeerX 10.1.1.62.580 . doi :10.1198/106186006x113430. S2CID  5730904.  
  6. ^ Fan Chen; Karl Rohe (2021). 「スパース主成分分析の新たな基礎」. Journal of Computational and Graphical Statistics . 33 (2): 421– 434. arXiv : 2007.00596 . doi :10.1080/10618600.2023.2256502.
  7. ^ ab Alexandre d'Aspremont; Laurent El Ghaoui; Michael I. Jordan; Gert RG Lanckriet (2007). 「半正定値計画法を用いたスパースPCAの直接定式化」(PDF) . SIAM Review . 49 (3): 434– 448. arXiv : cs/0406021 . doi :10.1137/050645506. S2CID  5490061.
  8. ^ Michel Journee、Yurii Nesterov、Peter Richtarik、Rodolphe Sepulchre (2010). 「一般化電力法によるスパース主成分分析」(PDF) . Journal of Machine Learning Research . 11 : 517–553 . arXiv : 0811.4724 . Bibcode :2008arXiv0811.4724J. CORE Discussion Paper 2008/70.
  9. ^ Peter Richtarik、Majid Jahani、S. Damla Ahipasaoglu、Martin Takac (2021). 「交代最大化：8つのスパースPCA定式化と効率的な並列コードのための統合フレームワーク」. Optimization and Engineering . 22 (3): 1493– 1519. arXiv : 1212.4137 . doi :10.1007/s11081-020-09562-3. S2CID  2549610.
  10. ^ Baback Moghaddam、Yair Weiss、Shai Avidan (2005). 「スパースPCAのスペクトル境界：正確なアルゴリズムと貪欲アルゴリズム」(PDF) .ニューラル情報処理システムの進歩. 第18巻. MITプレス.
  11. ^ Lauren Berk; Dimitris Bertsimas (2019). 「証明可能に最適なスパース主成分分析」.数理計画法計算. 11 (3). Springer: 381– 420. doi :10.1007/s12532-018-0153-6. hdl : 1721.1/131566 . S2CID  126998398.
  12. ^ Yue Guan; Jennifer Dy (2009). 「スパース確率主成分分析」(PDF) . Journal of Machine Learning Research Workshop and Conference Proceedings . 5 : 185.
  13. ^ Hui Zou; Lingzhou Xue (2018). 「スパース主成分分析の選択的概要」. Proceedings of the IEEE . 106 (8): 1311– 1320. doi : 10.1109/jproc.2018.2846588 .
  14. ^ Dimitris Bertsimas、Ryan Cory-Wright (2020). 「半正定値最適化問題の多面体および2次円錐分解について」. Operations Research Letters . 48 (1). Elsevier: 78–85 . arXiv : 1910.03143 . doi : 10.1016/j.orl.2019.12.003 .
  15. ^ Quentin Berthet; Philippe Rigollet (2013). 「高次元におけるスパース主成分の最適検出」Annals of Statistics . 41 (1): 1780– 1815. arXiv : 1202.5070 . doi :10.1214/13-aos1127. S2CID  7162068.
  16. ^ [1] https://cran.r-project.org/web/packages/amanpg/index.html
  17. ^ [2] https://cran.r-project.org/web/packages/elasticnet/index.html
  18. ^ [3] https://cran.r-project.org/web/packages/epca/index.html
  19. ^ [4] https://cran.r-project.org/web/packages/nsprcomp/index.html
  20. ^ [5] http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.SparsePCA.html
Retrieved from "https://en.wikipedia.org/w/index.php?title=Sparse_PCA&oldid=1332584994"