../_images/sphx_glr_plot_compare_methods_0011.png

El aprendizaje múltiple es un enfoque para la reducción de dimensionalidad no lineal. Los algoritmos para esta tarea se basan en la idea de que la dimensionalidad de muchos conjuntos de datos es solo artificialmente alta.

2.2.1. Introducción

Los conjuntos de datos de alta dimensión pueden ser muy difíciles de visualizar. Si bien los datos en dos o tres dimensiones pueden trazarse para mostrar la estructura inherente de los datos, los gráficos de alta dimensión equivalentes son mucho menos intuitivos. Para ayudar a visualizar la estructura de un conjunto de datos, la dimensión debe reducirse de alguna manera.

La forma más sencilla de lograr esta reducción de dimensionalidad es tomando una proyección aleatoria de los datos. Aunque esto permite cierto grado de visualización de la estructura de datos, la aleatoriedad de la elección deja mucho que desear. En una proyección aleatoria, es probable que se pierda la estructura más interesante dentro de los datos.

digits_img projected_img

Para abordar esta preocupación, se han diseñado una serie de marcos de reducción de dimensionalidad lineal supervisados ​​y no supervisados, como el análisis de componentes principales (PCA), el análisis de componentes independientes, el análisis discriminante lineal y otros. Estos algoritmos definen rúbricas específicas para elegir una proyección lineal “interesante” de los datos. Estos métodos pueden ser poderosos, pero a menudo pierden una estructura no lineal importante en los datos.

PCA_img LDA_img

El aprendizaje múltiple se puede considerar como un intento de generalizar marcos lineales como PCA para que sean sensibles a la estructura no lineal de los datos. Aunque existen variantes supervisadas, el típico problema de aprendizaje múltiple no está supervisado: aprende la estructura de alta dimensión de los datos a partir de los datos mismos, sin el uso de clasificaciones predeterminadas.

Ejemplos:

  • Ver Aprendizaje múltiple en dígitos escritos a mano: incrustación lineal local, Isomap … para un ejemplo de reducción de dimensionalidad en dígitos escritos a mano.
  • Ver Comparación de métodos de aprendizaje múltiple para ver un ejemplo de reducción de dimensionalidad en un conjunto de datos de “curva en S” de juguete.

Las múltiples implementaciones de aprendizaje disponibles en scikit-learn se resumen a continuación

2.2.2. Isomap

Uno de los primeros enfoques para el aprendizaje múltiple es el algoritmo Isomap, abreviatura de Isometric Mapping. Isomap puede verse como una extensión del Escalado multidimensional (MDS) o Kernel PCA. Isomap busca una incrustación de menor dimensión que mantenga las distancias geodésicas entre todos los puntos. Isomap se puede realizar con el objeto Isomap.

../_images/sphx_glr_plot_lle_digits_0051.png

2.2.2.1. Complejidad

El algoritmo Isomap consta de tres etapas:

  1. Búsqueda de vecino más cercano. Usos de Isomap BallTree para una búsqueda eficiente de vecinos. El costo es aproximadamente (O[D log(k) N log(N)]), por (k ) vecinos más cercanos de (NORTE) puntos en (D) dimensiones.
  2. Búsqueda de gráfico de ruta más corta. Los algoritmos conocidos más eficientes para esto son Algoritmo de Dijkstra, que es aproximadamente (O[N^2(k + log(N))]), o la Algoritmo de Floyd-Warshall, cual es (O[N^3]). El algoritmo puede ser seleccionado por el usuario con el path_method palabra clave de Isomap. Si no se especifica, el código intenta elegir el mejor algoritmo para los datos de entrada.
  3. Descomposición parcial de valores propios. La incrustación está codificada en los vectores propios correspondientes a la (D) valores propios más grandes de la (N veces N ) kernel de isomap. Para un solucionador denso, el costo es aproximadamente (O[d N^2]). Este costo a menudo se puede mejorar utilizando el ARPACK solucionador. El eigensolver puede ser especificado por el usuario con el eigen_solver palabra clave de Isomap. Si no se especifica, el código intenta elegir el mejor algoritmo para los datos de entrada.

