1 Computacion inteligente10/04/2017 Computacion inteligente Introduccion a la Clasificacion ICS 175a, Spring 2005. Padhraic Smyth Department of Computer Science University of California, Irvine

2 Contenido 10/04/2017 Mar 2009 Introduccion Fases y modelosVectores y espacios de caracteristicas Fronteras de decision Separabilidad lineal Clasificadores lineales El clasificador del vecino mas cercano El clasificador de los K vecinos mas proximos Precision de la clasificacion Evaluacion de la clasificacion Mar 2009

3 10/04/2017 Introduccion

4 Que es clasificacion La clasificación es un procedimiento en el cual se agrupan objetos individuales de un conjunto de objetos en clases, basados en la información cuantitativa de una o más características inherentes a los objetos Clasificacion Ejemplo: Medir el tamaño del pie y clasificar su genero de acuerdo a informacion estadistica Mar 2009

5 10/04/2017 Clasificacion Historicamente, los objectos son clasificados en clases o grupos La tabla periodica de los elementos (quimica) taxonomia (zoologia, botanica) ¿Por que clasificar? comprender prediccion conveniencia organizacional, resumen conveniente Resumir Reducir el tamaño de grandes conjuntos de datos Estos objetivos no necesariamente conducen a la misma clasificacion; Ej.TAMAÑO del objecto vs. TIPO/USO de objecto ppt Mar 2009

6 10/04/2017 Clasificacion La clasificacion divide los objectos en grupos basados en un conjunto de una o más características Al contrario de una teoria, una clasificacion no es falsa ni verdadera, y debe ser juzgada mas por la utilidad de sus resultados ppt Sin embargo, una clasificacion puede ser util para sugerir una teoria, la cual puede ser entonces probada Mar 2009

7 ? Clasificacion Clasificacion:10/04/2017 Clasificacion Clasificacion: Una tarea de induccion para hallar patrones en los datos Inferencia de conocimiento a partir de los datos ? Mar 2009

8 Aprendizaje a partir de datos10/04/2017 Aprendizaje a partir de datos Se pueden encontrar diferentes nombres al aprendizaje a partir de datos identificacion estimacion Regresion clasificacion reconocimiento de patrones aproximacion de funciones, ajuste de curvas etc… Mar 2009

9 Composicion de la leche en algunos mamiferos10/04/2017 Ejemplo de unos datos Especie Grasa (%) Proteinas (%) Horse Donkey Mule Camel Llama Zebra Sheep Buffalo Fox Pig Rabbit Rat Deer Reindeer Whale 1.0 1.4 1.8 3.4 3.2 4.8 6.4 7.9 5.9 5.1 13.1 12.6 19.7 20.3 21.2 2.6 1.7 2.0 3.5 3.9 3.0 5.6 7.4 6.6 7.1 12.3 9.2 10.4 11.1 Composicion de la leche en algunos mamiferos Existen patrones? tools_lec11_2005.ppt Mar 2009

10 Clasificacion C toma valores en {c1, c2, ......, cm}10/04/2017 Clasificacion La clasificacion es un componente importante de los sistemas inteligentes Se tiene una variable discreta especial llamada la Clase, C C toma valores en {c1, c2, , cm} Mar 2009

11 Clasificacion El problema es decidir a que clase pertenece un objecto10/04/2017 Clasificacion El problema es decidir a que clase pertenece un objecto Esto es, que valor toma la variable clase Y para un objecto dado Dadas las medidas del objecto, ej., x1, x2, …. Estas medidas se llaman “caracteristicas” Deseamos aprender un mapeo Caracteristicas -> Clase Mar 2009

12 g:  Que es un clasificador = c1 = x3 = x1 = c2 = x2Un clasificador es un mapeo desde un espacio de características (continuo o discreto) X a un conjunto discreto de etiquetas Y g:  = c1 = x3 = x1 = c2 = x2 Mar 2009

13 La funcion de clasificacion10/04/2017 La funcion de clasificacion Notacion Espacio de entrada: X – ( X  Rn ) Dominio de salida: Y clasificacion binaria: C = {-1, 1} clasificacion con m clases: Y = {c1, c2, c3, …, cm} Conjunto de entrenamiento: S Cada clase se describe con un nombre o label Mar 2009

