INSTITUTO TECNOLOGICO Y DE ESTUDIOS SUPERIORES DE MONTIERREY

CAMPUS CIUDAD DE MEXICO

IVIAESTRIA EN CIENCIAS COMPUTACIONALES

Muestreo progresivo: MSC

ASESOR:

Dr. Eduardo Morales

AUTOR:

lng. en Sistemas Computacionales Alfonso Estrada Díaz

Sometido al programa de graduados en informática y computación en cumplimiento con los requerimientos para obtener el grado

TECNOLÓGICO DE MONTERREY e

BIBLIOTECA Mayo/ 2004

iiMi@

Desc11brimie11ro de C'onocimienro en Bases de Daros

Resumen

En la actualidad es indispensable el análisis progresivo e incremental de datos (muestreo

progresivo) debido a los grandes volúmenes de información que se tienen; esto con la

finalidad de reducir costos computacionales en la aplicación del proceso de

descubrimiento de conocimiento en bases de datos. El muestreo progresivo de datos

forma parte del proceso inicial de descubrimiento de conocimiento, y constituye, en

general, una mejor opción que el análisis del total de información . Se busca procesar un

subconjunto de datos, cuya medida de calidad del análisis se asemeje a la obtenida a

partir del total de información. La adecuada selección de elatos permitirá que la

extracción de conocimiento genere eficientemente buenos re!iUltados. En la tesis se

diseñó un novedoso algoritmo de muestreo progresivo, el cual toma en cuenta los tres

puntos fundamentales que intervienen en el muestreo progresivo: tamaño de muestra

inicial, esquema de muestreo, y detección de la convergencia . Es1a técnica de muestreo

progresivo demostró, según las pruebas realizadas, ser consist,~ntemente superior al

muestreo progresivo aritmético y geométrico.

2

Desc11bri111ie1110 d<' Co11oci111ie11/0 ('11 Bases de Dalos

Índice

Capítulo 1. Introducción

1. 1. Objetivo 1.2. Retos computacionales 1.3. Contenido del documento

Capítulo 2. Antecedentes y marco teórico

2.1. Descubrimiento de conocimiento en bases de datos 2.1.1. Las fases del proceso de KDD 2.1.2. Tareas y técnicas en KDD

2.2. Muestreo Progresivo 2.2.1. Programación de muestreo 2.2.2. Detección de la convergencia

2.3. Muestreo adaptativo

Capítulo 3. NSC: Un algoritmo de muestreo progresivo

3.1. Descripción General 3.2. Selección de tamaño de muestra inicial 3.3 Esquema de muestreo 3.4. Detección de la convergencia por número de iteraciones y medida de precisión 3.5. Análisis del algoritmo

Capítulo 4. Pruebas y resultados obtenidos

4. 1. Datos empleados 4.2. Descripción general del proceso de pruebas 4.3. Selección de tamai'io de muestra inicial 4.4. Esquema de muestreo 4.5. Detección de la convergencia por número de iteraciones y medida de precisión 4.6. Comparación entre métodos

4.6.1. Precisión y tamaño de muestra 4.6.2. Tiempo de ejecución

Capítulo 5. Conclusiones

5. 1 Trabajo futuro

Fuentes de información

Anexos

A. Código fuente principal B. Base de datos de transacciones empleada

4

8 8 9

10

10 14 16 21 24 27 29

32

33 35 38 39

46

48

.......................... 49 51 52 54 55

56 57 60

63

65

67

71 78

3

DC'sc11bri111iC'11to de Co11ocimie1110 en BasC's de Datos

Capítulo 1. Introducción

En las últimas déccidas, el poder de almacenamiento y proceso de diversos

dispositivos de cómputo se ha incrementado considerablemente. Por otro lado la

velocidad de análisis de la información es cada vez mayor [ l]. Esto nos brinda

grandes oportunidodes para procesar y explotar datos, y convertirlos en

información valiosa según el área de aplicación. Sin embarqo, a pesar de que la

información es un recurso muy importante para toda industria, el desarrollo y

aplicación de las técnicas de análisis de información no ha crecido al mismo

ritmo que el almacenamiento de datos. Debido a esto, e>:iste la necesidad de

generar y emplear nuevas técnicas y herramientas [6] de cómputo que permitan

al usuario obtener mayor información de la que ya pos::;e, al aprovechar y

explotar al máximo los recursos computacionales.

El descubrimiento de conocimiento en bases de datos (KDD por sus siglas en

Inglés Knowledge Discovery in Databases) constituye un procedimiento para

generar información útil a partir de datos. La aplicación de los algoritmos para la

extracción de patrones 1 corresponde a una fase primordial del proceso de KDD, y

es conocido en sí corno minería de datos.

Se debe alcanzar el objetivo de que a partir de datos se ~1enere conocimiento

relevante, lo que implica poder procesar automáticamente grandes cantidades

de datos para hallar dicha información útil y novedosa. Se requiere que las

técnicas de análisis de datos interactúen adecuadamente para generar los

mejores resultados. Dado que la mayoría de las técnicas de minería de datos son

aún muy recientes, se requiere de investigación al respecto, todavía existen varias

áreas de oportunidad siguiendo o generando líneas de invesi·igación.

Hasta hace unos años, el proceso de KDD era hasta cierto punto suplantado por

la actividad de los gerentes, planificadores y administradores. Sin embargo,

actualmente en un buen proceso de KDD es más provechoso que un experto o

investigador realice esta labor al apoyarse en herramientas diseñadas para ese

1 Representan conocimiento siempre y cuando su medida de interés rebase un determinado umbral

4

Desc11bri111ie1110 de Co11oci111ien111 en Bases de Dalos

fin, y al generar un procedimiento a seguir con base en la experiencia. El experto

o investigador debe- interactuar constantemente durante los etapas del proceso,

con el objetivo de que la información generada sea efectivamente un resultado

valioso. La importancia y necesidad actual de un proceso de descubrimiento de

conocimiento en bases de datos, ya no se pone en discusión.

El empleo de KDD va en aumento, a pesar de que cada ·1ez es más claro que

este proceso involucra un mayor esfuerzo del que inicialmente se habría pensado.

Por mencionar algunos casos: es necesario preparar los dalos a examinar, varias

veces; se requieren numerosas pruebas de extracción para verificar el proceso; se

hace un gran (en ocasiones incierto) uso de recursos computacionales y

humanos. En efecto se estima que el 80% del tiempo empleado en KDD, está

destinado en la preparación de los datos, y el 20% restante es en sí el proceso de

minería. Esto parte ele la noción de que sin los datos adecuados, existen muy

pocas posibilidades de encontrar información útil, novedosa y relevante.

El tener grandes cantidades de datos no implica que se deban emplear en su

totalidad para la extracción de conocimiento, de hecho el volumen de

información almacenada hace a veces imposible el proceso de extracción.

Actualmente el incremento desmesurado en el tamaño de las bases de datos

constituye un problema grave para el proceso de KDD, dado que los algoritmos

de extracción no escalan adecuadamente; la complejidad de éstos es peor que

lineal.

Una técnica que tiene el objetivo de eliminar este problema, es el muestreo

progresivo. La idea fundamental es obtener un subconjunto de datos a partir del

cual se pueda generar un modelo donde, con base en una medida de

evaluación (como la precisión - ejemplos correctamente evaluados), se pueda

determinar la equivalencia de éste con respecto al modelo 9enerado a partir del

total de datos. Aquí se contraponen dos conceptos fundamentales para el

muestreo: la precisión y la eficiencia . La precisión permite :letectar estructuras

complejas en la generación de modelos lo cual demanda ~Jeneralmente el uso

5

Desc11hri111ie11to de Co11oci111ie1110 e11 Bases de Datos

de una gran cantidad de datos. Por el otro lado si se persigue una buena

eficiencia, es necesario emplear pocos datos dada la complejidad de los

algoritmos de extracción, los cuales normalmente, en el mejor de los casos, son

de forma polinomial con el número de datos.

Los algoritmos de extracción requieren de una adecuado cantidad de datos

para generar buenos resultados a partir de una base de da-·os, pero ¿cuál es esa

cantidad?, ¿cómo saber que son datos adecuados?, ¿cómo saber que otra

cantidad de datos no es mejor? Éstas son algunas de k:is preguntas que el

muestreo progresivo de datos aborda, pero en si ¿cuál es la necesidad de realizar

el muestreo progresivo? Para responder este cuestionamierto debemos retomar

el hecho de que las bases de datos almacenan diariamente grandes cantidades

de datos a tal grado que es muy difícil, y en algunos casos imposible, procesar

esos volúmenes de información. El problema se enfoca en dos puntos: el tiempo

que demanda el manejo de tanta información y las limitaciones del hardware­

software de poder analizarla adecuadamente.

En realidad estos problemas están fuertemente relacionados a costos para una

organización, debido a que los recursos tiempo y uso de hardware no son

baratos. En los inicios de la minería de datos la ejecución de los algoritmos se

llevaba a cabo con la totalidad de los datos2, pero en la actualidad esto ya no es

factible en muchos casos, tanto por costos (uso de recursos) como por

posibilidades (capacidades del hardware). Por citar algunos casos, WalMart

realiza más de 20 millones de transacciones diarias y tiene una base de datos de

11 terabytes; AT&T tiene 100 millones de clientes y realiza del orden de 300 millones

de llamadas al día de larga distancia; y el telescopio Hubble genera diariamente

entre 1 O y 15 gigabytes de datos para los astrónomos de todo el mundo

(http://www.centennialofflight.gov/essay/Dictionary/HST /DI 19.S.htm). Por tal razón

es que surge el muestreo progresivo cuyo objetivo a grandes -asgos es ir tomando

muestras incrementales de datos siguiendo un determinado esquema de

muestreo hasta que se satisfaga una condición de paro.

2 En algunos casos aplica: 2/3 de los datos para aprendizaje y 1/3 para comprobación

6

Desc11bri111ie1110 de Co11oci111ie1110 en Bases de Dalos

Mediante el muestreo progresivo se busca realizar el proce:;o de descubrimiento

de conocimiento, de forma más eficiente al no consumir ··iempo analizando la

totalidad de los datos, sino solamente una porción del total. Se espera que el

modelo de KDD resultante tenga una evaluación similar, en cierto rango, a la

alcanzada con la totalidad de los datos. En si con el muestreo progresivo se

desea hallar un tamaño de muestra que brinde la mayor precisión posible, al

menor costo (tiempo y uso de recursos).

Hoy en día existen diversas alternativas para realizar muestreo progresivo. Unas de

los más importantes son el muestreo aritmético y el geométrico [7], pero cada uno

de estas técnicas presenta problemas que deben ser corregidos . Así mismo

existen otros métodos que intentan resolver los problemas del muestreo progresivo

atacando los puntos principales de éste : selección del tamar"lo de muestra inicial,

esquema de muestreo, y detección del criterio de paro ó convergencia. Sin

embargo, en genero!, estos algoritmos tienen una complejidad que los hace

deficientes (poco competitivos, baja eficiencia) con respecto al aritmético y el

geométrico. Ejemplos de estos métodos, que en sí no realizan muestreo progresivo

como tal, son los que tratan de determinar el tamaño de muestra inicial para el

muestreo al analizar los datos previamente; o bien evitan el muestreo al procesar

los datos una sola vez y obtener así la información necesaria. En efecto la defensa

de estos algoritmos, basados en información de los datos, no exponen una

adecuada documentación y comparación con el muestreo aritmético y el

geométrico; y ademós, en muchos de los casos, terminan por emplear a estos

últimos para finalizar su ejecución [2] . Entonces, como se puede ver, es necesario

el desarrollo de nuevas técnicas de muestreo progresivo, que aborden los

problemas inherentes a este proceso.

7

Desrnbrimie1110 de Co11oci111ie1110 en Bases de Datos

1.1 Objetivo

El objetivo que en esta tesis se planteó, con la meta de impactar o mejorar

finalmente el proceso y resultados de KDD, es:

', Diseñar un nuevo algoritmo de muestreo progresivo, que considere:

o la selección del tamaño de muestra inicial,

o el esquema de muestreo,

o y la detección de la convergencia

Y que sea más eficiente y efectivo que los esquemas actuales; con lo cual se

espera resolver, en buena medida, el problema de la cantidad de datos que

debe ser procesada por los algoritmos de extracción para la minería de datos,

donde (como ya se mencionó) en ocasiones la ejecución de los mismos es

imposible (o extremadamente lenta-ineficiente) dados los gr::mdes volúmenes de

información.

1.2 Retos computacionales

Es importante señalar que el muestreo progresivo tiene retos actuales e

importantes, que se abordaron en esta investigación: selección del tamaño de

muestra inicial. selección de esquema de muestreo, y detección de la

convergencia. Se diseñó un algoritmo consistentemente superior (en lo que se

refiere a estos conceptos) al esquema aritmético y geométrico. Esta superioridad

será demostrada y detallada a lo largo de esta tesis.

El algoritmo planteado tiene, en el mejor de los casos, el mismo costo que la

ejecución del proceso de extracción al utilizar el tamaño óotimo N oráculo (caso

menos costoso). Así mismo, en el peor de los casos, el costo de ejecución es a lo

más semejante al costo del proceso de extracción con el total de datos. El

algoritmo de muestreo que se desarrolló, es el NSC, cuyas siglas simbolizan la

completa cobertura de los puntos importantes del muestreo progresivo: N inic ~ min -

8

Desrnbrimiento de Co11oci1111e1110 en Bases de Datos

tamaño inicial, Sampling - muestreo empleado, y Co1vergence - criterio de

terminación .

1.3 Contenido del documento

En el capítulo dos se plantean los antecedentes y marce teórico necesarios para

un buen entendimiento de la tesis, lo que básicamente consiste en situar al lector

en el contexto de KDD y el muestreo progresivo. En el copítulo tres se presenta el

algoritmo de muestreo progresivo NSC, y las características que lo definen. En el

capítulo cuatro de pruebas y resultados, se describen los datos usados para

corroborar lo planteado en el capítulo tres, así como los pruebas propiamente

hechas. Finalmente el capítulo cinco presenta las principales conclusiones del

trabajo realizado y se retoman los puntos que pueden dar paso a líneas de

investigación para un trabajo futuro .

9

Desc11bri111ie11to de Co11oci111ie11to en Bases de Datos

Capítulo 2. Antecedentes y marco teórico

2.1 Descubrimiento de conocimiento en bases de datos

Es impresionante si comenzamos a pensar en la canticad de información que

manejamos diariomente de manera individual, como códigos de barras, diversos

archivos de datos, números telefónicos, cuentas bancarias, etc . Y es aún mayor

nuestro asombro cuando escuchamos que la última película de Pixar consumió

varios terabytes de datos en su elaboración. Si trasladamos este escenario a un

ambiente productivo, fuera del entretenimiento, comenzamos a caer en cuenta

de los grandes retos y oportunidades que se nos presenten, en una base de datos

de "Cuentas Por Cobrar", por mencionar alguna. Estas oportunidades, a las que

hago mención, son por ejemplo el saber qué tipo de clientes requieren de ser

avisados con uno semana de antelación del pago que deben realizar dado el

perfil que presentan, o bien qué tipo de plan de pago es preferible ofrecer a

nuevos prospectos, etc.

Otra aplicación c'e KDD es en la industria farmacéutica, aue se caracteriza por sus

grandes costos en investigación y desarrollo. Globalme1te la industria gasta 13

billones de dólares al año en investigación y desarrollo de fármacos. El proceso

de desarrollo de un fármaco involucra millones de compuestos químicos de los

cuales solo unos cuantos son seguros y utilizables. Est:Js compañías emplean

sofisticadas técnicas de predicción para determinar que químicos producirán

fármacos usables. Al enfocar la investigación y desarrollo en los químicos

apropiados, las compañías ahorran millones y millones de dólares.

Estos son algunos beneficios que puede brindar la minerío de datos, por lo que es

fácil entender que las empresas comiencen a llevar a cabo procesos de KDD,

siempre y cuando se cumplan ciertos criterios prácticos (existe potencialmente un

impacto significativo, no hay métodos alternativos, existe soporte del cliente para

el desarrollo, y no existen problemas de legalidad con los datos) y técnicos

(existen suficientes datos, atributos relevantes, poco ruido en los datos, y

10

D1?srnbri111ie11to de Co11ocimiento en Bases de Datos

conocimiento del dominio) superando por mucho lo inversión de recursos

(tiempo, dinero, recursos humanos, maquinaria, etc.) que KDD demanda.

En general, el proceso de KDD es complejo de realizar, sin embargo, numerosas

empresas generan continuamente herramientas comerciales para determinadas

actividades. Tal es el caso de Clementine (de Integral Solutions), lntelligent Miner

(de IBM), y 4Thought (de Liningstones) . Pero cuando las condiciones de la

aplicación de KDD se vuelven más demandantes, el proceso debe aplicarse

particularmente.

A pesar de la necesidad que se tiene en el descubrimiento de conocimiento en

los grandes volúmenes de datos que se manejan diariamente, existen problemas

adicionales, inherentes al proceso que deben ser tratados según la aplicación en

cuestión. Esto se debe a que las técnicas empleadas en la minería de datos no

siempre se adapton o ajustan adecuadamente al proble-na, o bien los resultados

que proporcionan difieren por mucho a lo esperado. En algunos casos los

algoritmos empleodos requieren de mayor información, la cual no siempre esta

disponible, para poder generar resultados satisfactorios o bien viene con datos

corruptos que provocan un mal funcionamiento . En otros casos el proceso que se

ejecuta brinda como resultado demasiada información. difícil de tratar; lo que

puede deberse a un empleo inadecuado de las herramientas o técnicas .

Además de esto, debemos considerar que no siempre e'.; fácil aplicar el proceso

de KDD, ya que se depende del dominio de aplicación y en ocasiones los datos

pueden presentm una alta complejidad, o bien cambies drásticos en el tiempo

(lo que imposibilitd un buen tratamiento).

El descubrimiento de conocimiento en bases de datos es un proceso mediante el

cual se puede generar información aplicable a partir de volúmenes de datos

almacenados en una base de datos. La historia de KDD se remonta

concretamente hasta hace unas pocas décadas, sin embargo, la necesidad de

análisis e interpretación de información, es algo inherente al mismo desarrollo

humano. Siguiendo la huella que el hombre ha dejado desde su estancia en la

11

Desc11brimie1110 de Co11ocimie1110 en Bases de Dolos

Tierra, podemos hacer un resumen de los medios físicos que se han empleado

para hacer permanente dicha trayectoria. El ser humano ha plasmado su

estancia a través de pinturas rupestres, artesanías, lienzos, pergaminos, hojas,

libros, audio, vídeo, medios electrónicos (como las bases de datos), etc. Sin

embargo, conforme estos medios nos han permitido almacenar mayores

cantidades de datos, estos a su vez han aumentado la complejidad de su

estructura; tanto lo que representan, así como la que los constituye.

En la actualidad los grandes volúmenes de datos representan una gran

oportunidad desperdiciada. Las bases de datos son comúnmente empleadas

como enormes bodegas de datos, sin mayores beneficios que un historial que

permita trazar la 'vida" de un evento determinado por ciar un ejemplo. Por ello,

actualmente, dada la demanda acelerada de informoción que presenta la

sociedad, se ha provocado que el ritmo con que se puecen analizar los datos ya

no sea suficiente para cubrir los requerimientos diarios. Si bien es cierto que las

pequeñas3 bases de datos que anteriormente se manejaban no significaban gran

reto para las ciencias computacionales, también es cierto que hoy en día es

necesario, en lo posible, el análisis automático e inteligente de datos. Digo en lo

posible debido a los problemas que surgen durante el proceso, los cuales se

pueden resumir en:

• Disponibilidod de información.

• Naturaleza, comportamiento, características, y volumen de los datos.

• Interacción o dependencia con el experto o investi9ador.

• Entendimiento del dominio del problema, y de los resultados generados.

• Naturaleza incremental del proceso, dados los ajustes derivados del

análisis.

El descubrimiento de conocimiento en bases de datos es en si un reto; el

entendimiento del dominio del problema !dominio de aplicación) es un punto

