PDF de programación - Aprendizaje Inductivo - Clasificación y Clustering

Agenda
 Aprendizaje Inductivo

 Concepto

 Clasificación

 Árboles de Decisión
 Clasificador Bayesiano

 Clustering
 K-means
 Clustering jerárquico

Descubrimiento de conocimiento a Partir de Datos

D r . M a r c e l o G . A r m e n t a n o
D r . M a r c e l o G .
A r m e n t a n o

I S I S T A N , F a c . d e C s . E x a c t a s , U N I C E N
I S I S T A N , F a c . d e C s . E x a c t a s , U N I C E N

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Inducción vs. Deducción
 Argumento deductivo

 A ninguno de los alumnos le gusta matemáticas. Juan es

un alumno  a Juan no le gusta matemáticas

 Argumento inductivo

 A ninguno de los alumnos que fueron entrevistados les

gusta matemáticas a ningún alumno le gusta
matemáticas

Aprendizaje por inducción
 La descripción de un concepto, o clasificador, se

induce a partir de un conjunto de instancias dadas del
concepto (ejemplos)

 No puede garantizarse correctitud
 Es importante la interpretación humana

Jerarquía de aprendizaje

Aprendizaje
Inductivo

Aprendizaje
Supervisado

Aprendizaje no

supervisado

Clasificación

Regresión

Clustering

11

Agenda
 Aprendizaje Inductivo

 Concepto

 Clasificación

 Árboles de Decisión
 Clasificador Bayesiano

 Clustering

Clasificación
 El objetivo de la clasificación de datos es organizar y

categorizar los datos en clases diferentes
 Se crea un modelo basándose en la distribución de los datos
 El modelo es luego usado para clasificar nuevos datos
 Dado el modelo, se puede predecir la clase de un nuevo
dato

 Si se deduce un valor discreto  Clasificación
 Si se deduce un valor continuo  Regresión

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Preparación de los datos
 Transformación de datos

 Discretización de datos continuos
 Normalización a [-1..1] o [0..1]
 Generalización

 Limpieza de datos

 Suavizado para reducir el ruido y completar valores faltantes

 Análisis de relevancia (Feature Selection)

 Selección de características para eliminar atributos redundantes e

irrelevantes

Aplicaciones
 Aprobación de créditos
 Diagnóstico médico
 Identificación de partes defectuosas en

manufactura

 Detección de SPAM
 Etiquetado de emails
 Clasificación de documentos
 Clasificación de usuarios
 ...

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Proceso de clasificación

Terminología

Datos de

Entrenamiento

Derivar

Clasificador

(Modelo)

Datos

Datos de
Prueba

Estimar
Exactitud

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

22

Terminología
 Cada tupla se supone que pertenece a una clase
llamada

predefinida, dada por uno de los atributos,
etiqueta de clase

 El conjunto de todas las tuplas usadas para la construcción

del modelo se llama conjunto de entrenamiento

 El modelo se representa mediante alguna técnica. Por

ejemplo:
 Reglas de clasificación (sentencias IF-THEN)
 Árbol de decisión
 Fórmulas matemáticas

Aprendizaje

Datos de

Entrenamiento

Algoritmos de
Clasificación

Clasificador
(Modelo)

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Evaluación del modelo
 Se estima la exactitud del modelo basándose en un

conjunto de prueba
 Se compara la etiqueta conocida de una muestra de

prueba con el resultado de aplicar el modelo de
clasificación

 Accuracy rate (precisión) es el porcentaje de muestras
del conjunto de test que son correctamente clasificadas
por el modelo

 El conjunto de test es independiente del conjunto de

entrenamiento (método holdout)

Evaluación de Exactitud

Datos de

Entrenamiento

Clasificador
(Modelo)

¿Qué tan preciso es el modelo?

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Evaluación del modelo
 Holdout

 Los datos se particionan aleatoriamente en 2 conjuntos independientes:

training set (2/3 de los datos) y test set (1/3 de los datos)

 Random subsampling

 Holdout k veces

 K-fold cross validation

 Datos iniciales particionados en k subconjuntos mutuamente excluyentes

de aproximadamente igual tamaño. Se hace training y testing k veces, se
calcula la exactitud promediando los resultados.

 Stratisfied cross-validation

 Los subconjuntos son armados de tal manera que la distribución de clase de

los ejemplos en cada uno es aproximadamente igual a la que tienen los
datos iniciales

Evaluación del modelo
 Tasa de Error

error

h
)(

=

 Precisión

n

i

i∑ =
y
n

1

≠

xh
i

(

)

precisión

1)(
h

−=

error

)(
h

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

33

Matriz de Confusión

Etiqueta
de clase
Verdaderos
C1
Verdaderos
C2
...

Verdaderos
Ck

Predicciones C1 Predicciones C2

... Predicciones Ck

M(C1,C1)

M(C1,C2)

... M(C1,Ck)

M(C2,C1)

M(C2,C2)

... M(C2,Ck)

...

...

...

...

M(Ck,C1)

M(Ck,C2)

... M(Ck,Ck)

CCM

(

,

i

)

=

j

∑

=

C

j

)(
xh
=
}

