art

Grupo de investigación en Bases de Datos y Sistemas de Información InteligentesDepartamento de Ciencias de la Computación e Inteligencia ArtificialE.T.S Ingeniería Informática – Universidad de Granada

ARTART

Un método alternativo para la construcción

de árboles de decisión

Fernando [email protected]

2

IntroducciónIntroducción

IntroducciónEl modelo ARTHipótesis candidatasAtributos continuosConclusiones

Aprendizaje en Inteligencia Artificial

Programas/sistemas autónomos. Sistemas de ayuda a la decisión.

Resultado del aprendizajeMODELO

Funciones: descripción y/o predicción.

Construcción: manual o automática.

3

Objetivo

Conseguir modelos de clasificación simplessimples, inteligiblesinteligibles y robustosrobustos de una forma eficienteeficiente y escalableescalable.



4

Inducción de árboles de decisión+

Extracción de reglas de asociación=

ARTART[Association Rule Trees][Association Rule Trees]


Los desarrollos más provechosos han surgido siempre donde se encontraron dos formas de pensar diferentes.

Heisenberg


5

Árboles de decisiónÁrboles de decisiónIntroducciónIntroducción

IntroducciónÁrbolesReglasAsociación

El modelo ARTHipótesis candidatasAtributos continuosConclusiones

Representación del conocimiento: Árbol

Nodo internos Preguntas Nodos hoja Decisiones

Y

X

1

0

X

Z Z0

0 1 0 1

0 1

0 1 1

0 1 0 1

6

Construcción de árbolesConstrucción de árbolesIntroducción > Árboles de decisiónIntroducción > Á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.

Reglas de división Reglas de parada Reglas de poda



7

Reglas de divisiónReglas de divisiónIntroducción > Árboles de decisiónIntroducción > Árboles de decisión

Criterios heurísticos para evaluar la bondad de una partición

p.ej. Medidas de impureza

Ganancia de información (ID3)



8


Criterio de proporción de ganancia (C4.5)

Índice de diversidad de Gini (CART)



9


Otros criteriosIntroducciónÁrbolesReglasAsociación


10


Alternativas de formulación más simple

MAXDIF

Índice Generalizado de Gini



11


Pese a su sencillez, MAXDIF y el Índice Generalizado de Gini obtienen resultados satisfactorios en la práctica.

Las distintas reglas de división propuestas mejoran marginalmente la precisión de los árboles de decisión y lo hacen sólo en situaciones concretas.

Berzal, Cubero, Cuenca & Martín-Bautista

““On the quest for easy-to-understand splitting On the quest for easy-to-understand splitting rules”rules”Data & Knowledge Engineering, 2002



12

Inducción de reglasInducción de reglasIntroducciónIntroducción



IDEAEmplear reglas como bloque de

construcción de clasificadores

Una regla (del tipo IF-THEN) divide el dominio del problema en aquellos casos que satisfacen la regla y aquéllos que

no

13

EjemplosEjemplosIntroducción > Inducción de reglas Introducción > Inducción de reglas

Metodología STARMetodología STARAprendizaje incremental de expresiones lógicas en forma

normal disyuntiva para describir conceptos

Listas de decisiónListas de decisiónLista ordenada de reglas

if ... then ... else if ... else ...if ... then ... else if ... else ...Estrategia “separa y vencerás”



14

Reglas de asociaciónReglas de asociaciónIntroducciónIntroducción



ItemItem En bases de datos transaccionales:

Artículo involucrado en una transacción. En bases de datos relacionales:

Par (atributo, valor)(atributo, valor)

k-itemsetk-itemsetConjunto de k items

Soporte de un itemset (support)Soporte de un itemset (support) soporte(I) = P(I)

15

Reglas de asociaciónReglas de asociaciónIntroducciónIntroducción

Regla de asociaciónRegla de asociación

X X Y Y

Soporte de una regla de asociaciónSoporte de una regla de asociación

soporte(XY) = soporte(XUY) = P(XUY)

Confianza de una regla de asociaciónConfianza de una regla de asociación

confianza(XY) = soporte(XUY) / soporte(X)

= P(Y|X)



16

Clasificadores asociativosClasificadores asociativosIntroducción > Reglas de asociaciónIntroducción > Reglas de asociación

Modelos de clasificación parcialvg: Bayardo

Modelos de clasificación “asociativos” vg: CBA (Liu et al.)

Clasificadores bayesianosvg: LB (Meretakis et al.)

Patrones emergentesvg: CAEP (Dong et al.)

Árboles de reglasvg: Wang et al.

