Minería de datos (página 2)

Para la obtención de esta información censal, se utilizan métodos tradicionales de análisis de datos que incluyen el trabajo con variables estadísticas, varianza, desviación estándar, covarianza, análisis de factores entre otros, que generan largas demoras en el logro de los resultados y la publicación de los hallazgos, con lo que se reduce seriamente el valor práctico de los mismos. Todos estos métodos están orientados numéricamente, es decir , son esencialmente cuantitativos.

En la búsqueda de una alternativa metodológica que permitiese aligerar los lapsos de procesamiento, la minería de datos puede ser una solución, ya que esta permite construir sistemas capaces de adquirir el conocimiento necesario para realizar tareas, usando la experiencia acumulada.

La llegada de la minería de datos se considera como la última etapa de la introducción de métodos cuantitativos, científicos en el mundo del comercio, industria y negocios. Desde ahora, todos los no-estadísticos, es decir el 99,5% de nosotros pueden construir modelos exactos de algunas de sus actividades, para estudiarlas mejor, comprenderlas y mejorarlas.

Estadística y Minería de datos conducen al mismo objetivo, el de efectuar "modelos" compactos y comprensibles que rindan cuenta de las relaciones establecidas entre la descripción de una situación y un resultado (o un juicio) relacionado con dicha descripción. Fundamentalmente, la diferencia entre ambas reside en que las técnicas de Minería de datos construyen el modelo de manera automática mientras que las técnicas estadísticas "clásicas" necesitan ser manejadas y orientadas por un estadístico profesional.

Actualmente en el Instituto Nacional de Estadística (INE), el procesamiento de los datos se realiza utilizando software estadístico especializado como por ejemplo: SPSS, STATA, SAS, MINITAB. Estos programas están orientados a la realización de análisis estadísticos aplicando métodos tradicionales. El costo de estos programas es muy elevado y el uso de los mismos está reservado para los estadísticos.

Los índices de pobreza en el país son calculados mediante técnicas tradicionales de análisis de datos, basándose en los métodos de Necesidades Básicas Insatisfechas (NBI) y Línea de Pobreza (LP), información que es aportada por la base de datos del censo de población correspondiendo al INE el cálculo de dichos índices.

Mediante el uso de técnicas de minería de datos, específicamente árboles de decisión, dichos índices podrán ser generados por cualquier persona que no sea estadístico.

Al haberse tornado económico el almacenamiento de los datos en medios físicos y relativamente fáciles y/o accesibles la recolección de dichos datos, las bases de datos crecen en forma desmesurada. Hoy en día se recolectan datos simplemente por estar al alcance de la mano, sin tener en cuenta su importancia lógica o práctica, o sin saber si son importantes en algún sentido. El almacenamiento masivo de información hace que la minería de datos tenga una importancia cada vez mayor. El análisis de los datos que se recolectan actualmente para toda actividad humana y para cualquier evento o hecho del universo, excede las capacidades de una persona.

Los métodos utilizados hasta ahora para el análisis de datos, son esencialmente cuantitativos (métodos estadísticos), sin embargo, ¿qué pasa cuando más allá de los modelos matemáticos encerrados en los datos, interesan los modelos lógicos?. ¿Cuándo más allá de las direcciones para hacer una clasificación de la base de censo de población, interesa jerarquizar sólo a las potenciales familias en estado de pobreza? ¿Cómo se distingue a las potenciales familias pobres del resto de la gente? ¿Qué características tienen en común? ¿Qué datos las distinguen?. Cuando el análisis de los datos que se busca excede los alcances de un modelo cuantitativo y está orientado hacia una descripción cualitativa de los datos, se debe utilizar los algoritmos inteligentes, como los que se describen en el marco teórico de esta investigación, siendo esta la solución al problema planteado.

Estos algoritmos del aprendizaje automático están orientados hacia el desarrollo de descripciones simbólicas de los datos que puedan caracterizar a uno o más conceptos, diferenciar entre clases de conceptos y describir porqué razón un objeto pertenece a una clase y no a otra. Con este tipo de algoritmos el problema del análisis de las potenciales familias en estado de pobreza estaría resuelto.

Existen muchos tipos de algoritmos de aprendizaje automático; no obstante, los más útiles para este caso son aquellos que no quedan encerrados en el "cerebro" de la computadora, sino que pueden adaptarse a una forma de pensar. Si una persona se encuentra ante un árbol de decisión o un conjunto de reglas de decisión que debe aplicar en orden como resultado de la minería, la clasificación del nuevo caso es tan fácil como la lectura del árbol desde la raíz hasta las hojas.

Este tipo de modelo de datos que representa los conceptos inherentes y ocultos en los datos, de forma tal que son fáciles de interpretar, utilizar e incorporar para la persona humana son los que más enriquecen el conocimiento y como tales, aquellos sobre los cuales se centrará el estudio.

Objetivos de la Investigación

1. Desarrollar un sistema que permita el estudio de minería de datos en la base de datos de censo de población aplicando árboles de decisión.

   1. Objetivos Específicos
2. Objetivo General

1. Diagnosticar la necesidad de un sistema que permita el análisis de los datos del censo de población del Estado Lara aplicando árboles de decisión.
2. Determinar la factibilidad económica, técnica, social y operativa del sistema.
3. Diseñar los módulos del sistema que permita el análisis de los datos del censo de población del estado Lara basado en técnicas de minería de datos, para clasificar los hogares en situación de pobreza.

Justificación e Importancia

Uno de los métodos más conocidos para describir los atributos de una entidad de una base de datos es utilizar un árbol de decisión o de clasificación, que puede transformarse sin inconveniente a un conjunto de reglas de decisión.

La importancia de esta investigación, radica en estudiar de que manera la familia de los métodos inductivos, que aborda el problema de inducir árboles de decisión, puede utilizarse para descubrir automáticamente reglas de negocio a partir de la información disponible en una base de datos. Se trabajará en particular con los métodos ID3 y C4.5, miembros de dicha familia.

Este estudio tiene relevancia en el área de ingeniería porque aborda un tema novedoso como la Minería de Datos, la cual permite apoyar la agilización de los procesos en el ámbito operativo, con ayuda de la tecnología aplicada en este tipo de sistema.

El sistema permitirá clasificar grandes cantidades de información que actualmente se realizan con herramientas de software muy costosas.

Dentro de los beneficios que se conseguirán con este sistema, es que permitirá la construcción de diversos indicadores estadísticos como por ejemplo los de pobreza, con un menor esfuerzo manual y evaluar cantidades enormes de datos. La razón fundamental de esta investigación es encontrar decisiones finales necesarias para cualquier área específica utilizando árboles de decisión.

Con el sistema propuesto no solo se podrán analizar base de datos de censo de población, también tiene otras aplicaciones prácticas como por ejemplo:

1. Toma de decisiones médicas.
2. Análisis de base de datos de registros electorales entre otras.

Así mismo, este trabajo servirá de marco referencial para futuras investigaciones referidas al tema estudiado, además, de ser útil para aquellas instituciones que posean bases de datos con volúmenes de registros muy altos que deseen analizarlas mediante técnicas de minería de datos.

Esta investigación está enmarcada en el siguiente modelo:

Polo: Hombre, ciudad y territorio.

Línea: Sistemas inteligentes para el beneficio del hombre y la comunidad.

Sublinea de investigación: Sistemas inteligentes basados en minería de datos.

1. 2. Alcances
2. Alcances y Limitaciones

El alcance fundamental de esta investigación es el diseño, especificación e implementación de un ambiente de minería de datos que integra los algoritmos ID3 y C4.5, con la finalidad de analizar la base de datos de censo de población del estado Lara aplicando árboles de decisión, además, se desarrollará un método de evaluación de los resultados para determinar la calidad de las reglas obtenidas.

Con este sistema se podrá analizar dicha base de datos aplicando técnicas de minería de datos basado en árboles de decisión específicamente los algoritmos ID3 y C4.5 , lo cual permitirá construir el indicador estadístico que clasificará los hogares de acuerdo a su condición de pobreza.

Uno de los beneficios que aportará este sistema es que podrá se operado por personas que no posean grandes conocimientos de estadística y/o computación.

Limitaciones

2. En esta investigación será analizada solo la base de datos del censo de población y vivienda del Estado Lara.
3. El sistema no realiza el filtrado de los datos que han de ser procesados, previamente se debe realizar un análisis de correlación de los mismos, ya que la finalidad de este sistema es la de hacer clasificaciones mediante árboles de decisión.
4. El sistema no está diseñado para ser operado bajo plataforma de red.
5. El sistema, no podrá ser operado bajo ningún sistema operativo que no sea Microsoft Windows.
6. El sistema solo genera reportes por pantalla, los cuales quedan grabados automáticamente en el directorio donde este instalado el mismo.

CAPÍTULO II

MARCO TEÓRICO

Antecedentes de la Investigación

En el procesamiento de la base de datos de censo de población y vivienda del Estado Lara, en la cual se desarrolla el presente trabajo de grado, no existe ningún antecedente de clasificación de los datos basado en técnicas de Minería de Datos; debido a esto y aunado a que este trabajo representa un desarrollo innovador se dividen los antecedentes basándose en sus tópicos más importantes, que son inteligencia artificial e indicadores sociales realizando para ello búsquedas tanto en el ámbito universitario como en la Internet.

Galvis, (2002) desarrolló un "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 para la Clínica Razzetti de Barquisimeto". Para optar al Título de Ingeniero en Computación en la Universidad "Fermín Toro", teniendo como objetivo contribuir a una mayor eficacia y rapidez en la clasificación de neonatos empleando técnicas de inteligencia artificial específicamente enfocado en minería de datos, este estudio fue enmarcado en la modalidad de investigación de campo en el ámbito de proyecto factible.

Luego del análisis respectivo de los datos se concluyó que el sistema proporcionaba una solución al problema estudiado, se obtuvo una investigación que cumplió con los principios básicos de una problemática planteada.

Este proyecto da como aporte a la investigación planteada, la aplicación de la minería de datos, la cual es capaz de detectar patrones y relaciones que permanecen ocultas ante el uso de herramientas tradicionales. La búsqueda minuciosa, la extracción, agrupación y clasificación de datos estadísticos lo cual permite entre otras cosas, visualizar tendencias y hacer pronósticos.

García, (2004) desarrolló un "Sistema basado en Minería de Datos para la segmentación de clientes y proveedores en el negocio de importación en la Distribuidora Jaime García, C.A". Para optar al título de Ingeniero en Computación en la Universidad "Fermín Toro", utilizando el algoritmo de agrupamiento no supervisado K medias. El sistema además de llevar un registro digitalizado de todas sus operaciones, permite que proveedores y clientes no conocidos por la empresa puedan registrarse para ser evaluados a través de un proceso de Minería de Datos que los agrupe de acuerdo a las características más relevantes de cada uno, permitiendo segmentar y clasificar a los clientes y proveedores de la empresa, para luego generar estrategias gerenciales. El sistema sirvió de aporte en cuanto a como se clasificaron los clientes y proveedores, cómo se normalizaron los datos y los pasos a seguir en el procesamiento de los datos.

Bases Teóricas

Por razones distintas y para fines muy diversos, el país necesita disponer de información confiable sobre los aspectos coyunturales y estructurales de la dinámica de la población y de la situación habitacional; ya sea para responder a los requerimientos del sector oficial, o para satisfacer las necesidades de información del sector privado de la economía, o para nutrir el mejor criterio de la sociedad civil, lo cierto es que satisfacer la demanda de indicadores sobre aspectos relacionados con población y vivienda, requiere la aplicación de métodos y técnicas modernas que permitan reducir la complejidad del proceso de obtención de la información y asegurar la mayor confiabilidad posible de los resultados.

Con el propósito de sustentar conceptualmente este estudio se presenta una serie de autores como Quinlan, Winston, Michalski, entre otros, que abordan aspectos significativos relacionados con el tema tratado.

1. Según Grossman (1999). La inteligencia artificial comenzó como el resultado de la investigación en sicología cognitiva y lógica matemática. Se ha enfocado sobre la explicación del trabajo mental y construcción de algoritmos de solución a problemas de propósito general, punto de vista que favorece la abstracción y la generalidad. La inteligencia artificial es una combinación de la ciencia del computador, fisiología y filosofía, tan general y amplio como eso, reúne varios campos (robótica, sistemas expertos, por ejemplo), todos los cuales tienen en común la creación de máquinas que pueden "pensar".

   Como argumenta Winston (1994). La inteligencia artificial es el estudio de las computaciones que permiten percibir, razonar y actuar.

   Para Knight, (1991). "El estudio de cómo lograr que las computadoras realicen tareas que, por el momento, los humanos lo hacen mejor".

   Luger y Stubblefield. (1990). "La rama de la ciencia de la computación que se ocupa de la automatización de la conducta inteligente".

   2. Base de Datos

   Según Byers, (1986). Es una colección de información organizada y presentada para servir a un propósito específico. En una tabla las filas se denominan registros y las columnas campos. La primera fila contiene los nombres de campo. Cada campo contiene determinado tipo de datos y tiene una longitud expresada en él número de caracteres máximo del campo.

   Para crear una tabla será necesario definir su estructura. El nombre de la tabla, los nombres de campo, los tipos de datos de cada campo, las propiedades o características de cada campo y campo clave (clave principal).

