Programación Lógica y Recuperación de Información

Una de las aplicaciones prácticas de las Redes Neuronales Artificiales (RNA), es la clasificación de datos, entendida ésta como un proceso de búsqueda de propiedades comunes a una serie de objetos de un dominio del conocimiento, en función de los valores de determinados atributos. Dentro de la cuestión de la clasificación automática, en tanto que proceso subsidiario de procesos más generales englobados dentro de lo que se conoce como "machine learning", uno de los algoritmos de aprendizaje automático más conocidos, basado en "ejemplos", es el denominado ID3, o "Iterative Dichotomizer (version) 3" (J.R. Quinlan, 1979). Trabaja con datos simbólicos, en contraposición a los datos numéricos, y se basa en la obtención de un árbol de decisión (ver anexo), a partir del cual se obtienen una serie de reglas de producción, capaces de representar un dominio o universo determinado, generando conocimiento independiente de dicho dominio (el sistema de aprendizaje parte de un estado inicial del dominio escogido en el que no existe conocimiento de partida, extrayendo patrones comunes de entre los ejemplos utilizados, a partir de los cuales genera una base de conocimientos de aplicación a dicho dominio). El árbol de decisión permite por tanto clasificar los datos de entrada. Se pueden distinguir dos tipos de procesos de aprendizaje:

• Supervisado: los ejemplos o "explicaciones" son proporcionados al sistema por un sujeto externo. Pertenecen a esta categoría las clasificaciones de datos basadas en árboles de decisión en base a ejemplos, como es el caso del algoritmo de aprendizaje ID3.
• No supervisado: los ejemplos u "observaciones" son creados por el propio sistema. Pertenecen a esta categoría los procesos de agrupamiento de datos o data clustering (o simplemente clustering).

Atendiendo a un plano de abstracción conceptual superior, en el denominado "machine learning" o aprendizaje de máquina, es posible diferenciar dos tipos de aprendizaje: aprendizaje memorístico (o aprendizaje de memoria) y aprendizaje cognoscitivo. El primero hace referencia a procesos de memorización de a) hechos y b) secuencias o procedimientos de acciones, siendo el tipo de aprendizaje más fácil de implementar en un sistema computacional "inteligente". El segundo tipo de aprendizaje, el cognoscitivo, es el que hace uso de procedimientos de razonamiento a partir de un conocimiento básico, de forma que sea posible la obtención de "descripciones de clase", generalizaciones que se obtienen de la observación de ejemplos concretos. Es por tanto un tipo de aprendizaje basado en un razonamiento de carácter inductivo, aquel que permite la formulación de principios generales, a partir de casos específicos individuales, a diferencia del razonamiento deductivo, que a partir de generalizaciones, y por medio de la lógica (silogismos), infiere conclusiones de carácter particular y concreto. En el razonamiento inductivo, es la acumulación de observaciones lo que permite llegar a conclusiones de validez universal.

No obstante, no es infrecuente, en los sistemas de aprendizaje automático, encontrar ambos universos de razonamiento, ya que las generalizaciones que se obtienen mediante el razonamiento inductivo, a partir de un grupo relativamente reducido de "ejemplos" u observaciones (fase de entrenamiento previo), servirán posteriormente para la obtención de conclusiones particulares a través de un proceso de razonamiento deductivo.

Los árboles de decisión o clasificación consisten en una técnica de carácter inductivo muy utilizada en el ámbito del aprendizaje automático. Gráficamente, están formados por nodos y ramas. Los primeros representan el identificador de un atributo concreto. Los nodos terminales u hojas representan los valores asociados a dicho atributo, mientras que las ramas. A cada uno de estos valores, se accede a través de una rama que parte del nodo en cuestión. Los casos son dirigidos hacia una u otra rama en función de los valores de sus atributos. Los árboles de clasificación son un método de aprendizaje válido en aquellas situaciones en las cuales los ejemplos de partida se pueden representar mediante un conjunto finito de atributos y valores. Los árboles de clasificación también se pueden concebir, desde un punto de vista algorítmico, como un conjunto de reglas if-then.

El carácter de los árboles de decisión es jerárquico, por lo que solo son capaces de representar conocimiento jerárquico, la mayor parte del mismo. Por otro lado, su construcción tienen un carácter recursivo y descendente, de los conceptos generales a los particulares, razón por la cual el acrónimo TDIDT (Top-Down Induction on Decision Trees) es utilizado para referirse a los algoritmos de construcción de árboles de decisión, como es el caso del algoritmo ID3 de Quinlan.