14 La funcion de clasificacion10/04/2017 La funcion de clasificacion Buscamos un mapeo o funcion que: Tome cualquier combinacion de valores x = (a, b, d, .... z) y, produzca una prediccion C, Esto es, una funcion C = f(a, b, d, …. z) que produce un valor c1 o c2, etc El problema es que no conocemos este mapeo: debe ser aprendido a partir de los datos! Mar 2009

15 Funciones de clasificacion10/04/2017 Funciones de clasificacion Valores de las caracteristicas (los cuales son conocidos, medidos) Valor de la clase predicha (la clase verdadera es desconocida para el clasificador) Classifier C a b d z La funcion de clasificacion Mar 2009

16 Clasificacion: Construccion del modelo10/04/2017 Clasificacion: Construccion del modelo Training Data Classification Algorithms IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’ Classifier (Model) Rank = A relative position or degree of value in a graded group. Tenure = The status of holding one's position on a permanent basis without periodic contract renewals: a teacher granted tenure on a faculty. Mar 2009

17 Clasificacion: Prediccion usando el modelo10/04/2017 Clasificacion: Prediccion usando el modelo Classifier Testing Data Unseen Data (Jeff, Professor, 4) Tenured? Mar 2009

18 Aplicaciones de la clasificacion10/04/2017 Aplicaciones de la clasificacion Medical Diagnosis classification of cancerous cells Credit card and Loan approval Most major banks Speech recognition IBM, Dragon Systems, AT&T, Microsoft, etc Optical Character/Handwriting Recognition Post Offices, Banks, Gateway, Motorola, Microsoft, Xerox, etc classification classify as “junk” or “non-junk” Many other applications one of the most successful applications of AI technology Mar 2009

19 Ejemplos de caracteristicas y clases10/04/2017 Ejemplos de caracteristicas y clases Mar 2009

20 Ejemplos de caracteristicas y clases10/04/2017 Ejemplos de caracteristicas y clases Mar 2009

21 Ejemplos de caracteristicas y clases10/04/2017 Ejemplos de caracteristicas y clases Mar 2009

22 Maquina de clasificación de Frutas.Mar 2009

23 Monitoreo de tráfico Mar 2009

24 Ejemplo: Clasificacion de imagenes10/04/2017 Ejemplo: Clasificacion de imagenes Sensado remoto9 Original Image Classified Image Mar 2009

25 10/04/2017 Fases y modelos

26 Fases de la clasificacionNuestro interes Mar 2009

27 Modelos de los clasificadoresNo paramétricos paramétricos Mar 2009

28 El proceso de aprendizaje usado influye en la soluciónAprendizaje: extraccion deprincipios a partir de datos El mapeo o funcion debe ser aprendida: varios métodos disponibles. Aprendizaje supervisado: se tienen ejemplos (teacher) Aprendizaje no supervisado: ningún maestro, el “clasificador” aprende solo El proceso de aprendizaje usado influye en la solución Mar 2009

29 Aprendizaje Ejemplos de algunas tecnicas Clasificacion no supervisada10/04/2017 Aprendizaje Ejemplos de algunas tecnicas Clasificacion no supervisada Clustering Clasificacion supervisada K-vecinos mas proximos Redes neuronales Arboles de decision Clasificadores Bayesianos Maquinas de vectores de soporte (SVM) Y muchas mas ... Mar 2009

30 Aprendizaje supervisado10/04/2017 Aprendizaje supervisado En el aprendizaje supervisado, al clasificador se la da un conjunto de entrenamiento de entradas asociadas valores de salida l : Numero de muestras de entrenamiento x : ejemplos (entradas) y : labels o clases (salidas) Mar 2009

31 Aprendizaje supervisado10/04/2017 Aprendizaje supervisado Un conjunto de entrenamiento S se dice que es trivial si todos los labels son iguales Usualmente ejemplos labels Mar 2009

