algorithm - modelo - knn() r

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

Hace algunos días hice una question sobre cómo encontrar los vecinos más cercanos para un vector determinado. Mi vector ahora tiene 21 dimensiones y antes de continuar, porque no soy del dominio de Aprendizaje automático ni matemático, 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 puede decidir el umbral correcto para determinar los k-vecinos? ¿Hay algún análisis que se pueda hacer para calcular este valor?
Anteriormente, se me sugirió que utilizara kd-Trees, pero la página de Wikipedia dice claramente que, para las dimensiones más elevadas, kd-Tree es casi equivalente a una búsqueda de fuerza bruta. En ese caso, ¿cuál es la mejor manera de encontrar a los vecinos más cercanos en un conjunto de datos de un millón de puntos de manera eficiente?

¿Puede alguien aclarar algunas (o todas) las preguntas anteriores?

¿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 una agrupación de subespacios blandos , 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 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 clúster de tipo k-means para la agrupación de subespacios de conjuntos de datos mixtos numéricos y categóricos

Actualmente estudio tales problemas - clasificación, búsqueda de vecinos más cercanos - para la recuperación de información musical.

Es posible que le interesen los algoritmos del vecino aproximado ( ANN ). La idea es permitir que el algoritmo regrese suficientemente cerca de los vecinos (tal vez no sea el vecino más cercano); al hacerlo, reduces la complejidad. Usted mencionó el árbol kd ; ese es un ejemplo. Pero como dijiste, kd-tree funciona mal en altas dimensiones. De hecho, todas las técnicas de indexación actuales (basadas en particiones de espacio) se degradan a la búsqueda lineal para dimensiones suficientemente altas [1] [2] [3].

Entre los algoritmos ANN propuestos recientemente, quizás el más popular es 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 las localidades coloca los puntos cercanos en el mismo contenedor.

LSH tiene algunas ventajas enormes. Primero, es simple. Simplemente calcula el hash para todos los puntos de su base de datos y luego crea una tabla hash a partir de ellos. Para consultar, simplemente calcule el hash del punto de consulta y luego recupere todos los puntos en el mismo contenedor de la tabla hash.

En segundo lugar, existe 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 de 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 de Manhattan (L1). También hay variantes para la distancia de Hamming y la similitud del coseno.

Malcolm Slaney y Michael Casey, para la revista IEEE Signal Processing, en el año 2008, redactaron una reseña decente [4].

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

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

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

[3] Gionis, Indyk, Motwani, "Búsqueda por similitud en grandes dimensiones mediante hash", 1999.

[4] Slaney, Casey, "hashing localmente sensible para encontrar vecinos más cercanos", 2008.

Creo que el coseno en tf-idf de las 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 tipo de 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.

He experimentado el mismo problema y puedo decir lo siguiente.

La distancia euclidiana es una buena métrica de distancia, sin embargo es computacionalmente más costosa que la distancia de Manhattan , y en ocasiones arroja resultados ligeramente más pobres, por lo tanto, elegiría la posterior.
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.
Las distancias euclidianas y de Manhattan respetan la desigualdad del triángulo , por lo que puedes 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.

KD Trees funciona bien para 21 dimensiones, si sale temprano, después de mirar decir 5% de todos los puntos. FLANN hace esto (y otras aceleraciones) para hacer coincidir los vectores SIFT de 128 dim. (Desafortunadamente, FLANN solo hace la métrica euclidiana, y la rápida y sólida scipy.spatial.cKDTree solo hace métricas Lp, estas pueden ser o no adecuadas para sus datos). Por supuesto, aquí hay una compensación de velocidad-precisión.

(Si puede describir su Ndata, Nquery, distribución de datos, que podría ayudar a las personas a intentar datos similares).

Agregué el 26 de abril, los tiempos de ejecución para cKDTree con límite en mi viejo mac ppc, para dar una idea muy aproximada de la 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

La similitud del 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 no minimizarla. También puede usar una forma específica de dominio para comparar los datos, por ejemplo, si sus datos fueron 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, cuánto ruido hay, etc. No hay reglas generales, solo tiene que encontrar lo que funciona mejor para sus datos específicos y problema al probar todos los valores dentro de un rango . Las personas tienen una comprensión intuitiva de que cuantos más datos hay, menos vecinos necesita. En una situación hipotética donde tiene todos los datos posibles, solo necesita buscar el vecino más cercano para clasificar.

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

Las respuestas principales son buenas pero antiguas, por lo que me gustaría agregar 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 kd, sean tan lentos como un enfoque de fuerza bruta. Como resultado, volvemos nuestro interés en la búsqueda aproximada de vecinos cercanos (ANNS) , que a favor de cierta precisión acelera el proceso. Obtienes una buena aproximación de la NN exacta, con una buena capacidad de propagación.

Temas candentes que pueden ser valiosos:

Enfoques modernos de LSH , como los de Razenshteyn .
Bosque RKD : Bosque (s) de árboles kd aleatorizados (RKD), como se describe en FLANN , o en un enfoque más reciente del que yo era parte, kd-GeRaF .
LOPQ que significa cuantificación del producto optimizado localmente, como se describe here . Es muy similar al nuevo approach Babenko + Lemptitsky.

También puedes consultar mis respuestas relevantes:

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 encuentre 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 de señales biomédicas por 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á públicamente disponible para su descarga.~~ 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 he hecho hace mucho tiempo para recordar cómo. =)

La idea es que dividas tus señales en autovectores independientes (funciones propias discretas, realmente) y sus valores propios, 21 en tu caso. Cada valor propio muestra la cantidad de contribución que proporciona cada función propia a cada una de sus mediciones. Si un valor propio es muy 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.

