Clasificador k-Nn

Tema 5. Clasificadores K-NN
Abdelmalik Moujahid, I˜aki Inza y Pedro Larra˜aga n n Departamento de Ciencias de la Computaci´n e Inteligencia Artificial o Universidad del Pa´ Vasco–Euskal Herriko Unibertsitatea ıs

9.1 Introducci´n o En este tema vamos a estudiar un paradigma clasificatorio conocido como K-NN (KNearest Neighbour). La idea b´sica sobre la que se fundamenta este paradigma es que a unnuevo caso se va a clasificar en la clase m´s frecuente a la que pertenecen sus a K vecinos m´s cercanos. El paradigma se fundamenta por tanto en una idea muy a simple e intuitiva, lo que unido a su f´cil implementaci´n hace que sea un paradigma a o clasificatorio muy extendido. Despu´s de introducir el algoritmo K-NN b´sico y presentar algunas variantes del e a mismo, en este tema se estudianm´todos para la selecci´n de prototipos. e o 9.2 El algoritmo K-NN b´sico a La notaci´n a utilizar (v´ase la Figura 1) en este tema es la siguiente: o e
(x1 , c1 ) (xi , ci ) (xN , cN ) x 1 . . . i . . . N N +1 X1 x11 . . . xi1 . . . xN 1 xN +1,1 ... ... ... ... ... Xj x1j . . . xij . . . xN j xN +1,j ... ... ... ... ... Xn x1n . . . xin . . . xN n XN +1,n C c1 . . . ci . . . cN ?

Figura 1:Notaci´n para el paradigma K-NN o

D indica un fichero de N casos, cada uno de los cuales est´ caracterizado por n a variables predictoras, X1 , . . . , Xn y una variable a predecir, la clase C. Los N casos se denotan por (x1 , c1 ), . . . , (xN , cN ) xi = (xi,1 . . . xi,n ) ci ∈ {c1 , . . . , cm } donde para todo i = 1, . . . , N para todo i = 1, . . . , N

c1 , . . . , cm denotan los m posiblesvalores de la variable clase C. El nuevo caso que se pretende clasificar se denota por x = (x1 , . . . , xn ). En la Figura 2 se presenta un pseudoc´digo para el clasificador K-NN b´sico. Tal o a y como puede observarse en el mismo, se calculan las distancias de todos los casos ya clasificados al nuevo caso, x, que se pretende clasificar. Una vez seleccionados los k a e a K casos ya clasificados, Dx m´scercanos al nuevo caso, x, a ´ste se le asignar´ la
1

COMIENZO Entrada: D = {(x1 , c1 ), . . . , (xN , cN )} x = (x1 , . . . , xn ) nuevo caso a clasificar PARA todo objeto ya clasificado (xi , ci ) calcular di = d(xi , x) Ordenar di (i = 1, . . . , N ) en orden ascendente K Quedarnos con los K casos Dx ya clasificados m´s cercanos a x a K Asignar a x la clase m´s frecuente en Dx a FIN Figura 2:Pseudoc´digo para el clasificador K-NN o

k clase (valor de la variable C) m´s frecuente de entre los K objetos, Dx . La Figura a 3 muestra de manera gr´fica un ejemplo de lo anterior. Tal y como puede verse en a

Figura 3: Ejemplo de aplicaci´n del algoritmo K-NN b´sico o a

la Figura 3 tenemos 24 casos ya clasificados en dos posibles valores (m = 2). Las variables predictoras son X1 y X2 , yse ha seleccionado K = 3. De los 3 casos ya clasificados que se encuentran m´s cercanos al nuevo caso a clasificar, x (representado a por •), dos de ellos pertenecen a la clase ◦, por tanto el clasificador 3-NN predice la clase ◦ para el nuevo caso. N´tese que el caso m´s cercano a x pertenece a la clase o a +. Es decir, que si hubi´semos utilizado un clasificador 1-NN, x se hubiese asignado e a +.Conviene aclarar que el paradigma K-NN es un tanto at´ ıpico si lo comparamos con el resto de paradigmas clasificatorios, ya que mientras que en el resto de paradigmas la clasificaci´n de un nuevo caso se lleva a cabo a partir de dos tareas, como son la o inducci´n del modelo clasificatorio y la posterior deducci´n (o aplicaci´n) sobre el o o o nuevo caso, en el paradigma K-NN al no existir modelo expl´ıcito, las dos tareas anteriores se encuentran colapsadas en lo que se acostumbra a denominar transinducci´n. o En caso de que se produzca un empate entre dos o m´s clases, conviene tener una regla a
2

heur´ ıstica para su ruptura. Ejemplos de reglas heur´ ısticas para la ruptura de empates pueden ser: seleccionar la clase que contenta al vecino m´s pr´ximo, seleccionar la a o clase con...