Reglas generales con excepcionesvg: Liu et al.



17

Índice generalÍndice general

Introducción

El modelo de clasificación ART

Construcción de hipótesis candidatas

Manejo de atributos continuos

Conclusiones

18

El modelo ARTEl modelo ART


Presentación Construcción del clasificador ART Ejemplo Uso del clasificador ART Propiedades del clasificador ART Resultados experimentales

19

PresentaciónPresentaciónEl modelo ARTEl modelo ART

IntroducciónEl modelo ARTPresentaciónConstrucciónEjemploUsoPropiedadesResultados

Hipótesis candidatasAtributos continuosConclusiones

IDEAAprovechar la eficiencia de los algoritmos

de extracción de reglas de asociación para construir un modelo de

clasificación en forma de árbol de decisión.

ART = Association Rule Tree

CLAVE

Reglas de asociación + Ramas “else”

Híbrido árbol de decisión – lista de decisión

20

Un caso real: SPLICEUn caso real: SPLICEEl modelo ARTEl modelo ART



21

ConstrucciónConstrucciónEl modelo ARTEl modelo ART



K=1

Extracción de reglas con K items en su antecedente

¿existen reglasadecuadas?

Ramificación del árbolcon las reglas seleccionadasy procesamiento recursivode la rama “else” del árbol

Sí

K=K+1 ¿ K <= MaxSize ?

Sí

No

No

Creación de un nodo hoja etiquetado

con la clase más frecuente

22


Extracción de reglas: Hipótesis candidatas

MinSupp Umbral de soporte mínimo

MinConf Umbral de confianza mínima Umbral fijo Selección automática

K=1

Extracción

Selección

Ramificación

K++ Seguir?

Hoja



23

Selección de reglas:

Reglas agrupadas por conjuntos de atributos.

Criterio de preferencia.


K=1

Extracción

Selección

Ramificación

K++ Seguir?

Hoja



24

EjemploEjemplo Conjunto de datosConjunto de datos




25

EjemploEjemplo Nivel 1Nivel 1 K = 1K = 1


S1: if (Y=0) then C=0 with confidence 75%

if (Y=1) then C=1 with confidence 75%

S2: if (Z=0) then C=0 with confidence 75%

if (Z=1) then C=1 with confidence 75%

NIVEL 1 - Extracción de reglas de asociación

• Umbral de soporte mínimo = 20%

• Selección automática del umbral de confianza



26

EjemploEjemplo Nivel 1Nivel 1 K = 2K = 2


NIVEL 1 - Extracción de reglas de asociación

• Umbral de soporte mínimo = 20%

• Selección automática del umbral de confianza

S1: if (X=0 and Y=0) then C=0 (100%)

if (X=0 and Y=1) then C=1 (100%)

S2: if (X=1 and Z=0) then C=0 (100%)

if (X=1 and Z=1) then C=1 (100%)

S3: if (Y=0 and Z=0) then C=0 (100%)

if (Y=1 and Z=1) then C=1 (100%)



27

EjemploEjemplo Nivel 1Nivel 1


NIVEL 1

Selección del mejor conjunto de reglas

p.ej. S1

X=0 and Y=0: C=0 (2)

X=0 and Y=1: C=1 (2)

else

...

S1: if (X=0 and Y=0) then C=0 (100%)

if (X=0 and Y=1) then C=1 (100%)



28

EjemploEjemplo Nivel 1 Nivel 1 Nivel 2 Nivel 2




29

EjemploEjemplo Nivel 2Nivel 2


NIVEL 2

Extracción de reglas

S1: if (Z=0) then C=0 with confidence 100%

if (Z=1) then C=1 with confidence 100%

RESULTADO

X=0 and Y=0: C=0 (2)

X=0 and Y=1: C=1 (2)

else

Z=0: C=0 (2)

Z=1: C=1 (2)



30

EjemploEjemplo ART vs. TDIDTART vs. TDIDT


ARTART TDIDTTDIDT

X Y

Z

0

0

0 1

1

0 0 e ls e0 1

1

Y

X

1

0

X

Z Z0

0 1 0 1

0 1

0 1 1

0 1 0 1



31

Uso del clasificadorUso del clasificadorEl modelo ARTEl modelo ART



Berzal, Cubero, Sánchez & Serrano

““ART: A hybrid classification model”ART: A hybrid classification model”Machine Learning

32




33


Conversión del árbol en reglasConversión del árbol en reglas

Conjunto de reglas

Lista de decisión



34

PropiedadesPropiedadesEl modelo ARTEl modelo ART



