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

I. La Métrica de Distancia

Primero, el número de entidades (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 cuestión, y las bases habituales para la comparación son:

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

• La relación entre las características que comprenden sus datos (son ellos independiente independent es decir, ¿qué hace el covarianza matriz parecen); y

• El espacio de coordenadas desde el que su se obtuvieron los datos.

Si no tiene conocimiento previo de la distribución(es) de la que se muestrearon sus datos, al menos un estudio (bien documentado y exhaustivo) concluye que la distancia euclidiana es la mejor opción.

Métrica yeuclidiana utilizada en Motores de Recomendación Web de mega-escala, así como en la investigación académica actual. Distancias calculadas por Euclidean han intuitivo significado y las escalas de cálculo distance es decir, la distancia euclidiana se calcula de la misma manera, si los dos puntos están en dos dimensiones o en veintidós dimensiones espacio.

Solo ha fallado para mí unas pocas veces, cada uno de esos casos La distancia euclidiana falló porque el sistema de coordenadas subyacente (cartesiano) fue una mala elección. Y generalmente reconocerás esto porque, por ejemplo, las longitudes de ruta (distancias) ya no son aditivos e por ejemplo, cuando el espacio métrico es un tablero de ajedrez, Manhattan la distancia es mejor que la Euclidiana, del mismo modo cuando el espacio métrico es la Tierra y sus distancias son vuelos transcontinentales, una distancia métrica adecuada para un sistema de coordenadas polares es una buena idea (por ejemplo, Londres a Viena es de 2,5 horas, Viena a San Petersburgo es de otras 3 horas, más o menos en la misma dirección, sin embargo, Londres a San Petersburgo no es de 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 una coordenada no cartesiana sistema, la elección de la distancia métrica generalmente no es material. (Ver este blog post de un estudiante de CS, comparando varias métricas de distancia mediante el examen de su efecto en el clasificador kNN chi chi cuadrado dar los mejores resultados, pero las diferencias no son grandes; Un estudio más completo está en el documento académico, Estudio Comparativo de las Funciones de distancia para los Vecinos Más Cercanos Mah Mahalanobis (esencialmente Euclidiano normalizado por para tener en cuenta la covarianza dimensión) fue el mejor en este estudio.

Una condición importante: para que los cálculos de la métrica de distancia sean significativos, debe reescalar sus datos rarely 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 atlético, 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 verse algo como 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 del % de grasa corporal será casi insignificante. Dicho de otra manera, si en cambio, los datos se informaran de manera diferente, de modo que el peso corporal estuviera 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 desea. Probablemente la técnica de escalado más común es restar la media y dividir por el estándar desviación (media y de se refieren calculadas por separado para cada columna o entidad de ese conjunto de datos; X se refiere a una entrada/celda individual dentro de una fila de datos):

X_new = (X_old - mu) / sigma

II. La Estructura De Datos

Si le preocupa el rendimiento de la estructura kd-tree, un Teselación Voronoi es un contenedor conceptualmente simple pero que mejorará drásticamente el rendimiento y escalará mejor que kd-Trees.

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

Usar un VT para kNN funciona así::

De sus datos, seleccione al azar puntos w these estos son sus centros Voronoi. Una célula Voronoi encapsula todos los puntos vecinos que están más cerca de cada centro. Imagine si asigna un color diferente a cada uno de los centros de Voronoi, de modo que cada punto asignado a un centro dado esté pintado de ese color. Mientras tenga una densidad suficiente, hacer esto mostrará muy bien los límites de cada centro Voronoi (como el límite que separa dos colores.

¿Cómo seleccionar los Centros Voronoi? Uso dos pautas ortogonales. Después de seleccionar al azar los puntos w, calcule el VT para sus datos de entrenamiento. A continuación, compruebe el número de puntos de datos asignados a cada centro Voronoi these estos valores deben ser aproximadamente los mismos (dada la densidad de puntos uniforme en todo el espacio de datos). En dos dimensiones, esto causaría un VT con azulejos del mismo tamaño.Esa es la primera regla, aquí está la segunda. Seleccionar w por iteración run ejecutar su algoritmo kNN con w como parámetro variable, y medir el rendimiento (tiempo necesario para devolver una predicción consultando el VT).

Así que imagina que tienes un millón de puntos de datos..... Si los puntos se mantuvieran 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 para cada nuevos puntos de datos cuya variable de respuesta desea predecir. Por supuesto, esos cálculos se realizan en un solo conjunto de datos. Con a V / T, la búsqueda del vecino más cercano se realiza en dos pasos uno tras otro, contra dos poblaciones diferentes de datos first primero contra los centros Voronoi, luego una vez que se encuentra el centro más cercano, los puntos dentro de la celda correspondientes a ese centro se buscan para encontrar el vecino más cercano real (por 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 puntos de datos de 1M, supongamos que selecciona 250 centros Voronoi para teselar su espacio de datos. En promedio, cada célula de Voronoi tendrá 4.000 puntos de datos. Así que en lugar de realizar en promedio 500.000 cálculos de distancia (fuerza bruta), realizar mucho menos, en promedio sólo 125 + 2.000.

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

Hay dos pasos para calcular el valor predicho a partir de un conjunto de datos de entrenamiento kNN. La primera es identificar n, o el número de vecinos más cercanos a utilizar 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 teoría; en la práctica, la mayoría de la gente solo usa n = 3. En cualquier caso, es simple ejecutar su algoritmo kNN sobre un conjunto de instancias de prueba (para calcular los valores predichos) para n=1, n=2, n=3, etc. y trazar el error como una función de n. Si solo desea un valor plausible para n para empezar, de nuevo, solo use n = 3.

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

La técnica de ponderación más simple es simplemente 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. No soy fan de esta técnica porque a menudo sobre-pesa a los vecinos más cercanos( y concomitantemente sub-pesa a los más distantes); la importancia de esto es que una predicción dada puede ser casi totalmente dependiente de un solo vecino, lo que a su vez aumenta la sensibilidad del algoritmo al ruido.

Una función de ponderación mejor debe, 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 predicho 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 llamaría 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 para cada vecino, que luego se utiliza como coeficiente de ese vecino en el cálculo del promedio ponderado.

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

Actualización: Los encontré en un libro llamado Biomedical Signal Processing de Rangayyan (espero recordarlo correctamente). IC no es un técnica trivial, pero fue desarrollado por investigadores en Finlandia y creo que el código de Matlab para que está disponible públicamente para su descarga. PCA es una técnica más ampliamente utilizada y creo que debería ser capaz de encontrar su R u otra implementación de software. El PCA se realiza resolviendo ecuaciones lineales iterativamente. Lo he hecho hace mucho tiempo para recordar cómo. = )

La idea es que usted divide sus señales en vectores propios independientes (funciones propias discretas, realmente) y su 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 en absoluto, y así es como se deshace de una dimensión.

Para responder a sus preguntas una por una:

• No, la distancia euclidiana es una mala métrica en el espacio dimensional alto. Básicamente en dimensiones altas hay poca diferencia entre el vecino más cercano y el más lejano.
• Muchos artículos/investigaciones están allí 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 dimensionales altos ... evitar por todos los medios

Aquí hay un buen documento para empezar en la dirección correcta. " Cuando en el Vecino Más Cercano significativo?"by Beyer et all.

Trabajo con datos de texto de dimensiones 20K y superiores. Si quieres algún consejo relacionado con el texto, tal vez pueda ayudarte.

Las respuestas principales son buenas pero viejas, así que me gustaría sumar una respuesta de 2016.

Como se dijo, en un espacio de alta dimensión, la maldición de la dimensionalidad acecha a la vuelta de la esquina, haciendo que los enfoques tradicionales, como el popular árbol k-d, sean tan lentos como un enfoque de fuerza bruta. Como resultado, giramos nuestro interés en Búsqueda Aproximada del Vecino Más Cercano (ANNS) , que a favor de cierta precisión, acelera el proceso. Se obtiene una buena aproximación de la NN exacta, con una buena propabilidad.

Temas candentes que podrían ser dignos:

1. enfoques Modernos de LSH, tales como Razenshteyn's.
2. Bosque RKD : Bosque(s) de árboles k-d aleatorios (RKD), como se describe en FLANN, o en un enfoque más reciente yo era parte de, kd-GeRaF .
3. LOPQ que significa Cuantización de Productos Optimizada Localmente, como se describe aquí. Es muy similar a la nueva El enfoque de Babenko+Lemptitsky .

También puedes consultar mis respuestas relevantes:

1. Dos conjuntos de puntos dimensionales altos: 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. PCL kd-tree implementación extremadamente lenta

La similitud de coseno es una forma común de comparar vectores de alta dimensión. Tenga en cuenta que ya que es una similitud no una distancia, usted querría maximizarlo no minimizarlo. 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 secuencias que tenga en cuenta las probabilidades de mutaciones, etc.

El número de vecinos más cercanos a usar varía dependiendo del tipo de datos, cuánto ruido hay, etc. No hay reglas generales, solo tiene que encontrar lo que 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 hay, menos vecinos necesita. En una situación hipotética en la que tenga todos los datos posibles, solo necesita buscar el vecino más cercano para clasificar.

Se sabe que el método k Nearest Neighbor es computacionalmente caro. Es una de las principales razones por las que la gente recurre a otros algoritmos como máquinas de vectores de soporte.

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

Los árboles Kd de hecho no funcionarán 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 dimensional 1 - casi siempre será más pequeño que la desviación dimensional completa a los vecinos más cercanos conocidos.

Pero además, los árboles kd solo funcionan bien con 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 una dimensionalidad creciente.

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

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

La idistancia es probablemente la mejor para la recuperación exacta de knn en datos de alta dimensión. Puedes verlo como un aproximado de Voronoi tessalation.

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

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

Añadido 26 Abril, tiempos de ejecución para cKDTree con corte en mi viejo 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

Podría intentar una curva de orden z. Es fácil para 3 dimensiones.

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 usa en muchos motores de búsqueda como Lucene. La distancia euclidiana en mi experiencia muestra malos resultados para cualquier dato similar a texto. Selección de diferentes pesos y k-ejemplos se pueden hacer con datos de entrenamiento y selección de parámetros de fuerza bruta.

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 cara que la distancia de Manhattan , y a veces produce resultados ligeramente más pobres, por lo tanto, elegiría el más tarde.

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 euclidianas como las de 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é VP-trees para ser una mejor opción.

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

Sugeriría agrupación subespacial suave, un enfoque bastante común hoy en día, donde los pesos de las entidades se calculan para encontrar las dimensiones más relevantes. Puede utilizar estos pesos cuando se utiliza la distancia euclidiana, por ejemplo. Ver maldición de la dimensionalidad para problemas comunes y también este artículo puede iluminarte de alguna manera:

A k-significa algoritmo de clustering de tipo para clustering subespacial de conjuntos de datos categóricos