Minería de Datos –
Ingeniería Civil en
Bioinformática
Algoritmos de clasificación
Método de Vecinos Cercanos - KNN
16 junio 2021
¿Cómo funcionan?
• Notar que corresponde a una serie de
reglas o decisiones se van tomando.
• Ordenadas de la mas general a la más
específica
• La cuestión es ¿como se generan estas
reglas? ¿de donde salen?
Modelos supervisados
Ejemplo sencillo de clasificación
- -
- - + +
- - + +
- - - -
- + + + - + + +
- + - + +
- +
+ - + + +
+ +
+ γ +
γ
Buenos atributos o características
• Objetos de la misma clase, poseen características
similares.
“Buenos” atributos “Malos” atributos
Sobre ajuste de modelos de aprendizaje
Problema: que tan complejo o sofisticado tiene que ser mi
modelo.
Sub-ajustado Buen ajuste Sobre-ajustado
Modelo de Clasificación
Set de Entrenamiento
output conocido
Validar con
Set Testeo
Algoritmo de
Clasificación
Modelo
Clasificación
Nuevo(s) Nuevo(s) ejemplo(s)
ejemplo(s) Clasificados
¿Como funcionan los modelos de
clasificación?
Hay que entrenar los modelos –
generar un modelo
• Set de entrenamiento
• Pruebo varios modelos para ver cual es mejor
• Validación cruzada para escoger el mejor
modelo.
El modelos después se utiliza para
clasificar nuevos ejemplo
• El modelo se aplica a nuevas situaciones
Ejemplo Problema de Clasificación
ID Clase Real atr 1 atr 2 atr 3
1 C1 azul A 2
2 C2 rojo A 2 ¿Cómo clasifico los siguientes ejemplos?
3 C3 verde B 4
4 C2 azul B 4 P1) Rojo, A, 4 ¿?
5 C1 rojo C 6
6 C3 verde C 6
7 C1 azul A 4 P2) Verde, B, 6 ¿?
8 C3 rojo B 2
9 C2 verde C 6
10 C3 azul C 4
11 C1 rojo B 6
12 C2 verde A 1
¿Ideas?
¿Cómo clasifico los siguientes ejemplos?
Ejemplo Problema de Clasificación P1) Rojo, A, 4 ¿?
ID Clase Real atr 1 atr 2 atr 3
1 C1 azul A 2 P2) Verde, B, 6 ¿?
2 C2 rojo A 2
3 C3 verde B 4
4 C2 azul B 4
5 C1 rojo C 6
6 C3 verde C 6
7 C1 azul A 4
8 C3 rojo B 2
9 C2 verde C 6
10 C3 azul C 4
11 C1 rojo B 6
12 C2 verde A 1
Modelos de distinto tipo
Clasificar por vecindad o cercanía
Clasificar o asignar en base a una serie de reglas o condiciones
(basadas en valores de atributos)
Clasificar o asignar en base a probabilidad de pertenecer a una de
las clases (que clase tiene mayor probabilidad)
Clasificar en base a una función matemática (score o valor)
Clasificar en base a combinar varios modelos (mejor combinar
distintas visiones u opiniones)
Métodos de Clasificación por
Vecindad
• Parece razonable clasificar un nuevo ejemplo en base a
la similitud que este tiene con un ejemplo conocido.
• Método de los k vecinos más cercanos o próximos
– K= 1,…,N
• kNN – k nearest neighbor – k vecinos cercanos
• Ejemplos de uso de este tipo de métodos utilizados
comúnmente:
– ¿?
Métodos de Clasificación por
Vecindad
• La idea general es aprender de ejemplos conocidos, para
tomar decisión sobre nuevos casos
• Actuar como en situaciones parecidas o similares.
• Asignar un nuevo a caso a un grupo de ejemplos
similares
• Que se entiende por “similitud”??
• Pareciera ser inversamente proporcional a una cierta
medida de “distancia” entre ejemplos
Métodos de Clasificación por
Vecindad
• La idea es resolver un problema de clasificación basado
en la información extraída de un conjunto de ejemplos
existentes y conocidos (aprendizaje supervisado).
• En este caso la clasificación se basa en información de
un conjunto de ejemplos “VECINOS” al nuevo objeto a
clasificar.
• Se requiere definir cierta medida de disimilitud (o
distancia) entre los distintos elementos del espacio de
representación. Y comparar distancia entre distintos
objetos.
Clasificación por vecindad
Benigna
Maligna
Nuevo Caso
Clasificación por vecindad
Benigna
Maligna
Nuevo Caso
Clasificación por vecindad
Benigna
Maligna
Nuevo Caso
Métodos de Clasificación por Vecindad
• Ventaja asociada a simplicidad conceptual.
– La clasificación de un nuevo elemento se calcula en función de
las clases, conocidas de antemano, de los objetos mas
próximos a el.
• Ante una nueva situación, parece razonable actuar
como se hizo en situaciones anteriores, parecidas o
similares, si en estas se tuvo éxito.
• Necesitamos definir dos conceptos:
– Similitud
– Distancia
Métodos de Clasificación por
Vecindad
• La decisión de clasificar un nuevo caso X en una de las
clases Cl con (l=1,…L), depende de una colección de N
casos previamente clasificados (xi, Cl) con i=1,…N
• Este método puede dar origen a errores, por ejemplo en
aquellos ejemplos cercanos a dos o mas tipos de clases
• Recordar que: No existe clasificador óptimo que resuelva
todos los problemas.
– Sin embargo el error estimado, de forma empírica, para este
método es reducido.
– Es una buena manera de iniciar búsqueda de métodos de
clasificación
Clasificación por vecindad
Benigna
Maligna
Nuevo Caso
• No confundir con Naive
• Bayes.
• En que se diferencian?
• Como se entrena cada
modelo?
Métodos de Clasificación por Vecindad
• Necesitamos definir medidas de distancia / similitud
• Hablamos de función de distancia
• ¿Cuantas medidas de distancia hay?
– Distancia Euclidiana…
– Otras?
• Las más comunes son aplicadas sobre atributos
numéricos.
– Que hacemos con atributos nominales (colores, apreciaciones,
variables boolean si o no, etc.)
Medidas de distancia
Distancia entre dos puntos x e
y de dimensión n
n
• Distancia Euclidiana: recta
que une dos puntos
d ( x, y ) = å i i
( x -
i =1
y ) 2
n
• Distancia de Manhattan: d ( x, y ) = å | xi - yi |
distancia en zig-zag i =1
Medidas de distancia
• Distancia del coseno: si cada æ xT y ö
ejemplo es un vector, se d ( x, y ) = arccosçç ÷
÷
estima el coseno del Angulo è x. y ø
que forman.
• Distancia Mahalanobis: No
asume independencia de los d ( x, y ) = ( x - y )T S -1 ( x - y )
atributos. Utiliza la matriz de
covarianza S, entre muestras
de valores de x e y.
Funciones de distancia
• Las medidas de distancia nos indican cuan similar (ó
cercano) un vector de atributos esta de otro.
• Hay 4 propiedades que estas medidas deben seguir
para todo vector x, y, z Î RD
– No-negatividad: d(x,y) >= 0 --- d(x,y) = 0 si x = y
– Simetría: d(x,y) = d(y,x)
– diferencia triangular: d(x,y) + d(y,z) >= d(x,z)
Posibles problemas con métricas
• Normalizar valores: entre 0 y 1 ó entre -1 y 1
– Como hacen esto? averiguar para futura implementación
• Detección de valores anómalos ó atípicos
– Eliminar ejemplos
• Valores nominales:
– Definir función delta como
d (a, b) = 0 si y solo si a = b
d (a, b) = 1 en caso contrario
n
d ( x, y ) = w å d ( xi , yi )
i =1
Métodos de Clasificación por Vecindad
K=1
• Algoritmo para regla del vecino más próximo (k=1)
– Asignar clase del objeto más cercano al nuevo ejemplo
– Se estima la distancia a cada uno de los datos de entrenamiento
– Se asigna la clase del ejemplo más cercano.
Métodos de Clasificación por Vecindad
• Algoritmo para regla del vecino más próximo (k=1)
• Regla de los k vecinos más próximos
– Usualmente conocida como método kNN
– Similar al anterior pero considerando los k objetos más cercanos
– Asignar por mayoría de votos.
– En caso de empate asignar por ejemplo de manera aleatoria.
– Pesado de casos: el voto está asociado a algún peso. (e.j.
Inversamente proporcional a la distancia.
– Pesado de atributos: tomar en cuenta la información mutua entre
las distintas variables y la clase.
Ejemplo de KNN
Problema de clasificación, 2 clases, con S set de entrenamiento dado por:
• Clase C1: (9 ; 2 ; 1), (6 ; 3 ; 4), (7 ; 2 ; 4)
• Clase C2: (2 ; 3 ; 10), (4 ; 2 ; 9), (1 ; 3 ; 8)
Utilizando el método de clasificación de vecinos cercanos (kNN), clasifique
los siguientes ejemplos considerando k=1 y k=3.
1.- (5; 5 ;5) ; 2.- (7 ; 6 ; 9) y 3.- (2 ; 4 ; 3)
Como medida de distancia utilizar la distancia euclidiana:
Pattern Recognition and
Machine Learning, Bishop 2006
Pattern Recognition and
Machine Learning, Bishop 2006
Métodos de Clasificación por Vecindad
• Algoritmo para regla del vecino más próximo (k=1)
• Regla de los k vecinos más próximos
– Usualmente conocida como método kNN
– Similar al anterior pero considerando los k objetos más cercanos
– Asignar por mayoría de votos.
– En caso de empate asignar por ejemplo de manera aleatoria.
– Pesado de casos: el voto está asociado a algún peso. (e.j.
Inversamente proporcional a la distancia.
– Pesado de atributos: tomar en cuenta la información mutua entre
las distintas variables y la clase.
• Sobreajuste – como se podría observar?
Complejidad Computacional
• No existe un modelo propiamente tal. Si se fijan, el
entrenamiento no es requerido con antelación.
• Todo el esfuerzo computacional ocurre cuando se
clasifican nuevos objetos
• Complejidad es función del computo de distancias a
cada ejemplo disponible.
• Para Distancia Euclidiana, la complejidad depende de
la dimensionalidad del vector de atributos y el numero
de objetos para entrenamiento (DN)
– Problemas con N muy grande.
Otras características
• Métodos de vecinos cercanos son libres de parámetros
• Sin embargo hay 2 hiper-parámetros relacionados con
este método
– Numero de vecinos
– Función de distancia empleada
• Es necesario encontrar el número de vecinos óptimos
para un determinado problema.
– Graficar por ejemplo la eficiencia global (o tasa de falsos
positivos) del modelo en función del número de vecinos “k”
– Esto debe ser implementado en evaluación de este modelo en
taller Nº5