El análisis de componentes principales dispersos ( PCA disperso ) es una técnica especializada utilizada en el análisis estadístico y, en particular, en el análisis de conjuntos de datos multivariados . Amplía el método clásico de análisis de componentes principales (PCA) para la reducción de la dimensionalidad de los datos mediante la introducción de estructuras de dispersión en las variables de entrada.
Una desventaja particular del PCA ordinario es que los componentes principales suelen ser combinaciones lineales de todas las variables de entrada. Sparse PCA supera esta desventaja al encontrar combinaciones lineales que contienen solo unas pocas variables de entrada.
Los conjuntos de datos contemporáneos a menudo tienen el número de variables de entrada () comparable o incluso mucho mayor que el número de muestras (). Se ha demostrado que sino converge a cero, el PCA clásico no es consistente . Pero el PCA escaso puede conservar la consistencia incluso si[1]
Formulación matemática
Considere una matriz de datos ,, donde cada uno de los Las columnas representan una variable de entrada, y cada una de las Las filas representan una muestra independiente de la población de datos. Se supone que cada columna de tiene media cero, de lo contrario, se puede restar la media de cada columna de cada elemento de . Dejarser la matriz de covarianza empírica de, que tiene dimensión . Dado un número entero con , el problema de PCA escasa se puede formular maximizando la varianza a lo largo de una dirección representada por el vector mientras restringe su cardinalidad:
- Eq. 1
La primera restricción especifica que v es un vector unitario. En la segunda restricción, representa el pseudo-norma de v , que se define como el número de sus componentes distintos de cero. Entonces, la segunda restricción especifica que el número de componentes distintos de cero en v es menor o igual que k , que normalmente es un número entero mucho más pequeño que la dimensión p . El valor óptimo de Eq. 1 se conoce como el k - valor propio más grande escaso .
Si se toma k = p , el problema se reduce al PCA ordinario y el valor óptimo se convierte en el valor propio más grande de la matriz de covarianza Σ .
Después de encontrar la solución óptima v , se desinfla Σ para obtener una nueva matriz
e iterar este proceso para obtener componentes principales adicionales. Sin embargo, a diferencia de la PCA, la PCA escasa no puede garantizar que los diferentes componentes principales sean ortogonales . Para lograr la ortogonalidad, se deben aplicar restricciones adicionales.
La siguiente definición equivalente está en forma de matriz. Dejarser una matriz simétrica p × p , se puede reescribir el problema de PCA dispersa como
- Eq. 2
Tr es la traza de la matriz yrepresenta los no-cero elementos en la matriz V . La última línea especifica que V tiene rango de matriz uno y es semidefinido positivo . La última línea significa que uno tiene, entonces Eq. 2 es equivalente a la ecuación. 1 .
Además, la restricción de rango en esta formulación es realmente redundante y, por lo tanto, el PCA escaso se puede convertir como el siguiente programa semidefinito de enteros mixtos [2]
- Eq. 3
Debido a la restricción de cardinalidad, el problema de maximización es difícil de resolver con exactitud, especialmente cuando la dimensión p es alta. De hecho, el escaso problema de PCA en Eq. 1 es NP-hard en el sentido fuerte. [3]
Algoritmos para PCA disperso
Se han propuesto varios enfoques alternativos (de la ecuación 1 ), que incluyen
- un marco de regresión, [4]
- una relajación convexa / marco de programación semidefinido, [5]
- un marco de método de poder generalizado [6]
- un marco de maximización alterno [7]
- búsqueda codiciosa hacia adelante y hacia atrás y métodos exactos que utilizan técnicas de ramificación y enlace, [8]
- un enfoque de ramificación y enlace óptimo certificable [9]
- Marco de formulación bayesiano. [10]
- Un enfoque de ramificación y corte semidefinito de enteros mixtos óptimos y certificables [2]
Los desarrollos metodológicos y teóricos de Sparse PCA, así como sus aplicaciones en estudios científicos, se revisaron recientemente en un artículo de encuesta. [11]
Abordaje de regresión a través de lazo (red elástica)
Relajación de programación semidefinida
Se ha propuesto que el PCA disperso puede aproximarse mediante programación semidefinida (SDP). [5] Si se elimina la restricción de rango y se relaja la restricción de cardinalidad mediante una restricción convexa de 1 norma , se obtiene una relajación de programación semidefinida, que se puede resolver de manera eficiente en tiempo polinomial:
- Eq. 3
En la segunda restricción, es un vector p × 1 de unos, y | V | es la matriz cuyos elementos son los valores absolutos de los elementos de V .
La solucion optima al problema relajado Eq. 3 no está garantizado para tener un rango. En ese caso, se puede truncar para retener solo el vector propio dominante.
Si bien el programa semidefinito no escala más allá de n = 300 covariables, se ha demostrado que una relajación de cono de segundo orden de la relajación semidefinita es casi tan ajustada y resuelve con éxito problemas con n = 1000s de covariables [12]
Aplicaciones
Análisis de datos financieros
Suponga que el PCA ordinario se aplica a un conjunto de datos donde cada variable de entrada representa un activo diferente, puede generar componentes principales que son una combinación ponderada de todos los activos. Por el contrario, un PCA disperso produciría componentes principales que son una combinación ponderada de solo unos pocos activos de entrada, por lo que se puede interpretar fácilmente su significado. Además, si se utiliza una estrategia comercial basada en estos componentes principales, menos activos implican menos costos de transacción.
Biología
Considere un conjunto de datos donde cada variable de entrada corresponde a un gen específico. El PCA escaso puede producir un componente principal que involucra solo unos pocos genes, por lo que los investigadores pueden enfocarse en estos genes específicos para un análisis adicional.
Prueba de hipótesis de alta dimensión
Los conjuntos de datos contemporáneos a menudo tienen el número de variables de entrada () comparable o incluso mucho mayor que el número de muestras (). Se ha demostrado que sino converge a cero, el PCA clásico no es consistente . En otras palabras, si dejamosen la ecuación. 1 , entonces el valor óptimo no converge al valor propio más grande de la población de datos cuando el tamaño de la muestra, y la solución óptima no converge en la dirección de la varianza máxima. Pero el PCA escaso puede conservar la consistencia incluso si[1]
El k -valor propio más grande disperso (el valor óptimo de la Ec. 1 ) se puede usar para discriminar un modelo isométrico, donde cada dirección tiene la misma varianza, de un modelo de covarianza con picos en un entorno de alta dimensión. [13] Considere una prueba de hipótesis donde la hipótesis nula especifica que los datos se generan a partir de una distribución normal multivariante con media 0 y covarianza igual a una matriz de identidad, y la hipótesis alternativa especifica que los datos se genera a partir de un modelo con picos con intensidad de señal :
dónde tiene solo k coordenadas distintas de cero. El valor propio k -sparse más grande puede discriminar las dos hipótesis si y solo si.
Dado que calcular k -valor propio disperso es NP-duro, uno puede aproximarlo por el valor óptimo de relajación de programación semidefinida ( Ec. 3 ). En ese caso, podemos discriminar las dos hipótesis si. El adicionalEl término no puede mejorarse con ningún otro algoritmo de tiempo polinómico si se mantiene la conjetura de la camarilla plantada .
Software / código fuente
- elasticnet: paquete R para estimación dispersa y PCA dispersa mediante Elastic-Nets [14]
- nsprcomp: paquete R para PCA disperso y / o no negativo basado en iteraciones de potencia umbral [15]
- Scikit-learn : biblioteca de Python para aprendizaje automático que contiene Sparse PCA y otras técnicas en el módulo de descomposición. [dieciséis]
Referencias
- ^ a b Iain M Johnstone; Arthur Yu Lu (2009). "Sobre consistencia y escasez para el análisis de componentes principales en altas dimensiones" . Revista de la Asociación Estadounidense de Estadística . 104 (486): 682–693. doi : 10.1198 / jasa.2009.0121 . PMC 2898454 . PMID 20617121 .
- ^ a b Dimitris Bertsimas; Ryan Cory-Wright; Jean Pauphilet (2020). "Resolver PCA disperso a gran escala para certificable (casi) óptimo". arXiv : 2005.05195 . Cite journal requiere
|journal=
( ayuda ) - ^ Andreas M. Tillmann; Marc E. Pfetsch (2013). "La complejidad computacional de la propiedad de isometría restringida, la propiedad de espacio nulo y conceptos relacionados en la detección comprimida". Transacciones IEEE sobre teoría de la información . 60 (2): 1248-1259. arXiv : 1205.2081 . CiteSeerX 10.1.1.760.2559 . doi : 10.1109 / TIT.2013.2290112 . S2CID 2788088 .
- ^ Hui Zou; Trevor Hastie; Robert Tibshirani (2006). "Análisis de componentes principales dispersos" (PDF) . Revista de Estadística Computacional y Gráfica . 15 (2): 262–286. CiteSeerX 10.1.1.62.580 . doi : 10.1198 / 106186006x113430 . S2CID 5730904 .
- ^ a b Alexandre d'Aspremont; Laurent El Ghaoui; Michael I. Jordan; Gert RG Lanckriet (2007). "Una formulación directa para PCA dispersa mediante programación semidefinida" (PDF) . Revisión SIAM . 49 (3): 434–448. arXiv : cs / 0406021 . doi : 10.1137 / 050645506 . S2CID 5490061 .
- ^ Michel Journee; Yurii Nesterov; Peter Richtarik; Rodolphe Sepulcher (2010). "Método de potencia generalizada para análisis de componentes principales dispersos" (PDF) . Revista de investigación sobre aprendizaje automático . 11 : 517–553. arXiv : 0811.4724 . Código bibliográfico : 2008arXiv0811.4724J . Documento de debate CORE 2008/70.
- ^ Peter Richtarik; Majid Jahani; S. Damla Ahipasaoglu; Martin Takac (2020). "Maximización alterna: marco unificador para 8 formulaciones de PCA dispersas y códigos paralelos eficientes" . Optimización e Ingeniería .
- ^ Baback Moghaddam; Yair Weiss; Shai Avidan (2005). "Límites espectrales para PCA dispersa: algoritmos exactos y codiciosos" (PDF) . Avances en sistemas de procesamiento de información neuronal . 18 . Prensa del MIT.
- ^ Lauren Berk; Dimitris Bertsimas (2019). "Análisis de componentes principales dispersos óptimos y certificables". Computación de programación matemática . Saltador. 11 (3): 381–420. doi : 10.1007 / s12532-018-0153-6 . S2CID 126998398 .
- ^ Yue Guan; Jennifer Dy (2009). "Análisis de componentes principales probabilísticos dispersos" (PDF) . Taller de investigación y actas de conferencias de Journal of Machine Learning . 5 : 185.
- ^ Hui Zou; Lingzhou Xue (2018). "Una descripción selectiva del análisis de componentes principales dispersos" . Actas del IEEE . 106 (8): 1311-1320. doi : 10.1109 / jproc.2018.2846588 .
- ^ Dimitris Bertsimas; Ryan Cory-Wright (2020). "Sobre descomposiciones de conos poliédricos y de segundo orden de problemas de optimización semidefinidos" . Cartas de investigación operativa . Elsevier. 48 (1): 78–85. doi : 10.1016 / j.orl.2019.12.003 .
- ^ Quentin Berthet; Philippe Rigollet (2013). "Detección óptima de componentes principales dispersos en alta dimensión". Annals of Statistics . 41 (1): 1780–1815. arXiv : 1202.5070 . doi : 10.1214 / 13-aos1127 . S2CID 7162068 .
- ^ [1] https://cran.r-project.org/web/packages/elasticnet/elasticnet.pdf
- ^ [2] https://cran.r-project.org/package=nsprcomp
- ^ [3] http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.SparsePCA.html