La complejidad general de Isomap es (O[D log(k) N log(N)] + O[N^2(k + log(N))] + O[d N^2]).

  • (NORTE) : número de puntos de datos de entrenamiento
  • (D) : dimensión de entrada
  • (k ) : número de vecinos más cercanos
  • (D) : dimensión de salida

Referencias:

2.2.3. Incrustación localmente lineal

La incrustación localmente lineal (LLE) busca una proyección de menor dimensión de los datos que preserva las distancias dentro de los vecindarios locales. Se puede considerar como una serie de análisis de componentes principales locales que se comparan globalmente para encontrar la mejor integración no lineal.

La incrustación localmente lineal se puede realizar con la función locally_linear_embedding o su contraparte orientada a objetos LocallyLinearEmbedding.

../_images/sphx_glr_plot_lle_digits_0061.png

2.2.3.1. Complejidad

El algoritmo LLE estándar consta de tres etapas:

  1. Búsqueda de vecinos más cercanos. Vea la discusión en Isomap arriba.
  2. Construcción de matriz de peso. (O[D N k^3]). La construcción de la matriz de peso LLE implica la solución de un (k veces k ) ecuación lineal para cada uno de los (NORTE) barrios locales
  3. Descomposición parcial de valores propios. Vea la discusión en Isomap arriba.

La complejidad general de LLE estándar es (O[D log(k) N log(N)] + O[D N k^3] + O[d N^2]).

  • (NORTE) : número de puntos de datos de entrenamiento
  • (D) : dimensión de entrada
  • (k ) : número de vecinos más cercanos
  • (D) : dimensión de salida

Referencias:

2.2.4. Incrustación lineal localmente modificada

Un problema bien conocido con LLE es el problema de regularización. Cuando el número de vecinos es mayor que el número de dimensiones de entrada, la matriz que define a cada vecindario local tiene un rango deficiente. Para abordar esto, LLE estándar aplica un parámetro de regularización arbitrario (r ), que se elige en relación con la traza de la matriz de peso local. Aunque se puede demostrar formalmente que como (r a 0 ), la solución converge a la incrustación deseada, no hay garantía de que se encontrará la solución óptima para (r> 0 ). Este problema se manifiesta en incrustaciones que distorsionan la geometría subyacente del colector.

Un método para abordar el problema de la regularización es utilizar múltiples vectores de peso en cada vecindario. Esta es la esencia de incrustación localmente lineal modificada (MLLE). MLLE se puede realizar con la función locally_linear_embedding o su contraparte orientada a objetos LocallyLinearEmbedding, con la palabra clave method = 'modified'. Requiere n_neighbors > n_components.

../_images/sphx_glr_plot_lle_digits_0071.png

2.2.4.1. Complejidad

El algoritmo MLLE consta de tres etapas:

  1. Búsqueda de vecinos más cercanos. Igual que LLE estándar
  2. Construcción de matriz de peso. Aproximadamente (O[D N k^3] + O[N (k-D) k^2]). El primer término es exactamente equivalente al de LLE estándar. El segundo término tiene que ver con la construcción de la matriz de ponderaciones a partir de múltiples ponderaciones. En la práctica, el costo adicional de construir la matriz de peso MLLE es relativamente pequeño en comparación con el costo de las etapas 1 y 3.
  3. Descomposición parcial de valores propios. Igual que LLE estándar

La complejidad general de MLLE es (O[D log(k) N log(N)] + O[D N k^3] + O[N (k-D) k^2] + O[d N^2]).

  • (NORTE) : número de puntos de datos de entrenamiento
  • (D) : dimensión de entrada
  • (k ) : número de vecinos más cercanos
  • (D) : dimensión de salida

Referencias:

2.2.5. Eigenmapping de Hesse

