Modelado – Árbol de Decisión
Mg. Samuel Oporto Díaz
[email protected]
Mapa del Curso
Inteligencia
de Negocios
Metodología
Kimball
Planeamiento
del Proyecto
Modelo
del
Negocio
Modelado
Dimensional
Modelado
Físico
ETL
Reportes
Minería de
Datos
Tabla de Contenido
• Inducción.
• Aprendizaje Automático.
• Clasificación
• Procedimiento de Trabajo.
• Información, entropía y energía
• Árboles de decisión
– Construcción del árbol
– Condición de parada
– Poda del árbol
INDUCCIÓN
Inducción
• La inducción permite obtener la escencia de
los objetos que nos rodean, la escencia es
lo que define el objeto.
• La observación de la realidad proporciona
un conjunto de relaciones.
• La inducción busca la generalización de los
conceptos dados por estas relaciones.
• Va de lo particular a lo general.
Razonamiento Inductivo
• El razonamiento inductivo permite obtener conclusiones
generales a partir de premisas de datos particulares.
• Se obtienen conclusiones probables, más no absolutas.
Ejercicio 1
• Cuál es el siguiente número de la secuencia:
Ejercicio 2
• Sea la siguiente secuencia de números:
10, 7, 9, 6, 8, 5, 7, . . .
• Diga cuales son los siguientes tres números de la serie.
• Resolver por inducción.
Ejercicio 2
• Observando la forma en que los números cambian de
término a término.
• El primer término de la secuencia es 10. Le restas 3 para
obtener el 2o término. Después le sumas 2 para obtener el
3er término. Continúas alternando entre restar 3 y sumar 2
para generar los términos restantes.
• Los siguientes tres términos son:
Inducción
• Formalmente la observación de la realidad se configura
como un conjunto de pares, que definen una relación.
[x, f(x)]
• Este par se denomina un par de entrenamiento (x, f(x)),
donde x es la entrada y f(x) es la salida de la función
aplicada a x.
Inducción
• La inducción es un proceso mediante el cual, dado un
conjunto de ejemplos del par (x, f(x), se intenta encontrar
una hipótesis que se aproxime a f.
• Se entiende que una hipótesis es una función que se debe
validar mediante alguna prueba.
• La preferencia por alguna hipótesis es un desvio (bias).
• Todos los algoritmos tienen un grado de desvío dado que e
hay un gran número de hipótesis consistentes posibles.
• El aprendizaje se logrará cuando se encuentre la función f
que mejor explique los datos
Inducción
• El proceso de aprendizaje es un compromiso entre:
¿la función deseada es
representable en el lenguaje
de representación usado?
Inducción
¿será el problema de
aprendizaje tratable para
una elección dada del
lenguaje de representación?
Ejercicio 3
• Para el ejercicio 1 encuentre una fórmula para expresar el
número de la posición i ?. xi = g(i)
• En caso que no se pueda exprese la función
recursivamente: xi = h(xi-1).
Ejercicio 4
• En la clase de física, el grupo de Rumi soltó una pelota
desde diferentes alturas, se midió la altura del primer
rebote y se registraron los siguientes datos:
• Se pide:
– Preparar al menos dos hipótesis (conjeturas) acerca de
estos hallazgos.
– Aplicar una prueba para determinar cuál de las dos
hipótesis es mejor.
– Calcular la altura del primer rebote para una caída de
280 cm.
Ejercicio 4
• Preparando el gráfico de dispersión de los datos y
calculando el R2.
Primer Rebote
Altura Vs Primer Rebote
160
140
120
100
80
60
40
20
0
152
122
90
59
74
y = 0.7555x
R² = 0.9993
30
0
50
100
Altura
150
200
250
• Se observa comportamiento línea de los datos: R = f(A)
Ejercicio 4
• Se necesita plantear algunas hipótesis para f, asumiendo
que el comportamiento es lineal.
f1:
f2:
f3:
k1 = R/A
k2 = (A - R) / A
k3 = (A - R) / R
R = A*k1
R = A*(1-k2)
R = A*(1+k3)
• Intentando probar las hipótesis analíticamente:
A
120
100
160
40
200
80
R
90
74
122
30
152
59
A-R
30
26
38
10
48
21
STD =
(A-R)/A
25.00%
26.00%
23.75%
25.00%
24.00%
26.25%
1.01%
(A-R)/R
33.33%
35.14%
31.15%
33.33%
31.58%
35.59%
1.80%
R/A
75.00%
74.00%
76.25%
75.00%
76.00%
73.75%
1.01%
APRENDIZAJE
AUTOMÁTICO
Aprendizaje Automático
• El aprendizaje automático es una disciplina de la
Inteligencia Artificial que pretende desarrollar algoritmos
para que aprendan desde la experiencia, mediante un
proceso de inducción.
• Intenta crear algoritmos capaces de generalizar
comportamientos a partir de una información no
estructurada suministrada en forma de ejemplos.
• Los ejemplos (la experiencia) se presenta como n-tuplas.
• Es un proceso de inducción del conocimiento.
Aprendizaje Automático
• Se solapa con la estadística, ya que
se basan en el análisis de datos.
• Se centra en el estudio de la
Complejidad Computacional de los
problemas
• Muchos problemas de aprendizaje
son intratables (NP-completo), por lo
que el esfuerzo se centra en el
diseño de soluciones factibles.
La
complejidad
computacional
es
un
indicador
del
tiempo
necesario para que un
algoritmo
entregue
una
respuesta.
Problema Indecible.
No solucionables en forma
algorítmica,
se
pueden
describir, pero no se pueden
representar o resolver.
Problemas Decibles:
Problemas intratables:
Tiempo no polinómico O(kn)
Problemas tratables.
Tiempo polinómicos O(nk)
Tipos de Algoritmos de Aprendizaje
Aprendizaje Supervisado
• Establece una correspondencia entre la entrada y la salida
deseada (Clasificación, Regresión) [x, f(x)]
Aprendizaje No-supervisado
• Todo el proceso de modelado se realiza sobre un conjunto
de ejemplos donde se tiene solo las entradas [x]
Aprendizaje por refuerzo
• El algoritmo re-aprende constantemente, en función a sus
experiencias, refuerza el aprendizaje si tiene éxito
(Feedback) [x, f(x)]
Modelos de Aprendizaje
Supervisado
Una
especie
de
profesor sugiere una
categoría para cada
conjunto
de
entrenamiento.
Se
busca reducir el error
de entrenamiento.
No Supervisado
No existe el profesor,
el sistema realiza
agrupamientos
en
forma natural sobre
los
patrones
de
entrada,
para
determinar la clase a
la que pertenece.
Modelos de
Aprendizaje
CLASIFICACIÓN
Clasificación
• Intenta clasificar algunos objetos en un
número finito de clases, en función a sus
propiedades (características)
• Se intenta buscar un función de mapeo que
permita separar la clase 1 de la clase 2 y esta
de la clase 3…
• Las variables (atributos)
categóricas o numéricas.
pueden
• Árboles de
decisión.
• Redes
Neuronales.
ser
• El modelo se construye con datos completos,
cada registro tiene una clase predefinida.
• Busca formas de separar la data en clases
pre-definidas
• Clasificador
Bayesiano.
• Razonamiento
basado en
casos
Clasificación
• Atraer los clientes mas rentables.
% ingresos
Clasificar a los clientes según la respuesta que se obtiene ente una campaña de mailing
Mail a 30% de los
clientes para recibir el
60% de los ingresos
Gráfico de elevación:
% clientes
Regresión
• Intenta determinar la función que mapea un
conjunto de variables de entrada X
(independiente), en una (o más) variables de
salida Y (dependiente), .
• Es básicamente numérica.
• Está basada en supuestos estadísticos.
• Árboles de
decisión.
• Redes
Neuronales.
• Regresión
Logística
Regresión
Valor de reclamo
• Detectar efectivamente fraudes en el uso de servicios.
Valor de reclamo predecido
Clasificación Vs. Predicción
Clasificación:
• Intenta predecir
categóricas.
las
etiquetas
de
clases
• Los datos se dividen en atributos y en una clase
la que se pretende clasificar (categórica).
• Se clasifica los datos (construye un modelo)
basado en un conjunto de entrenamiento y la
clase a la que pertenece cada ocurrencia.
Pronóstico:
• Intenta predecir funciones continuas.
• La entrada puede tener atributos continuos o
categóricos.
PROCEDIMIENTO DE
TRABAJO
Procedimiento de solución
Definir la
arquitectura
Train
Recolección de
datos
Preprocesamiento
Parámetros
Inducción
Entrenamiento
Reglas
Test
Prueba
error
Procedimiento de solución
Recolección de datos:
• Recolectar los datos tanto de entrada como de salida en el
número de muestras suficientes.
Pre-procesamiento:
• Preparar los datos, para el proceso de aprendizaje
(inductivo)
Definir la arquitectura
• Definir el número de nivéles del árbol, el mínimo de
ocurrencias por hoja, el error máximo de entrenamiento.
Procedimiento de solución
Entrenamiento:
• El conjunto de tuplas es el conjunto de entrenamiento.
• Cada ocurrencia (tupla) pertenece a una clase.
• El modelo es representado como reglas de clasificación,
árboles de decisión, o fórmulas matemáticas.
Uso de modelo:
• Para clasificar nuevos casos
• Estimando la exactitud del modelo.
• La etiqueta conocida del conjunto de entrenamiento es
comparada con el resultado del clasificador
• La tasa de exactitud es el % correctamente clasificadas.
• Los datos de prueba independientes de los datos de
entrenamiento.
Construcción de modelo
Data de
Entrenamiento
NombreRango
Años Contratado
Mike Assistant Prof
3
no
Mary Assistant Prof
7
yes
Bill
Professor
2
yes
Jim
Associate Prof
7
yes
Dave Assistant Prof
6
no
Anne Associate Prof
3
no
Algoritmo de
Clasificación
Clasificador
(Model)
SI rango = ‘professor‘
o años > 6
entonces contratado = ‘yes‘
Uso del modelo
Classificador
Data de
Prueba
Datos
no usados
(Godofredo, profesor, 4)
NombreRango
Años Contratado
Tom
Assistant Prof
2
no
Merlisa Associate Prof
7
no
George Professor
5
yes
Joseph Assistant Prof
7
yes
¿Contratado?
INFORMACIÓN, ENTROPÍA
Y ENERGÍA
Información
• La información se mide en bits.
• Un bit de información es suficiente para
responder Verdadero/Falso a una
pregunta cuya respuesta no se sabe
(basado en la teoría de Shanon).
• La cantidad de información recibida
respecto a la ocurrencia de un evento es
inversamente
proporcional
a
la
probabilidad de ocurrencia de dicho
evento.
– Alta probabilidad  Mínima información
– Baja probabilidad  Máxima información
Entropía
• La entropía mide el grado de
incertidumbre
asociado
a
una
distribución de probabilidad.
• La entropía es la inversa de la cantidad
de información.
• Se basa en la medida de la cantidad de
información que da el atributo (basado
en la teoría de Shanon).
Entropía
• Para calcular la entropía de una variable se usa la
siguiente fórmula.
• Donde S es un conjunto que se puede dividir en |C| clases,
pi es la proporción de ocurrencias de la clase Ci en el
conjunto S.
Ejercicio 10
• Calcular la entropía para las siguientes variables discretas.
2
2
E(1/2, 1/2) = 1.0000
4
2
E(1/3, 2/3) = 0.9183
8
E(1/5, 4/5) = 0.7219
2
16
E(1/9, 8/9) = 0.5033
2
Ejercicio 11
• Calcular la entropía para las siguientes variables discretas.
2
2
2
E(1/3, 1/3, 1/3) =
1.5850
E(1/7, 2/7, 4/7) =
1.3788
8
4
2
16
E(1/13, 4/13, 8/13) =1.2389
8
2
32
16
2
E(1/25, 8/25, 16/25) 1.1239
=
Función de Entropía
http://dns1.mor.itesm.mx/~emorales/Cursos/KDD03/node17.html
Entropía
• En una distribución con un solo pico en la que pi = 1 y pj
=0, para i ≠ j la entropía es mínima lo cual indica mínima
incertidumbre o máxima información.
• En una distribución uniforme, todos los valores son
igualmente probables pi = 1/N y por tanto la entropía es
máxima, lo cual indica máxima incertidumbre o mínima
información.
Ganancia de Información
• La ganancia de información (GI), permite decidir qué
característica adicionar al árbol actual.
• Es una medida de cuánto ayuda el conocer el valor de
cierta característica para conocer el verdadero valor de la
clase a la que pertenece la clase asociada.
• Una ganancia de información alta implica que una
característica permite reducir la incertidumbre de la clase a
la que pertenece.
• La ganancia de información debe de tener su valor:
– máximo cuando el atributo sea perfecto (discrimine
perfectamente ejemplos)
– mínimo cuando el atributo no sea relevante.
Ganancia de Información
• La ganancia de información se puede calcular restando a
la entropía global, la media ponderada de las entropías
asociadas a los valores que puede tomar una
característica.
• Donde Sv, es el subconjunto de S, donde el atributo A toma
el valor de v.
ÁRBOLES DE DECISIÓN
Árboles de decisión
• Un árbol de decisión es un
conjunto de condicione (reglas)
organizadas en una estructura
jerárquica, de tal manera que la
decisión final se puede determinar
siguiendo las condiciones que se
cumplen desde la raíz hasta
alguna de sus hojas.
• Representación del conocimiento:
– Nodo internos
– Nodos hoja
 Preguntas
 Decisiones
Y
0
1
X
X
0
1
0
1
0
Z
1
Z
0
1
0
1
0
1
0
1
Ciclo de un árbol de decisión
Ejemplo 20
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student credit rating
high
high
high
medium
low
low
low
medium
low
medium
medium
medium
high
medium
no
no
no
no
yes
yes
yes
no
yes
yes
yes
no
yes
no
fair
excellent
fair
fair
fair
excellent
excellent
fair
fair
fair
excellent
excellent
fair
excellent
buys
computer
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
age?
<=30
student?
30..40
overcast
yes
>40
credit rating?
no
yes
excellent
fair
no
yes
no
yes
Árbol de decisión para
la compra de un
computador
Construcción de árboles de decisión
•
Consiste de tres etapas:
1. Construir el árbol
• Al inicio todos los ejemplos de entrenamiento están
a la raíz
• Partir los ejemplos en forma recursiva basado en los
atributos seleccionados
2. Detener la construcción.
3. Podar de árbol
• Identificar y eliminar ramas que reflejen ruido o
valores atípicos
Ejemplo Visual de Construcción de un DT
http://www-etsi2.ugr.es/depar/ccia/rf/www/tema3_00-01_www/node26.html
Ejemplo Visual de Construcción de un DT
Ejemplo Visual de Construcción de un DT
Construcción de árboles de decisión
Algoritmos TDIDT
[Top-Down Induction on Decision Trees]
Estrategia “divide y vencerás” para la construcción recursiva
del árbol de decisión de forma descendente.



Construcción del árbol.
Detener la construcción.
Podar el árbol.
 Reglas de división
 Reglas de parada
 Reglas de poda
1. Construcción del árbol
• Algoritmo básico (un algoritmo codicioso)
– Los atributos deben ser categóricos (si son continuos
ellos deben ser discretizados)
– El árbol es construido recursivamente de arriba hacia
abajo con una visión de divide y conquista.
– Al inicio, todos los ejemplos de entrenamiento están en
la raíz.
– Los ejemplos son particionados en forma recursiva
basado en los atributos seleccionados
– Los atributos son seleccionados basado en una medida
heurística o estadística (ganancia de información)
– La ganancia de información se calcula desde el nivel de
entropía de los datos.
Ejemplo 21
• Construir un árbol de decisión para los siguientes datos:
Ambiente
soleado
soleado
nublado
lluvia
lluvia
lluvia
nublado
soleado
soleado
lluvia
soleado
nublado
nublado
lluvia
Temp.
alta
alta
alta
media
baja
baja
baja
media
baja
media
media
media
alta
media
Cuenta de Clase
Total
Humedad
alta
alta
alta
alta
normal
normal
normal
alta
normal
normal
normal
alta
normal
alta
Clase
N
5
P
9
Viento
no
si
no
no
no
si
si
no
no
no
si
si
no
si
Total
14
Clase
N
N
P
P
P
N
P
N
P
P
P
P
P
N
N
0.5305
P
0.4098
E(N, P)
0.9403
Ejemplo 21
Cuenta de Clase
Total
Clase
N
5
P
9
Total
14
N
0.5305
P
0.4098
E(N, P)
0.9403
Total
5
4
5
14
N
0.5288
P
0.4422
0.0000
0.5288
E(N, P)
0.9710
0.0000
0.9710
Cuenta de Clase
Ambiente
lluvia
nublado
soleado
Total
Clase
N
2
3
5
P
3
4
2
9
Cuenta de Clase
Temp.
alta
baja
media
Total
Clase
N
2
1
2
5
P
2
3
4
9
Total
4
4
6
14
N
0.5000
0.5000
0.5283
Cuenta de Clase
Humedad
alta
normal
Total
Clase
N
4
1
5
P
3
6
9
Total
7
7
14
N
0.4613
0.4011
Cuenta de Clase
Viento
no
si
Total
Clase
N
2
3
5
P
6
3
9
Total
8
6
14
N
0.5000
0.5000
0.4422
P
0.5000
0.3113
0.3900
P
0.5239
0.1906
P
0.3113
0.5000
E(N, P)
1.0000
0.8113
0.9183
E(N, P)
0.9852
0.5917
E(N, P)
0.8113
1.0000
G
0.3468
0.0000
0.3468
0.6935
0.2467
G
0.2857
0.2318
0.3936
0.9111
0.0292
G
0.4926
0.2958
0.7885
0.1518
G
0.4636
0.4286
0.8922
0.0481
Ejemplo 21
Ambiente
soleado
soleado
nublado
lluvia
lluvia
lluvia
nublado
soleado
soleado
lluvia
soleado
nublado
nublado
lluvia
Temp. Humedad Viento Clase
alta
alta
no
N
alta
alta
si
N
alta
alta
no
P
media
alta
no
P
baja
normal
no
P
baja
normal
si
N
baja
normal
si
P
media
alta
no
N
baja
normal
no
P
media normal
no
P
media normal
si
P
media
alta
si
P
alta
normal
no
P
media
alta
si
N
saa
Árbol de decisión para jugar Golf.
Otros Algoritmos
Criterio de proporción de ganancia (C4.5)
Índice de diversidad de Gini
(CART)
Todos los atributos son continuos
Se Asume que existen varias
posibilidades de partir cada
atributo
Puede
requerir
otras
herramientas para partir los datos
(clustering)
Puede ser modificado para datos
categóricos
2. Condiciones de parada
• Condiciones para detener partición
– Todas las muestras para un nodo dado pertenecen a la
misma clase.
– No existe ningunos atributos restantes para ser
particionados – el voto de la mayoría es empleada para
clasificar la hoja.
– No existe más ejemplos para la hoja
3. Poda del árbol
• Identificar y eliminar ramas que reflejen ruido o valores
atípicos
Bibliografía
• Data Mining: Practical Machine Learning Tools and
Techniques. Ian H. Witten, Eibe Frank. Morgan Kaufmann;
2st edition (June 8, 2005). 560 pp.
• Data Mining with SQL Server 2005. ZhaoHui Tang, Jamie
MacLennan. Wiley Publishing Inc. (2004).
• Data Mining: Concepts and Techniques, Jiawei Han,
Micheline Kamber. Morgan Kaufmann; 1st edition (August,
2000), 500 pp.
• Introducción a la minería de datos. J. Hernández, J.
Ramírez.
PREGUNTAS
Mg. Samuel Oporto Díaz
[email protected]
http://www.wiphala.net/oporto
Descargar

ANN