2. Inteligencia Artificial

   Según Mitchell, (1997). La enorme cantidad de bases de datos en todas las áreas de aplicación humana, demanda nuevas y poderosas técnicas de transformación de los datos en conocimientos útiles. Entre dichas técnicas se puede nombrar a las pertenecientes al aprendizaje automático, el análisis estadístico de datos, la visualización de datos, y las redes neuronales. La minería de datos se refiere a la aplicación de técnicas de aprendizaje automático, entre otros métodos, para encontrar importantes patrones en los datos. El descubrimiento de conocimientos pone su énfasis en el ciclo de análisis de datos en sí, analiza su ciclo de vida.

   El Aprendizaje Automático se enfrenta con el desafío de la construcción de programas computacionales que automáticamente mejoren con la experiencia al respecto Mitchell (1997) señala que:

   Estos programas computacionales son sistemas de aprendizaje capaces de adquirir conocimientos de alto nivel y/o estrategias para la resolución de problemas mediante ejemplos, en forma análoga a la mente humana a partir de los ejemplos provistos por un tutor o instructor y de los conocimientos de base o conocimientos previos, el sistema de aprendizaje crea descripciones generales de conceptos (p.196).

   La minería de datos busca generar información similar a la que podría producir un experto humano, que además satisfaga el Principio de Comprensibilidad, la minería de datos es el proceso de descubrir conocimientos interesantes, como patrones, asociaciones, cambios, anomalías y estructuras significativas a partir de grandes cantidades de datos almacenadas en bases de datos, data warehouses, o cualquier otro medio de almacenamiento de información.

   La minería de datos es un campo en pleno desarrollo en el que se aplican métodos de varias disciplinas como los presentes en sistemas de bases de datos, data warehouses, estadística, el aprendizaje automático, visualización de datos, obtención de información y computación de alta performance. Además también se utilizan métodos de las áreas de redes neuronales, reconocimiento de patrones, análisis espacial de datos, bases de datos de imágenes, procesamiento de señales y programación lógica inductiva (ILP). Numerosos especialistas señalan que la minería de datos necesita de la integración de enfoques de múltiples disciplinas.

   Una gran cantidad de métodos de análisis de datos han sido desarrollados en estadística. El Aprendizaje automático ha contribuido en el área de clasificación e inducción. Las redes neuronales, por su lado, son efectivas en la clasificación, predicción y clustering de datos. Sin embargo, con la gran cantidad de datos almacenados en las bases de datos sobre los cuales se debe hacer la minería de datos, todos estos métodos deben reanalizarse o escalarse para ser efectivos.

   Además para procesar grandes volúmenes de datos de los cuales deben extraerse patrones automáticamente, es necesario contar con una gran capacidad computacional de procesamiento. Es necesario, entonces, desarrollar métodos de minería de datos distribuidos, paralelos e increméntales.

3. Minería de Datos
4. Descubrimiento de conocimientos

Anónimo (1999). La minería de datos no debe confundirse con el descubrimiento de conocimientos (knowledge discovery), aunque muchos investigadores consideran que la minería de datos no es más que un paso esencial en el descubrimiento de conocimientos. En general, un proceso de descubrimiento de conocimientos consiste de una repetición iterativa de los siguientes pasos:

1. Limpieza de datos (Data cleaning) procesamiento de los datos ruidosos, erróneos, faltantes o irrelevantes.
2. Integración de datos (Data integration) integración de múltiples fuentes heterogéneas de datos en una única fuente.
3. Selección de datos (Data selection) extracción de los datos relevantes al área de análisis del almacenamiento de datos.
4. Transformación de datos (Data transformation) transformación o consolidación de los datos en formas apropiadas para la minería mediante procedimientos de agregación.
5. Minería de Datos: proceso esencial donde se aplican diversos métodos para extraer patrones de los datos.
6. Evaluación de patrones (Pattern evaluation) identificación de patrones interesantes basándose en algún parámetro de comparación impuesto por el usuario.
7. Presentación de los conocimientos (Knowledge presentation) técnicas de visualización y representación de los conocimientos adquiridos.

Con los sistemas de bases de datos relacionales existentes hoy en día, los cuatro procesos iniciales: limpieza, integración, selección y transformación de datos pueden realizarse mediante la construcción de data warehouses. Los procesos de minería de datos, evaluación de patrones y presentación de conocimientos generalmente se agrupan en el proceso que se conoce como minería de datos. De ahí la confusión que puede llegar a existir con el nombre.

1. Fases de un Proyecto de Minería de Datos

Los pasos a seguir para la realización de un proyecto de minería de datos son

siempre los mismos, independientemente de la técnica específica de extracción de conocimiento usada. La figura No 1 muestra los pasos de un proyecto de Minería de Datos.

Figura 1

Fases de un proyecto de minería de datos

El proceso de minería de datos pasa por las siguientes fases:

1. Filtrado de datos: El formato de los datos contenidos en la fuente de datos (base de datos, Data Warehouse…) nunca es el idóneo, y la mayoría de las veces no es posible ni siquiera utilizar ningún algoritmo de minería sobre los datos "en bruto". Mediante el preprocesado, se filtran los datos (de forma que se eliminan valores incorrectos, no válidos, desconocidos… según las necesidades y el algoritmo a usar), se obtienen muestras de los mismos (en busca de una mayor velocidad de respuesta del proceso), o se reducen el número de valores posibles (mediante redondeo, clustering,…).

   Aquellos basados en la elección de los mejores atributos del problema, y  aquellos que buscan variables independientes mediante tests de sensibilidad, algoritmos de distancia o heurísticos.

2. Selección de Variables: Aún después de haber sido preprocesados, en la mayoría de los casos se tiene una cantidad inmensa de datos. La selección de características reduce el tamaño de los datos eligiendo las variables más influyentes en el problema, sin apenas sacrificar la calidad del modelo de conocimiento obtenido del proceso de minería. Los métodos para la selección de características son básicamente dos:
3. Extracción de Conocimiento: Mediante una técnica de minería de datos, se obtiene un modelo de conocimiento, que representa patrones de comportamiento observados en los valores de las variables del problema o relaciones de asociación entre dichas variables. También pueden usarse varias técnicas a la vez para generar distintos modelos, aunque generalmente cada técnica obliga a un preprocesado diferente de los datos.
4. Interpretación y Evaluación: Una vez obtenido el modelo, se debe proceder a su validación, comprobando que las conclusiones que arroja son válidas y suficientemente satisfactorias. En el caso de haber obtenido varios modelos mediante el uso de distintas técnicas, se deben comparar los modelos en busca de aquel que se ajuste mejor al problema. Si ninguno de los modelos alcanza los resultados esperados, debe alterarse alguno de los pasos anteriores para generar nuevos modelos.

1. Componentes de la Minería de Datos

Joshi (1997) considera que "La minería de datos cuenta con tres grandes componentes según Clustering o clasificación, reglas de asociación y análisis de secuencias" (p.82).