crítico para todo el proceso, y de hecho es la fase que consume mayor tiempo.

3 En comparación con las bases de datos actuales, las que fácilmente almacenan varios millones de registros.

12

Desc11bri111ie11/o de Co11ocimie1110 e11 Bases de Datos

Esto se debe a que el investigador debe ser un experto en técnicas de minería de

datos, así como U'l experto en el dominio del problema. Dada esta necesidad, el

proceso de KDD es por naturaleza muy interactivo e iterativo; el investigador debe

estar constantemente interpretando los resultados del proceso, para que de esta

forma , pueda ajustar adecuadamente el mismo y obtener un mejor análisis

posterior.

Hoy en día el proceso de descubrimiento de conocimiento no es una tarea

exclusiva de las bmes de datos, sino que se ha extendido hacia otros rumbos tales

como el descubrimiento de conocimiento en texto, en vídeo, en audio, y en

imagen [6] . Sin embargo, las mayores investigaciones :;e han realizado en el

análisis de bases de datos.

En nuestros días existe una gran cantidad de aplicaciones de la minería de datos

en diversas áreas que incluyen, entre otras muchas, a la astronomía, biología

molecular, aspectos climáticos y medicina [6]. KDD es un proceso que ya está

siendo puesto en marcha. Grandes organizaciones corno American Express y

AT&T emplean KDD para analizar sus archivos de clientes [6] . En el Reino Unido, la

BBC ha aplicado técnicas de minería de datos para analizar figuras de

despliegue, y en lo mayoría de los países europeos muchos de sus bancos han

comenzado a realizar experimentos con KDD.

KDD es un proceso que involucra un conjunto de técnica, que el ser humano ha

desarrollado y perfeccionado. La minería de datos es una respuesta a las

necesidades que se tienen en cuanto al proceso no trivial para identificar

patrones que sean válidos, novedosos, potencialmente útiles y entendibles a partir

de datos [6]. Se considera que KDD es un proceso debido a que se constituye de

una serie de pasos de manera iterativa, con el fin de que ol hallar información útil

se puedan realizar ajustes que mejoren los resultados obtenidos. Los patrones que

son descubiertos mediante este proceso deben ser válidos, en el sentido que

puedan ser aplicodos posteriormente. Adicionalmente estos patrones deben

cumplir las características de ser novedosos y útiles; la mzón es que no tendría

13

Desrnbrimie11to de Conocimie11to en Bases de Datos

sentido ejecutar un proceso de descubrimiento de conocimiento en bases de

datos si los resultados obtenidos fueran información corocída por el usuario, o

bien no aplicable al dominio del problema. En efecto los resultados que se

generen no deben ser complejos de interpretar, e~to con el fin de no

comprometer la utilidad que éstos puedan tener. Hay que señalar que el dominio

de aplicación es en sí el mayor trabajo del proceso de KCD; además los datos no

siempre son adecuados (tipos, valores faltantes, muchos datos, etc.) para la

extracción de conocimiento.

2.1.1 Las fases del proceso de KDD

El procesar automáticamente grandes cantidades de datos para encontrar

conocimiento útil para un usuario y satisfacerle sus metas, es el objetivo principal

de la minería de datos. El proceso de KDD se compone en general de las

siguientes 3 fases, con diversas tareas cada una (ver figura 2.1 .1. 1) :

• Preprocesarniento.

• Extracción de conocimiento.

• Postprocesamiento, evaluación o Análisis.

Conocimiento

Interpretación ~~ y e,:aluación y 1

Mineria oºn de datos D U Patroneii

Traruform.adón ~y _J _u u 1

~ transformados

IPreprocesamiento .,.---------1

. , ~ 1 ~ ~ 1 Pr!';::esados

~~\;~::;:· BD

Figura 2. 1.1 . 1. Proceso general de KDD

14

Desc11brimic11to de Co11ocimie11to en Bases de Datos

En el preprocesamiento se realizan las siguientes tareas:

• Entendimiento del dominio de aplicación, selección del conocimiento

relevante a emplear, y definición de las metas del usuario.

• Selección de un conjunto o subconjunto de bases de datos; seleccionar y

enfocar la búsqueda en subconjuntos de variables, y seleccionar muestras

o instancias de datos para realizar el proceso de descubrimiento. Hasta hoy

en día los datos han sido tradicionalmente tablas ASCII y la tendencia es

utilizar manejadores de bases de datos y almacenes de datos que estén

optimizados para realizar un proceso analítico.

• Limpieza y preprocesamiento de datos, diseiiando una estrategia

adecuada para manejar, entre otras cosas, ruido4, valores incompletos,

secuencias de tiempo, casos extremos, etc .

• Selección de la tarea de descubrimiento a realiza-; lo que puede ser, por

mencionar olgunas, clasificación, agrupamiento, e1c.

• Selección de los algoritmos a ejecutar.

• Transformación de los datos al formato requerido por el algoritmo

específico de minería de datos.

La extracción de conocimiento es básicamente:

• Llevar a cabo el proceso de extracción. Se buscan patrones que pueden

expresarse como un modelo, o que simplemente expresen dependencias

de los datos. El modelo encontrado depende de su función (tarea de

descubrimiento) y de su forma de representación (depende del algoritmo

seleccionaclo). Se tiene que especificar un criterio de preferencia para

seleccionar un modelo dentro de un conjunto posible de modelos.

4 Valores incorrectos (ya ,ea precisión o tipo de datos)

15

Descubrimiento de Co11oci111irnto en Bases de Datos

En el postprocesamiento se efectúan los siguientes pasos:

• Interpretación de resultados y posiblemente regreso a los pasos anteriores.

Esto puede involucrar repetir el proceso, quizás con otros datos, otros

algoritmos, otras metas y otras estrategias. Este es tc1mbién un paso crucial,

en el cual se requiere tener conocimiento del dominio de aplicación. La

interpretación puede beneficiarse de procesos d-3 visualización, y sirve

también para eliminar patrones redundantes o irrelevantes.

• Incorporación del conocimiento descubierto al proceso para mejorarlo, lo

cual puede incluir resolver conflictos potenciales con el conocimiento

existente.

• El conocimiento se obtiene para realizar acciones; ya sea incorporándolo

dentro de un sistema de desempeño, o simplemente para almacenarlo y

reportarlo a lm personas in teresadas.

2.1.2. Tareas y técnicas en KDD

Dado que la minería de datos explora y analiza grandes volúmenes de datos,

para descubrir patrones y reglas interesantes, entonces es necesario saber el

motivo por el cual se buscan esos patrones y reglas. La minería de datos se

enfoca a un conjunto específico de tareas, de las cuale:; todas involucran la

extracción de nuevo conocimiento significativo a partir ele los datos. Las seis

actividades principales de KDD [4] son las siguientes :

• Clasificación.

• Estimación.

• Predicción.

• Reglas de asociación.

• Clustering.

• Descripción y Visualización.

16

Desc11brimie11/o de Co11ocimie11to en Bases de Datus

Las primeras tres toreas se consideran instancias de minería de datos dirigida, en

la cual el objetivo es emplear los datos disponibles para construir un modelo que

describa un atributo de interés particular, en términos de los demás datos. Las

siguientes tres tareas son ejemplos de minería de datos no-dirigida, en la cual

ningún atributo es considerado como objetivo, sino que se busca establecer

alguna relación entre todos los datos.

Clasificación: Consiste en examinar las características de un nuevo objeto

presentado y asignarlo a una clase predefinida . Los objetos por clasificar son

generalmente registros (ejemplos) en una base de datos. La tarea de clasificación

es entonces actualizar cada registro con su clase correspondiente. Esta tarea se

caracteriza por uno buena definición de clases, y un conjunto de datos de

prueba formado por ejemplos preclasificados. Algunos ejemplos de clasificación

son : asignar palabrm clave a textos; clasificar aplicacione'.; de crédito como de

riesgo bajo, medio. o alto; determinar que líneas telel'ónicas de casa son

empleadas para acceso a Internet; asignar clientes a segmentos de clientes

predefinidos, etc .

Estimación: La clasificación trabaja con valores discretos: SÍ, NO, REPARAR;

TARJETA_DEBITO, TARJETA_CRÉDITO. Pero la estimación maneja los valores

continuos. Dada una entrada de datos, se usa la estimación para obtener un

valor de una variable desconocida continua; como lo puede ser por ejemplo: el

ingreso familiar, o un balance de tarjeta de crédito. En lo práctica se usa la

estimación para realizar tareas de clasificación. Por ejemplo un banco intentando

decidir a quien debe ofrecer una hipoteca, implica la toreo de que un modelo

base califique a sus clientes con valores entre O y 1; esto es en realidad una

estimación de la probabilidad de repuesta positiva de una persona hacia la

oferta . Este proceso presenta la ventaja de que los registros se ordenan de mayor

a menor (o viceversa) , según el grado de respuesta hacia esa oferta.

Comúnmente la clasificación y estimación son empleadas en conjunto; por dar

un caso, cuando se emplea la minería de datos para predecir quien es propenso

17

Desc11bri111iento de Co11oci111ie11to en Bases de Dalos

a responder a una oferta de transferencia de balance de tarjeta de crédito, y

también para estimar el tamaño del balance a ser transferido.

Predicción: No debería existir un apartado para predicción debido a que

cualquier predicción puede pensarse como una clasificación o estimación; la

diferencia es el énfasis. Cuando la minería de datos es usada para clasificar una

línea telefónica de acceso a Internet uno no espera poder dar marcha atrás

posteriormente para averiguar si la clasificación fue correcta . La clasificación

quizás sea correcta o incorrecta pero la incertidumbre queda sujeta solo al

conocimiento incompleto; afuera en el mundo real las acciones relevantes ya

han tomado su lugar: la línea de teléfono es o no empleada para una conexión

loca/ a ISP. Con suficiente esfuerzo es posible corroborar. Las tareas predictivas son

entonces diferentes dado que los registros son clasificados de acuerdo a un

comportamiento futuro predicho, o a un valor futuro estimado. Con la predicción,

la única forma de verificar que la clasificación sea ccrrecta, es esperar y ver.

Algunos ejemplos de predicción son: determinar que clientes se irán durante los

próximos seis meses y que subscriptores de teléfono ordenarán un servicio de valor

agregado como llamadas de tres vías o correo de voz. Cualquiera de las técnicas

usadas para clasificación o estimación pueden ser adaptadas para usarse en la

predicción al emplear ejemplos de prueba en los cuales el valor de la variable a

ser predicha ya es conocido; esto en conjunto con dotos históricos. Los datos

históricos se utilizon para elaborar un modelo que corresponda a una predicción

del comportamiento futuro .

Reglas de asocioción: la tarea es determinar "que cosm van juntas". El ejemplo

prototípico es determinar que cosas van juntas en un carrito de compras en el

supermercado. Se pueden usar las reglas de asociación para planear la

organización de productos es los estantes de una tiendo en la cual los productos

que comúnmente se compran a la misma vez sean colocados en el mismo lugar.

Las reglas de osociación también pueden ser empleadas para identificar

oportunidades de ventas cruzadas y para diseñar paquetes atractivos de

productos o serv:cios.

18

Desrnbrimiento de Co11ocimie11to e11 Bases de Datos

Clustering (Agrupoción): Es la tarea de segmentar un grupo diverso en un número

mayor de subgrupos similares o clusters (grupos) . Lo que diferencia a clustering de

clasificación es que clustering no se basa en clases predefinidas y ejemplos. Los

registros son agrupados con el principio de auto similaridad. Es decisión del

algoritmo determinar que significados otorgar a los clusters resultantes. Un cluster

particular de síntomas quizás indique una enfermedad específica. Clustering es

comúnmente llevoda a cabo como paso anterior a alguna otra forma de minería

de datos o modelado. Por ejemplo, esta tarea quizás sea el primer paso en un

esfuerzo de segmentación de mercado. En lugar de intentar generar una regla de

un-tamaño-abarca-todo para ver "a que tipo de promoción responderán mejor

los clientes", es mejor primero dividir la base de clientes en clusters o personas con

hábitos de compra similares, y después preguntar qué tipo de promoción

funciona mejor poro cada cluster.

Descripción y Visualización: En algunas ocasiones el propósito de la minería de

datos es simplemente describir lo que sucede con una base de datos compleja

de tal forma que se mejore el entendimiento de la gente, productos y procesos

que generan los datos. Una buena descripción d,9 un comportamiento

frecuentemente sugiere una explicación del mismo, o al menos establece los

pasos para comenzar a buscarla. El famoso eslogan de género en los políticos

americanos es un ejemplo de cómo una simple descripción: "las mujeres aceptan

a los demócratas en mayor número que los hombres". puede provocar gran

interés y trabajo futuro en sociólogos, economistas, y políticos. La visualización de

datos es una forma poderosa de minería de datos descriptiva . No es fácil generar

visualizaciones si~Jnificativas, pero la imagen adecuado realmente puede ser

mejor que miles de reglas de asociación debido a que para el ser humano le es

más sencillo extraer conocimiento de escenarios visuales.

