Los mapas de difusión son un algoritmo de reducción de dimensionalidad o extracción de características introducido por Coifman y Lafon [1] [2] [3] [4] que calcula una familia de incrustaciones de un conjunto de datos en el espacio euclidiano (a menudo de baja dimensión) cuyas coordenadas pueden ser calculado a partir de los autovectores y autovalores de un operador de difusión en los datos. La distancia euclidiana entre puntos en el espacio incrustado es igual a la "distancia de difusión" entre distribuciones de probabilidad centradas en esos puntos. A diferencia de los métodos de reducción de dimensionalidad lineal como el análisis de componentes principales (PCA), los mapas de difusión son parte de la familia demétodos de reducción de dimensionalidad no lineal que se centran en descubrir la variedad subyacente de la que se han muestreado los datos. Al integrar similitudes locales a diferentes escalas, los mapas de difusión brindan una descripción global del conjunto de datos. Comparado con otros métodos, el algoritmo del mapa de difusión es robusto a la perturbación de ruido y computacionalmente económico.
Definición de mapas de difusión
Los siguientes mapas de difusión [3] y [5] se pueden definir en cuatro pasos.
Conectividad
Los mapas de difusión explotan la relación entre la difusión de calor y la cadena de Markov de caminata aleatoria . La observación básica es que si damos un paseo aleatorio por los datos, es más probable caminar hacia un punto de datos cercano que caminar hacia otro que está lejos. Dejarser un espacio de medida , donde es el conjunto de datos y representa la distribución de los puntos en .
Basado en esto, la conectividad entre dos puntos de datos, y , se puede definir como la probabilidad de caminar desde a en un paso de la caminata aleatoria. Por lo general, esta probabilidad se especifica en términos de una función del núcleo de los dos puntos:. Por ejemplo, el popular kernel gaussiano:
De manera más general, la función del kernel tiene las siguientes propiedades
( es simétrico)
( es la preservación de la positividad).
El núcleo constituye la definición previa de la geometría local del conjunto de datos. Dado que un kernel determinado capturará una característica específica del conjunto de datos, su elección debe estar guiada por la aplicación que se tenga en mente. Ésta es una diferencia importante con métodos como el análisis de componentes principales , donde las correlaciones entre todos los puntos de datos se tienen en cuenta a la vez.
Dado , entonces podemos construir una cadena de Markov reversible en (un proceso conocido como el gráfico normalizado de construcción laplaciana):
y definir:
Aunque el nuevo kernel normalizado no hereda la propiedad simétrica, sí hereda la propiedad de preservación de positividad y gana una propiedad de conservación:
Proceso de difusión
De podemos construir una matriz de transición de una cadena de Markov () en . En otras palabras, representa la probabilidad de transición de un paso de a , y da la matriz de transición de t-pasos.
Definimos la matriz de difusión (también es una versión del gráfico de matriz laplaciana )
Luego definimos el nuevo kernel
o equivalente,
donde D es una matriz diagonal y
Aplicamos el gráfico de normalización laplaciana a este nuevo kernel:
dónde es una matriz diagonal y
Una de las ideas principales del marco de difusión es que hacer avanzar la cadena en el tiempo (tomando poderes cada vez mayores de ) revela la estructura geométrica de a escalas cada vez mayores (el proceso de difusión). Específicamente, la noción de un grupo en el conjunto de datos se cuantifica como una región en la que la probabilidad de escapar de esta región es baja (dentro de un cierto tiempo t). Por lo tanto, t no solo sirve como parámetro de tiempo, sino que también tiene la doble función de parámetro de escala.
La autodescomposición de la matriz rendimientos
dónde es la secuencia de valores propios de y y son los vectores propios biortogonales derecho e izquierdo, respectivamente. Debido a la disminución del espectro de los valores propios, solo se necesitan unos pocos términos para lograr una precisión relativa dada en esta suma.
Parámetro y el operador de difusión
La razón para introducir el paso de normalización que implica es sintonizar la influencia de la densidad de puntos de datos en la transición infinitesimal de la difusión. En algunas aplicaciones, el muestreo de los datos generalmente no está relacionado con la geometría de la variedad que estamos interesados en describir. En este caso, podemos configurary el operador de difusión se aproxima al operador de Laplace-Beltrami. Luego recuperamos la geometría de Riemann del conjunto de datos independientemente de la distribución de los puntos. Para describir el comportamiento a largo plazo de la distribución de puntos de un sistema de ecuaciones diferenciales estocásticas, podemos usary la cadena de Markov resultante se aproxima a la difusión de Fokker-Planck . Con, se reduce al gráfico clásico normalización laplaciana.
Distancia de difusión
La distancia de difusión en el tiempo entre dos puntos se puede medir como la similitud de dos puntos en el espacio de observación con la conectividad entre ellos. Es dado por
dónde es la distribución estacionaria de la cadena de Markov, dada por el primer vector propio izquierdo de . Explícitamente:
Intuitivamente, es pequeño si hay una gran cantidad de caminos cortos que conectan y . Hay varias características interesantes asociadas con la distancia de difusión, basadas en nuestra discusión anterior que también sirve como parámetro de escala:
- Los puntos están más cerca en una escala determinada (según lo especificado por ) si están muy conectados en el gráfico, lo que enfatiza el concepto de clúster.
- Esta distancia es resistente al ruido, ya que la distancia entre dos puntos depende de todos los posibles caminos de longitud. entre los puntos.
- Desde el punto de vista del aprendizaje automático, la distancia tiene en cuenta todas las evidencias que vinculan a , lo que nos permite concluir que esta distancia es apropiada para el diseño de algoritmos de inferencia basados en la mayoría de preponderancia. [3]
Proceso de difusión e incrustación de baja dimensión
La distancia de difusión se puede calcular utilizando los vectores propios mediante
Entonces, los vectores propios se pueden usar como un nuevo conjunto de coordenadas para los datos. El mapa de difusión se define como:
Debido al decaimiento del espectro, es suficiente usar solo los primeros k autovectores y autovalores. Así obtenemos el mapa de difusión de los datos originales a un espacio k -dimensional que está incrustado en el espacio original.
En [6] se demuestra que
por lo que la distancia euclidiana en las coordenadas de difusión se aproxima a la distancia de difusión.
Algoritmo
El marco de algoritmo básico del mapa de difusión es el siguiente:
Paso 1. Dada la matriz de similitud L .
Paso 2. Normalizar la matriz según parámetro : .
Paso 3. Forme la matriz normalizada .
Paso 4. Calcule los k valores propios más grandes de y los vectores propios correspondientes.
Paso 5. Utilice el mapa de difusión para realizar la incrustación. .
Solicitud
En el artículo, [6] Nadler et. Alabama. mostró cómo diseñar un núcleo que reproduzca la difusión inducida por una ecuación de Fokker-Planck . Además, explicaron que, cuando los datos se aproximan a una variedad, se puede recuperar la geometría de esta variedad calculando una aproximación del operador de Laplace-Beltrami . Este cálculo es completamente insensible a la distribución de los puntos y, por lo tanto, proporciona una separación de las estadísticas y la geometría de los datos. Dado que los mapas de difusión brindan una descripción global del conjunto de datos, pueden medir las distancias entre un par de puntos de muestra en la variedad en la que están incrustados los datos. Las aplicaciones basadas en mapas de difusión incluyen reconocimiento facial , [7] agrupamiento espectral , representación de imágenes de baja dimensión, segmentación de imágenes, [8] segmentación de modelos 3D, [9] verificación del hablante [10] e identificación, [11] muestreo en múltiples, anomalía detección, [12] [13] imagen en pintura, [14] revelando la organización de las redes del estado de reposo del cerebro [15] y así sucesivamente.
Ver también
Referencias
- ^ Coifman, RR; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). "Las difusiones geométricas como herramienta de análisis armónico y definición de estructura de datos: mapas de difusión" . PNAS . 102 (21): 7426–7431. Código bibliográfico : 2005PNAS..102.7426C . doi : 10.1073 / pnas.0500334102 . PMC 1140422 . PMID 15899970 .
- ^ Coifman, RR; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). "Las difusiones geométricas como herramienta de análisis armónico y definición de estructura de datos: métodos multiescala" . PNAS . 102 (21): 7432–7437. Código bibliográfico : 2005PNAS..102.7432C . doi : 10.1073 / pnas.0500896102 . PMC 1140426 . PMID 15899969 .
- ^ a b c Coifman, RR; S. Lafon. (2006). "Mapas de difusión" . Análisis Armónico Computacional y Aplicado . 21 : 5–30. doi : 10.1016 / j.acha.2006.04.006 .
- ^ Lafon, SS (2004). Mapas de difusión y armónicos geométricos (PDF) (PhD). Universidad de Yale.
- ^ De la Porte, J .; Herbst, BM; Hereman, W; Van der Walt, SJ (2008). "Introducción a los mapas de difusión". Actas del XIX Simposio Anual de la Asociación de Reconocimiento de Patrones de Sudáfrica (PRASA) . CiteSeerX 10.1.1.309.674 .
- ^ a b Nadler, Booz; Stéphane Lafon; Ronald R. Coifman; Ioannis G. Kevrekidis (2005). "Mapas de difusión, agrupación espectral y funciones propias de los operadores Fokker-Planck" (PDF) . Avances en sistemas de procesamiento de información neuronal . 18 . arXiv : matemáticas / 0506090 . Bibcode : 2005math ...... 6090N .
- ^ Barkan, Oren; Weill, Jonathan; Wolf, Lior; Aronowitz, Hagai. "Reconocimiento facial rápido de multiplicación de vectores de alta dimensión" (PDF) . Actas de la Conferencia Internacional IEEE sobre Visión por Computador 2013 : 1960–1967.
- ^ Zeev, Farbman; Fattal Raanan; Lischinski Dani (2010). "Mapas de difusión para la edición de imágenes consciente de los bordes". ACM Trans. Gráfico . 29 (6): 145: 1–145: 10. doi : 10.1145 / 1882261.1866171 .
- ^ Oana, Sidi; van Kaick, Oliver; Kleiman, Yanir; Zhang, Hao; Cohen-Or, Daniel (2011). Co-segmentación no supervisada de un conjunto de formas a través de la agrupación espectral del espacio descriptor (PDF) . Transacciones ACM en gráficos .
- ^ Barkan, Oren; Aronowitz, Hagai (2013). "Mapas de difusión para la verificación de hablantes basada en PLDA" (PDF) . Actas de la Conferencia Internacional IEEE sobre Acústica, Habla y Procesamiento de Señales (ICASSP) : 7639–7643.
- ^ Michalevsky, Yan; Talmon, Ronen; Cohen, Israel (2011). "Identificación de locutor mediante mapas de difusión" (PDF) . Parámetro desconocido
|conference=
ignorado ( ayuda );Cite journal requiere|journal=
( ayuda ) - ^ Mishne, Gal; Cohen, Israel (2013). "Detección de anomalías multiescala mediante mapas de difusión". Temas seleccionados de IEEE en procesamiento de señales . 7 (1): 111-123. Código bibliográfico : 2013ISTSP ... 7..111M . doi : 10.1109 / jstsp.2012.2232279 . S2CID 1954466 .
- ^ Shabat, Gil; Segev, David; Averbuch, Amir (7 de enero de 2018). "Descubrimiento de incógnitas desconocidas en Big Data de servicios financieros por metodologías no supervisadas: tendencias presentes y futuras" . Taller KDD 2017 sobre detección de anomalías en finanzas . 71 : 8-19.
- ^ Gepshtein, Shai; Keller, Yosi (2013). "Finalización de imagen por mapas de difusión y relajación espectral". Transacciones IEEE sobre procesamiento de imágenes . 22 (8): 2983–2994. Código Bibliográfico : 2013ITIP ... 22.2983G . doi : 10.1109 / tip.2013.2237916 . PMID 23322762 . S2CID 14375333 .
- ^ https://www.pnas.org/content/113/44/12574.short