Detalles de la derivación e implementación de algoritmo básico para la reducción de dimensionalidad con PCA

    

Details on the algorithm for dimensionality reduction via Principal Components Analysis

 

Detalhes da derivação e implementação do algoritmo básico para redução de dimensionalidade com PCA

 

 

 

 

 

 

 

 

 

 

Correspondencia: zenaida.castillo@espoch.edu.ec    

    

 

 

Ciencias Técnicas y Aplicadas

Artículo de Investigación

                                                                         

*Recibido: 04 de enero de 2022 *Aceptado: 31 de enero de 2022 * Publicado: 21 de febrero de 2022

 

 

1. Escuela Superior Politécnica de Chimborazo (ESPOCH), Facultad de Ciencias, Escuela de Matemática, Grupo CIDED, Riobamba, Ecuador.
2. Universidad de Investigación de Tecnología Experimental Yachay, Escuela de Ciencias Matemáticas y Computacionales, Urcuquí, 060150, Ecuador.
3. Escuela Superior Politécnica de Chimborazo (ESPOCH), Facultad de Ciencias, Escuela de Matemática, Grupo CIDED, Riobamba, Ecuador.
4. Escuela Superior Politécnica de Chimborazo (ESPOCH), Facultad de Administración y Empresas, Escuela de Finanzas, Grupo CIDED, Riobamba, Ecuador.

 

Resumen                                                             

Los problemas que requieren de análisis de datos, a menudo son difíciles de resolver, debido principalmente a la cantidad de variables involucradas en el modelo matemático. Los científicos de datos generalmente trabajan con millones de variables para hacer estimaciones que soportan decisiones importantes. En el procesamiento digital de imágenes, por ejemplo, el número de puntos que representan pixeles en tres dimensiones podría muy grande en imágenes a color. En estos casos, el costo computacional que requiere el manejo de estos datos puede resultar inaceptable, y la reducción de dimensionalidad de estos datos se hace necesaria. Aún cuando se cuente con la tecnología adecuada, la reducción en tiempo de cómputo siempre es deseable. El manejo de datos con alta dimensionalidad, el análisis y la interpretación se dificulta y en el caso de imágenes, su visualización podría verse afectada considerando las limitaciones de memoria. En la mayoría de los casos, estos datos son redundantes, y la información importante puede revelarse con solo parte de los mismos. La reducción de dimensionalidad es el proceso mediante el cual se descarta parte de la data que no aporta información relevante; y uno de los métodos más usados en todos los ámbitos es el análisis de componentes principales, o PCA, el cual se basa en el cálculo de algunos autovalores de la matriz de covarianzas de los datos. En este trabajo revisamos las herramientas matemáticas detrás del análisis del PCA, y detallamos los pasos de un algoritmo para reducir dimensionalidad que luego es implementado en Matlab. Se presenta también un ejemplo de aplicación para ilustrar el proceso.

Palabras claves: PCA; Reducción de dimensionalidad; Autovalores; Análisis de datos.

 

Abstract

In data analysis, we often deal with millions of variables to make estimations for decisions. Also, in digital image processing the number of data points representing pixels in three dimensions could become very large for color images. In all these cases computational costs for solving associated problems could not be affordable, and a reduction of dimensionality it is necessary. When working with high dimensional data, analysis and interpretation of results is difficult, and visualization of images could be prohibited in terms of memory. Frequently the data contains redundancy, and the important information can be found just with part of the data. In a color image, for example, with four channels, red, blue, green and grey-scale channel, one could combine the first three channels to get the information of the gray-scale channel. Dimensional reduction is a technique that allow us to work with a reduced part of the data without lost losing important information, and one of the methods used for dimensional reduction is the principal analysis component or PCA, which is based in the computation of a few eigenvalues of the covariance matrix. In this work we review the math tools and the steps to generate a classical algorithm for dimensionality reduction using PCA. We present mathematical elements and concepts involved in a principal component analysis algorithm for the projection of high dimensional data in a lower dimensional subspace. A practical example is presented to show how these mathematical tools work together to produce similar results in lower dimensional spaces.

Keywords: PCA; Dimensionality reduction; Eigenvalues; Data analysis.

 

Resumo

