1 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

2 2 Sumario 1.- Introducción 2.- Descubrimiento de Subgrupos 3.- Medidas Descriptivas de Interés de una Regla 4.- Preprocesamiento y Descubrimiento de Subgrupos

3 3 1.- Introducción Especificación del Problema Minería de Datos: Modelos Predictivos Modelos Descriptivos Preparación de Datos Implantación Evaluación Interpretación Explotación Extracción de Datos

4 4 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 Algoritmo Extrac. Modelos Predictivos Clasificador (modelo) if Edad < 31 or Tipo Coche = Deport. then Riesgo = Alto Edad < 31 Alto Bajo Tipo Coche=Deport. IND, S-Plus Trees, C4.5, CN2, FACT, QUEST, CART, OC1, LMDT, CAL5, T1… Medidas de calidad: Precisión, Interpretabilidad

5 5 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 Algoritmo Extrac. Modelos Descriptivos Modelos {Pañal} *  {Cerveza}, {Leche, Pan}  {Huevos, Refresco}, {Cerveza, Pan}  {Leche} AIS, Apriori, FP- Tree, RARM... * La implicación representa simultaneidad, no causalidad Medidas de calidad: Confidencia, Soporte

6 6 1.- Introducción Diferencias entre reglas de clasificación y de asociación: - Sintácticas: Reglas de ClasificaciónReglas de Asociación Un atributo en el consecuente. Asimetría con respecto a los atributos. Uno o más atributos en el consecuente. 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.

7 7 2.- Descubrimiento de Subgrupos “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. W. Klösgen, 1996:

8 8 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).

9 9 2.- Descubrimiento de Subgrupos negativospositivos Verdader. positivos Fals. pos. 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) FN=n(!Cond,Clase) TP FP TN FN

10 10 2.- Descubrimiento de Subgrupos Ejemplo : Datos Entrenamiento Algoritmo Descub. de Subgrupos Modelo Explora, Midos, Apriori-SD, CN2- SD... 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] Base de Datos de Animales 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, 115-143, 2004.

11 11 2.- Descubrimiento de Subgrupos EXPLORA: Efectúa el proceso de aprendizaje considerando toda la información situada en una única tabla. Revisión histórica: MIDOS: Este algoritmo extiende el proceso a bases de datos multirelacionales. W. Klösgen, Explora: A multipattern and multistrategy discovery assistant, Advance in Knowledge Discovery and Data Mining, MIT Press, 249-271, 1996. 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.

12 12 2.- Descubrimiento de Subgrupos Apriori-SD: Adaptación del algoritmo Apriori-C que emplea como medida de calidad de las reglas inducidas el acierto relativo ponderado. 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. 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. N. Lavrac, B.Kavsec, P. Flach, L. Todorovski, Subgroup Discovery with CN2-SD, Journal of Machine Learning Research, 5, 153-188, 2004. Revisión histórica:

13 13 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 the 5th European Conference (EWSL-91), Springer, 151 -163, 1991.

14 14 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. - 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. Peso Aditivo: Peso Multiplicativo:

15 15 2.- Descubrimiento de Subgrupos Ejemplo de Algoritmo de Descubrimiento de Subgrupos: CN2-SD Modificaciones: - Medidas de Evaluación: - 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] Las medidas descriptivas de interés de una regla consideradas son: Cobertura, Completitud, Tamaño, Relevancia y Atipicidad. 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)

16 16 Cobertura: 3.- Medidas Descriptivas de Interés de una Regla Completitud: Tamaño:

17 17 Atipicidad: 3.- Medidas Descriptivas de Interés de una Regla Relevancia:

18 18 4.- Preprocesamiento y Descubrimiento de Subgrupos Especificación del Problema Minería de Datos: Modelos Descriptivos Preparación de Datos Implantación Evaluación Interpretación Explotación Extracción de Datos M. Scholz, Knowledge-Based sampling for subgroup discovery, Local Pattern Detection, 3539, 171-189, 2005.

19 19 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.

20 20 4.- Preprocesamiento y Descubrimiento de Subgrupos El preprocesamiento se puede llevar a cabo siguiendo las siguientes vías: Reducción de datos. Reducción de Datos Selección de Características Selección de Instancias Compactación de instancias ó Data Squashing Discretización Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos: 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. W. Kim, B. Choi, E-K. Hong, S-K. Kim. A Taxonomy of Dirty Data. Data Mining and Knowledge Discovery 7, 81-99, 2003. Integración y recolección de datos. Limpieza de datos. Transformación de datos T. Y. Lin. Attribute Transformation for Data Mining I: Theoretical, Explorations. International Journal of Intelligent Systems 17, 213-222, 2002. 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.

21 21 4.- Preprocesamiento y Descubrimiento de Subgrupos Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos: Conjunto de Datos (D) Conj. Entrenamiento (TR) Conj. Test(TS) Instancias Seleccionadas (TSS) Alg. de Selección de Instancias Alg. de Minería de Datos (CN2-SD) Reglas Obtenidas

22 22 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 Algoritmos de Extracción de ReglasParámetros C4.5 CN2Estrella=5, Discret. Anchura e ID3 CN2-SDEstrella=5, γ=0.5, Discret. Anchura e ID3 Algoritmo de Selección de InstanciasParámetros CHCPob=50, Eval=10000, α=0.5 Conj. DatosNúm. InstanciasNúm. AtributosNúm. Clases Adult30132142 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.

23 23 4.- Preprocesamiento y Descubrimiento de Subgrupos Ejemplo de Preprocesamiento aplicado a Descubrimiento de Subgrupos: Algunos resultados: COBCOMPTAMRELATI C4.5 cl0.0041.00035949.3000.001 CHC st +CN2 Anchura0.0260.97231343.541-0.016 CHC st +CN2 ID30.0170.96644212.923-0.011 CHC st +CN2-SD Anchura0.4080.978111997.301-0.085 CHC st +CN2-SD ID30.4150.983102050.153-0.080

24 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