El mapeo propio de Hessian (también conocido como LLE: HLLE basado en Hessian) es otro método para resolver el problema de regularización de LLE. Gira en torno a una forma cuadrática basada en arpillera en cada vecindario que se utiliza para recuperar la estructura lineal local. Aunque otras implementaciones señalan su escasa escala con el tamaño de los datos, sklearn implementa algunas mejoras algorítmicas que hacen que su costo sea comparable al de otras variantes de LLE para pequeñas dimensiones de producción. HLLE se puede realizar con la función locally_linear_embedding o su contraparte orientada a objetos LocallyLinearEmbedding, con la palabra clave method = 'hessian'. Requiere n_neighbors > n_components * (n_components + 3) / 2.

../_images/sphx_glr_plot_lle_digits_0081.png

2.2.5.1. Complejidad

El algoritmo HLLE consta de tres etapas:

  1. Búsqueda de vecinos más cercanos. Igual que LLE estándar
  2. Construcción de matriz de peso. Aproximadamente (O[D N k^3] + O[N d^6]). El primer término refleja un costo similar al de LLE estándar. El segundo término proviene de una descomposición QR del estimador de arpillera local.
  3. Descomposición parcial de valores propios. Igual que LLE estándar

La complejidad general de HLLE estándar es (O[D log(k) N log(N)] + O[D N k^3] + O[N d^6] + O[d N^2]).

  • (NORTE) : número de puntos de datos de entrenamiento
  • (D) : dimensión de entrada
  • (k ) : número de vecinos más cercanos
  • (D) : dimensión de salida

Referencias:

2.2.6. Incrustación espectral

La incrustación espectral es un método para calcular una incrustación no lineal. Scikit-learn implementa laplacian Eigenmaps, que encuentra una representación de baja dimensión de los datos utilizando una descomposición espectral del gráfico laplaciano. El gráfico generado se puede considerar como una aproximación discreta de la variedad de baja dimensión en el espacio de alta dimensión. La minimización de una función de costo basada en el gráfico asegura que los puntos cercanos entre sí en el colector se mapeen cerca entre sí en el espacio de baja dimensión, preservando las distancias locales. La incrustación espectral se puede realizar con la función spectral_embedding o su contraparte orientada a objetos SpectralEmbedding.

2.2.6.1. Complejidad

El algoritmo de inclusión espectral (mapas propios de Laplacia) consta de tres etapas:

  1. Construcción de gráficos ponderados. Transforme los datos de entrada sin procesar en una representación gráfica utilizando una matriz de afinidad (adyacencia) representación.
  2. Gráfico Construcción Laplaciana. Graph Laplacian no normalizado se construye como (L = D – A ) para y normalizado como (L = D ^ {- frac {1} {2}} (D – A) D ^ {- frac {1} {2}} ).
  3. Descomposición parcial de valores propios. La descomposición de los valores propios se realiza en el gráfico Laplaciano

La complejidad general de la incrustación espectral es (O[D log(k) N log(N)] + O[D N k^3] + O[d N^2]).

  • (NORTE) : número de puntos de datos de entrenamiento
  • (D) : dimensión de entrada
  • (k ) : número de vecinos más cercanos
  • (D) : dimensión de salida

Referencias:

2.2.7. Alineación del espacio tangente local

Aunque técnicamente no es una variante de LLE, la alineación del espacio tangente local (LTSA) es algorítmicamente lo suficientemente similar a LLE que puede incluirse en esta categoría. En lugar de centrarse en preservar las distancias del vecindario como en LLE, LTSA busca caracterizar la geometría local en cada vecindario a través de su espacio tangente y realiza una optimización global para alinear estos espacios tangentes locales para aprender la incrustación. LTSA se puede realizar con la función locally_linear_embedding o su contraparte orientada a objetos LocallyLinearEmbedding, con la palabra clave method = 'ltsa'.

../_images/sphx_glr_plot_lle_digits_0091.png

2.2.7.1. Complejidad

El algoritmo LTSA consta de tres etapas:

  1. Búsqueda de vecinos más cercanos. Igual que LLE estándar
  2. Construcción de matriz de peso. Aproximadamente (O[D N k^3] + O[k^2 d]). El primer término refleja un costo similar al de LLE estándar.
  3. Descomposición parcial de valores propios. Igual que LLE estándar