La mayoría de las heurísticas utilizadas para la determinación de árboles de decisión mediante algoritmos de aprendizaje, se basan en la teoría matemática de la información (C. Shannon, W. Weaver; Bell Laboratories, 1948) [1] [2]. Las heurísticas son criterios, métodos o principios, que permiten decidir, de entre varias alternativas de acción, cuál será la más efectiva para cumplir determinada meta. Permiten restringir el número de evaluaciones, y en consecuencia repercuten en una mejora de los tiempos de búsqueda de soluciones. Entropía y cantidad de información son dos conceptos que se dan la mano en el campo de las heurísticas. Sobre Entropía y cantidad de información, ver en Tio Petros: [1] [2] [3] [4].

El algoritmo ID3 genera lo que se conoce como reglas "duras", es decir, aquellas que solo atienden a dos posibles estados (verdadero-falso, positivo-negativo, 0-1, etc.), y que tienen por tanto un carácter bivalente, a diferencia de las reglas "borrosas", que permiten representar un rango infinito de valores entre dos extremos de una escala, como las que se obtienen mediante algoritmos ID3 "extendidos" (ID4, ID5, ID5R, C4.5, C5, etc.).

Pseudocódigo del algoritmo ID3:

Si todos los ejemplos de E pertenecen a una misma clase C, entonces
   arbol1 <-- nodo etiquetado con C
SiNo
   Si a = f, entonces
      C <-- clase mayoritaria de los ejemplos de E
      arbol1 <-- nodo etiquetado con C
   SiNo
      A <-- mejor atributo de a
      arbol1 <-- nodo etiquetado con A
      Para cada v perteneciente a los valores de A, hacer
         EAv <-- los ejemplos de E que tienen el valor v para el atributo A
         Si EAv = f, entonces
            arbol2 <-- nodo etiquetado con la clase mayoritaria en E
         SiNo
            arbol2 <-- ID3(EAv , a-{A})
         arbol1 <-- añadir a arbol1 el arbol2, a través de una rama etiquetada con v
Devolver arbol1

Otra representación en pseudocódigo del algoritmo ID3:

Aprendizaje-Árbol-Decisión(Ejemplos, Atributos, Default)
   retorna un árbol de decisión

IF no hay Ejemplos, retornar Default
ELSE IF si todos los Ejemplos tienen la misma clasificación,
   retornar la clasificación,
ELSE IF Atributos = vacío, retornar Mayoría(Ejemplos)
ELSE
   mejor-atr <-- elegir-atributo(Atributos, Ejemplos)
   árbol <-- nuevo árbol de decisión con raíz en mejor-atr
   FOR EACH valor v[i] de mejor-atr DO
      Ejemplos[i] <-- {elementos de Ejemplos con mejor-atr = v[i]}
      subar <-- Aprendizaje-Árbol-Decisión(ejemplos[i], Atributos - mejor-atr, Mayoría(Ejemplos))
      agregar rama al árbol con etiqueta v[i] y subárbol subar
   OD
retornar árbol

Los procesos de aprendizaje, que hacen uso de la clasificación de datos, mediante el descubrimiento de patrones, se utilizan con profusión dentro de lo que se conoce como "Data Mining", en castellano minería de datos, explotación de datos, o descubrimiento de conocimiento en bases de datos, diversidad terminológica en torno a la cual existe una cierta polémica.

Maximiliano del Rio es autor de una versión escrita en lenguaje Prolog del algoritmo de aprendizaje ID3. Los archivos correspondientes a esta implementación (librería Clasif) se pueden localizar bien en la sección de código fuente de programacion.com (comprimidos en un "zip"), o en el espacio personal que el propio autor tiene en el "Wiki" de SWI-Prolog. En "guia.txt" se explica el manejo de esta implementación del algoritmo ID3 en Prolog, que hace uso de la interfaz ODBC para consultar las tablas de la base de datos seleccionada, de las que se obtienen los ejemplos necesarios para generar las reglas de producción. Se adjunta además el archivo "clasif.pl", programa de "Data Mining" que hace uso del algoritmo ID3, dotado de interfaz gráfica mediante la utilización de la librería nativa XPCE.

"[...] programa que utiliza la librería anterior [...] Ayuda a generar las reglas y muestra las reglas obtenidas textual y gráficamente; también muestra una traza de como trabaja el algoritmo."

Fuente

Esta interfaz gráfica se abre lanzando el objetivo "?- main." en la línea de órdenes de SWI-Prolog, una vez compilado el programa. Finalmente, la librería "compila.pl" contiene predicados que permiten generar un ejecutable para Windows de los resultados obtenidos, mediante SWI-Prolog.

