Descubrimiento de Subgrupos:
Reglas Atípicas y Relevantes
José Ramón Cano
Departamento de Informática
Universidad de Jaén
III Taller Nacional de Minería de Datos
y Aprendizaje, TAMIDA’2005 Granada,
Septiembre 2005
Sumario
1.- Introducción
2.- Descubrimiento de Subgrupos
3.- Medidas Descriptivas de Interés de una Regla
4.- Preprocesamiento y Descubrimiento de
Subgrupos
2
1.- Introducción
Especificación
del Problema
Extracción
de Datos
Implantación
Evaluación
Interpretación
Explotación
Minería de Datos:
Modelos Predictivos
Modelos Descriptivos
Preparación de
Datos
3
1.- Introducción
•Modelos Predictivos: Dedicados a la inducción predictiva y
compuestos por conjuntos de reglas empleadas en clasificación.
Kweku-Muata, Osei-Bryson, Evaluation of decision trees: a multicriteria approach.
Computers and Operations Research, 31, MIT Press, 1993 -1945, 2004.
Datos
Entrenamiento
Edad
20
18
40
50
35
30
32
40
Tipo Coche Riesgo
Combi
Alto
Deportivo
Alto
Deportivo
Alto
Familiar
Bajo
Minivan
Bajo
Combi
Alto
Familiar
Bajo
Combi
Bajo
IND, S-Plus Trees,
C4.5, CN2, FACT,
QUEST, CART,
OC1, LMDT, CAL5,
T1…
Algoritmo Extrac.
Modelos Predictivos
Clasificador
(modelo)
Edad < 31
if Edad < 31
or Tipo Coche = Deport.
then Riesgo = Alto
Tipo Coche=Deport.
Alto
Alto
Medidas de calidad: Precisión, Interpretabilidad
Bajo
4
1.- Introducción
•Modelos Descriptivos: Su finalidad es la inducción descriptiva,
buscando reglas que definan patrones interesantes en los
datos. El Descubrimiento de Subgrupos es un subtipo de
modelo descriptivo.
N. Lavrac, B.Kavsec, P. Flach, L. Todorovski, Subgroup Discovery with
CN2-SD, Journal of Machine Learning Research, 5, 153-188, 2004.
Datos
Entrenamiento
Id. Trans.
1
2
Artículos
Pan, Leche
Pan, Pañal, Cerveza, Huevos
3
L e c h e , P a ñ a l, C e r v e z a , R e f r e s c o
4
P a n , L e c h e , P a ñ a l, C e r v e z a
5
P a n , L e c h e . P a ñ a l, R e f r e s c o
Algoritmo Extrac.
Modelos Descriptivos
AIS, Apriori, FPTree, RARM...
Modelos
{Pañal} * {Cerveza},
{Leche, Pan}  {Huevos, Refresco},
{Cerveza, Pan}  {Leche}
* La implicación representa simultaneidad, no causalidad
Medidas de calidad: Confidencia, Soporte
5
1.- Introducción
Diferencias entre reglas de clasificación y de asociación:
Reglas de Clasificación
Reglas de Asociación
- Sintácticas:
• Un atributo en el consecuente.
• Uno o más atributos en el consecuente.
• Asimetría con respecto a los atributos.
• Simetría de los atributos.
- Semánticas:
• La Clasificación como tarea de predicción
del futuro es un problema no
determinístico.
• Puede aparecer overfitting/underfitting.
• Cualquier algoritmo de extracción de
reglas de asociación debe de encontrar el
mismo conjunto de reglas (tarea
determinística).
• Al ser determinística la tarea, no hay
posibilidad de overfitting/underfitting.
A. A. Freitas, Understanding the crucial differences between classification and
discovery of association rules – A position paper, SIGKDD Explorations, 2, 1, 1-5,
2000.
6
2.- Descubrimiento de Subgrupos
W. Klösgen , 1996:
“Given a population of individuals and a property
of those individuals we are interested in, find
population subgroups that are statistically ‘most
interesting’, e.g., are as large as possible and
have the most unusual statistical charasteristics
with respect to the property of interest”.
W. Klösgen, Explora: A multipattern and multistrategy discovery assistant, Advance
in Knowledge Discovery and Data Mining, MIT Press, 249-271, 1996.
7
2.- Descubrimiento de Subgrupos
• Un subgrupo interesante tiene asociada una distribución de
clases que se diferencia significativamente de la distribución
global
• Emplea diferentes heurísticas para conseguir equilibrio
entre acierto y generalidad.
• Las reglas de clasificación tienden a buscar subgrupos
puros.
• El descubrimiento de subrupos se centra en buscar reglas
con proporciones de positivos significativamente altos (o
diferentes).
8
2.- Descubrimiento de Subgrupos
Puede modelarse mediante una clasificación con ganancias (para
verdaderos pos/neg: TPr) y costes (para falsos pos/neg: FPr)
Reglas de la forma: Condición -> Clase [TPr,FPr]
Donde Clase es la propiedad en la que estamos interesados.
TP=n(Cond,Clase)
FP=n(Cond, !Clase)
TN=n(!Cond,!Clase)
T Pr 
TP
TP  FN
F Pr 
FP
FP  TN
FN=n(!Cond,Clase)
positivos
negativos
Verdader. Fals.
TP positivos pos.
FP
TN
FN
9
2.- Descubrimiento de Subgrupos
Ejemplo:
Algoritmo Descub.
de Subgrupos
Datos
Entrenamiento
Explora, Midos,
Apriori-SD, CN2SD...
Modelo
Base de Datos
de Animales
Si patas=2 Y plumas=si
Si pico=si
Entonces clase = pájaro [1,0]
Entonces clase = pájaro [1,0]
Si tamaño=grande Y vuela=no Entonces clase = elefante [0.17,0.83]
N. Lavrac, B. Cestnik, D. Gamberer, P. Flach. Decision support through subgroup
discovery: three case studies and the lessons learned, Machine Learning, 57, 1-2,
10
115-143, 2004.
2.- Descubrimiento de Subgrupos
Revisión histórica:
EXPLORA: Efectúa el proceso de aprendizaje considerando toda
la información situada en una única tabla.
W. Klösgen, Explora: A multipattern and multistrategy discovery assistant, Advance
in Knowledge Discovery and Data Mining, MIT Press, 249-271, 1996.
MIDOS: Este algoritmo extiende el proceso a bases de datos
multirelacionales.
S. Wrobel, An algorithm for multi-relational discovery of subgroups, Proceedigs of
the 4th European Conference on Principles of Data Mining and Knowledge
Discovery, Springer, 78 - 87, 1997.
EXPLORA y MIDOS utilizan árboles de decisión. Posteriormente se han
utilizado modelos de separate-and-conquer, diferentes de los de divide y
vencerás de los árboles, que permiten introducir intersecciones no nulas
entre reglas.
11
2.- Descubrimiento de Subgrupos
Revisión histórica:
Apriori-SD: Adaptación del algoritmo Apriori-C que emplea
como medida de calidad de las reglas inducidas el acierto
relativo ponderado.
B. Kavsek, N.Lavrac, V. Jovanoski, Apriori-sd: Adapating association rule learning to
subgroup discovery, Proceedings of the 5th International Symposium on Intelligent
Data Analysis, Springer, 230 -241, 2003.
CN2-SD: Adaptación del algoritmo CN2 modificándole el
algoritmo de cobertura, la búsqueda heurística, la clasificación
probabilística de instancias y las medidas de evaluación.
N. Lavrac, B.Kavsec, P. Flach, L. Todorovski, Subgroup Discovery with
CN2-SD, Journal of Machine Learning Research, 5, 153-188, 2004.
12
2.- Descubrimiento de Subgrupos
Ejemplo de Algoritmo de Descubrimiento de Subgrupos: CN2-SD
Adaptación del algoritmo de extracción de reglas por cobertura CN2.
•
Procedimiento CN2Desordenado(todosEjemplos,Clases)
– ConjReglas  {}
– Para cada Clase en Clases
• Genera reglas con CN2ParaUnaClase(todosEjemplos,Clase)
• Añade reglas a ConjReglas
– Devuelve ConjReglas
•
Procedimiento CN2ParaUnaClase(Ejemplos,Clase)
– Reglas  {}
– Repite
• mejorCondicion EncuentraMejorCondicion(Ejemplos,Clase)
• If (mejorCondicion no es nula) Then
– Añade Regla ‘If mejorCondicion then Clase’ a Reglas y elimina de Ejemplos todos los ejemplos
de la clase ‘Clase’ cubiertos por mejorCondición.
– Hasta que mejorCondicion sea nula
– Devuelve Reglas
P. Clark, R. Boswell, Rule induction with CN2: some recent improvement, Proceedings of 13
the 5th European Conference (EWSL-91), Springer, 151 -163, 1991.
2.- Descubrimiento de Subgrupos
Ejemplo de Algoritmo de Descubrimiento
de Subgrupos: CN2-SD
Las adaptaciones del algoritmo CN2 llevadas a cabo son:
- Algoritmo de Cobertura: Incorporación de pesos en los ejemplos en el
algoritmo de cobertura.
Peso Aditivo:
w (e j , i) 
1
i 1
Peso Multiplicativo:
w ( e j , i )   ,0    1
i
- Búsqueda Heurística: Se emplea una heurística basada en el acierto
relativo ponderado que supone un equilibro entre generalización y
acierto de la regla, a partir de la ponderación de ejemplos.
WRAcc ( Cond  Clase ) 
n ' ( Cond )  n ' ( Cond , Clase ) n ' ( Clase ) 

 

