Minería de datos (página 4)

Glosario de Términos Básicos

Censo de población: es un conjunto de operaciones que reúnen, elaboran y publican datos demográficos, económicos y sociales correspondientes a todos los habitantes de un país o territorio, referidos a un momento determinado o a ciertos períodos dados.

Muestra: una muestra es un conjunto de casos o individuos procedente de una población estadística que cumple las siguientes características: La muestra debe ser representativa de la población de estudio. Para cumplir esta característica la inclusión de sujetos en la muestra debe seguir una técnica de muestreo.

Estadística: la estadística es la rama de las matemáticas que describe los fenómenos donde no hay un componente absoluto, es decir es discreta, y sus modelos son estocásticos. La estadística ayuda a todas las demás ciencias a generar modelos matemáticos "generales" donde se haya considerado el componente aleatorio. Clustering: Es la agrupación que realizan los buscadores para no mostrar más de un cierto número de páginas de una web para una determinada búsqueda.

Data Warehouse: un Data Warehouse (DW) es un almacén o repositorio de datos categorizados, que concentra un gran volumen de información de interés para toda una organización, la cual se distribuye por medio de diversas herramientas de consulta y de creación de informes orientadas a la toma de decisiones.

Inteligencia: la inteligencia es una facultad especial propia de ciertas clases de seres orgánicos que les otorga, juntamente con el pensamiento, la voluntad de obrar, la conciencia de la existencia y de la Individualidad, así como también los medios de establecer relaciones con el mundo exterior y de atender a sus necesidades.

Inteligencia Artificial: se define la inteligencia artificial como aquella inteligencia exhibida por artefactos creados por humanos (es decir, artificial). A menudo se aplica hipotéticamente a los computadores. El nombre también se usa para referirse al campo de la investigación científica que intenta acercarse a la creación de tales sistemas.

Árbol de decisión: gráfico que muestra las posibilidades que existen ante un hecho determinado. Cada decisión se convierte en un "nodo" del que se generan "ramas" que muestran las opciones disponibles. A su vez, éstas crean nuevas "ramas" con lo que se conforma el árbol"

Base de datos: conjunto de registros (unidades de información relevante) ordenados y clasificados para su posterior consulta, actualización o cualquier tarea de mantenimiento mediante aplicaciones específicas.

Varianza: en teoría de probabilidad y estadística la varianza es un estimador de la divergencia de una variable aleatoria de su valor esperado . También se utilizan la desviación estándar, la raíz de la varianza.

Covarianza: en teoría de probabilidad y estadística la covarianza es un estimador de la dependencia lineal de dos variables aleatorias.

Desviación estándar: en probabilidad y estadística, la desviación estándar es la medida más común de dispersión. Dicho de manera sencilla, mide qué tan dispersos están los valores en una colección de datos.

Indicador: relación entre dos variables que sirve para medir un resultado. Por ejemplo: indicador de cobertura número de personas atendidas/número de solicitantes de un servicio.

Afeitadora de Occam: principio de la ciencia que determina que cuando todas las condiciones son iguales, se prefieren las teorías simples. Es decir, la mejor teoría científica es aquella que explica todos los hechos y tiene el menor tamaño. Como Einstein sostuvo: "Todo debe hacerse lo más simple posible, pero no más simple que eso".

Aprendizaje Supervisado: en el aprendizaje supervisado o aprendizaje a partir de ejemplos, el experto define clases y provee ejemplos de cada una. El sistema debe obtener una descripción para cada clase. Cuando el experto define una única clase, provee ejemplos positivos (pertenecen a la clase) y negativos (no pertenecen a la clase). En este caso, los ejemplos importantes son los cercanos al límite, porque proveen información útil sobre los límites de la clase.

CAPÍTULO III

MARCO METODOLÓGICO