Los kd-trees 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 de 1 dimensión - casi siempre será más pequeño que la desviación dimensional total a 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 al aumentar 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 (¡hay más de un lado!)

No estoy seguro de que haya mucho uso para simplemente aproximar ciegamente a los vecinos más cercanos euclidianos, por ejemplo, usando LSH o proyecciones aleatorias. ¡Puede ser necesario utilizar una función de distancia afinada mucho más fina en primer lugar!

Mucho depende de por qué quieres conocer a los vecinos más cercanos. Puede buscar en 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.

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 grandes dimensiones, hay poca diferencia entre el vecino más cercano y el más lejano.
Hay muchos documentos / investigaciones en datos de gran 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 que comiences en la dirección correcta. "¿ Cuándo en el vecino más cercano significa ?" por Beyer y todos.

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

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

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

I. La métrica de distancia

Primero, el número de características (columnas) en un conjunto de datos no es un factor en la selección de 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 componen sus datos (son independientes, es decir, cómo se ve la matriz de covarianzas); y
el espacio de coordenadas de donde se obtuvieron sus datos

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

La métrica YEuclidean se usa en los motores de recomendación web a mega escala, así como en la investigación académica actual. Las distancias calculadas por Euclidiano tienen un significado intuitivo y las escalas de cálculo, es decir, la distancia euclidiana se calcula de la misma manera, si los dos puntos están en dos dimensiones o en veintidós espacios de dimensión.

Solo me ha fallado algunas veces, cada uno de esos casos la distancia euclidiana ha fallado 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 la euclidiana, así como el espacio métrico es Tierra y sus distancias son trans -los vuelos continentales, una métrica de distancia 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 otras 3 horas, más o menos en la misma dirección, pero Londres a St . Petersburg 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 medidas de distancia al examinar su efecto en el clasificador de kNN - chi cuadrado da los mejores resultados, pero las diferencias no son grandes; un estudio más completo se encuentra en el trabajo académico, study Mahalanobis (esencialmente euclidiano normalizado por la covarianza de dimensión) fue el mejor en este estudio.

Una condición importante: para que los cálculos de métricas de distancia sean significativos, debe volver a escalar sus datos: rara vez es posible construir un modelo de kNN para generar predicciones precisas sin hacerlo. Por ejemplo, si está construyendo un modelo de 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), un punto de datos típico podría mira algo como esto: [180.4, 66.1, 11.3, 71]. Claramente, el cálculo de distancia estará dominado por la altura, mientras que la contribución por% de grasa corporal será casi insignificante. Dicho de otro modo, 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 los resultados, que es exactamente lo que no quiero Probablemente la técnica de escalado más común es restar la media y dividir por la desviación estándar (media y desviación estándar calculada por separado para cada columna, o característica en 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 del árbol kd, 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 consiguientes ventajas de rendimiento, están bien documentadas (véase, por ejemplo, este informe de Microsoft Research ). La importancia práctica de esto es que, siempre que esté utilizando un lenguaje ''convencional'' (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 idioma (por ejemplo, el paquete voronoi para R disponible en CRAN )

Usar un VT para kNN funciona así:

A partir de sus datos, seleccione aleatoriamente puntos w: estos son sus centros Voronoi. Una celda Voronoi encapsula todos los puntos vecinos que están más cerca de cada centro. Imagínese 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. Siempre que tengas una densidad suficiente, hacer esto mostrará muy bien los límites de cada centro de 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. A continuación, compruebe la cantidad de puntos de datos asignados a cada centro de Voronoi: estos valores deberían ser aproximadamente los mismos (dada la densidad de puntos uniforme en su espacio de datos). En dos dimensiones, esto causaría una TV con fichas 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 un parámetro variable, y mida el rendimiento (tiempo requerido para devolver una predicción al consultar el VT).

Imagine que tiene un millón de puntos de datos ... Si los puntos se conservaran en una estructura de datos bidimensional ordinaria, o en un árbol kd, realizaría en promedio un par de millones de cálculos de distancia para cada nuevo punto de datos cuya variable de respuesta quieres predecir Por supuesto, esos cálculos se realizan en un solo conjunto de datos. Con una V / T, la búsqueda del vecino más cercano se realiza en dos pasos, uno detrás de otro, contra dos poblaciones de datos diferentes: primero contra los centros de Voronoi, luego una vez que se encuentra el centro más cercano, los puntos dentro de la celda correspondientes a ese centro se busca 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, suponga que selecciona 250 centros Voronoi para teselar su espacio de datos. En promedio, cada celda de Voronoi tendrá 4.000 puntos de datos. Entonces, en lugar de realizar en promedio 500,000 cálculos de distancia (fuerza bruta), usted realiza mucho menos, en promedio solo 125 + 2,000.

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

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

Con el primer componente W / r / t, 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 simplemente usa n = 3. En cualquier caso, es simple ejecutar su algoritmo kNN sobre un conjunto de instancias de prueba (para calcular los valores pronosticados) para n = 1, n = 2, n = 3, etc. y graficar el error como una función de n. Si solo quiere un valor plausible para que n comience, nuevamente, 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 simplemente el 1 / (dist * K), o el inverso de la distancia de ese vecino a la instancia de prueba a menudo multiplicado por alguna constante derivada empíricamente, K. I no soy partidario de esta técnica porque a menudo sobrepasa a los vecinos más cercanos (y concomitantemente subponde los más lejanos); 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 mejor ponderación, 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 vecinos más cercanos al punto de datos cuya variable de respuesta desea pronosticar (''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 para cada vecino, que luego se utilizará como el coeficiente de ese vecino en el cálculo del promedio ponderado.