N'
n ' ( Cond )
N'


14
2.- Descubrimiento de Subgrupos
Ejemplo de Algoritmo de Descubrimiento
de Subgrupos: CN2-SD
Modificaciones:
- Clasificación Probabilística de Instancias:
Si patas=2 Y plumas=si
Entonces clase = pájaro [1,0]
Si pico=si
Entonces clase = pájaro [1,0]
Si tamaño=grande Y Vuela=no Entonces clase = elefante [0.17,0.83]
Si el ejemplo de entrada es: patas=2, plumas=si, pico=si, tamaño=grande y
vuela=no, se disparan todas las reglas consiguiendo una distribución de
[0.72,0.28], con lo que la clase seleccionada es Pájaro. (Considerando reglas
desordenadas)
- Medidas de Evaluación:
Las medidas descriptivas de interés de una regla consideradas son:
Cobertura, Completitud, Tamaño, Relevancia y Atipicidad.
15
3.- Medidas Descriptivas de Interés de una Regla
Cobertura:
Cob ( R i )  Cob ( Cond
i
n ( Cond i )
 Clase ) 
COB 
1
nR
N
nR
 Cob ( R )
i
i 1
Completitud:
Comp ( R i )  Comp ( Cond
COMP 
1
N

Clase
i
 Clase ) 