Para obtener una visión bastante amplia sobre la implementación en lenguaje Prolog de procesos de aprendizaje automático en general, y aprendizaje inductivo mediante árboles de decisión en particular (clasificación de datos), es muy recomendable la lectura del capítulo 18, "Machine Learning", de la (ya clásica) obra de Ivan Bratko "Prolog: Programming for Artificial Intelligence" (2ª ed. Addison-Wesley, 1994; ISBN: 0-201-41606-9). Sobre árboles de decisión trata concretamente el punto 18.6, "Induction of decision trees".

Existe así mismo un repositorio de algoritmos de aprendizaje automático escritos en lenguaje Prolog, Prolog library of machine learning algorithms, un tanto desactualizado eso sí, ya que la última actualización parece datar del año 1994, mantenido por Thomas Hoppe (Fraunhofer-Gesellschaft, Universidad Técnica de Berlín). Los programas están escritos haciendo uso de la sintaxis y, en la mayor parte de las ocasiones, de los predicados predefinidos (built-in predicates) contemplados en el Prolog descrito por Clocksin y Mellish, conocido como "estándar de Edimburgo", basado a su vez en el DECsystem-10 (D. Warren, F. Pereira y L. Pereira), para de esta forma asegurar el mayor grado posible de compatibilidad entre versiones de este lenguaje. Las implementaciones del algoritmo ID3 se localizan en la carpeta "IDT" (ver en cualquier caso el archivo "Readme" para más información).

Más información:

• Algoritmo ID3 de J.R. Quinlan (documento traducido por J.A. Fernández, en PDF, comprimido en un zip).
• Aspectos Básicos del Aprendizaje Simbólico (J.G. Boticario).
• Aprendizaje de clasificadores (F. Berzal Galiano; en PDF).
• ART: Un método alternativo para la construcción de árboles de decisión (F. Berzal Galiano; en PDF).
• ART: Un método alternativo para la construcción de árboles de decisión (F. Berzal Galiano, 2002; tesis doctoral, en PDF).
• IDT: Torgos ID3-like system based on the gain-ratio measure (algoritmo ID3 escrito en sintaxis del Prolog de Edimburgo). Este código se localiza en el directorio sobre Machine Learning del CMU Artificial Intelligence Repository (ver descripción; en cada uno de los directorios existen tres archivos, "0.html", "0.doc" y "readme.txt", que contienen la descripción de su contenido). El directorio dedicado al lenguaje Prolog en general se localiza en este enlace.
• Induction of Decision Trees.
• Árboles, Grafos (en Estructuras de Datos, algoritmia.net).
• Árboles de Clasificación (PDF; tema de los apuntes de la asignatura "Métodos Matemáticos en Ciencias de la Computación", UPV).
• Sistemas de Inducción de árboles de decisión.
• Decision Tree for Optimization Software.
• En Artificial Intelligence Lecture Notes: a) Problem Solving in Prolog; b) Induction of Decision Trees.
• Algoritmo ID3 escrito en Prolog.
• "ID3" en "The Machine Learning Dictionary".
• "IDT: Torgos ID3-like system based on the gain-ratio measure" en CMU Artificial Intelligence Repository. Forma parte del directorio de programas "Machine Learning Algorithms Implemented in Prolog".
• Tesis doctoral: Inducción de Conocimiento con Incertidumbre en Bases de Datos Relacionales Borrosas (A. J. Gómez Flechoso, 1998). En relación con los temas tratados en este "post", ver el capítulo 2 en general, y en particular los apartados 2.1 (Introducción), 2.2 (Descubrimiento de conocimiento y minería de datos), 2.3 (Métodos aplicados de minería de datos), y 2.4 (Programación Lógica Inductiva).
• MLnet (Machine Learning network) Online Information Service.

Anexo - Árboles de decisión

Los árboles de decisión son una representación de los procesos involucrados en las tareas de clasificación. Se componen de:

• Nodos: nombres o identificadores de los atributos.
• Ramas: posibles valores del atributo asociado al nodo.
• Hojas: conjuntos ya clasificados de ejemplos y etiquetados con el nombre de una clase.

Los nodos reflejan propiedades de los objetos del dominio, los arcos o ramas son los distintos valores de dichos atributos y las hojas son las clasificaciones posibles.

[Los árboles de decisión] Se adaptan especialmente bien a aquellos casos en los que:

• Los ejemplos pueden ser descritos como pares valor-atributo.
• La función objetivo toma valores discretos.
• Podemos tomar hipótesis con disyunciones.
• Posible existencia de ruido en el conjunto de entrenamiento.
• Los valores de algunos atributos en los ejemplos del conjunto de entrenamiento pueden ser desconocidos.

[Fuente: Inducción de Árboles de Decisión: extensiones del ID3] [Volver al texto]

[0] comentarios | # | lista |