KDD es un proceso complejo e interdisciplinario por lo que involucra y requiere de

áreas tales como:

19

Desc11brimie1110 de Conoci111io1/o en Bnses de Dntos

• Tecnologías de bases de datos y bodegas de da .. os. Se buscan maneras

eficientes de almacenar, acceder y manipular datos.

• Aprendizaje computacional, estadística,

neuronales, lógica difusa, algoritmos

probabilístico): Constituye el desarrollo

conocimiento a partir de datos.

computación

genéticos, y

de técnicas

suave (redes

razonamiento

para extraer

• Reconocimiento de patrones. Desarrollo de herramientas para la

detección v reconocimiento de patrones.

• Visualización : Se busca mejorar las interfaces en1re humanos y datos, y

entre humanos y patrones.

• Cómputo de alto desempeño: Es la mejora de desempeño de algoritmos

debido a su complejidad y a la cantidad de datos.

Como se puede ver, el proceso de KDD implica relaciones complejas entre

actividades hete 0 ogéneas que se aplican en cada fase. Por lo cual a

continuación se presenta una tabla con algunas técnicas empleadas en el

proceso, de acuerdo a cada etapa del mismo:

Tabla 2.1.2.1. Algunas técnicas de KDD en cada etapa del proceso

20

Descubrimiento de Co11oci111il·11to en Bases de Datos

KDD busca hallar patrones, tendencias y anomalías que presentan las bases de

datos, donde los avances tecnológicos y el abaratami,:;nto de dispositivos de

cómputo han permitido el surgimiento de grandes colecciones de datos. De

hecho se ha estimado que la cantidad de datos almacenados en el mundo en

las bases de dato5. se duplica cada 20 meses [6]. Sin emborgo, aún son necesarias

nuevas técnicas y herramientas que den solución al interés comercial que existe

por explotar los volúmenes de información almacenados. La velocidad a la que

se almacenan los datos es muy superior a la velocidad en que se analizan.

El muestreo progresivo de datos es indispensable hoy en día debido a la

complejidad y altos costos que demanda el análisis de grandes volúmenes de

información. En realidad el muestreo progresivo es en mJchas ocasiones mejor5

que el análisis de todas las instancias en una base de da-ros, lo que no ocurre así

en los casos donde el aplicar muestreo progresivo supero el costo de analizar la

totalidad de datos en primera instancia. El resultado finol esperado de ejecutar

muestreo progresivo es hallar un tamaño óptimo de muestra (N oráculo) tal, que

muestreos de mayor tamaño no involucran mejores precisiones. Si este tamaño es

previamente conocido; al ejecutar muestreo progresivo ele datos, en el mejor de

los casos, solo se i~Jualará el costo resultante de analizar inicialmente la N oráculo.

2.2 Muestreo progresivo

El objetivo principol de los métodos de muestreo progresivo de datos es maximizar

la precisión lo más eficientemente posible. La idea genero! es iniciar con muestras

pequeñas e ir aumentando el tamaño de éstas hasta que la precisión del modelo

generado no mejore. El muestreo progresivo requiere entonces de una

programación de muestreo la cual se sigue hasta que se cumple un criterio de

paro. En este punto surgen preguntas importantes: ¿qué programación de

muestreo es eficiente?, ¿cómo se puede detectar la convergencia efectiva y

5 En cuanto a costo: menor tiempo de ejecución, menor uso de recursos . Sin embargo la precisión alcanzada con muestras menores al total de los datos es en general menor bajo un cierto umbral aceptable

2 1

Descubrimiento de Co11ocimiento en Bases de Datos

eficientemente?, y ¿se puede ajustar la programación :::le muestreo conforme

avanza el muestreo?

Aquí comienza a ser evidente la necesidad de buenos métodos de muestreo; es

indispensable detectar que programación de muestreo es mejor dada una

expectativa de convergencia con base en una medida de evaluación del

algoritmo de extrocción. Es importante indicar el hecho de que existe una

interacción estrecha entre la programación de muestreo y el método de

detección de la convergencia, debido a que en ocasiones la programación de

muestreo no se cubre totalmente, si es que se converge (se alcanza el criterio de

paro) antes de evaluar la muestra final. El objetivo en sí es generar una

programación de muestreo adaptativa, la cual surja al tomar en consideración

tanto la convergencia del método, como la complejidad-tiempo de ejecución

de los algoritmos de extracción. Esto permitirá tener una programación dinámica

(ver sección 2.3) cuyas muestras presenten una variación en tamaño acorde al

comportamiento ~~eneral del método, y no con base en algún esquema

comúnmente fijo.

Para el muestreo progresivo es necesario establecer una re 'ación entre el tamaño

de muestra y la precisión del modelo, obtenida a partir del análisis de la muestra

en cuestión. Esto da como resultado las curvas de precisión mediante las cuales

es más sencillo visualizar la finalidad de los métodos de muestreo progresivo (ver

figura 2.2.1) .

22

Desc11brimie1110 de Conocimiento e11 Bases de Datos

Precisión

N oráculo

figura 2.2.1. Curva de precisión

Lo que una curva ce precisión indica es que al iniciar el muestreo la precisión del

modelo va mejorando conforme aumenta el tamaño de muestra. Pero llega un

punto a partir del cual la curva comienza a ser horizontal (indica convergencia),

lo que se logra en el momento en el cual al emplear más instancias de datos, la

precisión no mejore. En esto existe una suposición fuerte: IGs curvas de precisión

presentan un buen comportamiento como el mostrado en la figura 2.2. l, sin

embargo en la práctica el comportamiento de estas curvas tiende a ser

oscilatorio antes de converger.

La N oráculo entonces se define como: dado un conjunto de datos, un

procedimiento de muestreo, y un algoritmo de extracción, N orác ulo o N min es el

tamaño del más pequeño pero suficiente subconjunto de datos que cumple la

siguiente condición :

(precisión con N < N min) < (precisión con N min) ::::: (precisión con N total)

En algunos casos N min es imposible de determinar teóricamente, sin embargo,

ésta puede ser aproximada empíricamente mediante un procedimiento de

muestreo progresivo.

23

Descubrimiento ,te Co11oci111ie11to en Bases de Datos

Aquí se hacen evidentes los problemas del muestreo progresivo, los cuales se

tratarán con detalle posteriormente y que en general son : el establecimiento de

una buena programación de muestreo a partir de un buen tamaño de muestra

inicial, y con base en un adecuado esquema de muestreo; la detección de la

convergencia; y el lograr una programación adaptativa (sección 2.3).

2.2.1 Programación de muestreo

El problema de de1"erminar una programación de muestreo eficiente no es trivial,

involucra dos cuestionamientos importantes del muesireo progresivo: ¿qué

tamaño de muestm inicial es adecuada?, y ¿qué esquema de muestreo seguir?

Para dar solución a estas preguntas existen actualmente d versas técnicas, de las

cuales las más destocadas [7] son los siguientes.

Muestreo aritmético6 . Sigue una programación de muestreo acorde a: tamaño de

muestra = tamaño base + ( # del muestreo ó iteración * delta ó factor de

crecimiento). Por dar ·un ejemplo, este tipo de muestr,30 puede dar como

resultado programociones de muestreo tales como: 100, '.LOO, 300, 400, etc. Si se

toma el tamaño bme = 100 y el delta de crecimiento = 100, lo que significa n =

100 + (iteración * 100). Sin embargo, no se ha determinado un buen tamaño de

muestra inicial al emplear este tipo de muestreo, lo cual puede provocar que el

número de iteraciones necesarias para alcanzar la precisión buscada hagan que

el costo de este método sea elevado. A continuación se presenta el algoritmo de

muestreo progresivo aritmético.

6 Arithmetic Sampling

24

Descubrimic1110 de Conocimie11to en Bases de Datos

1. Generar programación de muestreo S = {no, n1, n2, n3 ... nk} con base en

la fórmula : n = tam_base + (iteración* factor_crec miento). Siempre que

n <= 50% del total de datos (criterio de paro empleado en la tesis).

2. n ~ no

3. M ~ modelo inducido a partir de n instancias

4. Mientras que no se converja (considerando S y la precisión de M)

a. n ~ siguiente elemento de S

b. M ~ modelo inducido a partir de n instancim

5. Regresar M

Tabla 2.2.1.1. Algoritmo para muestreo progresivo aritmé tico

Como puede apreciarse este algoritmo es muy sencillo de implementar, sin

embargo presenta el problema de realizar muchos muestreos (afecta el tiempo

de ejecución) antes de converger si la programación de muestreo no es

adecuada, lo que se refiere a una mala elección del tamaño base ó del factor

de crecimiento. Por tal motivo es importante estimar odecuadamente estos

valores, a pesar que este algoritmo no contempla dicha situación en su totalidad.

Muestreo estático7 . Intenta estimar N min sin muestreo progresivo. Se basa en

submuestreos de similaridad estadística a la muestra completa donde

generalmente se obtiene información (por dar un ejemplo: se emplean algoritmos

pesados que usan la medida de información de Kullback [3]) acerca de los datos.

Pero, como ya se mencionó es difícil estimar N min, o bien los algoritmos

empleados para dicho fin hacen que este tipo de muestreo este en desventaja

respecto a los otros (en cuanto a eficiencia; orden-complejidad del algoritmo) .

De hecho el muestreo estático corresponde a una degeneración del muestreo

progresivo debido a que consiste en un intento por "adivinar" N min, más que

realizar muestreo progresivo.

7 Static Sampling

25

Desc11bri111iento de Conocimi.~1110 en Bases de Datos

Muestreo geométrico8. Este método genera mejores modelos que el muestreo

estático y en general que el aritmético si consideramos boses de datos grandes. El

muestreo geométrico sigue una programación de muestreo acorde a: tamaño de

muestra = (factor AJ /\ (# del muestreo ó iteración) * tamaño base. Por dar un

ejemplo este tipo de muestreo puede dar como resultodo programaciones de

muestreo tales como: l 00, 200, 400, 800, etc. Si se toma el tamaño base = 100 y el

factor A = 2 [n = (2 ileraciónJ* 100]. En la práctica se ha estimado que un tamaño

base = 400 y un factor A = 2 son buenos parámetros (estos parámetros sin

embargo pueden ser adaptados) para una planeaciór de default para minar

grandes bases de datos empleando este tipo de muestreo, sin embargo, las

muestras crecen aceleradamente, lo que inevitablemente impacta en el costo

del método y la precisión alcanzada. Además en este método se tiene una

dependencia con los datos y el algoritmo de extracción de conocimiento. A

continuación se presenta el algoritmo de muestreo progresivo geométrico.

1. Generar programación de muestreo S = {no, n1, n2, n3 ... nk} con base en

la fórmulo: n = (factor_A iteración) * tam_base. Siempre que n <= 40% del

total de datos (criterio de paro reportado en la literatura) .

2. n f- no

3. M f- modelo inducido a partir de n instancias

4. Mientras que no se converja (considerando S y la precisión de M)

a. n ~- siguiente elemento de S

b . M f- modelo inducido a partir de n instancias

5. Regresar M

Tabla 2.2.1 .2. Algoritmo para muestreo progresivo geométrico

Al igual que en el esquema aritmético, este algoritmo es muy sencillo de

implementar, sin embargo presenta el problema de estimar adecuadamente el

tamaño base, así como el factor_A. Una mala elección de ambos valores

8 Geometric Sampling

26

Desrnbrimiento de Conocimirnto en Bases de Datos

provoca una pro,;;iramación de muestreo agresiva, la que en ocasiones queda

muy lejos de alcanzar N min ya sea sub ó sobre estimando este tamaño.

El muestreo progresivo de datos en general no es peor (en cuanto a costo) que la

ejecución única con la N 10101. De los esquemas antes descritos destaca el

muestreo geométrico por ser simple y converger en pocos muestreos. Para el

muestreo progresivo, N orócuio y N 10101 representan los límites de los posibles valores a

los que puede llegar finalmente la N del muestreo; entre mejor (más próxima a

Noracuio) sea esta t-..J, más bajos serán los costos esperados de las programaciones

obtenidas. Existen otros métodos que emplean programación dinámica9 para

generar la progmmación de muestreo, lo que en realidad es generar la misma

adaptativamente, no usando fuerza bruta parci explorar todas las

programaciones posibles . El resultado es un algoritmo de tiempo polinomial, a

partir del cual aún se realiza investigación para mejorarlo.

2.2.2. Detección de la convergencia

Este punto continúa siendo un problema abierto. Se persique la detección precisa

y eficiente de la convergencia del método, lo que frecuentemente se relaciona

con el algoritmo de extracción. La detección de la convergencia es entonces

generalmente un juicio estadístico que involucra algún procedimiento para

estimar la precisión tomando en cuenta las tres secciones de la curva de

aprendizaje: pendiente en creciente (positiva), pendiente en descenso (positiva

pero menor a lo anterior), pendiente horizontal (casi cero). Donde se debe

establecer un acotamiento para cada segmento.

Un problema de las estimaciones estadísticas de la convergencia es el hecho de

que compiten nuevamente la precisión y la eficiencia. Si se desea una buena

medida de la precisión se requiere que la programación de muestreo tenga un

mayor número de puntos, sin embargo, esto se contrapone a los objetivos del

muestreo progresivo (por eficiencia) . Otro problema es que las medidas de

9 Muestreo Progresivo Dinámico

27

Descubrimiento de Conocim;ento en Bases de Datos

calidad empleadas (por ejemplo la precisión) presentan altibajos que deben ser

asimilados por el algoritmo de muestreo. El objetivo es poder analizar el

comportamiento general de la curva de aprendizaje si esta comienza por

ejemplo a oscilar, por mencionar un caso: puede presentarse una oscilación

(alternación de pendientes negativas y positivas) mínima con los últimos cinco

puntos de una curva de precisión, pero en conjunto al ccnsiderar diez de éstos, es

posible apreciar que se ha convergido (ver figura 2.2.2. l).

Precisión

Pendiente casi cero

l~

N oráculo

Figura 2.2.2.1. Oscilaciones en una curva de precisión

Hasta el momento el método más prometedor es el LRLS 10 [7] que toma cada

punto de la programación de muestreo y examina los k vecinos para realizar una

regresión lineal. Se considera que la pendiente de las líneos tangentes a las curvas

de aprendizaje siempre disminuye hasta que se alcanza un determinado criterio

de convergencia. Pero este criterio debe ser definido y el método LRLS aumenta

la complejidad del muestreo progresivo en un factcr constante dado que

requiere k vecinos por cada punto de la programoción para efectuar la

estimación estadística.

'º Linear Regression with Local Sampling

28

DC'sc11brimie11to de Co11ocimie11to e11 Bases de Datos

2.3. Muestreo adaptativo

Un objetivo importante del muestreo progresivo es construir modelos

adaptativamente tomando como experiencia el muestreo progresivo dinámico

(sección 2.2.1) qJe requiere la definición de un modelo de probabilidad de

convergencia, y lo definición de un modelo de complejidad de ejecución; ambos

posiblemente ob1enidos a partir del algoritmo de extracción. Un algoritmo de

muestreo podría entonces generar (de manera ne costosa) información

substancial al incluir estas evaluaciones en su programación .

Al modelar la probabilidad de convergencia y el costo o complejidad actual de

ejecutar el algoritmo de extracción [7), se puede permitir a un procedimiento de

muestreo progresivo incrementar la eficiencia ele su programación

adaptativamente durante la ejecución, esto al tener la posibilidad de ajustar la

programación de muestreo según el comportamiento que se presente. Sin

embargo, esto no es siempre sencillo y eficiente de obtener a pesar de que el

muestreo progresivo puede permitirlo dinámicamente en ejecución . Pero, como

ya se mencionó, en esta línea de investigación faltan por definirse aún muchos

puntos abiertos pero críticos, que le den fortaleza a este tipo de muestreo. Por

ejemplo: ¿cómo realizar el ajuste de la programación de muestreo?, ¿en qué

medida?, y ¿acora e a que variación en la precisión y la complejidad? Hasta el

momento el muestreo progresivo adaptativo no ha demostrado ser más eficiente

que el muestreo geométrico, por dar un caso.

En general el real:zar muestreo progresivo de datos e~: menos costoso que

emplear el total de los datos cuando la convergencia del método no se prolonga

[7]. De todas formas si esto sucede, el aplicar el método 110 es por mucho más

caro que el análisis de toda la base de datos, pero sí se debe considerar el hecho

de que la mejor ejecución posible es saber de antemano N oráculo (como ya se

explicó esto difícilmente es posible). Un punto importante es que las técnicas de

muestreo progresivo a vencer son principalmente el esquema aritmético y el

29

Desrnbrimiento de Co11ocimie11to en Bases de Datos

geométrico; y dcido que ambos presentan las desventajas descritas entonces es

necesario diseñar nuevos algoritmos que los superen.

En cuanto a la selección de tamaño de muestra iricial tanto el esquema

geométrico corro el aritmético no presentan una buena elección, y ambos

esquemas de muestreo arrastran inconvenientes deb dos este problema. En

cuanto al esquema aritmético, una mala elección del tcrmaño de muestra inicial

puede provocar que el número de muestreos sea muy costoso (muchos

muestreos, muchos accesos a base de datos), y además este esquema de

muestreo debe ser adaptado particularmente a la aplicación sin considerar algún

criterio adaptativo.

Si bien es cierto que el muestreo geométrico puede iniciar con un tamaño de

muestra pequeño (la sugerencia es 400), también es cierto que el crecimiento

que lo caracterizo es muy acelerado dando grandes saltos en la programación

de muestreo. Esto puede provocar que difícilmente se alcance la N oráculo ya sea

sobrepasándola por mucho, o quedando muy lejos de ella. Ambos casos se ven

reflejados en costos debido a que por un lado se pierde eficiencia, y por el otro

precisión. Este tipo de muestreo, al igual que el aritmético, no es adaptativo.

En lo referente al criterio de paro ambos esquemas tienen deficiencias. No se ha

definido para ninguno de los casos un buen método para detectar la

convergencia. Hmta el momento solo han surgido técnicas particulares a la

aplicación del muestreo en las cuales se define un criterio de paro específico.

Pero además de poder detectar la convergencia con base en la precisión,

también es posible hacerlo con base en el tamaño del muestreo. En el caso del

esquema geométrico este criterio de paro se alcanza cuando el tamaño del

muestreo corresponde al 40% del total de los datos. Esto es evidente dado que el

siguiente muestreo a partir del 40% de los datos es prácticamente el total de la

base de datos, y peor aún si se consideran todos los muestreos que se han

realizado previamente a este tamaño. Con respecto al esquema aritmético, no se

ha definido un criterio de paro general con base en el tcrmaño de muestra, sino

30

Desrnbrimiento de Co11oci111ie1110 en Bases de Datos

más bien este tipo de muestreo se adapta particularmente a la aplicación en

cuestión.

Por tales motivos -problemas, en el siguiente capítulo se presenta un novedoso

método de muestreo progresivo de datos denominodo NSC; del cual se

comprobarán las ventajas que tiene sobre los otros métodos (muestreo aritmético,

geométrico, ejecución con todos los datos, y ejecución con N orócu10).

31

Descubrimie1110 de Conocimienro en Bases de Datos

Capítulo 3. NSC: Un algoritmo de muestreo progresivo

Como puede verse, existe la necesidad de un algoritmo que de inicio comience

con un buen tamaño de muestra, y que ésta crezca grodualmente permitiendo

un buen análisis del comportamiento del muestreo. Esto permitirá que, con base

en un buen método de detección de la convergencia, y tomando en cuenta la

precisión y el tamaño del muestreo; el criterio de paro se alcance

adecuadamente. A continuación se presenta de manera general el algoritmo

NSC el cual cubre las deficiencias que tienen las otras técnicas de muestreo

progresivo haciendo énfasis principalmente en: el tamaño de muestra inicial, un

buen esquema de muestreo (todo muestreo se hace aleotoriamente a partir del

total de datos con el objetivo de tener una selección justa y sin tendencias), y una

buena detección de la convergencia considerando la precisión y el tamaño del

muestreo.

1 . Sea N el número de instancias, M el número de atr:butos, A el algoritmo

de aprendizaje, y CA la complejidad del algoritmo con base en A N, y

M.

2. Sea S = {SO, S l, S2, ... , Sk} (- generaPlaneaciónNSC '.N, CA)

3. Sea conta = O;

4. Mientras que halla elementos en S

a. precision = ejecutaAlgoritmoExtracción(A S[conta])

b. Si evaluaPrecision(precision) es igual a CONVERGE,

i. Entonces fin de ciclo,

ii . de lo contrario conta = conta + l

5. END

Tabla 3.1 . Algoritmo para muestreo progresivo NSC

Si se desea analizar en mayor detalle el algoritmo NSC, en E·I anexo A se brinda el

listado completo del código fuente principal (el algoritmo, por reflejar un

32

Desc11bri111ie11/o de Co11oci111ien10 en Bnses de Dnlos

panorama globo!, difiere un poco del código fuente). El entendimiento del

algoritmo se complementa con la descripción que se da en la sección 3.2.

3.1. Descripción general

El algoritmo NSC genera la planeación de muestreo tomando en cuenta los

siguientes límites: inferior = tamaño de muestra inicial; superior = número máximo

de iteraciones o muestreos. La planeación de muestreo sigue el siguiente

esquema de muestreo: tamaño de muestra actual = 1.1 * tamaño de muestra

anterior (ver sección 3.3). La evaluación de la convergencia, en lo que se refiere a

precisión, se rea 'iza con base en pendientes de precisión (en la sección:

detección de la convergencia, se explicarán a detolle las pendientes de

precisión; corresponden a las pendientes de las regresiones lineales empleadas).

A continuación se describirán brevemente las etapas principales del algoritmo

presentado, para oosteriormente analizar a profundidad los puntos principales del

mismo.

En generaPlaneaciónNSC se involucran tres aspectos funcamentales: la selección

del tamaño de muestra inicial, la selección del número máximo de muestreos

(parte del criterio de paro), y la generación de la programación de muestreo con

base en el esquema de muestreo (factor de crecimiento 11 = 1 .1) . En seguida se

proporciona el algoritmo correspondiente.

11 Tamaño de muestra actual = 1.1 * tamaño de muestra anterior

33

Descubrimiento de Conoci111iento en Bases de Datos

generaPlaneaciónNSC(N, CA)

1. Sea Nmin = calculaNmin(N)

2. Sea Max_lt = calculaMaxlteraciones(N, CA)

3. Sea factorCrecimiento = 1 .1

4. Sea S f- arreglo[Max_lt+ 1]

S. Sea conto = O

6. Sean= Nmin

7. Mientras que conta sea menor o igual a Maxlt

a. S[conta] = n

b. n = n * factorCrecimiento

8. Regresa S

Tabla 3.1.1. Extensión de rutina del algoritmo para muestreo progresivo NSC

El ciclo que sigue a continuación de generaPlaneación~JSC lleva el control que

relaciona el muestreo NSC con el proceso de extracción de patrones. Este ciclo

valida la convergencia con base en dos criterios: la precis ón, y el número máximo

de iteraciones. Es importante señalar que estos controles no se llevan a cabo

propiamente dentro del ciclo, sino más bien son validaciones de resultados que

devuelven otrm rutinas del algoritmo NSC, como lo son:

ejecutaAlgoritmoExtraccion y evaluaPrecision. Esto se debe a que en cuanto a la

precisión, evaluaF'recisión() se encarga de verificar el cri1erio de paro y da fin al

ciclo o permite la siguiente iteración. En cuantQ al número de iteraciones, como

éstas ya fueron previamente definidas en el paso anterior y si el ciclo no finaliza

por el criterio de precisión, entonces éste se realiza hasta el número de iteraciones

permitidas.

El paso ejecutaAl~JoritmoExtracción ejecuta el algoritmo de extracción con base

en el muestreo actual y devuelve una medida de la evaluación del proceso

34

Desc11brimie1110 de Co11ocimie1110 en Bases de Daros

efectuado, que en este caso es la precisión (precisión= porcentaje de ejemplos

correctamente evaluados, sin embargo se puede emplear otra medida como lo

es recall, medida F, etc.). Esta medida posteriormente es analizada en

evaluaPrecisión donde se toma en cuenta el posible corrportamiento de la curva

de precisión y se determina cuando el método ha alcanzado el criterio de paro.

En este algoritmo intervienen varios aspectos que son importantes para un

completo entendimiento del mismo, por tal motivo en lm siguientes secciones se

detalla cada uno de estos puntos cruciales.

3.2. Selección del tamaño de muestra inicial y esquema de muestreo

Como se mencionó anteriormente los métodos de muestreo deben partir de un

tamaño de muestra inicial adecuado para evitar que los olgoritmos de extracción

se ejecuten demasiadas veces, agregando así ineficiencia al método. Existen

métodos que traton de estimar un buen tamaño de muestra inicial mediante un

análisis estadístico a partir del total de la base de datos [3]. Buscan hallar una

muestra cuyo anólisis sea lo suficientemente semejante al análisis del total de

datos, sin embargo, no se ha demostrado aún que estos métodos sean en

general más eficientes y menos costosos que los esquemas aritmético y

geométrico.

En la tesis se propone un método que más que basado en información estadística

a partir del análisis de los datos, obtiene un tamaño inicial adecuado a partir del

tamaño total. Esto se basa en el hecho de que es posible determinar el número

de observaciones necesarias para estimar una media poblacional tomando en

consideración que existe un límite para el error de la estimoción.

La suposición es que si se tiene una muestra de datos de un atributo, ésta permite

calcular con un morgen pequeño de error la media del atributo. La consideración

se extendió entonces para el cálculo de N min tomando en cuenta todos los

atributos. Se toma una muestra de datos que aproxime con un alto grado de

confianza la media de una variable aleatoria. En las pruebas realizadas se

35

Desrnbri111ie11to de Conoci111ie11to en Bases de Datos

observó que éste es en general un buen estimador, y por consiguiente en el

capítulo cuatro se presentan los resultados comparativos entre la N min calculada

y la real ( N orácu10).

La fórmula estadística [5] que se adecuó, y que a continuación se presenta,

aplica sobre el total de ejemplos más que sobre la información que se pueda

generar con base en los atributos de la base de datos. Esto hace que el estimador

resultante sea muy eficiente debido a que es en sí un cálculo directo.

_ Total de Datos* a- 1

Tamano de muestra incial = - - ,

D d D límite error estimación 2

on e = - -

y cr = Total_ de_ Datos

4

4

Total de Datos* D +:J -. . ... (3.2.1)

Cabe señalar que existe una estrecha relación entre límite para el error de

estimación y el total de datos. En efecto el límite para el error de estimación

corresponde a un porcentaje 12 del total de datos, sin embargo, en lugar de fijar

un porcentaje se determinó información a partir de varias bases de datos, para

obtener así una proporción adecuada según el tamaño total.

Esto se realizó calculando el N min de las bases de datos (capítulo cuatro), al

aumentar gradualmente el tamaño de muestra, y repitiendo el proceso 1 O veces.

Con estos datos, se calculó un valor de porcentaje de confianza que diera como

resultado un tamaño equivalente al N min, y acorde al total de datos.

Límite error estimación = Total de Datos* C - - -

12 Esto implica que en las fórmulas 3.2.2 y 3.2.3, C = C/100 para que quede expresado como porcentaje

36

Desc11brimiento de Conocimie1110 en Bases de Datos

E t D .D (Total de datos* C) 2

n onces = = - -4

Donde C = 41.468 * Total de Datos-º·479 + 0.05

El cálculo de C se realizó con base en una regresión lineal a partir de las pruebas

realizadas sobre diversas colecciones de datos; lo que se detalla en el capítulo

cuatro. El valor obtenido del límite, expresado como porcentaje, para el error de

estimación es la mejor relación entre éste y el total de datos.

· Entonces, para simplificar la fórmula 3.2. l primero consideremos que

Total_de_Datos = N, y que Tamaño_de_muestra_inicial = n:

N•(:)' 11 =

(NC)2

( N) 2

N* + 4 4

. .... (3.2.2)

Ahora al simplificar la fórmula 3.2.2 se obtiene la "fórmula para estimar el tamaño

de muestra inicial" que aquí se propone:

N n= -

4NC 1 +l . . . .. (3.2.3)

Al realizar este cálculo se tiene como resultado una buena estimación 13 del

tamaño de muestra inicial con base en la media poblacionol y un posible error en

la estimación a partir del total de datos. Al emplear este vclor en el muestreo se

puede lograr una buena programación de muestreo, lo cual se explica a

continuación.

13 En el capítulo: Pruebas y resultados obtenidos, se muestra que n N0 ,áculo

37

Desc11bri111iento de Conocimiento en Bnses de Dntos

3.3. Esquema de muestreo

La programación de muestreo NSC es en sí un cálculo muy sencillo (lo que se

mostrará posteriormente), sin embargo, es un punto importante debido a que

ésta programación es la que establecerá los tamaños de muestra que serán

proporcionados ol algoritmo de extracción. Adicionalmente aquí es donde

comienza a intervenir uno de los dos criterios de paro el cual se trata en la

siguiente sección: máximo número de iteraciones.

Esto se debe a que la programación de muestreo NSC se rige en realidad por la

fórmula 3.2.3, a partir del tamaño de muestra inicial (límite inferior), y hasta que se

alcanza el máximo número de iteraciones (límite superior). El esquema de

muestreo, para el olgoritmo NSC, se incrementa entonces de la siguiente forma:

Tamaiio actual = 1.1 * Tama,10 anterior ..... (3.3.1)

La justificación-elección del valor 1 . 1 es resultado de las pruebas efectuadas, y

que se presentan en el capítulo cuatro; en esta sección solo se detallan las

características que tiene una programación de muestreo derivada de la fórmula

3.3.1. Este esquema de muestreo genera programaciores de muestreo más

eficientes que las aritméticas y geométricas. Al comenzar el muestreo a partir de

un buen tamaño de muestra inicial el muestreo progresivo NSC convergerá en

pocas iteraciones o diferencia del muestreo aritmético. El valor de 1 . 1 evita

realizar numerosos muestreos como en el esquema aritmético. De igual manera

no sucede lo mismo que con el muestreo geométrico, con el cual en ocasiones el

muestreo sobrepasa por mucho el tamaño de muestra Nmin, o bien se queda muy

lejos de éste. Este problema se debe a las características del, hasta cierto punto

agresivo, esquema de muestreo geométrico, sin embargo, el esquema de

muestreo NSC genera una programación de muestreo ade::uado al tamaño de

muestra inicial. No crece desmesuradamente ni a pasos cortos. sino trata de

mediar el crecimiento apoyándose en la ventaja de iniciar con un buen tamaño

de muestra inicial.

38

Desc11bri111ie11to de Co11ocimie1110 en Bases de Datos

El algoritmo NSC genera inicialmente la programación de muestreo con el

objetivo de mejorar la eficiencia del mismo y sobre todo simplificar el

entendimiento del muestreo. Esto se debe a que el únic:i control adicional que

debe realizarse en el muestreo es la detección de la convergencia con base en

la precisión

3.4. Detección de la convergencia por número de iteraciones y medida de

precisión

La detección de lo convergencia es un problema abierto. No existen muchos

métodos propiamente y en efecto los esquemas aritmético y geométrico no

detallan en gran medida el proceso que siguen al respecto. Lo que si se

menciona es que emplean el método LRLS, abordado en el capítulo dos. La

propuesta que aquí se presenta en cuanto a la detección :le la convergencia es

una técnica doble que considere:

l. Un número máximo de iteraciones con base en el costo de realizar el

muestreo.

2. Una medida de la precisión con base en una técnica similar al método

LRLS.

Primero analicemos el criterio de paro con base en un máximo de iteraciones, lo

cual no es contemplado por los esquemas aritmético y geométrico. Para

entender que significa el máximo de iteraciones debemos estar consientes de

que este límite se relaciona con el costo de ejecución del algoritmo de minería de

datos que se emplee. No tiene caso realizar el muestreo progresivo si es más

costoso que ejecutar el proceso de extracción con el total de datos. Por tal

motivo este límite se define con la siguiente relación:

Costo con Total de Datos 2: Costo usando Muestreo NSC

39

Desc11brimien10 de Conocimienlo en Bases de Daios

Donde Costo_con_Total_de_Datos se refiere al costo computacional de analizar

todos los dotos con un cierto algoritmo de minería, y

Costo_usando_Muestreo_NSC se refiere al costo computc1cional total al emplear

muestreo progresivo NSC y el mismo algoritmo de minería.

Como el costo de la generación de conocimiento radica ,3n sí en el algoritmo de

extracción, entonces en la relación anterior el costo corresponde al orden de

dicho algoritmo. Este orden depende completamente del algoritmo de

extracción aplicado y por tal motivo las siguientes fórmulas se expresan de

manera genérica mostrando que el algoritmo de muestreo progresivo NSC no

depende estrechamente del algoritmo de extracción empleado. La gama de

costos que se rigen con las siguientes fórmulas corresponden al O(n cost0 u 0rden¡.

Otro punto a señolar es que el ~, queda sustituido por un = dado que

analizaremos el caso límite de la relación:

Costo_ Total== (N101

a, )ºrd"" = Costo _usando _Muestreo _NSC ..... (3.4.1)

Donde el costo de aplicar el muestreo progresivo NSC, con base en el orden del

algoritmo de extracción y el esquema de muestreo NSC, se obtiene de la

siguiente manera (tomando en consideración que Nmin = n ele las fórmulas 3.2.2 y

3.2.3):

Costo_ con_ NSC = N,1¡11 + 1.1 * N 111¡11 + 1.1(1.1 * N min) + 1.1(1.1(1.1 * Nmin )) + ...

Costo _con _NSC = Nmin (1.1° + l. 11 + 1. 12 + 1.1 3 + ... )

Costo _con_NSC = N111

¡11 ¿;~

01.1;

Dondel4 ""x 1.1; = 1.1>+1 _1 L,i=O Ü.1

De tal manera que la fórmula 3.4.1 queda expresada como:

14 Fórmula deducida con ayuda del Dr. Antonio Acosta. Departamento de Matemátic:1.s, ITESM CCM.

40

Desc11bri111ie1110 de Co11oci111ie1110 en Bases de Datos

x+I

(N ) urden = (N . )orden 1.1 -1 toral mm O. l ..... (3.4.2)

Lo que sigue es despejar x (que es el número máximo de iteraciones) de la

IRlJ> X<ID GRQ3H \H ll XD<ID HCFR~ GH OS <JFDUP XH\freo NSC con el costo de

la extracción empleando el total de datos. Finalmente, después del despeje y

tomando en cuenta que en esta tesis se usó C4.5 15, el cua· tiene un costo teórico

de O(ea2) (e = número de ejemplos, y a = número de atributos), pero en la

práctica se ha estimado de entre O(e 12) y O(e 14 ); la fórmula para calcular el

número máximo de iteraciones en el muestreo NSC es entonces (el valor 1.3

corresponde al promedio de 1.2 y l .4):

numero maxzmo iteraciones =

In{o.1[ N,mat Ju + 1} Nmm

-1 ln(l.1) . . . . . (3.4.3)

Esta fórmula corresponde al primer criterio de paro del algoritmo NSC la cual nos

asegura que el muestreo progresivo NSC aplicado no es mfo costoso que realizar

el proceso de extracción de conocimiento empleando el total de datos, y el

algoritmo de extracción C4.5 (al emplear otro algoritmo, se modifican los

números). Para efectos de implementación nótese que el número de iteraciones

involucra a la número cero, y finaliza en x (inclusive). Ademós el valor resultante

de la fórmula equivale al entero inferior.

Ahora analicemos el criterio de paro con base en la precisión lo cual si es

contemplado por los esquemas aritmético y geométrico con base en el método

LRLS (a pesar que no se detalla mucho al respecto) . Aquí se propone un método

similar al LRLS en cuarn'o a que se realiza una regresión lineal, sin embargo, no se

emplean k vecinos que implican ejecuciones del algoritmo de extracción

15 Los detalles del algoritmo de extracción empleado se proporcionan en el capítulo: Dominio de aplicación.

41

Desc11bri111ie1110 de Conocimi~nlo en Bases de Datos

adicionales a los muestreos de la programación de muestreo. El método

propuesto empleC1 los puntos generados por el mismo muestreo progresivo para

realizar la regresión lineal considerando las tres secciones de la curva de precisión

y el comportamiento que puede presentar la pendiente de la recta obtenida.

Lo anterior se refiere al hecho de que en un buen compor-'amiento de una curva

de precisión se tienen tres secciones:

Prt?cisión 2 3

N oráculo

Figura 3.4.1. Secciones en una curva de precisión

1. La pendiente de la recta de regresión calculada va er aumento

2. La pendiente ele la recta de regresión calculada comienza a decrecer o a

"acostarse"

3. La pendiente de la recta de regresión calculada se 'acuesta" o es casi

cero.

Sin embargo, las curvos de precisión no siempre presentan este comportamiento

idóneo, y en ocasiones comienzan casi horizontales y de repente suben para

nuevamente acostarse, o en ocasiones decrecen para luego subir y acostarse,

etc. Pueden tener un comportamiento impredecible diferente ol de la figura 3.4.1.

Por tal motivo es importante el método de detección de la convergencia con

42

Desc11brimie1110 de Co11ocimie1110 e11 Bases de Datos

base en la precisión que aquí se propone, el cual soporta el comportamiento real

y teórico de una curva de precisión.

Antes de dar la descripción del método es necesario señolar que los datos que a

continuación se muestran fueron obtenidos empíricamente, y corresponden a

una buena evaluación de los criterios que miden o representan.

> La medida estadística empleada para evaluar la ejecución del algoritmo

de extracción en el muestreo progresivo NSC es la precisión (ejemplos

correctamente evaluados, aunque el algoritmo pu,9de dar soporte a otras

medidas}

> La precisión empleada corresponde a un promedio pesado 16 de las

precisiones (de cada clase} que intervienen en un<J sola ejecución de un

algoritmo de extracción. Cada valor de precisión se multiplica por la

cantidad de datos (expresada como porcentaje del total) acordes a esa

clasificación . Posteriormente se suman las precisiones para obtener así el

resultado final.

> Se considera que el muestreo progresivo NSC converge si la precisión del

algoritmo de extracción = 1

~ En caso de no cumplirse el punto anterior, el criter o de convergencia se

corrobora empleando al menos dos puntos en la regresión lineal.

Adicionalmente este criterio se verifica 2 veces: con la regresión lineal

actual y con el ajuste de la misma con base en el ::omportamiento de la

pendiente.

~ La pendiente de la regresión lineal se realiza con base en: cambio en la

precisión o cambio en el muestreo. El cambio en el muestreo (fórmula 3.3.1)

corresponde a un porcentaje del total de datos 17 .

~ Se considera que el muestreo progresivo NSC converge si el valor absoluto

de la pendiente de la regresión lineal es suficientem9nte pequeña, lo cual

16 Ponderación implícitamente promediada. El objetivo es que el cálculo sea lo más justo posible con base en la cantidad de datos involucrados. 17 Para que la evaluación de la pendiente sea lo más justa posible. No olvidar q:.1e el cambio en el tamaño del muestreo no es constante, sino incremental con base en el esquema de muestJ:eo. Éste cambio es en mayor medida que el cambio en la precisión, el cual es en si muy pequeño.

43

Desc11brimie1110 de Co11ocimie1110 en Bases de Datos

es aceptable si la pendiente es < O.O l (valor exoerimental, ver capítulo

cuatro).

-., Se considera que la pendiente de la regresión lineo! comienza a acostarse

si esta entre 0.01 y 0.025 (valor experimental, ver caoítulo cuatro).

-., Se considera que la pendiente de la regresión lineo! va en aumento si es ?

0.025 (valor experimental, ver capítulo cuatro).

>- Si el valor de la pendiente de la regresión lineal es negativa, pero no

converge, entonces la recta tiene un comportomiento importante de

analizar debido a que ésta puede iniciar un movimiento oscilatorio.

El método es sencillo de comprender, es robusto y soporto situaciones anormales

de la curva de precisión como las descritas anteriormente, pero adicionalmente

el caso crítico que es cuando la curva de precisión zigzaguea. El método tiene la

capacidad de detectar esta situación y generar la regresión lineal con un

conjunto mayor de puntos para analizar la tendencia de la recta.

;¡ y :;> <;> e¡> 'ií

Figura 3.4.2. CapacidoJd del método de de1ección de la convergencia con base en la precisión. paro analizar el comportamiento global de la regresión lino~al

El método en general consiste en los siguientes posos, realizados en

evaluaPrecisión del algoritmo de muestreo NSC:

44

Desrnbrimienlo de Co11oci111ie1110 en Bases de Dalos

evaluaPrecision ( p)

1 . Si p es iguol a 1, entonces regresa CONVERGE

2. Si hay disponibles más de dos puntos de lo programación de

muestreo, para aplicar la regresión lineal, entonces

a. Si se converge con la regresión actual, entonces regresa

COI\IVERGE, si no

1. Si la pendiente es negativa, aumentar dos puntos al

conjunto de puntos de la regresión lireal (se mantienen a

lo más la cantidad de puntos actuales de la

programación de muestreo)

11. Si la pendiente indica que la recta comienza a

acostarse, aumentar un punto al conjunto de puntos de

la regresión lineal (se mantienen a lo rnás la cantidad de

puntos actuales de la programación de muestreo)

iii. Si la pendiente va en aumento, quitar un punto al

conjunto de puntos de la regresión lineal (se mantienen

al menos dos puntos)

1v. Si se converge con la regresión ajustada, entonces

regresa CONVERGE

3. regresa NO __ CONVERGE

Tabla 3.4.1. Extensión de rutina del algoritmo para muestreo pro~1resivo NSC

Es necesario indicar que la regresión lineal se hace con el conjunto de puntos

señalados, comenzando con el último punto analizado. Esto para que la recta

obtenida sea siempre la que defina la última posición de lo curva de precisión.

Cuando se quita o agrega algún punto del conjunto, éste corresponde al

elemento opuesto al elemento más reciente dentro del mismo.

45

Descubrimiento de Conocimiento en Bases de Datos

Este método es un cálculo eficiente con base en la información que ya se tiene

del mismo muestreo. Corresponde a un control que permite detectar la

convergencia oportunamente y que en unión a la detección de la convergencia

por número máximo de iteraciones, el esquema de muestreo NSC, y el tamaño de

muestra inicial, hacen del muestreo progresivo de dotos NSC un algoritmo

eficiente.

3.4. Análisis del algoritmo

En el siguiente capítulo se muestra como el algoritmo NSC presentado supera en

general a los métodos por vencer aritmético y geométrico. Sin embargo, para

enfatizar los beneficios del esquema NSC, y también paro que el lector pueda

forjar un criterio que contemple los pormenores del mismo, a continuación se

brindan algunas de las ventajas de éste algoritmo (no se detectaron desventajas

como tal, sin embmgo en el capítulo cinco se describe'l algunos puntos por

desarrollar).

Ventajas:

1. El algoritmo NSC no es dependiente del algoritmo de extracción, ni de los

datos empleados.

2. El cálculo del tamaño de muestra inicial es muy sencillo, y demostró ser un

buen estimador.

3. El esquema de muestreo evita caer en los problemas del aritmético y

geométrico (punto intermedio entre lo conservodor del muestreo

aritmético, y lo agresivo del geométrico).

4. Se tiene un criterio de paro que considera el costo de ejecución.

5. Se tiene un criterio de paro robusto y eficiente que considera los tres puntos

de la curva de precisión, así como un comportamiento real complejo. Es

más eficiente que el método LRLS, debido a que realizo menos muestreos­

evaluaciones.

46

Descubrimiento de Co11oci111ie1110 en Bases de Datos

6. El algoritmo no requiere de variar parámetros para una buena ejecución a

pesar que .. de ser necesario, es sencillo modificar el comportamiento

alterando mínimamente el código fuente.

Ahora que ya se ho explicado el algoritmo de muestreo progresivo NSC, entonces

es necesario comprobar lo antes descrito vía las pruebas y resultados obtenidos.

Para ello en el siguiente capítulo se detalla primero el contexto en el cual se

realizaron las pruebas, con el objetivo de mejorar el entendimiento de las mismas

y de los resultados obtenidos.

47

Desrnbrimiento de Conocimiento en Bases de Datos

Capítulo 4. Pruebas y resultados obtenidos

En las secciones iniciales de este capítulo se establece el ambiente en el cual se

realizaron las pruebas. Es necesario señalar primero las características del

desarrollo tanto del algoritmo, como de las pruebas en sí. 1:1 lenguaje de desarrollo

fue java 1.4.1 _01 en unó máquina con procesador lntel Celeron a 2.4 GHz y 512

Mb en RAM . Adicionalmente se empleó el algoritmo de extracción J48 (con los

parámetros: -t <orch .arff> -i -o -v. Con el objetivo de obtener solamente

información estadística) que es parte del ambiente de descubrimiento de

conocimiento en bases de datos WEKA [8]. J48 corresponde en realidad a la

implementación del algoritmo de clasificación C4.5 (autor: Ross Quinlan .

http://www.cse.umw.edu.au/-auinlan/) para la generoción de árboles de

decisión. Se seleccionó este algoritmo debido a que, por su uso frecuente, se

podría considerar como un estándar de comparación entre métodos.

Antes de dar una descripción de los datos usados en la tesis es necesario señalar

que durante el desarrollo se tuvo que modificar mínimamente la clase

weka.classifiers .Evaluation, con el objetivo de que al ejecutar el algoritmo de

extracción se pudieran encapsular los datos estadísticos d9 la evaluación de la

ejecución. Esto se logró mediante la creación y añndidura, al paquete

correspondiente, de la clase weka.classifiers.Evaluation_St<Jtistics. Con base en

estas dos clases se obtiene la información necesaria de la ejecución del algoritmo

de extracción, la cuol es utilizada por el muestreo progresivo.

Así mismo fue necesario implementar la clase com.kdd.SampleFileGenerator cuya

finalidad es generar un archivo con la cantidad de datos (selección aleatoria

exclusiva) indicados por cada iteración en el muestreo progresivo.

Adicionalmente para la regresión lineal se empleó la clase l~egressionCalculator

con base en una aplicación (the Calico Sta t.

http://www.math.csusb.edu/faculty/stanton/calico/index.htm1) estadística del

Departamento de Matemáticas de la Universidad San Bernardino, California, USA

(CSUSB). Hay que tomar en cuenta que otras clases tuvieron que ser

48

Descubrimiento de Conocimiento en Bases de Datos

implementadas para generar un ambiente de desorrollo adecuado en la

ejecución de pruebas. Estas clases implementan el muestreo aritmético y

geométrico, y la detección del tamaño de muestra óptimo por fuerza bruta. Vía

estas clases se pudo llevar un control detallado de las ejecuciones de los

algoritmos de muestreo progresivo aritmético, geométrico, y NSC, así como la

ejecución con el total de datos y el tamaño de muestra óptimo.

4.1. Datos empleados

Las bases de datos que fueron empleadas corresponden a archivos de texto en

formato ARFF 18 requerido por WEKA el cual consiste de tags especiales para

indicar características de los datos como nombres de atributos, tipos de atributos,

valores de atributos, y los datos en sí. Este formato fue desarrollado en el

Departamento de Ciencias Computacionales de la Universidad de Waikato,

Nueva Zelandia. Para mayor referencia, este formato se detalla en el sitio:

h ttp ://www. es . waikato .oc .nz/-ml/weka/ arff .html

Las bases de datos que se usaron fueron quince (nueve de prueba). Éstas,

excepto una, pueden ser descargadas gratuitamente de la red, dado que están

disponibles en repositorios de datos como el de la Universidad de California, USA

(http://www.ics.uci.edu/-mlearn/MLRepository.html). O bien de los sitios

referenciados que corresponden a ambientes de descubrimiento de

conocimiento en bases de datos (por ejemplo la base de datos capufe se

localiza en: http://doc.mor.itesm.mx/-ADEX/kddsite/kddHome.htm). Las bases de

datos no restringidas son fáciles de obtener para realizar ( corroborar) el proceso

de pruebas, pero la base de datos transaccional es propiedad de una empresa

de seguros 19 la cual autorizó el uso exclusivo de la misma en esta tesis.

A continuación se da una descripción general de las bases de datos ( de pruebas,

así como las de cálculos). Dado que estas se obtienen de la red no se ahonda

18 Attribute-Relation File Format. 19 Se omite el nombre de esta empresa por confidencialidad.

49

Dcsn1bri111ie1110 de Co11oci11,ie1110 ,•11 Bases de Datos

mucho al respecto, sin embargo, en el anexo B se presentan con mayor detalle

las características generales de la base de datos transaccional.

CH.arff

HY.arff lris.arff ,

Kroptarff

f ,. '

MU.arff

SE.arff

Sonar.arff

Soybean.arff

Spambase .arff

Tic data_ categ .arff

Transaccional.arff . •

Tabla 4. L L Corocteríslicos generales de las bases de dolos empleodas en lo tesis

Como se puede observar se emplearon grandes colecciones de datos. La

diferencia que exis1e entre el # de registros originales y el # de registros

empleados radica en el hecho de que algunas bases de datos eran inicialmente

pequeñas, por lo cu:JI, para obtener una base de datos oe mayor tamaño se

repitió un número determinado de v_eces, y de igual manera (justa), cada registro

de esas bases de dotas. La consecuencia de esta acción fue que el N min en

algunas bases de dotas se mantuvo bajo, no proporcional al crecimiento; sin

embargo al usar estos casos de prueba se le dio realismo a la aplicación. El

resultado de ello fue entonces, para algunas bases de datos, una sobre

50

Descubrimiento de Conocimiento en Bases de Datos

estimación de la N min. En el caso de la base de datos tronsaccional2º el número

de registros empleados fue acotado con base en los problemas (limitaciones de

recursos como memoria, tiempo, etc.) que surgieron durante el proceso de

extracción de conocimiento. El límite para las demás bases de datos en cuanto a

# de registros empleados, también se baso en las características de la ejecución.

La excepción a este procedimiento es la base de datos spambase, la cual

corresponde a un posible caso de base de datos pequeña en el muestreo

progresivo. Esta elección se realizó también debido a que la extracción de

conocimiento a pmtir de spambase con un mayor número de registros demandó

una cantidad de tiempo excesiva21 (días) para la generación de·conocimiento. El

motivo de esta demora se relaciona estrechamente a los datos analizados. Al

emplear estas bases de datos en la tesis se tuvo variedao en cuanto a tamaño,

tipos de datos, y sobre todo dominio de aplicación, lo cual sin duda hace que el

algoritmo de muestreo progresivo NSC presente hasta cierto punto buen soporte

de otras bases de datos.

4.2. Descripción general del proceso de pruebas.

Las pruebas realizodas se efectuaron para el muestro progresivo aritmético,

geométrico, NSC, el total de datos, y el N min. En las pruebas se utilizaron las nueve

bases de datos, aplicando todo el proceso diez veces por cada una de éstas (los

resultados obtenidos corresponden a promedios de las ejecuciones). En las

siguientes secciones se describen las pruebas correspondientes a cada fase del

muestro progresivo NSC, así como la comparación entre los métodos

involucrados. Las comparaciones principales se enfocan a la precisión que

alcanzan los métodos, el tamaño de muestra, y el tiempc de ejecución. Estas

comparaciones se realizaron empleando un criterio de par:> común para todos

los métodos en cuanto a precisión. El criterio de paro usado es entonces el

definido por el muesti-eo progresivo NSC (la elección se debe al hecho de que los

otros métodos no especifican su proceso de evaluación de lo precisión). Un punto

20 En el anexo B se detalla la búsqueda enfocada que se realizó para la selección de registros empleados 21 En comparación con las ejecuciones de las otras bases de datos.

51

Descubrimiento de Conocimiento en Bases de Datos

a resaltar es el hecho de que las variaciones en la ejecución de los algoritmos, se

debe a la selección aleatoria de registros de la base de datos, por tal motivo el

proceso se repitió diez veces con la finalidad de analizar un comportamiento

general.

4.3. Selección del tamaño de muestra inicial

Lo que a continuación se presenta es el procedimiento que se realizó para

determinar que la fórmula 3.2.3 corresponde a una buena estimación del tamaño

de muestra inicial para las bases de datos. Se corroboró el cálculo de la

constante C de la fórmula, tomando en cuenta diversos límites de errores en la

estimación (lo que constituyó básicamente el cálculo del factor C). Para hacer

esto se empleó una regresión lineal que tomara en cuento la estimación de N min

de cada base de datos. Esto es dado que se ejecutó uno prueba para conocer

el tamaño de muestra óptimo real, la meta era lograr que ol variar C en la fórmula

3.2.3, la estimación de la N min calculada fuera lo más próxima a la real para cada

base de datos. Sin embargo, esta aproximación siempre se mantuvo por debajo

del valor real, dado que a partir del tamaño de muestro inicial comenzaría el

muestreo progresivo. Por tal motivo el N min calculado siempre fue menor al N

oráculo. Hay que considerar que en algunos casos esto no sucedió así y la

estimación de N min sobrepasó a la N_orácuio. Estos casos mejoraron finalmente la

estimación de C y por consiguiente de N min, dado que en la vida real el

comportamiento esperado de los estimadores no siempre es perfecto, y si el

estimador aquí propuesto contempla dichas situaciones, entonces éste es más

robusto que si se hubiera diseñado para condiciones controlables.

Los rangos de valores que finalmente se obtuvieron experimentalmente de C

presentaron variaciones entre el 0.05 (5 %) y 0.0015 (0.15 %). Esto dio como

resultado N mins calculadas con una aproximación de entre el 86 % y 53 % (68 % en

promedio, desviación estándar de 11.7) a las N_oráculo de cada base de datos.

Esta relación se generalizó para cualquier tamaño de base de datos mediante

una regresión lineal que tomara en cuenta el tamaño de la base de datos y el

52

Desrnbri111ien10 de Co11oci111irn10 e,, !Jases de Datos

mejor porcentaje a partir del total de datos, esto pare que la estimación del

tamaño de muestra inicial fuese adecuada . La regresión lineal dio como

resultado el cálculo del factor C, lo que se muestra en la figura 4.3.1. El ajuste de

la curva se efectuó mediante las nueve bases de datos originales (tamaño real).

limite_error_estimacion

o

o 50000

C = 41.468 Nt ·0479 + O.OS R2 = 0.9361

100000 150000 200000 250000 300000

N total

Figura 4.3.1 . Fórmula para determinar el fac tor C de la fórm•Jla 3.2.3

La regresión lineal aplicada fue de tipo potencial dado que se ajustó mejor a los

datos con un factor R2 = 0.936 l ("confianza de la aproximación"). Esta relación

permite estimar el valor adecuado de C (expresado como porcentaje) acorde al

total de datos en una base de datos. Al emplear este valor de C, en la fórmula

3.2.2 o 3.2.3, se obtiene una buena aproximación (por debajo) del tamaño de

muestra inicial con respecto a la N oráculo (real) . A continuación se presenta una

tabla que muestra la N min calculada y la N ~rácu10, así como la diferencia en

porcentaje que existe entre ambas medidas. La finalidad de la tabla es que

quede claro el hecho de que la fórmula de N min propuesta corresponde a un .

buen estimador. Cabe señalar que la N oráculo se obtuvo al anolizar, por cada base

de datos, la ejecución del proceso de extracción con un incremento constante

de un registro por muestreo. De esta forma se pudo detectar el tamaño de

muestra en el que la precisión se mantuvo constante (para la tesis constante

implica tres decimales fijos).

53

Descubrimie1110 de Conocim,ento en Bases de Datos

Base de Datos Noráculo Valor de C Nmin % de aproximación capufe CH HY

1800 2400 1900

21700

Tabla 4.3.1. Aproximación entre Nrnin y Noráculo, así corno el volor de C asociado.

4.4. Esquema de muestreo

A partir de ese momento la meta fue determinar un esquema de muestreo que

aprovechara la cercanía de la N min calculada a la N c,róculo, con el objetivo de

alcanzar ésta última en el menor número de iteraciones. El esquema de muestreo

se relaciona estrechamente con el criterio de paro con base en el número de

iteraciones, dado que éste establece el tope de muestreos que es posible hacer.

Este dato es importante dado que el esquema de muestreo debe alcanzar la

N_orácuio antes de converger por número de iteracione:i. Este análisis se realizó

experimentalmente con esquemas de muestreo que variaron el factor constante

de la fórmula 3.3. l de 1.05 a 1.15, teniendo los mejores resultados empíricamente

(prueba y error para todas las bases de datos) con el valor de 1.1. La elección de

esta constante se realizó tomando en consideración que se parte de un buen

tamaño de muestra inicidl y se conoce el máximo de iteraciones que deben

realizarse, así como el tamaño N oráculo. Se eligió el esquema de muestreo, que con

base en ajustes realizados en la comparación de métodos, provocó el menor

costo para el muestreo NSC y una buena22 precisión. Este punto es el que

presenta mayor oportunidad de mejora del muestreo NSC: al diseñar un esquema

de muestreo adaptativo que se plantea en el último capítulo de la tesis.

22 Precisión aceptable, debido a que lo que se establece o usa es una relación costo-beneficio.

54

Desc11bri111ie1110 de Conocimiento en Bases de Datos

4.5. Detección de la convergencia por número de itmaciones y medida de

precisión

En esta sección solo se discute la detección de la convergencia con base en una

medida de precisión. debido a que el criterio de paro que verifica el número

máximo de iteraciones (fórmula 3.4.3) corresponde a un cálculo sólido basado en

el costo (orden) de ejecución y que toma en cuenta el e~;quema de muestreo.

La detección de la convergencia con base en la precisión se definió analizando

el comportamiento que mostraron las respectivas curvas de precisión a partir de

cada base de datos. En efecto lo que se determinó fueron los rangos que

corresponden a una pendiente en crecimiento. una pendiente que indica que la

recta de regresión lineal que la forma esta acostándose, y una pendiente que

indica cuando dicha recta se ha acostado.

Durante las pruebas el método empleado demostró ser robusto ante casos

extremos en los cuales la pendiente aumentó inicialmente, posteriormente fue

negativa, y después aumentó para finalmente acostarse. El comportamiento del

método al agre~1ar y quitar puntos. los cuales forman la recta vía la regresión

lineal. permitió que el algoritmo detectara la convergencia del muestreo

oportunamente antes de alcanzar el máximo de iteraciones.

La doble verificación (con la cantidad de puntos actuoles y después del ajuste

según el valor de la pendiente) del método permite que en un mismo punto del

muestreo se pueda alcanzar el criterio de paro sin la necesidad de un muestreo

adicional. Las pruebas realizadas mostraron que para todas las bases de datos un

valor aceptable para el criterio de paro lo constituía una pendiente< 0.01. lo que

indicó que la variación de la precisión fue aceptablemente pequeña

(centésimas) . De igual manera los valores que definen "crecimiento" (pendiente>

0.025) y "casi horizontal" (pendiente entre 0.01 y 0.025) se obtuvieron

empíricamente.

55

Desc11brimie1110 de Conocimirnto en Bases de Datos

Es necesario señcilar que como la ejecución depende de la selección aleatoria

de datos, en ocasiones el método converge antes de alcanzar la N oráculo (sí esto

sucede el tamaño de muestra final es muy próximo al óptimo), sin embargo éste

no es el común de los casos. Así mismo si consideramos un caso donde la N oráculo

corresponda casi al total de datos, entonces puede que el método converja, por

costo, antes de alcanzar la N oráculo . Sin embargo, la detección de la

convergencia con base en estas pendientes constituye un método nuevo, y que

además demostró ser robusto.

4.6. Comparación entre métodos

La comparación entre métodos se realizó con base en los resultados de las

ejecuciones de los diferentes esquemas de muestreo empleados. Cabe señalar

que para el muestreo geométrico se tomó la configuración por default explicada

anteriormente (tamaño base = 400), y para el muestreo ,:iritmético se empleó un

tamaño de muesira inicial acorde al tamaño de cada bme de datos (en general

1000 para las bases de datos aumentadás, y l 00 para las pequeñas). Los

resultados que sei analizaron se explican en las siguientes secciones, pero para

comprender el proceso general es necesario señalar que el algoritmo de

extracción se ejecutó usando el total de datos y el tarraño de muestra óptimo

para cada base de datos. Lo anterior se debe a que para realizar una

comparación se requiere de un punto de referencia. En este caso fue necesario

establecer los límites superior e inferior dentro de los cuales se halla muestreo

progresivo. Estos li'mites en general son:

~ El mejor tamar'io de muestra lo constituye N oráculo

~ El mejor tiempo o esfuerzo de ejecución se alcanza con N oráculo

~ Una precisión aceptable (casi la mejor) se alcanza con N oráculo

~ El tiempo o esfuerzo máximo de ejecución se alcanza con el total de datos

~ En general la máxima precisión se alcanza con el tota! de datos

56

Desc11brimie1110 de Conocimiento en Bases de Datos

ticdaia_categ tr.ans, ccional

' 1 ·1

p.99968 0.93885

1 1

0.98872 0.67538 90.2670B

Tabla 4.6.1. Tie'Tlpos y precisiones resultantes de ejecutar el algoritmo de extracción en cada

base de datos considerando el total de datos y el tamaño de muestra óptimo

4.6.1. Precisión y tamaño de muestra

Como el objetivo del muestreo progresivo es obtener la mayor precisión, al menor

costo, entonces lo que se diseñó fue un algoritmo que alcanzara la N oráculo con el

menor uso de recursos (tiempo, uso de máquina, etc.). Esto con base en un

tamaño de muestra inicial efectivo, un adecuado esquema de muestreo y un

doble criterio de paro. A continuación se presenta la comparación entre métodos

en lo que se refiere a la precisión y tamaño de muestra . Cabe señalar que en la

comparación se loma como punto de referencia a la tabla 4.6. l (límites inferior y

superior). Adicionalmente se abrevian los métodos y medidas evaluadas

mediante la siguiente convención, la cual aplica también en la siguiente sección:

~ t = tiempo [para la tabla 4.6.2. l)

~ p = precisión final

);>- s = tamaño de muestra final

~ AS = muestreo aritmético

);>- GS = mues1reo geometrico

~ NSC = muestreo NSC

~ deltas = comparación, expresada como porcentoje, tomando en cuenta

los límites (labia 4.6.1)

57

Desc11bri111ie1110 de Co11oci111iento e11 En.fes de Datos

Tabla 4.6.1.1. Comparación entre métodos considerando la precisión y el tamaño de muestra alcanzados

Como se puede ver en todos los casos (cuando se ha convergido) el método que

presenta una precisión superior a las demás, y muy próxima a la óptima, es el

muestreo progresivo NSC. Ahora bien en cuanto al tamaño de muestra final se

presentó un problema generalizado. Este problema, co'Tlo ya se mencionó, se

debió a la repetición de registros poro aumentar el tamai10 de las bases de datos

Jo cual mantuvo Jo Noróculo baja y no acorde al crecimiento.

Los problemas generados afectaron a todos los métodos. En el caso del muestreo

geométrico y aritmético el tamaño de muestra final se mantuvo muy bajo (dado

el criterio de poro que aplicó) en comparación con el t..JSC (excepto con la BD

CH aplicando AS), y por consiguiente la precisión alconzada. En el caso del

muestreo NSC el tamaño final se disparó dado que la fói-mula de estimación del

tamaño inicial torna en cuenta el tamaño de la base de datos. Sin embargo, en

tres casos (kropt, ticdata_categ, y transaccional) el tamoño de muestra final fue

mejor que en los otros métodos. Si consideramos el hecho de que el esquema

NSC tuvo un mayor número de aciertos con respecto a los otros esquemas en un

contexto complejo, entonces se puede decir que la ejecución del muestreo NSC

alcanzó mejores tamaños de muestra final que el muestreo aritmético y

58

Desrnbri111ie11to de Co11oci111iento en Bases de Datos

geométrico. Además hay que considerar que si el tamaño de muestra final

excede al óptimo, entonces la precisión será adecuc1da desde los primeros

muestreos; pero el precio a pagar es el tiempo de ejecución.

Para resaltar las ventajas que tiene el muestreo NSC sobre los demás métodos

(principalmente el muestreo geométrico), a continuación se presenta la

comparación entre métodos con las bases de datos originales . Esta comparación

se llevó a cabo para todas las bases de datos excepto la transaccional, dado

que su tamaño original de por si excede al empleado en la comparación

anterior. Los resultados de esta evaluación se muestran en la tabla 4.6. l .2:

file Ntot Norácu/o p_Ntot p_Orác p_AS s_AS capufe CH HY ~ropt MÚ SE 'ticdata-'categ

1800 2400 1900

2,17.00 ~ ,' . 5500 ·.,

. 250(! 4500 ·

0.96990""

o.977;8o_ · · 0.89903 -

0.96651 0.99525 0.99044 0.52898

' .. :1 0.97377 0.89813

0.96042 0.98754

,0.94524 0.27881

',, 1

0.96477 0.8~33°60

Tabhl 4.6.1.2. Comparación entre los métodos, consideranclo la precisión

y el tamaño de muestra alcanzados, para las bases de delos origina les

En esta tabla P _ok indica, en porcentaje, la superioridod total en precisión del

muestreo NSC sobre el geométrico y el aritmético. Y S_ok indica, en porcentaje,

la proximidad de la N min estimada del muestreo NSC, con respecto a la N orócuio:

donde se observan mejores números con respecto a los otros esquemas de

muestreo.

59

Descubrimiento de Conocimiento en Bases de Datos

Como puede verse el muestreo NSC presenta mejores res·.1ltados que el muestreo

geométrico y aritmético, sin embargo cabe señalar que ~n la comparación con

las bases de datos aumentadas, la repetición de registros (lo cual no puede

considerarse un comportamiento común en los datos) impactó finalmente la

ejecución de los métodos de muestreo.

En general el muestreo progresivo NSC superó a los muestreos aritmético y

geométrico en cuanto a precisión y tamaño de muestreo final. Esto con base en

un buen tamaño de muestra inicial, un buen esquema de muestreo, y una

detección de la convergencia con base en un máximo de iteraciones y una

medida de precisión.

4.6.2. Tiempo de ejecución

Las comparaciones de los métodos en cuanto a tiempo se realizaron permitiendo

que la convergencia de los mismos se alcanzara sin tomcr en cuenta la precisión.

Esto es, el criterio de paro para el esquema aritmético se estableció cuando el

tamaño de muestra = 60 % de los datos, el criterio de paro para el esquema

geométrico cuando el tamaño de muestra = 50 % de los datos (ya no el 40 % de

los datos, porque estamos considerando el caso extremo de ejecución para esta

comparación), y el criterio de paro para el muestreo NSC correspondió entonces

al número máximo de iteraciones. Los criterios de pClro para los esquemas

aritmético y geométrico, en cuanto al tamaño de muestra, se definieron por

configuraciones comunes y de default reportadas en la literatura, además el

tamaño de mues1ra inicial utilizado no se afectó en ningún caso.

60

Desrnbrimieu10 de Co11oci111ic11to en Bases de Dalos

Tabla 4.6.2.1. Comparación entre métodos considerando el tiempo empleado en la ejecución

La tabla 4.6.2.1 muestra que, en general, . el esquema aritmético es muy inferior al

geométrico y NSC. También muestra que aparentemente el esquema geométrico

es mejor que el NSC, el cual demanda una cantidad de tiempo semejante a la

ejecución con el total de datos ( esto derivado del problema tratado en la

sección anterior) en algunos casos. Sin embargo, este no constituye un punto

crítico por el cual se considere que el esquema geométrico es superior al NSC, lo

cual se debe a que el tamaño de muestra final del muestreo geométrico queda

muy por debajo del N oráculo y por consiguiente de una buena precisión.

Aquí se nota también la superioridad del muestreo progresivo NSC, donde a pesar

de aparentemente requerir más tiempo de ejecución que lo otros métodos, la

precisión que alcanza es mayor a la de éstos, así como la proximidad del tamaño

de muestra final o N oráculo. La explicación radica en el hecho de que como se

comienza con un buen tamaño de muestra inicial se consume mayor tiempo,

pero se necesitan menos iteraciones (para converger) que en los otros esquemas,

donde la precisión que alcanzan estos últimos es inferior (dado su tamaño de

muestra final} a la precisión del muestreo NSC.

61

Descubrimie1110 de Co11ocimie1110 en Bases de Datos

Nuevamente para entender mejor la comparación entre métodos, en lo referente

al tiempo de procesamiento, es necesario analizar lm ejecuciones con los

tamaños originales de las bases de datos; lo que se muestra en la tabla 4.6.2.2:

file t_Ntot t_Orác t_AS t_GS t_NSC T_ok capufe CH HY

22,102 10.084 12.068

, 3 1.054 '6,519 .

. 2~.9'14

: 1~.007 ' 5.778

··4.847 31 .846

Tabla 4.6.2.2. Comparación entre los métodos, considerando el tiempo

empleado en la ejecución. para las bases de datos originales

En la tabla anterior, T_ok indica, en segundos, la superioridad en tiempo de

ejecución del muestreo NSC. Sin embargo, cabe señalar que en tres ocasiones

esto no se cumplió como tal dado que el esquema geométrico presentó mejores

números; pero al onalizar estos casos se puede observar que para dos de estos la

qiferencia en tiempo de procesamiento radica alrededor de solamente medio

segundo.

En resumen el muestreo progresivo de datos NSC demostró ser superior a los otros

esquemas de muestreo, así como una mejor opción al análisis del total de datos

de una base de datos. En efecto el muestreo NSC se mantiene al margen del uso

de la N orácuio .

62

Desc11bri111iti11to de Co11oci111ie1110 en Bases de Datos

Capítulo 5. Conclusiones y trabajo futuro

Los resultados de lo minería de datos pueden influir en el hecho de que cualquier

negocio adquiera cierta ventaja sobre sus competidores. A pesar que KDD

demanda una inversión fuerte de recursos (tiempo, dinero y personal), las

empresas ponen cada vez más énfasis en su ejecución, gracias a su importancia.

En efecto en un futuro próximo la minería de datos deberó constituir parte crucial

para el éxito de los organizaciones. Debido al incremento en el tamaño de las

bases de datos, el muestreo progresivo de datos es cada vez más relevante.

En esta investigación se diseñó un algoritmo de muestreo progresivo de datos el

cual demostró ser mejor que el análisis completo de una base datos, mejor que el

muestreo progresivo aritmético y geométrico, y muy próximo a los resultados que

genera el análisis de datos del tamaño de muestra óptimo. Los beneficios

obtenidos son en 9eneral la reducción de costos al emplear una menor cantidad

de recursos, y disminuir el volumen de datos por analizar, lo que finalmente

impacta en el tiempo de procesamiento. Este algoritmo denominado NSC debe

su fortaleza a que considera los puntos críticos del muestreo progresivo, que son:

un buen tamaño de muestra inicial, un buen esquema de muestreo, y una buena

detección de la convergencia. Las principales aportaciones de este trabajo son

entonces:

1. En cuanto al tamaño de muestra inicial el muestreo 1\ISC emplea un cálculo

sencillo y el'iciente a partir del total de datos, el cual genera resultados

próximos al tamaño de muestra óptimo.

2. Tornando ventaja de este cálculo el algoritmo genera la programación de

muestreo con un esquema de muestreo que c::msidera tanto la Nmin

estimada, como el número máximo de iteraciones que se pueden

efectuar.

63

Descubrimienlo de Co11oci111ie1110 en Bases de Dalos

3. Este máximo de iteraciones forma parte de la doble detección de la

convergencia de éste algoritmo de muestreo orogresivo. El máximo

número de iteraciones se obtiene mediante una fórmula que considera el

costo de analizar el total de datos vs. el muestreo NSC. Lo anterior se debe

al hecho de que no tiene sentido continuar el muestreo progresivo si es más

costoso que ejecutar el proceso de extracción con el total de datos.

4. La segunda forma de detección de la convergencia corresponde a una

medida de precisión del proceso de extracción. l:sta evaluación aplica

propiamente sobre la curva de precisión que genera el muestreo

progresivo. Lo que hace el muestreo NSC es evaluar la tangente de la

recta de re¡Jresión lineal que se forma a partir de la curva de precisión

(parte actuol de la curva). Este método analiza el comportamiento de la

curva de precisión: aumentando, "casi horizontal", y "horizontal", para

definir la cantidad de puntos a considerar en la regresión. Donde horizontal

implica que se ha convergido. Este procedimiento permite dar soporte a

comportamientos reales de la curva de precisión; como lo es que ésta

zigzaguee.

El muestreo progresivo de datos NSC demostró en general, con base en las

pruebas realizadas. ser superior a los otros esquemas de muestreo. La estimación

del tamaño de muestra inicial es en realidad próxima ol tamaño de muestra

óptimo. El esquemo de muestreo es acorde al tamaño _de muestra inicial y toma

en cuenta el criterio de paro por número máximo de iteraciones (el cual se basa

en costos). El criterio de paro por medida de precisión ano iza el comportamiento

de la ejecución y se adapta a la misma, realizando así una robusta y pronta

detección de la convergencia. El muestreo NSC constituye entonces una técnica

superior de muestreo progresivo de datos, debido a: el cálculo de tamaño de

muestra inicial que realiza, el esquema de muestreo NSC, el número máximo de

muestreos con base en el costo de ejecución, y la detección de la convergencia

por medida de precisión.

64

Desrnbri111ie1110 de Conocimiento en Bases de Datos

El algoritmo NSC se diseñó o probó bajo condiciones reales, lo cual lo hace más

robusto que si se hubiera creado con condiciones controlables. A pesar que el

método mostró buenos resultados, éste tiene partes específicas que pueden ser

mejoradas: El algoritmo no es parametrizable a tal grado como los esquemas

aritmético y geométrico (la ejecución puede ser afectada mediante valores que

reciben los algoritmos), sin embargo puede ser fácilmente modificado en caso de

ser necesario. Hay que considerar que el algoritmo NSC tiene la característica de

ser en cierto grado genérico, para poder ser aplicado sin la necesidad de variar

parámetros en una ejecución particular.

5.1. Trabajo futuro

En si, es importante ejecutar el algoritmo de muestreo NSC considerando diversos

esquemas tales como: diferentes algoritmos de extracción, varios dominios de

aplicación, y un mayor número de bases de datos. Otro punto por desarrollar es el

hecho de que el cálculo de N min no involucre exclusivamen1e la cantidad total

de datos, sino también información que se pueda obtener eficientemente a partir

de la base de datos.

También el criterio de paro con base en la medida de precisión puede ser

perfeccionado. En efecto los rangos de valores de la pendiente definidos para

determinar la convergencia, el "crecimiento", "casi horizontal", y negativa,

pueden ser comprobados o reajustados empleando más bases de datos.

Sin embargo, el mayor trabajo futuro que debe realizarse sobre el muestreo

progresivo NSC, es hacerlo adaptativo (punto importante en el muestreo

progresivo). Este algoritmo puede ser adaptativo en cuanto al esquema de

muestreo y no usar un factor constante de crecimiento (tom_actual = 1 .1 *

tam_anterior). Lo adaptativo se refiere al hecho de que si se conoce el tamaño

de muestra inicial, el máximo de iteraciones, y se tiene una detección de

convergencia con base en una medida de precisión, entonces se puede ir

variando el factor constante para ajustarlo adecuadamente según el

65

Descubrimiento de Conocimienlo en Bases de Dalos

comportamiento de la ejecución. Esto permitirá que el método converja más

eficiente y rápidamente con un nivel de precisión adecuado.

En resumen, el trabajo aquí presentado fue satisfactorio. Se busca que a partir de

esta tesis se incentive el surgimiento de líneas de investigación que apoyen el

desarrollo de técnicm de KDD y mejoren el proceso. Hay que resaltar el hecho

de que los datos son la materia prima que actualmente se debe aprovechar al

máximo para converfüla en una ventaja competitiva (intelinencia de negocio)

que mueva a las empresas en el futuro.

66

Descubrimiento de Conocimiento en Bases de Datos

Fuentes de información

67

Descubrimienlo de Co11ocimie1110 en Bases de Dalos

[1 ]. Adriaans, Pieter; Zantinge, Dolf. 1996. Data Mining. Addison Wesley, p 2.

[2]. Fon, Wei; Wang, Haixun; Yu, Philip; Lo, Shaw-Hwa. lnductive Learning in Less

Than One Sequentiol Data Sean. Machine Learning: Proceedings of the

Nineteenth lnternational Conference, pp 395-402.

[3]. Gu, Baohua; Liu, Bing; Hu, Feifang; Liu, Huan. Efficiently Determine the Starting

Sample Size for Progressive Sampling. In de Raedt, L., Flach, P., eds.: Proceedings

of the 12th European Conference on Machine Learning ¡ECML-01), Springer­

Verlag. 2001 pp 192-202.

[4]. J, Michael; A, Berry; Linoff, Gordon. Mastering Data Mining, the art and science

of customer relationship management. Wiley Computer Fublishing. Segunda

edición, 2000.

[5]. Mendenhall, Scheoffer .. Elementos de Muestreo. Grupo Editorial lberoamérica,

1998, pp 39-76.

[6]. Descubrimiento de conocimiento en bases de oatos. ITESM MOR

(http://doc.mor.itesm.mx/-ADEX/kddsite/kddHome.htm). Septiembre 2003 - Marzo

2004.

[7]. Provost, Foster; Jensen, David; Oates Tim. Efficient Progressive Sampling. In

Knowledge Discovery in Data Minino. 1999, pp 23-32.

[8]. Data mining with open source machine learning software in java. The University

of Waikato (http://www.cs.waikato.ac.nz/ml/weka). Enero 2004- Marzo 2004.

68

Descubrimiento de Conocimiento en Bases de Datos

Association for Computing Machinery. ACM SIGKDD. http://www.acm.org/sigkdd

(Febrero 2004).

Bigus Josep P. Data Mining With Neura/ Networks. McGraw-Hill . 1996.

Guzmán Arenas, A. Estado del Arte y de la Práctica en Minerío de Datos, Análisis y

Crítica. Conferencia Magistral, Cuba, Marzo de 1996.

Huan Liu, Hiroshi Motoda, y Lei Yu. "Feature selection with selective sampling".

Arizona and Osaka Universities.

Saar-Tsechansky Maytal, y Provost Foster. "Active Sampling far Class Probability

Estimation and Rankin i;J''. Texas and New York Universities.

Srinivasan Parthasarathy. "Efficient Progressive Sampling far Association Rules".

Computer and lnformation Science Ohio State University.

Witten lan y Eibe Frank. Data Mining Practica/ Machine Learning Too/s and

Techniques with Java lmplementations. Morgan Kaufmann Publishers, 2000.

69

Desc11brimien10 de Conocimiento en Bases de Daros

Anexos

70

Descubrimiento de Conocimiento en Bases de Datos

Anexo A. Código fuente principal

/* * WrapperNSC.java * Copyright (C) 2004 Alfonso Estrada */

package corn.kdd;

import java.util.*; import weka.classifiersª*; import weka.classifiers.j48.*;

/** * Test Class "7 NSC progressive sampling algorithm. <p> *

* @author Alfonso Estroda (00922073@academ01.ccm.itesm.mx) * @version 1 .O *! public class WrapperNSC {

/** Configurable Values */ private static String fileName; prívate static String dataHeader; prívate static String dataProvideer; prívate static int dataProvideerSize;

/** * Main method for testing this class * * @param String options */ public static voicl main[String [] argv) {

double time; System.out.println("\nRunning ... "); fileName == "transaccional.arff"; dataHeader = "headerTransacc.txt"; dataProvideer = "dataTransacc.txt"; dataProvideerSize = 265691; /** Running J48 using NSC progresive sampling * / time= runt~SCProgressiveSampling[J; System.out.println["Total Time: " + [int)([[time)/1000)/60) + " min. " +

((time)/1000)%60 +"seg."); }

/** * Method for running J48 using NSC progresive sampling

71

Desrnbrimicnto de Conocimielllo en Bases de Datos

* * @return the time */ private static double runNSCProgressiveSampling() {

double tini, tfin, ttot = O; int actua1Size; NSCProgressiveSampling schedule = new

NSC ProgressiveSampling ( dataProvideerSize); while ((actua1Size = schedule.next()) != -1) {

System.out.println("Sampling: "+ actualSize); System .out .println ("Generating File ... "); while(true) {

if (SamplefileGenerator.f¡eneratefile(actualSize, dataProvideerSize, dataHeader, dataProvideer, fileName)== 1)

}

/**

}

break; System .out .println ("Error: SamplefileGenerator ... ");

} System.out.println("NSC_Progressive_Sarnpling:"); String[] command = {"-t", fileName, "-i", "--o", "-v"}; tini = System.currentTimeMillis() ; double wAvgs = getWeightedAverages(command); tfin = System.currentTimeMillis(); ttot+= (tfin-tini); System.out.println(''\tPWA: "+ wAvgs); schedule .setCurrent Precision (w A vgs);

return ttot;

* Method for getting the statistic: precision * * @param the command to be executed * @return the statistic */ prívate static: double getWeightedAverages(String[] command) {

double wAvgs; Evaluotion_Statistics info = new Evaluation_Statistics(); // console output of J48 ... String result = null; try {

result = Evaluation.evaluateModel(new J48(), command, info); } catch (Exception e) {

}}

System.err.println( e.getMessage()); } wAvg:; = info.getPrecisionWeightedAverage(); return wAvgs;

72

Descubrimiento de Conocimiento en Bases de Datos

/* • NSC ProgressiveSampling.java • Copyright ( C) 2004 Alfonso Estrada */

package com.kdd;

/** * Class that implement: NSC Progressive Sampling. <p> *

* @author Alfons~ Estrada I00922073@academ0l .ccm.itesm.mx) * @version l .O */

public class NSCProgressiveSampling {

/** Points to be used in the precision regression (the begining is the last used point) */

int precisionPoints;

/** Current Size/Position of the Schedule * / int currentSize;

/** To tal size of the data provideer * / int tota1Size;

/** Sample size growing percentage - Sampling schene * / double xFactor = l. l;

/** Indica tes 1he end of the algorithm * /

boolean endAlgorithm;

/** Precisions 9ained given a sample size * / double [] precisions = null;

/** Sampling schedule * / double[] samples = null;

/** * NSCProgressiveSampling Constructor *

* @param toto1Size of the data provideer */ NSCProgressiveSampling(int tota1Size) {

this.toto1Size = tota1Size; precisionPoints = 2; endAlgorithm = false; generateSchedule (); currentSize = O;

73

Desc11brimie11to de Conocimieno'o e11 Bases de Datos

}

/** * Generates the samplíng schedule */ prívate voíd 9enerateSchedule() {

ínt cur'S = calculateNmín(); ínt regEnd = calculateMaxlteratíons(currS); // regEnd = num max iterations -> regEnd + 1 : síze of the array

because regEnd stmts from O

/**

samples = new double[regEnd+ 1 ]; precísíons = new double[regEnd+ 1 ]; for (int x=O; x<=regEnd; x++) {

samples[x] = currS; currS = (int) ( currS * xFactor);

}

* Max. lteratíons * * @return max íteratíons */ prívate ínt calculateMaxlteratíons(int nminC) {

double val= Math.log(0.1 * Math.pow((double) totalSize/nmínC, 1.3) + 1) / Math.log( 1.1) -· 1;

return (ínt) Math.round(val) ;

!** * Sets the current Precision of a model * * @param the current precísíon generated with the last sample size */ public void setCurrent Precision(double precision) {

if (precisíons == null) return;

precisíons[currentSíze-1] = precísion; // Possíble schemes íf (precísion == 1)

endAlgoríthm = true; // There are more than one point; currentSize >== 2 if ( currentSíze-1 >= 1) {

// check slope double val= evaluateConvergence(); if ( acceptableConvergence(val))

endAlgoríthm = true; else {

74

Desc11brimie11to de Conocimiefllo en Bases de Datos

by 2)

by l)

} }

}

/**

/ / there are only 3 cases switch(analyzeConvergence(val)) {

case -1: {

/ / negative slope // more poin··s, untill currentSize (2

int pP = precisionPoints + 2; if (pP > currentSize)

precisionPoints = currentSize; else

precisionPoints += 2; } break;

case O: {

/ / flat slope // more points, untill currentSize ( l

int pP = precisionPoints + l; if (pP > curren1Size)

precisionPoints = currentSize; else

precisionPoints ++; } break;

case l: {

/ / positive slope // less precisionPoints, untill 2 int pP = precisionPoints - l; if (pP > 2)

precisionPoints --; else

precisionPoints = 2; } break;

}; val= evaluateConvergence(); if (acceptableConvergence(val))

endAlgorithm = true;

* This method returns the value wich will be used to detect the convergence * * @return the slope of the regression line defined by precisions[J (y) and

samples[J (x) using precisionPoints */

75

Desrnbrimiento de Conocimiento en Bases de Datos

private doub1e evaluateConvergence() { double s[] = new double[precisionPoints]; double p[] = new double[precisionPoints]; int x = O, y = O; // ever: y>= x for (x = precisionPoints - 1, y= currentSize - 1; x>:=O && y>= 1; x--, y--) {

s[x] = (samples[y]-samples[y-1 ])*1 OO.O/to1a1Size; p[x] = precisions[y];

} // Base Case (first 2 points): we hove to calculc1te a sample size point

befoe nmin cale.

}

/**

J / Or when all the data must be used to calculcite the regression ... // ever currentSize >= 2, also precisionPoints if (currentSize == precisionPoints) {

s[O] = ((int)(samples[O]-samples[0]/1.05))*100.0/totalSize; p [O] = precisions [O];

RegressionCalculator re= new RegressionCalculator(s, p); return rc.getSlope();

* This method checks if the end criterio has been achieved *

* @param val the slope of the regression line (convergence criterio) * @return true/false */ prívate boolecin acceptableConvergence(double val) {

val= Moth.abs(val); if (val< 0.01)

return true; return false;

}

/** * This method checks the behaviour, to achieve the end criterio * * @param val the slope of the regression line (convergence criterio) * @return -1: negative slope, O: flat slope, l: positive slope */ private int analyzeConvergence(double val) {

if (val< O)

}

return -1; if (val>= 0.01 && val<= 0.025)

return O; return l;

76

Descubrimiento de Conocimiento en Bases de Datos

/** * Returns the next sampling size * * @return the next sampling size */ public int next() {

}

/**

if (samples == null) return -1;

int val== O; if (endAlgorithm)

return -1; val= (int) (samples[currentSize]); currentSize++; if (currentSize == samples.length)

endAlgorithm = true; return val;

* Returns the final sampling size *

* @return the final sampling size */ public int getFinalSize() {

if (endAlgorithm)

}

/**

return (int) (samples[currentSize-1 ]); return -1;

* Calculates the aprox. Nmin ... * * @param tota1Size * @return the aprox. nmin given the tota1Size. nminCalc = (int) (1 /((4 *

Math.pow( 41.468 * Math.pow((double)tota1Size, -0.479) + 0.05, 2) / 10000) + ( 1.0 / tota1Size)JJ;

}

*/ private int calculateNmin(){

}

double in= 41.468 * Math.pow((double)tota1Size, -0.479) + 0.05; double op 1 = 4 * Math.pow(in, 2) / 10000; double op2 = 1 .0/tota1Size; return (int) (1 / (opl + op2));

77

Descubrimienro de Conocimienro en Bases de Daros

Anexo B. Base de dc:itos de transacciones empleada.

Los datos que se manejaron corresponden a las transocciones de siniestros

vehiculares generadas por una compañía de seguros. Una vez que algún

"accidente" tiene lugar, el agente a cargo recopila la información del mismo

para que posteriormente sea almacenada en la base de dotos.

La base de datos tiene un tamaño superior a 2 Gb, en formato Microsoft SQL

Server 2000. Debido a esto fue necesario migrar23 los dalos hacia archivos de

texto mediante las herramientas del DBMS. Por motivos de optimización los datos

que fueron migrados correspondían a la selección final de los datos para la

minería. Las tablas que constituyen la estructura de la base de datos son las

siguientes:

~ AGENTE ~ REGISTRO_ VEHÍCULO ~ CATEGORIA ? COBERTURA >, CLAVE_FLOTILU\ ~ DEDUCCION_DM ~ DEDUCCION_RT ? DESCUENTO >" DISPOSITIVO_SEGURIDAD >" ESTADO >" FORMA_PAGO >" PAQUETE >" TONELAJE >" TRANSACCION );;, uso

En esta estructura la mayor parte de las tablas se rela:::::ionan con la tabla

transacciones. En efecto esta fue la tabla objetivo a partir de la cual surgió la

selección de datos oara KDD. No es necesario dar la descripción de todas las

tablas24 debido a que en los atributos de la tabla transacciones se da

23 Para un adecuado funcionamiento de las herramientas, la migración requirió ajt.stes tales como nombres de campos válidos 24 Aquí también se involucran cuestiones de privacidad

78

Desc11bri111iento de Conocimiento en Bases de Datos

implícitamente el significado de las demás; que en sí la mayor parte son

catálogos relacionodos vía llaves foráneas.

La tabla transacciones tiene una extensión de más de 5 millones25 de registros;

motivo por el cual la partición y proyección de datos fue indispensable. Un punto

a destacar, antes de describir la tabla de transacciones, e5 el hecho de que los

datos que serán mostrados han sido alterados de tal modo que se respete la

confidencialidad de la información. Los datos más importantes de la tabla

corresponden a dotos de la compañía de seguros, dotos de su personal,

cantidades monetarias, y servicios ofrecidos por la compoñía a sus clientes. El

esquema de protección de datos se estableció en conjunto con los proveedores

de la información, con el objetivo de evitar una posible desventaja (estrategia de

negocio) ante sus competidores en el caso de que lo información fuese

distribuida incorrecto y deslealmente26 .

A continuación se do la descripción del significado que tie'len, para el dominio

de aplicación, los atributos que forman la tabla transacciones, así como los tipos

de datos y características principales de la misma.

~ AAAAMM - Fecha de emisión de la póliza (formato año y mes) ~ AGTE - Clave del agente que atendió la petición ~ FLOT - Si el automóvil pertenece a una flotilla o no (individual) ~ CCOB - Clave de la cobertura que se maneja ~ DISP - Si el vehículo tiene algún dispositivo de seguridad ~ AMIS - Numero de registro vehicular ~ MODELO - Modelo del automóvil ~ DEDDM - Deducible de daños materiales ~ DEDRT - Deducible de Robo Total ~ USO - Tipo de uso del automóvil: por ejemplo mensajeri'a, taxi, etc. ~ SERV - Tipo de servicio del automóvil: particular u otro ~ DESCUENTO - Si la póliza presenta algún descuento ~ MONEDA- La moneda con la cual se realiza el pago de la póliza ~ ESTADO - El estodo donde fue emitida la póliza ~ PAQUETE - El tipo de paquete que se tiene: sea plus, limitada, etc. ~ FORMAPAGO - La forma como se realiza el pago de la póliza: pago a un

mes, trimestre, etc.

25 En el ambiente de bases de datos se considera "grande", a partir de 1 millón de registros 26 El objetivo de este documento es académico

79

Desc11brimie11to de Conocimiento en Bases de Datos

~ TARIFA - La tarifa de la póliza -, DEDRCLUC - El deducible de responsabilidad civil ~ DEDRCPASAJl:RO - El deducible de responsabilidad civil por pasajero >- TARJETA - Nur1ero de tarjeta vehicular >- ZONAAUTOS >- ZONAOTROS ', CARGA - Tipo de carga que maneja el vehículo , PERGRACIA .,.. El periodo de gracia que se tiene para realizar el pago

correspondiente >- [Prima Emitido] - Prima emitida de la póliza (no cobrado) -,, [Prima deven9ada] - Prima devengada (lo cobrado) ~ [Numero Siniestros] - Número de siniestros ;... [Monto Siniestros] - El monto de siniestros ., [Pago de Siniestros] - El pago del siniestro ;... [Gastos Siniestros] - Los gastos del siniestro -, Salvamentos -- El salvamento de la póliza -, Recuperaciones - Las recuperaciones de dinero de lo póliza -,, Reserva -, [Reserva de solvamentos] - La reserva en dinero de solvamentos >- [Numero Afectación] - Número de afectación para e siniestro -, [Numero de incisos] - El apartado de la póliza -,, [Incisos Afectodos] - Los incisos afectados por cambios en la póliza

Nombre de columna 1 Tipo de datos 1 Longtud I Permiti' valores nulos I Nombre de cokimna 1 Tipo de d,itos 1 Longitud I Permiti' valores nulos AAAAMM char 6 V TARJETA char 1 V AGTE char s ZONAAUTOS char 2 V FLOT char ZONAOTROS char 2 V CCOB char 2 CARGA char V DISP char 2 PERGRACIA char V AMIS char s PrimaEmitida decimal 9 V MODELO char 4 PrimaDevengada decimal 9 V DEDDM char 2 V NumeroSiniestros decimal 9 V DEDRT char 2 V MontoSiniestros decimal 9 V uso char 2 PagoSiniestros decimal 9 V SERV char 2 V GastosSiniestros decimal 9 V DESCUENTO char 2 V Salvamentos decimal 9 V MONEDA char 2 V Recuperaciones decimal 9 V ESTADO char 2 V Reserva decimal 9 V PAQUETE char 2 V ReservaSalvamentos decimal 9 V FORMAPAGO char V NumeroAfectacioo decimal 9 V TARIFA char 4 V Numerolncisos decimal 9 V DEDRCLUC char 3 V IncisosAfectados decimal 9 V DEDRCPASAJERO char 3 V !

Atributos a Usar.

Es importante señalar que por motivos de extensión no pueden ser detalladas las

numerosas pruebas que se requirieron para refinar la selección de datos, solo se

presenta la elección final de información (registros) y atributos empleados. Es por

ello que, con base en la experiencia/aprendizaje adquiridos en esta

80

Desc11brimiento de Conocimiento en Bases de Dalos

investigación, se efectuó una selección de campos que contempló a los de

mayor impacto pam el proceso27 de KDD. Estos campos son los siguientes:

)" FLOT )" uso ~ SERV )" ESTADO y FORMAPAGO ,.,

CARGA , » CCOB >" PAQUETE

La selección de datos (registros) se llevó a cabo aplicando la siguiente consulta.

Esta consulta tuvo ICJ función de filtrar la información contenida en la base de

datos, con base en un previo análisis28 de la misma.

SELECT FLOT, USO, SEl~V. ESTADO, FORMAPAGO, CARGA. CCOB, PAQUETE FROM TRANSACCIOt--JAL WHERE FLOT <> " AND USO<>" AND SERV <>" ANO ESTADO<>" ANO FORMAPAGO <> " ANO CARGA <> " ANO CCOB <>" ANO PAQUETE <> ";

Datos de Ejemplo.

A continuación se proporciona una muestra de los registros de la tabla

transacciones con el fin de ilustrar la importancia de los dotos y de una buena

selección de los mismos, así como del entendimiento del dominio de aplicación.

Esto enfatiza el hecho de que el objetivo de la minería de datos es extraer

modelos valiosos y óptimos a partir de datos adecuados. Adicionalmente se

busca que el lector t13nga una mayor idea del tipo de datos que se manipularon:

27 Particularmente el muestreo progresivo de datos 28 Información incorrecta, faltante, incongruente, etc.

81

De.<c11bri111i1•1110 de Co11oci111ie11to 1•11 Rases de Datos

valores continuos y discretos; números enteros y decimales; caracteres y cadenas;

etc.

AAAAMM AGTE FLOT CCOB DISP AMIS MODELO DEDDM DEDRT USO SERV 200207 9508 1 98881 2001 5 10 19 2 200207 9508 2 98881 2001 5 10 19 2 200207 9508 3 98881 2001 5 10 19 2 200207 9508 4 98881 2001 5 10 19 2 200207 9508 12 98881 2001 5 10 19 2 200207 9_508 15 98881 2001 ' 10 19 2 200207 9508 1 ,98881 2002'. 10 19 2

' -~ 10 ' ' '19 > 200207 , 9508 2 98881 2002 2'

200207 9508 3 , 98881 2002 10 19 2 200207 9508 4 , · 98881 2002 . 5 \. 10 19 2 200207 9508 12 ' 98881 2002 5 10 19 2 200207 9508 15 98881 2002 5 10 19 2 200207 9711 F 2 81354 1993 5 10 6 1 200207 9711 F 4 81354 1993 5 10 6 1 200207 9711 F 12 81354 1993 5 10 6 1 200207 9711 F 3 81354 1993 ·5 10 6 1 . 200207 9711 F 1 . '.) 81354 ,1993,,, ,,, ·5· 10 6 " 1 '

1994 .. ,'", 5 . 10 . ' 200207 9711 F 4 81354 . 6 ' ' " 1 200207 9711 F 81354 1994.:,'.'' 5 10 6 1 200207 9711 F .. 81354 1994 : . 5 10 6 1 200207 9711 F 81354 1994)', . ,5 · 10 6 ··, t . 200207 9711 F .''81354 -1994' ,5 10 6 '. ' 1 l 200207 20477 . 790 1999 , 5 ' ' 10 1 :.; { 1· 200207 20477 . 790 1999 · 5 ' 10 1 1 .

82

ncsc11bri111ic1110 de Co11oci111icnro en Bns<'s de Daros

20 20 20 15 15

o o o o o

28 28 28 10 10

21 T 21 T 21 T 21 T 21 T

203 203 203 203 203

25 25 25 o o

DEDRCPASAJERO TARJETA ZONAAUTOS ZONAOTROS CA GA PERGRACIA o 75 o o o 75 o o o 75 o o o 75 o o

'.º .· 75 . o , o ro 75 ¡: o: \,.o. o 75 Ü · o o 75 o o o 75 ~;' , ;, o o o 75 o o o 75 o o o 75 o o o o A o

o A o, o o o o o o

o o

. o/ k

o o o o

83

Desc11brimi1?11/o de Co11oci111ien10 e11 Bases de Dalos

9364.02 o 3632.95 o

162140.03 o 7269.8.71 o 91099.69 o

o o

o. o o, o o

150 10000

o: O , , o o

Num roAfectacion Numerolncisos lncisosAfectado .. , . ;él' o o o cr o o ci ' o o

o o 1 J: '

'}

1 1 1 1 1 4

4

84

Desc11bri111ie1110 de Co11oci111ie1110 e11 Bases de Dn1os

85