1 1 3.5. Líneas de Investigación Abiertas

2 2 Líneas de Investigación Abiertas Resúmenes: S.K.Madria, S.S.Bhowmick, W.K.Ng, and E.P.Lim. Research issues in Web data mining. In Proceedings of Data Warehousing and Knowledge Discovery, First International Conference, DaWaK '99, pages 303-312, 1999 http://citeseer.nj.nec.com/madria99research.html Padhraic Smyth. "Breaking Out of the Black-Box: Research Challenges in Data Mining", Workshop on Research Issues in Data Mining and Knowledge Discovery DMKD 2001 Pedro Domingos and Geoff Hulten. "Catching Up with the Data: Research Issues in Mining Data Streams" Workshop on Research Issues in Data Mining and Knowledge Discovery DMKD 2001

3 3 Líneas de Investigación Abiertas Resúmenes: Ramakrishnan Srikant (IBM Almaden) "New Directions in Data Mining", Workshop on Research Issues in Data Mining and Knowledge Discovery DMKD 2002 John F. Roddick "Data Warehousing and Data Mining: Are we working on the right things?" Advances in Database Technologies. Berlin, Springer-Verlag. Lecture Notes in Computer Science. 1552. Kambayashi, Y., Lee, D. K., Lim, E.-P., Masunaga, Y. and Mohania, M., Eds. 141-144

4 4 Líneas de Investigación Abiertas Conferencias especializadas en Minería de Datos: KDD – International Conference on Knowledge Discovery from Databases IEEE ICDM – IEEE International Conference on Data Mining IDA – Intelligent Data Analysis PKDD – European Conference on Principles and Practice of Knowledge Discovery in Databases DMKD - Workshop on Research Issues in Data Mining and Knowledge Discovery DS – International Conference on Discovery Science DWDM - International Workshop on Data Warehouse and Data Mining. DaWaK - International Conference on Data Warehousing and Knowledege Discovery.

5 5 Líneas de Investigación Abiertas Conferencias especializadas en Aprendizaje Automático: ICML “International Conference on Machine Learning” ECML “European Conference on Machine Learning” MLDM – “Machine Learning and Data Mining in Pattern Recognition”

6 6 Nuevos Lenguajes de Consulta: El descubrimiento en bases de datos se ve como un proceso de consulta a una base de datos (Imielinski and Manilla 1996). La situación se parece al desarrollo de lenguajes de consulta en los sesenta y setenta. Una consulta inductiva o de búsqueda de patrones debe permitir al usuario restringir la búsqueda inductiva en los siguientes aspectos (Han et al. 1999): La parte de la base de datos a ser minada (también llamada la vista minable o vista relevante) (Ng et al. 1998). El tipo de patrón/reglas a ser minado (también llamado restricciones del conocimiento). Cuantificadores estadísticos: representatividad (support)  %, precisión (confidence/accuracy)  %. Otras propiedades que el patrón debería cumplir (número y forma de las reglas, interés, novedad, etc.). Lenguajes de Consulta Inductivos

7 7 Ejemplos de consultas que se desean: ASOCIACIÓN -¿Por qué (causa) la división de "serie para torpes" es tan provechosa? ASOCIACIÓN + CLASIFICACIÓN -¿Qué características comparten los clientes que no renovaron sus pólizas y en qué se diferencian de las que renovaron sus pólizas? CLUSTERING: -Grupos de clientes que no pagaron su crédito. -Grupos de productos que han fallado el test de calidad. CLUSTERING + PREDICCIÓN -Grupos de clientes que es probable que vayan a comprar un nuevo producto en el próximo año. CLUSTERING + ASOCIACIÓN -Grupos de pacientes cuya muerte la causó combinaciones (cócteles) de fármacos. Lenguajes de Consulta Inductivos

8 8 La consultas no pueden ser en lenguaje natural... EJEMPLO: Lenguajes de Consulta Inductivos ¿Qué es exactamente lo que se busca?

