Data Mining (LSI-2000-08)
Full text
'$7$0,1,1* Francisco J. Ferrer Jesús Aguilar Joaquín Peña Departamento de Lenguajes y Sistemas Informáticos Facultad de Informática Universidad de Sevilla INFORME TÉCNICO: LSI-2000-08 Julio, 2000
,1',&(*(1(5$/ 1. Introducción Pág. 3 2. KDD y Data Mining Pág. 5 3. Sistemas Data Warehousing y Data Marts Pág. 28 4. Referencias Pág. 36
Conocimiento y Minería de Datos 3 ,QWURGXFFLyQ Según [1] se estima que cada 20 meses se duplica la información en todo el mundo. La 6RFLHGDGGHOD,QIRUPDFLyQ destina gran cantidad de recursos en adquirir, almacenar y procesar enormes cantidades de información de muy diversa índole (financiera, comercial, industrial, científica, publicitaria, etc.) y todo ello a un ritmo que se acelera diariamente debido al constante desarrollo tecnológico donde ,QWHUQHW, base de datos dinámica y creciente llamada a ser la principal fuente de extracción de información, es sólo el pico visible del iceberg. Hoy en día las grandes organizaciones se administran con el apoyo de sistemas de gestión que manejan terabytes de información, una información que oculta FRQRFLPLHQWRen forma de reglas, asociaciones, excepciones o patrones, todos ellos de gran valor en la toma de decisiones de negocio. Frente a las respuestas proporcionadas por los tradicionales sistemas de gestión de bases de datos (³¢&XiOHV IXHURQ ODV YHQWDV HQ HO WHUFHU WULPHVWUH HQ OD UHJLyQ QRUWH"´) aparecieron las herramientas de análisis multidimensional (también llamadas OLAP, On-Line Analytical Processing) que permiten realizar consultas mucho mas complejas (³¢4XpYHQWDVVH SUHYHHQHQHOWHUFHUWULPHVWUHGHODxRSUy[LPRHQODUHJLyQQRUWH"´) y donde el tiempo aparece como una de las variables principales. Sin embargo, en ambos casos los valores obtenidos siguen derivando de los datos existentes. Figura 1. Diagrama del proceso OLAP.
Conocimiento y Minería de Datos 4 El fuerte análisis estadístico sobre el que operan estas últimas consultas proporciona métodos para la búsqueda de correlaciones y dependencias entre los datos. Y mediante herramientas de visualización (a veces XQD LPDJHQ GLFHPiVTXHPLO SDODEUDV) se identifican fácilmente tendencias en el tiempo entre varias medidas de un fenómeno. Pero no parece nada claro que las habilidades de un experto puedan con igual eficiencia analizar trillones de datos almacenados en soporte informático e inducir patrones desconocidos, en un momento en el que la diferencia entre la cantidad de datos manejados y el conocimiento que se tiene de los mismos aumenta continuamente. El interés está en ³¢&yPRDXPHQWDUODVYHQWDVHQHOWHUFHUWULPHVWUHHQ ODUHJLyQQRUWH"´ A finales de la década de los 80, la creciente necesidad de automatizar todo este proceso inductivo abre una línea de investigación para el análisis inteligente de datos. De las similitudes entre buscar valiosa información de negocio en grandes bases de datos y minar una montaña para encontrar una veta de metales valiosos, el conjunto de métodos matemáticos y técnicas software para análisis inteligente de datos y búsqueda de regularidades y tendencias en los mismos, aplicados de forma iterativa e interactiva, se denominaron técnicas de 0LQHUtDGH'DWRV o 'DWD0LQLQJ.
Conocimiento y Minería de Datos 5 .''\'DWD0LQLQJ Desde hace más de dos décadas se vienen desarrollando y utilizando complejos algoritmos para la extracción de patrones útiles en grandes conjuntos de datos. Unos de los pioneros en ello fue la administración de hacienda estadounidense que, mediante lógica difusa, redes neuronales y reconocimiento de patrones, ha intentado detectar fraudes en la declaración y evasión de impuestos [2]. Sin embargo durante todo este tiempo, las técnicas aplicadas fueron en su mayor parte dominio de las administraciones públicas. El elevado coste asociado y los enormes requisitos de almacenamiento, tiempo y memoria limitaron en gran medida el enorme campo de aplicación actual. Esta escasa difusión generó diversas nombres para una misma disciplina: NQRZOHGJH H[WUDFWLRQ LQIRUPDWLRQ GHVFRYHU\ LQIRUPDWLRQ KDUYHVWLQJ GDWD DUFKDHRORJ\ VLIWZDUH GDWD GUHGJLQJGDWDSDWWHUQSURFHVVLQJy'DWD0LQLQJ. Hoy en día el hardware ha dejado de ser el problema. Los grandes avances en las tecnologías de la información han provocado un aumento sin precedentes del volumen y el flujo de datos. Códigos de barra, tarjetas electrónicas, sensores remotos, transacciones bancarias, satélites espaciales o el reciente proyecto de cooperación internacional para descifrar el código genético humano son ejemplos de la necesidad de filtrar, analizar e interpretar volúmenes de datos que se miden en terabytes. Consolidación. Marketing dirigido, modelos de financiación, bonos del estado, control de calidad, la industria del petróleo, banca, biología molecular, prevención de incendios forestales, criminología, diagnósticos médicos, etc. El amplio campo de actuación del que ya disfrutan las herramientas de la Minería de Datos frente a su relativa novedad hace ver áreas problemáticas rápidamente. Los factores principales en la consolidación de las técnicas de la minería de datos como herramienta principal en la toma de decisiones de negocio son: 1. (O VRUSUHQGHQWH GHVDUUROOR WHFQROyJLFR XQLGR D ORV FRVWHV GH SURGXFFLyQ \ FRPHUFLDOL]DFLyQ. Los avances alcanzados en el procesamiento paralelo (sin duda factor clave) junto con la capacidad de los dispositivos de almacenamiento, permiten hoy día la aplicación a grandes bases de datos de métodos computacionalmente muy complejos en poco tiempo, algo impensable hace 20 años. En [3] se describe un ejemplo muy significativo: el %DQFR GH $PpULFD gastaba 2430 dólares por una consulta sobre 15 gigabytes en el año 1985; en 1995 gastaba 24 dólares por una consulta de 800 gigabytes. Según [4] el almacenamiento de un terabyte de información costaría hace 5 años 10 millones de dólares, hoy en día no llega al millón de dólares. 2. (O DXPHQWR HQ OD IUHFXHQFLD \ FDQWLGDG HQ DGTXLVLFLyQ GH GDWRV. Se estima que actualmente un satélite produce 50 gigabytes por hora [5]. Este ejemplo señala el enorme crecimiento en el trafico de datos, causa no solo del abaratamiento de los sistemas de almacenamiento masivo, sino también de la automatización de muchos experimentos y técnicas de recogida de datos.
Conocimiento y Minería de Datos 6 3. Intensa y creciente competencia en un comercio saturado. El comercio electrónico es ya una realidad en Estados Unidos. Grandes compañías han visto crecer y aumentar sus puntos de venta como nunca, pudiendo llegar a mercados antes no previstos. Las campañas publicitarias a través del correo electrónico garantizan que el cliente recibe la información y reduce costes implícitos en la publicidad tradicional. 4. &RQVROLGDFLyQ GH OD WHFQRORJtD SDUD HO GHVDUUROOR GH VLVWHPDV GH JHVWLyQ GH OD LQIRUPDFLyQ Definición. Dos términos empleados erróneamente sinónimos son KDD y 'DWD0LQLQJ. Según [1] se denomina 0LQHUtD GH 'DWRV al conjunto de técnicas y herramientas aplicadas al proceso no trivial de extraer y presentar conocimiento implícito, previamente desconocido, potencialmente útil y humanamente comprensible, a partir de grandes conjuntos de datos, con objeto de: 3UHGHFLUGHIRUPDDXWRPDWL]DGDWHQGHQFLDV\FRPSRUWDPLHQWRV 'HVFULELUGHIRUPDDXWRPDWL]DGDPRGHORVSUHYLDPHQWHGHVFRQRFLGRV .'' (.QRZOHGJH'LVFRYHU\LQ'DWDEDVHV, 'HVFXEULPLHQWRGH&RQRFLPLHQWRHQ%DVHV GH'DWRV) debe referirse al amplio proceso de búsqueda de un alto nivel de conocimiento a partir de datos a un bajo nivel, con la aplicación de los métodos específicos de 0LQHUtD GH 'DWRV como uno de los pasos más importantes en todo el proceso global. .'' supone la convergencia de distintas disciplinas de investigación, fundamentalmente: Aprendizaje Automático, Estadística, Reconocimiento de Patrones, Inteligencia Artificial, Sistemas de Gestión de Bases de Datos, Técnicas de Visualización de Datos, los Sistemas para el Apoyo a la Toma de Decisiones, la Recuperación de Información. Así, mientras que el término 'DWD0LQLQJ suele utilizarse por estadísticos, analistas de datos y la comunidad de sistemas de gestión de la información (MIS), .'' (formalizado en un encuentro celebrado en 1989 [1]) es aplicado a las disciplinas de la ,QWHOLJHQFLD$UWLILFLDO\HO $SUHQGL]DMH$XWRPiWLFR que tratan la extracción de conocimiento en grandes bases de datos, donde: Dado un conjunto de hechos (datos) H, un lenguaje L y alguna medida de la certeza C, definimos una regularidad o patrón S (pattern) como una sentencia en L que describe relaciones dentro de un subconjunto Hs de H con una certidumbre c, de forma que 6HVPiVVHQFLOORTXHODHQXPHUDFLyQGHWRGRVORVKHFKRVGH+ . Una regularidad que sea interesante y altamente cierta (según criterios definidos por el usuario experto) será considerado conocimiento, de forma que cuando el conocimiento se extrae partiendo de los datos de una base de datos, se tiene .'' [5].
Conocimiento y Minería de Datos 7 Los pasos en el proceso global del .'' no están claramente diferenciados y lo convierten en un proceso iterativo e interactivo con el usuario experto. Las interacciones entre las decisiones tomadas en diferentes pasos, así como los parámetros de los métodos utilizados y la forma de representar el problema suelen ser extremadamente complejos. Pequeños cambios en una parte pueden afectar fuertemente al resultado final. En [5] se estructura el proceso global en 9 etapas: Figura 2. Proceso global del .''. 1. Desarrollo y entendimiento del dominio de la aplicación, el conocimiento relevante y los objetivos del usuario final. Este paso requiere cierta dependencia usuario/analista, pues intervienen factores como: Conocer los cuellos de botella del dominio. Saber qué partes son susceptibles de un procesado automático Cuáles son los objetivos y los criterios de rendimiento exigibles. Para qué se usarán los resultados que se obtengan. Compromisos entre simplicidad y precisión del conocimiento extraído, etc. 2. Creación del conjunto de datos objetivo, seleccionando el subconjunto de variables o ejemplos sobre los que se realizará el descubrimiento. Esto implica consideraciones sobre: La homogeneidad de los datos Variación a lo largo del tiempo de los datos Estrategia de muestreo. Grados de libertad, etc. 3. Limpieza y Preprocesado de los datos: eliminación de ruido, estrategias para manejar valores ausentes, normalización de los datos, etc.
Conocimiento y Minería de Datos 8 4. Transformación y reducción de los datos. Incluye la búsqueda de características útiles de los datos según sea el objetivo final, la reducción del número de variables y la proyección de los datos sobre espacios de búsqueda en los que sea más fácil encontrar una solución. Este es un paso crítico dentro del proceso global, que requiere un buen conocimiento del problema y una buena intuición, y que, con frecuencia, marca la diferencia entre el éxito o fracaso de la Minería de Datos. 5. Elección del tipo de sistema para Minería de Datos según el conocimiento objetivo que se quiera extraer en el proceso de .'': clasificación de conceptos, agrupamiento de conceptos, predicción de comportamientos, detección de desviaciones, etc. 6. Elección del algoritmo de 0LQHUtD GH 'DWRV según el conocimiento objetivo que se desea extraer. 7. Aplicación del algoritmo de 0LQHUtD GH 'DWRV elegido. En este paso se realiza la búsqueda de conocimiento con una determinada representación del mismo. El éxito de la 0LQHUtD GH 'DWRV depende en gran parte de la correcta realización de los pasos previos, por parte del usuario. 8. Interpretación del conocimiento extraído, con posibilidad de iterar de nuevo desde el primer paso. La obtención de resultados aceptables dependerá de factores como: definición de medidas del interés del conocimiento (de tipo estadístico, en función de su sencillez, etc.) que permitan filtrarlo de forma automática, existencia de técnicas de visualización para facilitar la valoración de los resultados o búsqueda manual de conocimiento útil entre los resultados obtenidos. 9. Consolidación del conocimiento descubierto, incorporándolo al sistema, o simplemente documentándolo y enviándolo a la parte interesada. Esta etapa incluye la revisión y resolución de posibles inconsistencias con otro conocimiento extraído previamente. Por todo ello y sin quitar importancia a ninguna etapa del KDD, se puede decir que la Minería de los Datos es la parte fundamental y en la que más esfuerzos se han realizado. Medidas del Rendimiento. La definición anterior utiliza términos que son claves para determinar el rendimiento de un sistema de adquisición de conocimiento: 3UHFLVLyQ Los descubrimientos representan el contenido de la base de datos que, como reflejo de la realidad, puede contener LPSHUIHFFLRQHV \ UXLGR. Por tanto, será raro que algún conocimiento se cumpla con todos los datos. El grado de certidumbre medirá el FUpGLWRR FRQILDQ]D que el sistema o usuario puede asignar a cierto descubrimiento; si la FHUWH]D no es lo suficientemente alta, los patrones descubiertos no llegarán a ser conocimiento.
Conocimiento y Minería de Datos 9 ,QWHUpV Aunque es posible extraer numerosos SDWURQHV de cualquier base de datos, sólo se consideran como conocimiento aquéllos que resulten interesantes según ciertos criterios del usuario. En particular, un patrón interesante debe ser nuevo, potencialmente útil y no trivial. /HQJXDMHGHDOWRQLYHO El conocimiento descubierto debe representarse de forma inteligible desde el punto de vista humano Limitaciones. La inducción de conocimiento en bases de datos se encuentra con dificultades no previstas por los tradicionales sistemas de aprendizaje, pues en el mundo real, las bases de datos suelen ser GLQiPLFDVLQFRPSOHWDVUXLGRVDV\PX\JUDQGHV [1]. Por estos motivos, muchos algoritmos de aprendizaje no son HILFLHQWHV al ser aplicados sobre determinadas bases de datos y gran parte del trabajo que se realiza en la inducción de conocimiento trata de solucionar estos problemas: 'DWRVGLQiPLFRV En la mayoría de las bases de datos, los datos son modificados de forma continua. Cuando el valor de los datos almacenados es función del tiempo, el conocimiento inducido varía según el instante en que se obtenga. Por ello es deseable un sistema que funcione de forma continua, en modo secuencial, para tener siempre actualizado el conocimiento extraído. 'DWRVLQFRPSOHWRV El manejo de datos incompletos en una base de datos puede deberse a pérdida de valores de algún atributo (al que se asigna entonces el valor desconocido), o a la ausencia del mismo en la vista que el sistema posee sobre los datos. En ambos casos, la incidencia en el resultado dependerá de que el dato incompleto sea relevante o no para el objetivo del sistema de aprendizaje. Por ejemplo, un sistema para aprender a diagnosticar arritmias cardíacas no se verá afectado por la pérdida de datos como el color del pelo del paciente, pero sí por otros como el ritmo cardíaco. 5XLGRHLQFHUWLGXPEUHHQORVGDWRV El ruido existente en los datos viene determinado tanto por el tipo de valores de los atributos: real (presión arterial), entero (ritmo cardíaco), cadena de caracteres (nombre del paciente) o nominal (tipo de arritmia), como por la exactitud en la medida de dichos valores (especialmente para atributos numéricos). Por otro lado, es frecuente que las regularidades que se encuentran entre los datos de partida no se verifiquen siempre, sino con cierta probabilidad. Este efecto se debe no sólo a la presencia de ruido en la base de datos, sino también a la indeterminación existente en muchos aspectos de la realidad y a imprecisiones en el modelado de la misma (no hay que olvidar que en el diseño de la base de datos se modela la realidad, y todo modelo no es sino una aproximación más o menos precisa).
Conocimiento y Minería de Datos 16 Aprendizaje Supervisado. Para describir los distintos algoritmos usaremos un clásico ejemplo didáctico (tabla 1) donde se describen las condiciones ambientales que han determinaron en el pasado si se jugó o no un partido de golf. Las 4 primeras columnas representan los atributos de la base de datos; los valores pueden ser de distinto tipo (discreto o continuo) y estar en distinto rango. La ultima columna es la etiqueta (o clase) que diferencia a cada uno de los ejemplos (o casos) y sobre la cual se intenta extraer conocimiento. Tabla 1. Base de datos de ejemplo. El último ejemplo representa la situación ambiental actual para la que se quiere conocer si en función de los datos pasados se jugará o no el partido. $UEROHVGHGHFLVLyQ Es una forma de representación sencilla basada en la lógica de proposiciones extendida (también denominada "0+" o REMHWRDWULEXWRYDORU). Utiliza la técnica ³GLYLGH\YHQFHUiV´ para clasificar el conjunto de ejemplos en un número finito de clases predefinidas realizando particiones o subconjuntos de forma recursiva y sin backtracking [8]. Las particiones del conjunto inicial se traducen en subarboles para cuyos ejemplos, los valores del nodo padre cumplen la condición o etiqueta de la rama asociada, siendo conjuntos disjuntos respecto al atributo sobre el cual se generan los cortes.
Conocimiento y Minería de Datos 17 Una vez se obtiene el árbol a partir del conjunto de entrenamiento, los ejemplos del test cuya clase se desconoce son clasificados recorriendo el árbol por aquellas ramas para las cuales los valores de sus atributos se cumplen hasta alcanzar una hoja. Los nodos del árbol quedan etiquetados con nombres de atributos, las ramas con los valores posibles para el atributo, y las hojas con las diferentes clases. Figura 6. Árbol de decisión. Los sistemas basados en árboles de decisión forman una familia llamada TDIDT (Top- Down Induction of Decision Trees), cuyo representante más conocido es C4.5 [9], mejora de ID3 (Interactive Dichotomizer) que permite clasificar ejemplos con atributos que toman valores continuos. El método de clasificación de C4.5 es ya una técnica empleadas por herramientas de 'DWD 0LQLQJ junto a otros dos métodos específicos: Arboles de Clasificación y Regresión (CART: Classification And Regression Tree) y Detección de Interacción Automática de Chi Cuadrado (CHAI: Chi Square Automatic Interaction Detection). La principal ventaja de esta representación son sus reducidos requisitos computacionales. Sin embargo cuando el número de atributos es elevado y para estos lo es también el dominio de valores, se vuelven difíciles de comprender. La construcción y clasificación de un árbol de decisión viene dada por: la función de selección, el criterio de parada y el algoritmo de podado. La función selección es el criterio utilizado por el árbol para particionar el conjunto de entrenamiento, esto es, obtener los sucesivos subarboles que lo componen. Las mas utilizada es la ganancia de información media (*DLQ UDWLR [10]) que selecciona para cada partición el atributo que genera la reducción máxima de la entropía media. Otras medidas utilizadas son GINI [11 – Cart 86] y la ganancia de información normalizada [12]. 3/$<123/$<123/$<3/$<
Conocimiento y Minería de Datos 18 El criterio de parada determina cuando una partición se completa. Generalmente se llega a una hoja cuando todos los ejemplos del subconjunto que contiene pertenencen a la misma clase, pero no es el único criterio. El algoritmo de podado intenta prevenir el sobreajuste (overfiting). El sobreajuste puede evitarse mediante un pre-podado (que sufre el efecto horizonte) o un post-podado donde el árbol ya esta totalmente construido (Error-Complexity [11], error pesimista [8], error mínimo). En su contra los arboles de decisión poseen una potencia descriptiva limitada por las condiciones o reglas con las que se divide el conjunto de entrenamiento (normalmente relaciones de comparación entre un atributo y un valor). Los DUEROHV PRQRWKHWLF (un solo atributo para cada nodo) están limitados a particiones D[LVSDUDOOHO del espacio de búsqueda. Los DUEROHVSRO\WKHWLF (más de un atributo para cada nodo) tienen un alto coste computacional. Figura 7. TDIT. 7',7(MHPSORVÌI3RGDGRI*HQHUDU$UERO(MHPSORV I*HQHUDU$UERO(MHPSORV 6LI&RQGLFLRQ3DUDGD(MHPSORV Í&ODVH0D\RULWDULD(MHPSORV 6LQR PHMRU&RUWHÌI6HOHFFLRQ(MHPSORV 1RGRÌI1XHYR1RGRPHMRU&RUWH ∀YDORUY∈(MHPSORVPHMRU&RUWH &RUWH9ÌH∈(MHPSORVHPHMRU&RUWH=Y 6XE$UERO9ÌI*HQHUDU$UERO&RUWH9 1RGRDUERO9Ì6XE$UERO9
Conocimiento y Minería de Datos 19 5HJODVGHSURGXFFLyQ Una desventaja de los árboles de decisión es que tienden a ser demasiado grandes en aplicaciones reales (al manejar valores continuos y decenas de atributos) y por tanto, se hacen difíciles de interpretar desde el punto del usuario. Para simplificar y hacer comprensible un modelo tan complejo existen técnicas para convertir árboles de decisión en otras formas de representación, como las reglas de producción del tipo VLHQWRQFHV, basadas también en lógica de proposiciones: el consecuente es una clase, y el antecedente es una expresión proposicional, que puede estar en forma normal conjuntiva (CNF) o ser simplemente un término (figura 3). Sin embargo sigue siendo una forma de representación limitada ya que no permite expresar incertidumbre. Figura 8. Reglas de producción. En [9] se propone una técnica para construir reglas de decisión, basadas en lógica de proposiciones, a partir de árboles de decisión, convirtiendo cada ruta UDL]KRMD en una regla y eliminado aquellas redundantes. El problema es que incluso las reglas de producción que se obtienen resultan a veces demasiado complejas para el experto. Algunos sistemas como PRISM [14], generan directamente reglas algo más sencillas, sin tener que construir el árbol previamente, mediante un algoritmo parecido a ID3 y con una precisión similar. La familia AQ [7] la forman sistemas (AQ11, AQ15, etc.) que generan descripciones estructurales, por diferenciarlas de las descripciones de atributos de los sistemas anteriormente mencionados. Estas descripciones son también reglas de producción, aunque con mayor capacidad descriptiva, pues su antecedente es una fórmula lógica. La notación utilizada en estas reglas se denomina VL1 (Variable-valued Logic system 1, [15]) y permite utilizar selectores (igualdad entre un atributo y un valor o conjunto de valores), complejos (conjunciones de selectores) y disyunciones de complejos para construir las reglas de producción. Play Ì outlook = sunny, humid > 75 Play Ì outlook = rainy, wind = FALSO Play Ì outlook = overcast No Play Ì outlook = sunny, humid ≤ 75 No Play Ì outlook=rainy, wind = CIERTO
Conocimiento y Minería de Datos 20 /LVWDVGHGHFLVLyQ Las listas de decisión son otra forma de representación basada en lógica de proposiciones. Es una generalización de los árboles de decisión y de las representaciones conjuntivas (CNF) y disyuntivas (DNF). Una lista de decisión es una lista de pares de la forma: G & G & G & donde cada di es una descripción elemental, cada Ci es una clase, y la última descripción dn es el valor verdadero. Así, la clase de un objeto será Ci cuando di sea la primera descripción que lo satisface. Por tanto, se puede pensar en una lista de decisión como en una regla de la forma: VLG HQWRQFHV& VLQR VLG HQWRQFHV& VLQR VLG HQWRQFHV& Se usan por ejemplo en el sistema CN2 [16] que es una modificación del sistema AQ, que pretende mejorar el aprendizaje a partir de ejemplos con ruido (al evitar la dependencia de ejemplos específicos e incorporar una poda del espacio de búsqueda). Las descripciones elementales de los pares que forman la lista de decisión tienen la misma forma que los complejos de AQ. Figura 9. Listas de decisión. (outlook = rainy AND wind, No Play); (outlook = sunny AND humid ≤ 75, No Play); (CIERTO, Play)
Conocimiento y Minería de Datos 21 5HSUHVHQWDFLRQHVEDVDGDVHQHMHPSORV El aprendizaje basado en ejemplos (,QVWDQFH%DVHG /HDUQLQJ $OJRULWKPV ,%/ $OJRULWKPV) ha recibido distintos nombres desde sus origines: /D]\/HDUQLQJ,QVWDQFH%DVHG 0HPRU\BEDVHG ([HPSODU%DVHG, etc. Representan el conocimiento mediante ejemplos representativos, basándose en "similitudes" entre los datos [17]. Figura 10. Lazy Learning. El aprendizaje consiste en la selección de los ejemplos que mejor representan a los conceptos existentes en la base de datos; estos ejemplos representativos serán los únicos que se almacenen, reduciendo así considerablemente el espacio necesario y acelerando el posterior proceso de aprendizaje. Los sistemas de aprendizaje por vecindad suelen realizar un preprocesado de los datos antes del aprendizaje y un postprocesado. Normalmente el preprocesado consiste en filtrar el ruido y normalizar (lineal o standard) en un mismo rango todos los atributos del conjunto de entrada. Sistemas más complejos utilizan una representación diferente (prototipos, hiperrectangulos, reglas, etc.) para reducir de entrada el espacio de búsqueda. Utilizan una )XQFLyQ 6LPLOLWXG para clasificar los nuevos ejemplos según sea su parecido o proximidad. Esta suele ser difícil de definir cuando la base de datos contiene atributos discretos y continuos, utilizando distintas métricas en cada caso. La tabla 2 muestra un resumen de las principales distancias continuas utilizadas. En [18] se propone una métrica homogénea.
Conocimiento y Minería de Datos 22 Tabla 2. Distancias continuas usuales. Los algoritmos de aprendizaje basado en ejemplos han adquirido mayor importancia recientemente con los sistemas de razonamiento basado en casos (&DVH%DVHG5HDVRQLQJ) para diagnóstico y resolución de problemas. Además, pueden utilizarse como paso previo a otros sistemas de aprendizaje a partir de ejemplos, para entrenarlos con conjuntos de ejemplos más pequeños y representativos.
Conocimiento y Minería de Datos 23 Redes neuronales. Incluidas dentro de los modelos conexionistas, ([19], [20]) son sistemas de representación no simbólico, formados por un conjunto de sencillos elementos de computación llamados neuronas artificiales. Estas neuronas están interconectadas a través de unas conexiones con unos pesos asociados, que representan el conocimiento en la red. Cada neurona calcula la suma de sus entradas, ponderadas por los pesos de las conexiones, le resta un valor umbral y le aplica una función no lineal (normalmente una VLJPRLGH). Figura 11. Modelo 3HUFHSWRQ. Dos modelos básicos de redes neuronales son el percepton (basado en la teoria de resonancia adaptativa) y el backpropagation (redes recurrentes). En modelos multicapa como el percepton, el resultado sirve de entrada a las neuronas de la capa siguiente. El modelo EDFN SURSDJDWLRQ utiliza un método iterativo para propagar los términos de error (diferencia entre valores obtenidos y valores deseados), necesarios para modificar los pesos de las conexiones interneuronales. El EDFNSURSDJDWLRQ puede considerarse como un método de regresión no lineal en el que aplica un descenso de gradiente en el espacio de parámetros (pesos), para encontrar mínimos locales en la función de error [5]. Las redes neuronales han sido utilizadas con éxito en diferentes tipos de problemas: • Auto-asociación: la red genera una representación interna de los ejemplos aportados, y responde con el más aproximado a su "memoria". Ejemplo: máquina de Boltzman. • Clasificación de patrones: la red es capaz de clasificar cada entrada en un conjunto predefinido de clases; pe. back-propagation. • Detección de regularidades: la red se adapta a los ejemplos de entrada, tomando de ellos varias características para clasificarlos; en este caso, el conjunto de clases no está definido de antemano, por lo que el aprendizaje es no supervisado. Ej.: red MAXNET, ART1, mapas de Kohonen, red de Oja, etc.
Conocimiento y Minería de Datos 24 Las tasas de error de las redes neuronales son equivalentes a las de las reglas generadas por los métodos de aprendizaje simbólicos, aunque son algo más robustas cuando los datos son ruidosos. Las principales desventajas para usar redes neuronales en la 0LQHUtDGH'DWRV son: • el aprendizaje es bastante más lento que en un sistema de aprendizaje simbólico [21]. • el conocimiento obtenido por las mismas no es representable en forma de reglas inteligibles, sino que lo forma el conjunto de pesos de las conexiones interneuronales. • además, es difícil incorporar conocimiento de base o interacción del usuario en el proceso de aprendizaje de una red neuronal. • Requiren gran cantidad de variables (neuronas). Figura 12. Modelo Backpropagation.
Conocimiento y Minería de Datos 25 Algoritmos Genéticos. Los algoritmos genéticos surgen a finales de la década de los 60 gracias a John Holland, entonces investigador de la universidad de Michigan. Inicialmente denominados SODQHV UHSURGXFWLYRV, se popularizan bajo el nombre de algoritmos genéticos tras la publicación de su libro $GDSWDWLRQLQ1DWXUDODQG$UWLILFLDO6\VWHPV en 1975. Se inspiran en la teoría de la selección de las especies de Charles Darwin que sostiene que aquellos individuos de una población que posean los caracteres más ventajosos dejarán proporcionalmente más descendencia en la siguiente generación; y si tales caracteres se deben a diferencias genéticas que pueden transmitirse a los descendientes, tenderá a cambiar la composición genética de la población, aumentando el número de individuos con dichas características. De esta forma, la población completa de seres vivos se adapta a las circunstancias variables de su entorno. El resultado final es que los seres vivos tienden a perfeccionarse en relación con las circunstancias que los envuelven. La flexibilidad de los algoritmos genéticos les permiten ser aplicadRs como técnicas de Búsqueda, Clasificación, Predicción y Optimización (parametrización, configuración, maximización, minimización). Esto es así puesto que una predicción puede considerarse como una clasificación en la que interviene el tiempo, o como una búsqueda dentro del espacio de posibles estados futuros, o como un problema de minimización del tiempo empleado en esta búsqueda. En este sentido plantean el problema como un proceso iterativo de optimización donde la IXQFLyQGHDSWLWXGfunción objetivo) debe ser capaz de FDVWLJDU a las malas soluciones, y de SUHPLDU a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez. A partir de un conjunto aleatorio de soluciones tentativas que constituye la población inicial, combinan las mejores respuestas de ese conjunto para crear uno nuevo que reemplaza al anterior, y que se constituye como la generación subsecuente. Repetidamente, con cada nueva iteración, la población se va refinando consiguiendo mejores respuestas al problema, hasta converger finalmente la mayoría de los individuos en un entorno de la solución óptima. Figura 13. Diagrama para un Algoritmo genético.
Conocimiento y Minería de Datos 32 &DUJD La carga comprende los procesos asociados con la migración de los datos desde los aplicativos fuentes a las bases del :DUHKRXVH. Incluyen H[WUDFFLyQOLPSLH]DWUDQVIRUPDFLyQ \FDUJDGHGDWRV. La H[WUDFFLyQ involucra acceder a los datos de los aplicativos, por lo que es necesaria una preparación previa de los datos. Hay varias alternativas de extracción que balancean el SHUIRUPDQFH y las restricciones de tiempo y almacenamiento. Si las aplicaciones fuentes mantienen una base de datos en línea, se puede hacer una consulta que cree directamente los archivos de extracción. Debe asegurarse que no se actualicen los datos mientras se hace la extracción para no generar inconsistencias. Por otro lado el SHUIRUPDQFH puede caer si las transacciones en línea compiten con la extracción. Una solución alternativa es crear una vista, desde la cual extraer los datos. El inconveniente aquí, es el espacio de disco adicional para guardar esa copia de la base. El tiempo es un factor crucial; muchos aplicativos de extracción tienen un ciclo batch, en el cual transacciones fuera de línea son aplicadas a la base de datos. La OLPSLH]D de los datos puede ser manejada de muchas maneras. Si los errores son inherentes a los aplicativos fuentes, los datos pueden ser limpiados sistemáticamente como parte del proceso de transformación. Desgraciadamente, muchos errores ocurren porque los aplicativos fuentes sólo tienen una mínima validación de dominio, que permite la aparición de datos inválidos. La única manera de solucionarlos es corriendo rutinas pesadas de validación a nivel de fuentes. Los errores que surgen de tipeos incorrectos, son muy difíciles de detectar y corregir. La carga se completa con la WUDQVIRUPDFLyQ. Este proceso invoca reglas de conversión de valores de aplicativos locales a valores globales integrados. $OPDFHQDPLHQWR Comprende la arquitectura necesaria para integrar las vistas varias. Aunque a menudo se habla del :DUHKRXVH como si fuera un único almacén de datos, sus datos pueden estar distribuidos en múltiples bases manejadas por diferentes DBMSs. Dos tipos de gestores se ajustan bien a esta tarea: relacionales (RDBMSs) y multidimensionales (MDDBMSs). Un MDDBMS organiza los datos en un array de n dimensiones. Cada dimensión representa algún aspecto de los negocios a ser analizado. Las bases multidimensionales presentan los datos de manera que los usuarios puedan entenderlos y accederlos fácilmente. Cada área de la empresa puede necesitar que su propia visión de los negocios sea organizada como un array multidimensional, de manera de optimizar sus requerimientos específicos. Generalmente no es deseable que la misma base multidimensional soporte los requerimientos de todas las áreas de la empresa. Una RDBMS usualmente se ajusta más, al manejo de la base integrada.
Conocimiento y Minería de Datos 33 0LHQWUDVTXHODVYLVWDVPXOWLGLPHQVLRQDOHVVRQGLVHxDGDVSDUDRSWLPL]DUHODFFHVR GH XVXDULRV ILQDOHV GH FDGD iUHD OD EDVH GH GDWRV LQWHJUDGD GHO :DUHKRXVH HV GLVHxDGD SDUDRSWLPL]DUHODFFHVRGHWRGDVODViUHDV Se le llama 'DWD :DUHKRXVH a la base integrada, y Data Marts a las vistas multidimensionales de cada área. La separación entre el 'DWD :DUHKRXVH corporativo y sus Data Marts satélites, introduce la necesidad de una estrategia que coordine la distribución de los datos hacia los Data Marts. Se debe considerar la incorporación de un servidor de replicación, que entregue los datos correctos, al Data Mart correcto en el momento correcto. Los datos son almacenados en varios niveles. Los más actuales se guardan en un medio de fácil acceso en línea. Datos más viejos se pueden guardar en un medio seguro, pero más barato. Y los datos históricos pueden ser guardados en otros medios, o eliminados si ya no tienen más valor decisional. &RQVXOWDV Uno de los principales propósitos de las tecnologías de la Minería de Datos es chequear la efectividad de las reglas de empresa. Las herramientas de VLPXODFLyQ GH QHJRFLRV crean modelos para testear el impacto de cambios en el ambiente de negocios. Se pueden establecer nuevas reglas de empresa. Luego hay que realimentar los aplicativos operacionales. El arquitecto del 'DWD :DUHKRXVH, debe determinar como totalizar los datos. Existen varios enfoques viables: la sumarización puede ser hecha durante la carga, y almacenada en el 'DWD :DUHKRXVH; durante la replica a los Data Marts; o a demanda, por las herramientas de consulta y simulación. 0HWD'DWRV Los Meta Datos incluyen el dominio, las reglas de validación, la derivación y la transformación de los datos extraídos. También describen las bases de datos del :DUHKRXVH, incluyendo la reglas de distribución y control de la migración hacia los Data Marts. Los procesos que monitorizan los procesos del :DUHKRXVH (como extracción, carga, y uso) crean meta datos que son usados para determinar que tan bien se comporta el sistema. Los meta datos, deberían estar disponibles para los usuarios, para ser usados en sus análisis. Los administradores pueden manejar y proveer el acceso a través de los servicios del repositorio. (OFRQRFLPLHQWRGHORVPHWDGDWRVHVWDQHVHQFLDOFRPRHOFRQRFLPLHQWRGHORVGDWRV GHO'DWD:DUHKRXVH
Conocimiento y Minería de Datos 34 Data Marts. Introducción. Los Data Marts nacen para satisfacer las comunes y distintas necesidades de las distintas áreas (divisiones geográficas, departamentos corporativos, grupos de usuario, etc.) que componen la estructura de las grandes corporaciones, donde determinados recursos deben compartirse sin provocar conflictos mientras otros, por el contrario, deben ser exclusivos. Situaciones generadas por complejos sistemas 'DWD:DUHKRXVLQJ, de difícil implantación para los técnicos y difícil navegación para los usuarios, no han tardado en encontrar en los Data Marts una respuesta con gran efectividad. Crecimiento. Los Data Marts nacen en principio para tratar subconjuntos del 'DWD:DUHKRXVH (integrando también un número de fuentes heterogéneas), sin embargo actualmente están llegando a tener tamaños semejantes a los 'DWD:DUHKRXVH corporativos de menor escala, y ello ha generado nuevos problemas de navegación: • 6H SLHUGH SHUIRUPDQFH D PHGLGD TXH DXPHQWD HO WDPDxR GH ORV 'DWD 0DUWV. Los usuarios esperan mejor respuesta de los Data Marts, que de los 'DWD:DUHKRXVHs. • /RVXVXDULRVUHTXLHUHQDFFHVRDGDWRVGHPXFKRV'DWD0DUWV. Los datos pueden ser replicados entre los Data Marts, pero se requieren mejores soluciones. • /DVFRPSDxtDVQRSXHGHQDGPLQLVWUDUIiFLOPHQWHPXFKRV'DWD0DUWV. Mientras sólo se tiene un 'DWD:DUHKRXVH, se pueden tener gran número de Data Marts. • /DV RUJDQL]DFLRQHV WLHQHQ GLILFXOWDGHV SDUD FRQVWUXLU ORV 'DWD 0DUWV. Aunque es aceptable que la construcción de un 'DWD:DUHKRXVH lleve varios años, los Data Marts requieren un ciclo de desarrollo muy corto, para una inversión moderada. Rendimiento. A la hora de medir el rendimiento de un sistema 'DWD:DUHKRXVLQJ deben considerarse cuatro factores fundamentales: tiempo de respuesta a usuario final, datos precalculados frente a sumarización a demanda, performance en la carga y tamaño: 5HG %ULNH :DUHKRXVH (Red Brike Systems Inc.) posee índices que se adaptan de forma continua a los datos que están siendo procesados. Un nuevo tipo de -RLQ +DVK +tEULGR, maneja más eficientemente algunas situaciones como recursión en 6XEMRLQV.
Conocimiento y Minería de Datos 35 (VVEDVH (Arbol Software Corp.) es una bases de datos multidimensional (MDDB) que soporta actualización incremental, de manera que la estructura entera no necesita ser cambiada para cada actualización. 3LORW'HFLVLRQ6XSSRUW6XLWH (de Pilot Software Inc.) provee dimensiones dinámicas, que permiten que las agregaciones sean calculadas a demanda, en lugar de preagregadas y almacenadas en el cubo. Esto puede reducir signifacativamente el tamaño del cubo, al igual que el tiempo de consolidación requerido al generar el cubo. Data Marts Virtuales y Meta Vistas. Los Data Marts Virtuales son vistas, de varios Data Marts físicos o del 'DWD:DUHKRXVH corporativo, brindadas a grupos específicos de usuarios y evitando así replicas excesivas de los datos. 6DJHQW 'DWD 0DUW 6ROXWLRQ (Sagent Technology Inc.) provee los conceptos de 9LVWD %iVLFD\0HWD9LVWDV. Una Vista Básica es una representación gráfica de una base de datos que incluye tablas y consultas almacenadas. Una vez que una Vista Básica es creada, múltiples Meta Vistas pueden derivar de ella. Una Meta Vista es una representación lógica de partes de una o más Vistas Básicas. Administración de los Data Marts. A medida que el número de Data Marts va creciendo, crece también la necesidad de administración y coordinación central, que debe garantizar permanentemente:ODFRQVLVWHQFLDH LQWHJULGDG HQ ORV GDWRV FDUJD DOPDFHQDPLHQWR FRQVXOWDV UHSOLFDV YHUVLRQHV EDFNXS \ UHFXSHUDFLyQ\ORVPHWDGDWRVODVHJXULGDGGHOVLVWHPD\ODSHUIRUPDQFHJOREDO La administración debe tener un enfoque centralizado y no ser realizada entre los diferentes grupos de usuario del 'DWD:DUHKRXVLQJ. Alternativas. Existen formas muy usuales en dar a los usuarios un acceso a datos de soporte decisional: Construir un 'DWD :DUHKRXVH corporativo, que puede ser usado directamente por los usuarios, o puede alimentar Data Marts. Construir Data Marts planeados para eventualmente integrarlos en un 'DWD:DUHKRXVH. Construir la infraestructura para un 'DWD :DUHKRXVH, mientras al mismo tiempo, se construyen uno o más Data Marts para satisfacer las necesidades más inmediatas. Es la técnica más difundida.
Conocimiento y Minería de Datos 36 La inversión en tiempo y recursos para la construcción e implantación de un sistema 'DWD :DUHKRXVH corporativo, debe compararse con los beneficios y costes de tener un Data Mart funcionando en un plazo más corto de tiempo. Las ventajas de una u otra implantación pueden resumirse: 'DWD:DUHKRXVH: Los requisitos de todas las funciones de la empresa pueden ser incluidos. Las definiciones de los datos y las reglas de empresa son consistentes. La redundancia de los datos, es eliminada. 'DWD0DUWV: Menor coste y esfuerzo en una implementación inicial. Menor tiempo de desarrollo. La experiencia de los usuarios mejora el rendimiento. Las funciones de cada área pueden controlar su propio Data Mart. Aunque los Data Marts pueden proveer el éxito en solucionar muchos problemas de negocios, la proliferación de Data Marts no planeados a través de la corporación, puede llevar a inconsistencias en los datos, duplicación de éstos, y a que los usuarios no puedan acceder a todos los datos necesarios. Los vendedores están llevando a cabo algunos de estos desafíos: • Respuesta rápida, a medida que los Data Marts crecen en tamaño. • Administración de los Data Marts de toda la organización, para asegurar la consistencia en la definición de los datos, la seguridad, y la efectiva replica de los datos. • Implementación rápida y repetitiva, incluyendo el acceso a Internet, para proveer la capacidad de tomar decisiones de una manera más rápida, efectiva y menos costosa.
Conocimiento y Minería de Datos 37 5HIHUHQFLDV [1] W.J. Frawley, G. Piatetski-Shapiro, C.J. Matheus (1991). .QRZOHGJH 'LVFRYHU\ LQ 'DWDEDVHV $Q 2YHUYLHZ. Knowledge Discovery in Databases, G. Piatetsky-Shapiro, W. Frawley. AAAI-MIT Press, Menlo Park, California, p. 1-27. [2] B. DePompe (1996). 7KHUHVJROGLQGDWDEDVHVCMP Publications (Enero). [3] T. Hoffman, K.S. Nash (1995). 'DWD 0LQLQJ XQHDUWKV FXVWRPHUV Computerworld (Julio), p. 1-28. [4] L. Connor (1996). 'DWD:DUHKRXVLQJ0LQLQJIRUGDWD. CMP Publications (Febrero). [5] U.M. Fayyad, G. Piatetsky-Shapiro, P Smyth (1996). )URP'DWD0LQLQJWRNQRZOHGJH GLVFRYHU\. Advances in knowledge discovery and 'DWD0LQLQJ, (eds) U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy. AAAI Press/MIT Press, CA., p. 1-31. [6] A.J. Gómez Flechoso (1998). ,QGXFFLyQGH&RQRFLPLHQWRFRQLQFHUWLGXPEUHHQ%DVHVGH 'DWRV 5HODFLRQDOHV %RUURVDV 7HVLV 'RFWRUDO (http://www.gsi.dit.upm.es/~anto/tesis/html/). Universidad Politécnica de Madrid. [7] R.S. Michalski (1987). &RQFHSW/HDUQLQJ. Encyclopedia of Artificial Intelligence, Stuart C. Shapiro, Ed. John Wiley & Sons, p. 185-194. [8] J.R. Quinlan (1986). ,QGXFWLRQRI'HFLVLRQ7UHHV. Machine Learning, vol. 1, p. 81-106. [9] J.R. Quinlan (1987). *HQHUDWLQJ3URGXFWLRQ5XOHV)URP'HFLVLRQ7UHHV. Proceedings of IJCAI-87, Milan, Italy, p. 304-307. [10] J. R. Quinlan (1993). &3URJUDPVIRUPDFKLQHOHDUQLQJ, Morgan Kaufmann. [11] L. Breiman, J. H. Friedman, R. A. Olshen y C. J. Stone. &ODVVLILFDWLRQDQGUHJUHVVLRQ WUHHV. Wadsworth International Group. Belmont, CA, (1984). [12] R. López de Mántaras (1991). $ 'LVWDQFH%DVHG $WWULEXWH 6HOHFWLRQ 0HDVXUH IRU 'HFLVLRQ7UHH,QGXFWLRQ. Machine Learning, vol. 6(1), p. 81-92. [13] K. Murthy and S. Kasif and S. Salzberg. $ 6\VWHP IRU ,QGXFWLRQ RI 2EOLTXH 'HFLVLRQ 7UHHV. Journal of Artificial Intelligence Research, (1994). [14] J. Cendrowska (1988). 35,60$QDOJRULWKPIRULQGXFLQJPRGXODU UXOHV. Knowledgebased systems, vol. 1, p. 255-276.
Conocimiento y Minería de Datos 38 [15] T.G. Dietterich, R.S. Michalski (1984). $&RPSDUDWLYH5HYLHZRI6HOHFWHG0HWKRGVIRU /HDUQLQJIURP([DPSOHV. Machine Learning: An Artificial Intelligence Approach, R.S. Michalski, J.G. Carbonell y T.M. Mitchell, Tioga Publishing, Palo Alto, California, p. 41-81. [16] P. Clark, T. Niblett (1989). 7KH&1,QGXFWLRQ$OJRULWKP0DFKLQH/HDUQLQJ, vol. 3, p. 262-283. [17] D.W. Aha, D. Kibler, M.K. Albert (1991). ,QVWDQFH%DVHG /HDUQLQJ $OJRULWKPV. Machine Learning, vol. 6, p. 37-66. [19] R.P. Lippmann. $Q,QWURGXFWLRQWR&RPSXWLQJZLWK1HXUDO1HWV. IEEE ASSP Magazine (Abril 1987), p. 4-22. [18] D.R. Wilson and T.R. Martinez, ,PSURYHGKHWHURJHQHRXVGLVWDQFHIXQFWLRQV, Journal of Artificiall Intelligence Research 6 (1997), no. 1, 1-34. [20] J.A. Freeman, D.M. Skapura (1993). 5HGHV 1HXURQDOHV $OJRULWPRV DSOLFDFLRQHV \ WpFQLFDVGHSURSDJDFLyQ Addison-Wesley. [21] J.W. Shavulk, R.J. Mooney, G.G. Towell. 6\PEROLFDQG1HXUDO/HDUQLQJ$OJRULWKPV$Q ([SHULPHQWDO &RPSDULVRQ. Computer Sciences Technical Report 955, University of Wisconsin (August 1990), ftp://ftp.cs.wisc.edu/tech-reports/reports/90/tr955.ps.Z. [22] S. Muggleton. ,QGXFWLYH/RJLF3URJUDPPLQJ. Academic Press, San Diego (CA), 1992. [23] A. Silberschatz, M. Stonebraker, J. Ullman. 'DWDEDVH 5HVHDUFK $FKLHYHPHQWV DQG 2SSRUWXQLWLHV ,QWR WKH VW &HQWXU\. Report of an NSF Workshop on the Future of Database Systems Research (Mayo 1995), http://db.stanford.edu/pub/ullman/logii.ps.