Problemas que requerem análise de dados são muitas vezes difíceis de resolver, principalmente devido ao número de variáveis ​​envolvidas no modelo matemático. Os cientistas de dados normalmente trabalham com milhões de variáveis ​​para fazer estimativas que apoiam decisões importantes. No processamento digital de imagens, por exemplo, o número de pontos representando pixels em três dimensões pode ser muito grande em imagens coloridas. Nesses casos, o custo computacional necessário para lidar com esses dados pode ser inaceitável, e a redução da dimensionalidade desses dados torna-se necessária. Mesmo quando a tecnologia apropriada está disponível, a redução do tempo de computação é sempre desejável. O manuseio de dados com alta dimensionalidade, análise e interpretação é difícil e, no caso de imagens, sua visualização pode ser afetada por limitações de memória. Na maioria dos casos, esses dados são redundantes e informações importantes podem ser reveladas apenas com parte deles. A redução de dimensionalidade é o processo pelo qual parte dos dados que não fornecem informações relevantes é descartada; e um dos métodos mais utilizados em todas as áreas é a análise de componentes principais, ou PCA, que se baseia no cálculo de alguns autovalores da matriz de covariância dos dados. Neste artigo, revisamos as ferramentas matemáticas por trás da análise de PCA e detalhamos as etapas de um algoritmo para reduzir a dimensionalidade que é implementado no Matlab. Um exemplo de aplicação também é apresentado para ilustrar o processo.

Palavras-chave: PCA; Redução de dimensionalidade; Autovalores; Analise de dados.

 

Introducción

La reducción de dimensionalidad no es más que la determinación de un número de variables mínimo con el cual se puedan representar los datos, y consiste en eliminar variables que no sean relevantes o que no aporten suficiente información. Actualmente existen técnicas o algoritmos para hacer esta tarea, la cual ha pasado a ser una actividad obligada en disciplinas como la ciencia de datos, una vez que simplifica el manejo de los datos y al mismo tiempo reduce el costo computacional en tiempo de procesamiento y utilización de memoria. Una técnica usada para reducir la dimensionalidad es eficiente mientras logra esta reducción de costos al mismo tiempo que mantiene una buena representación del modelo.

En la actualidad muchas aplicaciones dependen del manejo apropiado de datos, y a menudo los datos suelen presentarse en muchas dimensiones, dependiendo de la cantidad de variables involucradas, que en principio se justifican para la toma de decisiones; por lo tanto se espera que al tener representación en muchas dimensiones la información sea más completa. Sin embargo, el manejo y la interpretación de los datos se hace más complicado, sin contar el costo computacional que a veces es imposible de afrontar, véase por ejemplo (James, 2013)

La reducción de dimensionalidad explota la estructura del problema respetando la correlación entre variables, lo cual permite un manejo más eficiente de los datos sin pérdida de la información relevante.

Este trabajo está orientado a describir en forma simple para lectores que se inician en el tópico, las herramientas matemáticas que se usan en el proceso de la reducción lineal de dimensionalidad a través del análisis de componentes principales o PCA (por sus siglas en inglés).  Se mostrará la derivación y posterior implementación en Matlab del algoritmo clásico que define esta técnica para el análisis de datos.

En las próximas secciones estaremos definiendo conceptos básicos asociados al análisis de datos a través de la estadística, con el objetivo de identificar el aporte del análisis de componentes principales al manejo eficiente y significativo de datos con altas dimensiones.

 

Medidas estadísticas empíricas de los datos

Generalmente, el manejo de los datos, a través de una muestra de ellos, a fin de obtener información de interés, comienza por establecer parámetros estadísticos como la media y la varianza, que nos dan información sobre la dispersión de los datos. En esta sección se presentan estos conceptos que miden la variabilidad de los datos. Comenzaremos considerando datos en una dimensión (1D) y luego extenderemos los conceptos a dos 2D o más dimensiones.

Sea , un conjunto de datos u observaciones en una dimensión donde cada  , se define la media del conjunto como:

En este caso, cada x_i representa una característica o variable que se desea estudiar.

La varianza se define como:

En algunas aplicaciones se divide por  para que sea insesgado.

La varianza, como estadístico de dispersión, mide la variabilidad de los datos de su medida central o media aritmética. Una medida que suele darnos más información sobre los datos es la desviación estándar s, o la raíz cuadrada de la varianza, la cual indica el rango de la variabilidad en los datos. La desviación estándar se indica en las mismas unidades de la media, mientras que la varianza se especifica en unidades al cuadrado por lo que no es tan fácil conjeturar sobre la información que brinda.