1. Naturaleza de la Investigación

   Con el propósito de desarrollar un sistema que permita el estudio de minería de datos en la base de datos de censo de población del estado Lara utilizando árboles de decisión para clasificar los hogares con la finalidad de calcular los indicadores de pobreza, se realiza un estudio enmarcado en la modalidad de investigación de campo en el ámbito de proyecto factible.

   La Universidad Fermín Toro a través del Manual de Normas para la presentación de trabajo de grado de la Universidad "Fermín Toro" (2001) define la modalidad del proyecto factible como "una propuesta basada en la factibilidad para la resolución de un problema dado. Puede apoyarse tanto en la investigación de campo como documental o un diseño, que incluya ambas modalidades. Puede referirse a la formulación de políticas, programas, técnicas, métodos, procesos", (p.6).

   Las técnicas que serán utilizadas para la recolección de información y la puesta en marcha del mismo, fueron clasificadas según el nivel de conocimiento.

   La presente investigación se apoya en una indagación documental, ya que se recolectó información, obtenida en diversos libros, páginas Web, trabajos de grado relacionadas con las técnicas de inteligencia artificial y censos de población. Se utilizó la investigación de campo debido a que se realizó la recolección, procesamiento y análisis de los datos directamente de la realidad, para lograr de esta forma la obtención de información objetiva y concreta.

   Fases de la Investigación

   Para tener un orden progresivo de las acciones y actividades que se realizaron durante el desarrollo de la prepuesta, la misma se divide en las siguientes fases:

   Fase I: Diagnóstico

   En esta fase se recolectó toda la información necesaria para el análisis del problema. Se utilizó la investigación documental en varias fuentes bibliográficas especializadas en inteligencia artificial, aprendizaje automático y minería de datos, además se captó información proveniente de expertos especializados en el cálculo de indicadores sociales tomando como referencia bases de datos censales, otra herramienta que se utilizó fue la Internet, visitando varios sitios Web a través de buscadores como Altavista, Google, Monografías, localizando información relacionada con el tema de investigación. En esta fase se pudo determinar la necesidad de contar con una herramienta distinta a las tradicionales para analizar base de datos censales.

   Fase II: Estudio de la Factibilidad

   El desarrollo de esta fase representa un paso importante, ya que involucra la toma de decisión acerca de si un proyecto es viable o no, se justifican con detalle todos los agentes que participan o pueden afectar al proyecto, por tanto se determina la factibilidad técnica, económica y operativa.

   Factibilidad Técnica

   Según Llorens (1991). "La factibilidad técnica corresponde a un estudio de la funcionalidad, el rendimiento y las restricciones que puedan afectar a la posibilidad de un sistema aceptable" (p.28).

   En el desarrollo de la investigación se utilizaran recursos de software, hardware, soporte técnico y humano, ya que es requisito indispensable porque conforman la base tecnológica requerida y empleada para el diseño de un sistema basado en minería de datos.

   Para el desarrollo y la instalación de este sistema, los requerimientos indispensables son los siguientes:

   Cuadro 2

   Requerimientos Mínimos de Hardware

   

   Fuente: Borges (2006)

   Cuadro 3

   Requerimientos Mínimos de Software

   

   Fuente: Borges (2006)

   Para el desarrollo de este sistema se utilizará la herramienta de software C++ Builder, lenguaje de programación de alto nivel orientado a eventos y funciona bajo una plataforma de 32 bits en el sistema operativo Windows 98/Me/2000/XP.

   C++ Builder

   C++ Builder es una aplicación que proporciona un entorno de trabajo visual para construir aplicaciones Windows que integra distintos aspectos de la programación en un entorno unificado o integrado. La integración y facilidad de manejo hace que sea una herramienta indispensable para el desarrollo rápido de aplicaciones.

   Microsoft Windows XP

   Dentro de lo que es Windows XP, existen dos versiones, casera (Home Edition) y la versión Profesional (Professional). En este caso se utilizará Windows XP Professional, ya que ayuda a realizar más tareas en la computadora y en la Internet, proporcionando una interfaz amigable para el usuario y facilidad de uso.

   Es posible el impulso de este sistema debido a que los módulos a desarrollar y el rendimiento necesario, es técnicamente viable con los recursos anteriormente mencionados, además existe disponibilidad en el mercado de estos recursos, tanto de software, hardware y de personal calificado.

   En esta fase se presenta el análisis económico de los recursos necesarios para el desarrollo e implementación del sistema, tomando en cuenta los aspectos señalados en el estudio técnico, determinando la viabilidad del proyecto ajustable a los recursos humanos materiales y económicos para llevarlo a cabo.

   Para verificar la factibilidad de este proyecto, se consideraron los recursos de hardware y software necesarios. En cuanto al hardware, solo se requerirá de un computador para su funcionamiento. Este computador puede adquirirse en el mercado, al igual que sus componentes (ver cuadro No 4).

   Cuadro 4

   Precio de Componentes de Hardware

   Descripción			Costo (Bs.)
   CPU Pentium IV 2.66 Ghz			364.232
   256 de Memoria RAM			65.316
   Disco Duro 80 GB			163.652
   Monitor SVGA			259.918
   Teclado, Ratón			32.114
   Unidad de CD-ROM			38.765
   Floppy disk 3 ½			18.425
   Impresora HP Deskjet 3920			123.205
   Regulador de Voltaje			39.903
   Tarjeta Madre Foxconn 661MX			126.077
   Total			1231.607

   Fuente: Micro Max C.A (2006)

   En cuanto al software, se utilizará Windows XP como plataforma o sistema operativo, Base de datos donde se encuentra almacenada la información requerida y Lenguaje C++ Builder para diseñar los diferentes módulos que conforman el sistema y la interfaz con el usuario. La combinación de este software ofrece un ambiente interactivo y amigable para el mismo.

   Cuadro No 5

   Costos Aproximados del Software

   Componentes del Software				Costo (Bs.)
   Microsoft Windows XP Profesional				270.000
   Borland C++ Builder 2006				2.343.500
   Total				2.613.500

   Fuente: Borges (2006)

   Según Pressman (1997). Para obtener los costos asociados con el desarrollo de un sistema basado en computadoras, el análisis debe estimar cada costo y usar después el desarrollo y los costos sucesivos para determinar la recuperación de lo invertido, un punto de beneficio cero y un período de rentabilidad.

   Por otra parte, el sueldo de un programador en el INE es de 1.220.000 Bs. mensuales, lo que representa un total de 3.660.000 Bs. en tres meses.

   En la tabla que se presenta a continuación (ver cuadro No. 6), se observa detalladamente cada uno de los recursos necesarios con sus respectivos precios, y la suma total de todos los recursos.

   Cuadro 6

   Relación de precios. Factibilidad económica

   Recursos						Precio (Bs.)
   Microsoft Windows XP Profesional, Borland C++ Builder 2006						2.613.500
   Sueldo del programador						3.660.000
   Hardware requerido						1.231.607
   Total						7.505.107

   Fuente: Borges (2006)

2. Factibilidad Económica
3. El INE dispone de el hardware y software requerido lo que reduce notablemente los costos y aumenta la factibilidad del proyecto.

   Las estrategias aplicadas en el diseño del sistema basado en minería de datos, son orientadas para que el uso del sistema sea de una manera fácil y amigable para ganar la atención e interés del usuario, de tal manera que pueda ser usado por diferentes usuarios del área de estadísticas, que tengan un conocimiento básico de computación. Además el sistema contará con un manual de usuario que guiaran al mismo en el manejo del sistema. Por otra parte es conveniente resaltar que el proceso de minería realizado por el sistema es totalmente transparente para el usuario por lo que el mismo no necesita conocer los detalles para poder operar el sistema.

