Reducción de dimensión escalable

9

Teniendo en cuenta la cantidad constante de características, Barnes-Hut t-SNE tiene una complejidad de , las proyecciones aleatorias y PCA tienen una complejidad de hace "asequibles" para conjuntos de datos muy grandes.O(nlog⁡n)O(n)

Por otro lado, los métodos que se basan en el escalamiento multidimensional tienen una complejidad .O(n2)

¿Existen otras técnicas de reducción de dimensiones (aparte de las triviales, como mirar las primeras columnas, por supuesto) cuya complejidad es menor que ?kO(nlog⁡n)

pca dimensionality-reduction large-data multidimensional-scaling tsne RUser4512
fuente

Respuestas:

5

Una opción interesante sería explorar la reducción de la dimensionalidad basada en los nervios. El tipo más comúnmente utilizado de red para la reducción de dimensionalidad, la autoencoder, puede ser entrenado a costa de , donde i representa el iteraciones de entrenamiento (es una hiper-parámetro independiente de los datos de entrenamiento). Por lo tanto, la complejidad del entrenamiento se simplifica a O ( n ) .O(yo⋅norte)yoO(norte)

Puede comenzar por echar un vistazo al trabajo del seminario de 2006 de Hinton y Salakhutdinov [1]. Desde entonces, las cosas han evolucionado mucho. Ahora, la mayoría de la atención se logra mediante Autoencoders Variacionales [2], pero la idea básica (una red que reconstruye la entrada en su capa de salida con una capa de cuello de botella en el medio) sigue siendo la misma. Tenga en cuenta que, a diferencia de PCA y RP, los codificadores automáticos realizan una reducción de dimensionalidad no lineal. Además, a diferencia de t-SNE, los codificadores automáticos pueden transformar muestras invisibles sin la necesidad de volver a entrenar todo el modelo.

En el aspecto práctico, recomiendo echar un vistazo a esta publicación , que brinda detalles sobre cómo implementar diferentes tipos de codificadores automáticos con la maravillosa biblioteca Keras.

[1] Hinton, GE y Salakhutdinov, RR (2006). Reducción de la dimensionalidad de los datos con redes neuronales. ciencia, 313 (5786), 504-507.

[2] Kingma, DP y Welling, M. (2013). Bayes variacionales de codificación automática. preimpresión de arXiv arXiv: 1312.6114.

Daniel López
fuente
1
técnicamente no tiene que volver a entrenar el modelo para nuevas muestras con t-SNE utilizando este enfoque particular: lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
bibliolytic
Seguro. El autor también sugirió capacitar a un regresor multivariado para predecir la ubicación del mapa de muestras de datos de entrada como un enfoque potencial. En el artículo menciona que el autor entrena una red neuronal para minimizar directamente la pérdida de t-SNE. Sin embargo, en ambos casos debe definir un modelo o función explícitos para asignar puntos de datos al espacio resultante, por lo que tiene que ser lo suficientemente potente (suficientes capas / neuronas) para aprender la incrustación, pero no demasiado para evitar un ajuste excesivo ... sacrifica parte de la usabilidad de t-SNE estándar.
Daniel López
No hay desacuerdo allí, solo creo que es un poco impreciso contrastar los autoencoders y t-SNE como lo hace en su respuesta, ya que t-SNE puede usarse como una pérdida para la reducción de la dimensionalidad
bibliolítico
O(norte)
O(metro2)metro