Se entiende por población a un conjunto bien definido de elementos; por ejemplo, los habitantes de una comunidad o los estudiantes de una Universidad. Si por cada elemento de una población se mide un conjunto de variables estaremos hablando de estadística multivariante, y los estadísticos como la media y la varianza se extienden apropiadamente. Por ejemplo, en el caso de los estudiantes de una Universidad pudiéramos recoger datos como la edad, género, promedio de calificaciones, carrera que cursa, etc., y por cada estudiante obtener esta información con el fin de analizarla para tomar alguna decisión gerencial.

Cada característica o variable puede tomar valores cuantitativos o cualitativos; sin embargo, en la práctica los variables cualitativas como color o género podrán representarse en una escala numérica; de esta manera si tenemos n individuos y medimos k características o variables podemos utilizar una matriz para representar estos datos:

Donde   es el vector que representa las características del i-ésimo individuo. En este caso tendremos un vector de medias con k componentes, cada una representando la media de los valores de la variable respectiva.

La dispersión o variabilidad de los datos en el caso multivariable puede ser analizada a través de las relaciones lineales entre las variables y representada mediante una matriz llamada matriz de varianzas y covarianzas, o simplemente matriz de covarianza.

Las entradas de la diagonal de esta matriz son las varianzas de cada variable, mientras que las entradas fuera de la diagonal son las covarianzas o los indicadores bivariantes. La entrada S_ij (i ≠ j) de esta matriz mide la variación conjunta de las variables x_i, y x_j; si S_ij es positiva significa que a valores altos/bajos de la variable xi podemos esperar valores altos/bajos de xi. Si el valor de S_ij es negativo significa que la covariación es en sentido inverso. Si la covarianza es cero no se puede establecer una relación entre la variabilidad e las variables.

El cálculo de S también puede realizarse como:

Para efectos prácticos es importante reconocer que la matriz S es simétrica y semidefinida positiva, lo cual garantiza, entre otras cosas, que:

1. Para cualquier vector  de.
2. Todos los autovalores de  son positivos o cero.

La covarianza de dos variables x, y, con medias  ,   respectivamente, puede calcularse directamente como:

Cuando los datos están centrados alrededor de la media, la esperanza o valor esperado de la variable aleatoria es E[x]=0. En este caso la matriz de covarianzas es:

Otro estadístico importante que señala en qué proporción una variable y está explicada por la influencia lineal de otra variable x, es el coeficiente de correlación lineal, denotado por

El coeficiente de correlación lineal toma valores en [-1,1], si se dice que las variables están directamente relacionadas si una crece/decrece la otra crece/decrece; y si , la relación es contraria, si una crece/decrece la otra decrece/crece. Cuando  decimos que las variables no están correlacionadas.

Una explicación detallada de estos estadísticos con ejemplos incluidos puede ser hallada en (Salazar, 2017, Rencher, 1994).

 

Transformaciones lineales de los datos

En muchas aplicaciones se desea conocer lo que pasa con estos estadísticos si a los datos se les suma una cantidad o si se multiplican por un escalar; es decir, si son sometidos a transformaciones de desplazamiento o de compresión/estiramiento. Para analizar matemáticamente esta situación, consideremos un conjunto de datos , donde

 (1-dimensión),  ,  y  .

Si cada  se modifica como ,   con para a  y  c dados, entonces,

E[D] + c  Þ 

Ilustremos este resultado con un ejemplo, sea ,  y tomemos . Entonces

2   y.

.

.

Una situación similar se presenta con la varianza.

V[D]   Þ 

Ejemplificamos estas propiedades con los datos del ejemplo anterior.

2/3,.

.

.

El detalle de estas propiedades y su deducción puede ser hallado en (De la Puente, 2018, Rencher 1994).

 

Algunos conceptos de espacios vectoriales

A continuación revisamos brevemente conceptos del álgebra lineal, dentro del tópico de espacios vectoriales, cuyo entendimiento nos permitirá entender cómo proyectar en espaciós de menor dimensión.

 

Producto escalar:  Sean   y   dos vectores de  , se define su producto escalar o producto punto como:

.

El producto escalar es un producto interior, o producto interno, este último definido como una función que toma dos elementos de un espacio vectorial V y devuelve un número real, usualmente se denota como , y satisface las siguientes propiedades:

1. Simetría: para todo par de vectores x, y se cumple que  .
2. Definida positiva: Para     se cumple que  , y .
3. Bilineal: Para toto ,  y   se cumple que:
• 
• 

La norma de un vector x está vinculada al producto interno , y podría ser diferente para dos funciones que definan productos internos distintos. Por ejemplo, en  tomando dos vectores genéricos   pudiéramos definir el siguiente producto interno:

Una inspección de esta función nos hará concluir que en efecto satisface las propiedades I, II y III, mencionadas previamente, que definen un producto interno.  En este producto interno, la longitud del vector  será = 1, mientras que en el producto punto

= 2.

Otro ejemplo de funciones que definen un producto interno es la covarianza, que por definición es bilineal, simétrica y definida positiva.

De igual manera podemos predecir que la distancia entre vectores depende del producto interno que se utilice. Si usamos el producto punto, más generalmente conocido, obtenemos lo que se conoce como la distancia euclídea.

En general, dado un producto interno   la distancia entre dos vectores x, y se define como:

Otro aspecto geométrico a considerar en el análisis de datos es la orientación de los datos, la cual como veremos en la próxima sección puede establecerse mediante direcciones dadas por vectores. Así, la medida del ángulo entre dos vectores puede decirnos qué tan similar son sus direcciones, y esta medida también está relacionada con el producto interno y la norma de los vectores; por ejemplo:

Ortogonalidad: Se dice que dos vectores, distintos de cero, son ortogonales si su producto interno es cero. Por ejemplo, los vectores    y     son ortogonales ya que su producto escalar es cero; haciendo notar que en el producto interno definido en (1) estos vectores no serían ortogonales ya que

.

Una base de un espacio vectorial V es un conjunto de vectores de V que son linealmente independientes y generan a cualquier otro vector de V a través de alguna combinación lineal. Por ejemplo, en   los conjuntos B₁ y B₂ cumplen con tales requisitos.

La base B1 del ejemplo, conocida como la base canónica de , contiene dos vectores ortogonales entre sí y de norma 1, por lo que decimos que es una base ortonormal de . Existen otras bases con estas características que resultan provechosas cuando se hacen proyecciones a espacios de menor dimensión. Todas las bases de un espacio vectorial tienen el mismo número de vectores, y a este número se le conoce como la dimensión del espacio.  El concepto se puede extender a  y también a espacios vectoriales de funciones.

Una base ortonormal de vectores en  es un subconjunto de n vectores de los cuales son ortogonales dos a dos, y cada uno tiene norma 1. Siempre es posible ortonormalizar vectores linealmente independientes para producir una base ortogonal, por ejemplo mediante el proceso de Gram Schmidt (Lay, 2012, Datta, 2010).

Los subespacios de un espacio vectorial V son subconjuntos propios de V que también son espacios vectoriales y por lo tanto disponen de bases para representar sus elementos.

 

Proyección en espacios de menor dimensión

Los grandes volúmenes de datos, generados por datos con alta dimensionalidad, son difíciles de analizar o de visualizar, por ejemplo, en el caso de las imágenes a colores, que son representadas por una matriz de pixeles, cada uno de los cuales representa 3 dimensiones, una para cada color (rojo, verde y azul), lo que significa que en alta resolución, la compresión y visualización son tareas que requieren de algoritmos eficientes; afortunadamente,  con frecuencia, los datos pueden ser representados con tan solo algunas de las dimensiones.  En particular, los procedimientos para comprimir imágenes utilizan técnicas para reducir su tamaño manteniendo la información más relevante o significativa. La reducción de dimensionalidad está fuertemente ligada al concepto de proyección ortogonal ya que se trata de proyectar la data en un subespacio de menor dimensión en el cual se puedan manejar los datos con mayor facilidad y extraer información relevante a menor costo.

Comencemos mostrando como se proyecta un vector x de  en un subespacio de menor dimensión, por ejemplo una recta con vector director . La recta es un subespacio de dimensión 1 que denotaremos con . La proyección de x sobre U es un vector de U que denotaremos  , la figura 1 ilustra el proceso. 

De acuerdo con la definición, el vector proyección se puede escribir como combinación lineal de los vectores en la base del subespacio U, en este caso la base está formada solo por el vector v, por lo tanto , para algún escalar .

Fig. 1. Proyección en un subespacio de dimensión 1.

 

 

