Download árbol valor -hay

Seminari sobre Arbres de Decisió
27 de Març del 2006
Tomàs Aluja
Los árboles de decisión en la minería
de datos
Tareas centrales en minería de datos
“Pattern recognition” (modelización)
Clasificación
Regresión
Clustering
Asociación
Los árboles de decisión son una alternativa no
paramétrica de modelización.
Otras posibilidades: Regresión Logística, Análisis
Discriminante, Redes Neuronales, Support Vector Machines, ...
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
2
Objetivo
Segmentar la población para encontrar grupos
homogéneos según una cierta variable de respuesta.
Los resultados se dan
de forma visual.
Los árboles difieren según:
- Tipo de la variable de respuesta
- Tipos de variables de segmentación
- Árboles binarios o n-arios
- Criterio de partición
- Criterio de parada
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
3
Construcción de un árbol de decisión
Para la construcción de un árbol de decisión, el usuario
deberá siempre definir :
Var. de respuesta
–La variable de respuesta
–Continua
Árbol de regresión
–Categórica
Árbol de clasificación
–El conjunto de variables
explicativas (de cualquier tipo)
Vars. explicativas
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
4
Algoritmo de construcción del árbol
Situar toda los datos en el nodo raíz
Encontrar la partición óptima del nodo raíz en
nodos hijos.
En cada nodo hijo: Decidir si debemos parar el
proceso o volver al paso 2.
Necesitamos definir:
• un criterio de partición
• un criterio de parada
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
5
Número de particiones por nodo (t)
Se calculan todas las particiones posibles y
selecciona entre ellas la partición óptima.
Particiones posibles en un nodo:
Según la variable explicativa:
Árbol n-ario
Árbol binario
Binaria
1
1
Nominal
1
2q-1-1
Ordinal
1
q-1
Continua
nt-1
nt-1
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
6
Antecedentes
AID (Sonquist y Morgan, 1963)
–
–
–
–
Variable de respuesta continua
Árbol n-ario con reagrupamiento
Criterio de partición: F
Criterio de parada: umbral sobre la significación
CHAID (Kass, 1980)
–
–
–
–
Variable de respuesta categórica
Árbol n-ario con reagrupamiento
Criterio de partición: χ2
Criterio de parada: umbral sobre la significación
Tendencia al sobreajuste. No optimalidad del criterio de
parada. Falta de estimaciones honestas sobre la calidad del
árbol
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
7
AID Automatic Interaction Detection,
(Sonquist & Morgan 1963)
AID se basa en la descomposición de la variancia de la variable de respuesta
en los nodos hijos.
nt
q
q
2
(
y
−
y
)
=
n
(
y
−
y
)
+
(
y
−
y
)
∑ it t ∑ tk tk t ∑∑ itk tk
2
i =1
k =1
q
F=
Parámetros
– Stopping p-value (0.01).
k =1 i∈tk
∑n
k =1
tk
( ytk − y ) q − 1
q
2
y
−
y
(
)
∑∑ itk tk nt − q
∼ Fq −1,nt − q
k =1 i∈tk
Un nodo se considera terminal si ninguna partición da un p-valor inferior al
crítico (pre-pruning).
– Merging p-value (0.05).
Los nodos hijos no se reagrupan si la significación de su diferencia es inferior al
valor crítico especificado.
– Corrección de Bonferroni.
Corrección del p-valor de parada para tener en cuenta el diferente número
nodos hijos (modalidades de las variables explicativas categóricas).
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
8
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
9
CHAID (Kass, 1980)
nj
respuesta
CHAID se basa en el cálculo del
estadístico de entre la variable de
respuesta categórica y la partición en
nodos hijos.
partición
2
(
−
)
n
n
m
jk
k
2
n ∼χ
χ = ∑∑
(q−1)(m−1)
n
k=1 j=1
nk j
n
q
nk1
nkj
n⋅ j
nkp
nk ⋅
n
Parámetros
– Stopping p-value (0.01).
Un nodo se considera terminal si ninguna partición da un p-valor inferior al
crítico (pre-pruning).
– Merging p-value (0.05).
Los nodos hijos no se reagrupan si la significación de su diferencia es inferior al
valor cr´tico especificado.
– Corrección de Bonferroni.
Corrección del p-valor de parada para tener en cuenta el diferente número de
modalidades de las varaibles explicativas categóricas.
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
10
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
11
La solución CART (Friedman, Breiman,
Olshen, Stone, 1984)
Árboles binarios
Unifica la variable de respuesta continua y categórica bajo un
mismo marco.
• Árboles de clasificación
• Árboles de regresión
Variables de segmentación de todo tipo
Criterio de partición: Impureza del nodo
No utiliza criterio de parada
Da estimaciones honestas de la calidad del árbol
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
12
Impureza de un nodo
Para variables de respuesta categóricas:
Gini
i ( t ) = ∑ i ≠ j p ( j / t ) p (i / t )
Entropia
i(t ) = −∑ j p( j / t )log2 p( j / t )
Para variables de respuesta continuas:
Variancia
2
(
y
−
y
)
∑
i
t
i ( t ) = i ∈t
n
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
13
Selección de la partición óptima
Maximizar el decremento de impureza
t
tl
nt
tr
ntr
ntl
∆i(t ) = i(t ) −
ntl
nt
i(tl ) −
ntr
nt
i(tr )
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
14
SAAD
Criterio de partición SAAD:
Maximizar la distancia de Smirnov generalizada dS
Fi función acumulada de los individuos de la clase i en el nodo t
FT función acumulada de todos los individuos del nodo t
1
FT
F1
F2
0
dS =
k
∑ Fi ( x ) − FT ( x )
i =1
x
Selección de la partición óptima (SAAD)
Variable explicativa nominal
Variable explicativa ordinal
Variable explicativa continua
Criterio de parada
Construir un árbol máximo y podar en vez de aplicar un
criterio de parada.
Árbol máximo: nodos terminales puros
36000
31 min
Hombres
No Jubilados
14000
19
Autonomica
2000
12
17000
22
3000
Aut,Ambas 35
2000
40
13 o + años
19000
39
2000
17
Castellano
1000
23
12000
21
4-12 años
4-12 años
Jubilados
Cast,Ambas
Mujeres
17000
42
Aut,Ambas
5000
28
< 10m hab.
>10m hab.
Castellano
12000
46
13 a 44
13 o + años
2000
14
17000
22
No Jubilados
Autonomica
2000
12
14000
19
Cast,Ambas
3000
Aut,Ambas 35
1000
23
Castellano
2000
40
19000
39
2000
17
< 10m hab.
Castellano
10000
19000
22
39
2000
17
Aut,Ambas
< 10m hab.
2000
22
5000
28
2000
22
13 o + años
>10m hab.
3000
32
17000
42
8000
43
12000
46
17000
42
>10m hab.
Castellano
Castellano
3000
19000
8000
32 4-12 años
39
43
4000
53
2000
22
17000
42
5000
28
17000
42
>10m hab.
3000
19000
32
39
2000
22
45 o +
Castellano
12000
46
13 a 44
8000
13
o + años
43
Aut,Ambas
5000
< 10m hab. 28
Castellano
8000
43
13 o + años4000
53
Aut,Ambas
2000
Castellano 17
13 o + 4000
años
53
3000
32
2000
17
2000
22
4-12 años
45 o +
5000
12000
28
< 10m hab.
>10m hab.
13 a 44 46
45 o +
19000
8000
39
43
< 10m hab.
12000
46
13 a 44
2000
17 Aut,Ambas
Castellano
Castellano
13 a 44
5000
28
3000
4-12 años
32
13 o + años
Aut,Ambas
13 o + años
2000
14 4-12 años
2000
22
Mujeres
4-12 años
Jubilados
12000
21
4-12 años
10000
36000
22min
31
Hombres
45 o +
17000
42
4000
53
Castellano
>10m hab. 13 a 44
3000
32
45 o +
8000
43
12000
46
45 o +
4000
53
4000
53
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
17
Coste de un árbol
Coste de un nodo:
prob. de mal clasificación
Coste de un árbol:
(decreciente con el tamaño)
Árbol óptimo
r ( t ) = 1 − max j p( j / t )
R (T ) rel =
r (root ) − ∑t∈T~ p (t )r (t )
r (root )
× 100
Min R (T )
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
18
Coste de un árbol de regresión
El árbol de regresión segmenta la población en tantos
grupos como nodos terminales.
A cada individuo de un nodo terminal se le asigna el valor
medio de la variable de respuesta en este nodo.
Coste del árbol =
error de predicción (variancia residual)
r (t ) =
1 nt
2
(
y
−
y
)
∑ it t
nt i =1
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
19
Operación de podar
Se calcula el valor de R(T), para la secuencia de árboles
óptimos por complejidad:
1
t1
t0
Tmax
Tmax , Tmax − Tt0 , Tmax − Tt0 − Tt1 ,…,1
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
20
Selección del árbol podado óptimo
Muestra test
Dividimos la muestra aleatoriamente en:
una muestra para Aprender
otra muestra para Validar
Aprendizaje
Total
R ts (T ) rel =
r ts (root ) − ∑ t∈T p (t )r ts (t )
ts
r (root )
× 100
Valida
ción
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
21
Calidad del árbol según tamaño
Calidad
20
18
16
14
12
10
8
6
4
2
0
Aprendizaje
Validación
1
5
10
15
Árbol óptimo
20
30
40
50
60
70
80
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
90
Tamaño
22
Ventajas de los árboles de decisión
Fáciles de interpretar .
Las ramas del árbol simulan bastante bien el proceso humano
para la toma de decisiones.
Las ramas del árbol definen directamente las reglas de
asignación. Los resultados son operativos de forma inmediata.
Minimizan el pretratamiento, pueden trabajar con un cierto nivel
de ruido y datos faltantes.
Detectan de forma automática estructuras complejas entre
variables.
Computacionalmente eficientes
Aproximación por saltos a la función de respuesta (el error de
predicción puede ser mayor que en otros modelos más
flexibles)
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
23
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
24
Práctica en árboles de decisión
Inadecuación del criterio de calidad de los árboles.
La asignación de un nodo a una clase de respuesta
depende de las probabilidades iniciales de cada clase de
respuesta. Necesidad de partir de situaciones
equilibradas.
El poder de discriminación de un árbol debe medirse
relativa a la situación inicial de partida.
El interés del árbol es la ordenación de la población por
grupos según valores crecientes de la variable de
respuesta. Estos grupos somos capaces de entenderlos y
localizarlos en la base de datos.
Seminari Arbres de Decisió. CPSV. Tomàs Aluja
25