¿Cómo hacer SVD y PCA con big data?

Tengo un gran conjunto de datos (alrededor de 8 GB). Me gustaría utilizar el aprendizaje automático para analizarlo. Entonces, creo que debería usar SVD y luego PCA para reducir la dimensionalidad de los datos para la eficiencia. Sin embargo, MATLAB y Octave no pueden cargar un conjunto de datos tan grande.

¿Qué herramientas puedo usar para hacer SVD con una cantidad de datos tan grande?

En primer lugar, la reducción de dimensionalidad se usa cuando tiene muchas dimensiones covariadas y desea reducir el tamaño del problema girando los puntos de datos a una nueva base ortogonal y tomando solo ejes con la mayor varianza. Con 8 variables (columnas), su espacio ya es de baja dimensión, es poco probable que reducir el número de variables resuelva problemas técnicos con el tamaño de la memoria, pero puede afectar mucho la calidad del conjunto de datos. En su caso concreto, es más prometedor echar un vistazo al aprendizaje en líneamétodos En términos generales, en lugar de trabajar con todo el conjunto de datos, estos métodos toman una pequeña parte de ellos (a menudo denominados "mini lotes") a la vez y construyen un modelo de forma incremental. (Personalmente, me gusta interpretar la palabra "en línea" como una referencia a una fuente de datos infinitamente larga de Internet, como un feed de Twitter, donde simplemente no se puede cargar todo el conjunto de datos a la vez).

Pero, ¿qué pasaría si realmente quisiera aplicar la técnica de reducción de dimensionalidad como PCA a un conjunto de datos que no cabe en una memoria? Normalmente, un conjunto de datos se representa como una matriz de datos X de tamaño n x m , donde n es el número de observaciones (filas) ym es el número de variables (columnas). Por lo general, los problemas con la memoria provienen solo de uno de estos dos números.

Demasiadas observaciones (n >> m)

Cuando tiene demasiadas observaciones , pero el número de variables es de pequeño a moderado, puede construir la matriz de covarianza de forma incremental . De hecho, la PCA típica consiste en construir una matriz de covarianza de tamaño m x m y aplicarle una descomposición de valor singular. Con m = 1000 variables de tipo float64, una matriz de covarianza tiene un tamaño de 1000 * 1000 * 8 ~ 8Mb, que cabe fácilmente en la memoria y puede usarse con SVD. Por lo tanto, solo necesita construir la matriz de covarianza sin cargar todo el conjunto de datos en la memoria, tarea bastante manejable .

Alternativamente, puede seleccionar una pequeña muestra representativa de su conjunto de datos y aproximar la matriz de covarianza . Esta matriz tendrá las mismas propiedades que lo normal, solo que un poco menos precisa.

Demasiadas variables (n << m)

Por otro lado, a veces, cuando tiene demasiadas variables , la matriz de covarianza en sí misma no cabe en la memoria. Por ejemplo, si trabaja con imágenes de 640x480, cada observación tiene 640 * 480 = 307200 variables, lo que da como resultado una matriz de covarianza de 703 Gb. Eso definitivamente no es lo que le gustaría tener en la memoria de su computadora, o incluso en la memoria de su clúster. Por lo tanto, debemos reducir las dimensiones sin construir una matriz de covarianza.

Mi método favorito para hacerlo es la proyección aleatoria . En resumen, si tiene un conjunto de datos X de tamaño n x m , puede multiplicarlo por una matriz aleatoria dispersa R de tamaño m x k (con k << m ) y obtener una nueva matriz X ' de un tamaño mucho menor n x k con aproximadamente las mismas propiedades que el original. Por que funciona Bueno, debe saber que PCA tiene como objetivo encontrar un conjunto de ejes ortogonales (componentes principales) y proyectar sus datos en el primer kde ellos. Resulta que los vectores aleatorios dispersos son casi ortogonales y, por lo tanto, también pueden usarse como una nueva base.

Y, por supuesto, no tiene que multiplicar todo el conjunto de datos X por R : puede traducir cada observación x a la nueva base por separado o en mini lotes.

También hay un algoritmo algo similar llamado Random SVD . No tengo ninguna experiencia real con él, pero puedes encontrar un código de ejemplo con explicaciones aquí .

Como conclusión, aquí hay una breve lista de verificación para la reducción de dimensionalidad de grandes conjuntos de datos:

1. Si no tiene tantas dimensiones (variables), simplemente use algoritmos de aprendizaje en línea.
2. Si hay muchas observaciones, pero un número moderado de variables (la matriz de covarianza encaja en la memoria), construya la matriz de forma incremental y use SVD normal.
3. Si el número de variables es demasiado alto, use algoritmos incrementales.

No te molestes.

Primera regla de programación, que también se aplica a la ciencia de datos: hacer que todo funcione en un pequeño problema de prueba.

entonces tome una muestra aleatoria de sus datos de digamos 100,000 filas. pruebe diferentes algoritmos, etc. una vez que tenga todo funcionando a su satisfacción, puede probar conjuntos de datos más grandes (y más grandes) y ver cómo se reduce el error de prueba a medida que agrega más datos.

además, no desea aplicar svd a solo 8 columnas: lo aplica cuando tiene muchas columnas.

PCA generalmente se implementa calculando SVD en la matriz de covarianza.

Calcular la matriz de covarianza es una tarea vergonzosamente paralela , por lo que se escala de forma lineal con el número de registros y es trivial de distribuir en varias máquinas.

Simplemente haga una pasada sobre sus datos para calcular los medios. Luego, una segunda pasada para calcular la matriz de covarianza. Esto se puede hacer con map-reduce fácilmente, esencialmente es lo mismo que calcular los medios nuevamente. ¡Los términos de suma como en covarianza son triviales para paralelizar! Es posible que solo tenga que prestar atención a los números al sumar muchos valores de magnitud similar.

Las cosas se ponen diferentes cuando tienes una gran cantidad de variables . Pero en un sistema de 8 GB, debería poder ejecutar PCA en hasta 20.000 dimensiones en memoria con las bibliotecas BLAS. Pero entonces puede encontrarse con el problema de que PCA ya no es tan confiable, porque tiene demasiados grados de libertad. En otras palabras: se sobrepone fácilmente. He visto la recomendación de tener al menos 10 * d * d registros (o fue d ^ 3). Entonces, para 10000 dimensiones, debe tener al menos mil millones de registros (de 10000 dimensiones ... ¡eso es mucho!) Para que el resultado sea estadísticamente confiable.

Aunque probablemente pueda encontrar algunas herramientas que le permitirán hacerlo en una sola máquina, está entrando en el rango en el que tiene sentido considerar herramientas de "grandes datos" como Spark, especialmente si cree que su conjunto de datos podría crecer. Spark tiene un componente llamado MLlib que admite PCA y SVD. La documentación tiene ejemplos .

Implementamos SVD en un conjunto de datos más grande usando PySpark. También comparamos la consistencia en diferentes paquetes. Aquí está el enlace.

Recomendaría Python si evalúas perezosamente el archivo, tendrás una huella de memoria minúscula, y numpy / scipy te dará acceso a todas las herramientas que tendría Octave / Matlab.