En el Clustering o Clasificación se analizan los datos y se generan conjuntos de reglas que agrupen y clasifiquen los datos futuros. Debe tenerse en cuenta que en la minería de datos se busca obtener reglas que particionen los datos en clases predefinidas, esto se torna complicado cuando hay una gran cantidad de atributos y millones de registros.

Una regla de asociación es una regla que implica o presenta ciertas relaciones entre un grupo de objetos en una base de datos. En el proceso de la minería de datos se obtienen varias reglas de este tipo con distintos niveles de abstracción.

Nuevamente, no olvidar que esto puede implicar el análisis iterativo de bases de datos transaccionales o relacionales, con millones de registros, lo cual presenta un elevado costo operativo. Por lo tanto, la obtención de reglas a partir de bases de datos relacionales o transaccionales es un importante tema de estudio.

Por último, el análisis de secuencias trata de encontrar patrones que ocurren con una secuencia determinada. Trabaja sobre datos que aparecen en distintas transacciones a diferencia de los datos que aparecen relacionados mediante reglas dentro de una misma transacción.

A continuación se presentan ejemplos de algoritmos de minería de datos existentes, de cada uno de los tipos presentados.

Algoritmos de Clasificación (Classification Algorithms)

Según Joshi, (1997). La clasificación de datos desarrolla una descripción o modelo para cada una de las clases presentes en la base de datos. Existen muchos métodos de clasificación como aquellos basados en los árboles de decisión TDIDT como el ID3 y el C4.5, los métodos estadísticos, las redes neuronales, y los conjuntos difusos, entre otros.

A continuación se describen brevemente aquellos métodos de aprendizaje automático que han sido aplicados a la minería de datos con cierto éxito:

1. Algoritmos estadísticos: muchos algoritmos estadísticos han sido utilizados por los analistas para detectar patrones inusuales en los datos y explicar dichos patrones mediante la utilización de modelos estadísticos, como, por ejemplo, los modelos lineales. Estos métodos se han ganado su lugar y seguirán siendo utilizados en los años venideros.
2. Redes Neuronales: las redes neuronales imitan la capacidad de la mente humana para encontrar patrones. Han sido aplicadas con éxito en aplicaciones que trabajan sobre la clasificación de los datos.
3. Algoritmos genéticos: técnicas de optimización que utilizan procesos como el entrecruzamiento genético, la mutación y la selección natural en un diseño basado en los conceptos de la evolución natural.
4. Método del vecino más cercano: es una técnica que clasifica cada registro de un conjunto de datos en base a la combinación de las clases de los k registros más similares. Generalmente se utiliza en bases de datos históricas.
5. Reglas de inducción: la extracción de reglas si-entonces a partir de datos de importancia estadística.
6. Visualización de los datos: la interpretación visual de las relaciones entre datos multidimensionales.
7. Clasificadores basados en instancias o ejemplos: Una manera de clasificar un caso es a partir de un caso similar cuya clase es conocida, y predecir que el caso pertenecerá a esa misma clase. Esta filosofía es la base para los sistemas basados en instancias, que clasifican nuevos casos refiriéndose a casos similares recordados. Un clasificador basado en instancias necesita teorías simbólicas. Los problemas centrales de este tipo de sistemas se pueden resumir en tres preguntas: ¿cuáles casos de entrenamiento deben ser recordados?, ¿cómo puede medirse la similitud entre los casos?, y ¿cómo debe relacionarse el nuevo caso a los casos recordados?.

Los métodos de aprendizaje basados en reglas de clasificación buscan obtener reglas o árboles de decisión que particionen un grupo de datos en clases predefinidas.

Para cualquier dominio real, el espacio de datos es demasiado grande como para realizar una búsqueda exhaustiva en el mismo.

En cuanto a los métodos inductivos, la elección del atributo para cada uno de los nodos se basa en la ganancia de entropía generada por cada uno de los atributos. Una vez que se ha recopilado la información acerca de la distribución de todas las clases, la ganancia en la entropía se calcula utilizando la teoría de la información o bien el índice de Gini. En la solución propuesta se utilizaran métodos inductivos.

Aplicaciones

A continuación se describen los algoritmos de aprendizaje automático que han sido utilizados en el sistema propuesto de Minería de Datos.

1. Este sistema ha sido el que más impacto ha tenido en la minería de datos. Desarrollado en los años ochenta por Quinlan, ID3 significa Induction Decision Trees, y es un sistema de aprendizaje supervisado que construye árboles de decisión a partir de un conjunto de ejemplos. Estos ejemplos son tuplas compuestas por varios atributos y una única clase. El dominio de cada atributo de estas tuplas está limitado a un conjunto de valores. Las primeras versiones del ID3 generaban descripciones para dos clases: positiva y negativa. En las versiones posteriores, se eliminó esta restricción, pero se mantuvo la restricción de clases disjuntas. ID3 genera descripciones que clasifican cada uno de los ejemplos del conjunto de entrenamiento.

   Este sistema tiene una buena performance en un amplio rango de aplicaciones, entre las cuales se pueden nombrar, aplicaciones de dominios médicos, artificiales y el análisis de juegos de ajedrez. El nivel de precisión en la clasificación es alto. Sin embargo, el sistema no hace uso del conocimiento del dominio. Además, muchas veces los árboles son demasiado frondosos, lo cual conlleva a una difícil interpretación. En estos casos pueden ser transformados en reglas de decisión para hacerlos más comprensibles.

2. ID3

   El C4.5 es una extensión del ID3 que permite trabajar con valores continuos para los atributos, separando los posibles resultados en dos ramas: una para aquellos Ai<=N y otra para Ai>N. Este algoritmo fué propuesto por Quinlan en 1993. El algoritmo C4.5 genera un árbol de decisión a partir de los datos mediante particiones realizadas recursivamente. El árbol se construye mediante la estrategia de profundidad-primero (depth-first). El algoritmo considera todas las pruebas posibles que pueden dividir el conjunto de datos y selecciona la prueba que resulta en la mayor ganancia de información. Para cada atributo discreto, se considera una prueba con n resultados, siendo n el número de valores posibles que puede tomar el atributo. Para cada atributo continuo, se realiza una prueba binaria sobre cada uno de los valores que toma el atributo en los datos.

   1. La familia TDIDT
3. C4.5

Según Korab, (1997). La familia de los Top Down Induction Trees (TDIDT) pertenece a los métodos inductivos del aprendizaje automático que aprenden a partir de ejemplos preclasificados. En Minería de Datos, se utiliza para modelar las clasificaciones en los datos mediante árboles de decisión.

1. Construcción de los árboles de decisión

Los árboles TDIDT, a los cuales pertenecen los generados por el ID3 y por el C4.5, se construyen a partir del método de Hunt. El esqueleto de este método para construir un árbol de decisión a partir de un conjunto T de datos de entrenamiento es muy simple. Sean las clases {C1, C2,. . ., Ck}. Existen tres posibilidades:

1. El árbol de decisión para T es una hoja identificando la clase Cj .

2. T contiene uno o más casos, todos pertenecientes a una única clase Cj :
3. T no contiene ningún caso: el árbol de decisión es una hoja, pero la clase asociada debe ser determinada por información que no pertenece a T. Por ejemplo, una hoja puede escogerse de acuerdo a conocimientos de base del dominio, como ser la clase mayoritaria.
4. T contiene casos pertenecientes a varias clases: en este caso, la idea es refinar T en subconjuntos de casos que tiendan, o parezcan tender hacia una colección de casos pertenecientes a una única clase. Se elige una prueba basada en un único atributo, que tiene uno o más resultados, mutuamente excluyentes {O1, O2,. . ., On}. T se particiona en los subconjuntos T1, T2,. . ., Tn donde Ti contiene todos los casos de T que tienen el resultado Oi para la prueba elegida. El árbol de decisión para T consiste en un nodo de decisión identificando la prueba, con una rama para cada resultado posible. El mecanismo de construcción del árbol se aplica recursivamente a cada subconjunto de datos de entrenamientos, para que la i-ésima rama lleve al árbol de decisión construido por el subconjunto Ti de datos de entrenamiento.

1. Según Korab, (1997). En los casos, en los que el conjunto T contiene ejemplos pertenecientes a distintas clases, se realiza una prueba sobre los distintos atributos y se realiza una partición según el "mejor" atributo. Para encontrar el "mejor" atributo, se utiliza la teoría de la información, que sostiene que la información se maximiza cuando la entropía se minimiza. La entropía determina la azarosidad o desestructuración de un conjunto.

   Al suponer que se tienen ejemplos positivos y negativos. En este contexto la entropía del subconjunto 0, , puede calcularse como:

   

   Donde es la probabilidad de que un ejemplo tomado al azar de sea positivo. Esta probabilidad puede calcularse como:

   

   Siendo la cantidad de ejemplos positivos de , y la cantidad de ejemplos negativos.

   La probabilidad pi- se calcula en forma análoga a pi+, reemplazando la cantidad de ejemplos positivos por la cantidad de ejemplos negativos, y viceversa.

   Generalizando la expresión (1) para cualquier tipo de ejemplos, se obtiene la fórmula general de la entropía:

   

   En todos los cálculos relacionados con la entropía, se define 0log0 igual a 0.

   Si el atributo at divide el conjunto S en los subconjuntos Si, i = 1,2,….. , n, entonces, la entropía total del sistema de subconjuntos será:

   

   Donde es la entropía del subconjunto S i y P ( Si ) es la probabilidad de que un ejemplo pertenezca a Si. Puede calcularse, utilizando los tamaños relativos de los subconjuntos, como:

   

   La ganancia en información puede calcularse como la disminución en entropía. Es decir:

   

   Donde H(S) es el valor de la entropía a priori, antes de realizar la subdivisión, y H(S, at)es el valor de la entropía del sistema de subconjuntos generados por la partición según at.

   El uso de la entropía para evaluar el mejor atributo no es el único método existente utilizado en aprendizaje automático. Sin embargo, es el utilizado por Quinlan al desarrollar el ID3 y su sucesor el C4.5.

   1. Los árboles de decisión pueden generarse tanto a partir de atributos discretos como de atributos numéricos. Cuando se trabaja con atributos discretos, la partición del conjunto según el valor de un atributo es simple. Por ejemplo, Se agrupan todos los animales que tengan pico, siendo tiene pico un atributo y sus posibles valores sí y no.

      En el caso de los atributos numéricos esta división no es tan simple. Por ejemplo, al querer partir los días de un mes en función a la cantidad de lluvia caída, es casi imposible encontrar dos días con exactamente la misma cantidad de precipitaciones.

      Para solucionar este problema, puede recurrirse a la binarización. Este método consiste en formar dos rangos de valores de acuerdo al valor de un atributo, que pueden tomarse como simbólicos. Por ejemplo, si en un día hubo 100ml de lluvia, pueden crearse los intervalos [0,100) y [100, +.) y el cálculo de la entropía se realiza como si los dos intervalos fueran los dos valores simbólicos que puede tomar el atributo.

   2. Datos Numéricos

      Existen varias razones para la poda de los árboles generados por los métodos de TDIDT. Michalski, (1998). Entre ellas se pueden nombrar la sobre generalización, la evaluación de atributos poco importantes o significativos, y el gran tamaño del árbol obtenido. En el primer caso, un árbol puede haber sido construido a partir de ejemplos con ruido, con lo cual algunas ramas del árbol pueden ser engañosas. En cuanto a la evaluación de atributos no relevantes, éstos deben podarse ya que sólo agregan niveles en el árbol y no contribuyen a la ganancia de información. Por último, si el árbol obtenido es demasiado profundo o demasiado frondoso, se dificulta la interpretación por parte del usuario, con lo cual hubiera sido lo mismo utilizar un método de caja negra.

      Existen dos enfoques para podar los árboles: la pre-poda (preprunning) y la post-poda (postprunning). En el primer caso se detiene el crecimiento del árbol cuando la ganancia de información producida al dividir un conjunto no supera un umbral determinado. En la post-poda se podan algunas ramas una vez que se ha terminado de construir el árbol.

      El primer enfoque, tiene la atracción de que no se pierde tiempo en construir una estructura que luego será simplificada en el árbol final. El método típico en estos casos es buscar la mejor manera de partir el subconjunto y evaluar la partición desde el punto de vista estadístico mediante la teoría de la ganancia de información, reducción de errores, etc. Si esta evaluación es menor que un límite predeterminado, la división se descarta y el árbol para el subconjunto es simplemente la hoja más apropiada. Sin embargo, este tipo de método tiene la contra de que no es fácil detener un particionamiento en el momento adecuado, un límite muy alto puede terminar con la partición antes de que los beneficios de particiones subsiguientes parezcan evidentes, mientras que un límite demasiado bajo resulta en una simplificación demasiado leve.

      El segundo enfoque es, entonces, el utilizado por el ID3 y el C4.5. Una vez construido el árbol se procede a su simplificación según los criterios propios de cada uno de los algoritmos.

   3. Poda de los árboles generados
   4. Transformación a reglas de decisión

   Según Korab, (1997) Los árboles de decisión demasiado grandes son difíciles de entender porque cada nodo debe ser interpretado dentro del contexto fijado por las ramas anteriores. Cada prueba tiene sentido, solamente, si se analiza junto con los resultados de las pruebas previas. Cada prueba en el árbol tiene un contexto único que es crucial a la hora de entenderla y puede ser muy difícil comprender un árbol en el cual el contexto cambia demasiado seguido al recorrerlo. Además, la estructura de árbol puede hacer que un concepto en particular quede fragmentado, lo cual hace que el árbol sea aún más difícil de entender.

   Existen dos maneras de solucionar estos problemas: definir nuevos atributos que estén relacionados con las tareas o cambiar de método de representación, por ejemplo, a reglas de decisión.

   En cualquier árbol de decisión, las condiciones que deben satisfacerse cuando un caso se clasifica por una hoja pueden encontrarse analizando los resultados de las pruebas en el camino recorrido desde la raíz. Es más, si el camino fuese transformado directamente en una regla de producción, dicha regla podría ser expresada como una conjunción de todas las condiciones que deben ser satisfechas para llegar a la hoja.

   Consecuentemente, todos los antecedentes de las reglas generadas de esta manera serían mutuamente excluyentes y exhaustivos.

   Al hablar de reglas de decisión o de producción se refiere a una estructura de la forma:

   Si atributo1 = valorX y atributo2 = valorY …. y atributo n = valorZ Entonces claseK.

   Se dice que una regla cubre un caso si el caso satisface todas las condiciones en el antecedente de la misma.

