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
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.- Objetivos Específicos
- Objetivo General
- 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. - Determinar la factibilidad
económica, técnica, social y operativa del
sistema. - 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:
- Toma de decisiones médicas.
- 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.
- Alcances
- 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
- En esta investigación será analizada
solo la base de datos del censo de población y vivienda
del Estado Lara. - 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. - El sistema no está diseñado para ser
operado bajo plataforma de red. - El sistema, no podrá ser operado bajo
ningún sistema
operativo que no sea Microsoft
Windows. - 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.
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".- 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).- 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. - Minería de Datos
- 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:
- Limpieza de datos (Data cleaning) procesamiento de
los datos ruidosos, erróneos, faltantes o
irrelevantes. - Integración de datos (Data integration)
integración de múltiples fuentes
heterogéneas de datos en una única
fuente. - Selección de datos (Data selection)
extracción de los datos relevantes al área de
análisis del almacenamiento de datos. - 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. - Minería de Datos: proceso esencial donde se
aplican diversos métodos para extraer patrones de los
datos. - 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. - 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.
- 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:
- 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. - 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: - 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. - 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.
- 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:
- 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. - 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. - 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. - 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. - Reglas de inducción: la extracción de
reglas si-entonces a partir de datos de importancia
estadística. - Visualización de los datos: la interpretación visual de las relaciones
entre datos multidimensionales. - 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.
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.- 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.- La familia TDIDT
- 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.
- 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:
El árbol de decisión para T es una
hoja identificando la clase Cj .- T contiene uno o más casos, todos
pertenecientes a una única clase Cj
: - 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. - 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.
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.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.- 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. - Poda de los árboles
generados - 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.- Cálculo de la ganancia de
información - Evaluación de los métodos de
aprendizaje
, puede calcularse como:
es la 
sea positivo. Esta probabilidad puede
la cantidad de ejemplos positivos de 
la cantidad de
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):
- 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). - 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. - 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. - 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. - 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.
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.- Estimación del
costo
- 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.
Clase predicha | ||||
Sí | No | |||
Clase Verdadera | Sí | Verdadero positivo | Falso negativo | |
No | Falso positivo | Verdadero negativo | ||
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.
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 KLas 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.- Características de las reglas de
decisiónTanto 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
algoritmosEl 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. - 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 alternativano se exploran. Por este motivo, la elección
debe ser bien realizada. - 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. - Elección del criterio de
divisiónLa 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. - 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. - Criterio de Proporción de
Ganancia - 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:
- la cantidad de objetos presentados como
ejemplos. - la cantidad de atributos dados para describir estos
objetos. - 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.
- 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:
- Un conjunto de datos
- Un conjunto de descriptores de cada dato
- 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.
 Página anterior | Volver al principio del trabajo | Página siguiente  |