La complejidad general del estándar LTSA es (O[D log(k) N log(N)] + O[D N k^3] + O[k^2 d] + O[d N^2]).

  • (NORTE) : número de puntos de datos de entrenamiento
  • (D) : dimensión de entrada
  • (k ) : número de vecinos más cercanos
  • (D) : dimensión de salida

Referencias:

2.2.8. Escala multidimensional (MDS)

Escalamiento multidimensional (MDS) busca una representación de baja dimensión de los datos en la que las distancias respeten bien las distancias en el espacio original de alta dimensión.

En general, MDS es una técnica utilizada para analizar datos de similitud o disimilitud. Intenta modelar datos de similitud o disimilitud como distancias en espacios geométricos. Los datos pueden ser calificaciones de similitud entre objetos, frecuencias de interacción de moléculas o índices comerciales entre países.

Existen dos tipos de algoritmo MDS: métrico y no métrico. En scikit-learn, la clase MDS implementa ambos. En Metric MDS, la matriz de similitud de entrada surge de una métrica (y, por lo tanto, respeta la desigualdad triangular), las distancias entre dos puntos de salida se establecen para que estén lo más cerca posible de los datos de similitud o disimilitud. En la versión no métrica, los algoritmos intentarán preservar el orden de las distancias y, por lo tanto, buscarán una relación monótona entre las distancias en el espacio incrustado y las similitudes / disimilitudes.

../_images/sphx_glr_plot_lle_digits_0101.png

