Universidad de Manizales

Facultad de Ciencias e Ingeniería

Mate-tree: un algoritmo para la WDUHDGHFODVLÀFDFLyQEDVDGR en operadores algebraicos y primitivas SQL*1 [Mate-tree: an Algorithm for FODVVL¿FDWLRQWDVNEDVHGRQDOJHEUDLF RSHUDWRUVDQG64/SULPLWLYHV@ RICARDO TIMARÁN PEREIRA2 RECIBO: 20.02.2012 - APROBACIÓN: 20.05.2012

Resumen /DFODVL¿FDFLyQEDVDGDHQiUEROHVGHGHFLVLyQHVHOPRGHORPiV XWLOL]DGR\SRSXODUSRUVXVLPSOLFLGDG\IDFLOLGDGSDUDVXHQWHQGL PLHQWR(OFiOFXORGHOYDORUGHODPpWULFDTXHSHUPLWHVHOHFFLRQDU HQ FDGD QRGR HO DWULEXWR TXH WHQJD XQD PD\RU SRWHQFLD SDUD FODVL¿FDU VREUH HO FRQMXQWR GH YDORUHV GHO DWULEXWR FODVH HV HO SURFHVRPiVFRVWRVRGHODOJRULWPRXWLOL]DGR3DUDFDOFXODUHVWD PpWULFDQRVHQHFHVLWDQORVGDWRVVLQRODVHVWDGtVWLFDVDFHUFD GHOQ~PHURGHUHJLVWURVHQORVFXDOHVVHFRPELQDQORVDWULEXWRV FRQGLFLyQFRQHODWULEXWRFODVH(QWUHORVDOJRULWPRVGHFODVL¿FDFLyQ SRUiUEROHVGHGHFLVLyQVHFXHQWDQ,'&635,17\6/,4 6LQHPEDUJRQLQJXQRGHHVWRVDOJRULWPRVVHEDVDQHQRSHUD GRUHV DOJHEUDLFRV UHODFLRQDOHV \ VH LPSOHPHQWD FRQ SULPLWLYDV 64/(QHVWHDUWtFXORVHSUHVHQWD0DWHWUHHXQDOJRULWPRSDUDOD * 

1

2

Modelo para citación de este Reporte de Caso: 7,0$5È13(5(,5$5LFDUGR 0DWHWUHHXQDOJRULWPRSDUDODWDUHDGHFODVL¿FDFLyQ basado en Operadores algebraicos y Primitivas SQL. En: Ventana Informática. No. 26 (ene. – jun., 2012). Manizales (Colombia): Facultad de Ciencias e Ingeniería, Universidad de Manizales. p. 61-76. ISSN: 0123-9678 Artículo proveniente del proyecto de investigación 3RVWJUH64/.''8Q6LVWHPDGH'HVFX EULPLHQWRGH&RQRFLPLHQWRIXHUWHPHQWHDFRSODGRFRQHO6*%'3RVWJUH64/, ejecutado en el periodo IHEUHUR±IHEUHUR, e inscrito en el grupo de investigación *5,$6 de la 8QLYHUVLGDGGH1DULxR. Doctor en Ingeniería, Master of Science en Ingeniería, Especialista en Multimedia e Ingeniero de Sistemas y Computación. Director grupo de investigación GRIAS, Profesor Asociado, DeSDUWDPHQWRGH6LVWHPDV)DFXOWDGGH,QJHQLHUtD8QLYHUVLGDGGH1DULxR3DVWR&RORPELD  Correo electrónico: [email protected] Nº 26 - Universidad de Manizales, enero-junio/2012 - pp 61-76

61

Nº 26 - enero - junio / 2012

WDUHDGHPLQHUtDGHGDWRVFODVL¿FDFLyQEDVDGRHQORVRSHUDGRUHV DOJHEUDLFRVUHODFLRQDOHV0DWH(QWUR*DLQ\'HVFULEH&ODVVL¿HU LPSOHPHQWDGRVHQODFOiXVXOD64/6HOHFWFRQODVSULPLWLYDV64/ 0DWHE\(QWUR *DLQ \'HVFULEH&ODVVL¿FDWLRQ5XOHVORVFXDOHV IDFLOLWDQHOFiOFXORGH*DQDQFLDGH,QIRUPDFLyQODFRQVWUXFFLyQ GHOiUEROGHGHFLVLyQ\HODFRSODPLHQWRIXHUWHGHHVWHDOJRULWPR FRQXQ6*%' Palabras Claves:ÈUEROHVGH'HFLVLyQ0LQHUtDGH'DWRV2SHUDGRUHV $OJHEUDLFRV5HODFLRQDOHV3ULPLWLYDV64/7DUHDGH&ODVL¿FDFLyQ

Abstract 'HFLVLRQWUHHFODVVL¿FDWLRQLVWKHPRVWXVHGDQGSRSXODUPRGHOEH FDXVHLWLVVLPSOHDQGHDV\WRXQGHUVWDQG7KHFDOFXODWLRQRIWKHYDOXH RIWKHPHDVXUHWKDWDOORZVVHOHFWLQJLQHDFKQRGHWKHDWWULEXWHZLWK WKHKLJKHVWSRZHUWRFODVVLI\RQWKHVHWRIYDOXHVRIWKHFODVVDWWULEXWH LVWKHPRVWH[SHQVLYHSURFHVVLQWKHXVHGDOJRULWKP7RFRPSXWHWKLV PHDVXUHWKHGDWDDUHQRWQHHGHGEXWWKHVWDWLVWLFVDERXWWKHQXPEHU RIUHFRUGVLQZKLFKFRPELQHWKHWHVWDWWULEXWHVZLWKWKHFODVVDWWULEXWH $PRQJWKHFODVVL¿FDWLRQDOJRULWKPVE\GHFLVLRQWUHHVDUH,'& 635,17DQG6/,4+RZHYHUQRQHRIWKHVHDOJRULWKPVDUHEDVHGRQ UHODWLRQDODOJHEUDLFRSHUDWRUVDQGDUHLPSOHPHQWHGZLWK64/SULPLWLYHV ,QWKLVSDSHU0DWHWUHHDQDOJRULWKPIRUWKHFODVVL¿FDWLRQGDWDPLQLQJ WDVNEDVHGRQWKHUHODWLRQDODOJHEUDLFRSHUDWRUV0DWH(QWUR*DLQDQG 'HVFULEH&ODVVL¿HULVSUHVHQWHG7KH\ZHUHLPSOHPHQWHGLQWKH64/ 6HOHFWFODXVHZLWK64/SULPLWLYHV0DWHE\(QWUR *DLQ \'HVFULEH &ODVVL¿FDWLRQ5XOHV7KH\IDFLOLWDWHWKHFDOFXODWLRQRIWKH,QIRUPDWLRQ *DLQWKHFRQVWUXFWLRQRIWKHGHFLVLRQWUHHDQGWKHWLJKWFRXSOHGRIWKLV DOJRULWKPZLWKD'%06 .H\ZRUGV'HFLVLRQ7UHHV'DWD0LQLQJ5HODWLRQDO$OJHEUDLF2SHUDWRUV 64/3ULPLWLYHV&ODVVL¿FDWLRQ7DVN

Introducción El proceso de extracción de conocimiento a partir de grandes volúmenes de datos tiene como objetivo descubrir patrones que deben ser válidos, novedosos, interesantes y comprensibles para el usuario (Chen, Han & Yu (1996), Fayyad, Piatetsky-Shapiro & Smyth (1996a), Fayyad, Piatetsky-Shapiro & Smyth (1996b), Cabena et al. (1997)). La minería de datos es la etapa más importante de este proceso (Imielnski & Mannila (1996) y Hernández, Ramírez & Ferri (2005)). 62

Universidad de Manizales

Facultad de Ciencias e Ingeniería

La minería de datos consta de diferentes tareas, cada una de las cuales puede considerarse como un tipo de problema a ser resuelto por un DOJRULWPR GH PLQHUtD GH GDWRV D¿UPDQ$GDPR   \ +HUQiQGH] 5DPtUH] )HUUL GRQGHODWDUHDGHFODVL¿FDFLyQSRUiUEROHVGH decisión es una de ellas. Se han propuesto varias métricas para este proceso. Para Wang, Iyer & Scott (1998), el cálculo del valor de la métrica que permite seleccionar, en cada nodo, el atributo que tenga una mayor potencia para FODVL¿FDUVREUHHOFRQMXQWRGHYDORUHVGHODWULEXWRFODVHHVODSDUWHPiV costosa del algoritmo utilizado. Los algoritmos ID3 (Quinlan, 1986) y C4.5 (Quinlan, 1993) utilizan como métrica, para seleccionar el atributo candidato en cada nodo del árbol, la reducción de la entropía denominada *DQDQFLDGH,QIRUPDFLyQ, mientras que SLIQ (Metha, Agrawal & Rissanen, 1996) y SPRINT (Shafer, Agrawal & Metha, 1996), usan el íQGLFH*LQL. Para el cálculo de estas métricas, no se necesitan los datos en sí, sino las estadísticas acerca del número de registros en los cuales se combinan los atributos condición con el atributo clase. Un operador DOJHEUDLFRUHODFLRQDOSDUDFODVL¿FDFLyQEDVDGRHQiUEROHVGHGHFLVLyQ debe facilitar estas combinaciones, que conjuntamente con operadores agregados, permita el cálculo de estas métricas. En este artículo se propone 0DWHWUHH, un algoritmo para la tarea de PLQHUtDGHGDWRVFODVL¿FDFLyQEDVDGRHQHORSHUDGRUDOJHEUDLFRUHODcional 0DWH que conjuntamente con los operadores agregados (QWUR y *DLQ facilitan el cálculo de la Ganancia de Información y con el operador algebraico relacional 'HVFULEH&ODVVL¿HU, la construcción del árbol de decisión. La implementación en el lenguaje SQL del operador relacional 0DWH dentro de la cláusula 6HOHFW, como la primitiva 0DWHE\, de (QWUR y *DLQ como las funciones agregadas SQL (QWUR  y *DLQ y de 'HVFULEH &ODVVL¿HU como el operador SQL 'HVFULEH&ODVVL¿FDWLRQ5XOHV, facilita la integración de 0DWHWUHH al interior de un Sistema Gestor de Base GH'DWRV6*%' DFRSODQGRODWDUHDGH&ODVL¿FDFLyQGHXQDPDQHUD fuerte, propuesta por Timarán (2001). Esta es una de las ventajas del algoritmo con respecto a los demás. Debido a que el algoritmo es ejecutado conjuntamente con los datos en el SGBD, su ventaja potencial es que resuelve los problemas de escalabilidad y rendimiento de las implementaciones débilmente acopladas. Al implementarse 0DWHWUHH en el lenguaje SQL permite la realización de consultas de minería de datos DGKRF y el desarrollo de aplicaciones en esta área. El artículo está organizado en secciones: en la primera se presentan DOJXQRVFRQFHSWRVDFHUFDGHODWDUHDGHPLQHUtDGHGDWRVFODVL¿FDFLyQ HQODVHFFLyQVHGH¿QHQORVRSHUDGRUHVGHOiOJHEUDUHODFLRQDOTXH 63

Nº 26 - enero - junio / 2012

forman parte del algoritmo 0DWHWUHH; en la sección 3, se presentan las primitivas SQL con las cuales se implementa el algoritmo 0DWHWUHHHn la sección 4, se describe el algoritmo 0DWHWUHH y su implementación en SQL 0DWHWUHH; y en la sección 5 se muestran las pruebas y evaluación GHGHVHPSHxRGHORVDOJRULWPRV0DWHWUHH, & y 6/,4. Finalmente se presentan las conclusiones y trabajos futuros.

1. Conceptos preliminares 7DUHDGHFODVL¿FDFLyQ /DFODVL¿FDFLyQGHGDWRVHVHOSURFHVRSRUPHGLRGHOFXDOVHHQFXHQWUDQ propiedades comunes entre un conjunto de objetos de una base de datos \VHORVFODVL¿FDHQGLIHUHQWHVFODVHVGHDFXHUGRDOPRGHORDSOLFDGR Este proceso de aprendizaje supervisado, se realiza en dos pasos: - En el primer paso, se construye un modelo en el cual, cada tupla, de un conjunto de tuplas de la base de datos, tiene una clase conocida, determinada por uno de los atributos de la base de datos, llamado atributo clase, según Witten & Frank (2000). El conjunto de tuplas que sirve para construir el modelo se denomina conjunto de entrenamiento, siendo, de acuerdo con Han & Kamber (2001), cada tupla de este conjunto un ejemplo de entrenamiento. (QHOVHJXQGRSDVRVHXVDHOPRGHORSDUDFODVL¿FDU,QLFLDOPHQWHVH estima la exactitud del modelo utilizando un conjunto de tuplas de la base de datos, generalmente diferente al de entrenamiento, cuya clase HVFRQRFLGDGHQRPLQDGRFRQMXQWRGHSUXHEDVHJ~QD¿UPDQ:LWWHQ  Frank (2000). A cada tupla de este conjunto, consideran Han & Kamber (2001), se le denomina ejemplo de prueba.

&ODVL¿FDFLyQSRUiUEROHVGHGHFLVLyQ /DFODVL¿FDFLyQSRUiUEROHVGHGHFLVLyQHVSUREDEOHPHQWHHOPRGHOR más utilizado y popular por su simplicidad y facilidad para su entendimiento, de acuerdo con Han & Kamber (2001) y Sattler & Dunemann (2001). El conocimiento obtenido en el proceso de aprendizaje se representa mediante un árbol en el cual cada nodo interior contiene una pregunta sobre un atributo concreto (con un hijo por cada posible resSXHVWD \FDGDKRMDGHOiUEROVHUH¿HUHDXQDGHFLVLyQXQDFODVL¿FDFLyQ  Durante la etapa de construcción del árbol, en forma recursiva, cada conjunto de datos se divide en subconjuntos de acuerdo a un criterio de SDUWLFLRQDPLHQWRFRQHO¿QGHHVFRJHUHODWULEXWRTXHPHMRUVHSDUHORV ejemplos restantes en clases individuales. Seleccionar el mejor punto de particionamiento es la parte de la construcción del árbol que mayor tiempo consume (Sattler & Dunemann, 2001). 64

Universidad de Manizales

Facultad de Ciencias e Ingeniería

2. Operadores algebraicos UHODFLRQDOHVSDUDFODVL¿FDFLyQ 3DUDORJUDUH¿FLHQFLDHQODVRSHUDFLRQHVGHPLQHUtDGHGDWRVXQQXHYR operador algebraico debe facilitar los procesos de minería de datos computacionalmente más costosos. Los operadores algebraicos propuestos por Timarán & Millán (2006), con los que se extiende el álgebra relacional facilitan estos procesos en el descubrimiento de reglas de FODVL¿FDFLyQ

2SHUDGRU0DWHP El operador 0DWH genera, por cada una de las tuplas de una relación, todas los posibles combinaciones de los valores no nulos de los atributos de una lista de atributos denominados Atributos Condición, con el valor no nulo del Atributo Clase. 0DWH realiza estas combinaciones, en una sola pasada sobre la tabla de entrenamiento. Formalmente, sea$ ^$$Q`el conjunto de atributos de la relación 5de gradoQy cardinalidadP/&  $/& Ila lista de atributos condición a combinar yQ¶el número de atributos de/&_ /&_= Q¶, Q¶ WHERE 67

Nº 26 - enero - junio / 2012

MATE BY WITH GROUP BY : := , : :=, : := : :=, ::=

)XQFLyQDJUHJDGD64/(QWUR Esta función agregada SQL implementa el operador algebraico agregado (QWURen la cláusula SQL SELECT. SQL (QWUR permite calcular, conjuntamente con la primitiva 0DWH%\, la entropía de una tabla con respecto a cada una de las combinaciones de los DWULEXWRVFRQGLFLyQ con el DWULEXWR FODVH. SQL (QWUR se debe ejecutar conjuntamente con la función agregada &RXQW . La sintaxis de SQL (QWUR en la cláusula SELECT es la siguiente: SELECT WHERE MATE BY WITH GROUP BY , &RXQW , (QWUR *DLQ  [INTO ] FROM 68

Universidad de Manizales

Facultad de Ciencias e Ingeniería

(MHPSOR Sea la tabla SINTOMAS (SID, D_MUSCULAR, TEMPERATURA, GRIPA). Calcular la entropía y ganancia de información de las diferentes combinaciones de los DWULEXWRVGBPXVFXODU, WHP SHUDWXUD con el atributo JULSDy almacenar el resultado en la tabla JDQVLQWRPDV: SELECT GBPXVFXODUWHPSHUDWXUDJULSDFRXQW (QWUR *DLQ INTO JDQVLQWRPDV FROM VLQWRPDV MATE BY GBPXVFXODUWHPSHUWXUD WITH JULSD GROUP BY GBPXVFXODUWHPSHUWXUDJULSD

&OiXVXOD64/'HVFULEH&ODVVL¿FDWLRQ5XOHV 'HVFULEH &ODVVLILFDWLRQ 5XOHV implementa el operador algebraico 'HVFULEH &ODVVL¿HU en una nueva cláusula SQL. Este operador SQL construye el árbol de GHFLVLyQ\JHQHUDODVUHJODVGHFODVL¿FDFLyQ(O operador 'HVFULEH &ODVVL¿FDWLRQ 5XOHV permite la construcción del iUEROGHGHFLVLyQGHPDQHUDXQL¿FDGDFRQHOFiOFXORGHODPpWULFDGH SDUWLFLRQDPLHQWR con la primitiva 0DWH%\y las funciones agregadas (QWUR y *DLQ en una sola instrucción SQL o en forma separada con sentencias SQL independientes, para luego generar las reglas. 'HVFULEH &ODVVL¿FDWLRQ5XOHV tiene la siguiente sintaxis: DESCRIBE CLASSIFICATION RULES [INTO ] FROM USING [DO ] ::= ::=

4. Mate-tree, un algoritmo para FODVL¿FDFLyQSRUiUEROHVGHGHFLVLyQ (ODOJRULWPRGHFODVL¿FDFLyQ 0DWHWUHH se basa en los operadores algebraicos relacionales 0DWH, (QWUR, *DLQ y 'HVFULEH &ODVVL¿HU propuestos por Timarán & Millán (2006) y Timarán (2007). 0DWH realiza las combinaciones de los atributos condición con el atributo clase, (QWURy *DLQcalculan las métricas de Entropía y Ganancia de información y 'HVFULEH&ODVVL¿HU facilita la construcción del árbol de 69

Nº 26 - enero - junio / 2012

decisión. Este hecho facilita su integración al interior de cualquier 6*%'DFRSODQGRODWDUHDGH&ODVL¿FDFLyQGHXQDPDQHUDIXHUWH\ favorece la aplicación de técnicas de optimización de consultas para mejorar su rendimiento.

4.1 Descripción del algoritmo Mate-tree En el primer paso el algoritmo calcula la (QWURStD del de la relación 5 con respecto al DWULEXWR FODVH. En el subsiguiente paso, se aplica el operador 0DWHFRQHO¿QGHJHQHUDUWRGDVODVSRVLEOHVFRPELQDFLRQHV de los DWULEXWRVFRQGLFLyQ con el DWULEXWRFODVH Se calcula el número de ocurrencias de cada combinación y a la relación resultante 5, se aplica la funcion agregada (QWUR que calcula para cada combinación de DWULEXWRVFRQGLFLyQ y FODVH la entropía de la relación R1 con respecto a estos atributos. Posteriormente, se calcula con la función agregada *DLQ , la Ganancia de Información obtenida por el particionamiento de la relación R1 por las diferentes combinaciones de DWULEXWRVFRQGLFLyQ y FODVH. Finalmente, con la relación resultante R2, el operador GHVFUL EHFODVVL¿HU construye el árbol de decisión. El algoritmo 0DWHWUHH se PXHVWUDHQOD¿JXUDD

4.2 Implementación del algoritmo Matetree HQHOOHQJXDMH64/ El algoritmo 0DWHWUHH se implementa en el lenguaje SQL, utilizando la primitiva SQL 0DWH%\el operador SQL 'HVFULEH&ODVVL¿FDWLRQ5XOHVy la funciones agregadas (QWUR y *DLQ GH¿QLGRVHQ7LPDUiQ 0LOOiQ (2006) y Timarán (2007). La implementación del algoritmo 0DWHWUHH HQHOOHQJXDMH64/VHPXHVWUDHQOD¿JXUDE (MHPSOR  Sea la tabla CLIENTES (EDAD, INGRESOS, ES_ESTUDIANTE, MANEJOCREDITO, COMPRAEQUIPO) cuyos valores han sido GLVFUHWL]DGRV. Utilizando el algoritmo SQL 0DWHWUHH, construir el iUEROGHGHFLVLyQ\JHQHUDUODVUHJODVGHFODVL¿FDFLyQDOPDFHQiQGRODV en la tabla UHJODV&ODVL¿FDFLyQ En este caso, el algoritmo SQL 0DWHWUHHa través del operador 'HVFULEH &ODVVL¿FDWLRQ5XOHV construye el árbol de decisión en la tabla QRGRVDUERO a partir de la tabla PpWULFDVSDUWLFLyQdonde se encuentran almacenados los valores de las métricas de (QWURStDy *DQDQFLDGH,QIRUPDFLyQ de todas las combinaciones de los atributos condición HGDGLQJUHVRV DVBHVWXGLDQWHPDQHMRFUHGLWRcon el atributo clase FRPSUDHTXLSR. Finalmente, de la tabla QRGRVDUEROVHJHQHUDODVUHJODVGHFODVL¿FDFLyQ almacenándolas en la tabla UHJODV&ODVL¿FDFLyQ. El resultado se muestra HQOD¿JXUDF

70

Universidad de Manizales

Facultad de Ciencias e Ingeniería

)LJXUD$OJRULWPR0DWHWUHH

5. Evaluación de desempeño del algoritmo Mate-tree Para analizar el rendimiento del algoritmo 0DWHWUHH, se realizaron varias pruebas en un equipo Intel Pentium IVF de 64 bits a 3,0 Ghz, memoria RAM de 2Gb, disco duro serial ata de 160 Gb con sistema operativo )HGRUDFRUH. Se utilizaron los siguientes conjuntos de datos: - =RRGDWD del repositorio de la UCI (5 Kb) con 101 registros y 18 atributos con información de 101 animales, - 7LWDQLFGDWD del repositorio de la UCI (120 Kb) con 2201 registros y 4 atributos, con información correspondiente a 2.201 pasajeros de este crucero, - 6LVEHQGDW (1.466 Kb) con 15.000 registros y 10 atributos, perteQHFLHQWHVDD¿OLDGRVGHOUpJLPHQVXEVLGLDGRGHVDOXGGHOD ciudad de Pasto (Colombia), - 8GHQDUGDW (1.366 Kb) con 20.328 registros y 26 atributos, con información correspondiente a la parte académica y social de 20.328 HVWXGLDQWHVGHOD8QLYHUVLGDGGH1DULxR&RORPELD /RVDOJRULWPRV utilizados para las pruebas fueron 0DWHWUHH, C4.5 y SLIQ. Para realizar las pruebas con los algoritmos 0DWHWUHH, C4.5 y SLIQ, se implementaron en la herramienta 0DWH.''XQFODVL¿FDGRUPHGLDQD71

Nº 26 - enero - junio / 2012

mente acoplado con el SGBD PostgreSQL desarrollado en el laboraWRULRGH.''GHOD8QLYHUVLGDGGH1DULxR&RORPELD FRPRIXQFLRQHV GH¿QLGDVSRUHOXVXDULR)'8 HQHOOHQJXDMHSURFHGXUDO PL/PgSQL.

4.1 Pruebas 6HGLVHxDURQWUHVWLSRVGHSUXHEDSDUDHYDOXDUHOFRPSRUWDPLHQWRGH los algoritmos 0DWHWUHH&\6/,4en diferentes condiciones. En la primera prueba se mantiene constante el número de atributos y se incrementa el número de registros. Para esta prueba se utilizaron los conjuntos de datos 7LWDQLFGDWy 6LVEHQGDWEl conjunto de datos 7LWDQLFGDWDse duplicó hasta obtener el número de registros que se requerían. Los resultados se muestran en la Figura 2a, estando el tiempo expresado en segundos. Con el conjunto de datos real 6LVEHQGDW se seleccionaron aleatoriamente seis subconjuntos de datos con diferente número de instancias y se midió el costo computacional de los algoritmos. Los resultados se muestran en la Figura 2b. En la segunda prueba se mantiene constante el número de registros y se varía el número de atributos. Esta prueba se realizó con el conjunto de datos XGHQDUGDW Los resultados de esta prueba se muestran en la Figura 2c. Teniendo en cuenta que el operador algebraico 0DWH realiza todas las combinaciones entre los DWULEXWRVFRQGLFLyQ y el DWULEXWRFODVH, es el proceso más costoso del algoritmo 0DWHWUHHVHGLVHxyODWHUFHUD SUXHEDFRQHO¿QGHPHGLUHOFRPSRUWDPLHQWRGHORSHUDGRU 0DWH en dos diferentes arquitecturas: mediana y fuertemente acoplada con el SGBD PostgreSQL. Por esta razón, el operador algebraico 0DWH, conjuntamente con la primitiva SQL 0DWHE\se implementaron en el interior del motor de PostgreSQL (Momjian (2001) y Geschwinde & Schoning (2002)) en una arquitectura fuertemente acoplada (Timarán, 2001) y como una FDU en PL/PgSQL en una arquitectura medianamente acoplada (Timarán, 2001). Para esta prueba se utilizó el conjunto de datos ]RRGDWD, el cual se duplicó hasta obtener un máximo de 40.400 transacciones. Los resultados de esta prueba se muestran en la Figura 3.

4.2 Análisis de resultados Analizando los resultados de las dos primeras pruebas se puede obserYDUTXHHOGHVHPSHxRGHODOJRULWPR0DWHWUHH es mejor en conjuntos de datos con pocos atributos, como sucede con el conjunto de datos 7LWDQLF GDWD, pero su rendimiento empieza a degradarse cuando el número de atributos aumenta, como se puede deducir de la segunda prueba. En general, 0DWHWUHH y C4.5 tienen un comportamiento similar, pues sus WLHPSRVGHHMHFXFLyQVRQVHPHMDQWHVORTXHQRVHSXHGHD¿UPDUGHO algoritmo SLIQ, que es muy costoso. 72

Universidad de Manizales

Facultad de Ciencias e Ingeniería

)LJXUD5HVXOWDGRGHODVSUXHEDVGHUHQGLPLHQWR\FRPSRUWDPLHQWR GHORVDOJRULWPRVFRQ7LWDQLFGDWD6LVEHQGDW\8GHQDUGDW

)LJXUD5HVXOWDGR\FRPSRUWDPLHQWRGHORSHUDGRU0DWHHQGLIHUHQWHVDUTXLWHFWXUDV

73

Nº 26 - enero - junio / 2012

&RPRVHSXHGHREVHUYDUHQOD¿JXUDHOUHQGLPLHQWRGHORSHUDGRU 0DWH es mejor en su versión fuertemente acoplada, cuando el número de atributos aumenta, debido al número de combinaciones que se deben realizar. Sin embargo, 0DWH, en las dos arquitecturas tiende a presentar un comportamiento exponencial. Por esta razón, en el algoritmo 0DWHWUHH se debe contemplar una pre-poda que evite combinaciones innecesarias.

&RQFOXVLRQHV\WUDEDMRVIXWXURV 0DWHWUHHHVXQDOJRULWPRSDUDGHVFXEULUUHJODVGHFODVL¿FDFLyQEDVDGR en los operadores algebraicos relacionales 0DWH, (QWUR, *DLQ y 'HVFULEH &ODVVL¿HUTXHORGLIHUHQFLDGHOUHVWRGHDOJRULWPRVGH&ODVL¿FDFLyQ(VWH hecho facilita la integración fuerte de este algoritmo con un SGBD, al extender el lenguaje SQL con las primitivas y funciones agregadas 0DWH %\, (QWUR , *DLQ y 'HVFULEH&ODVVL¿FDWLRQ5XOHV que implementan fácilmente a 0DWHWUHH, generando rápidamente, a través de consultas DGKRFUHJODVGHFODVL¿FDFLyQ Los resultado de las pruebas con el algoritmo 0DWH7UHH, muestran que los tiempos de ejecución están directamente relacionados con el número de atributos y las distintas categorías del atributo clase. El tiempo de HMHFXFLyQGHODOJRULWPRFUHFHVLJQL¿FDWLYDPHQWHGHDFXHUGRDOJUDGR\ cardinalidad del conjunto de datos. Las resultados con las pruebas realizadas con la implementación del operador algebraico 0DWH en una arquitectura medianamente y fuertePHQWHDFRSODGDFRQHO6*%'3RVWJUH64/GHPRVWUDURQODH¿FLHQFLD de esta segunda arquitectura, debido a que 0DWH hace uso de todas las ventajas de estar integrado al motor de PostgreSQL, como el de ejecutarse en el mismo espacio de direccionamiento que los datos, ser un objeto de la base de datos, poder ser optimizable, entre otras. Como trabajos futuros están, el de contemplar dentro del algoritmo 0DWHWUHH un sistema de prepoda, que evite que el operador 0DWH haga combinaciones de los atributos FRQGLFLyQ con el atributo FODVH que no intervienen en la construcción del árbol de decisión. Integrar el algoritmo 0DWHWUHH al interior del motor de PostgreSQL, acoplando fuertemente todos sus operadores algebraicos y realizar pruebas de GHVHPSHxRHQHVWDDUTXLWHFWXUD

74

Universidad de Manizales

Facultad de Ciencias e Ingeniería

Bibliografía ADAMO, J.M. (2001). Data Mining for Association Rules and Sequential Patterns: Sequential and Parallel Algorithms. New York (USA): Springer-Verlag. 253 p. ISBN: 0-387-95048-6. CABENA, P.; HADJINIAN, P.; STADLER, R.; VERHEES, J. & ZANASI, A. (1997). Discovering Data Mining from Concept to Implementation. New York (USA): Prentice Hall. 224 p. ISBN: 978-0137439805. CHEN, M.; HAN, J. & YU, P. (1996). Data Mining: An Overview from Database Perspective. In: Journal IEEE Transactions on Knowledge Data Engineering, Vol. 8, No. 6 (Dec.). New Jersey (USA): IEEE Educational Activities Department Piscataway. p. 866-883. ISSN: 1041-4347. FAYYAD, U.; PIATETSKY-SHAPIRO, G. & SMYTH, P. (1996a). From Data Mining to Knowledge Discovery: An Overview. In: Advances in Knowledge Discovery and Data Mining. Menlo Park (USA): AAAI Pres/The MIT Press. 595 p. ISBN: 0-262-56097-6. FAYYAD, U.; PIATETSKY-SHAPIRO, G. & SMYTH, P. (1996b). The KDD Process for Extracting Useful Knowledge from Volumes of Data. In: Communications of the ACM, Vol. 39, No 11 (Nov.). New York, NY (USA): ACM. p. 27-34. ISSN: 0001-0782. GESCHWINDE, E. & SCHONING, H.J. (2002). PostgreSQL: Developer’s Handbook. Indianapolis (Indiana, USA): Sams Publishing. 751 p. ISBN: 0-672-32260-9. HAN, J. y KAMBER, M. (2001). Data Mining: Concepts and Techniques. San Diego (USA): Morgan Kaufmann Publishers. 745 p. ISBN: 978-1-55860-901-3. HERNÁNDEZ, O.J.; RAMÍREZ, Q.M. & FERRI, R.C. (2005). Introducción a la Minería de Datos. 0DGULG(VSDxD 3HDUVRQ3UHQWLFH+DOOS,6%1 IMIELNSKI, T. & MANNILA, H. (1996). A Database Perspective on Knowledge Discovery. In: Communications of the ACM. Vol. 39, No. 11 (Nov.): New York (USA): ACM. p. 58-64. ISSN: 0001-0782. 0(7+$0$*5$:$/5 5,66$1(1- 6/,4$)DVW6FDODEOH&ODVVL¿HUIRU'DWD Mining. In: The 5th International Conference on Extending Database Technology EDBT, (2529/03/1996), Avignon (France): Advances in Database Technology. Proceedings Lecture Notes in Computer Science Springer. p. 18-32. ISBN: 3-540-61057-X. MOMJIAN, B. (2001). PostgreSQL: Introduction and Concepts. New York (USA): Addison-Wesley. 455 p. ISBN: 0-201-70331-9. QUINLAN, J.R. (1986). Induction of Decision Trees. In: Machine Learning Journal, Vol. 1, No. 1 (Jan.). Boston (USA): Kluwer Academic Publishers. p. 81-106. QUINLAN, J.R. (1993). C4.5: Programs for Machine Learning. San Francisco, CA (USA): Morgan Kaufmann Publishers. 299 p. ISBN: 1-55860-238-0. 6$77/(5. '81(0$112 64/'DWDEDVH3ULPLWLYHVIRU'HFLVLRQ7UHH&ODVVL¿HUV,Q The 10th ACM International Conference on Information and Knowledge Management - CIKM, (5-10/11/2001), Atlanta, Georgia (USA): ACM. Proceedings, p. 379-386. ISBN: 1-58113-436-3. 6+$)(5-$*5$:$/5 0(7+$0 635,17$6FDODEOH3DUDOOHO&ODVVL¿HUIRU Data Mining. In: The 22th International Conference on Very Large Data Bases – VLDB, (36/09/1996), Mumbai, Bombay (India): ACM. Proceedings Morgan Kaufmann, p. 544-555. ISBN: 1-55860-382-4 TIMARÁN, R. (2001). Arquitecturas de Integración del Proceso de Descubrimiento de Conocimiento con Sistemas de Gestión de Bases de Datos: un Estado del Arte. En: Revista Ingeniería y Competitividad. Vol. 3, No. 2 (dic.). Cali (Colombia): Universidad del Valle. ISSN: 0123-3033. TIMARÁN, R. & MILLÁN, M. (2006). New Algebraic Operators and SQL Primitives for Mining &ODVVL¿FDWLRQ5XOHV,Q7KH6HFRQG,$67(',QWHUQDWLRQDO&RQIHUHQFHRQ&RPSXWDWLRQDO Intelligence - CI 2006, (20-22/11/2006), San Francisco, CA (USA): The International Association of Science and Technology for Development. Proceedings, p. 59 - 63. ISBN: 0-88986-603-1. TIMARÁN, R. (2007). Extensión del Lenguaje SQL con Nuevas Primitivas para el Descubrimiento GH5HJODVGH&ODVL¿FDFLyQ(Q9,-RUQDGDV,EHURDPHULFDQDVGH,QJHQLHUtDGHO6RIWZDUH e Ingeniería del Conocimiento - JIISIC, (31/01-02/02/2007), Lima (Perú): Facultad de &LHQFLDVH,QJHQLHUtD3RQWL¿FLD8QLYHUVLGDG&DWyOLFDGHO3HU~Memorias, p. 19-26. ISBN: 978-9972-2885-1-7.

75

Nº 26 - enero - junio / 2012 :$1*0,