KNN significa K Nearest Neighbourd o en castellano «los k vecinos más cercanos». Es un algoritmo de clasificación (indica aque clase pertenece uque parte de unos datos de ejemplo ya clasificados contra los que compara con los nuevos datos.

Supongamos que tenemos un montón de ejemplo clasificados. Estos ejemplos están repartidos en un espacio de N dimensiones o, dicho de forma más cercana a los programadores, cada caso es un vector de N elementos. Cuando nos dan un punto nuevo, que no está en los ejemplos, podemos ver de que clase son los K vecinos más cercanos y concluir que el nuevo punto, posiblemente, es de la clase mayoritaria.

Este algoritmo requiere calcular la distancia a cada vecino, ordenarlos según esta distancia y elegir los k primeros.

Implementación

Podemos usar la librería Arduino_KNN.h. No ha sido pensada de propio para Arduino UNO, sin embargo funciona sin problemas con él. Su uso es muy sencillo basta con proporcionar cada uno de los ejemplos y la clase a la que corresponde.

El primer paso es incluir la librería:

#include <Arduino_KNN.h>

Luego creamos una instancia a de la clase KNNClassifier indicando cual es la dimensión de nuestros datos:

KNNClassifier myKNN(2);

Para añadir ejemplos se usa la función addExample(), pasando en el primer parámetro el vector que representa al vecino y en el segundo la clase (que debe de ser un entero).

myKNN.addExample(example1, 1);

Finalmente, cuando todos los ejemplos están añadidos se puede clasifica un elemento con la función classify(); Que toma como primer parámetro el elemento a clasificar y como segundo el número de vecinos K a comparar:

int myKNN.classify(input, k);

Veamos un ejemplo adaptado de los de la librería :

#include <Arduino_KNN.h>

KNNClassifier myKNN(2);

void setup() {
  Serial.begin(9600);
  while (!Serial);

  Serial.println("Añadiendo ejemplos: ");
  Serial.println();

  // add examples to KNN
  float example1[] = { 7.0, 7.0 }; // clase 1
  float example2[] = { 5.0, 5.0 }; // clase 2
  float example3[] = { 9.0, 9.0 }; // clase 3
  float example4[] = { 6.0, 6.0 }; // clase 2

  myKNN.addExample(example1, 1); // clase 1
  myKNN.addExample(example2, 2); // clase 2
  myKNN.addExample(example3, 3); // clase 3
  myKNN.addExample(example4, 2); // clase 2

  Serial.println("Clasificar entrada:");

  float input[] = { 5.5, 5.5 };

  int classification = myKNN.classify(input, 3); // K = 3

  Serial.print("Clasificacion = ");
  Serial.println(classification);
}

void loop() {

}

Confianza

Hay una medida que puede servir de guía de lo segura que es cada estimación, la confianza. Su valor esta entre 0 y 1, siendo 1 el máximo de confianza. Se calcula tomando todos los vecinos que entran dentro de «los K vecinos más cercanos» se cuentan aquellos cuya clase es mayoritaria y se divide por K. Por ejemplo si tenemos K igual a 5 y hay 3 vecinos de la misma clase C1, la confianza de la clasificación será de 3/5 = 0,6 . Si todos los vecinos fueran de la clase C1 la confianza seria de 5/5 = 1. La clasificación en ambos casos puede ser la misma, la clase C1, pero la confianza no.

Para saber la confianza de una clasificación en la librería Arduino_KNN.h podemos llamar a la función confidence() justo después de realizar la clasificación.

float myKNN.confidence();

NN El vecino más cercano

Tiene una estrategia aún mas simple. Buscas el ejemplo más cercano y le asignas la misma clase. Se la conoce como NN Nearest Neighbourd (el vecino más cercano). Aunque no es la forma más optima de implementarlo se puede como el algoritmo KNN usado K = 1.

 int classification = myKNN.classify(input, 1);