9 9 EJEMPLO (cont.): Tipo de consulta: SELECT CORRELATIONS ON NUMERICAL FROM Persona Respuesta: Renta Familiar y Edad correlacionan (0.XX). Hijos y Edad correlacionan (0.YY). Renta Familiar e Hijos correlacionan (0.ZZ). Tipo de consulta: SELECT APPROX. ASSOCIATIONS ON (Obeso, Casado, Hijos > 0) FROM Persona Respuesta: Casado e (Hijos > 0) están asociados (4 casos, 80%). Obseso y casado están asociados (4 casos, 80%) Se deben poder poner condiciones, p.ej.: SUPPORT > 3, CONFIDENCE > 75% Lenguajes de Consulta Inductivos Correlaciones y Asociaciones

10 10 EJEMPLO (cont.): Tipo de consulta: SELECT EXACT DEPENDENCY RULES ON (Obeso, Casado, Hijos > 0) FROM Persona Respuesta:(Hijos > 0)  Casado (5 casos, 100%). Casado  Obeso (5 casos, 100%) Tipo de consulta: SELECT EXACT DEPENDENCY RULES ON * FROM Persona Respuesta:(DNI) ... Ciudad ... Tipo de consulta: SELECT PROB. DEPENDENCY RULES ON * FROM Persona Respuesta: Casado  Obeso (5 casos, 100%) Se compara P(RHS/LHS) con P(RHS) para ver si tiene SUPPORT (significación). Lenguajes de Consulta Inductivos Reglas de Dependencias de Valor

11 11 EJEMPLO (cont.): Tipo de consulta: SELECT CLASSIFICATION RULES FOR (Hijos > 0) ON * FROM Persona Respuesta: Casado AND (Renta Familiar > 2.000.000)  (Hijos > 0) También se deberían poder obtener reglas exactas, fuertes (sólo se permite un máx de errores) o probabilísticas. Lenguajes de Consulta Inductivos Clasificación

