filosofia computacional

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´s Vasco–Euskal Herriko Unibertsitatea
ı

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 esque
a
un nuevo 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 estetema se estudian m´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 )

1
.
.
.

X1
x11
.
.
.

...
...

Xj
x1j
.
.
.

...
...

Xn
x1n
.
.
.

C
c1
.
.
.

(xi , ci )

i
.
.
.

xi1
.
.
.

...

xij
.
.
.

...

xin
.
.
.

ci.
.
.

N
N +1

xN 1
xN +1,1

...
...

xN j
xN +1,j

...
...

xN n
XN +1,n

cN
?

(xN , cN )
x

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 posibles valores 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 calculanlas 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´s cercanos 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
aFigura 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 , y se 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-NNpredice 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 casose 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...