Estrategia de búsquedaAlgoritmo greedy “separa y vencerás”

Robustez del clasificadorRuido y claves primarias

Complejidad del árbolProfundidadFactor de ramificación 1/MinSupp1/MinSupp

35

Resultados experimentalesResultados experimentalesEl modelo ARTEl modelo ART



ImplementaciónJava 2 SDK (Sun Microsystems) AspectJ

Experimentación10-CV & Tests estadísticosJDBC (InterBase 6) Windows NT 4.0 Workstation

Conjuntos de datosUCI Machine Learning Repositoryhttp://www.ics.uci.edu/~mlearn/MLRepository.html

36

Precisión del clasificadorPrecisión del clasificadorEl modelo ART > Resultados experimentalesEl modelo ART > Resultados experimentales

0

10

20

30

40

50

60

70

80

90

100

ART C4.5 CN2-STAR CN2-DL RIPPER Naive Bayes Por defecto

Pre

cisi

ón d

el c

lasi

fica

dor

audiology

car

chess

hayesroth

lenses

lungcancer

mushroom

nursery

soybean

splice

tictactoe

titanic

vote



37

ComplejidadComplejidadEl modelo ART > Resultados experimentalesEl modelo ART > Resultados experimentales

1

10

100

1000

ART C4.5 AQR CN2-STAR CN2-DL RIPPER

Com

plej

idad

del

cla

sifi

cado

r

audiology

car

chess

hayesroth

lenses

lungcancer

mushroom

nursery

soybean

splice

tictactoe

titanic

vote



38

Tiempo de entrenamientoTiempo de entrenamientoEl modelo ART > Resultados experimentalesEl modelo ART > Resultados experimentales

1

10

100

1000

10000

100000

1000000

ART C4.5 CN2-STAR CN2-DL RIPPER Naive Bayes

Tie

mp

o d

e en

tren

amie

nto

(m

s)

audiology

car

chess

hayesroth

lenses

lungcancer

mushroom

nursery

soybean

splice

tictactoe

titanic

vote



39

Operaciones de E/SOperaciones de E/SEl modelo ART > Resultados experimentalesEl modelo ART > Resultados experimentales

1

10

100

1000

10000

100000

1000000


Ope

raci

ones

de

E/S

(rec

orri

dos)

audiology

car

chess

hayesroth

lenses

lungcancer

mushroom

nursery

soybean

splice

tictactoe

titanic

vote



40


1

10

100

1000

10000

100000

1000000

10000000

100000000

1000000000


Ope

raci

ones

de

E/S

(reg

istr

os)

audiology

car

chess

hayesroth

lenses

lungcancer

mushroom

nursery

soybean

splice

tictactoe

titanic

vote



41


1

10

100

1000

10000

100000

1000000

10000000

100000000

1000000000

1 2 4 8 16 32 64 128 256 512 1024

Tamaño de página

Ope

raci

ones

de

E/S

(pá

gina

s)

ART

C4.5

CN2 - STAR

CN2 - DL

RIPPER

Naive Bayes



42

Comentarios finalesComentarios finalesEl modelo ARTEl modelo ART

Modelos de clasificación obtenidos Precisión aceptable Complejidad reducida Interacciones entre atributos

Método de construcción de clasificadores

Algoritmo eficiente Método escalable Selección automática de

parámetros



43


Introducción




Conclusiones

44

Hipótesis candidatasHipótesis candidatas


Extracción de reglas de asociaciónEl algoritmo TBARTBAR en ART

Evaluación de las reglas obtenidasMedidas disponiblesResultados experimentales

45

Extracción de reglasExtracción de reglasHipótesis candidatasHipótesis candidatas

IntroducciónEl modelo ARTHipótesis candidatasExtracciónEvaluación

Atributos continuosConclusiones

Sí

No

No

K=1




Sí




46

Reglas de asociaciónReglas de asociaciónHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

Extracción de reglas de asociaciónExtracción de reglas de asociación

Umbrales mínimos MinSupport MinConfidence

Estrategia “divide y vencerás” Encontrar todos los itemsets frecuentes. Generar las reglas de asociación que se

derivan de los itemsets frecuentes.



47

Reglas de asociaciónReglas de asociaciónHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

Obtención de los itemsets Obtención de los itemsets frecuentes Lfrecuentes Lkk

Algoritmos de la familia Apriori

Generación de candidatos CCkk

a partir de LLk-1 k-1 x Lx Lk-1k-1

Recorrido secuencial de la base de datos

para obtener LLkk a partir de CCkk