:

∀
,({

iCyTyx

∈
)

Clasificador ideal
 M(Ci, Ci) Casos correctamente clasificados
 M(Ci, Cj) i≠j Errores de clasificación

C1

C1 M(C1,C1)

C2
0

C2

...

Ck

0

...

0

M(C2,C2)

...

0

...
...

...

...

...

Ck
0

0

0

M(Ck,Ck)

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Evaluación del Modelo (Documentos)
 Precisión

 De la cantidad de veces que se predijo una clase, cuántas

fueron correctas?

 Recall

 Se encontraron todos los ejemplos que pertenecen a la

clase?

Precisión y recall

Clase real

Predicción

Verdaderos positivos (vp)
Falsos negativos (fn)

Falsos positivos (fp)
Verdaderos negativos
(vn)

precisión

=

vp
+

vp

fp

recall

=

vp
+

vp

fn

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Uso del modelo - Clasificación
 El modelo se utiliza para clasificar nuevos objetos

 Dar una etiqueta de clase a una nueva tupla
 Predecir el valor de un atributo

Nuevos
Datos

Clasificador
(Modelo)

Mejorar la precisión: Clasificadores
compuestos
• Bagging: ej. consulto varios doctores y me quedo con la

opinión mayoritaria (la que tenga más votos)

• Boosting: ej. pondero cada diagnóstico según la exactitud

del médico (del clasificador)

Datos

Clasificador 1
Clasificador 1

Clasificador 2
Clasificador 2

……

Clasificador n
Clasificador n

Combinar
predicciones

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

44

Métodos de clasificación
 Árboles de decisión
 Redes Neuronales
 Clasificador Bayesiano
 Clasificación basada en asociación
 Vecino más cercano
 Razonamiento Basado en Casos
 Algoritmos Genéticos
 Modelos de Markov
 ...

Evaluación y comparación de
métodos de clasificación
 Exactitud de predicción

 Habilidad del modelo de predecir correctamente la etiqueta de clase

de nuevos ejemplos

 Velocidad

 Tiempo para construir el modelo
 Tiempo para usar el modelo

 Robustez

 Manejo de valores faltantes y ruido

 Escalabilidad

 Eficiencia en grandes bases de datos

 Facilidad de interpretación

 Nivel de entendimiento provisto por el modelo

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Agenda
 Aprendizaje Inductivo
 Clasificación

 Árboles de Decisión
 Clasificador Bayesiano

 Clustering

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Árboles de Decisión
 Un árbol de decisión es una estructura de datos

definida recursivamente como:
 Un nodo hoja que contiene una clase
 Un nodo de decisión que contiene una comprobación

sobre algún atributo. Para cada resultado de esa
comprobación existe un subárbol hijo, con la misma
estructura descripta.

Ejemplo

El paciente
se siente bien

Si

Sano

No

El paciente
tiene dolor

No

Si

Temperatura
del paciente

Enfermo

<=37

Sano

>37

Enfermo

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

55

Ejemplo: Datos de entrenamiento

Ejemplo árbol de decisión

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Utilización del árbol
 Directamente

 Verificar el valor de un atributo de un ejemplo no

conocido con el árbol

 Se sigue el camino desde la raíz a la hoja que posea la

etiqueta

 Indirectamente

 El árbol de decisión se convierte en reglas de

clasificación

 Se crea una regla por cada camino de la raíz a las hojas
 Las reglas IF-THEN son más fáciles de entender

Clasificación de nuevos ejemplos
 Partir desde la raíz
 Avanzar por los nodos de decisión hasta alcanzar una hoja
 La clase del nuevo ejemplo es la clase que representa la

hoja.

Clase

Asociada

Nuevo Ejemplo

Atributo1=..
Atributo2=..

Clase = A

B

A

A

C

B

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

Equivalente en reglas
 Si El paciente se siente bien = Si entonces

 Clase = Sano

 Sino

 Si El paciente tiene dolor = No entonces

 Si Temperatura del paciente <= 37 entonces

 Clase = Sano

 Sino (Temperatura del paciente > 37)

El paciente
se siente bien

 Clase = Enfermo

 Sino (El paciente tiene dolor = Si)

 Clase = Enfermo

Si

Sano

No

El paciente
tiene dolor

No

Temperatura
del paciente

Si

Enfermo

<=37

Sano

>37

Enfermo

Equivalente en reglas
 Si El paciente se siente bien = Si entonces

 Clase = Sano

 Si El paciente se siente bien = No and El paciente tiene

dolor = No and Temperatura del paciente <=37 entonces
 Clase = Sano

 Si El paciente se siente bien = No and El paciente tiene
dolor = No and Temperatura del paciente >37 entonces
 Clase = Enfermo

 Si El paciente se siente bien = No and El paciente tiene

dolor = Si entonces
 Clase = Enfermo

Dr. Marcelo G. Armentano - ISISTAN - UNICEN

66

Construcción del árbol de decisión

Construcción del árbol de decisión



La generación de árbol básica de arr