4. Factibilidad Operativa

   Esta fase es importante, ya que aquí se definen y se aplican los recursos especificados anteriormente y se analizan los resultados obtenidos en las fases anteriores para la elaboración y ejecución del sistema.

   El primer paso a seguir para la realización del sistema es el levantamiento de la información, referente a los sistemas basados en minería de datos y la aplicación de este en el análisis de la base de datos del censo de población del Estado Lara.

   Luego se procederá al diseño de los módulos encargados de realizar la minería de datos basados en los algoritmos ID3 y C4.5 los cuales permitirán hacer una clasificación de los hogares de acuerdo a ciertas características, lo cual permitirá construir los índices de pobreza del Estado Lara.

5. Fase III: Diseño del Proyecto

   1. Diseñar un sistema que permita la aplicación de minería de datos aplicando árboles de decisión en la base de datos de censo de población del Estado Lara.

      2. Objetivos Específicos
   2. Objetivo General
6. Objetivos del Diseño

1. Diseñar los módulos de opciones. Estos módulos realizan todas las operaciones comunes al ID3 y al C4.5, como el cambio de la tabla de datos, la elección de la tabla, sobre la cual se desea evaluar el rendimiento, entre otros.
2. Diseñar los módulos de minería de datos. Son aquellos que construyen los árboles y las reglas de decisión a partir de las tablas.
3. Diseñar el módulo de ayuda. En este módulo el usuario podrá aclarar cualquier duda sobre la información del sistema.
4. Diseñar el módulo de evaluación. Este módulo permite evaluar los resultados obtenidos con el ID3 y el C4.5 respectivamente.
5. Diseñar el módulo de clave de acceso. Este módulo maneja toda la información sobre los usuarios del sistema.

Al tener listo el diseño, se procederá a diseñar los diferentes algoritmos que permiten manipular el Sistema de Minería de Datos Aplicando Árboles de Decisión en la Base de Datos de Censo de Población del estado Lara.

Culminando todos los procedimientos antes descritos, se puede comenzar el desarrollo del proyecto.

• CAPÍTULO IV

ANÁLISIS DE RESULTADOS

Desarrollo del Proyecto

Para el desarrollo del sistema Estudio de Minería de Datos en Base de Datos de Censo de Población Aplicando Árboles de Decisión (SIMIDACE Tree), se hizo necesaria la elaboración de cuatro módulos, el sistema está estructurado de la siguiente manera,(ver figura No 5).

Figura 5

Estructura de SIMIDACE Tree

SIMIDACE Tree, tiene como una de sus finalidades la clasificación de los hogares de acuerdo a ciertas características, lo cual permitirá construir los índices de pobreza del Estado Lara con la base de datos del censo 2001.

Cabe destacar que la minería de datos se aplica cuando existe una gran acumulación de datos y es imposible realizar el procesamiento manualmente, por lo tanto esta tecnología facilita la recolección y acumulación de datos, estos datos ocultan tendencias que se pueden descubrir por medio de los algoritmos ID3 y C4.5 que usan la técnica de árboles de decisión, la cual es una forma de representación sencilla, muy usada entre los sistemas de aprendizaje supervisado, para clasificar ejemplos en un número finito de clases. Se basan en la partición del conjunto de ejemplos según ciertas condiciones que se aplican a los valores de los atributos. Su potencia descriptiva viene limitada por las condiciones o reglas con las que se divide el conjunto de entrenamiento.

Para realizar la minería se cumplieron una serie de etapas que pertenecen al proceso de minería de datos.

Etapas para la Minería de Datos

Comprensión del problema

En esta etapa se centra la comprensión del problema y en concretar los objetivos perseguidos. El problema surge de la necesidad de contar con un software que permita la construcción de indicadores estadísticos como los índices de pobreza con un menor esfuerzo manual y evaluar cantidades enormes de datos.

1. En esta etapa se trabajó con la base de datos del censo de población y vivienda del Estado Lara, esto con la finalidad de que el sistema detecte automáticamente conjuntos interesantes no explícitos en los datos para formular hipótesis sobre información oculta. Tras el estudio de la base de datos, se efectuó una descripción de dichos datos, desarrollando una exploración general sobre los mismos y finalmente verificar la calidad de los datos.

2. Comprensión de los datos
3. Descripción de los datos

En la exploración de la base de datos del censo del Estado Lara, se encontraron tres (3) tablas en formato mdb, las cuales contienen la información sobre las viviendas, hogares y personas del estado Lara. La cantidad de registros de cada una de las tablas se especifica a continuación:

1. Viviendas 415.291 registros.
2. Hogares 349.715 registros.
3. Personas 1.556.416 registros.

Pre-procesamiento de los datos

Tomando como punto de partida la información levantada en la etapa anterior en esta fase se desarrollan las actividades destinadas a confeccionar el conjunto de datos final (conjunto que servirá de entrada a los algoritmos ID3 Y C4.5) a partir del conjunto inicial. No se debe olvidar que estos algoritmos requieren de un entrenamiento supervisado por lo que las tareas dedicadas a la preparación de los datos se explican a continuación:

Con la ayuda del experto en estadística y análisis de datos, se relacionaron las tablas mencionadas anteriormente con el objeto de obtener en una sola tabla todos los registros de viviendas, hogares y personas. Luego se procedió a seleccionar de esta tabla los campos que permitirán construir el índice de pobreza en el Estado Lara de acuerdo al método Necesidades Básicas Insatisfechas (NBI).

La tabla obtenida tiene un total de 349.651 registros que corresponden al total de hogares del estado Lara según el censo de población y vivienda 2001. Luego se procedió a separar estos hogares por municipio, obteniéndose un total de nueve tablas, una por cada municipio del estado. Dado que los algoritmos ID3 y C4.5 están orientados hacia el desarrollo de descripciones simbólicas de los datos, los valores numéricos de los registros fueron convertidos a etiquetas. Posteriormente se exportaron estas tablas en formato dbf, txt y db, para poder ser procesadas por el sistema. La figura 6 , muestra un ejemplo de la tabla que sirve de entrada al sistema.

