Fundamentos de Minería de Datos
description
Transcript of Fundamentos de Minería de Datos
![Page 1: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/1.jpg)
Intelligent Databases and Information Systems research groupDepartment of Computer Science and Artificial IntelligenceE.T.S Ingeniería Informática – Universidad de Granada (Spain)
Fundamentos de Minería de DatosFundamentos de Minería de Datos
Clasificación
Fernando [email protected]
http://elvex.ugr.es/idbis/dm/
![Page 2: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/2.jpg)
2
ClasificaciónClasificación
Clasificación vs. PredicciónClasificación vs. Predicción
Clasificación: Para predecir el valor de un atributo categórico (discreto o nominal).
Predicción: Para modelar funciones que toman valores continuos (esto es, predecir valores numéricos desconocidos).
AplicacionesAplicaciones Concesión de créditos Campañas de marketing dirigido Diagnóstico médico Detección de fraudes
IntroducciónTécnicas
ÁrbolesReglasOtros
EvaluaciónBibliografía
![Page 3: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/3.jpg)
3
ClasificaciónClasificación
Construcción del modeloConstrucción del modelo El conjunto de datos utilizado para
construir el modelo de clasificación se denomina conjunto de entrenamiento.
Cada caso/tupla/muestra corresponde a una clase predeterminada: los casos de entrenamiento vienen etiquetados por su atributo de clase.
Uso del modeloUso del modelo El modelo construido a partir del conjunto de
entrenamiento se utiliza para clasificar nuevos datos.
![Page 4: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/4.jpg)
4
ClasificaciónClasificación
AprendizajeAprendizaje
Supervisado vs. No SupervisadoSupervisado vs. No Supervisado
Aprendizaje supervisado (clasificación): Los casos del conjunto de entrenamiento aparecen etiquetados con la clase a la que corresponden.
Aprendizaje no supervisado (clustering) : No se conocen las clases de los casos del conjunto de entrenamiento (ni siquiera su existencia).
![Page 5: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/5.jpg)
5
ClasificaciónClasificación
Inducción
Deducción
Modelo
Tid Attrib1 Attrib2 Attrib3 Class
1 Yes Large 125K No
2 No Medium 100K No
3 No Small 70K No
4 Yes Medium 120K No
5 No Large 95K Yes
6 No Medium 60K No
7 Yes Large 220K No
8 No Small 85K Yes
9 No Medium 75K No
10 No Small 90K Yes 10
Tid Attrib1 Attrib2 Attrib3 Class
11 No Small 55K ?
12 Yes Medium 80K ?
13 Yes Large 110K ?
14 No Small 95K ?
15 No Large 67K ? 10
Conjunto de prueba
Algoritmo de
aprendizaje
Conjunto de entrenamiento
Aprendermodelo
Aplicarmodelo
![Page 6: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/6.jpg)
6
La evaluación de un algoritmo de clasificación se puede realizar atendiendo a distintos aspectos del modelo creado o del proceso utilizado para crearlo:
Precisión (porcentaje de casos clasificados correctamente).
Eficiencia(tiempo necesario para construir/usar el clasificador).
Robustez(frente a ruido y valores nulos)
Escalabilidad(utilidad en grandes bases de datos)
Interpretabilidad(el clasificador, ¿es sólo una caja negra?)
Complejidad(del modelo de clasificación) Navaja de Occam
EvaluaciónEvaluación
![Page 7: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/7.jpg)
7
Estimación de la precisión del Estimación de la precisión del modelomodelo
Antes de construir el modelo de clasificación, se divide el conjunto de datos disponible en un conjunto de entrenamiento (para construir el modelo) y un conjunto de prueba (para evaluar el modelo).
Una vez construido el modelo, se usa para clasificar los datos del conjunto de prueba: Comparando los casos etiquetados del conjunto de prueba con el resultado de aplicar el modelo, se obtiene un porcentaje de clasificación.
Si la precisión del clasificador es aceptable, podremos utilizar el modelo para clasificar nuevos casos (de los que desconocemos su clase).
EvaluaciónEvaluación
![Page 8: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/8.jpg)
8
Estimación de la precisión del Estimación de la precisión del modelomodelo
Cuanto mayor sea su complejidad, los modelos de clasificación tienden a ajustarse más al conjunto de entrenamiento utilizado en su construcción (sobreaprendizaje).
El conjunto de prueba debe ser independiente del conjunto de entrenamiento.
El error de clasificación en el conjunto de entrenamiento NONO es un buen estimador de la precisión del clasificador.
EvaluaciónEvaluación
![Page 9: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/9.jpg)
9
SobreaprendizajeSobreaprendizaje
Sobreaprendizaje debido a la complejidad del clasificador
![Page 10: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/10.jpg)
10
SobreaprendizajeSobreaprendizaje
Sobreaprendizaje debidoa la presencia de ruido en los datos
![Page 11: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/11.jpg)
11
SobreaprendizajeSobreaprendizaje
Sobreaprendizaje debidoa la escasez de muestras
![Page 12: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/12.jpg)
12
TécnicasTécnicas
Se pueden construir distintos tipos de clasificadores
Árboles de decisión Reglas (p.ej. Listas de decisión) Clasificadores basados en casos Clasificadores paramétricos Redes neuronales Redes bayesianas SVMs (Support Vector Machines) …
![Page 13: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/13.jpg)
13
Modelo de clasificación:Árbol de decisión
Árboles de decisiónÁrboles de decisión
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Refund Marital Status
Taxable Income Cheat
No Married 80K ? 10
Caso de prueba
![Page 14: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/14.jpg)
14
Modelo de clasificación:Árbol de decisión
Árboles de decisiónÁrboles de decisión
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Refund Marital Status
Taxable Income Cheat
No Married 80K ? 10
Caso de prueba
![Page 15: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/15.jpg)
15
Modelo de clasificación:Árbol de decisión
Árboles de decisiónÁrboles de decisión
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Refund Marital Status
Taxable Income Cheat
No Married 80K No 10
Caso de prueba
Clase ‘No’Clase ‘No’
![Page 16: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/16.jpg)
16
Árboles de decisiónÁrboles de decisión
Tid Refund MaritalStatus
TaxableIncome Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes10
categóric
o
categóric
o
continuo
clase
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Conjunto de entrenamiento
Modelo de clasificación:Árbol de decisión
![Page 17: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/17.jpg)
17
Árboles de decisiónÁrboles de decisión
Tid Refund MaritalStatus
TaxableIncome Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes10
categóric
o
categóric
o
continuo
clase
Conjunto de entrenamiento
Modelo de clasificación:Árbol de decisión
MarSt
Refund
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Podemos construir Podemos construir distintos árboles:distintos árboles:¿cuál es mejor?¿cuál es mejor?
![Page 18: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/18.jpg)
18
Árboles de decisiónÁrboles de decisión
Construcción de árboles de decisión
Estrategia greedy (problema NP) Algoritmo “divide y vencerás”:
Comenzamos con todos los ejemplos de entrenamiento en la raíz del árbol de decisión.
Los ejemplos se van dividiendo en función del atributo que se seleccione para ramificar el árbol en cada nodo.
Los atributos que se usan para ramificar se eligen en función de una heurística.
![Page 19: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/19.jpg)
19
Árboles de decisiónÁrboles de decisión
Construcción de árboles de decisión
Criterios de parada: ¿Cuándo se detienela construcción del árbol de decisión?
Cuando todos los ejemplos que quedan pertenecen a la misma clase (se añade una hoja al árbol con la etiqueta de la clase).
Cuando no quedan atributos por los que ramificar (se añade una hoja etiquetada con la clase más frecuente en el nodo).
Cuando no nos quedan datos que clasificar.
![Page 20: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/20.jpg)
20
Árboles de decisiónÁrboles de decisión
Construcción de árboles de decisión¿Qué heurísticas se pueden utilizar para decidir cómo ramificar el árbol?
¿Cuál es mejor?
OwnCar?
C0: 6C1: 4
C0: 4C1: 6
C0: 1C1: 3
C0: 8C1: 0
C0: 1C1: 7
CarType?
C0: 1C1: 0
C0: 1C1: 0
C0: 0C1: 1
StudentID?
...
Yes No Family
Sports
Luxury c1c10
c20
C0: 0C1: 1
...
c11
![Page 21: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/21.jpg)
21
Árboles de decisiónÁrboles de decisión
Construcción de árboles de decisión¿Qué heurísticas se pueden utilizar para decidir cómo ramificar el árbol?
La que nos proporciona nodos más más homogéneoshomogéneos
OwnCar?
C0: 6C1: 4
C0: 4C1: 6
C0: 1C1: 3
C0: 8C1: 0
C0: 1C1: 7
CarType?
C0: 1C1: 0
C0: 1C1: 0
C0: 0C1: 1
StudentID?
...
Yes No Family
Sports
Luxury c1c10
c20
C0: 0C1: 1
...
c11
Necesitamos medir la impureza de un nodoNecesitamos medir la impureza de un nodo
![Page 22: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/22.jpg)
22
Árboles de decisiónÁrboles de decisión
Construcción de árboles de decisión
Reglas de división(heurísticas para la selección de atributos):
Ganancia de información (ID3, C4.5)
Índice de Gini (CART, SLIQ, SPRINT)
Existen otras muchas reglas de división: 2, MDL (Minimum Description Length)…
![Page 23: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/23.jpg)
23
Entropía
Medida basada en la Teoría de la Información
Árboles de decisiónÁrboles de decisión
)(log)( 21
i
m
ii ppDInfo
C1 0 C2 6
C1 2 C2 4
C1 1 C2 5
Entropía = – 0 log 0 – 1 log 1 = 0
Entropía = 0.65= – (1/6) log2 (1/6) – (5/6) log2 (1/6)
Entropía = 0.92 = – (2/6) log2 (2/6) – (4/6) log2 (4/6)
![Page 24: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/24.jpg)
24
Ganancia de información (ID3) pi Estimación de la probabilidad de que
un ejemplo de D pertenezca a la clase Ci
Entropía (información necesaria para clasificar un ejemplo en D)
Información necesaria para clasificar D después de usar el atributo A para dividir D en v particiones:
Ganancia obtenidaal ramificar utilizando el atributo A:
Árboles de decisiónÁrboles de decisión
)(log)( 21
i
m
ii ppDInfo
)(||
||)(
1j
v
j
jA DI
D
DDInfo
(D)InfoInfo(D)Gain(A) A
![Page 25: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/25.jpg)
25
Criterio de proporción de ganancia (Gain Ratio, C4.5) ID3 tiende a ramificar el árbol utilizando los atributos que tengan más valores diferentes,por lo que se “normaliza” la ganancia de información usando la entropía de la partición(que será mayor cuantas más particiones pequeñas haya):
Árboles de decisiónÁrboles de decisión
)||
||(log
||
||)( 2
1 D
D
D
DDSplitInfo j
v
j
jA
GainRatio(A) = Gain(A) / SplitInfo(A)
![Page 26: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/26.jpg)
26
Índice de Gini (CART, SLIQ, SPRINT)Medida estadística de impureza
Para construir el árbol, elegimos el atributo que proporciona la mayor reducción de
impureza
Árboles de decisiónÁrboles de decisión
n
jp jDgini
1
21)(
C1 0C2 6
Gini=0.000
C1 2C2 4
Gini=0.444
C1 3C2 3
Gini=0.500
C1 1C2 5
Gini=0.278
![Page 27: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/27.jpg)
27
Árboles de decisiónÁrboles de decisión
Comparación de reglas de divisiónPara problemas con dos clases:
![Page 28: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/28.jpg)
28
Árboles de decisiónÁrboles de decisión
Comparación de reglas de división Ganancia de información
Sesgado hacia atributos con muchos valores diferentes.
Criterio de proporción de gananciaTiende a preferir particiones poco balanceadas (con una partición mucho más grande que las otras)
Índice de GiniFunciona peor cuando hay muchas clases y tiende a favorecer particiones de tamaño y pureza similares.
Ninguna regla de división es significativamente mejor que los demás
![Page 29: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/29.jpg)
29
Árboles de decisiónÁrboles de decisión
Otros aspectos
¿Árboles binarios o n-arios?(CART binario; C4.5 n-ario para atributos categóricos, binario para atributos continuos)
Manejo de atributos continuos(selección del conjunto de tests candidatos para ramificar el árbol, p.ej. discretización previa)
Manejo de valores nulos(cómo se tratan los valores nulos/desconocidos)
![Page 30: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/30.jpg)
30
Árboles de decisiónÁrboles de decisión
El problema del sobreaprendizaje
Los árboles de decisión tienden a ajustarse demasiado al conjunto de entrenamiento utilizado para construir el árbol
Demasiadas ramas del árbol reflejan anomalías del conjunto de entrenamiento (ruido y outliers).
El árbol resultante es más complejo de lo que debería ser.
Como consecuencia, disminuye la precisióndel clasificador de cara a situaciones nuevas.
![Page 31: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/31.jpg)
31
Árboles de decisiónÁrboles de decisión
Una solución al problema del sobreaprendizaje:
Técnicas de PodaTécnicas de Poda
Una vez construido el árbol, se van eliminando ramas: utilizando un conjunto de datos distinto al conjunto de entrenamiento [CART: Poda por coste-complejidad] o no [C4.5: Poda pesimista].
![Page 32: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/32.jpg)
32
Árboles de decisiónÁrboles de decisión
Ventajas de los árboles de decisión
Algoritmos eficientes y escalables
PUBLIC (Rastogi & Shim, VLDB’1998)integra la poda en el proceso de construcción del árbol
RainForest (Gehrke et al., VLDB’1998)separa lo que determina la escalabilidad del
algoritmo
BOAT (Gehrke et al., PODS’1999)sólo necesita recorrer 2 veces el conjunto de datos
![Page 33: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/33.jpg)
33
Árboles de decisiónÁrboles de decisión
Ventajas de los árboles de decisión
Fácil interpretación (cuando son pequeños)
Rapidez para clasificar nuevos datos
Precisión comparable a otras técnicas
![Page 34: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/34.jpg)
34
Árboles de decisiónÁrboles de decisión
DEMODEMO
TDIDTTop-Down Induction of Decision Trees
![Page 35: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/35.jpg)
37
ReglasReglas
Existen muchas formas de construir modelos de clasificación basados en reglas:
A partir de un árbol de decisión Diseñando algoritmos
específicosde inducción de reglas
Metodología STAR de Michalski Listas de decisión (p.ej. RIPPER)
A partir de reglas de asociación
![Page 36: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/36.jpg)
38
ReglasReglas
A partir de un árbol de decisión
¿Por qué?Las reglas son más fáciles de interpretarque un árbol de decisión complejo.
¿Cómo? Se crea una regla para cada hoja del
árbol. Las reglas resultantes son
mutuamente excluyentes exhaustivas
![Page 37: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/37.jpg)
39
ReglasReglas
A partir de un árbol de decisión
IF (age<=30) AND (student=no)THEN buys_computer = no
IF (age<=30) AND (student=yes)THEN buys_computer = yes
IF (30<age<=40)THEN buys_computer = yes
IF (age>40) AND (credit_rating=excellent)THEN buys_computer = yes
IF (age>40) AND (credit_rating=fair)THEN buys_computer = no
age?
student? credit rating?
<=30 >40
no yes yes
yes
31..40
no
fairexcellentyesno
![Page 38: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/38.jpg)
40
ReglasReglas
A partir de un árbol de decisión
Las reglas que se derivan de un árbol se pueden
simplificar (generalizar), aunque entonces: dejan de ser mutuamente excluyentes:
varias reglas pueden ser válidas para un mismo ejemplo (hay que establecer un orden entre las reglas [lista de decisión] o realizar una votación).
Dejan de ser exhaustivas: puede que ninguna regla sea aplicable a un ejemplo concreto (hace falta incluir una clase por defecto).
![Page 39: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/39.jpg)
41
ReglasReglas
Directamente a partir del conjunto de entrenamientop.ej. LISTAS DE DECISIÓN
¿Cómo? Las reglas se aprenden de una en una. Cada vez que se escoge una regla, se
eliminan del conjunto de entrenamiento todos los casos cubiertos por la regla seleccionada.
El proceso se repite iterativamente hasta que se cumpla alguna condición de parada.
![Page 40: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/40.jpg)
42
ReglasReglas
(i) Original Data (ii) Step 1
(iii) Step 2
R1
(iv) Step 3
R1
R2
![Page 41: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/41.jpg)
43
ReglasReglas
Directamente a partir del conjunto de entrenamientop.ej. LISTAS DE DECISIÓN
¿Cómo se aprende una regla? Se empieza con la regla más general
posible. Se le van añadiendo antecedentes a la
regla para maximizar la “calidad” de la regla (cobertura y precisión).
![Page 42: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/42.jpg)
44
ReglasReglas
Ejemplospositivos
Ejemplos negativos
A3=1A3=1&&A1=2
A3=1&&A1=2&&A8=5
![Page 43: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/43.jpg)
45
ReglasReglas
Directamente a partir del conjunto de entrenamientop.ej. LISTAS DE DECISIÓN
Algoritmos de inducción de reglas FOIL (Quinlan, Machine Learning, 1990) CN2 (Clark & Boswell, EWSL’1991) RIPPER (Cohen, ICML’1995) PNrule (Joshi, Agarwal & Kumar,
SIGMOD’2001)
![Page 44: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/44.jpg)
46
ReglasReglas
DEMODEMO
CN2 Metodología STAR: Unordered CN2 Listas de decisión: Ordered CN2
RIPPERRepeated Incremental Pruning to Produce Error Reduction(basado en IREP, Iterative Reduced Error Pruning)
![Page 45: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/45.jpg)
47
ReglasReglas
Modelos basados en reglas de asociación
¿Por qué?
Buscando entre las mejores reglas de asociación, se superan algunas limitaciones de los árboles de decisión (que sólo consideran los atributos de uno en uno [y parcialmente]).
![Page 46: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/46.jpg)
48
ReglasReglas
Modelos basados en reglas de asociación
Modelos de clasificación parcialvg: Bayardo, KDD’1997
Modelos “asociativos” de clasificación vg: CBA (Liu, Hsu & Ma,
KDD’1998) RCBT (Cong et al., SIGMOD’2005)
Patrones emergentesvg: CAEP (Dong et al., ICDS’1999)
Árboles de reglasvg: Wang et al., KDD’2000
Reglas con excepcionesvg: Liu et al., AAAI’2000
![Page 47: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/47.jpg)
49
ReglasReglas
Modelos basados en reglas de asociación
CMARClassification based on Multiple Association Rules
Li, Han & Pei, ICDM’2001 CPAR
Classification based on Predictive Association Rules
Yin & Han, SDM’2003 ART
Association Rule Trees Berzal et al., Machine Learning, 2004
![Page 48: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/48.jpg)
50
ARTART
SPLICESPLICE
![Page 49: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/49.jpg)
51
ART: ART: ConstrucciónConstrucción
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
![Page 50: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/50.jpg)
52
ART: ART: ConstrucciónConstrucción
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
![Page 51: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/51.jpg)
53
ART: ConstrucciónART: Construcción
Selección de reglas:
Reglas agrupadas por conjuntos de atributos.
Criterio de preferencia.
K=1
Extracción
Selección
Ramificación
K++ Seguir?
Hoja
![Page 52: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/52.jpg)
54
ART: EjemploART: Ejemplo Conjunto de datosConjunto de datos
![Page 53: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/53.jpg)
55
ART: EjemploART: Ejemplo 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
![Page 54: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/54.jpg)
56
ART: EjemploART: Ejemplo Nivel 1Nivel 1 K = 2K = 2
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%)
NIVEL 1 - Extracción de reglas de asociación
• Umbral de soporte mínimo = 20%
• Selección automática del umbral de confianza
![Page 55: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/55.jpg)
57
ART: EjemploART: Ejemplo Nivel 1Nivel 1
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%)
NIVEL 1
Selección del mejor conjunto de reglas
p.ej. S1
![Page 56: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/56.jpg)
58
ART: EjemploART: Ejemplo Nivel 1 Nivel 1 Nivel 2 Nivel 2
![Page 57: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/57.jpg)
59
ART: EjemploART: Ejemplo Nivel 2Nivel 2
S1: if (Z=0) then C=0 with confidence 100%
if (Z=1) then C=1 with confidence 100%
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)
NIVEL 2
Extracción de reglas
RESULTADO
![Page 58: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/58.jpg)
60
ART: EjemploART: Ejemplo 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
![Page 59: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/59.jpg)
61
ARTART
DEMODEMO
ARTAssociation Rule Tree
![Page 60: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/60.jpg)
62
Clasificadores bayesianos p.ej. Naïve BayesAplicando el Teorema de Bayes, se maximiza
Ventaja Basta con recorrer los datos una sola
vezDesventajas Interpretabilidad del modelo Supone que las variables son
independientes
Otros modelosOtros modelos
)()|()|( iCPiCPiCP XX
)|(...)|()|(1
)|()|(21
CixPCixPCixPn
kCixPCiP
nk
X
![Page 61: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/61.jpg)
63
Otros modelosOtros modelos
SVMs (Support Vector Machines)
x
xx
x
xx
x
x
x
x ooo
oo
o
o
o
o o
oo
o
![Page 62: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/62.jpg)
64
Otros modelosOtros modelos
SVMs (Support Vector Machines)
Ventajas Precisión generalmente alta Robustez frente a ruido
Desventajas Costosos de entrenar
(eficiencia y escalabilidad) Difíciles de interpretar
(basados en transformaciones matemáticas para conseguir que las clases sean linealmente separables)
![Page 63: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/63.jpg)
65
Otros modelosOtros modelos
Clasificadores basados en casos (lazy learners)
Almacenan el conjunto de entrenamiento (o parte de él) y lo utilizan directamente para clasificar nuevos datos.
Ejemplos k-NN (k Nearest Neighbors) Razonamiento basado en casos (CBR)
![Page 64: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/64.jpg)
66
Otros modelosOtros modelos
k-NN (k vecinos más cercanos)
K demasiado pequeño Sensible a ruido
K demasiado grande El vecindario puede incluir puntos de otras clases
X X X
(a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor
![Page 65: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/65.jpg)
67
“Ensembles”
Combinan varios modelos con el objetivo de mejorar la precisión final del clasificador.
Bagging: Bagging: Votación por mayoríaVarios clasificadores diferentes votan para decidir la clase de un caso de prueba (ver bootstrapping).
Boosting: Boosting: Votación ponderadaLos clasificadores tienen distintos pesos en la votación (en función de su precisión), vg: AdaBoost
Otros modelosOtros modelos
![Page 66: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/66.jpg)
68
EvaluaciónEvaluación
Métricas Cómo evaluar la “calidad” de un modelo de
clasificación
MétodosCómo estimar, de forma fiable, la calidad de un
modelo.
ComparaciónCómo comparar el rendimiento relativo
de dos modelos de clasificación alternativos
![Page 67: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/67.jpg)
69
Evaluación: MétricasEvaluación: MétricasMatriz de confusión(confusion matrix)
Precisión del clasificadorPrecisión del clasificador
accuracyaccuracy = (TP+TN)/(TP+TN+FP+FN)
Predicción
CP CN
Cla
se re
al
CP TP: True positive
FN: False negative
CN FP: False
positive
TN: True negative
![Page 68: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/68.jpg)
70
Evaluación: MétricasEvaluación: Métricas
Limitaciones de la precisión (“accuracy”) :
Supongamos un problema con 2 clases: 9990 ejemplos de la clase 1 10 ejemplos de la clase 2
Si el modelo de clasificación siempre dice que los ejemplos son de la clase 1, su precisión es
9990/10000 = 99.9%
Totalmente engañosa, ya que nunca detectaremos ningún ejemplo de la clase 2.
![Page 69: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/69.jpg)
71
Evaluación: MétricasEvaluación: Métricas
Alternativa: Matriz de costes
El coste de clasificación será proporcional
a la precisión del clasificador sólo si i,j: i j C(i|j) = C(j|i)
C(i|i) = C(j|j)
C(i|j)Predicción
CP CN
Cla
se
real
CP C(P|P) C(N|P)
CP C(P|N) C(N|N)
![Page 70: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/70.jpg)
72
Evaluación: MétricasEvaluación: MétricasMedidas “cost-sensitive”
precision = TP/(TP+FP)
True positive recognition raterecall = sensitivity = TP/P = TP/(TP+FN)
True negative recognition ratespecificity = TN/N = TN/(TN+FP)
Predicción
CP CN
Cla
se re
al
CP TP: True positive
FN: False negative
CN FP: False
positive
TN: True negative
![Page 71: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/71.jpg)
73
Evaluación: MétricasEvaluación: MétricasMedidas “cost-sensitive”
F-measureF-measure
F = 2*precision*recall / (precision+recall)
F= 2TP / (2TP+FP+FN)
Predicción
CP CN
Cla
se re
al
CP TP: True positive
FN: False negative
CN FP: False
positive
TN: True negative
![Page 72: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/72.jpg)
74
Evaluación: MétricasEvaluación: Métricas
AccuracyAccuracy
Predicción
CP CN
Real
CP TP FN
CN FP TN
RecallRecall
Predicción
CP CN
Real
CP TP FN
CN FP TN
PrecisionPrecision
Predicción
CP CN
Real
CP TP FN
CN FP TN
F-measureF-measure
Predicción
CP CN
Real
CP TP FN
CN FP TN
![Page 73: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/73.jpg)
75
Evaluación: MétodosEvaluación: Métodos
Para evaluar la precisión de un modelo de clasificación nunca debemos utilizar el conjunto de entrenamiento (lo que nos daría el “error de resustitución” del clasificador), sino un conjunto de prueba independiente:
Por ejemplo, podríamos reservar 2/3 de los ejemplos disponibles para construir el clasificador y el 1/3 restante lo utilizaríamos de conjunto de prueba para estimar la precisión del clasificador.
![Page 74: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/74.jpg)
76
Evaluación: MétodosEvaluación: MétodosValidación cruzada Validación cruzada
(k-CV: k-fold Cross-Validation)(k-CV: k-fold Cross-Validation)
Se divide aleatoriamente el conjunto de datos en k subconjuntos de intersección vacía (más o menos del mismo tamaño). Típicamente, k=10.
En la iteración i, se usa el subconjunto i como conjunto de prueba y los k-1 restantes como conjunto de entrenamiento.
Como medida de evaluación del método de clasificación se toma la media aritmética de las k iteraciones realizadas.
![Page 75: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/75.jpg)
77
Evaluación: MétodosEvaluación: MétodosValidación cruzada Validación cruzada
Variantes de la validación cruzadaVariantes de la validación cruzada
“Leave one out”: Se realiza una validación cruzada con k particiones del conjunto de datos, donde k coincide con el número de ejemplos disponibles.
Validación cruzada estratificada: Las particiones se realizan intentando mantener en todas ellas la misma proporción de clases que aparece en el conjunto de datos completo.
![Page 76: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/76.jpg)
78
Evaluación: MétodosEvaluación: MétodosBootstrapping Bootstrapping
Muestreo uniforme con reemplazo de los ejemplos disponibles (esto es, una vez que se escoge un ejemplo, se vuelve a dejar en el conjunto de entrenamiento y puede que se vuelva a escoger).
0.632 bootstrap: Dado un conjunto de d datos, se toman d muestras. Los datos que no se escojan formarán parte del conjunto de prueba.
En torno al 63.2% de las muestras estarán en el “bootstrap” (el conjunto de entrenamiento) y el 36.8% caerá en el conjunto de prueba ya que (1-1/d)d e-1 =0.368
Si repetimos el proceso k veces, tendremos:
))(368.0)(632.0()( _1
_ settraini
k
isettesti MaccMaccMacc
![Page 77: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/77.jpg)
79
Evaluación: ComparaciónEvaluación: ComparaciónPrecisión Precisión [Accuracy][Accuracy]
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
![Page 78: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/78.jpg)
80
Evaluación: ComparaciónEvaluación: ComparaciónComplejidad del clasificadorComplejidad del clasificador
1
10
100
1000
ART C4.5 AQR CN2-STAR CN2-DL RIPPER
Com
ple
jid
ad d
el c
lasi
fica
dor
audiology
car
chess
hayesroth
lenses
lungcancer
mushroom
nursery
soybean
splice
tictactoe
titanic
vote
![Page 79: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/79.jpg)
81
Evaluación: ComparaciónEvaluación: ComparaciónTiempo de entrenamientoTiempo de entrenamiento
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
![Page 80: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/80.jpg)
82
Evaluación: ComparaciónEvaluación: ComparaciónOperaciones de E/S: RecorridosOperaciones de E/S: Recorridos
1
10
100
1000
10000
100000
1000000
ART C4.5 CN2-STAR CN2-DL RIPPER Naive Bayes
Op
erac
ion
es d
e E
/S (
reco
rrid
os) audiology
car
chess
hayesroth
lenses
lungcancer
mushroom
nursery
soybean
splice
tictactoe
titanic
vote
![Page 81: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/81.jpg)
83
Evaluación: ComparaciónEvaluación: ComparaciónOperaciones de E/S: RegistrosOperaciones de E/S: Registros
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
ART C4.5 CN2-STAR CN2-DL RIPPER Naive Bayes
Op
erac
ion
es d
e E
/S (
regi
stro
s)
audiology
car
chess
hayesroth
lenses
lungcancer
mushroom
nursery
soybean
splice
tictactoe
titanic
vote
![Page 82: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/82.jpg)
84
Evaluación: ComparaciónEvaluación: ComparaciónOperaciones de E/S: PáginasOperaciones de E/S: Páginas
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
Op
erac
ion
es d
e E
/S (
pág
inas
) ART
C4.5
CN2 - STAR
CN2 - DL
RIPPER
Naive Bayes
![Page 83: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/83.jpg)
85
Evaluación: ComparaciónEvaluación: ComparaciónCurvas ROC Curvas ROC (Receiver Operating Characteristics)(Receiver Operating Characteristics)
Eje vertical: “true positive rate” TPR = TP/(TP+FN)
Eje horizontal: “false positive rate” FPR = FP/(FP+TN)
![Page 84: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/84.jpg)
86
Evaluación: ComparaciónEvaluación: ComparaciónCurvas ROCCurvas ROC
Desarrolladas en los años 50 para analizar señales con ruido: caracterizar el compromiso entre aciertos y falsas alarmas.
Permiten comparar visualmente distintos modelos de clasificación.
El área que queda bajo la curva es una medida de la precisión (accuracyaccuracy) del clasificador:
Cuanto más cerca estemos de la diagonal (área cercana a 0.5), menos preciso será el modelo.
Un modelo “perfecto” tendrá área 1.
![Page 85: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/85.jpg)
87
Evaluación: ComparaciónEvaluación: ComparaciónCurvas ROCCurvas ROC
Ningún modelo es consistentemente mejor que el otro: M1 es mejor para FPR bajos, M2 para FPR altos.
![Page 86: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/86.jpg)
88
Evaluación: ComparaciónEvaluación: ComparaciónCurvas ROCCurvas ROC
¿Cómo construir la curva ROC?¿Cómo construir la curva ROC? Se usa un clasificador que prediga la
probabilidad de que un ejemplo E pertenezca a la clase positiva P(+|E)
Se ordenan los ejemplos en orden decreciente del valor estimado P(+|E)
Se aplica un umbral para cada valor distinto de P(+|E), donde se cuenta el número de TP, FP, TN y FN.
TPR = TP/(TP+FN)
FPR = FP/(FP+TN)
![Page 87: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/87.jpg)
89
Curvas ROCCurvas ROC
Evaluación: ComparaciónEvaluación: ComparaciónEjemplo P(+|E) Clase
1 0.95 +
2 0.93 +
3 0.87 -
4 0.85 -
5 0.85 -
6 0.85 +
7 0.76 -
8 0.53 +
9 0.43 -
10 0.25 +
Class + - + - - - + - + +
P 0.25 0.43 0.53 0.76 0.85 0.85 0.85 0.87 0.93 0.95 1.00
TP 5 4 4 3 3 3 3 2 2 1 0
FP 5 5 4 4 3 2 1 1 0 0 0
TN 0 0 1 1 2 3 4 4 5 5 5
FN 0 1 1 2 2 2 2 3 3 4 5
TPR 1 0.8 0.8 0.6 0.6 0.6 0.6 0.4 0.4 0.2 0
FPR 1 1 0.8 0.8 0.6 0.4 0.2 0.2 0 0 0
![Page 88: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/88.jpg)
90
BibliografíaBibliografía F. Berzal, J.C. Cubero, D. Sánchez, and J.M. Serrano: ART: A hybrid
classification method. Machine Learning, 2004 L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and
Regression Trees. Wadsworth International Group, 1984. W. Cohen. Fast effective rule induction. ICML'95 R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification, 2ed.
John Wiley and Sons, 2001 U. M. Fayyad. Branching on attribute values in decision tree
generation. AAAI’94 Y. Freund and R. E. Schapire. A decision-theoretic generalization
of on-line learning and an application to boosting. J. Computer and System Sciences, 1997.
J. Gehrke, V. Gant, R. Ramakrishnan, and W.-Y. Loh, BOAT -- Optimistic Decision Tree Construction. SIGMOD'99.
J. Gehrke, R. Ramakrishnan, and V. Ganti. Rainforest: A framework for fast decision tree construction of large datasets. VLDB’98.
.
![Page 89: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/89.jpg)
91
BibliografíaBibliografía T.-S. Lim, W.-Y. Loh, and Y.-S. Shih. A comparison of prediction
accuracy, complexity, and training time of thirty-three old and new classification algorithms. Machine Learning, 2000.
S. K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery 2(4): 345-389, 1998
J. R. Quinlan. Induction of decision trees. Machine Learning, 1:81-106, 1986.
J. R. Quinlan and R. M. Cameron-Jones. FOIL: A midterm report. ECML’93.
J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
J. R. Quinlan. Bagging, boosting, and c4.5. AAAI'96.
R. Rastogi and K. Shim. Public: A decision tree classifier that integrates building and pruning. VLDB’98
H. Yu, J. Yang, and J. Han. Classifying large data sets using SVM with hierarchical clusters. KDD'03.
![Page 90: Fundamentos de Minería de Datos](https://reader035.fdocumento.com/reader035/viewer/2022062518/56813ff5550346895dab16d7/html5/thumbnails/90.jpg)
92
CréditosCréditos Jiawei Han (University of Illinois at Urbana-
Champaign): “Data Mining: Concepts and Techniques”, capítulo 6, 2006
Pang-Ning Tan (Michigan State University), Michael Steinbach & Vipin Kumar (University of Minnesota): “Introduction to Data Mining”, capítulos 4 y 5, 2006