32 Ejemplo de clasificacion supervisada10/04/2017 Ejemplo de clasificacion supervisada Clasificacion de escritura a mano: Primero se necesita un conjunto de datos para aprender: conjunto de caracteres a b Estos se representan como un vector de entrada x = (x1, …, xn) al clasificador (por ejemplo, un vector de unos y ceros para cada pixel de acuerdo a si es blanco o negro Mar 2009

33 Ejemplo de clasificacion supervisada10/04/2017 Ejemplo de clasificacion supervisada Este conjunto de vectores de entrada es nuestro conjunto de entrenamiento X el cual ya ha sido clasificado en a’s y b’s Dado el conjunto de entrenamiento X, nuestro objetivo es decir si una nueva imagen es una a o una b a b Muchas variaciones de un patrón pueden ser reconocidas como pertenecientes a una misma clase. Mar 2009

34 Modelos de los clasificadoresDependiendo de si se supone o no un conocimiento a priori de la estructura estadística de las clases, la forma de construir el clasificador será radicalmente distinta. Aproximación paramétrica Podemos modelar las clases de nuestro problema mediante funciones de densidad de probabilidad conocidas… Aproximación no paramétrica NO podemos modelar las clases de nuestro problema mediante funciones de densidad de probabilidad conocidas… Mar 2009

35 Modelos parametricos Los datos se reducen parametricamente 10/04/2017Mar 2009

36 Modelos no parametricos10/04/2017 Modelos no parametricos Los datos de entrenamiento se retienen; cada una afecta potencialmente la estimacion de un nuevo punto Mar 2009

37 Vectores y espacios de caracteristicas10/04/2017 Vectores y espacios de caracteristicas

38 Vectores y espacios de caracteristicas10/04/2017 Vectores y espacios de caracteristicas Vector de caracteristicas: Sea que tenemos 2 caracterisiticas: podemos ver las caracteristicas como un vector de 2 componentes (vector bi-dimensional, [a b]) Las caracteristicas corresponden a un espacio bi-dimensional Generalizamos a un espacio d-dimensional. Este es llamado el “espacio de caracteristicas” Mar 2009

39 Vectores y espacios de caracteristicas10/04/2017 Vectores y espacios de caracteristicas Cada vector de caracteristicas representa las “cordenadas” de un objeto particular el el espacio de caracteristicas Si el espacio de caracteristicas es bi-dimensional (por ejemplo), y las caracteristicas a y b son numeros reales Podemos visualmente examinar y graficar la localizacion de los vectores de caracteristicas Mar 2009

40 Ejemplo: Datos con 2 caracteristicas10/04/2017 Ejemplo: Datos con 2 caracteristicas Mar 2009

41 Ejemplo: Datos con 2 caracteristicas10/04/2017 Ejemplo: Datos con 2 caracteristicas Mar 2009

42 Another Example: Red Blood Cells10/04/2017 Another Example: Red Blood Cells Mar 2009

43 Datos con 3 caracteristicas10/04/2017 Datos con 3 caracteristicas Dado un conjunto de bolas Clasificar por “color” Additive RGB color model HSV Color Space (H) es un atributo del color que describe su pureza o matiz (amarillo puro, rojo, naranja, ...), mientras la saturacion (S) proporciona una medida del grado en el que el color puro es diluido con luz blanca. (Hue-Saturation-Value) Mar 2009

44 Datos con multiples clases10/04/2017 Datos con multiples clases Consideremos que tenemos datos de m classes e.g., m=5 Podemos imaginar los datos de cada clase como pertenecientes a una “nube” en el espacion de caracteristicas Mar 2009

45 Ejemplo de datos con 5 Clases10/04/2017 Ejemplo de datos con 5 Clases Composition of mammalian milk Fat (%) Proteins (%) Classes Mar 2009

46 10/04/2017 Fronteras de decision

47 Fronteras de decision ¿Que es a Clasificador?10/04/2017 Fronteras de decision ¿Que es a Clasificador? Un clasificador es un mapeo desde el espacio de caracteristicas a las clases {1, 2, … m} Entonces, un clasificador divide el espacio de caracteristicas en m regiones de decision La linea o superficie que separa 2 clases cualquiera es una superficie de decision Mar 2009

48 Clasificadores lineales10/04/2017 Clasificadores lineales Clasificadores lineales Un clasificador lineal es un mapeo que divide el espacio de caracteristicas usando una funcion lineal Es uno de los clasificadores mas simples que podemos imaginar En 2 dimensiones la frontera de decision es una linea recta Mar 2009

49 Datos de 2 clases con frontera de decision lineal10/04/2017 Datos de 2 clases con frontera de decision lineal Mar 2009

50 Traslape de las clases Consideremos el caso de dos clases10/04/2017 Traslape de las clases Consideremos el caso de dos clases Los datos de C1 y C2 pueden traslaparse caracteristicas = {edad, temperatura}, clases = {gripa, no-gripa} caracteristicas = {sueldo, ahorros}, clases = {riesgo alto/bajo} Mar 2009

51 10/04/2017 Traslape de las clases En la practica las clases se traslapan de manera natural Esto significa que las caracteristicas no son capaces de discriminar perfectamente entre las clases nota: con caracteristicas adicionales mas detalladas/costosas podemos lograr una separacion perfecta (por ejemplo, una prueba especifica para la gripa) Si existe traslape => las clases no son linealmente separables Mar 2009

52 Problema de clasificacion con traslape10/04/2017 Problema de clasificacion con traslape Mar 2009

53 10/04/2017 Mar 2009

54 10/04/2017 Mar 2009

55 10/04/2017 Mar 2009

56 Solucion: Una frontera de decision mas compleja10/04/2017 Solucion: Una frontera de decision mas compleja 2 3 4 5 6 7 8 9 10 -1 1 Feature 1 Feature 2 TWO-CLASS DATA IN A TWO-DIMENSIONAL FEATURE SPACE Decision Region 2 Region 1 Boundary Mar 2009

57 10/04/2017 Separabilidad lineal

58 10/04/2017 Linear separability Mar 2009

59 Convex Hull of a Set of Points10/04/2017 Convex Hull of a Set of Points Convex Hull of a set of Q points: Intuitively think of each point in Q as a nail sticking out from a 2d board the convex hull = the shape formed by a tight rubber band that surrounds all the nails Formally: “the convex hull is the smallest convex polygon P for which each point in Q is either on the boundary of P or in its interior” can be found (for n points) in time n log n Mar 2009

60 Convex Hull: Relation to Class Overlap10/04/2017 Convex Hull: Relation to Class Overlap Define convex hulls of data points D1 and D2 as P1 and P2 if P1 and P2 intersect, then we have overlap If P1 and P2 intersect then D1 and D2 are not linearly separable Mar 2009

61 10/04/2017 Convex Hull Example Feature 1 Feature 2 Mar 2009

62 Convex Hull Example Convex Hull P1 Feature 2 Feature 1 10/04/2017Mar 2009

63 Data from 2 Classes: Linearly Separable?10/04/2017 Data from 2 Classes: Linearly Separable? Feature 1 Feature 2 x Mar 2009

64 Data from 2 Classes: Linearly Separable?10/04/2017 Data from 2 Classes: Linearly Separable? Feature 1 Feature 2 Convex Hull P1 x Mar 2009

65 Data from 2 Classes: Linearly Separable?10/04/2017 Data from 2 Classes: Linearly Separable? Feature 1 Feature 2 Convex Hull P1 x Convex Hull P2 The 2 Hulls intersect => data from each class are not linearly separable Mar 2009

66 Different data => linearly separable10/04/2017 Different data => linearly separable Feature 1 Feature 2 Convex Hull P1 x Convex Hull P2 Mar 2009

67 Some Theory Let N be the number of data points10/04/2017 Some Theory Let N be the number of data points Let d be the dimension of the data points Consider N points in general position and assume each point is labeled as belonging to class 1 or class 2 There are 2N possible dichotomies Mar 2009

68 10/04/2017 Some Theory Let F(N, d) = the fraction of dichotomies of N points in d dimensions that are linearly separable It can be shown that: Mar 2009

69 Fraction of Labellings in d-space that are Linearly Separable10/04/2017 Fraction of Labellings in d-space that are Linearly Separable N/(d+1) 1 2 3 0.5 d = infinity d = 1 d = 10 F(N,d) = fraction that are linearly separable Mar 2009

70 Fraction of Labellings in d-space that are Linearly Separable10/04/2017 Fraction of Labellings in d-space that are Linearly Separable N/(d+1) 1 2 3 0.5 F(N,d) = fraction that are linearly separable Note that for N <= d+1, any labeling of N points in d-dimensions is linearly separable (e.g., N=3, d = 2 or N=50, d=100) Mar 2009

71 Clasificadores lineales10/04/2017 Clasificadores lineales

72 10/04/2017 Separabilidad lineal Mar 2009

73 Un clasificador lineal en 2 dimensiones10/04/2017 Un clasificador lineal en 2 dimensiones Denominemos x1 a la caracteristica 1 y x2 a la caracteristica 2 Un clasificador lineal es una funcion lineal de x1 y x2, es decir, calcula: Mar 2009

74 Un clasificador lineal en 2 dimensiones10/04/2017 Un clasificador lineal en 2 dimensiones Se define la salida del clasificador lineal como si f(x1,x2) <= 0, el clasificador produce un “-1” (Region de decision 1) si f(x1,x2) > 0, el clasificador produce un “+1” (Region de decision 2) Mar 2009

75 Frontera de decision para el clasificador lineal 2D10/04/2017 Frontera de decision para el clasificador lineal 2D Dependiendo si f(x1,x2) es > o < 0, las caracteristicas (x1,x2) se clasifican en la clase 1 o en la clase 2 Por lo tanto, f(x1,x2) = 0 define la frontera de decision entre la clase 1 y la clase 2 Mar 2009

76 Frontera de decision para el clasificador lineal 2D10/04/2017 Frontera de decision para el clasificador lineal 2D Cual es la ecuacion para esta frontera de decision? Por lo tanto, definiendo w1, w2, y b automaticamente se localiza la frontera de decision en el espacio X Mar 2009

77 Frontera de decision para el clasificador lineal 2D10/04/2017 Frontera de decision para el clasificador lineal 2D Regla de clasificacion: Si predecir la class 1 else predecir la clase 2 En forma vectorial: Mar 2009

78 Frontera de decision para el clasificador lineal10/04/2017 Frontera de decision para el clasificador lineal En resumen: Un clasificador define una frontera de decision entre las clases Para un clasificador lineal, esta frontera es una linea o un (hiper)-plano La ecuacion del plano esta definida por los parametros del clasificador Mar 2009

79 Clasificacion binaria n-dimensional10/04/2017 Clasificacion binaria n-dimensional Clasificacion binaria Entrada x = (x1, x2, …, xn)’ Si f(x1,x2) <= 0, el clasificador produce “-1” (Region de decision 1) Si f(x1,x2) > 0, el clasificador produce “+1” (Region de decision 2) Superficie de decision Mar 2009

80 Relaciones de frontera10/04/2017 Relaciones de frontera q Superficie de decision S Mar 2009

81 Relaciones de frontera10/04/2017 Relaciones de frontera q Superficie de decision S Mar 2009

82 Clasificacion binaria10/04/2017 Clasificacion binaria hiperplano Un hiperplano de separacion (w,b) Є RnxR para un conjunto de entrenamiento 2D Mar 2009

83 Clasificacion binaria10/04/2017 Clasificacion binaria w define una direccion perpendicular al hiperplano hiperplano Un hiperplano de separacion (w,b) Є RnxR para un conjunto de entrenamiento 2D Mar 2009

84 Clasificacion binaria10/04/2017 Clasificacion binaria w define una direccion perpendicular al hiperplano hyperplane b mueve al hiperplano paralelo a si mismo (el numero de parametros libres es n+1) Mar 2009

85 Distancia perpendicular de xi10/04/2017 Distancia perpendicular de xi Mar 2009

86 Clasificacion binaria10/04/2017 Clasificacion binaria Probar! Mar 2009

87 Clasificacion binaria10/04/2017 Clasificacion binaria Margen funcional  > 0 implica una clasificacion correcta Mar 2009

88 Clasificacion binaria10/04/2017 Clasificacion binaria El margen geometrico es la distancia Euclidea de la perpendicular del punto al hiperplano El margen geometrico sera igual al margen funcional si w es un vector unitario Mar 2009

89 Clasificacion binaria10/04/2017 Clasificacion binaria El margen de S es el valor de  mas pqueño en S con respecto al hiperplano (w, b) Objetivo: Tratar de encontrar el hiperplano (wopt, bopt) donde el margen es el mas grande Mar 2009

90 Clasificacion binaria10/04/2017 Clasificacion binaria Mar 2009