Dejar (S) ser la matriz de similitud, y (X) las coordenadas del (norte) puntos de entrada. Disparidades ( hat {d} _ {ij} ) son la transformación de las similitudes elegidas de alguna manera óptima. El objetivo, llamado estrés, se define entonces por ( sum_ {i

2.2.8.1. MDS métrico

La métrica más simple MDS modelo, llamado MDS absoluto, las disparidades se definen por ( hat {d} _ {ij} = S_ {ij} ). Con MDS absoluto, el valor (S_ {ij} ) entonces debe corresponder exactamente a la distancia entre el punto (I) y (j ) en el punto de empotramiento.

Más comúnmente, las disparidades se establecen para ( hat {d} _ {ij} = b S_ {ij} ).

2.2.8.2. MDS no métrico

No métrico MDS se centra en la ordenación de los datos. Si (S_ {ij} , entonces la incrustación debería hacer cumplir (d_ {ij} . Un algoritmo simple para hacer cumplir es usar una regresión monótona de (d_ {ij} ) sobre (S_ {ij} ), produciendo disparidades ( hat {d} _ {ij} ) en el mismo orden que (S_ {ij} ).

Una solución trivial a este problema es establecer todos los puntos en el origen. Para evitar eso, las disparidades ( hat {d} _ {ij} ) están normalizados.

../_images/sphx_glr_plot_mds_0011.png

Referencias:

2.2.9. Incrustación de vecinos estocásticos distribuidos en t (t-SNE)

t-SNE (TSNE) convierte afinidades de puntos de datos en probabilidades. Las afinidades en el espacio original están representadas por probabilidades conjuntas de Gauss y las afinidades en el espacio incrustado están representadas por distribuciones t de Student. Esto permite que t-SNE sea particularmente sensible a la estructura local y tiene algunas otras ventajas sobre las técnicas existentes:

  • Revelar la estructura a muchas escalas en un solo mapa
  • Revelar datos que se encuentran en múltiples, diferentes, múltiples o agrupaciones
  • Reducir la tendencia a agrupar puntos en el centro.

Si bien Isomap, LLE y las variantes son las más adecuadas para desplegar una única variedad continua de baja dimensión, t-SNE se centrará en la estructura local de los datos y tenderá a extraer grupos de muestras locales agrupados como se destaca en el ejemplo de la curva S. Esta capacidad de agrupar muestras en función de la estructura local podría ser beneficiosa para desenredar visualmente un conjunto de datos que comprenda varias variedades a la vez, como es el caso del conjunto de datos de dígitos.

La divergencia Kullback-Leibler (KL) de las probabilidades conjuntas en el espacio original y el espacio incrustado se minimizará mediante el descenso del gradiente. Tenga en cuenta que la divergencia KL no es convexa, es decir, varios reinicios con diferentes inicializaciones terminarán en mínimos locales de la divergencia KL. Por lo tanto, a veces es útil probar diferentes semillas y seleccionar la incrustación con la menor divergencia de KL.

Las desventajas de usar t-SNE son aproximadamente:

  • t-SNE es computacionalmente costoso y puede tomar varias horas en conjuntos de datos de millones de muestras donde PCA terminará en segundos o minutos
  • El método Barnes-Hut t-SNE se limita a incrustaciones bidimensionales o tridimensionales.
  • El algoritmo es estocástico y varios reinicios con diferentes semillas pueden producir diferentes incrustaciones. Sin embargo, es perfectamente legítimo elegir la incrustación con el menor error.
  • La estructura global no se conserva explícitamente. Este problema se mitiga inicializando puntos con PCA (usando init="pca").

../_images/sphx_glr_plot_lle_digits_0131.png

2.2.9.1. Optimización de t-SNE

El objetivo principal de t-SNE es la visualización de datos de alta dimensión. Por lo tanto, funciona mejor cuando los datos se integrarán en dos o tres dimensiones.

Optimizar la divergencia de KL puede ser un poco complicado a veces. Hay cinco parámetros que controlan la optimización de t-SNE y, por lo tanto, posiblemente la calidad de la incrustación resultante:

  • perplejidad
  • factor de exageración temprana
  • tasa de aprendizaje
  • número máximo de iteraciones
  • ángulo (no utilizado en el método exacto)

La perplejidad se define como (k = 2 ^ {(S)} ) dónde (S) es la entropía de Shannon de la distribución de probabilidad condicional. La perplejidad de un (k )-Diseño de caras es (k ), así que eso (k ) es efectivamente el número de vecinos más cercanos que t-SNE considera al generar las probabilidades condicionales. Las perplejidades más grandes conducen a vecinos más cercanos y menos sensibles a las estructuras pequeñas. Por el contrario, una perplejidad menor considera un número menor de vecinos y, por lo tanto, ignora más información global a favor del vecindario local. A medida que el tamaño de los conjuntos de datos aumenta, se requerirán más puntos para obtener una muestra razonable del vecindario local y, por lo tanto, es posible que se requieran mayores perplejidades. De manera similar, los conjuntos de datos más ruidosos requerirán valores de perplejidad más grandes para abarcar suficientes vecinos locales para ver más allá del ruido de fondo.

El número máximo de iteraciones suele ser lo suficientemente alto y no necesita ningún ajuste. La optimización consta de dos fases: la fase de exageración inicial y la optimización final. Durante la exageración inicial, las probabilidades conjuntas en el espacio original se incrementarán artificialmente mediante la multiplicación con un factor dado. Los factores más grandes dan como resultado brechas más grandes entre los conglomerados naturales en los datos. Si el factor es demasiado alto, la divergencia de KL podría aumentar durante esta fase. Por lo general, no es necesario ajustarlo. Un parámetro crítico es la tasa de aprendizaje. Si la pendiente es demasiado baja, el descenso se quedará atascado en un mínimo local malo. Si es demasiado alto, la divergencia de KL aumentará durante la optimización. Se pueden encontrar más consejos en las preguntas frecuentes de Laurens van der Maaten (ver referencias). El último parámetro, el ángulo, es una compensación entre rendimiento y precisión. Los ángulos más grandes implican que podemos aproximar regiones más grandes por un solo punto, lo que conduce a una mejor velocidad pero resultados menos precisos.

“Cómo utilizar t-SNE de forma eficaz” proporciona una buena discusión de los efectos de los distintos parámetros, así como gráficos interactivos para explorar los efectos de diferentes parámetros.

2.2.9.2. Barnes-Hut t-SNE

El t-SNE de Barnes-Hut que se ha implementado aquí suele ser mucho más lento que otros algoritmos de aprendizaje múltiples. La optimización es bastante difícil y el cálculo del gradiente es (O[d N log(N)]), dónde (D) es el número de dimensiones de salida y (NORTE) es el número de muestras. El método de Barnes-Hut mejora el método exacto donde la complejidad de t-SNE es (O[d N^2]), pero tiene otras diferencias notables:

  • La implementación de Barnes-Hut solo funciona cuando la dimensionalidad objetivo es 3 o menos. El caso 2D es típico cuando se construye visualizaciones.
  • Barnes-Hut solo funciona con datos de entrada densos. Las matrices de datos dispersos solo se pueden incrustar con el método exacto o se pueden aproximar mediante una proyección densa de rango bajo, por ejemplo, utilizando TruncatedSVD
  • Barnes-Hut es una aproximación del método exacto. La aproximación se parametriza con el parámetro de ángulo, por lo tanto, el parámetro de ángulo no se utiliza cuando método = “exacto”
  • Barnes-Hut es significativamente más escalable. Barnes-Hut se puede utilizar para incrustar cientos de miles de puntos de datos, mientras que el método exacto puede manejar miles de muestras antes de volverse intratable computacionalmente.

Para fines de visualización (que es el caso de uso principal de t-SNE), se recomienda encarecidamente utilizar el método de Barnes-Hut. El método t-SNE exacto es útil para verificar las propiedades teóricas de la incrustación posiblemente en un espacio dimensional más alto, pero se limita a pequeños conjuntos de datos debido a restricciones computacionales.

También tenga en cuenta que las etiquetas de dígitos coinciden aproximadamente con la agrupación natural encontrada por t-SNE, mientras que la proyección 2D lineal del modelo PCA produce una representación en la que las regiones de etiquetas se superponen en gran medida. Esta es una pista sólida de que estos datos pueden estar bien separados por métodos no lineales que se centran en la estructura local (por ejemplo, una SVM con un kernel RBF gaussiano). Sin embargo, no poder visualizar grupos bien separados etiquetados homogéneamente con t-SNE en 2D no implica necesariamente que los datos no puedan ser clasificados correctamente por un modelo supervisado. Puede darse el caso de que dos dimensiones no sean lo suficientemente bajas para representar con precisión la estructura interna de los datos.

Referencias:

2.2.10. Consejos de uso práctico

  • Asegúrese de que se utilice la misma escala en todas las funciones. Debido a que varios métodos de aprendizaje se basan en una búsqueda del vecino más cercano, el algoritmo puede funcionar mal de otra manera. Ver Escalador estándar para formas convenientes de escalar datos heterogéneos.
  • El error de reconstrucción calculado por cada rutina se puede utilizar para elegir la dimensión de salida óptima. Para (D)-múltiple dimensional incrustado en un (D)-espacio de parámetros dimensionales, el error de reconstrucción disminuirá a medida que n_components se incrementa hasta n_components == d.
  • Tenga en cuenta que los datos ruidosos pueden “provocar un cortocircuito” en el colector, actuando en esencia como un puente entre las partes del colector que, de otro modo, estarían bien separadas. El aprendizaje múltiple sobre datos ruidosos y / o incompletos es un área activa de investigación.
  • Ciertas configuraciones de entrada pueden dar lugar a matrices de peso singulares, por ejemplo, cuando más de dos puntos en el conjunto de datos son idénticos o cuando los datos se dividen en grupos inconexos. En este caso, solver="arpack" no podrá encontrar el espacio nulo. La forma más sencilla de solucionar este problema es utilizar solver="dense" que funcionará en una matriz singular, aunque puede ser muy lento dependiendo del número de puntos de entrada. Alternativamente, se puede intentar comprender la fuente de la singularidad: si se debe a conjuntos disjuntos, aumentar n_neighbors puede ayudar. Si se debe a puntos idénticos en el conjunto de datos, eliminar estos puntos puede ayudar.

Ver también

Incrustación de árboles totalmente aleatorios también puede ser útil para derivar representaciones no lineales del espacio de características, además no realiza reducción de dimensionalidad.