Knn

De Viquipèdia
Dreceres ràpides: navegació, cerca

El KNN (o veí més proper) és un classificador (model discriminador) d'aprenentatge supervisat no paramètric que, amb una imatge d'entrada a classificar, busca les K imatges d'entrenament que més s'hi assemblen per, posteriorment, seleccionar la classe més abundant entre les K possibilitats. En reconeixement de patrons, l'algorisme del knn és un mètode per 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 a l'entrenament s'assemblen més a la nova observació a classificar per seguidament assignar-li la classe més comú entre aquestes K a la nova mostra.

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

Elecció de la K

Per 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 majoría de vots dels seus veïns, amb la intenció de ser assignat a la classe més comú 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'entrenment o models) per als quals es coneix la classificació correcte. L'argorisme KNN és sensible a la estructura local de les dades. Les regles de KNN calculen de forma implícita els hiperplans de decisió entre les diferents classes.


Algorisme[modifica | modifica el codi]

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

El espacio es particionado en regiones por localizaciones y etiquetas de los ejemplos de entrenamiento. Un punto en el espacio es asignado a la clase C si esta es la clase más frecuente entre los k ejemplos de entrenamiento más cercano. Generalmente se usa la distancia euclidiana.

La fase de entrenament per k-NN consisteix simplement en 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 el 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 distancia que s'utilitza la distancia euclidiana


d(x_i,x_j) = \sqrt{\sum_{r=1}}^p (x_ir - x_jr)^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 dispongui 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[modifica | modifica el codi]

El classificador K-NN és un classificador fàcil d'implementar , però no per això amb dolents resultats, precisament atorga bons resultats a la classificació. Però quan tenim un gran volum de dades pot ser costós a nivell computacional. 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. KNN 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[modifica | modifica el codi]

Veïns més propers amb distància ponderada Per tal de obtenir uns millors resultats de la classificació, podem ponderar les distancies en l'etapa de votació, és a dir, per a cada un dels k veïns s'obtindrà un pes wi relacionat amb la distancia, de forma que els veïns més propers tinguin major influencia 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 altre variant d'aquest mètode de distancia ponderada és ponderar el vot de cada veí d'acord al quadrat invers de la seva distancia.

\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 un promitjat dels k veïns més propers l'algoritme pot evitar l'impacte de exemples al soroll aïllat.

Enllaços externs[modifica | modifica el codi]

Referències[modifica | modifica el codi]