12 12 EJEMPLO (cont.): Tipo de consulta: SELECT SEGMENTATION RULES ON * FROM Persona Respuesta: Three Classes Class 1 if Casado AND (Renta Familiar > 2.000.000) Class 2 if Casado AND (Renta Familiar = 2.000.000 if Casado Renta Familiar < 2.000.000 if ¬Casado Lenguajes de Consulta Inductivos Segmentación

13 13 EJEMPLO (cont.): Patrón secuencial: ¿Qué compras preceden a la compra de un microondas? Respuesta: Frigorífico con congelador de cuatro pisos (60%). Predicciones: ¿Volumen total de ventas estimado para el año 2000? Regresión lineal sobre ventas 1995-1999 para predecir ventas 2000. Tipo de consulta: SELECT PRIMARY KEYS ON (Obeso, Casado, Hijos, Profesión) FROM Persona Respuesta: (Profesión, Hijos) (Hijos, Obeso, Casado) Lenguajes de Consulta Inductivos Tendencias temporales, Predicción Información del Esquema (descubrir claves primarias, R.I.).

14 14 EJEMPLO (cont.): Varias tablas: SELECT RULES FROM Persona, Casado Respuesta: Persona(X) AND Persona (Y) AND Casado(X,Y)  Renta Familiar(X) = Renta Familiar(Y) Lenguajes de Consulta Inductivos Esta aproximación es restrictiva a los “modelos de consulta” que permita el lenguaje. Patrones más complicados

15 15 Propuesta M-SQL (Imielinski et al. 1996) Basada en modelos de consulta... Ejemplo: SELECT FROM MINE(T): R WHERE R.Consequent = { (Age = *) } R.Support > 1000 R.Confidence > 0.65; R es una variable de regla y se puede utilizar: R.Consequent R.Body (antecedente) R.Support R.Confidence. Lenguajes de Consulta Inductivos

16 16 Propuesta DMQ (Data-Mining Query) language ( Ng et al. 1998 ): Utiliza la sintaxis del SQL para la vista minable También basado en modelos de consulta. EJEMPLO: Esquema: SALES(customer_name, item_name, transaction_id) LIVES(customer_name, district, city) ITEM(item_name, category, price) TRANSACTION(transaction_id, day, month, day) Consulta Inductiva (lenguaje natural): “buscar las ventas de qué artículos baratos (con una suma de precios menor que $100) que puede motivar las ventas de qué artículos caros (con el precio mínimo de $500) de la misma categoría de los clientes de Vancouver en 1998”. Lenguajes de Consulta Inductivos

17 17 Propuesta DMQ. EJEMPLO: Ejemplo de Consulta Inductiva: mine associations as lives(C,_, “Vancouver”) and sales+(C, ?[I], {S})  sales+(C, ?[J], {T}) from sales where S.year = 1998 and T.year = 1998 and I.category = J.category group by C, I.category having sum(I.price) = 500 with min_support = 0.01 and min_confidence = 0.5 Ejemplo de Respuesta: lives(C,_, “Vancouver”) and sales(C, “Census_CD”, _) and sales(C, “Ms/Office97”, _)  sales(C, “Ms/SQLServer”,_) [0.015, 0.68] Lenguajes de Consulta Inductivos +: operador regular (1 o más tuplas) ?[I] : utilizar clave ajena. I es la tupla instanciada. Es un patrón relacional. Support & Confidence.

18 18 Propuesta “OLE DB for Data Mining” de Microsoft. extensión del protocolo de acceso a BB.DD. OLE DB. Implementa una extensión del SQL que trabaja con DMM( Data Mining Model) y permite: 1. Crear el modelo 2. Entrenar el modelo 3. Realizar predicciones Lenguajes de Consulta Inductivos

19 19 Propuesta “OLE DB for Data Mining”: Ejemplo: CREACIÓN DEL MODELO (DMM): CREATE MINING MODEL CredikRisk ( [Customer ID] LONG KEY, [Profession] TEXT DISCRETE, [Income] TEXT DISCRETE, [Age] LONG CONTINUOUS, [Risk Level] TEXT DISCRETE PREDICT, ) USING [Microsoft Decision Tree] Esto crea un DMM vacío. Lenguajes de Consulta Inductivos Atributos de Entrada Atributo de Salida Tipo de Modelo

20 20 Propuesta “OLE DB for Data Mining”: Ejemplo: ENTRENAR EL MODELO: Se usa una sentencia INSERT INTO. A diferencia de insertar datos como en una tabla normal lo que hace es analizar los casos que le introduzcamos y construir el contenido del DMM. INSERT INTO [CreditRisk] ( [CustomerID],[Profession],[Income],[Age],[RiskLevel] ) OPENROWSET('[Provider='MSOLESQL','user','pwd', 'SELECT [CustomerID],[Profession], [Income],[Age],[Risk] FROM [Customers]' ) Lenguajes de Consulta Inductivos Obtención de los datos de entrenamiento a través de una consulta SQL por OLE SQL Vista Minable

21 21 Propuesta “OLE DB for Data Mining”: Ejemplo: USAR EL MODELO: El modelo se aplica a nuevos datos. La manera de hacerlo es similar a la concatenación de dos tablas relacionales, considerando el modelo como una tabla y los datos a predecir como otra tabla. El resultado es una nueva tabla con los datos que queramos (todos o sólo las predicciones). SELECT [CustomerID],[Income],[Age], CreditRisk.RiskLevel, PredictProbability(CreditRisk.RiskLevel) FROM CreditRisk PREDICTION JOIN Customers ON CreditRisk.Profession=Customers.Profession AND CreditRisk.Income=Customers.Income AND CreditRisk.Age=Customers.Age Lenguajes de Consulta Inductivos

22 22 También existen lenguajes de consulta para seleccionar patrones relativos a uso de páginas web: P.ej. En el sistema WUM (Web Utilization Miner) (Berendt & Spiliopoulou 2000), basado también en un grafo de secuencias de visitas, se puede utilizar el lenguaje MINT para hacer consultas del estilo: SELECT t FROM NODE AS a b, TEMPLATE a * b AS t WHERE a.support > 7 AND (b.support / a.support) >= 0.4 AND b.url != “G.html” Seleccionaría pares de páginas visitadas consecutivamente en la que la primera se ha visitado al menos 7 veces y de éstas, al menos el 40% han llegado a la segunda. Además la segunda no puede ser “G.html”. Lenguajes de consulta inductivos para Web Usage Mining

23 23 Escalabilidad: esquemas de muestreo eficientes y suficientes. procesamiento en memoria vs. en disco. combinación de recursos entre tareas involucradas. interfaces con los almacenes de datos. uso de metadata para optimizar el acceso. cuestiones cliente/servidor (dónde hacer el procesamiento). aprovechamiento de paralelismo y de computación distribuida. Retos para la Minería de Datos

24 24 Automatización: Desarrollo de asistentes (wizards) y/o lenguajes de consulta: para definir la tarea de minería, entradas, salidas,... seleccionar y utilizar el conocimiento previo. Transformación de los datos y reducción de dimensionalidad. Compromiso entre simplicidad y precisión de los modelos en pro de una mayor inteligibilidad. Retos para la Minería de Datos

25 25 Otros Retos: Tratamiento de datos cambiantes: necesidad de revisión y extensión de patrones (incrementalidad). Minería de datos con tipos no-estándar (no numérico o no textual, p.ej. gráficos vectoriales, índices a ficheros, hiperenlaces), multimedia u orientados a objetos. Retos para la Minería de Datos

26 26 80s y principios 90s: OLAP y reporting: consultas predefinidas. El sistema OLAP como sistema para extraer informes, gráficas y confirmar hipótesis. Técnicas fundamentalmente estadísticas. Se usa casi exclusivamente información interna a la organización. Finales de los 90 Data-Mining: descubrimiento de patrones. Técnicas de aprendizaje automático para generar patrones novedosos. El Data-Warehouse incluye Información Interna fundamentalmente. Principios de los 00 Técnicas de “scoring” y simulación: descubrimiento y uso de modelos globales. Estimación a partir de variables de entrada de variables de salida (causa-efecto) utilizando simulación sobre el modelo aprendido. El Data-Warehouse incluye Información Interna y Externa (parámetros de la economía, poblacionales, geográficos, etc.). Tendencias

27 27 Software Gratuito Software Disponible: Librerías Genéricas: MLC++ en C++. (Kohavi et al. 1994) (http://www.sgi.com/Technology/mlc/) WEKA en Java. (http://www.cs.waikato.ac.nz/ml/weka) Acompañado por el libro: “Data Mining: practical machine learning tools and techniques with Java implementations” Morgan Kaufmann ML-Lisp en LISP (ftp://ftp.cs.utexas.edu/pub/mooney/ml-progs/) (http://mlwww.diee.unica.it/ML/gdl/mlsoftware.html) Entorno DELVE: http://www.cs.utoronto.ca/~delve/index.html Otros (data-mining): http://www.the-data-mine.com/bin/veiw/Software/WebIndex Software Particular: C4.5 (http://mlwww.diee.unica.it/ML/gdl/c4_5.html) Progol (http://www-users.cs.york.ac.uk/~stephen/progol.html) Golem (http://www-users.cs.york.ac.uk/~stephen/golem.html). ILP systems (http://www-ai.ijs.si/~ilpnet2/systems/) FLIP & SMILES (http://www.dsic.upv.es/~flip/)

28 28 Recursos Generales: KDcentral ( www.kdcentral.com ) The Data Mine ( http://www.the-data-mine.com ) Knowledge Discovery Mine ( http://www.kdnuggets.com ) Mailing list: KDD-nuggets: moderada y con poco ruido: Para suscribirse, enviar un mensaje a “[email protected]” con “subscribe kdnuggets” en la primera línea del mensaje (el resto en blanco). Revistas: Data Mining and Knowledge Discovery. ( http://www.digimine.com/usama/datamine ) Intelligent Data Analysis ( http://www.elsevier.com/locate/ida ) Asociaciones: ACM SIGKDD (y la revista “explorations”, http://www.acm.org/sigkdd/explorations/instructions.htm ) Direcciones

29 29 Refrescadores de Estadística: http://cne.gmu.edu/modules/dau/stat/index.html http://www.statsoft.com/textbook/stathome.html Otras fuentes sobre DM: CRISP - DM, un consorcio industrial. http://www.crisp-dm.org DMG - The Data Mining Group, un consorcio mixto para crear estándares para intercambiar modelos predictivos. http://www.dmg.org/ Kurt Thearling's site: libros, artículos, tutoriales. http://www3.shore.net/~kht/ Más Direcciones

30 30 RED MIDAS: Red Española de Minería de Datos y Aprendizaje Automático. Coordinador: José Riquelme, Universidad de Sevilla. http://www.lsi.us.es/~riquelme KDNET: Red de Excelencia Europea en “Knowledge Discovery” http://www.kdnet.org Redes de Investigación

31 31...