¿Vecinos más cercanos en datos de alta dimensión?

Hace unos días hice una pregunta sobre cómo encontrar a los vecinos más cercanos para un vector dado. Mi vector ahora tiene 21 dimensiones y antes de continuar, como no soy del dominio de Machine Learning ni Math, estoy empezando a hacerme algunas preguntas fundamentales:

• ¿Es la distancia euclidiana una buena métrica para encontrar a los vecinos más cercanos en primer lugar? Si no es así, ¿cuáles son mis opciones?
• Además, ¿cómo se decide el umbral correcto para determinar los k-vecinos? ¿Hay algún análisis que se pueda hacer para calcular este valor?
• Anteriormente, me sugirieron usar kd-Trees, pero la página de Wikipedia dice claramente que para grandes dimensiones, kd-Tree es casi equivalente a una búsqueda de fuerza bruta. En ese caso, ¿cuál es la mejor manera de encontrar vecinos más cercanos en un conjunto de datos de un millón de puntos de manera eficiente?

¿Alguien puede aclarar algunas (o todas) de las preguntas anteriores?

Actualmente estudio tales problemas (clasificación, búsqueda del vecino más cercano) para recuperar información musical.

Puede que le interesen los algoritmos de vecino más cercano aproximado ( ANN ). La idea es que permita que el algoritmo regrese suficientemente cerca de los vecinos (quizás no el vecino más cercano); Al hacerlo, se reduce la complejidad. Mencionaste el árbol kd ; Ese es un ejemplo. Pero como dijiste, kd-tree funciona mal en grandes dimensiones. De hecho, todas las técnicas de indexación actuales (basadas en particiones espaciales) se degradan a búsqueda lineal de dimensiones suficientemente altas [1] [2] [3].

Entre los algoritmos ANN propuestos recientemente, quizás el más popular es el Hashing sensible a la localidad ( LSH ), que mapea un conjunto de puntos en un espacio de alta dimensión en un conjunto de contenedores, es decir, una tabla hash [1] [3]. Pero a diferencia de los hashes tradicionales, un hash sensible a la localidad coloca los puntos cercanos en el mismo contenedor.

LSH tiene algunas grandes ventajas. Primero, es simple. Simplemente calcule el hash para todos los puntos en su base de datos, luego haga una tabla hash a partir de ellos. Para consultar, solo calcule el hash del punto de consulta, luego recupere todos los puntos en el mismo bin de la tabla hash.

En segundo lugar, hay una teoría rigurosa que respalda su desempeño. Se puede demostrar que el tiempo de consulta es sublineal en el tamaño de la base de datos, es decir, más rápido que la búsqueda lineal. Cuánto más rápido depende de cuánta aproximación podamos tolerar.

Finalmente, LSH es compatible con cualquier norma Lp para 0 < p <= 2. Por lo tanto, para responder a su primera pregunta, puede usar LSH con la métrica de distancia euclidiana, o puede usarla con la métrica de distancia Manhattan (L1). También hay variantes para la distancia de Hamming y la similitud de coseno.

Malcolm Slaney y Michael Casey escribieron una descripción general decente para IEEE Signal Processing Magazine en 2008 [4].

LSH se ha aplicado aparentemente en todas partes. Es posible que desee darle una oportunidad.

[1] Datar, Indyk, Immorlica, Mirrokni, "Esquema de Hashing sensible a la localidad basado en distribuciones p-estables", 2004.

[2] Weber, Schek, Blott, "Un estudio de análisis cuantitativo y de rendimiento para métodos de búsqueda de similitud en espacios de alta dimensión", 1998.

[3] Gionis, Indyk, Motwani, "Búsqueda de similitud en altas dimensiones mediante hashing", 1999.

[4] Slaney, Casey, "Localidad sensible al hash para encontrar vecinos más cercanos", 2008.

I. La métrica de distancia

Primero, el número de características (columnas) en un conjunto de datos no es un factor para seleccionar una métrica de distancia para usar en kNN. Hay bastantes estudios publicados dirigidos precisamente a esta pregunta, y las bases habituales para la comparación son:

• la distribución estadística subyacente de sus datos;

• la relación entre las características que comprenden sus datos (son independientes, es decir, cómo se ve la matriz de covarianza); y