En este caso, la proyección es el vector de U más cercano a x, lo que significa que es mínima y en consecuencia el segmento es ortogonal a v, esto se caracteriza como:

 para algún escalar

Tomando en cuenta que el producto interno es bilineal, inferimos que

Nótese que conociendo los vectores que generan el subespacio U, solo necesitamos el valor de  para obtener la proyección. En el ejemplo, si el vector v, que es la base del subespacio de proyección, tiene norma 1, entonces conseguir la proyección de x en U se reduce a hallar el escalar  = < v, x >, y posteriormente la proyección .

Si usamos el producto punto como producto interno tendremos que

En esta última expresión notamos que el vector   es calculado como el escalar   multiplicado por el vector v; sin embargo, esto es equivalente a calcularlo como el producto de la matriz     por el vector v. A esta matriz P la llamamos matriz de proyección. Nótese que en este caso, sólo necesitamos al escalar  para representar la proyección, lo cual señala el camino hacia la reducción de la dimensionalidad.

 

 

 

Proyección en espacios de gran dimensión

Supongamos ahora que queremos proyectar un vector  de un espacio tridimensional en un subespacio U de dos dimensiones generado por los vectores . Haciendo la analogía con la proyección en un subespacio de una dimensión, el vector proyección será una combinación lineal de .

Adicionalmente, considerando que la proyección ortogonal nos dará la menor distancia, el vector  será ortogonal al plano expandido por  , lo cual significa que es ortogonal a  y a  , ver figura 2.

 

 

 

En términos matriciales, consideremos B la matriz que tiene como columnas a ,  y  sea    el vector de escalares, entonces, las siguientes dos condiciones deben cumplirse:

1)      

 

2)      = 0     y      

 

Sustituyendo (1) en (2) obtenemos

 = 0     y     

 = 0     y     = 0   

 = 0     y       

  

 

Una vez que los vectores  son linealmente independientes, la matriz  es cuadrada de orden 2 con columnas independientes, lo que significa que su inversa existe, y en consecuencia los escalares de la combinación pueden obtenerse como:

Una vez que obtenemos  , la proyección será .

A la matriz  se le conoce como matriz de proyección. Si los vectores columnas de B son ortonormales, entonces    es la matriz identidad y el cálculo de la proyección se reduce a , siendo  la matriz de proyección. En este caso, para representar al vector   de  en el subespacio U basta con tener , cumpliendo con el propósito de reducir la dimensionalidad.

En el caso general de la proyección de un vector n-dimensional en un subespacio U de dimensión k << n, del cual se conoce una base } de vectores ortonormales, la matriz B tendrá como como columnas los vectores ,  y por lo tanto será de , la   será un vector n-dimensional que podrá ser representado por un vector    que es k-dimensional.

Este resultado es la base que sustenta la reducción de dimensionalidad vía análisis de componentes principales.

 

Análisis de Componentes Principales y reducción de dimensionalidad

El análisis de componentes principales (PCA por sus siglas en inglés) es una de las técnicas más usadas para la comprensión y manejo de datos con altas dimensiones. Se ha utilizado por muchos años en el almacenamiento, compresión y visualización, de imágenes, aprovechando la característica de que generalmente las imágenes pueden ser representadas solo con algunas de las direcciones, y que muchas direcciones están altamente correlacionadas.

La siguiente gráfica ilustra la situación en dos dimensiones, en la cual los datos no están necesariamente en la misma recta; sin embargo su variación en un espacio de una dimensión es poco significativa, por lo que bien pudieran ser modelados por la recta que mejor los represente; este último término debe estar bien establecido, por ejemplo podríamos hablar de la recta de mejor ajuste en algún sentido; un modelo sugerido muchas veces es la recta que minimiza los errores cuadráticos en cada punto, sustentado por el método de los mínimos cuadrados lineales. La figura 3 muestra el caso de variables linealmente correlacionadas, en el cual los datos bien pueden ser modelados por una recta.

 

Fig. 3. Correlación lineal entre variables

 

 

Supongamos que tenemos un conjunto de datos X que contiene N vectores , cada uno de ellos representando d características, es decir cada uno es d-dimensional. Hablamos entonces de una muestra de N objetos en un espacio d-dimensional que quisiéramos representar en un espacio k-dimensional de menor dimensión (k << d) de tal forma que esta representación sea lo más similar posible a la muestra original X. El objetivo del análisis de componentes principales es minimizar el error de reconstrucción promedio de las proyecciones ortogonales con respecto a la data original.

