Knn

El k-NN (o veí més proper) és un classificador (model discriminador) d'aprenentatge supervisat no paramètric usat en classificació estadística i anàlisi de la regressió.

Descripció

Amb una imatge d'entrada a classificar, busca les K imatges d'entrenament que més s'hi assemblen per a, posteriorment, seleccionar la classe més abundant entre les K possibilitats. En reconeixement de patrons, l'algorisme del k-NN és un mètode per a classificar objectes basant-se en els exemples més propers de l'espai de característiques. Aquest classificador treballa cercant primer quines de les K observacions classificades en l'entrenament s'assemblen més a la nova observació a classificar per a, seguidament, assignar-li la classe més comuna entre aquestes K en la nova mostra.

Fem servir l'algoritme k-NN com a mètode de classificació d'objectes en el reconeixement de patrons.

Elecció de la K

Per a fer una bona elecció del paràmetre K, ens haurem de basar principalment en les dades.

Trobem, per exemple, que valors grans de K redueixen el problema del soroll a la classificació, però que, per altra banda, creen límits entre classes semblants. Un bon valor de K pot ser seleccionat mitjançant una optimització d'ús (fer proves fins a trobar un valor de k que ens doni bons resultats). K acostuma a ser un nombre enter positiu senar.

En un dels algorismes de classificació més simples; una mostra es classifica per la majoria dels vots dels seus veïns, amb la intenció de ser assignat a la classe més comuna entre els seus veïns més propers.

Un cas especial el trobem per K=1 anomenat Nearest Neighbor Algorithm.

Trobem els punts febles d'aquest algorisme en l'alta presència de soroll o de característiques irrellevants. També trobem problemes si les escales de característiques no són consistents.

Els veïns els obtenim d'un conjunt de mostres (conjunt d'entrenament o models) per als quals es coneix la classificació correcta. L'algorisme KNN és sensible a l'estructura local de les dades. Les regles de k-NN calculen de forma implícita els hiperplans de decisió entre les diferents classes.

Algorisme

Els exemples d'entrenament són vectors en un espai de característiques multidimensional, cada etiqueta té un vector de característiques associat.

$x_{i}=(x_{1i},x_{2i},...,x_{pi})\in X$

L'espai és particionat en regions per localitzacions i etiquetes dels exemples d'entrenament. Un punt a l'espai és assignat a la classe C si aquesta és la classe més freqüent entre els k exemples d'entrenament més proper. Generalment, s'empra la distància euclidiana.

La fase d'entrenament per k-NN consisteix simplement a emmagatzemar tots els casos coneguts i les seves etiquetes de classe. Si tenim la mostra a classificar (‘I’) i també tenim les noves instàncies (‘t’) hem de seguir els següents passos.

1. Calculi la distància entre l'element a classificar ('I') i cada model de l'entrenament ('t)
2. Ordena les distàncies en ordre numèric ascendent i recollir elements dels k primers
3. Calcular i retornar la classe més freqüent en els 'k' veïns més propers.

Generalment, la distància que s'usa és la distància euclidiana

$d(x_{i},x_{j})={\sqrt {\sum _{r=1}}}^{p}(x_{i}r-x_{j}r)^{2}$

Els exemples d'entrenament són vectors en un espai de característiques multidimensionals, cadascun amb una etiqueta de classe. La fase d'entrenament de l'algorisme consisteix crear models amb elements que tenen assignats les seves característiques. De manera que un cop entrenat, el sistema disposi d'exemples a comparar amb el nou element.

En la fase de classificació, K és una constant definida per l'usuari, i un vector sense marcar (una consulta o punt de prova) es classifica mitjançant l'assignació de l'etiqueta, que és més freqüent entre les K mostres d'entrenament més properes a aquest punt de la consulta. Una mètrica de distància utilitzada per a les variables contínues és la distància euclidiana. Sovint, la precisió de la classificació de k-NN es pot millorar significativament si la distància mètrica s'aprèn amb algorismes especialitzats com a ampli marge les Veí més proper o l'anàlisi dels components de veïnatge.

Propietats

El classificador k-NN és un classificador fàcil d'implementar, però no per això té mals resultats. Precisament obté bons resultats en la classificació. Però quan tenim un gran volum de dades pot ser costós computacionalment. També depèn del valor K que assignem prèviament. Un valor de K adequat pot estalviar cost computacional encara que tinguem grans volums de dades. k-NN està garantit per apropar-se a l'error de Bayes per a algun valor de k (on k augmenta en funció del nombre de punts de dades). Diverses millores per a k-NN són possibles mitjançant l'ús de les gràfiques de proximitat.

Variants de l'algoritme bàsic

Veïns més propers amb distància ponderada Per tal d'obtenir uns millors resultats de la classificació, podem ponderar les distàncies en l'etapa de votació, és a dir, per a cada un dels k veïns s'obtindrà un pes wi relacionat amb la distància, de forma que els veïns més propers tinguin major influència sobre el resultat final. Es pot implementar fent que els pesos compleixin que 0≤wi≤1 fent que la suma de pesos sigui 1.

0 ≤ w_i ≤ 1 $\sum _{i}w_{i}=1$

Una altra variant d'aquest mètode de distància ponderada és ponderar el vot de cada veí d'acord amb el quadrat invers de la seva distància.

${\hat {f}}(x_{q})\leftarrow argmax_{v\in V}\sum _{i=1}^{k}w_{i}\delta (v,f(x_{i}))$

on

$w_{i}\equiv {\frac {1}{d(x_{q},x_{i})^{2}}}$

D'aquesta manera es veu com no hi ha risc de permetre a tots els exemples d'entrenament contribuir a la classificació de l'element a classificar, ja que si són molt distants no tenen un pes associat. Aquesta millora és molt efectiva. És robust per problemes de soroll de dades i bastant efectiu amb grans conjunts de dades. Es pot veure com quan fem una mitjana dels k veïns més propers l'algoritme pot evitar l'impacte d'exemples al soroll aïllat.

Enllaços externs

• Classification problem: k-Nearest neighbor algorithm
• K Nearest Neighbors - Classification Arxivat 2012-08-15 a Wayback Machine.
• Identificació automàtica de càmeres en produccions televisives amb el classificador K-veïns més propers
• Algoritmo KNN basado en Informacion´ Mutua para Clasificación de Patrones con Valores Perdidos