• El espacio de coordenadas del que se obtuvieron sus datos.

Si usted no tiene conocimiento previo de la distribución (s) de los cuales se tomaron muestras de sus datos, al menos uno (bien documentada y exhaustiva) estudio concluye que la distancia euclidiana es la mejor opción.

Métrica euclidiana utilizada en motores de recomendación web a gran escala, así como en investigaciones académicas actuales. Las distancias calculadas por Euclidiana tienen un significado intuitivo y las escalas de cálculo, es decir, la distancia euclidiana se calcula de la misma manera, ya sea que los dos puntos estén en dos dimensiones o en un espacio de veintidós dimensiones.

Solo me ha fallado unas pocas veces, cada uno de esos casos la distancia euclidiana falló porque el sistema de coordenadas subyacente (cartesiano) era una mala elección. Y generalmente reconocerá esto porque, por ejemplo, las longitudes de camino (distancias) ya no son aditivas, por ejemplo, cuando el espacio métrico es un tablero de ajedrez, la distancia de Manhattan es mejor que Euclidiana, del mismo modo cuando el espacio métrico es la Tierra y sus distancias son trans -vuelos continentales, una métrica de distancia adecuada para un sistema de coordenadas polares es una buena idea (por ejemplo, Londres a Viena son 2.5 horas, Viena a San Petersburgo son otras 3 horas, más o menos en la misma dirección, pero Londres a St Petersburgo no es 5,5 horas, en cambio, es un poco más de 3 horas

Pero aparte de aquellos casos en los que sus datos pertenecen a un sistema de coordenadas no cartesiano, la elección de la métrica de distancia generalmente no es material. (Vea esta publicación de blog de un estudiante de CS, comparando varias métricas de distancia examinando su efecto en el clasificador kNN: el chi cuadrado da los mejores resultados, pero las diferencias no son grandes; un estudio más completo se encuentra en el documento académico, Estudio comparativo de Funciones de distancia para los vecinos más cercanos: Mahalanobis (esencialmente euclidiana normalizada para dar cuenta de la covarianza de la dimensión) fue la mejor en este estudio.

Una condición importante: para que los cálculos métricos de distancia sean significativos, debe volver a escalarsus datos: rara vez es posible construir un modelo kNN para generar predicciones precisas sin hacer esto. Por ejemplo, si está construyendo un modelo kNN para predecir el rendimiento deportivo, y sus variables de expectativa son altura (cm), peso (kg), grasa corporal (%) y pulso en reposo (latidos por minuto), entonces un punto de datos típico podría se parece a esto: [180.4, 66.1, 11.3, 71]. Claramente, el cálculo de la distancia estará dominado por la altura, mientras que la contribución por% de grasa corporal será casi insignificante. Dicho de otra manera, si en cambio, los datos se informaron de manera diferente, de modo que el peso corporal estaba en gramos en lugar de kilogramos, entonces el valor original de 86.1 sería 86,100, lo que tendría un gran efecto en sus resultados, que es exactamente lo que no tiene no quiero

X_new = (X_old - mu) / sigma

II La estructura de datos

Si le preocupa el rendimiento de la estructura de kd-tree, A Voronoi Tessellation es un contenedor conceptualmente simple pero que mejorará drásticamente el rendimiento y las escalas mejor que kd-Trees.

Esta no es la forma más común de conservar los datos de entrenamiento de kNN, aunque la aplicación de VT para este propósito, así como las ventajas de rendimiento consecuentes, están bien documentadas (ver, por ejemplo, este informe de Microsoft Research ). El significado práctico de esto es que, siempre que esté utilizando un lenguaje 'convencional' (por ejemplo, en el Índice TIOBE ), entonces debería encontrar una biblioteca para realizar la TV. Sé que en Python y R, hay múltiples opciones para cada idioma (por ejemplo, el paquete voronoi para R disponible en CRAN )

Usar un VT para kNN funciona así:

A partir de sus datos, seleccione al azar w puntos: estos son sus centros Voronoi. Una célula de Voronoi encapsula todos los puntos vecinos más cercanos a cada centro. Imagínese si asigna un color diferente a cada uno de los centros Voronoi, de modo que cada punto asignado a un centro determinado esté pintado de ese color. Siempre que tenga una densidad suficiente, al hacerlo se mostrarán los límites de cada centro Voronoi (como el límite que separa dos colores).

¿Cómo seleccionar los Centros Voronoi? Yo uso dos pautas ortogonales. Después de seleccionar al azar los puntos w, calcule el VT para sus datos de entrenamiento. Luego, verifique la cantidad de puntos de datos asignados a cada centro de Voronoi: estos valores deben ser aproximadamente los mismos (dada la densidad de puntos uniforme en su espacio de datos). En dos dimensiones, esto causaría un VT con mosaicos del mismo tamaño. Esa es la primera regla, aquí está la segunda. Seleccione w por iteración: ejecute su algoritmo kNN con w como parámetro variable y mida el rendimiento (tiempo necesario para devolver una predicción consultando el VT).

Imagine que tiene un millón de puntos de datos ..... Si los puntos persistieran en una estructura de datos 2D ordinaria, o en un árbol kd, realizaría en promedio un par de millones de cálculos de distancia por cadanuevos puntos de datos cuya variable de respuesta desea predecir. Por supuesto, esos cálculos se realizan en un solo conjunto de datos. Con un V / T, la búsqueda del vecino más cercano se realiza en dos pasos uno tras otro, contra dos poblaciones diferentes de datos: primero contra los centros Voronoi, luego, una vez que se encuentra el centro más cercano, los puntos dentro de la celda corresponden a se buscan en ese centro para encontrar el vecino más cercano real (mediante cálculos de distancia sucesivos) Combinados, estas dos búsquedas son mucho más rápidas que una sola búsqueda de fuerza bruta. Eso es fácil de ver: para 1 millón de puntos de datos, suponga que selecciona 250 centros Voronoi para testear su espacio de datos. En promedio, cada celda Voronoi tendrá 4,000 puntos de datos. Entonces, en lugar de realizar en promedio 500,000 cálculos de distancia (fuerza bruta), realiza mucho menos, en promedio solo 125 + 2,000.

III. Cálculo del resultado (la variable de respuesta pronosticada)

Hay dos pasos para calcular el valor predicho a partir de un conjunto de datos de entrenamiento de kNN. El primero es identificar n, o el número de vecinos más cercanos a usar para este cálculo. El segundo es cómo ponderar su contribución al valor predicho.

W / r / t el primer componente, puede determinar el mejor valor de n resolviendo un problema de optimización (muy similar a la optimización de mínimos cuadrados). Esa es la teoria; en la práctica, la mayoría de las personas solo usan n = 3. En cualquier caso, es simple ejecutar su algoritmo kNN en un conjunto de instancias de prueba (para calcular los valores pronosticados) para n = 1, n = 2, n = 3, etc. y trazar el error en función de n. Si solo desea un valor plausible para que n comience, nuevamente, use n = 3.

El segundo componente es cómo ponderar la contribución de cada uno de los vecinos (suponiendo que n> 1).

La técnica de ponderación más simple consiste en multiplicar cada vecino por un coeficiente de ponderación, que es solo el 1 / (dist * K), o la inversa de la distancia desde ese vecino a la instancia de prueba a menudo multiplicada por alguna constante derivada empíricamente, K. I No soy un fanático de esta técnica porque a menudo sobrepesa a los vecinos más cercanos (y concomitantemente subestima a los más distantes); La importancia de esto es que una predicción dada puede depender casi por completo de un solo vecino, lo que a su vez aumenta la sensibilidad del algoritmo al ruido.

Una función de ponderación mejor, que evita sustancialmente esta limitación es la función gaussiana , que en python se ve así:

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

Para calcular un valor pronosticado usando su código kNN, identificaría los n vecinos más cercanos al punto de datos cuya variable de respuesta desea predecir ('instancia de prueba'), luego llame a la función weight_gauss, una vez para cada uno de los n vecinos, pasando en la distancia entre cada vecino, el punto de prueba. Esta función devolverá el peso de cada vecino, que luego se utiliza como el coeficiente de ese vecino en el cálculo del promedio ponderado.

Lo que estás enfrentando se conoce como la maldición de la dimensionalidad . A veces es útil ejecutar un algoritmo como PCA o ICA para asegurarse de que realmente necesita las 21 dimensiones y posiblemente encontrar una transformación lineal que le permita usar menos de 21 con aproximadamente la misma calidad de resultado.

Actualización: los encontré en un libro llamado Procesamiento biomédico de señales de Rangayyan (espero recordarlo correctamente). ICA no es una técnica trivial, pero fue desarrollada por investigadores en Finlandia y creo que el código de Matlab está disponible públicamente para descargar. PCA es una técnica más utilizada y creo que debería poder encontrar su R u otra implementación de software. La PCA se realiza resolviendo ecuaciones lineales de forma iterativa. Lo hice hace mucho tiempo para recordar cómo. =)

La idea es que divida sus señales en vectores propios independientes (funciones propias discretas, realmente) y sus valores propios, 21 en su caso. Cada valor propio muestra la cantidad de contribución que cada función propia proporciona a cada una de sus mediciones. Si un valor propio es pequeño, puede representar muy de cerca las señales sin usar su función propia correspondiente, y así es como se deshace de una dimensión.

Las mejores respuestas son buenas pero antiguas, por lo que me gustaría agregar una respuesta de 2016 .

Como se dijo, en un espacio de altas dimensiones, la maldición de la dimensionalidad acecha a la vuelta de la esquina, haciendo que los enfoques tradicionales, como el popular árbol kd, sean tan lentos como un enfoque de fuerza bruta. Como resultado, volcamos nuestro interés en la Búsqueda aproximada de vecinos más cercanos (ANNS) , que a favor de cierta precisión, acelera el proceso. Obtiene una buena aproximación del NN exacto, con una buena capacidad de propagación.

Temas candentes que pueden ser dignos:

1. Enfoques modernos de LSH , como el de Razenshteyn .
2. Bosque RKD : Bosque (s) de árboles kd aleatorizados (RKD), como se describe en FLANN , o en un enfoque más reciente del que formé parte, kd-GeRaF .
3. LOPQ que significa Cuantización de productos localmente optimizada, como se describe aquí . Es muy similar al nuevo enfoque de Babenko + Lemptitsky .

También puedes consultar mis respuestas relevantes:

1. Dos conjuntos de puntos de alta dimensión: encuentra el vecino más cercano en el otro conjunto
2. Comparación del tiempo de ejecución de las consultas del vecino más cercano en diferentes estructuras de datos
3. Implementación de PCL kd-tree extremadamente lenta

Para responder a sus preguntas una por una:

• No, la distancia euclidiana es una mala métrica en el espacio de alta dimensión. Básicamente en las dimensiones altas, los puntos de datos tienen grandes diferencias entre sí. Eso disminuye la diferencia relativa en la distancia entre un punto de datos dado y su vecino más cercano y más lejano.
• Hay muchos trabajos / investigaciones en datos de alta dimensión, pero la mayoría de las cosas requieren mucha sofisticación matemática.
• El árbol KD es malo para datos de alta dimensión ... evítelo por todos los medios

Aquí hay un buen documento para comenzar en la dirección correcta. "¿ Cuándo es significativo el vecino más cercano ?" por Beyer et al.

Trabajo con datos de texto de dimensiones 20K y superiores. Si desea algún consejo relacionado con el texto, podría ayudarlo.

La similitud de coseno es una forma común de comparar vectores de alta dimensión. Tenga en cuenta que, dado que es una similitud, no una distancia, querrá maximizarla y no minimizarla. También puede usar una forma específica de dominio para comparar los datos, por ejemplo, si sus datos eran secuencias de ADN, podría usar una similitud de secuencia que tenga en cuenta las probabilidades de mutaciones, etc.

El número de vecinos más cercanos a usar varía según el tipo de datos, la cantidad de ruido que haya, etc. No hay reglas generales, solo tiene que encontrar qué funciona mejor para sus datos y problemas específicos probando todos los valores dentro de un rango . La gente tiene una comprensión intuitiva de que cuantos más datos haya, menos vecinos necesitará. En una situación hipotética en la que tiene todos los datos posibles, solo necesita buscar el vecino más cercano para clasificar.

Se sabe que el método k vecino más cercano es computacionalmente costoso. Es una de las principales razones por las que las personas recurren a otros algoritmos, como las máquinas de vectores de soporte.

kd-trees de hecho no funcionará muy bien en datos de alta dimensión. Debido a que el paso de poda ya no ayuda mucho, ya que el borde más cercano, una desviación unidimensional, casi siempre será más pequeño que la desviación dimensional completa de los vecinos más cercanos conocidos.

Pero además, los árboles kd solo funcionan bien con las normas Lp por lo que sé, y existe el efecto de concentración de distancia que hace que los algoritmos basados ​​en la distancia se degraden con el aumento de la dimensionalidad.

Para obtener más información, es posible que desee leer sobre la maldición de la dimensionalidad y las diversas variantes de la misma (¡tiene más de un lado!)

No estoy convencido de que sea muy útil aproximarse ciegamente a los vecinos más cercanos euclidianos, por ejemplo, usando LSH o proyecciones aleatorias. ¡Puede ser necesario usar una función de distancia mucho más fina en primer lugar!

Mucho depende de por qué quieres conocer a los vecinos más cercanos. Puede consultar el algoritmo de cambio medio http://en.wikipedia.org/wiki/Mean-shift si lo que realmente desea es encontrar los modos de su conjunto de datos.

Creo que el coseno en tf-idf de características booleanas funcionaría bien para la mayoría de los problemas. Eso es porque su heurística probada en el tiempo se utiliza en muchos motores de búsqueda como Lucene. La distancia euclidiana en mi experiencia muestra malos resultados para cualquier información similar a un texto. La selección de diferentes pesos y ejemplos k se puede hacer con datos de entrenamiento y selección de parámetros de fuerza bruta.

iDistance es probablemente el mejor para la recuperación exacta de knn en datos de alta dimensión. Puede verlo como una teselación aproximada de Voronoi.

He experimentado el mismo problema y puedo decir lo siguiente.

1. La distancia euclidiana es una buena métrica de distancia, sin embargo, es computacionalmente más costosa que la distancia de Manhattan , y a veces produce resultados ligeramente más pobres, por lo tanto, elegiría la posterior.

2. El valor de k se puede encontrar empíricamente. Puede probar diferentes valores y verificar las curvas ROC resultantes o alguna otra medida de precisión / recuperación para encontrar un valor aceptable.

3. Tanto las distancias Euclidiana como Manhattan respetan la desigualdad del Triángulo , por lo que puede usarlas en árboles métricos. De hecho, los árboles KD tienen su rendimiento severamente degradado cuando los datos tienen más de 10 dimensiones (yo mismo he experimentado ese problema). Encontré que los árboles VP son una mejor opción.

Los árboles KD funcionan bien para 21 dimensiones, si abandonas temprano, después de mirar, por ejemplo, el 5% de todos los puntos. FLANN hace esto (y otras aceleraciones) para que coincida con los vectores SIFT de 128 dim. (Desafortunadamente, FLANN solo hace la métrica euclidiana, y el scipy.spatial.cKDTree rápido y sólido solo hace métricas Lp; estas pueden o no ser adecuadas para sus datos). Por supuesto, aquí hay una compensación de precisión de velocidad.

(Si pudiera describir su distribución de datos Ndata, Nquery, eso podría ayudar a las personas a probar datos similares).

Agregué el 26 de abril, tiempos de ejecución para cKDTree con corte en mi antigua Mac ppc, para dar una idea muy aproximada de viabilidad:

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.253

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.245

Puedes probar una curva de orden az. Es fácil para 3 dimensiones.

¿Es la distancia euclidiana una buena métrica para encontrar a los vecinos más cercanos en primer lugar? Si no es así, ¿cuáles son mis opciones?

Sugeriría la agrupación suave del subespacio , un enfoque bastante común hoy en día, donde los pesos de las características se calculan para encontrar las dimensiones más relevantes. Puede usar estos pesos cuando usa la distancia euclidiana, por ejemplo. Vea la maldición de la dimensionalidad para problemas comunes y también este artículo puede iluminarlo de alguna manera:

Un algoritmo de agrupamiento de tipo k-means para el agrupamiento de subespacios de conjuntos de datos numéricos y categóricos mixtos