Figura 6

Tabla de entrada al sistema SIMIDACE Tree

Para todas las tablas los atributos son los siguientes:

El método (NBI) consiste en cuantificar la pobreza de aquellos hogares que habitan en viviendas familiares, seleccionando cinco parámetros que indican el grado de satisfacción de cada una de las necesidades, considerando un nivel mínimo para cada indicador, es decir, se clasifican los hogares de acuerdo al número de necesidades insatisfechas que presenten. Los hogares se catalogan en pobres cuando presentan por lo menos una necesidad básica insatisfecha y en pobres extremos si presentan dos o más necesidades básicas insatisfechas.

El NBI analiza variables o parámetros que son poco sensibles a variaciones en el corto plazo, las cuales determinan la medición estructural de la pobreza, proporcionando características asociadas a necesidades en cuanto a: educación, dependencia económica, servicios básicos (agua potable, eliminación de excretas) y condiciones de habitabilidad de las viviendas (hacinamiento y viviendas inadecuadas). De acuerdo al experto dichos parámetros o variables son:

1. Hogares con niños en edad escolar (7 a 12 años) que no asisten a la escuela.
2. Hogares en hacinamiento crítico: mide el grado de hacinamiento en los cuartos de la vivienda, que los integrantes de un hogar utilizan para dormir, se incluyen en esta clasificación aquellos hogares en los cuales hay más de tres personas por cuarto para dormir.
3. Hogares en Viviendas Inadecuadas: Considera los hogares que habitan en viviendas improvisadas (Ranchos y ranchos campesinos), en casas de vecindad y en otra clase (trailer o remolques, embarcaciones, carpas, cuevas, etc.).
4. Hogares en viviendas sin servicios básicos: A través de este indicador se mide la inaccesibilidad de los hogares a agua potable y a eliminación de excreta, de acuerdo al área geográfica donde se encuentran. Cuando un hogar corresponde al área urbana se toma en consideración si carece de al menos uno de los dos servicios. En caso de que pertenezca al área rural se considera si carece de los dos servicios simultáneamente.
5. Hogares con alta dependencia económica: Se refiere a las condiciones de empleo de los integrantes del hogar y a la educación del jefe del mismo. En el se contempla aquellos hogares con más de tres personas por ocupado, cuyo jefe de hogar no haya alcanzado una escolaridad de tres grados o tres años.

Con estas variables más el campo que servirá como clasificador según criterio del experto, los algoritmos ID3 y C4.5 podrán generar el árbol de decisión y transformarlo a reglas de decisión, lo cual facilitará enormemente la clasificación de los hogares en pobres o no pobres.

Vale la pena mencionar que las distintas metodologías o indicadores que se utilizan para la identificación de hogares en situación de pobreza no son medidas alternativas de un mismo fenómeno, sino más bien visiones distintas, y complementarias, de un fenómeno complejo de múltiples aristas. Por eso no es conveniente privilegiar en particular una sola medida sino realizar un estudio comparativo de los factores altamente asociados a la condición de vida pobre según cada indicador, con el fin de obtener el conjunto de estos factores que mejor explica la condición de vida pobre.

A continuación se muestra en la figura No 7, la estructura jerárquica del sistema en donde se observan los diferentes módulos y sub-módulos que permiten realizar las funciones para las cuales fue diseñado el sistema.

Figura 7

Carta Estructurada de SIMIDACE Tree

Descripción general

Para estudiar los algoritmos propuestos se desarrolló un sistema que integra el ID3 y el C4.5. El sistema recibe los datos de entrenamiento como entrada y permite que el usuario elija cuál algoritmo y con qué criterio de decisión (ganancia o proporción de ganancia) desea aplicar. Una vez generados el árbol y las reglas de decisión, el usuario puede evaluar los resultados sobre los datos de prueba. En el caso del ID3, esta evaluación se realiza a partir de las reglas de decisión cuya performance, es idéntica a la de los árboles. La evaluación de los resultados del C4.5, en cambio, se realiza por separado y se obtienen, por lo tanto, dos evaluaciones distintas, una para el árbol y otra para las reglas.

Esto se debe a que el modelo de clasificación generado con el C4.5 como árbol de decisión es distinto al generado como reglas de decisión. La figura 8. presenta un esquema general del funcionamiento del sistema.

Figura 8

Esquema General del sistema SIMIDACE Tree

A continuación se presenta de manera detallada los procedimientos que se siguieron para llevar a cabo los cuatro (4) módulos principales del sistema.

Módulo de Acceso al Sistema

Para iniciar el funcionamiento del sistema se solicita un nombre de usuario y una clave, que se crea para evitar que personas no autorizadas puedan acceder al sistema y de una u otra manera se destruya o altere la información contenida en el mismo. El administrador del sistema controla el acceso al mismo asignando nombre de usuario y clave de acceso en el sub-módulo usuarios. Existen dos tipos de usuarios en el sistema, uno con nivel o estatus cero (0) y otro con estatus uno (1). El usuario con estatus cero, tiene acceso a todas la opciones del sistema y el usuario con estatus uno, solo puede evaluar el rendimiento del sistema con las corridas hechas en el mismo. El diagrama de flujo correspondiente al módulo de acceso al sistema es el siguiente:

Figura 9

Diagrama de flujo de acceso al sistema

2. Módulo Minería

Este módulo agrupa todas las funciones necesarias para aplicar el ID3 y el C4.5 a una tabla. Se utiliza tanto para generar el árbol de decisión como para construir las reglas de decisión.. El corazón del sistema reside en los sub-módulos ID3 y C45, quienes aplican el ID3 y el C4.5 respectivamente. La figura 10 muestra el diagrama modular del módulo minería.

