Este equipo de expertos luego de muchos días de investigación y de recopilar de información, han obtenido la solución, nuestro deseo es que te sea de utilidad en tu trabajo.
Solución:
Actualmente estudio estos problemas (clasificación, búsqueda del vecino más cercano) para recuperar información musical.
Te puede interesar Vecino más cercano aproximado (ANA) algoritmos. La idea es que permitas que el algoritmo regrese lo suficiente vecinos cercanos (quizás no el vecino más cercano); al hacerlo, reduce la complejidad. Mencionaste el árbol-kd; ese es un ejemplo. Pero como dijiste árbol-kd Funciona mal en grandes dimensiones. De hecho, todos Las técnicas de indexación actuales (basadas en la partición del espacio) se degradan a la búsqueda lineal de dimensiones suficientemente altas. [1][2][3].
Entre ANA algoritmos propuestos recientemente, quizás el más popular es Hash 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 hash tradicionales, un sensible a la localidad lugares hash cercano apunta al mismo contenedor.
LSH tiene 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, simplemente calcule el hash del punto de consulta, 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 Lp para 0 < p <= 2. Por lo tanto, para responder a su primera pregunta, puede utilizar 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 escribieron una descripción decente para la revista IEEE Signal Processing 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 hash sensible a la localidad basado en distribuciones p-estables", 2004.
[2] Weber, Schek, Blott, "Un análisis cuantitativo y un estudio de rendimiento para métodos de búsqueda de similitudes en espacios de alta dimensión", 1998.
[3] Gionis, Indyk, Motwani, "Búsqueda de similitudes en dimensiones altas mediante hash", 1999.
[4] Slaney, Casey, "Hash sensible a la localidad para encontrar vecinos más cercanos", 2008.
I. La métrica de la distancia
Primero, el número de entidades (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 cuestión, y las bases habituales de 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 covarianza); y
-
el espacio de coordenadas del que se obtuvieron los datos.
Si no tiene conocimiento previo de las distribuciones de las que se tomaron muestras de sus datos, al menos un estudio (bien documentado y exhaustivo) concluye que la distancia euclidiana es la mejor opción.
Métrica de YEuclidean utilizada en motores de recomendación web a gran escala, así como en la investigación académica actual. Las distancias calculadas por Euclidean 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, en cada uno de esos casos la distancia euclidiana falló porque el sistema de coordenadas subyacente (cartesiano) fue una mala elección. Y generalmente reconocerá esto porque, por ejemplo, las longitudes de ruta (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, 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, de Londres a Viena es de 2,5 horas, de Viena a San Petersburgo son otras 3 horas, más o menos en la misma dirección, pero de Londres a St . 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 un sistema de coordenadas no cartesiano, la elección de la métrica de distancia generalmente no es importante. (Vea esta publicación de blog de un estudiante de CS, comparando varias métricas de distancia al examinar su efecto en el clasificador kNN; chi cuadrado da los mejores resultados, pero las diferencias no son grandes; un estudio más completo se encuentra en el artículo académico, Estudio comparativo de Funciones de distancia para vecinos más cercanos: Mahalanobis (esencialmente euclidiana normalizada por para tener en cuenta la covarianza de dimensiones) fue la 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 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 la altura (cm), el peso (kg), la grasa corporal (%) y el pulso en reposo (latidos por minuto), entonces un punto de datos típico podría parece 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 porcentaje 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 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 usted hace. no quiero. Probablemente, la técnica de escalado más común es restar la media y dividir por la desviación estándar (la media y la sd se refieren a calculadas 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 Teselación de Voronoi es un contenedor conceptualmente simple pero que mejorará drásticamente el rendimiento y se escalará 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 (consulte, por ejemplo, este informe de investigación de Microsoft). 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 VT. Sé que en Python y R, hay varias opciones para cada idioma (por ejemplo, el voronoi paquete para R disponible en CRAN)
Usar un VT para kNN funciona así:
A partir de sus datos, seleccione w puntos al azar: estos son sus centros Voronoi. Una celda de 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 determinado se pinte de ese color. Siempre que tenga 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? Utilizo dos guías ortogonales. Después de seleccionar aleatoriamente los puntos w, calcule el VT para sus datos de entrenamiento. A continuación, 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).
Así que imagina que tienes un millón de puntos de datos ..... Si los puntos se conservaran en una estructura de datos 2D ordinaria, o en un árbol kd, realizarías un promedio de 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 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 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 (mediante cálculos de distancia sucesivos) Combinadas, 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 1M de puntos de datos, 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 un promedio de 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 prevista)
Hay dos pasos para calcular el valor predicho a partir de un conjunto de datos de entrenamiento kNN. El primero es identificar n, o el número de vecinos más cercanos utilizar para este cálculo. El segundo es cómo ponderar su contribución al valor predicho.
Con / r / t el primer componente, puede determinar el mejor valor de n resolviendo un problema de optimización (muy similar a la optimización por mínimos cuadrados). Esa es la teoría; en la práctica, la mayoría de la gente usa n = 3. En cualquier caso, es sencillo 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 graficar el error como una función de n. Si solo desea un valor plausible para que n comience, nuevamente, simplemente use n = 3.
El segundo componente es cómo ponderar la contribución de cada uno de los vecinos (asumiendo n> 1).
La técnica de ponderación más simple es simplemente multiplicar a cada vecino por un coeficiente de ponderación, que es solo el 1 / (dist * K), o el inverso de la distancia desde ese vecino a la instancia de prueba, a menudo multiplicado por alguna constante derivada empíricamente, K. I no soy un fanático de esta técnica porque a menudo sobreponde a los vecinos más cercanos (y concomitantemente subestima a los más distantes); El significado 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 imprescindible 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 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.
A lo que te enfrentas se le conoce como maldición de 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.
Actualizar:
Los encontré en un libro llamado Procesamiento de señales biomédicas 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 su descarga. PCA es una técnica más ampliamente utilizada y creo que debería poder encontrar su R u otra implementación de software. El PCA se realiza resolviendo ecuaciones lineales de forma iterativa. Lo he hecho hace demasiado tiempo para recordar cómo. =)
La idea es que divida sus señales en vectores propios independientes (funciones propias discretas, en realidad) 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 medidas. 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.
Aquí puedes ver las reseñas y valoraciones de los lectores
Si estás contento con lo expuesto, puedes dejar un enunciado acerca de qué le añadirías a esta noticia.