¿El más cercano k vecino más cercano con métrica arbitraria? - algoritmo, matemática, matemática discreta, vecino más cercano

El gotcha con esta pregunta es "arbitrario.métrica ". Si no sabe qué es eso, es la manera de medir la distancia entre puntos. (En el mundo" real ", la distancia 1-dimensional es la magnitud absoluta de la diferencia entre los dos puntos ).

Basta de pre-lims. Estoy tratando de encontrar un algoritmo k vecino más rápido con estas propiedades:

• trabaja en una métrica arbitraria
• algo fácil de implementar
• optimizado para encontrar la distancia de un conjunto de puntos a otro conjunto de puntos

Wikipedia ofrece una lista de algoritmos y enfoques, pero nada en la implementación.

ACTUALIZACIÓN: la métrica es la similitud de coseno, que hace no Satisfacer el triángulo de la desigualdad. Sin embargo, parece que puedo usar la "similitud angular" (según Wikipedia).

ACTUALIZAR: El caso de uso es el procesamiento del lenguaje natural. Los "vectores" son el "contexto" de una palabra dada, representada por propiedades binarias (por ejemplo, el título del documento). Entonces, mientras que solo puede haber unas pocas propiedades (ahora mismo estoy usando solo 3), cada vector tiene una dimensión arbitrariamente grande (en el ejemplo del título, cada título en la base de datos correspondería a una dimensión en el vector).

ACTUALIZACIÓN: Para los curiosos, estoy implementando este algoritmo:

http://josquin.cs.depaul.edu/~mramezani/papers/IEEEIS.pdf

ACTUALIZAR: El algoritmo deberá encontrar vecinos más cercanos para aproximadamente una docena de puntos de aproximadamente 100s de puntos. La dimensión promedio probablemente será muy grande, digamos 50 (aún no lo sé). Y sí, estoy interesado en un algoritmo, no en una biblioteca. Y sí, las estimaciones son probablemente lo suficientemente buenas.

Respuestas

Te aconsejo que vayas por Locality sensiblehashing (LSH), que está en tendencia en este momento. Reduce la dimensionalidad de los datos de alta dimensión, pero no estoy seguro de que su dimensión vaya bien con ese algoritmo. Ver la wikipedia página para más.

Puede usar su propia métrica, pero en general puede hacerlo en muchos algoritmos. Espero que esto ayude.

Podrías buscar árboles RKD, un bosque de ellos, pero tal vez esto sea demasiado ahora.