Figura 10

Diagrama modular del módulo minería

1. En este sub-módulo a partir de los datos disponibles, el ID3 analiza todas las divisiones posibles según los distintos atributos y calcula la ganancia y/o la proporción de ganancia para generar el árbol y las reglas de decisión. Una vez generado el árbol lo recorre en preorden y cada vez que llega a una hoja, escribe la regla que tiene como consecuente el valor de la misma, y como antecedente, la conjunción de las pruebas de valor especificados en todos los nodos recorridos desde la raíz para llegar a dicha hoja.

   La figura 11, presenta el diagrama de flujo de datos para la sección del ID3. Con una mirada rápida, se observa que el árbol y las reglas de decisión se generan a partir de los datos de entrenamiento. A su vez, los procesos que los generan graban el árbol, las reglas y las sentencias SQL en sus correspondientes archivos. Además, se genera un log del proceso. Por otro lado, la evaluación de resultados se realiza a partir de las sentencias SQL y de los datos de prueba.

   Figura 11

   Diagrama de flujo de datos del ID3

   

   Cada uno de los procesos mostrados en la figura 11 se describe en las secciones siguientes.

2. Diseño para el ID3
3. Generación del árbol de decisión

Este proceso genera el árbol de decisión según el algoritmo explicado para el ID3.El árbol se construye a partir de los datos de entrenamiento en formato db, dbf o un archivo plano seleccionado por el usuario.

Durante este proceso se genera un archivo de log que guarda todos los cálculos de ganancia y de proporción de ganancia realizadas en cada paso; y el atributo escogido para realizar la división. El archivo de log se encuentra dentro del directorio donde está instalado el programa, y su nombre está compuesto de la siguiente manera: MétodoDD-MM-AA HH_MM_SSNombreTabla.log. Esto permite identificar fácilmente el log correspondiente a una corrida. El formato del archivo de log se especifica a continuación:

Archivo de Log del ID3

Durante la generación del árbol de decisión, se genera un archivo de log que almacena todos los cálculos realizados. En cada paso, se almacenan:

1. El "Nivel" en el que se está, entendiéndose por "Nivel" el número de ciclo de procesamiento en el que se está.

   El nombre del descriptor

   Una matriz con la cantidad de instancias pertenecientes a cada clase para cada valor posible del descriptor.

   El valor de la ganancia.

   El valor de la proporción de ganancia.

2. Para cada descriptor:
3. La ganancia o la proporción de ganancia máxima (según el criterio de división con el que se esté trabajando).

A continuación se presenta una entrada del archivo de log.

1. Este proceso realiza la poda del árbol de decisión según la metodología explicada en las bases teóricas.

2. Poda del árbol de decisión

   Una vez podado, el árbol de decisión se muestra en pantalla, de forma tal que figure la prueba realizada en cada nodo y el valor de la prueba en cada rama, como aparece en la figura 12.

   Figura 12

   Formato del árbol de decisión impreso en pantalla

   

3. Impresión del árbol de decisión en pantalla

   A partir del árbol de decisión podado, se generan las reglas de decisión de acuerdo con el método explicado en las bases teóricas. Se guarda en disco un archivo de texto que contiene las reglas obtenidas, y un archivo de Paradox que contiene las sentencias SQL equivalentes. También se genera otra tabla de Paradox, "Updates.db", que contiene los datos necesarios para identificar la transformación correspondiente a cada sentencia SQL.

   Guardado del árbol de decisión a disco

   Una vez presentado el árbol por pantalla, se le ofrece al usuario la posibilidad de guardarlo en el disco rígido. Si acepta, el árbol se guarda en el directorio donde esta instalado el programa. La extensión del archivo resultante es "tree".

   Evaluación de los resultados

   A partir de una lista de corridas realizadas, el usuario elige cuál corrida del ID3 desea evaluar. Los datos de las corridas previas están almacenados en la tabla "Updates Header". Una vez realizada la elección, se obtienen de la tabla de Sentencias SQL" las sentencias SQL generadas durante la transformación del árbol a reglas de decisión. Estas sentencias se aplican al conjunto de datos de prueba determinado por el usuario.

   Se genera una matriz de confusión que indica para cada clase la cantidad de casos correctamente clasificados y los incorrectamente clasificados. Se calcula la probabilidad de que un caso sea clasificado correctamente como perteneciente a esa clase. Finalmente, se obtienen los totales generales. La matriz de confusión obtenida se muestra en pantalla. La Figura 13 muestra un ejemplo de dicha matriz de confusión.

   Figura 13

   Matriz de confusión generada durante la evaluación de los resultados

   

4. Transformación a reglas de decisión

   El archivo de reglas de decisión generado durante la transformación a reglas de decisión contiene las reglas para el árbol analizado. Por cada regla guarda el número de regla y la regla en sí.

   Archivo del Árbol de decisión del ID3

   Cuando el usuario elige guardar el árbol de decisión a disco, este se almacena en un archivo plano, tabulándose n veces cada renglón, siendo n el nivel del nodo de decisión. A continuación se muestra el contenido de un archivo ".tree" a modo de ejemplo.

   