2. Cálculo de la ganancia de información
3. Evaluación de los métodos de aprendizaje

La evaluación es la clave del progreso en la Minería de Datos. Existen varias maneras de inferir estructuras a partir de los datos; para determinar cuál es el mejor método para cada conjunto de datos, debe existir una manera de evaluar los métodos de aprendizaje y compararlos entre sí.

Si se cuenta con una gran cantidad de datos, la evaluación no es problema: se genera un modelo a partir de un conjunto grande de entrenamiento y, luego, se lo prueba con otro gran conjunto de datos. Sin embargo, aunque la Minería de Datos implica por su definición trabajar con grandes cantidades de datos, los conjuntos de datos de buena calidad son pocos. Los datos de entrenamiento deben ser cuidadosamente generados y analizados por expertos humanos, un recurso que escasea.

Existen varios indicadores de la performance de un algoritmo de aprendizaje, algunos de ellos se describen a continuación. Michalski, (1998):

1. Precisión: cantidad de ejemplos positivos y negativos evaluados correctamente. Algunas veces, es importante distinguir entre dos tipos de errores: los ejemplos positivos clasificados como negativos (errores de omisión) y viceversa (errores de comisión). Estos dos tipos de errores nos ayudan a determinar si los conceptos aprendidos son demasiado generales o demasiado específicos. Para que un sistema sea preciso, es necesario que genere descripciones que sean consistentes (no cubran ningún ejemplo negativo) y que sean completas (cubran todos los ejemplos positivos).
2. Eficiencia: un sistema debe ser capaz de generar descripciones correctas con un número mínimo de ejemplos. Un instructor no siempre puede dotar al sistema de una cantidad infinita de ejemplos, y la velocidad en el aprendizaje es un indicador de inteligencia. Dentro de la eficiencia, debemos evaluar también los requerimientos computacionales. Estos se miden en función a la cantidad de tiempo y recursos que un sistema necesita para llegar a una buena descripción.
3. Comprensibilidad: es importante que los conceptos generados sean comprensibles al usuario, ya que el fin último de estos sistemas es que el usuario aprenda algo de ellos.
4. Robustez: contra el ruido y contra los ejemplos incompletos. Cada sistema maneja estos dos problemas de forma diferente, con lo cual debe evaluarse en cada sistema en particular.
5. Requerimientos especiales: en algunos dominios, se requiere que un sistema aprenda a medida que llegan los ejemplos. Esto se conoce como aprendizaje incremental y es, especialmente, importante en aquellas áreas en que los conceptos evolucionan, cambian su significado a través del tiempo.

1. Para los problemas de clasificación, como los de la familia TDIDT, es natural medir la performance del clasificador con una proporción de error. El clasificador predice la clase de cada instancia: si la predicción es correcta, es un éxito; si no lo es, un error. La proporción de error, entonces, es simplemente la cantidad de errores sobre la cantidad total de instancias clasificadas.

   Por supuesto, lo que interesa es estimar la proporción de errores sobre los nuevos datos y no sobre los datos de entrenamiento, los cuales ya están clasificados. ¿Se puede decir que la proporción de error estimada a partir de los datos de entrenamiento es correcta para los datos futuros?. No, si los datos sobre los que se estimó el error fueron utilizados al generar el clasificador. La proporción de error sobre los datos de entrenamiento no es un buen indicador de los errores futuros; como el clasificador se generó a partir de estos datos, la proporción de error es subjetiva y totalmente optimista. La proporción de error generada a partir de los datos de entrenamiento se conoce como error de sustitución, ya que se calcula al sustituir las instancias en un clasificador que fue construido a partir de ellas. A pesar de que no es un buen estimador para la predicción de futuros errores, es muy útil conocerlo.

   Para predecir la performance del clasificador en los datos futuros, se necesita evaluar la proporción de error sobre datos no utilizados durante la construcción del mismo. El conjunto independiente de datos utilizado con este propósito es el conjunto de prueba. Es esencial que el conjunto de prueba no haya sido utilizado para nada en la generación del clasificador. Entonces, aquellos esquemas en que la construcción se realiza en dos etapas o requieren probar el clasificador, trabajan con dos conjuntos de datos: el de entrenamiento y el de prueba.

   Se Puede decir que a mayor cantidad de datos, mejor clasificador y mejor estimador de error. El problema está cuando hay una pequeña cantidad de datos de entrenamiento. En muchas situaciones, los datos de entrenamiento y prueba deben clasificarse manualmente. Se Debe encontrar la forma de conseguir un buen estimador de error, aún cuando los datos de prueba escasean. A continuación, se explican varios métodos para evaluar los algoritmos de clasificación.

   2. Estimación del costo
2. Evaluación en la familia TDIDT

Hasta ahora no se ha considerado el costo de tomar malas decisiones y malas clasificaciones. La optimización de las proporciones de clasificación sin considerar el

costo de los errores, generalmente lleva a resultados extraños. Existe un ejemplo famoso de un sistema de inducción utilizado para predecir los períodos fértiles de las vacas. Las vacas se controlaron con un identificador electrónico en la oreja, y otros atributos como el volumen de leche y su composición química. En las primeras pruebas del sistema de aprendizaje automático, los resultados afirmaban que las vacas nunca estaban en el período fértil. El período menstrual de las vacas es similar al de los humanos, con lo cual la regla generada era correcta el 97% de las veces, un grado de precisión impresionante para el dominio de la agricultura. Sin embargo, lo que se buscaba eran reglas que predijeran cuando una vaca estaba fértil y no cuando no lo estaba, con lo cual, los costos de los dos casos de error son distintos. La evaluación por exactitud en la clasificación asume costos iguales por naturaleza. Si los costos son conocidos, pueden incluirse en el análisis de los métodos. Al restringir el análisis a los casos que tienen clases sí y no únicamente. Los cuatro resultados posibles de una predicción pueden listarse en una matriz de confusión como la que se muestra a continuación.