Ahora bien, sea } una base ortonormal de un espacio d-dimensional, entonces cada elemento de   , del conjunto de datos, se puede escribir como una combinación lineal de los vectores de la base , esto es, existe un vector de escalares  tal que:

Una vez que   son ortonormales  , con  , lo cual significa que  representa la proyección de  sobre el subespacio unidimensional generado por . Si ahora tomamos dos vectores  de , obtendremos que = [] es una representación de  en un espacio de dos dimensiones. Es claro que con este procedimiento podríamos obtener siempre una representación de los datos en un espacio de menor dimensión, y también pudiéramos reconocer que para un cierto k << n la representación es adecuada.

Con todas estas consideraciones, podríamos seleccionar k vectores de  (k << d) y definir B como la matriz cuyas columnas son los k vectores ortonormales seleccionados, y la proyección del dato  sobre el subespacio U generado por estos k vectores se calcula como  , y puede ser representada por un vector de coordenadas (reconocido como  code)   .

Como hemos dicho anteriormente, la proyección  es un elemento del espacio d-dimensional, y por lo tanto se puede expresar como combinación lineal de los vectores de , .

Sin pérdida de generalidad, asúmanos que los k vectores que generan el subespacio U son los vectores   de  , los cuales son las columnas de la matriz B; entonces

.

 

La primera suma es  la aproximación a los datos en el subespacio U, con ,  y la segunda suma es un vector en el complemento ortogonal de U. Lo que se plantea en el análisis de componentes principales es descartar la segunda suma, tal como lo hemos indicado previamente, y definir al subespacio generado por los vectores  como el subespacio principal, aceptando al vector   como la representación o aproximación de   en el subespacio U de menor dimensión.

Considerando N objetos en el conjunto de datos  el objetivo entonces es hallar el vector de coordenadas   y los vectores  , con  , tal que el error cuadrático de reconstrucción promedio se minimice. Si denotamos   este error de reconstrucción cuando deseamos representar la data a un espacio k-dimensional, el problema consiste en:

 =

Con el propósito de facilitar la notación asumimos que la esperanza del conjunto de datos es cero y que disponemos de una base   de vectores ortonormales en el espacio d-dimensional donde se encuentran los datos, y que para todo n queremos hallar    similar a . 

La medida de similaridad que se plantea es el cuadrado de la distancia euclídea , siendo el objetivo minimizar el promedio de los errores cuadráticos o el error de reconstrucción (Pearson, 1901).

Se plantea entonces un problema de optimización, y para hallar el  óptimo, para un n dado n = 1, …, N, debemos encontrar el conjunto de escalares   y el conjunto de vectores  óptimos, por lo tanto se trata de un problema de optimización multivariable. Una forma simple de lograr este objetivo es hallar primero el conjunto de escalares óptimos dada una base fija de vectores  , y luego hallar los vectores óptimos, que conformarán el subespacio principal.

Una vez que hemos escogido la norma euclídea, como la herramienta para medir la similaridad, el conjunto de escalares óptimos, para un  dado, es aquel que anula las derivadas parciales de  con respecto a cada coordenada en , las cuales son funciones de  , por lo tanto debemos aplicar la regla de la cadena.

Considerando que el error de reconstrucción viene dado por  ,  tenemos que para un dato particular  el término correspondiente en la sumatoria es:

Por lo tanto,

 Ahora bien, una vez que      se deduce que:

Por lo tanto, el valor óptimo para el parámetro   viene dado por:

                    (1)                           

De esta manera, para cada   podemos obtener  reconociendo que el valor óptimo de  coincide con aquel que nos da la proyección ortogonal del elemento    de la data original en el subespacio 1-dimensional generado por el vector .  La generalización de este resultado apoya la propuesta inicial de considerar la proyección ortogonal  como una representación de la de la data original d-dimensional X en el subespacio k-dimensional U (k << d) producido por k-vectores dados. El próximo paso será la escogencia de los vectores que definen el subespacio principal.

 

Tal como quedó establecido en el resultado (1) cada coordenada del vector de escalares para un determinado  se calcula como  , y la proyección se expresa en términos de la combinación lineal   por lo tanto,

La última igualdad en (2) se justifica por la simetría del producto interno.

De igual manera,   se expresa como combinación lineal de todos los vectores de la base , lo cual podemos expresar en términos de dos sumatorias, esto es:

 

