Se necesitaría más de un terabyte solo para almacenar una matriz de distancia densa de ese tamaño, utilizando números de coma flotante de doble precisión. Probablemente no sea factible atacar de frente un problema de tan gran escala utilizando un algoritmo MDS estándar. El tiempo de ejecución se escala como $ O (n ^ 3) $, y es posible que ni siquiera pueda ajustar la matriz de distancia en la memoria en una sola máquina. Dependiendo de su situación, es posible que pueda solucionarlo. Cómo hacer esto depende de sus datos y problemas específicos, pero aquí hay algunos ejemplos:
1) PCA es equivalente a MDS clásico usando la métrica de distancia euclidiana. Entonces, si este es el tipo de MDS que desea realizar, puede usar PCA en su lugar. Un requisito adicional es que tenga acceso a los puntos de datos originales como vectores, en lugar de solo la matriz de distancias. Existen muchos algoritmos para ejecutar PCA de manera eficiente en enormes conjuntos de datos.
2) Utilice una forma aproximada de MDS. Este enfoque podría funcionar si desea realizar MDS clásico. No requiere una métrica de distancia euclidiana o una representación del espacio vectorial de los datos (el acceso a las distancias es todo lo que se requiere). Landmark MDS es un buen ejemplo. El primer paso es elegir un conjunto más pequeño de 'puntos de referencia' que representen el conjunto de datos completo. Estos se pueden obtener simplemente muestreando aleatoriamente los datos, o usando un algoritmo rápido y codicioso para optimizarlos un poco más. La agrupación en clústeres también podría usarse en principio, pero es computacionalmente costosa y no necesaria. La MDS clásica se realiza en los puntos de referencia para incrustarlos en un espacio vectorial. Los resultados clásicos de MDS para los puntos de referencia se utilizan luego para mapear el conjunto de datos completo en el espacio de incrustación. Aunque no se formuló originalmente como tal, resulta que Landmark MDS funciona utilizando la aproximación de Nyström, que es una forma de aproximar los valores propios / vectores propios de una matriz grande utilizando una submatriz más pequeña.
3) Si desea realizar una MDS no clásica, métodos como Landmark MDS no funcionarán. Esto se debe a que las variantes no clásicas de MDS se resuelven de forma iterativa mediante algoritmos de optimización, en lugar de resolver un problema de valor propio. En su lugar, podría funcionar adoptar el siguiente enfoque: a) Seleccione una submuestra representativa de los datos. b) Use el tipo de MDS que elija para incrustar estos puntos en un espacio vectorial. c) Usando los puntos de datos submuestreados como ejemplos, aprenda un mapeo en el espacio de incrustación usando un método de regresión no lineal. Se necesitaría el cuidado adecuado para aprender un buen mapeo, no sobreajustarlo, etc. d) Utilice el mapeo aprendido para obtener una incrustación para todo el conjunto de datos. Recuerdo haber visto un par de artículos que describen este tipo de enfoque como una forma de realizar generalizaciones fuera de muestra para algoritmos de reducción de dimensionalidad no lineal en general. Pero me parece que también podría usarse como una forma de aproximar de manera eficiente MDS no clásica. Es posible que existan soluciones más especializadas; si es así, me encantaría saber de ellos.
4) La paralelización podría usarse para resolver el problema completo si es absolutamente necesario. Por ejemplo, para MDS clásico, podría distribuir bloques de la matriz de distancia entre máquinas, luego usar operaciones matriciales paralelas / distribuidas y eigensolver para realizar MDS. Probablemente se podría imaginar algún esquema para MDS no clásicos. Pero, esto podría ser una empresa considerable, y es muy posible que un MDS aproximado funcione lo suficientemente bien. Entonces, ese es un mejor lugar para comenzar.
Referencias:
De Silva y Tenenbaum (2004). Escala multidimensional escasa utilizando puntos de referencia.
Platt (2005). FastMap, MetricMap y Landmark MDS son todos algoritmos de Nystrom.