Cuadro 1

Matriz de confusión para los casos que tienen clases si y no únicamente.

Fuente: Un algoritmo de aprendizaje de conceptos para sistemas inteligentes. Buenos Aires 1987.

Elaborado: García (1987)

Los verdaderos positivos y verdaderos negativos son los casos sin error. Los falsos positivos corresponden a aquellas instancias negativas que fueron clasificadas como positivas, mientras que los falsos negativos son aquellas instancias clasificadas como negativas cuando en realidad son positivas.

Estos dos casos de errores generalmente tienen distintos costos, como los casos clasificados correctamente tienen distintos beneficios. El hecho de pensar en el costo genera mejores decisiones.

No obstante, la mayoría de los algoritmos de aprendizaje automático no tienen en cuenta el costo al aprender. Existen, sin embargo, dos maneras de transformarlo fácilmente. La primera idea para transformar un clasificador para que tome en cuenta el costo, es variar la cantidad de ejemplos positivos y negativos en los datos de entrenamiento de acuerdo a la importancia de cada uno de los errores. Otra idea es ponderar las instancias. Por ejemplo, al generar un árbol de decisión, una instancia puede dividirse en partes con un esquema de ponderación que indique la proporción con que debe tomarse cada rama.

Características de los árboles de decisión

Los árboles de decisión representan una estructura de datos que organiza eficazmente los descriptores. Se construye un árbol de forma tal que en cada nodo se realiza una prueba sobre el valor de los descriptores y de acuerdo con la respuesta se va descendiendo en las ramas, hasta llegar al final del camino donde se encuentra el valor del clasificador. Se puede analizar un árbol de decisión como una caja negra en función de cuyos parámetros (descriptores) se obtiene un cierto valor del clasificador.

Figura 2

Estructura de un árbol de decisión

Un árbol de decisión puede analizarse como una disyunción de conjunciones. Cada camino desde la raíz hasta las hojas representa una conjunción, y todos los caminos son alternativos, es decir, son disyunciones.

1. Las reglas de decisión o de producción son una alternativa a los árboles de decisión, y todo árbol de decisión puede llevarse a reglas de este tipo Witten y Frank , (2000).

   Antecedente => Consecuente

   Donde el antecedente es una conjunción entre distintas pruebas de valor sobre los valores de los atributos; y el consecuente es una clase para todos los casos que satisfagan el antecedente. Por ejemplo,

   Si atributo1="valor a" y atributo2= "valor y", entonces Clase K

   Las reglas de decisión se presentan en orden, y deben interpretarse de esa manera. El orden determina cuáles reglas deben ejecutarse primero. Al clasificar un nuevo caso se avanza en la lista hasta llegar a un antecedente que sea satisfecho por el caso, entonces la clase del caso es la correspondiente al consecuente de dicha regla. El C4.5 en particular, agregar una última regla a la lista, ésta no tiene antecedente, es la regla con la clase por defecto, es decir, si el caso no satisfizo ninguna de las reglas anteriores, entonces es de la clase indicada por la última regla que no tiene antecedente.

   En el caso de las reglas de decisión, agregar una nueva regla implica simplemente añadirla a la lista de reglas sin necesidad de hacer cambios de estructura, mientras que agregar una nueva regla en un árbol implicaría rehacer la estructura del mismo.

2. Características de las reglas de decisión

   Tanto el ID3 como el C4.5 generan un clasificador de la forma de un árbol de decisión, cuya estructura es Quinlan, (1993):

   Una hoja, indicando una clase.

   Un nodo de decisión que especifica alguna prueba a ser realizada sobre un único atributo, con una rama y subárbol para cada valor posible de la prueba.

   El árbol de decisión generado por el C4.5 cuenta con varias características particulares: cada hoja tiene asociados dos números, que indican el número de casos de entrenamientos cubiertos por cada hoja y la cantidad de ellos clasificados erróneamente por la hoja. Es en cierta manera, un estimador del éxito del árbol sobre los casos de entrenamiento. El ID3, en cambio, no clasifica erróneamente a los datos de entrenamiento, con lo cual no son necesarios este tipo de indicadores. Es por ello, que este algoritmo, a diferencia del C4.5, corre el riesgo de caer en sobre ajuste.

   El propósito de construir modelos de clasificación no se limita al desarrollo de predictores precisos, también es esencial que el modelo construido sea comprensible para los seres humanos. Michie (1986), critica al ID3 al sostener que los resultados recientes demuestran que los programas construidos sobre la base de sistemas tales como el ID3 pueden ser considerados, de alguna manera, "super-programas" y al mismo tiempo ser incomprensibles para las personas. Se han estudiado varias maneras de simplificar los árboles de decisión. Por ejemplo, en el sistema integrado propuesto, los árboles generados por el C4.5 como por el ID3 se transforman en un conjunto de reglas de producción o decisión, un formato que parece más comprensible que los árboles, cuando estos últimos son demasiado extensos o frondosos.

   Descripción general de los algoritmos

   El algoritmo principal de los sistemas de la familia TDIDT, a la cual pertenecen el ID3 y su descendiente el C4.5, es el proceso de generación de un árbol de decisión inicial a partir de un conjunto de datos de entrenamiento. La idea original está basada en un trabajo de Hoveland y Hunt de los años 50, culminado en el libro Experiments in Induction Hunt, 1966 que describe varios experimentos con varias implementaciones de sistemas de aprendizaje de conceptos.

3. Presentación de los resultados

   Se debe recordar que el método "divide y reinarás" realiza en cada paso una partición de los datos del nodo según una prueba realizada sobre el "mejor" atributo.

   Cualquier prueba que divida a T en una manera no trivial, tal que al menos dos subconjuntos distintos {Ti} no estén vacíos, eventualmente resultará en una partición de subconjuntos de una única clase, aún cuando la mayoría de los subconjuntos contengan un solo ejemplo. Sin embargo, el proceso de construcción del árbol no apunta meramente a encontrar cualquier partición de este tipo, sino a encontrar un árbol que revele una estructura del dominio y, por lo tanto, tenga poder predictivo. Para ello, se necesita un número importante de casos en cada hoja o, dicho de otra manera, la partición debe tener la menor cantidad de clases posibles. En el caso ideal, lo deseable es elegir en cada paso la prueba que genere el árbol más pequeño.

   La mayoría de los métodos de construcción de árboles de decisión, incluyendo el C4.5 y el ID3, no permiten volver a estados anteriores, es decir, son algoritmos golosos sin vuelta atrás. Una vez que se ha escogido una prueba para particionar el conjunto actual, típicamente basándose en la maximización de alguna medida local de progreso, la partición se concreta y las consecuencias de una elección alternativa

   no se exploran. Por este motivo, la elección debe ser bien realizada.

