Tratar con lazos, pesas y votar en kNN

Estoy programando un algoritmo kNN y me gustaría saber lo siguiente:

Tie-breaks:

1. ¿Qué sucede si no hay un ganador claro en la votación mayoritaria? Por ejemplo, todos los vecinos más cercanos k son de diferentes clases, o para k = 4 hay 2 vecinos de la clase A y 2 vecinos de la clase B?
2. ¿Qué sucede si no es posible determinar exactamente k vecinos más cercanos porque hay más vecinos que tienen la misma distancia? Por ejemplo, para la lista de distancias (x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2), no sería posible determinar los vecinos más cercanos k = 3 o k = 4, porque los vecinos 3 ° a 5 ° tienen la misma distancia.

Pesos:

1. Leí que es bueno ponderar a los vecinos más cercanos antes de seleccionar la clase ganadora. ¿Cómo funciona? Es decir, ¿cómo se ponderan los vecinos y cómo se determina la clase?

Alternativas de voto mayoritario:

1. ¿Existen otras reglas / estrategias para determinar la clase ganadora además del voto mayoritario?

La forma ideal de romper un empate para un vecino más cercano k en mi opinión sería disminuir k en 1 hasta que haya roto el empate. Esto siempre funcionará independientemente del esquema de ponderación de votos, ya que un empate es imposible cuando k = 1. Si aumentara k , en espera de su esquema de ponderación y el número de categorías, no podría garantizar un quiebre de empate.

Al hacer kNN, debe tener en cuenta una cosa, a saber, que no es un algoritmo estrictamente derivado matemáticamente, sino un simple clasificador / regresor basado en una intuición: la función subyacente no cambia mucho cuando los argumentos no cambian mucho. O en otras palabras, la función subyacente es localmente casi constante. Con este supuesto, puede estimar el valor de la función subyacente en cualquier punto dado, por una media (posiblemente ponderada) de los valores de los k puntos más cercanos.

Teniendo esto en cuenta, puede darse cuenta de que no hay un imperativo claro sobre qué hacer cuando no hay un ganador claro en la votación por mayoría. Siempre puede usar una k impar, o usar una ponderación inyectiva.

En el caso de que los vecinos 3 a 5 estén a la misma distancia del punto de interés, puede usar solo dos o usar los 5. Nuevamente, tenga en cuenta que kNN no es un algoritmo derivado de un análisis matemático complejo, sino solo un intuición simple Depende de usted cómo quiere lidiar con esos casos especiales.

$\frac{1}{||x-y||^2}$

También ha habido un buen artículo de Samory Kpotufe y Abdeslam Boularias este año sobre NIPS tocando el tema de encontrar la ponderación correcta. Su intuición general es que la función subyacente varía de manera diferente en diferentes direcciones (es decir, sus diferentes derivadas parciales son de diferente magnitud), por lo tanto, sería aconsejable cambiar en algún sentido las métricas / ponderaciones de acuerdo con esta intuición. Afirman que este truco generalmente mejora el rendimiento de kNN y la regresión del núcleo, y creo que incluso tienen algunos resultados teóricos para respaldar esta afirmación (aunque no estoy seguro de qué afirman realmente esos resultados teóricos, no tuve tiempo para ir a través de todo el documento todavía). El documento se puede descargar de forma gratuita desde sus sitios o después de buscar en Google "Gradient Weights ayuda a los regresores no paramétricos".

Ahora, probablemente querrá saber cómo puede encontrar la k, la métrica, la ponderación y la acción correctas para realizar cuando hay sorteos, etc. Lo triste es que, básicamente, es difícil llegar a los hiperparámetros correctos después de pensarlo profundamente, probablemente necesitará probar diferentes grupos de hiperparámetros y ver cuáles funcionan bien en algún conjunto de validación. Si tiene algunos recursos computacionales y desea llegar automáticamente a los parámetros correctos en un buen conjunto de hiperparámetros, existe una idea reciente (que me gusta mucho) de utilizar procesos gaussianos para la optimización sin derivaciones en ese entorno.

Permítanme explicarlo: encontrar el conjunto de hiperparámetros (es decir, que minimizan el error en los datos de validación) puede verse como un problema de optimización. Desafortunadamente, en esta configuración no podemos obtener el gradiente de la función que intentamos optimizar (que es lo que generalmente queremos hacer, realizar el descenso del gradiente o algunos métodos más avanzados). Los procesos gaussianos se pueden utilizar en esta configuración, para encontrar conjuntos de hiperparámetros, que tienen grandes posibilidades, de desempeñarse mejor que los mejores que hemos encontrado hasta el momento. Por lo tanto, puede ejecutar el algoritmo de forma iterativa con algún conjunto de hiperparámetros, luego preguntar en el proceso gaussiano cuáles serían los mejores para probar a continuación, probar esos, y así sucesivamente.

Para más detalles, busque el documento "Optimización práctica bayesiana de algoritmos de aprendizaje automático" de Jasper Snoek, Hugo Larochelle y Ryan P Adams (que también se puede encontrar en sus sitios web o en Google).

Acerca de esta parte del empate, la mejor idea de referencia para los empates suele ser la ruptura aleatoria, por lo que seleccionar una clase aleatoria de todos los que ganan la votación y seleccionar aleatoriamente un subconjunto de objetos empatados lo suficientemente grandes como para llenar k.

Tal solución enfatiza el hecho de que esos son casos patológicos que simplemente no proporcionan suficiente información para tomar una decisión en el régimen de kNN. Por cierto, si son comunes a sus datos, ¿tal vez debería intentar una distancia de diferenciación más?

Una forma posible es hacer que el algoritmo aumente o disminuya automáticamente k hasta obtener un claro ganador.