Date post: | 21-Jan-2015 |
Category: |
Documents |
Upload: | martin-alatorre |
View: | 15 times |
Download: | 3 times |
K-NN: K vecinos más cercanos
MSc. Carlos Alberto Cobos Lozada
http://www.unicauca.edu.co/~ccobos
Grupo de I+D en Tecnologías de la Información
Departamento de Sistemas
Facultad de Ingeniería Electrónica y Telecomunicaciones
Universidad del Cauca
Resumen Previo
Enfoque estadístico para estimación y predicción
Métodos univariable
Métodos multivariable – Regresión Lineal Multivariable
Determinar la confianza de las estimaciones
Intervalos de predicción
Verificar los supuestos del modelo
Métodos supervisado vs. no supervisado Métodos no supervisados:
No hay variable objetivo Algoritmos buscan patrones. Por ejemplo: Clustering
Métodos supervisados Mayoría de métodos de minería de datos Variable objetivo pre clasificada Proceso de aprendizaje Por ejemplo: Árboles de decisión, redes neuronales y los k-
vecinos más cercanos. Mixtos (supervisados y no supervisados)
Reglas de Asociación ¿Cuáles ítems se compran juntos? – No supervisado Con cierta confianza y soporte ¿Cuáles ítems se compran juntos? -
Supervisado (apriori)
Metodología para modelos supervisados
Conjunto de entrenamiento
Generar el modelo de minería de datos
provisional
Aplicar el modelo provisional al conjunto
de prueba.Ajustar el modelo para
minimizar la rata de error en el conjunto de
prueba
Aplicar el modelo ajustado al conjunto de
validación. Ajustar el modelo para minimizar la rata de error en el
conjunto de validación
Modelo de minería
provisional
Conjunto de Prueba
Conjunto de Validación
Modelo de minería ajustado
Modelo de minería final
Adaptado de [1] para uso educativo
Nivel óptimo de complejidad
Sobre ajusteBajo ajuste
Tomado de [1] para uso educativo
Complejidad vs. Error
Alta complejidadAlta varianzaBajo sesgo (error)
Baja complejidad Baja varianzaAlto sesgo (error)
x
x
xx
x
x
x
Conocido como Bias-variance trade-offDilema de sobre/bajo ajusteUn modelo más complejo disminuye el sesgo (bias) en el conjunto de entrenamiento pero incrementa la varianza (dispersión de la variables con respecto a su esperanza)
Tomado de [1] para uso educativo
Pilas con la idiosincrasia de los datos
Complejidad vs. Error
El Error Cuadrado Medio (Mean-squared error, MSE) es una buena medida para evaluar dos modelos que compiten (debe minimizarse)
MSE contempla el sesgo y la varianza
P es el número de parámetros del modelo, en regresión lineal simple p=1 (y=m*x+b entonces y depende de 1 solo parámetro, x en este caso)
Tomado de [1] para uso educativo
Tareas de clasificación
Hay una variable categórica objetivo. Ejemplos de tareas de clasificación
Banca: Transacciones fraudulentas y riesgo crediticio Educación: Orden de cursos a tomar por un nuevo
estudiante Medicina: Diagnosticar si una enfermedad esta
presente Leyes: Determinar si un testamento es fraudulento Seguridad Nacional: Comportamiento financiero que
señale una amenaza de terrorismo
Tareas de clasificación
Tomado de [1] para uso educativo
Comprensión del negocio
Análisis de los datos
Preparación de los datos
ModelamientoEvaluación
Despliegue Datos
Algoritmo de los k vecinos más cercanos El más usado para
clasificación También es usado para
estimaciones y predicciones
Aprendizaje basado en instancias
Examina K tuplas cercanas a la tupla que se va a clasificar
O(n) para cada tupla a clasificar (n es el numero de tuplas en el data set de entrenamiento)
Algoritmo de los k vecinos más cercanos
Tomado de [2] para uso educativo
Algoritmo de los k vecinos más cercanos
Tomado de [1] para uso educativo
Algoritmo de los k vecinos más cercanos
New patient 1 tiene cerca drogas Y
NP1
Algoritmo de los k vecinos más cercanos
Tomado de [1] para uso educativo
New patient 2 con k=1 droga BCon k=2 droga B o A?
NP2
Algoritmo de los k vecinos más cercanos
Tomado de [1] para uso educativo
New patient 3 con k=1 droga BCon k=2 droga B o A?
Con k=3 droga B o A o X?
NP3
Problemas de los k vecinos más cercanos ¿Cuántos vecinos considerar? ¿Valor de k? ¿Cómo medir la distancia? ¿Cómo combinar la información de más de
una observación? ¿El peso de los vecinos debe ser igual?
¿algunos vecinos deben tener mayor influencia que otros?
Función de Distancia
Debe cumplir tres reglas (distancia o similitud) 1. d (x, y) >= 0, y d (x, y) = 0 si y sólo si x = y
(No ser negativa) 2. d (x, y) = d (y, x) (Conmutativa) 3. d (x, z) <= d (x, y) + d (y, z) (desigualdad
triangular)
Distancia Euclidiana
Tomado de [1] para uso educativo
2)(),(
iiiEuclidiana yxyxd
Función de Distancia
Distancia Euclidiana
Importantísimo Normalización Min-Max o Estandarización Z-score
Tomado de [1] para uso educativo
Función de Distancia
Para variables categóricas la Distancia Euclidiana no aplica. Para ello definimos una función “Diferente de” para comparar el i-ésimo atributo
Tomado de [1] para uso educativo
Función Combinación
Tomado de [1] para uso educativo
NP2
Función Combinación Simple
Tomado de [1] para uso educativo
NP2
Función Combinación Simple
Con K= 1 gana Droga del punto A Con K= 2 empate como decido? Con K= 3 gana Droga de puntos B y C
Tomado de [1] para uso educativo
Función Combinación Ponderada
Tomado de [1] para uso educativo
NP2
Función Combinación Ponderada Los votos son pesados de acuerdo al cuadrado inverso
de sus distancias
Para los registros B y C, Gris medio:
Con K= 3 gana Droga A (contrario a función de combinación simple)
Tomado de [1] para uso educativo
Validación Cruzada
Cross-Validation: Holdout validation: Separar el Training Set en
Validation y Traininng, normalmente hasta una tercera parte … realmente no es validación cruzada
K-fold cross-validation: Realizar k particiones del DataSet, tomar k-1 de ellas como Training Set y la otra (k) como Validation Set, y repetir el proceso rotando la partición que se toma como Validation Set
Leave-one-out cross-validation: Igual al anterior pero tomando cada fila como Validation set
Para K-nn la validación cruzada puede ayudar a encontrar el mejor valor de K.
Resumen
Aprendizaje supervisado y no supervisado Nivel optimo de complejidad (under fitting y over fitting) K-nn muy usado para clasificación, estimación y
predicción – Algoritmo basado en instancias – Lazy (perezoso)
Normalización y/o Estandarización de los datos, inicialmente igual peso, dependiendo de la aplicación o un experto los pesos se pueden cambiar
La medida de distancia es clave: distancias numéricas y categóricas
Función de combinación de k valores (Votación simple o ponderada)
Modelado con Validación cruzada (Cross-Validation: Holdout validation, K-fold cross-validation, Leave-one-out cross-validation)
Taller
Usar IBK (K-nn) de Weka para el data set de drogas y entender todos los parámetros y resultados entregados
Implementar K-nn en VS.NET o java y probarlo con un data set de la UCI Machine Learning Repository
Referencias
1. Discovering knowledge in Data: An Introduction to Data Mining. Daniel T. Larose. John Wiley & Sons, Inc. 2005. ISBN 0-471-66657-2
2. Dunham, Margaret H. Data Mining: Introductory and Advanced Topics. Prentice Hall, 2003. 315 p. ISBN-10: 0130888923, ISBN-13: 9780130888921. Slides available on http://lyle.smu.edu/~mhd/book.
3. Análisis y Extracción de Conocimiento en Sistemas de Información: Datawarehouse y Datamining. Departamento de Sistemas Informáticos y Computación. Universidad Politécnica de Valencia. http://www.dsic.upv.es/~jorallo/cursoDWDM.