5. Archivo de Reglas de decisión del ID3

   La figura 14, presenta el diagrama de flujo de datos general para la sección del C4.5. A simple vista, se observa que el diseño de este proceso difiere ligeramente del diseño del ID3. Aunque los procesos principales (generación y poda del árbol de decisión, generación de las reglas de decisión, evaluación de los resultados) se mantienen, se encuentra que hay dos evaluaciones de resultados, una para el árbol de decisión y otra para las reglas.

   Figura 14

   Diagrama de flujo de datos del C4.5

   

   Esto se debe a que, a diferencia del ID3, las reglas de decisión y el árbol generados por el C4.5 no son modelos de clasificación equivalentes. Por otro lado, se encuentra que tanto el archivo del árbol de decisión como el de las reglas de decisión se presentan junto a la evaluación de resultados. Se debe recordar que, como se explicó en las bases teóricas, el C4.5 evalúa cada rama y cada regla en particular. Por lo tanto, la evaluación no puede separarse de los modelos generados.

   Cada uno de los procesos mostrados en la figura 14 se describe en las secciones siguientes.

   Generación del árbol de decisión

   Este proceso genera el árbol de decisión según el algoritmo explicado para el C4.5 en las bases teóricas. El árbol se construye a partir de los datos de entrenamiento en formato db, dbf o un archivo plano seleccionado por el usuario.

   Poda del árbol de decisión

   Este proceso realiza la poda del árbol de decisión según la metodología explicada en las bases teóricas.

   Evaluación del árbol de decisión

   El árbol de decisión se evalúa según el algoritmo explicado en las bases teóricas . Se le agrega una prueba de valor a cada rama y se genera una matriz de confusión a partir de la performance del árbol sobre los datos de prueba.

6. Diseño para el C4.5

   El árbol de decisión se muestra en pantalla para el usuario, de manera idéntica al árbol generado para el ID3.

7. Impresión del árbol de decisión en pantalla

   El árbol de decisión generado, se transforma a reglas de decisión según la metodología explicada en las bases teóricas. Las reglas se almacenan en un archivo con extensión .rules.

   Evaluación de las reglas de decisión

   Una vez generadas las reglas de decisión, el sistema las evalúa contra los datos de prueba. Genera una apreciación de exactitud para cada reglan y una matriz de confusión general. Almacena todos los resultados en un archivo plano.

8. Transformación a reglas de decisión
9. Archivo del árbol de decisión y evaluación de resultados del C4.5

Durante la generación del árbol de decisión, su correspondiente poda y su posterior evaluación se genera un archivo de resultados obtenidos en cada paso. En este archivo se almacenan:

1. N es la sumatoria de los casos de entrenamiento fraccionales que llegan a cada hoja.

   E es la cantidad de casos, cubiertos por la hoja, que no pertenecen a la clase de la misma.

2. El árbol de decisión sin podar, donde cada rama tiene asociados dos números: N y E, cuyo sentido se detalla a continuación:
3. El árbol de decisión podado, con dos números N y E asociados, donde: N es la

cantidad de casos de entrenamiento cubiertos por la hoja.

E es la cantidad de errores predichos, según la distribución binomial, para la

hoja si una cantidad N de nuevos casos fuese evaluada por el árbol.

3. La evaluación sobre los datos de prueba con el siguiente formato:

Donde:

Tamaño = cantidad de nodos + cantidad de hojas

Errores = x (y%)

Con:

x = cantidad de casos clasificados erróneamente

y = cantidad de casos clasificados erróneamente / cantidad total de casos

Estimación =

Donde:

t es la cantidad de hojas del árbol

Ei es el E asociado a cada hoja

N es la cantidad total de casos de entrenamiento

1. A continuación se presenta un archivo de muestra.

   

   Archivo de Reglas de decisión y evaluación de resultados del C4.5

   El formato del archivo de reglas de decisión y evaluación de los resultados es el siguiente:

   Regla

   Tamaño

   Error

   Usada

   Errores

   Ventaja

   Clase

   Donde:

   1. Regla: es el número de la regla.

   2. Tamaño: es la cantidad de pruebas de valor en el antecedente de la regla.

   3. Error: es el estimador calculado como el complemento de la proporción de éxito. asociado a cada regla.

   4. Usada: indica la cantidad de veces que se utilizó la regla durante la evaluación.

2. Una matriz de confusión que indica para cada clase, la cantidad de casos clasificados erróneamente y la cantidad de casos de la misma clasificados como pertenecientes a otra clase.
3. Errores: indica la cantidad de errores cometidos durante la evaluación, y la proporción de error calculada como dicha cantidad sobre la cantidad de veces en que se utilizó la regla.

   b es la cantidad de casos que serian clasificados erróneamente si dicha regla se omitiese.

   c es la cantidad de casos que serian clasificados correctamente si dicha regla se omitiese por las reglas siguientes.

   a es el beneficio neto de omitir la regla, calculado como b-c.

4. La ventaja tiene el siguiente formato a(b/c), donde
5. Matriz de confusión para los datos de entrenamiento.
6. Evaluación de los datos de prueba
7. Matriz de confusión para los datos de prueba.

A continuación se muestra un ejemplo del archivo en cuestión.

1. Módulo de evaluación

Cuando el usuario desea evaluar el rendimiento del modelo generado con el ID3, deberá entrar en este módulo para elegir la tabla sobre la que desea trabajar y la fecha y hora en que se generó el modelo que está tratando de evaluar. Una vez que el usuario ha determinado todos estos datos, se realiza la evaluación del rendimiento del modelo escogido, aparecerá por pantalla la matriz de evaluación del rendimiento del modelo escogido por el usuario. La matriz de evaluación muestra, para cada clase, la cantidad de casos que fueron evaluados correctamente y la cantidad de casos que fueron evaluados incorrectamente. En el caso del C4.5 la evaluación se hace directamente con los datos de prueba. La figura 15 muestra el diagrama modular del módulo evaluación.

Figura 15

Diagrama modular del módulo evaluación

