Un resumen de preguntas frecuentes sobre el algoritmo KNN
Generalmente, en tareas de clasificación, puede usar "votación", es decir, seleccionar la categoría de anotación con la mayor frecuencia entre k instancias como resultado de predicción, en tareas de regresión, puede usar "promedio"; es decir, tome k El valor promedio de la salida de la etiqueta de k instancias se usa como resultado de la predicción; el valor promedio de la salida de la etiqueta de k instancias también se puede usar como resultado de la predicción; En tareas de regresión, puede utilizar el "método promedio", es decir, utilizar el promedio de las etiquetas de salida de valor real de k instancias como valor predicho; también puede realizar un promedio ponderado o una votación ponderada según la proximidad del; instancias Cuanto más cerca esté la instancia, mayor será el peso.
El método del vecino más cercano K no tiene un proceso de aprendizaje explícito; de hecho, es un conocido representante del aprendizaje diferido. Esta técnica de aprendizaje solo guarda muestras durante la fase de entrenamiento, sin tiempo de entrenamiento adicional. luego recibe muestras de prueba procesadas cuando.
KNN suele utilizar la distancia euclidiana, pero también se pueden utilizar otras medidas de distancia, concretamente la distancia Lp general:
La elección del valor K en KNN puede tener un impacto significativo en los resultados. del algoritmo K vecino más cercano. Si elige un valor K más pequeño, equivale a utilizar ejemplos de entrenamiento en un dominio más pequeño para hacer predicciones. Se reducirá el error de aproximación de "aprendizaje" (error de aproximación: puede entenderse como el error de entrenamiento en el conjunto de entrenamiento existente). solo con la entrada Solo los ejemplos de entrenamiento con ejemplos cercanos o similares pueden contribuir a los resultados de la predicción. Esto también genera el problema de "en otras palabras, la reducción del valor K significa que el modelo general se vuelve más complejo y propenso a sobreajustarse";
Elegir un valor K más grande es equivalente a usar ejemplos de entrenamiento en un campo más grande para la predicción. La ventaja es que reduce el error de estimación del aprendizaje, pero la desventaja es que aumenta el error de aproximación del aprendizaje. El error aumentará. En este punto, las instancias de entrenamiento que están lejos (diferentes) de la instancia de entrada también actuarán sobre el predictor, lo que hará que la predicción sea incorrecta, y un aumento en el valor K significa que todo el modelo se vuelve más simple.
En la práctica, el valor K generalmente se considera un valor relativamente pequeño, por ejemplo, utilizando validación cruzada para seleccionar el mejor valor K. Según la experiencia, el valor k suele ser menor que la raíz cuadrada del número de muestras de entrenamiento
1. Calcule la distancia entre el objeto de prueba y cada objeto en el conjunto de entrenamiento
2. Ordene los objetos de prueba por distancia
p>
3. Seleccione el objeto de entrenamiento con la k distancia más cercana al objeto de prueba actual como vecino del objeto de prueba
4. Cuente las frecuencias de categoría de estos k vecinos
5. La clase con la frecuencia más alta entre k vecinos es la clase del objeto de prueba
La entrada X puede usar BallTree o KDTree estructura de datos para optimizar la eficiencia computacional, que se puede especificar al crear una instancia de KNeighborsClassifier.
KDTree
La idea básica es que si el punto A está lejos del punto B y el punto B está muy cerca del punto C, entonces se sabe que el punto A está lejos de punto C, por lo que no es necesario calcular explícitamente la distancia entre ellos. De esta manera, el costo computacional de la búsqueda del vecino más cercano se puede reducir a O[DNlog(N)] o menos.
La construcción del árbol KD es muy rápida y la búsqueda del vecino más cercano para dimensiones bajas (D <20) también es muy rápida, pero cuando D se vuelve grande, su eficiencia disminuye: esta es la llamada "dimensionalidad". " desastre".
Un árbol KD es una estructura de árbol binario que divide recursivamente el espacio de parámetros a lo largo del eje de datos en regiones anisotrópicas anidadas incrustadas con puntos de datos. Los árboles KD son muy rápidos de construir: dado que la partición se realiza solo a lo largo del eje de datos, no es necesario calcular distancias D-dimensionales. Una vez construido, la complejidad de calcular la distancia vecina de un punto de consulta es solo O [log (N)]. Aunque el método del árbol KD es muy rápido para búsquedas de vecinos de baja dimensión (D < 20), su eficiencia disminuye cuando D aumenta.
Las propiedades de los árboles KD son adecuadas para utilizar la distancia euclidiana.
BallTree
BallTree resuelve el problema de la ineficiencia de KDTree en grandes dimensiones.
Los árboles construidos de esta manera consumen más tiempo que los árboles KD, pero esta estructura de datos funciona muy bien para datos altamente estructurados, incluso en dimensiones altas.
El árbol KD es un árbol construido dividiendo secuencialmente la mediana del eje K-dimensional; el árbol esférico divide el espacio muestral según el centro de masa C y el radio r, y cada nodo es un hiperesfera. En otras palabras, para el espacio objetivo (q, r), se atravesarán todos los subespacios dentro de todas las subhiperesferas truncadas por la hiperesfera.
BallTree reduce el número de puntos candidatos para la búsqueda del vecino más cercano utilizando la desigualdad del triángulo: |x+y|<=|x|+|y|| debe calcularse una vez. La distancia entre centros es suficiente para determinar los límites superior e inferior de las distancias para todos los puntos dentro del nodo. Debido a la geometría esférica de los nodos del árbol esférico, funciona mejor que los árboles KD en dimensiones altas, aunque el rendimiento real depende en gran medida de la estructura de los datos de entrenamiento.
BallTree es adecuado para distancias más generales.
1. Ventajas
Algoritmo de clasificación muy simple, ningún otro, fácil de usar, fácil de entender, fácil de implementar
Muy adecuado para tratar con múltiples problemas de clasificación, como Usuarios recomendados
Se puede utilizar tanto para datos numéricos como para datos discretos, tanto para clasificación como para regresión
Insensible a valores atípicos
2, Desventajas
El algoritmo es lento y tiene una gran complejidad temporal porque necesita calcular la distancia desde la muestra desconocida hasta todas las muestras conocidas.
El equilibrio de la muestra depende en gran medida cuando se produce un desequilibrio extremo de la muestra. En este caso, la clasificación definitivamente estará sesgada. Puede ajustar el peso de la muestra para mejorarla.
La interpretabilidad es pobre y no se pueden dar reglas similares a los árboles de decisión.
Cuanto mayor sea el valor. dimensión del vector, mayor es la euclidiana La capacidad discriminativa de la distancia es más débil
El espacio muestral es demasiado grande e inapropiado porque la cantidad de cálculo es demasiado grande y la velocidad de predicción es lenta
Clasificación de texto
Recomendación del usuario
Problema de regresión
1) Seleccione aleatoriamente k observaciones de todas las instancias de observación como centros de grupo y luego recorra las observaciones restantes para encontrar la distancia del centro del grupo más cercana entre puntos y agregarlos al grupo. De esta manera, obtenemos un resultado de agrupación inicial, que es un proceso iterativo.
2) Cada uno de nuestros centros de conglomerados tiene al menos una instancia de observación, por lo que podemos encontrar el punto central (MEDIOS) de cada conglomerado como el nuevo centro del conglomerado y luego recorrer todas las observaciones para encontrar el centro más cercano. apunte y agréguelo al clúster. Luego continúa corriendo 2).
3) Ejecute 2) hasta obtener exactamente el mismo punto central del cluster en las dos iteraciones.
La complejidad temporal de este algoritmo es O(tkmn):O(tkmn), donde t es el número de iteraciones, k es el número de clústeres, m es el número de registros y n es el número de dimensiones;
Complejidad espacial: O((m+k)n), donde k es el número de clústeres, m es el número de registros y n es el número de dimensiones.
Ámbito de aplicación:
El algoritmo K-menas intenta encontrar grupos que minimicen la función de criterio de error simple. Los resultados de agrupación de este algoritmo son más ideales cuando la forma de los grupos subyacentes es convexa, las diferencias entre los grupos son grandes y los tamaños de los grupos son similares. Como se mencionó anteriormente, la complejidad temporal de este algoritmo es O (tkmn), que es lineal en el número de muestras, por lo que es muy eficiente y escalable al procesar grandes conjuntos de datos. Sin embargo, además de tener que determinar el número de conglomerados K de antemano y ser sensible a los centros iniciales de los conglomerados, este algoritmo también es sensible al "ruido" y a los puntos aislados, y no es adecuado para descubrir conglomerados con formas no convexas o grupos con grandes diferencias en tamaño, por lo que el algoritmo a menudo termina en un óptimo local.
1) En primer lugar, este algoritmo solo puede encontrar clústeres óptimos localmente, no clústeres óptimos globalmente. Además, los resultados de este algoritmo dependen en gran medida de la ubicación de los centros de conglomerados inicialmente seleccionados al azar. Ejecutamos el algoritmo varias veces con diferentes centros de clúster generados aleatoriamente, luego usamos la función evaluar (C) para evaluar los resultados respectivos C y elegimos el que tiene el valor de evaluación (C) más pequeño entre los múltiples resultados.
La idea básica de seleccionar semillas iniciales para el algoritmo k-means++ es que los centros del grupo inicial deben estar lo más lejos posible entre sí
2) Respecto a la selección del valor k inicial. Lo primero que pensamos es en la evaluación (C) utilizada anteriormente. Sin embargo, cuanto mayor es k, más centros de conglomerados hay y, obviamente, menor es la suma de las distancias al cuadrado entre cada observación y su centro. Esto también se ha verificado en la práctica. Este tema se discutirá en detalle en el análisis de los resultados experimentales en la Sección 4.
3) Sobre el rendimiento. En el algoritmo original, la distancia entre cada observación y todos los centros de los grupos debe calcularse en cada iteración. ¿Hay alguna manera de mejorar la eficiencia? Sí, podemos utilizar estructuras de datos como árboles k-d o árboles de bolas para mejorar la eficiencia del algoritmo. Bajo ciertas condiciones, para un área de observación determinada, todos los puntos del área se pueden clasificar en el grupo más cercano sin atravesar cada punto de observación. La sección 3 presentará esto en detalle.
Similitudes: Ambos implican el proceso de, dado un punto, encontrar la aproximación más cercana a ese punto en un conjunto de datos. Es decir, ambos utilizan el algoritmo NN (vecino más cercano) y los árboles KD se utilizan a menudo para implementar NN.
1) árbol k-d[5]
Coloque las instancias de características n-dimensionales observadas en un espacio n-dimensional, y el árbol k-d selecciona una a la vez a través de un determinado algoritmo ( eje de coordenadas), cree un hiperplano para dividir uno de sus valores, divida todas las observaciones actuales en dos partes y luego use el mismo método para cada parte hasta que se alcance una determinada condición.
En la expresión anterior, hay varios lugares que se presentarán en detalle a continuación: (1) El método de selección de características (eje) (2) Qué característica se utiliza como límite (3) Bajo qué condiciones en las que termina el algoritmo.
(1) Selección de características
Calcule la varianza de cada característica en el conjunto de datos de observación actual, seleccione la característica con la mayor variación y luego dibuje un hiperplano perpendicular a la característica a combinar todas las observaciones Los datos se dividen en dos grupos.
(2) Qué valor de la característica es el límite, es decir, la posición exacta del hiperplano perpendicular al eje de coordenadas seleccionado.
Primero, la varianza mediana (mediana) de cada punto se utiliza como límite. Esto producirá un árbol muy equilibrado que separa uniformemente un conjunto. El problema con esto es que si la distribución de puntos tiene una pendiente baja, entonces elegir la mediana dará como resultado divisiones continuas en la misma dirección, lo que resultará en hiperrectángulos alargados.
Otro enfoque consiste en calcular la media de estos puntos en el eje y seleccionar el punto más cercano a la media como punto de intersección del hiperplano con el eje. De esta manera, el árbol no estará perfectamente equilibrado, pero las regiones tenderán a dividirse ortogonalmente y es más probable que se produzcan divisiones sucesivas en diferentes direcciones.
(3) ¿Qué condiciones deben cumplirse para que finalice el algoritmo?
De hecho, cuando el nodo hoja solo contiene dos puntos, no es necesario indicarle al nodo hoja que finalizar el algoritmo. Puede establecer un valor mínimo predeterminado y finalizar el algoritmo cuando se alcance ese valor mínimo.
En la Figura 6, el asterisco marca el punto objetivo. Primero encontramos el área donde se encuentra este punto en el árbol k-d y luego calculamos las distancias de los puntos contenidos en esta área para encontrar el. punto más cercano (punto negro), si otras áreas también contienen puntos más cercanos, entonces este punto debe estar en un círculo con estos dos puntos como radio. Supongamos que este círculo contiene las otras áreas como se muestra. Primero verifique el área correspondiente a los nodos hermanos del área, que no se superpone con el círculo, luego verifique el área correspondiente a los nodos hermanos de su nodo gemelo; Mire el área correspondiente a sus nodos secundarios (el gráfico se superpone con el área correspondiente a los nodos secundarios de los nodos hermanos del nodo principal). Vea si hay nodos más cercanos.
La ventaja de los árboles k-d es que se pueden actualizar gradualmente. Se pueden agregar nuevas observaciones continuamente. Encuentre el área donde se encuentra el nuevo punto de observación y, si el área está vacía, agréguela; de lo contrario, divida el área a lo largo del lado más largo para acercarla a un cuadrado. Esto altera el equilibrio del árbol y hace que el área sea menos propicia para encontrar vecinos cercanos. Cuando la profundidad del árbol alcanza un cierto valor, podemos reconstruir el árbol.
Sin embargo, los árboles K-D también tienen algunos problemas. Los rectángulos no son la mejor manera de usarlos aquí. Un conjunto de datos sesgado puede crear un conflicto entre nuestro deseo de mantener el árbol equilibrado y mantener la naturaleza cuadrada de la región. Además, un rectángulo o incluso un cuadrado no es la mejor forma debido a las esquinas.
Si el círculo en la Figura 6 es más grande, es decir, el punto negro está más lejos del punto objetivo, entonces el círculo se cruzará con el rectángulo en la esquina superior izquierda, por lo que se debe verificar otro punto en el área, y esto area es el nodo padre del área actual. Los nodos secundarios de los nodos hermanos.
Para resolver los problemas anteriores, introdujimos el árbol de bolas.
2) Árbol de esferas [4]
La forma de resolver el problema anterior es usar hiperesfera en lugar de hiperrectángulo para dividir el área. El uso de esferas puede provocar superposición entre esferas, pero esto no es crítico. Un árbol de esferas es una hiperesfera de k dimensiones que se utiliza para superponer estas observaciones y colocarlas en un árbol. La Figura 7(a) muestra un plano bidimensional que contiene 16 instancias de observación, y la Figura 7(b) muestra su árbol de bolas correspondiente, donde los números en los nodos representan el número de observaciones incluidas.
Se dibujan diferentes niveles de círculos en diferentes estilos. Cada nodo en el árbol corresponde a un círculo. El número de nodos representa el número de observaciones contenidas en el área, pero no necesariamente representa la cantidad de puntos contenidos en el área en el gráfico. Debido a que hay superposición, solo se puede realizar una observación. pertenecer a un área. Los nodos del árbol de bolas real representan el centro y el radio del círculo. Los nodos de hoja representan las observaciones que contienen.
Para utilizar un árbol de bolas, trabaje de arriba a abajo para encontrar el nodo de hoja que contiene el objetivo y encuentre la observación más cercana a ese nodo. Esta distancia es el límite superior de la distancia del vecino más cercano. Comprueba si sus hermanos contienen observaciones menores que este límite superior. El método específico es que si la distancia entre el punto objetivo y el centro del nodo hermano es mayor que el valor del centro del círculo más el valor límite superior anterior, entonces el nodo hermano no puede contener el punto de observación requerido. (Como se muestra en la Figura 8). De lo contrario, verifique si el nodo hermano contiene un punto de observación calificado.
Entonces, ¿cuál es el algoritmo de segmentación del árbol de bolas?
Seleccione el punto de observación i1 más alejado del centro actual del círculo y el punto de observación i2 más alejado de i1, y asigne a los centros todos los puntos de observación más cercanos a estos dos puntos en el círculo. de estos dos grupos. Luego se calcula el punto central de cada grupo y el radio mínimo que contiene todos los puntos de observación a los que pertenece. La segmentación de un hipercírculo que contiene n observaciones requiere sólo un tiempo lineal.
Al igual que con los árboles k-d, si un nodo contiene un número mínimo predefinido de observaciones, el vértice ya no se puede dividir.