4. División de los datos

   Para realizar la división de los datos en cada paso, Quinlan propone la utilización de los métodos de la Teoría de la Información. En un principio, el ID3 utilizaba la ganancia como criterio de división. Sin embargo, a partir de numerosas pruebas se descubrió que este criterio no era efectivo en todos los casos y se obtenían mejores resultados si se normalizaba el criterio en cada paso. Por lo tanto, comenzó a utilizarse la ganancia de información, con mayor éxito. El C4.5 también utiliza este último criterio para realizar la división de los casos. Quinlan afirma que en su opinión el criterio de proporción de ganancia es robusto y generalmente da resultados más consistentes que el criterio de ganancia.

   La solución propuesta permite la utilización de ambos criterios. Se estudiarán y compararán los resultados obtenidos con el ID3 y con el C4.5 utilizando la ganancia y la proporción de ganancia.

5. Elección del criterio de división

   La definición de ganancia presentada en la ecuación 6. Al Suponer que se tiene una prueba posible con n resultados que particionan al conjunto T de entrenamiento en los subconjuntos T1, T2,. . ., Tn. Si la prueba se realiza sin explorar las divisiones subsiguientes de los subconjuntos Ti , la única información disponible para evaluar la partición es la distribución de clases en T y sus subconjuntos.

   Al considerar una medida similar luego de que T ha sido particionado de acuerdo a los n resultados de la prueba X. La información esperada (entropía) puede determinarse como la suma ponderada de los subconjuntos, de la siguiente manera

   

   La cantidad

   

   mide la información ganada al partir T de acuerdo a la prueba X. El criterio de ganancia, entonces, selecciona la prueba que maximice la ganancia de información. Es decir, antes de particionar los datos en cada nodo, se calcula la ganancia que resultaría de particionar el conjunto de datos según cada uno de los atributos posibles. Se realiza la partición que resulta en la mayor ganancia.

6. Criterio de Ganancia

   El criterio de ganancia tiene un defecto muy serio: presenta una tendencia muy fuerte a favorecer las pruebas con muchos resultados. Al analizar una prueba sobre un atributo que sea la clave primaria de un conjunto de datos, en la cual, se obtendrá un único subconjunto para cada caso, y para cada subconjunto se tendrá

   I (T,X) = 0, entonces la ganancia de información será máxima. Desde el punto de vista de la predicción, este tipo de división no es útil.

   Esta tendencia inherente al criterio de ganancia puede corregirse mediante una suerte de normalización, en la cual se ajusta la ganancia aparente, atribuible a pruebas con muchos resultados. Consideremos el contenido de información de un mensaje correspondiente a los resultados de las pruebas. Por analogía a la definición de la I(S) se tiene:

   

   Esto representa la información potencial generada al dividir T en n subconjuntos, mientras que la ganancia de información mide la información relevante a una clasificación que nace de la misma división.

   Entonces,

   

   expresa la proporción útil de información generada en la partición. Si la partición es casi trivial, la información de la división será pequeña y esta proporción se volverá inestable. Para evitar este fenómeno, el criterio de proporción de ganancia selecciona una prueba que maximice la expresión anterior, sujeto a la restricción de que la información de la división sea grande, al menos tan grande como la ganancia promedio sobre todas las pruebas realizadas.

7. Criterio de Proporción de Ganancia
8. ID3

El algoritmo ID3 fue diseñado en 1993 por J. Ross Quinlan. El ID3 toma objetos de una clase conocida y los describe en términos de una colección fija de propiedades o de atributos, y produce un árbol de decisión sobre estos atributos que clasifica correctamente todos los objetos. Hay ciertas cualidades que diferencian a este algoritmo de otros sistemas generales de inferencia. La primera se basa en la forma en que el esfuerzo requerido para realizar una tarea de inducción crece con la dificultad de la tarea. El ID3 fue diseñado específicamente para trabajar con masas de objetos, y el tiempo requerido para procesar los datos crece sólo linealmente con la dificultad, como producto de:

1. la cantidad de objetos presentados como ejemplos.
2. la cantidad de atributos dados para describir estos objetos.
3. la complejidad del concepto a ser desarrollado (medido por la cantidad de nodos en el árbol de decisión).

Esta linealidad se consigue a costo del poder descriptivo: los conceptos desarrollados por el ID3 sólo toman la forma de árboles de decisión basados en los atributos dados, y este "lenguaje" es mucho más restrictivo que la lógica de primer orden o la lógica multivaluada, en la cual otros sistemas expresan sus conceptos Quinlan, (1993).

Según Quinlan, (1993).Una regla de clasificación en la forma de un árbol de decisión puede construirse para cualquier conjunto C de atributos de esa forma. Si C está vacío, entonces se lo asocia arbitrariamente a cualquiera de las clases. Si no, C contiene los representantes de varias clases; se selecciona un atributo y se particiona C en conjuntos disjuntos C1, C2,…, Cn, donde Ci contiene aquellos miembros de C que tienen el valor i para el atributo seleccionado. Cada una de estos subconjuntos se maneja con la misma estrategia. El resultado es un árbol en el cual cada hoja contiene un nombre de clase y cada nodo interior especifica un atributo para ser testeado con una rama correspondiente al valor del atributo.

1. Descripción del ID3

El objetivo del ID3 es crear una descripción eficiente de un conjunto de datos mediante la utilización de un árbol de decisión. Dados datos consistentes, es decir, sin contradicción entre ellos, el árbol resultante describirá el conjunto de entrada a la perfección. Además, el árbol puede ser utilizado para predecir los valores de nuevos datos, asumiendo siempre que el conjunto de datos sobre el cual se trabaja es representativo de la totalidad de los datos.

Dados:

1. Un conjunto de datos
2. Un conjunto de descriptores de cada dato
3. Un clasificador/conjunto de clasificadores para cada objeto.

Se desea obtener:

Un árbol de decisión simple basándose en la entropía, donde los nodos pueden ser:

Nodos intermedios: en donde se encuentran los descriptores escogidos según el criterio de entropía, que determinan cuál rama es la que debe tomarse.

Hojas: estos nodos determinan el valor del clasificador.

Este procedimiento de formación de reglas funcionará siempre dado que no existen dos objetos pertenecientes a distintas clases pero con idéntico valor para cada uno de sus atributos; si este caso llegara a presentarse, los atributos son inadecuados para el proceso de clasificación.

Según Blurock, (1996). Hay dos conceptos importantes a tener en cuenta en el algoritmo ID3: la entropía y el árbol de decisión. La entropía se utiliza para encontrar el parámetro más significativo en la caracterización de un clasificador. El árbol de decisión es un medio eficiente e intuitivo para organizar los descriptores que pueden ser utilizados con funciones predictivas.