48

TBARTBARHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

Algoritmo de la familia Apriori

IDEA

Árbol de itemsets[Tree-Based Association Rule mining]

Berzal, Cubero, Marín & Serrano

““TBAR: An efficient method TBAR: An efficient method

for association rule mining in relational for association rule mining in relational databases”databases”

Data & Knowledge Engineering, 2001



49

TBAR: Árbol de itemsetsTBAR: Árbol de itemsetsHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

A:0 A:0 [3][3]

A:1 A:1 [2][2]

B:0 B:0 [2][2]

B:1 B:1 [3][3]

B:0 B:0 [2][2]

C:1 C:1 [2][2]

B:1 B:1 [2][2]

C:1 C:1 [2][2]

C:1 C:1 [3][3]

C:1 C:1 [4][4]

Nivel L[2]Nivel L[2]


C:1 C:1 [2][2]


A:0 A:0 [3][3]

A:1 A:1 [2][2]

B:0 B:0 [2][2]

B:1 B:1 [3][3]

B:0 B:0 [2][2]

C:1 C:1 [2][2]

B:1 B:1 [2][2]

C:1 C:1 [2][2]

C:1 C:1 [3][3]

C:1 C:1 [4][4]



C:1 C:1 [2][2]




50

TBAR vs. AprioriTBAR vs. AprioriHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

vg: CENSUS



51

TBARTBARHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

http://frontdb.ugr.es/IntroducciónEl modelo ARTHipótesis candidatasExtracciónEvaluación


52

TBAR en ARTTBAR en ARTHipótesis candidatas > Extracción de reglasHipótesis candidatas > Extracción de reglas

Extracción de itemsetsEn la última iteración, L[MaxSize+1], se eliminan los itemsets candidatos que no incluyen el atributo de la clase.

Generación de reglasSe sustituye la fase de generación de reglas por una exploración adecuada del árbol de itemsets.



53

Evaluación de las reglasEvaluación de las reglasHipótesis candidatasHipótesis candidatas



K=1




Sí


Sí

No

No



54

Medidas de cumplimientoMedidas de cumplimientoHipótesis candidatas > Evaluación de las reglasHipótesis candidatas > Evaluación de las reglas

Medidas alternativasMedidas alternativas

Confianza Convicción Interés Divergencia Hellinger Factores de certeza Utilidad...



55

Resultados experimentalesResultados experimentalesHipótesis candidatas > Evaluación de las reglasHipótesis candidatas > Evaluación de las reglas

0

10

20

30

40

50

60

70

80

90

100

Confianza Utilidad CF Convicción Interés Hellinger

Medida de evaluación de las reglas

Pre

cisi

ón d

el c

lasi

fica

dor

audiology

car

chess

hayesroth

lenses

lungcancer

mushroom

nursery

soybean

splice

tictactoe

titanic

vote



56

Comentarios finalesComentarios finalesHipótesis candidatasHipótesis candidatas



Formulación de hipótesis candidatas:Extracción de reglas de asociación

Algoritmo TBAR

Evaluación de hipótesis candidatas:Existencia de criterios alternativos

Confianza / UtilidadFactores de certeza / Convicción

57


Introducción




Conclusiones

58

Atributos continuosAtributos continuos


Discretización

vg: Discretización contextual

Árboles n-arios con atributos continuos

Resultados experimentales:Manejo de atributos continuos en ART

Anexo: Medidas de similitud

59

DiscretizaciónDiscretizaciónAtributos continuosAtributos continuos

IntroducciónEl modelo ARTHipótesis candidatasAtributos continuosDiscretizació

nÁrboles n-

ariosResultados

Conclusiones

Métodos de agrupamiento Basados en centroides Jerárquicos

AglomerativosDivisivos

Métodos de discretización Discretización supervisada vs. no

supervisada Uso local vs. global

60

Discretización contextualDiscretización contextualAtributos continuosAtributos continuos

IDEAMedir la similitud existente entre los vectores característicos de los valores

adyacentes del atributo continuo.

Discretización supervisada

Discretización jerárquica


nÁrboles n-

ariosResultados

Conclusiones

61


VersiónVersión VersiónVersión

aglomerativaaglomerativa divisivadivisiva

tt tt


nÁrboles n-

ariosResultados

Conclusiones

62


EjemploEjemploIntroducciónEl modelo ARTHipótesis candidatasAtributos continuosDiscretizació

nÁrboles n-

ariosResultados

Conclusiones

63

Árboles n-ariosÁrboles n-ariosAtributos continuosAtributos continuos