1. Módulo opciones

   Este módulo contiene aquellos sub-módulos que realizan todas las operaciones comunes al ID3 y al C4.5, como seleccionar la tabla de datos sobre la cual se aplicará el proceso de minería, ver la tabla activa, cambiar la tabla de datos y entrar al módulo de usuarios donde se podrán incluir o eliminar los usuarios del sistema. La figura 16, muestra el diagrama modular de este módulo.

   Figura 16

   Diagrama modular del módulo opciones.

   

   Seleccionar tabla: esta opción, permite seleccionar la tabla de trabajo sobre la cual que se aplicará el ID3 o el C4.5 según la elección del usuario.

   Cambiar tabla: permite que el usuario seleccione otra tabla sobre la cual trabajar.

   Ver tabla activa: lista todo los datos de la tabla sobre la cual se está trabajando por pantalla.

   Usuarios: maneja toda la información sobre usuarios que pueden acceder al sistema SIMIDACE Tree. Está constituido por usuario (nombre del usuario), clave (código de acceso del usuario), y tipo (nivel de acceso al sistema, ya sea administrador o usuario). La figura 18, muestra el diagrama de flujo del módulo opciones.

   El sub-modulo usuario queda estructurado de la siguiente manera (ver figura 17).

   Figura 17

   Estructura del sub-módulo usuarios

Modulo Ayuda

Este módulo está formado por dos sub-módulos:

SIMIDACE Tree: se encarga de mostrar el manual de usuario con una interfaz sencilla y amplia información en el manejo del mismo.

Acerca de…: muestra una pantalla donde se visualiza la versión del sistema y el autor del trabajo de grado.

1. Análisis de los resultados obtenidos

Se realizaron múltiples pruebas tanto con el sistema ID3 como con el C4.5. A continuación se presentan los dominios de datos sobre los cuales se trabajó.

Para cada dominio, se presentan dos conjuntos de resultados para cada uno de los sistemas: uno utilizando la ganancia como medida de la ganancia de información en cada iteración del sistema, y otra utilizando la proporción de ganancia con el mismo propósito. Entonces, para cada combinación dominio – sistema – medidor de ganancia, se presentan el árbol y las reglas de decisión obtenidas.

Descripción de los dominios

A continuación se presentan los dominios sobre los cuales se realizaron las pruebas. Para cada dominio se presenta:

1. Una breve descripción
2. Los atributos con sus correspondientes valores posibles
3. Las clases con sus valores
4. La cantidad de instancias y la distribución de clases del dominio

En todos los casos, se dividieron los datos preclasificados en dos subconjuntos: uno de entrenamiento y uno de prueba.

AEB (Municipio Andrés Eloy Blanco).

Descripción: para todos los dominios los ejemplos planteados fueron provistos por el Instituto Nacional de Estadísticas, utilizando la base de datos del censo de población y vivienda 2001 del estado Lara. Los campos de los ejemplos provistos son los parámetros que se tienen en cuenta al analizar la condición de pobreza de un hogar según el método NBI.

1. 	Pobre	No pobre	Totales
   En el conjunto de entrenamiento	2958	2389	5347
   En el conjunto de prueba	3467	0	3467
   Totales	6425	2389	8814

2. Cantidad de instancias y distribución de las clases

Resultados obtenidos con el ID3

A continuación se presentan los resultados obtenidos con el ID3 en cada uno de los dominios analizados. Cada uno de los resultados consiste en un árbol de decisión, un conjunto de reglas de decisión y una matriz de resultados obtenida al aplicar los modelos sobre los datos de prueba. Dicha matriz informa por cada clase, la cantidad de instancias del conjunto de prueba que fueron clasificadas correctamente, la cantidad que fueron clasificadas erróneamente y la probabilidad de que una nueva instancia sea clasificada correctamente.

AEB (Municipio Andrés Eloy Blanco).

ID3 utilizando la ganancia como criterio de decisión

Reglas de decisión

Evaluación de los resultados

ID3 utilizando la proporción de ganancia como criterio de decisión

Reglas de decisión

1. Evaluación de los resultados

   Conclusiones

   En este caso, tanto el árbol como las reglas obtenidas mediante el ID3 son idénticos para la ganancia y para la proporción de ganancia. Al analizar la tabla de evaluación de los resultados, se observa que el clasificador obtenido es excelente para clasificar ambas clases, "No pobre"y "Pobre, es decir, que un nuevo caso de ambas clases, tendrá una probabilidad de 1 de ser clasificado correctamente.

   Iribarren (Municipio Iribarren).

   	Pobre	No pobre	Totales
   En el conjunto de entrenamiento	46920	73080	120000
   En el conjunto de prueba	32444	50532	82976
   Totales	79364	123612	202976

   Iribarren (Municipio Iribarren).

   ID3 utilizando la ganancia como criterio de decisión

   

   

   Reglas de decisión

   

   Evaluación de los resultados

   Iribarren (Municipio Iribarren).

   ID3 utilizando la proporción de ganancia como criterio de decisión

   

   

   Reglas de decisión

   

   Evaluación de los resultados

   Conclusiones

   Al igual que en el caso del municipio Andrés Eloy Blanco, tanto el árbol como las reglas obtenidas mediante el ID3 son idénticos para la ganancia y para la proporción de ganancia. Al analizar la tabla de evaluación de los resultados, se observa que el clasificador obtenido es excelente para clasificar ambas clases, "No pobre"y "Pobre, es decir, que un nuevo caso de ambas clases, tendrá una probabilidad de 1 de ser clasificado correctamente. Estos resultados se repiten para el resto de los municipios, esto se debe a que todos los atributos tienen solo dos valores posibles iguales en todas las tablas.

   Resultados obtenidos con el C4.5

   A continuación, se presentan los resultados obtenidos con el sistema C4.5. Se realizaron pruebas sobre los mismos dominios que para el sistema ID3. Al igual que en el caso anterior, se presentan los resultados para el sistema utilizando la ganancia y la proporción de ganancia para medir la ganancia de información en cada paso del algoritmo.

   AEB (Municipio Andrés Eloy Blanco).

   C4.5 utilizando la ganancia como criterio de decisión

   

   Evaluación de los resultados del árbol de decisión

   

   Evaluación con datos de prueba (3467 items):

   