n ( Clase
n ( Cond i , Clase )
N
j

Cond i  Clase
Cond i )
j
j
Tamaño:
TAM  n R
16
3.- Medidas Descriptivas de Interés de una Regla
Atipicidad:
n ( Cond )  n ( Cond , Clase ) n ( Clase ) 

Ati  R i   Ati Cond  Clase  
 

N
n ( Cond )
N


ATI 
nR
1
 Ati  R 
i
nR
i 1
Relevancia:
Re l  R i   Re l Cond
i
 Clase
  2   n Cond
j
REL 
1
nR
i
, Clase
j
  log
n Cond i , Clase
n Clase
j
j

 p Cond 
nR
 Re l  R 
i
i 1
17
4.- Preprocesamiento y Descubrimiento de Subgrupos
Especificación
del Problema
Extracción
de Datos
Implantación
Evaluación
Interpretación
Explotación
Minería de Datos:
Modelos Descriptivos
Preparación de
Datos
M. Scholz, Knowledge-Based sampling for subgroup discovery, Local Pattern
Detection, 3539, 171-189, 2005.
18
4.- Preprocesamiento y Descubrimiento de Subgrupos
Ventajas del Preprocesamiento:
• Los datos reales pueden ser impuros. Pueden conducir a la
extracción de reglas poco útiles
• La preparación de datos genera “datos de calidad”, los cuales
pueden conducir a reglas de calidad.
• El preprocesamiento de datos puede generar un conjunto de
datos más pequeño que el original, lo cual mejora la eficiencia de
los algoritmos de extracción de reglas.
19
4.- Preprocesamiento y Descubrimiento de Subgrupos
Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos:
El preprocesamiento se puede llevar a cabo siguiendo las siguientes vías:
• Integración y recolección de datos.
V. Detours, J. E. Dumont, H. Bersini and C. Maenhaut. Integration and cross-validation of high-throughput gene
expression data: comparing heterogeneous data sets, FEBS Letters 546:1, 2003, 98-102.
• Limpieza de datos.
W. Kim, B. Choi, E-K. Hong, S-K. Kim. A Taxonomy of Dirty Data. Data Mining and Knowledge Discovery 7, 81-99, 2003.
• Transformación de datos
T. Y. Lin. Attribute Transformation for Data Mining I: Theoretical, Explorations. International Journal of Intelligent
Systems 17, 213-222, 2002.
Reducción de
Datos
• Reducción de datos.
Selección de
Características
J.R. Cano, F. Herrera, M. Lozano.
Using evolutionary algorithms as
instance selection for data reduction in
Kdd: an experimental study, IEEE
Transactions on Evolutionary
Computation, 7, 6, 561-575, 2003.
Selección de
Instancias
Discretización
Compactación de
instancias ó
Data Squashing
20
4.- Preprocesamiento y Descubrimiento de Subgrupos
Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos:
Conjunto de Datos (D)
Conj. Entrenamiento (TR)
Conj. Test(TS)
Alg. de
Selección de
Instancias
Instancias Seleccionadas (TSS)
Alg. de Minería de
Datos (CN2-SD)
Reglas
Obtenidas
21
4.- Preprocesamiento y Descubrimiento de Subgrupos
Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos:
Algunos resultados:
- Metodología de la Experimentación: Conjunto de Datos y Parámetros
Conj. Datos
Adult
Núm. Instancias
Núm. Atributos
Núm. Clases
30132
14
2
Algoritmo de Selección de Instancias
CHC
Algoritmos de Extracción de Reglas
Parámetros
Pob=50, Eval=10000, α=0.5
Parámetros
C4.5
CN2
CN2-SD
Estrella=5, Discret. Anchura e ID3
Estrella=5, γ=0.5, Discret. Anchura e ID3
Debido al tamaño del conjunto de datos se lleva cabo la selección de instancias
siguiendo un modelo estratificado de 100 estratos:
J.R. Cano, F. Herrera, M. Lozano, Stratification for scaling up evolutionary prototype
selection, Pattern Recognition Letters, 26, 953-963, 2005.
22
4.- Preprocesamiento y Descubrimiento de Subgrupos
Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos:
Algunos resultados:
COB
COMP
TAM
REL
ATI
C4.5 cl
0.004
1.000
359
49.300
0.001
CHC st +CN2 Anchura
0.026
0.972
31
343.541
-0.016
CHC st +CN2 ID3
0.017
0.966
44
212.923
-0.011
CHC st +CN2-SD Anchura
0.408
0.978
11
1997.301
-0.085
CHC st +CN2-SD ID3
0.415
0.983
10
2050.153
-0.080
23
Descubrimiento de Subgrupos:
Reglas Atípicas y Relevantes
José Ramón Cano
Departamento de Informática
Universidad de Jaén
III Taller Nacional de Minería de Datos
y Aprendizaje, TAMIDA’2005 Granada,
Septiembre 2005
Descargar

Diapositiva 1