Разреженный PCA

Разреженный анализ главных компонент (SPCA или разреженный PCA) — это метод, используемый в статистическом анализе и, в частности, при анализе многомерных наборов данных. Он расширяет классический метод анализа главных компонентов (PCA) для уменьшения размерности данных путем введения структур разреженности во входные переменные.

Особым недостатком обычного PCA является то, что основные компоненты обычно представляют собой линейные комбинации всех входных переменных. SPCA преодолевает этот недостаток, находя компоненты, которые представляют собой линейные комбинации всего нескольких входных переменных (SPC). Это означает, что некоторые коэффициенты линейных комбинаций, определяющих SPC, называемые нагрузками , равны нулю. Число ненулевых нагрузок называется мощностью СПК.

Математическая формулировка

данных Рассмотрим матрицу , $X$, где каждый из $p$ столбцы представляют собой входную переменную, и каждый из $n$ строки представляют собой независимую выборку из совокупности данных. Предполагается, что каждый столбец $X$ имеет нулевое среднее значение, в противном случае можно вычесть среднее значение по столбцу из каждого элемента $X$.Позволять $\Sigma ={\frac {1}{n-1}}X^{\top }X$ быть эмпирической ковариационной матрицей $X$, который имеет размерность $p\times p$.

Учитывая целое число $k$ с $1\leq k\leq p$, проблему разреженного PCA можно сформулировать как максимизацию дисперсии вдоль направления, представленного вектором $v\in \mathbb {R} ^{p}$ при ограничении его мощности:

${\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 является единичным вектором. Во втором ограничении $\left\Vert v\right\Vert _{0}$ представляет собой $\ell _{0}$ псевдонорма v , которая определяется как количество его ненулевых компонентов. Таким образом, второе ограничение указывает, что количество ненулевых компонентов в v меньше или равно k , которое обычно является целым числом, намного меньшим, чем размерность p . Оптимальное значение уравнения. 1 известен как k -разреженное наибольшее собственное значение .

Если взять k=p , проблема сводится к обычному PCA , и оптимальным значением становится наибольшее собственное значение ковариационной матрицы Σ .

Найдя оптимальное решение v , можно сдуть Σ, чтобы получить новую матрицу

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

и повторите этот процесс, чтобы получить дополнительные основные компоненты. Однако, в отличие от PCA, разреженный PCA не может гарантировать, что различные главные компоненты ортогональны . Для достижения ортогональности необходимо ввести дополнительные ограничения.

Следующее эквивалентное определение дано в матричной форме.Позволять $V$ быть симметричной матрицей p × p , можно переписать разреженную задачу PCA как

${\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 — матричный след , а $\Vert V\Vert _{0}$ представляет ненулевые элементы в матрице V .Последняя строка указывает, что V имеет матричный ранг один и является положительно полуопределенным .Последняя строка означает, что у вас есть $V=vv^{T}$, поэтому уравнение 2 эквивалентно уравнению. 1 .

Более того, ограничение ранга в этой формулировке на самом деле избыточно, и поэтому разреженную PCA можно представить как следующую смешанно-целочисленную полуопределенную программу

${\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 велика. Фактически, проблема разреженной PCA в уравнении. 1 является NP-трудным в сильном смысле.

Вычислительные соображения

Как и большинство разреженных задач, выбор переменных в SPCA представляет собой вычислительно неразрешимую невыпуклую NP-трудную задачу. поэтому для поиска решений требуются жадные неоптимальные алгоритмы.

Алгоритмы для SPCA

несколько альтернативных подходов ( уравнения 1 Было предложено ), в том числе

• модель регрессии,
• система штрафной матричной декомпозиции,
• структура выпуклого релаксации/полуопределенного программирования,
• структура обобщенного степенного метода
• альтернативная структура максимизации
• жадный поиск вперед-назад и точные методы с использованием методов ветвей и границ,
• сертифицированно оптимальный подход ветвей и границ
• Байесовская формулировка.
• Сертифицированно оптимальный смешанно-целочисленный полуопределенный подход ветвей и разрезов

Методологические и теоретические разработки Sparse PCA, а также его применение в научных исследованиях недавно рассматриваются в обзорной статье.

Заметки о релаксации полуопределенного программирования

Было предложено, что разреженный PCA может быть аппроксимирован с помощью полуопределенного программирования (SDP). ограничения с 1 нормой Если отбросить ограничение ранга и ослабить ограничение мощности с помощью выпуклого , мы получим полуопределенное программное расслабление, которое можно эффективно решить за полиномиальное время:

${\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

Во втором ограничении $\mathbf {1}$ представляет собой p × 1 вектор единиц , а |V| элементы которой являются абсолютными значениями элементов V. — матрица ,

Оптимальное решение $V$ к расслабленной задаче (уравнение). 3 не обязательно будет иметь первый ранг. В этом случае $V$ может быть усечен, чтобы сохранить только доминирующий собственный вектор.

Хотя полуопределенная программа не масштабируется за пределы n = 300 ковариат, было показано, что конусная релаксация второго порядка полуопределенной релаксации почти столь же точна и успешно решает проблемы с n = 1000 ковариат.

Приложения

Анализ финансовых данных

Предположим, что обычный PCA применяется к набору данных, где каждая входная переменная представляет собой отдельный актив. Он может генерировать основные компоненты, которые представляют собой взвешенную комбинацию всех активов. Напротив, разреженный PCA будет создавать основные компоненты, которые представляют собой взвешенную комбинацию всего лишь нескольких входных активов, поэтому можно легко интерпретировать его значение. Более того, если использовать торговую стратегию, основанную на этих основных компонентах, меньшее количество активов означает меньшие транзакционные издержки.

Биология

Рассмотрим набор данных, в котором каждая входная переменная соответствует определенному гену. Разреженный PCA может производить основной компонент, включающий лишь несколько генов, поэтому исследователи могут сосредоточиться на этих конкретных генах для дальнейшего анализа.

Многомерная проверка гипотез

Современные наборы данных часто имеют количество входных переменных ( $p$), сравнимое или даже намного превышающее количество выборок ( $n$). Было показано, что если $p/n$ не сходится к нулю, классический PCA несовместен . Другими словами, если мы позволим $k=p$ в уравнении 1 , тогдаоптимальное значение не сходится к наибольшему собственному значению совокупности данных, когда размер выборки $n\rightarrow \infty$, и оптимальное решение не сходится к направлению максимальной дисперсии.Но разреженный PCA может сохранять согласованность, даже если $p\gg n.$

k - разреженное наибольшее собственное значение (оптимальное значение уравнения 1 ) можно использовать для отличия изометрической модели, в которой каждое направление имеет одинаковую дисперсию, от модели с пиковой ковариацией в многомерной обстановке. Рассмотрим проверку гипотезы, в которой нулевая гипотеза указывает, что данные $X$ генерируются из многомерного нормального распределения со средним значением 0 и ковариацией, равной единичной матрице, а альтернативная гипотеза указывает, что данные $X$ генерируется на основе пиковой модели с уровнем сигнала $\theta$:

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

где $v\in \mathbb {R} ^{p}$ имеет только k ненулевых координат. Наибольшее k -разреженное собственное значение может различать две гипотезы тогда и только тогда, когда $\theta >\Theta ({\sqrt {k\log(p)/n}})$.

Поскольку вычисление k -разреженного собственного значения является NP-трудным, его можно аппроксимировать оптимальным значением релаксации полуопределенного программирования ( уравнение 3 ). В этом случае мы можем различить две гипотезы, если $\theta >\Theta ({\sqrt {k^{2}\log(p)/n}})$. Дополнительный ${\sqrt {k}}$ Этот термин не может быть улучшен каким-либо другим алгоритмом с полиномиальным временем, если верна гипотеза о посещенной клике .

Программное обеспечение/исходный код

• amanpg — пакет R для разреженного PCA с использованием метода проксимального градиента чередующегося многообразия
• elasticnet — пакет R для разреженной оценки и разреженной PCA с использованием Elastic-Nets
• epca – пакет R для исследовательского анализа главных компонентов крупномасштабных наборов данных, включая анализ разреженных главных компонентов и аппроксимацию разреженной матрицы.
• nsprcomp — пакет R для разреженного и/или неотрицательного PCA на основе итераций пороговой мощности
• scikit-learn — библиотека Python для машинного обучения, которая содержит Sparse PCA и другие методы в модуле декомпозиции.