2. Cantidad de instancias y distribución de las clases

   Clasificación general en los datos de entrenamiento:

4. 

   Reglas de decisión

   

   Evaluación de los resultados de las reglas de decisión

   Evaluación sobre los datos de entrenamiento:

5. Evaluación sobre los datos de prueba:

   

   Clasificación general en los datos de prueba:

   

   Utilizando la proporción de ganancia como criterio de decisión

   

   Evaluación de los resultados del árbol de decisión

   

   Evaluación con datos de prueba (3467 items):

   

   Clasificación general en los datos de entrenamiento:

6. 

   Reglas de decisión

   

   Evaluación de los resultados de las reglas de decisión

   Evaluación sobre los datos de entrenamiento:

7. 

   Evaluación sobre los datos de prueba:

   

   Clasificación general en los datos de prueba:

   

   Iribarren (Municipio Iribarren).

   C4.5 utilizando la ganancia como criterio de decisión

   

   Evaluación de los resultados del árbol de decisión

   

   Evaluación con datos de prueba (82976 items):

   

8. 

   Clasificación general en los datos de entrenamiento:

9. Reglas de decisión

   

   

   Evaluación de los resultados de las reglas de decisión

   Evaluación sobre los datos de entrenamiento:

   

   Evaluación sobre los datos de prueba:

   

   Clasificación general en los datos de prueba:

   

   Iribarren (Municipio Iribarren).

   C4.5 utilizando la proporción de ganancia como criterio de decisión

   

   Evaluación de los resultados del árbol de decisión

   

   Evaluación con datos de prueba (82976 items):

   

   Clasificación general en los datos de entrenamiento:

10. 
11. 

Reglas de decisión

Evaluación de los resultados de las reglas de decisión

Evaluación sobre los datos de entrenamiento:

Clasificación general en los datos de prueba:

Conclusiones

En este caso, tanto los árboles como las reglas obtenidas son iguales si se utiliza la ganancia o la proporción de ganancia como criterio de decisión. Los árboles son pequeños y poco frondosos, lo cual facilita su comprensión. Además, no clasifican ningún ejemplo erróneamente en los datos de prueba.

Las reglas de decisión generadas, también son pocas, lo cual hace que su lectura sea más comprensible. Por lo tanto, se puede decir que tanto los árboles como las reglas obtenidas en este dominio constituyen un buen clasificador.

CAPÍTULO V

CONCLUSIONES Y RECOMENDACIONES

Conclusiones

A partir del estudio realizado sobre la Minería de Datos y el Aprendizaje Automático en general, y de los métodos de la familia TDIDT en particular, se puede concluir que hay varios puntos claves a tener en cuenta al realizar Minería de Datos con algoritmos inteligentes. Entre ellos, se pueden destacar:

1. El Aprendizaje de Conceptos puede verse como una búsqueda en un gran espacio de hipótesis predefinidas. En el caso de la familia TDIDT este espacio de hipótesis, está constituido por todos los árboles de decisión posibles para los datos que se analizaron.
2. Los datos sobre los que se construye el problema son representativos del dominio sobre el que se aplicó el modelo obtenido.
3. Finalmente, cabe destacar que el ID3 y el C4.5 utilizan todos los datos de entrenamiento en cada paso para elegir el "mejor" atributo; esta elección se realiza estadísticamente. Esto es favorable frente a otros métodos de aprendizaje automático que analizan los datos de entrada en forma incremental. El hecho de tener en cuenta todos los datos disponibles en cada paso, resulta en una búsqueda mucho menos sensible a errores en casos individuales. Con los resultados obtenidos se cumplieron todos los objetivos propuestos de analizar la base de datos de censo de población del estado Lara, utilizando técnicas de minería de datos específicamente árboles de decisión

2. Recomendaciones

Como línea futura de trabajo, se propone analizar los datos de entrada con los cuatro métodos (ID3 utilizando ganancia, ID3 utilizando proporción de ganancia, C4.5 utilizando ganancia y C4.5 utilizando proporción de ganancia) y elegir para el nuevo dominio, el modelo que presenta la menor proporción de error. Teniendo en cuenta que si con el primer método la proporción de error es inaceptable, probablemente también sea inaceptable para el resto de los métodos. En cuyo caso, convendría analizar el problema con otros métodos de aprendizaje que enfoquen la resolución del mismo desde otro ángulo.

REFERENCIAS BIBLIOGRÁFICAS

Universidad Fermín Toro (2000). Normas para la presentación del trabajo de grado. Cabudare Estado Lara

García, (2004). Sistema basado en minería de datos para la segmentación de clientes y proveedores en el negocio de importación. Universidad Fermín Toro.

Galvis, (2002). Sistema Inteligente basado en minería de datos para la clasificación de neonatos según su crecimiento intrauterino, edad de gestación y peso al nacer. Universidad Fermín Toro

WINSTON, PATRICK (1994). Inteligencia Artificial. 3era Edición Estados Unidos. Editorial Addison Wesley Iberoamericana S.A

KEVIN KNIGHT. Inteligencia Artificial. 2da Edición Editorial Mc Graw Hill.

WITTEN Y FRANK (2000) Data Mining: Practical Machine

Learning Tools and Techniques with Java Implementations. Ediciones Morgan

Kaufmann, San Diego, EE.UU.

Referencias de fuentes electrónicas

http://www.uv.mx/aguerra/teaching/ml-04/clase07.pdf

http://www.daedalus.es/AreasMD-E.php

http://es.wikipedia.org/wiki/ID3

http://es.wikipedia.org/wiki/php

http://es.wikipedia.org/wiki/mysql

http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/t10arboles.pdf

http://www.sia.eui.upm.es/integr/jalcala/ia/InteligenciaArtificial.pdf

ia.inteligenciartificial[arroba]yahoo.es

Partes: , 2, 3, 4