Por lo tanto, el error al aproximar    por  , en la medida establecida, es igual a la aproximación que resultaría si usáramos el complemento ortogonal del subespacio principal, y este hecho puede ser usado equivalentemente para hallar la solución óptima, tal como veremos a continuación.

Veamos como reformular la expresión    del error cuadrático promedio que queremos optimizar usando el resultado en (3).

En esta última expresión podemos identificar escalares  que intervienen en una combinación lineal de los vectores  del complemento ortogonal.

Por lo tanto, la norma euclídea al cuadrado no es más que el producto escalar de un vector del complemento ortogonal por si mismo.

En donde   = 0   si      y    = 1   si   ,  por ser estos vectores ortonormales. De esta manera

Luego, sustituyendo este resultado en el objetivo a optimizar, tenemos que:

El último resultado, que obedece a la simetría de del producto interno, y una vez que las sumas son intercambiables, tenemos que:

Podemos identificar en esta nueva expresión del error cuadrático de reconstrucción a la matriz S como la matriz de covarianzas de datos centrados.

Con esta reformulación de , el problema se traduce en hallar los vectores  con j en  del complemento ortogonal al subespacio principal, sujeto a que estos vectores sean ortonormales. Esto lo podemos escribir como:

minimizar  

sujeto a:               con    .

Podemos resolver este problema usando el método de los multiplicadores de Lagrange (ver Thomas, 2005). La función Lagrangiana sería:

.

La solución se hallaría resolviendo el sistema de Lagrange, para lo cual se igualan a cero las derivadas parciales con respecto a cada multiplicador  , y también las derivadas parciales con respecto a los vectores  .

Finalmente, podemos notar, que los vectores que optimizan el error cuadrático promedio son autovectores de la matriz de covarianzas. En este caso, el valor del objetivo estaría dado por:

Así, para saber el valor mínimo de  basta con hallar los d-k autovalores de menor valor de S, que por ser una matriz simétrica y semidefinida positiva tiene autovalores reales no negativos. Sin embargo, los correspondientes autovectores   pertenecen al complemento ortogonal del subespacio principal. Por lo tanto, y los vectores que necesitamos en la base B son los autovectores correspondientes a los k autovalores de mayor valor.

Esto puede apreciarse en la figura 4, que presenta una data en dos dimensiones y señala los dos autovectores de la matriz de covarianzas; se puede observar que el autovector asociado al mayor autovalor (resaltado en rojo) representará la mejor base para la proyección, mientras que el autovector asociado al autovalor de módulo mínimo sugiere la magnitud del error.

 

Fig. 4. Representación del subespacio principal

 

 

Algoritmo básico (reducción de dimensionalidad vía PCA)

Una vez que entendemos cómo obtener la base del espacio de proyección, podemos retomar el cálculo de los escalares (el code) de la combinación lineal que permite construir la proyección para cada dato , con  . Esto nos habilita para definir un algoritmo con los pasos básicos del proceso.

En la solución del problema hemos asumido que la data es centrada, o que la media es cero; solo para disminuir la dificultad en la derivación, pero obtendríamos el mismo resultado con cualquier valor de la media; aunque por cuestiones numérico-computacionales, es preferible restar la media a los datos en este tipo de análisis. Para mayor información sobre estas prácticas y otras técnicas eficientes para implementaciones de PCA se sugiere ver Deisenroth 2020, y James, 2013)

Otra práctica conveniente es normalizar la data; y esto lo hacemos dividiendo en cada dirección por la desviación estándar, lo cual libera la dependencia de unidades y garantiza una varianza unitaria en cada dimensión sin alterar la correlación entre variables.

En resumen, los primeros pasos del algoritmo consisten en centrar y normalizar la data; eso es, por cada punto :

Luego, debemos hallar la matriz de covarianzas S de la data , y calcular los k autovalores de mayor valor. Los k autovectores asociados a estos autovalores formarán las columnas de la matriz de proyección, con la cual finalmente obtenemos la data proyectada.

Implementación en Matlab

A continuación, se presenta un código básico para la reducción de dimensionalidad; en el cual se crea una data aleatoria, que será sujeta a la reducción de dos dimensiones a una dimensión. La salida es el vector de escalares alfa (en este caso un escalar, ya que el subespacio de proyección es unidimensional).

Fig. 5. Código básico en Matlab para PCA