nÁrboles n-

ariosResultados

Conclusiones

Atributos continuos en árboles de decisiónAtributos continuos en árboles de decisión Árboles binarios Árboles n-arios

Métodos de discretizaciónMétodos de discretización Local Global

vg: Discretización local jerárquicaVariante aglomerativaVariante aglomerativa con pre-discretizaciónVariante divisiva

64

Árboles n-ariosÁrboles n-ariosAtributos continuosAtributos continuos

Resultados experimentales:Resultados experimentales:

Discretización en los algoritmos TDIDTDiscretización en los algoritmos TDIDT

Precisión similar a la obtenida por C4.5.

Árboles más pequeños (tanto en número de hojas como en profundidad media).

La discretización global mejora la eficiencia, manteniendo la precisión y reduciendo la complejidad del árbol.


nÁrboles n-

ariosResultados

Conclusiones

65

Resultados experimentalesResultados experimentalesAtributos continuosAtributos continuos

0

10

20

30

40

50

60

70

80

90

100

Contex

tual A

Contex

tual B

Contex

tual C 1R

MDLP

Zeta

K-Mea

ns

Equiw

idth

Equide

pth

Método de discretización local

Pre

cisi

ón d

el c

lasi

fica

dor

AR

T adultaustralianbreastbupacarglasshayesrothheartionosphereirispimaspambasethyroidwaveformwineyeastPromedio


nÁrboles n-

ariosResultados

Conclusiones

66


0

10

20

30

40

50

60

70

80

90

100

Contex

tual A

Contex

tual B

Contex

tual C 1R

MDLP

Zeta

K-Mea

ns

Equiw

idth

Equide

pth

Método de discretización global

Pre

cisi

ón d

el c

lasi

fica

dor

AR

TadultaustralianbreastbupacarglasshayesrothheartionosphereirispimaspambasethyroidwaveformwineyeastPromedio


nÁrboles n-

ariosResultados

Conclusiones

67



nÁrboles n-

ariosResultados

Conclusiones

0 10 20 30 40 50

Sin discretización - ART

Contextual - Local - ART

MDLP - Local - ART

K Means - Local - ART

Equidepth - Local - ART

Equidepth - Global - ART

K Means - Global - ART

MDLP - Global - ART

Contextual - Global - ART

Equidepth - Local - TDIDT

Equidepth - Global - TDIDT

MDLP - Local - TDIDT

Contextual - Global - TDIDT

C4.5 - Local - TDIDT

Contextual - Local - TDIDT

MDLP - Global - TDIDT

Error

68

0 20 40 60 80

MDLP - Local - ART

MDLP - Global - ART

Contextual - Global - ART

Sin discretización - ART

MDLP - Local - TDIDT

Contextual - Global - TDIDT

Contextual - Local - ART

Equidepth - Global - ART

Equidepth - Local - ART

MDLP - Global - TDIDT

Contextual - Local - TDIDT

Equidepth - Global - TDIDT

C4.5 - Local - TDIDT

Equidepth - Local - TDIDT


Complejidad


nÁrboles n-

ariosResultados

Conclusiones

69

Comentarios finalesComentarios finalesAtributos continuosAtributos continuos

ART con atributos continuos...ART con atributos continuos...

Precisión similar a la obtenida por los algoritmos TDIDT.

Árboles mucho más pequeños que los obtenidos por otros métodos.

Mejor si se utiliza discretización global:Mayor precisión.Menor complejidad.Mayor eficiencia.


nÁrboles n-

ariosResultados

Conclusiones

70


Introducción




Conclusiones

71

InfraestructuraInfraestructura

ConclusionesConclusiones

IntroducciónEl modelo ARTHipótesis candidatasAtributos continuosConclusiones Técnicas de Técnicas de

clasificaciónclasificación ARTART

Extracción de reglas Extracción de reglas de asociaciónde asociación

Técnicas de Técnicas de discretizacióndiscretización

72


ARTARTÁrboles n-arios politéticos con ramas

“else”

vs. TDIDT Árboles más pequeñosvs. DL Extracción más eficiente de

reglas

Sin mecanismos artificiales adicionales. Ajuste automático de parámetros. Método escalable (reglas de asociación). Modelos de clasificación simples y

precisos.vg: ADN


73


Resultados complementariosResultados complementarios

Algoritmo TBAR.

Algoritmos TDIDT:Reglas de división alternativas:

MaxDif y el Índice Generalizado de Gini.Árboles n-arios arbitrarios con técnicas de discretización jerárquica.

Discretizador contextual.


art

Documents