La figura 6 muestra los resultados de la ejecución del código (Fig. 5) para un conjunto N=500 datos aleatorios.

 

Fig. 6.  PCA para reducción de datos de 2 dimensiones a una dimensión

 

 

Esta filosofía puede extenderse al caso general de N datos con d características que se desee proyectar en un espacio de k << d dimensiones; así, seleccionaríamos k autovectores asociados a los k autovalores de mayor valor de la matriz de covarianzas.

Nótese que en el paso 20 del código estamos calculando la descomposición espectral de la matriz que representa a los datos; sin embargo, lo conveniente en la práctica es calcular solo k autovectores asociados a los autovalores de mayor valor, y esto puede hacerse con métodos de proyección para el cálculo de autovalores; lo que sería recomendable en el caso general de aplicaciones con alta dimensionalidad. Para una explicación detallada de estas técnicas se recomienda ver (Trefethen, 1997). Una vez que la matriz S es simétrica y deficiente en rango, una propuesta con cálculo estable sería hallar la descomposición en valores singulares truncada de la matriz X.  El tópico ha sido tratado ampliamente en bibliografías recientes, ver por ejemplo (Deisenroth, 2020).    

                                                                                                                    

Conclusiones

Bajo la suposición de tener un conjunto de N datos  con media 0, en un espacio d-dimensional, y disponer de una base ortogonal de vectores para este espacio, se han descrito en forma detallada los elementos de la matemática que sirven de base para uno de los algoritmos más usado en la reducción de dimensionalidad, como lo es el análisis de componentes principales o PCA. En forma incremental se describieron las bases del algoritmo que soluciona el problema.

El análisis de componentes principales ha sido por muchos años la referencia para hacer reducción de dimensionalidad y existen muchas referencias que lo definen y documentan, generalmente desde perspectivas de alto nivel  de especialización en estadística, o bajo el enfoque de nuevos paradigmas como el aprendizaje automático (o Machine Learning) sin embargo, las herramientas básicas para entender el funcionamiento del algoritmo y programarlo en el lenguaje de programación de preferencia, yacen en el álgebra lineal, por lo que puede ser considerado como una aplicación del álgebra lineal.

Otro esquema de derivación del algoritmo consiste en maximizar la varianza en el subespacio de proyección para retener información de interés (Deisenroth, 2020). El enfoque es elegante pero requiere de elementos más sofisticados ligados a la estadística. En este trabajo hemos querido usar herramientas más básicas de la matemática.

Describimos normas relacionadas con diferentes productos internos, aunque usamos el producto escalar clásico en la derivación del algoritmo, por lo cual queda abierta la posibilidad de generar y comparar con otros algoritmos basados en diferentes normas. De igual manera trabajos para el cálculo efectivo y de bajo costo computacional de los autovalores de módulo máximo de la matriz de covarianza se proponen a futuro.

 

Referencias

1. Datta, B.N (2010). Numerical Linear Algebra and Applications. ‎ Society for Industrial and Applied Mathematics; 2a. Edición.
2. De la Puente, V., C. (2018). Estadística descriptiva e inferencial, Ediciones IDT CB, Madrid, España.
3. Deisenroth, M.P., Faisal, A., Soon, C. (2020). Mathematics for Machine Learning. Cambridge University Press. https://mml-book.com.
4. James, G., Witten, D., Hastie, T., Tibshirani, R. (2013).  An introduction to Statistical learning with applications in R, Springer, New York.
5. Lay, D. (2012). Álgebra lineal y sus aplicaciones. Pearson Education, México.
6. Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(6), 559 – 572
7. Rencher, A.C., Bruce Schaalje G.B. (1996). (2008). Linear models in statistics. Hoboken, N.J: Wiley-Interscience, 6a. Edición.
8. Thomas, G.B. (2005). Cálculo. Varias Variables, Pearson, Addison Wesley, 11a. Edición.
9. Salazar, P., C., Del Castillo, G., S. (2017). Fundamentos Básicos de Estadística, http://www.dspace.uce.edu.ec/handle/25000/13720, 1ª. Edición
10. Trefethen, L. N. & Bau III, D. (1997). Numerical linear algebra. Siam, Philadelphia.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

© 2022 por los autores. Este artículo es de acceso abierto y distribuido según los términos y condiciones de la licencia Creative Commons Atribución-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0)

(https://creativecommons.org/licenses/by-nc-sa/4.0/).