Un Modelo Conceptualpara el Desarrollo de Árboles de Decisión

con Programación Genética

Leonardo Jiménez MoscovitzFundación Universitaria Konrad Lorenz

Matemático

Director: Dr. Nelson Obregón NeiraIC, MSc, PhD.

Especialización en Informáticay

Ciencias de la Computación

28 de mayo de 2007

Resumen

Este trabajo explora la generación de árboles de decisión siguiendola metodología de la programación genética. Al observar los algoritmosbásicos clásicos como ID3 y algunas de sus limitaciones, surge la inqui-etud de aplicar la PG de la manera menos restringida posible, para asíexaminar las soluciones obtenidas. La presentación es conceptual, aunquese muestran aquí algunos fragmentos de código utilizado.

1

Índice

Introducción 3

1. Árboles de Decisión y PG en el Marco de la IA 41.1. Inteligencia Artificial . . . . . . . . . . . . . . . . . . . . . . . . . 41.2. Aprendizaje Automático . . . . . . . . . . . . . . . . . . . . . . . 41.3. Reconocimiento de Patrones . . . . . . . . . . . . . . . . . . . . . 41.4. Minería de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5. Árboles de Decisión . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5.1. Ventajas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5.2. Inducción de Árboles de Decisión. . . . . . . . . . . . . . 91.5.3. Algunos Métodos de Validación para Reducir el Sobreajuste. 12

1.6. Programación Genética . . . . . . . . . . . . . . . . . . . . . . . 131.6.1. Generalidades de la PG . . . . . . . . . . . . . . . . . . . 15

2. Generación de Árboles de Decisión con PG. 252.1. Tamaño del Espacio de Búsqueda . . . . . . . . . . . . . . . . . . 252.2. Aplicación de la PG a los Árboles de Decisión. . . . . . . . . . . 27

2.2.1. Ciclo Evolutivo General . . . . . . . . . . . . . . . . . . . 292.2.2. Generación de la Población Inicial. . . . . . . . . . . . . . 332.2.3. Operadores Evolutivos y Mecanismos de Selección . . . . 342.2.4. Evaluación de los Árboles de Decisión . . . . . . . . . . . 382.2.5. Diseño General de la Solución . . . . . . . . . . . . . . . . 38

3. Conclusiones 43

Referencias 44

2

Introducción

El presente trabajo exploratorio que representa la investigación desarrolladadurante algo más de un mes, referente a la combinación de dos técnicas modernasde aprendizaje de máquina: los árboles de decisión y la programación genética.Se examinó bibliografía y software existente, y con base en esa exploración sedecidió presentar un desarrollo conceptual que sirviera de base a la generaciónde árboles de decisión mediante programación genética, con la menor cantidadposible de restricciones, y lograr de esta manera la exploración más exhaustivadel espacio de búsqueda.

La ciencia está dominada cada vez más por la necesidad de una aplicabilidadinmediata. La era del conocimiento en la cual se está adentrando la humanidadha incorporado una competitividad comercial cada vez mayor, global e inmedi-ata.

Por lo tanto, se buscan afanosamente nuevas técnicas, que tengan aplicabil-idad en el menor tiempo posible y además, que tengan interés comercial. Estees el caso de las técnicas de IA, muchas de ellas orientadas hacia la minería dedatos. En la medida en que se pueda extraer información útil de una base dedatos, más valiosas se hacen las herramientas que se utilizan para ello, y másapoyo reciben los investigadores que las desarrollan.

La técnica de los árboles de decisión tiene grán interés por ser de aplicaciónsencilla y por ser una aplicación de caja blanca: Un árbol de decisión representaun conjunto de reglas si-entonces, y estas reglas se pueden extraer e interpretarde una manera sencilla.

La construcción del mejor árbol de decisión es un problema de complejidadexponencial, y para algunos tipos de árbol puede llegar a ser un problema NPHard [Llo07]. Los árboles que se obtienen pueden adolecer de algunos problemas,tales como el sobreajuste a los datos de entrenamiento o el excesivo tamaño.

Los algoritmos tradicionales (ID3, C4.5 por ejemplo) no exploran todo elespacio de búsqueda. En este punto, la programación genética puede intentarun aporte en el proceso de construir un buen árbol de decisión. El modelo con-ceptual que se elabora intenta en primera instancia dejar que la evolución corralo más libre posible, con el fin que permita observar los resultados obtenidosbajo esta aproximación.

En un árbol de decisión, se espera que un recorrido desde la raíz hasta unnodo terminal no repita nodos con el mismo atributo. Sin embargo, aunqueen la generación de los árboles iniciales se pueda restringir esta opción paraobtener árboles suficientemente pequeños, no se piensa controlar este aspectoinicialmente. El objetivo que se persigue es que en las primeras implementacionesse pueda observar y examinar el proceso de evolución libre, en el cual la principalo tal vez la única presión evolutiva se deba a la aptitud de los árboles.

En la sección 2.2 se presentan los algoritmos principales, y el esqueleto prin-cipal de la implementación en C++ mediante algunas clases simples.

3

varios meses

varios meses

varios mesesvarios meses

varios meses

algunos meses y días

1. Árboles de Decisión y PG en el Marco de laIA

1.1. Inteligencia Artificial

La Inteligencia Artificial (AI) es una de las disciplinas más avanzadas dentrode las nuevas tecnologías de la información, y ha surgido como una respuestaa la necesidad de encontrar modelos y programas del llamado comportamientointeligente [Mar87]. La AI trata con adaptación, aprendizaje o conductainteligente, para ser desarrollada en máquinas o computadoras.

En el orígen y desarrollo de la AI confluyeron dos puntos de vista: el científico,que intenta simular con el computador la verificación de teorías sobre los mecan-ismos de la inteligencia; y el de ingeniería, que intenta dar a los computadorescapacidades lo más cercanas posibles a las intelectuales [Mar87]. Para ello losusuarios de AI se han debido enfrentar a cuestiones nuevas y muy variadas, y alpretender resolverlas ha desarrollado un enorme conjunto de innovadoras técni-cas: representación y modelización del conocimiento, búsqueda heurís-tica, aprendizaje automático, y técnicas de razonamiento aproximadoentre muchas otras.

Las diferentes técnicas que se han desarrollado a medida que evolucionala AI no son excluyentes entre sí, sino que más bien se complementan unasa otras. Eventualmente algunas técnicas pueden desaparecer del interés de losinvestigadores cuando, según el estado del arte en un momento dado, esténsuficientemente desarrolladas.

1.2. Aprendizaje Automático

Al considerar la AI, es fácil ver que una de las áreas más importantes con-siste en lo que se denomina aprendizaje de máquinas o aprendizaje automático(machine learning). Su objetivo fundamental es el desarrollo de técnicas quepermitan que una máquina, la computadora, pueda generalizar comportamien-tos a partir de información no estructurada, y que se suministra en forma deejemplos.

La generalización del comportamiento es lo que se conoce como aprendiza-je, que se puede considerar en general, perteneciente a uno de los siguientesdos tipos: inductivo y deductivo. El aprendizaje automático se clasifica dentrodel tipo de aprendizaje inductivo, ya que estrae reglas y patrones a partir deconjuntos masivos de datos.

1.3. Reconocimiento de Patrones

Esto nos introduce en el concepto de reconocimiento de patrones, comoun campo del aprendizaje automático: el reconocimiento de patrones se puededefinir como el acto de tomar datos no estructurados de entrada y encontrar enellos categorías, reglas o patrones ocultos. Es de especial interés que las reglasobtenidas se puedan hacer explícitas y sean almacenadas en el computador, con

4

el fin de que sean utilizadas posteriormente para clasificar adecuadamente unconjunto de datos nuevo.

1.4. Minería de Datos

Dentro de los campos de aplicación particulares que existen detrás del apren-dizaje automático se puede encontrar principalmente la minería de datos. Ladisposición de enormes cantidades de información ha hecho crecer un gran in-terés en manipular dichos datos y extraer de ellos información que puede ser devalor para quien posee la base de datos.

1.5. Árboles de Decisión

Dentro del área de la AI, y más exactamente dentro de la sub-área delaprendizaje automático se encuentran los árboles de decisión. Son utilizadosprincipalmente con propósitos de clasificación, pero son también útiles paradescubrir características de los datos que no son directamente visibles [Roa06].Por este motivo, los árboles de decisión son importantes tanto en aplicacionesde clasificación como de minería de datos.

Un árbol de decisión es en esencia un modelo predictivo, esto es, permiteque las observaciones acerca de las características de un elemento conduzcan aconclusiones acerca de un valor objetivo. La técnica de aprendizaje automáticoque permite la inducción de un árbol de decisión a partir de un conjunto dedatos se llama aprendizaje de árboles de decisión.

Si se hace referencia a los árboles de decisión como una técnica, se dice queson un método para aproximar funciones objetivo de valor discreto.

Definición 1.1 (Árbol de Decisión) Sea T un grafo acíclico dirigido, en elcual se cumple que cada nodo del grafo es

1. Un nodo no terminal o interno si tiene p nodos hijos, p ≥ 1. Los nodosinternos están etiquetados con atributos.

2. un nodo terminal u hoja si el nodo no tiene nodos hijos. Los nodos termi-nales están etiquetados con clasificaciones. El conjunto de todas las hojasde T se llama T .

Cada nodo tiene exactamente un padre, a excepción del nodo superior o raiz,que no tiene padre.

Cada arco o rama del grafo que sale de un nodo etiquetado con un atributoai, está a su vez etiquetado con alguno de los posibles valores v de ai.

Los nodos internos equivalen a pruebas de un atributo, y las ramas que salende un nodo equivalen a las resultados para la prueba.

Notación 1.1 Se utilizará la siguiente notación:

El tamaño del árbol T se denota por |T | , y el tamaño del conjunto de

terminales T se denota por∣∣∣T∣∣∣ .

5

A tr ibu to i

A tr ibu to j A tr ibu to k

V a l_1 Va l_ n* * *

V a l_1 V a l_n2* * *

Va lo r A tribu toob je t ivo

V a lo r A tr ibu toob je t ivo

* * *

Figura 1: Estructura de un Arbol de Decisión

Al conjunto de todos los atributos que conforman el árbol de decisión se lellamará A, y su tamaño será |A| .

Al conjunto de todas las clases se les llama Y , y cada clase tiene asignadaun valor entero, de tal manera que C = {0, 1, ...,K − 1} donde K ≥ 2

Por lo tanto, con esta definición, se tiene que la cantidad de nodos delárbol es |T | , mientras que la cantidad de hojas es

∣∣∣T∣∣∣ .

La estructura del árbol de la figura 1 muestra los nodos internos, ramas yhojas. Un nodo interno representa la prueba de un atributo, mientras que lasramas representan los diferentes valores que puede tomar el atributo. Las hojasrepresentan los valores de clasificación para la secuencia de pruebas que va desdeel nodo raiz hasta llegar a la hoja.

Las entradas del árbol de decisión son un conjunto de características o atrib-utos, que pueden representar objetos o situaciones. La salida correspondiente delárbol es un valor correspondiente del atributo que se desea conocer. Se puedetambién entender la salida del árbol como un valor booleano Si/No para losdiversos valores de atributo de salida.

La Tabla 1.1 muestra una tabla de datos usual, tal como se obtiene a partirde las bases de datos originales del usuario. La fila de encabezados de las nprimeras columnas muestran todos los atributos considerados y por lo tantocontienen las pruebas para los nodos internos (por ejemplo ¿Cuanto vale elatributo A?). Las filas 1..m de las primeras n columnas son valores para losatributos considerados, y por lo tanto contienen las etiquetas de las ramas. Las

6

filas 1..m de la última columna son los valores de las clasificaciones para lasfilas correspondientes, y por lo tanto contienen las clases que se asignan para losnodos terminales. Es importante notar que algunos valores se pueden repetir,ya que no es forzoso que todos los m valores de cada columna sean diferentes.

Tabla 1.1 Tabla de datos típica con m observaciones.

Atributo Atributo ... Atributo Valor1 2 n Objetivo

Nombres Atributos → A B ... N CLASE

patrón 1 a1 b1 ... n1 Y1patrón 2 a2 b2 ... n2 Y2

... ... ... ... ... ...patrón m am bm ... nm Ym

Definición 1.2 (Partición del Conjunto de Patrones) Una instancia es unaentrada o patrón en la tabla de datos. Al conjunto de todos los posibles objetosdescritos mediante los atributos se les conoce como espacio de instancias D.El espacio de instancias D se particiona usualmente en dos subconjuntos: unsubconjunto de instancias de entrenamiento S y un subconjunto de instanciasde validación V, tales que (S ∩ V ) = ∅ y (S ∪ V ) = D. Es conveniente que eltamaño de V sea de por lo menos el 20% del tamaño de D, porcentaje que seconsidera aceptable para la mayoría de los casos, aunque otras técnicas proponenporcentajes diferentes (Sección 1.5.3).

Si se toma un conjunto de datos con etiquetas, de m entradas, equivale auna secuencia de m parejas de la forma (Xi, Yi), donde Xi ∈ Rn , siendo nes el número de características de clasificación, y Yi ∈ Y es una etiqueta declasificación asignada al vector Xi.

En la Figura 2, se tiene un espacio de instancias D que está determinadopor una sola variable. La última columna contiene el valor objetivo; entre laúltima columna y las que le preceden existe una función oculta f . Luego lafunción objetivo f es un morfismo desconocido desde cada elemento del espaciode instancias hacia una etiqueta de clasificación objetivo.

El proceso de inducción de los árboles de decisión pretenden hallar unafunción h, llamada hipótesis, que aproxime a la función f . Dado que existenmuchas funciones que pueden aproximar a f , es conveniente definir un espaciode hipótesis H adecuado, en el cual se puedan encontrar todas las posibleshipótesis que se consideren útiles para el caso particular.

Cualquier función booleana puede representarse mediante un árbol de de-cisión [Rus96]. En general, un árbol de decisión equivale a conjuntos de oracionesde implicación, con la forma de reglas Si-Entonces, en la cual se evalúan uno auno los atributos para el conjunto posible de valores que puede tomar.

Para el ejemplo de la tabla 1.1, el árbol de decisión correspondiente repre-senta expresiones de la forma:

7

......

-2.96374574-0.27941987

-2.96462983-0.27937055

-2.97802995-0.27862448

-2.99004805-0.27795786

Y(Valor Deseado)X

......

2812.8251467.9419

16.691724412.7937

-0.50000184-0.7903

-0.4149258-1.3546

Y(Valor Estimado)X

En una Base de Datos:

Se Tienen Nuevos Valores para x:

Función real fOCULTA ex + seno (1 / x)

Hipótesis h

......

?7.9419

?2.7937

?-0.7903

?-1.3546

Y(Valor Estimado)X

......

?7.9419

?2.7937

?-0.7903

?-1.3546

Y(Valor Estimado)X

DATOS ENTRENAMIENTO

Figura 2: Ejemplo de morfismo oculto y una hipótesis (caso de regresión).

(A = a2) ∧ (N = n1) =⇒ Y1

(B = b1) ∧ (N = n2) =⇒ Y2

...otras conjunciones...

Esto es, el árbol de decisión se puede leer como una disyunción de con-junciones.

Sin embargo, dado un problema real pueden existir muchos árboles capacesde representarlos adecuadamente. Algunos de ellos serán mejores que otros ala hora de clasificar correctamente nuevos datos, y se podría eventualmente en-contrar el mejor o posiblemente, los mejores árboles árboles que lo hagan: elproblema de encontrar un árbol óptimo no es de tipo polinomial sino expo-nencial; por lo tanto para problemas relativamente complejos, difícilmente o talvez nunca se podrá garantizar que se ha encontrado un árbol óptimo [Rus96].

Cuando el investigador se enfrenta al problema de tener varios árboles consimilar comportamiento, usualmente se utiliza la estrategia de Occam y se tomael árbol más pequeño (con el menor valor |T |).

1.5.1. Ventajas

Dentro del conjunto de todas las herramientas de soporte a las decisionesdisponibles actualmente, los árboles de decisión tienen algunas ventajas impor-tantes.

Los árboles de decisión son modelos de caja blanca: una vez se haobtenido un modelo, es simple obtener de él una expresión matemáticafácilmente interpretable, a diferencia de modelos de caja negra como lasredes neuronales. La expresión final tiene una lectura e interpretación muyintuitiva lo que facilita su aplicación en múltiples disciplinas.

8

Soportan ruido en los datos de entrada.

Permiten trabajar con pocos datos de entrenamiento: pueden sum-inistrar algunas generalizaciones útiles a partir de pequeñas cantidades dedatos.

Poco costo computacional: los algoritmos principales y más conocidospara la generación de árboles de decisión (ID3, C4.5, etc) son bastanteeficientes y consumen pocos recursos de máquina.

Herramienta integrable: finalmente, los árboles de decisión son unaherramienta que se puede combinar fácilmente con otras herramientas deminería de datos.

1.5.2. Inducción de Árboles de Decisión.

El tipo de aprendizaje que se realiza al construir un árbol de decisión cor-responde a un aprendizaje de tipo inductivo, supervisado, en el cual los datosde entrada con los que se realiza el aprendizaje, que se llaman ejemplo, dansiempre el valor esperado de la función. Para el caso de los árboles de decisión,los ejemplos son tuplas (x, f(x)) donde x es un vector de entradas y f(x) es lasalida esperada.

Como se ha mencionado anteriormente el proceso de inducción consiste enhallar, para un conjunto de datos de entrenamiento que contienen implícita-mente una función f , una función h llamada hipótesis que la aproxime lo másposible [Rus96]. La verdadera definición de f se desconoce, y existen por lo gen-eral muchas opciones para elegir h, cada una de ellas consistente con el conjuntode datos de entrenamiento. Cualquier preferencia por alguna hipótesis en partic-ular, más allá de esta consistencia, constituye un sesgo en el proceso inductivo,y se conoce como predisposición. Para presentarlo de manera matemática sedeben establecer primero unas definiciones: Se llamará D al conjunto completode instancias o patrones.

Definición 1.3 (Hipótesis Consistente) Una hipótesis h se dice consistentecon un conjunto de datos de entrenamiento S para la función objetivo f , si ysolo si h(x) = y para cada tupla (x, y) ∈ S.

Definición 1.4 (Error de Clasificación) Para una muestra de datos D detamaño m, compuesta por tuplas (x, y) ∈ D, si una hipótesis h genera i clasifi-caciones incorrectas, entonces el error de clasificación de la hipótesis h se puede

determinar como eh =i

m. Por tanto, 0 ≤ e ≤ 1.

Una hipótesis consistente debe tener un error de clasificación de 0, aunqueesto no se pueda obtener en casos reales debido al ruido presente en los datosde entrada. Nótese además que se pueden definir otros tipos de medidas paradeterminar el error de clasificación.

Dada la estructura general de un árbol de decisión, la manera más conve-niente de construir un árbol de decisión se basa en un algoritmo clásico que

9

emplea búsqueda descendente (top-down) y egoista en el espacio de búsquedade los posibles árboles de decisión.

El algoritmo general de construcción de un árbol se puede expresar de di-versas maneras [Joa07] [Gue04], [Mit97]. Una versión simplificada se observa enel algoritmo 1.1, tomado de [Mit97].

El interrogante que surge en este momento tiene que ver con el criterio quese utiliza para ejecutar la línea del algoritmo: “seleccionar el mejor atributo pdel siguiente nodo”. En el caso de que se esté comenzando a construir el árbol,se trata entonces de seleccionar cual debe ser el nodo raiz.

Los algoritmos ID3 y C4.5 de Quinlan son dos ejemplos de criterios paraseleccionar los nodos de un árbol de decisión. La explicación que se expone acontinuación se basa en el algoritmo ID3. Para seleccionar cada nodo, comen-zando desde el nodo raíz, el algoritmo ID3 se pregunta: ¿Qué atributo es elmejor clasificador?

La respuesta a este interrogante se halla tomando independientemente cadauno de los atributos, y verificando qué tan bien clasifica él solo a los datos delconjunto de entrenamiento S. El atributo que mejor los clasifique es tomadocomo el nodo raíz; y el árbol se seguirá generando con la misma concepciónhasta finalizar. Los posibles valores que puede tomar el atributo seleccionadoconforman las nuevas ramas que parten de este nodo hacia abajo [Gue04].

Los ejemplos de entrenamiento son repartidos en los nodos descendientes,de acuerdo con el valor que tengan para el atributo de la raíz. Es decir, seconsideran para una determinada rama únicamente los ejemplos que coincidencon el valor del atributo de la raiz especificado en la rama.

Algoritmo 1.1 (ID3 Versión Simplificada)Id3(S,C,A )

Ejemplos: Conjunto de patrones de entrenamiento (S).Clase: valor a predecir (C).Atributos: conjunto de atributos para verificar durante aprendizaje (A)

1. Crear raiz para el árbol de decisión2. Si todos los ejemplos son de clase Ci entonces

3. devolver raiz con etiqueta Ci.4. Si A = ∅ entonces

5. devolver raız con Ck = etiqueta más común en S.6. En otro caso

7. Aj ←− atributo en A mejor clasificador (criterio de entropía.)8. raiz←− Aj9. Para cada posible valor vi de Aj10. Adicione rama debajo de raiz, para prueba Aj = vi.11. sea Svi,Aj ⊂ S patornes con valor vi para atributo Aj .12. si Svi,Aj = ∅ entonces

13. agrege debajo nodo con Ck = etiqueta más común en S.14. si no es vacío, entonces

15. bajo rama agrege subárbol: Id3(Svi,Aj ,C,A−Aj)16. Fin.

10

17. Devuelve raiz.

El algoritmo ID3 utiliza los trabajos desarrollados por Shannon para de-cidir cual es el mejor atributo en cada etapa de inducción del árbol. El métodoconsidera la ganancia en información que es capaz de proveer cada atributo.

Dado un atributo vi, su probabilidad de ocurrencia es p(vi). De acuerdo conlos trabajos de Shannon, la cantidad de información o entropía asociada a esteatributo es:

Entropıa(S) =n∑

i=1

p(i) log2

(1

p(i)

)

Es conveniente cuantificar el costo de representar cada entrada de datos deentrenamiento mediante la cantidad de bits de información que se requierenpara describirla. Cada bit tiene dos estados posibles, y es por ello que la teoríade la información utiliza logaritmos en base 2 para calcular la entropía.

La entropía cuantifica de alguna manera la cantidad de ruido, desorden oimpureza que tienen los patrones de una colección de patrones o de un sis-tema completo. Mientras más entropía tiene un sistema, más desordenado es, ymientras menos entropía se puede decir que presenta un patron más claro.

La heurística del algoritmo ID3 utiliza el concepto de entropía para selec-cionar el órden en que aparecen los atributos en el árbol. La heurística debehallar el atributo que reduzca en mayor cantidad la entropía del conjunto dedatos, logrando de esta manera que se reduzca la cantidad de información nece-saria para describir completamente cada entrada del conjunto de datos de en-trenamiento. En otras palabras, se busca el atributo que provea mayor gananciaG, para un conjunto de datos de entrenamiento S y un determinado atributo A:

G(S,A) = Entropıa(S)−∑

v∈A

|Sv|

|S|Entropia(Sv)

donde |Sv| es el subconjunto de S para los cuales un atributo A toma el valorv, y el valor |S|

El atributo que ofrecerá una mayor ganancia de información es aquel quemás reduzca la entropía del conjunto de datos. De todos los atributos posibles,el que más ganancia de información ofrezca será seleccionado como nodo raíz, yasí sucesivamente.

De esta manera, el algoritmo ID3 realiza el proceso de búsqueda en el espaciode hipótesis H, encontrando en este proceso la hipótesis que mejor ajusta a losdatos del conjunto de entrenamiento S. A medida que el árbol se va llenando,la hipótesis h es cada vez más compleja.

Sin embargo, en el ID3 se presenta sesgo inductivo o preferencia en la búsque-da en los aspectos siguientes:

11

Hipótesis compactas: ID3 tiene preferencia por árboles pequeños sobreárboles grandes, intentando asegurar que la búsqueda termine siempre lomás cerca posible a la raíz.

ID3 es un algoritmo egoista, de búsqueda primero en profundidad.

De acuerdo con estos aspectos mencionados, es claro que ID3 no intentaexplorar todo el espacio de búsqueda. Por lo tanto, se puede discutir si ID3generaliza más allá de los datos observados. Otra pregunta fundamental es siel árbol encontrado es el menos parsimonioso posible. Dada la complejidad delproblema, que es exponencial, los costos de averiguarlo pueden ser prohibitivosen tiempo y recursos de máquina.

Por otra parte, existe la posibilidad de que el árbol encontrado medianteel algoritmo ID3 sea sobreajustado, y por lo tanto más que generalizar hayamemorizado.

Definición 1.5 (Sobreajuste) Dado un espacio de hipótesis H, se dice queh ∈ H está sobreajustado a los ejemplos de entrenamiento, si existe una hipótesisalternativa h′ ∈ H tal que h tiene error de clasificación menor que h′ para lospatrones de entrenamiento, pero h tiene un error de clasificación mayor que h′

para la distribución completa de los ejemplares del problema, esto es:eh < eh′ con los patrones de entrenamiento S.eh > eh′ con todos los patrones D.

Por lo tanto, al evaluar h con el conjunto de datos de validación V , es quese conocerá si hay sobreajuste. El sobreajuste se puede producir por diversosfactores, uno de ellos es la presencia de ruido en los datos y el ajuste del árbola presencia del ruido. Pero tal vez la principal fuente de sobreajuste es disponerde un conjunto de datos de entrenamiento S pequeño: mientras menos datos setengan para entrenamiento, más fácil es que un modelo aleatorio cualquiera seajuste a estos datos, a la vez que tiene un comportamiento pobre con los datosde validación.

1.5.3. Algunos Métodos de Validación para Reducir el Sobreajuste.

La técnica común de dividir el conjunto de datos en datos de entrenamientoy datos de validación, reduce el conjunto de datos de entrenamiento y por ellocontribuye de cierta manera al sobreajuste.

Existen diferentes técnicas para reducir el sobreajuste, entre ellos está lapoda del árbol. Para ello, se considera cada nodo del árbol como candidato aser eliminado, y se observa el impacto de esta eliminación en el comportamientogeneral del árbol. El nodo se elimina solo si el árbol podado se comporta igual omejor que el original [Rus96]. La técnica de poda del árbol es sin embargo costosaen recursos de computación. Por ello, se proponen otras técnicas para reducir elsobreajuste: la validación cruzada y la validación dejar-uno-fuera (leave-one-outvalidation).

12

Definición 1.6 (Técnica de la Validación Cruzada) Sea S el espacio dedatos de entrenamiento, y sea P una partición de S en K subconjuntos deigual tamaño. El método de la validación cruzada consiste en que para cada Pi,1 ≤ i ≤ K, se realiza el entrenamiento con la unión de los K − 1 subconjuntosrestantes, y empíricamente se determina el error ei en el conjunto Pi, definidocomo la relación entre los errores de clasificación y el número de patrones enPi (ver definición 1.4). El error final que devuelve es el valor promedio de todoslos ei.

En esta técnica se entrena y se evalúa con un conjunto diferente cada vez. Elerror final esperado de la iteración de aprendizaje deberá ser el valor promediode todos los ei.

Definición 1.7 (Técnica Leave-One-Out) Sea S el espacio de datos de en-trenamiento, y sea P una partición de S en |S| subconjuntos. El método de lavalidación cruzada consiste en que para cada Pi, 1 ≤ i ≤ |S| , se realiza el entre-namiento con la unión de los |S|−1 subconjuntos restantes, y empíricamente sedetermina el error ei en el conjunto Pi, definiendo ei = 1 si hubo error y ei = 0si no lo hubo. El error final que devuelve es

e =

∑|S|i=1 ei|S|

.

La técnica dejar-uno-fuera toma todos los datos excepto uno para entre-namiento, y valida con el único dato disponible para validación. Cada vez setoma un patrón de validación diferente, repitiendo hasta que ha validado concada uno de los datos disponibles.

Las dos técnicas mencionadas son costosas computacionalmente, en partic-ular la técnica leave-one-out, pero esta última reporta mayores beneficios a lahora de reducir el sobreajuste. Sin embargo, en la sección siguiente se definen loselementos básicos de una técnica que teóricamente puede ayudar en el procesode generación y selección de un buen árbol de decisión.

1.6. Programación Genética

A la hora de definir un algoritmo de inducción para un árbol de decisión,bien sea el ID3, el C4.5 o muchos otros, se puede estar definiendo un sesgoinadecuado en la búsqueda de la hipótesis h.

Uno de los ingredientes que se han considerado a la hora de elaborar lasmetodologías de aprendizaje automático es la necesidad de la intuición humanaen el análisis de datos. Algunos desarrolladores de sistemas de aprendizaje au-tomático la intentan eliminar, mientras que otros desarrolladores la incorporanal tomar una aproximación colaborativa para la interacción hombre-máquina.Sin embargo, si se considera que el Ingeniero de Conocimiento debe especificaraspectos vitales como por ejemplo la representación de los datos y los mecanis-mos de búsqueda de patrones, se llega a la conclusión de que el factor humanoy por tanto la intuición, no se puede eliminar totalmente [Mar87].

13

La programación genética (PG) [Koz92] proporciona una técnica para re-ducir sustancialmente algunos sesgos propios de la orientación algorítmica oheurística de la solución. Se basa en reproducir computacionalmente algunastécnicas propias de la naturaleza que resultan en una mejor exploración desoluciones dentro de todo el espacio de búsqueda posible para un problemadeterminado.

La PG es una extensión de la técnica de los algoritmos genéticos, dondelos individuos que evolucionan son estructuras de tipo árbol que pueden mode-lar muchos tipos de problemas diferentes. Los árboles que evolucionan puedenrepresentar expresiones matemáticas, programas de computador, secuencias depasos para realizar una labor cualquiera, etc.

Mediante técnicas como la PG, se reduce sustancialmente el sesgo inadecuadoen la exploración del espacio de búsqueda de una solución. Estas técnicas evitanque el programa se quede examinando exclusivamente alguna zona del espaciode búsqueda: se produce una exploración más general del mismo, si bien porrazones obvias de complejidad y tiempo computacional no se explora todo elespacio de búsqueda.

Al igual que los árboles de decisión, la PG es un modelo de caja blanca:la solución que se halla es expresable, y en caso de tener una complejidad al-ta, se puede en muchos casos simplificar utilizando metodologías adecuadas depostprocesamiento de datos.

Desde el punto de vista comparativo con la biología, la PG tiene preferen-cia por algunas de las características del pensamiento neo-darwiniano, que haresumido Mayr [May88] y se presentan a continuación. Este grupo de carac-terísticas participan en la constitución del marco de la programación genéticaen general:

El individuo es el objetivo primordial de la selección.

La variación genética es en gran medida un fenómeno aleatorio: los pro-cesos estocásticos juegan un papel significante en la evolución.

La variación genotípica es principalmente un producto de la recombi-nación, y en últimas de la mutación.

La evolución gradual puede incorporar discontinuidades fenotípicas.

No todos los cambios son necesariamente consecuencias de selección nat-ural ad hoc.

La evolución es un cambio en adaptación y diversidad, no simplemente uncambio en las frecuencias de los genes.

La selección es probabilística, no determinística.

Los diferentes desarrollos de PG comparten gran cantidad de propiedadescomunes con los modelos biológicos de la evolución::

14

La PG utiliza procesos de aprendizaje colectivo de una población de indi-viduos. Cada individuo representa o codifica uno de los puntos del espaciode búsqueda de las soluciones potenciales de un problema.

Los descendientes son individuos generados por procesos aleatorios quepretenden emular la mutación y el cruce. La mutación se puede asimi-lar a un proceso de autoreplicación errada, en la cual cambios pequeñostienen mayor probabilidad de ocurrir que los cambios grandes. El cruceintercambia información entre (usualmente) dos individuos.

Mediante la evaluación de los individuos en su ambiente, se puede asignarun valor de calidad o aptitud a cada uno de los individuos. El mínimo re-querimiento es que los valores de aptitud sean comparables, de tal maneraque se pueda conocer cual es mejor. De acuerdo con la medida de apti-tud, el proceso de selección favorece los mejores individuos para que sereproduzcan más a menudo que los peores.

La fortaleza de la metodología de la PG radica, entre muchos otros factores,en la diversidad y diferencias entre los individuos. Esa diversidad facilitaque se explore mejor el espacio de búsqueda, y que durante el proceso evoluti-vo el sistema converja adecuadamente, es decir que se encuentre un individuosatisfactorio.

Cuando por algún motivo los individuos de la población van perdiendo di-versidad, por ejemplo cuando los buenos individuos dominan excesivamente laevolución, se habla de convergencia prematura. Si este es el caso, el procesoevolutivo puede quedar atrapado en un mínimo local y no se obtiene el resultadoesperado, siendo necesario reiniciar el proceso.

1.6.1. Generalidades de la PG

A continuación se van a examinar los elementos principales que intervienenen la técnica de la PG, con el fin de conocer algunos aspectos conceptuales gen-erales importantes. Se expondrán algunas definiciones, por sencillas que parez-can, con el fin de hacer claridad en el uso de la terminología. En esta secciónse tratarán los aspectos generales, mientras que detalles adicionales que han dedefinir los algoritmos se especifican en la sección 2.2.

Se denomina población a un grupo de individuos que pueden interactuarjuntos. Cada individuo es una solución potencial a un problema y su estructuraen PG es de tipo árbol n-ario (figura 5). La principal manera en que interactuanlos individuos es en los procesos de competencia entre ellos (torneo), y el losprocesos de creación de una nueva generación. El ambiente o entorno es todoaquello que rodea a un individuo, y lo presiona de cierta manera al verificar sitiene el comportamiento esperado.

El genotipo denomina a la composición genética de un individuo y quedefine sus potencialidades; en PG el genotipo determina la representación delproblema en la estructura propia del individuo, el árbol. Por otra parte, elfenotipo denomina los rasgos observables del individuo. Durante el proceso

15

evolutivo en PG, debe existir una función que permita observar el fenotipo aque da lugar un determinado genotipo. La capacidad de computación actualpermite que en PG esta función sea la más simple posible, ya que se puedeoperar de manera eficiente con estructuras computacionales complejas que seasemejan mucho al problema real y requieren la menor cantidad de codificación.(esto no vale para todas las técnicas, ya que por ejemplo los algoritmos genéticossí requieren una alta codificación del problema).

Desde el punto de vista del ambiente, la aptitud de un individuo es unafunción que permite evaluar su comportamiento, esto es, verificar en qué pro-porción cumple con determinadas habilidades y qué tan bueno es con respectoa los demás. Para el interés del propio individuo, la aptitud se define comola probabilidad de que el individuo viva y sea seleccionado para reproducirse(viabilidad), o también como una función del número de descendientes queeste tiene (fertilidad del individuo). En la terminología de koza [Koz92], sedenomina paisaje de aptitudes (fitness landscape) a la hipersuperficie obtenidaal graficar la función de aptitud aplicada a cada punto del espacio de búsquedaexplorado.

La selección es el proceso mediante el cual algunos individuos de la poblaciónson seleccionados para reproducirse. Este proceso se lleva típicamente medianteuna combinación de técnicas aleatorias y probabilísticas. Dentro de los tipos deselección, se pueden resaltar dos de ellos que son la selección dura y la selecciónblanda. La selección dura solo permite que los mejores individuos se manten-gan para conformar una nueva generación. La selección blanda tiene lugarcuando se utilizan métodos probabilísticos que de alguna manera permiten queindividuos de aptitud baja también participen en la formación de una nuevageneración.

Se llama generación a cada iteración que obtiene una nueva población alaplicar operadores evolutivos. Una nueva generación implica una nueva medi-da de la aptitud (fig 3). Los operadores evolutivos que se trabajarán aquí sonprincipalmente tres: operador de cruce, de clonación y de mutación, si bien elproceso de selección también es considerado como un operador genético. Eloperador de cruce forma un nuevo cromosoma (individuo en PG) combinandopartes de cada uno de los cromosomas (individuos) padre. El operador de mu-tación forma un nuevo individuo mediante alteraciones aleatorias de parte dela estructura del individuo padre. El operador de clonación crea una réplicadel padre en la nueva generación. Este operador es la base del elitismo, que esuna técnica que garantiza que el mejor individuo (o los mejores individuos) decada generación, pase a la generación siguiente sin modificaciones, asegurandoque la aptitud máxima obtenida en la población nunca decrezca.

Estos elementos descritos se pueden ver de manera gráfica en la figura 3.De manera más formal Bäck y otros autores han definido algunos de los

elementos que conforman el marco de trabajo para PG así [Bac00]:

Notación 1.2 Sea I el espacio arbitrario de todos los individuos a ∈ I.

Sea F : I → R una función de aptitud para los individuos.

16

Población Inicial (Generación Aleatoria):

Aplicar Función de Aptitud (Evaluación)

OperadoresEvolutivos

Nueva Generación:

¿Alguno Cumple Condición

Aptitud=UMBRAL?

*

cos +

x 7 x

+

exp seno

x /

x1

+

exp tan

*

3x

+

tanx

3

+

exp seno

x /

x1

*

invm

senh

*

3x

+

lnx

3

invm

+

lnx

3

Figura 3: Esquema gráfico del proceso evolutivo en PG

Sea µ el tamaño de la población de padres.

Sea λ el tamaño de la población de hijos.

Sea P (t) = (a1(t), a2(t), ..., aµ(t)) ∈ Iµ una caracterización de la poblaciónen la generación t.

Sean s : Iλ → Iµ,m : Iκ → Iλ, r : Iµ → Iκ operadores evolutivos deselección, mutación y cruce respectivamente.

Sean θι, θr, θm, θ conjuntos de parámetros para condiciones de terminación,de los operadores de cruce y mutación y generales.

Es importante notar que para el caso del presente trabajo, se puede tenera convenciencia µ = λ = κ. El diagrama de flujo general de la PG se observaen la figura 4, mientras que [Bac00] propone un algoritmo en pseudocódigo conalgunas modificaciones, tal como aparece en el algoritmo 2.1.

La población está conformada por individuos o árboles, cuya aptitud debeser medible por el entorno. Lo que se exige en primera instancia, es que la estruc-tura del árbol sea sintácticamente correcta para modelar el problema deseado,y que esa corrección sintáctica se mantenga a medida que progresa la evolu-ción. Además, en cualquier algoritmo de PG es importante tener en cuenta dosaspectos muy importantes:

1. La aptitud de la nueva generación debe estar relacionada con la aptitudde la generación de padres. Si esto no fuera así, el proceso degeneraría enuna búsqueda aleatoria.

17

Generación = 0

¿Cumple Criterio Terminación?

Individuo = 0

¿Individuo = M?

Evaluar Aptitud de Cada Individuo

Crear Población Inicial

Seleccionar Probabilísticamente Operador Genético

Seleccionar Dos Individuos Probabilísticamente y por Aptitud

(Torneo)

Individuo = Individuo +1

Realizar Cruce

Insertar Nuevos Individuos en Nueva

Población

Individuo = Individuo +1

Seleccionar Un Individuo Probabilísticamente y por Aptitud

(Torneo)

Realizar Reproducción

Realizar Mutación

Insertar Nuevos Individuos en Nueva

Población

No

No

Clonación / Mutación Cruce

MutaciónClonación

Generación = Generación + 1 Si

Generar Resultado

Si

Fin

Figura 4: Diagrama de flujo para la PG (Modificado de [Koz92])

18

E

B

D

b2b1

1 3 2

d1

d3

2 3

e1

e2

Si B=b1 y D=d1 entonces 1OSi b=b1 y D=d2 entonces 3OSi B=b1 y D=d3 entonces 2OSi B=b2 y E=e1 entonces 2OSi B=b2 y E=e2 entonces 3

Regla:

Figura 5: Ejemplo de árbol de decisión representado en PG.

2. Cualquier variación heredable puede ser introducida en la aptitud de lanueva generación. Si no fuera así, no sería posible un mejoramiento con-tínuo en la búsqueda de un óptimo.

Al igual que en los árboles de decisión, los individuos de la población en PGson árboles con nodos internos, ramas y nodos terminales. En el caso general, losnodos internos de un árbol en PG representan funciones, y las ramas enlazan conotros nodos hijos que son los diferentes argumentos que puede tener una funcióndeterminada; los nodos terminales representan ya sea constantes o variablesque toman su valor de los datos de entrada (que se lee en el momento de laverificación de la aptitud del individuo, de validación o en la aplicación final).Los nodos y ramas de un árbol de PG puede representar objetos muy diferentes.En la figura 5 se observa un árbol que representa una árbol de decisión típico.

Los nodos terminales y no terminales se construyen a partir de un conjun-to de funciones llamadas funciones primitivas, que pueden por ejemplo fun-ciones matemáticas típicas o funciones construidas a gusto del diseñador. Elsistema evlutivo debe construirse de tal manera que cumpla con el requisitode clausura [Koz92], que especifica que un nodo terminal acepte cualquier val-or posible del conjunto de datos de entrada, y que un nodo no terminal aceptede los nodos hijo cualquier valor que ellos puedan suministrar y que utilice elsistema.

Generación de la Población Inicial. Una característica propia de la PGes la metodología que sigue para generar los individuos y evolucionarlos, esque que se basa en todo momento, en métodos probabilísticos. Para generar lapoblación inicial, se define previamente un tamaño de población m, cuyo valorrecomendado varía de acuerdo con diferentes factores entre ellos la complejidaddel problema. Un valor típico de m puede estar en el rango comprendido de 300

19

a 500 individuos. Luego, se comienza a crear lo que se llama población inicialdonde cada uno de los m individuos es generado de manera aleatoria en buengrado.

De manera resumida se puede ver que el proceso de generación de cada indi-viduo de la población inicial consiste en establecer probabilísticamente los tiposde nodo (terminales y no terminales), escoger probabilísticamente las funcioneso tipos de nodo terminal según corresponda, y así sucesivamente hasta com-pletar el individuo con nodos terminales. El algoritmo se puede observar en lasección 2.2.

Datos de Entrenamiento y Validación. Todo sistema de aprendizaje au-tomático requiere un conjunto de valores de entrenamiento o aprendizaje S.Para el caso de la PG, la filosofía es la misma que para la inducción de árbolesde decisión: se dispone de un conjunto de datos D, del cual se toma un sub-conjunto S para entrenamiento y un subconjunto V para validación, tal quecumplan con la definición 1.2.

Evaluación de los individuos. Una vez que se ha generado la población, yse dispone tanto del conjunto de datos de entrenamiento y validación, el pasosiguiente consiste en evaluar los individuos para verificar qué tambien ajustana los datos. Esta medida se llama medida de aptitud. Esta medida debe sercapaz de evaluar cualquier individuo posible que se encuentre en la población,con cualquiera de los datos disponibles.

Para ello, se toma cada uno de los individuos y se les suministra como entradacada una de las entradas en S. Para cada individuo, se calcula el error cometidoal evaluarlos con todas las tuplas de datos en S. Las diferentes maneras decuantificar el error nos dan diferentes medidas posibles de aptitud.

Operadores Evolutivos. Los operadores evolutivos son principalmente: se-lección, cruce, mutación y clonación. Se pueden definir nuevos operadores evo-lutivos de acuerdo con la conveniencia del investigador.

En la reproducción, un individuo es seleccionado probabilísticamente, deacuerdo con su aptitud, para ser replicado en la nueva generación.

En la mutación, un individuo es seleccionado probabilísticamente de acuerdocon su aptitud. Aleatoriamente se selecciona un nodo cualquiera del árbol, difer-ente del nodo raiz. Todo el subárbol que se encuentra bajo el nodo seleccionadose elimina, y su lugar es reemplazado por un nuevo árbol generado probabilís-ticamente, de la misma manera como se genera cualquier árbol de la poblacióninicial. El nuevo individuo obtenido pasa a formar parte de la nueva generación(Figura 6).

En el cruce, que se puede observar en la figura 7, la diferencia consiste enque se seleccionan dos individuos. En cada uno de ellos, se selecciona alatoria-mente un nodo no raiz. Los subárboles ubicados bajo cada nodo seleccionado seintercambian. Los dos individuos resultantes pasan a formar parte de la nuevageneración.

20

E

B

D

b2b1

1 2 3

d1

d3

1 3

e1

e2

E

B

D

b2

c1

1 2 3

d1

d31 3

e1

e2

C

E

c3

c 2

b1

1 2

e1

e2

1

PUNTO DE MUTACION

NUEVA GENERACIÓN

HIJO

GENERACIÓN ACTUAL

X

x

1

Nodo con atributo X

x=Resultado de evaluar X

Clasificación

PADRE SELECCIONADO

ARBOL NUEVO

Figura 6: Mutación de un árbol de decisión.

Elitismo. Un concepto importante en la evolución artificial es el elitismo. Sepuede pensar que no tiene mucho sentido que se pierda el mejor individuo al crearuna nueva generación, ya que muy posiblemente ha sido el fruto de un procesoevolutivo y el sistema debería posiblemente trabajar mucho para obtener unindividuo similar. Siendo así, las evoluciones artificiales consideran típicamentereplicar o clonar el mejor individuo de una generación, en la generación siguiente.

Selección de Individuos. La selección de los nuevos individuos se puederealizar mediante estrategias diferentes; en el presente trabajo se consideraráúnicamente la selección por torneo. La literatura de PG básica, por ejemplo[Koz92] compendia algunas técnicas principales de selección, aunque existendiferentes variantes para implementarlas:

1. Selección Proporcional (fitness proportionate): los individuos se eligende acuerdo con la contribución de su aptitud respecto de la aptitud totalde la población. Esta técnica tiene diferentes implementaciones: La téc-nica de la ruleta, la técnica del sobrante estocástico, la técnica universalestocástica, y la técnica del muestreo determinístico. Sin embargo, se debetener en cuenta que si existe una supersolución en la población, esto es,un individuo excepcionalmente bueno con respecto a todo el resto de in-vididuos, una selección basada en la aptitud escogerá muy probablemente

21

E

B C

D

A

a2

c1

b2b1

a1

1 2 3

d1

d3

1 3

e1

e2

1

C

B E

F E

c3

c2

c1

b2b1

1 2

e1

e2

1

1 2

e1

e2

f2

3

E

B C D

A

a2

c1

b2

c1a1

1 2 3

d1

d3

1 3

e1

e2

1

C

B

E

F C

c3

c2

b1

b2b1

1 2

e1

e2

1

1 2

c1

c2

f2

3

PUNTO DE

CRUCE

PUNTO DE

CRUCE

NUEVA GENERACIÓN

INDIVIDUO SELECCIONADO 1

INDIVIDUO SELECCIONADO 2

HIJO 1 HIJO 2

GENERACIÓN ACTUAL

X

x

1

Nodo con atributo X

x=Resultado de evaluar X

Clasificación

Figura 7: Cruce de árboles de decisión.

22

la misma solución; la población perderá rápidamente diversidad y se ten-drá una convergencia pramatura hacia una solución subóptima.Por otraparte, si en la selección proporcional todos los individuos tienen aptitudesmuy parecidas, el proceso se asemeja a una selección aleatoria. El méto-do proporcional trata de evitar estos problemas utilizando un esquema deescalamiento y mapeo de la aptitud de cada individuo predefinido [Gol89].

2. Selección por Torneo: El torneo consiste en seleccionar aleatoriamentedos o más individuos, y hacerlos competir con base en la aptitud de cadauno. El que tenga la mejor aptitud, es seleccionado.

El método del torneo ayuda a evitar en gran parte uno de los proble-mas que puede enfrentar la PG simple: la convergencia prematura.Mediante la realización del torneo, cualquier individuo, incluso un mal in-dividuo, puede participar en la nueva generación (esto es garantizado porla selección aleatoria inicial de los dos individuos). Si los individuos uti-lizados para crear una nueva generación se seleccionaran únicamente conbase en la aptitud, al cabo de unas cuantas generaciones se tendría unapoblación excesivamente homogénea, conformada por individuos idénticoso muy parecidos, usualmente los mejores individuos encontrados en lasprimeras evoluciones.

Se tienen 2 métodos para aplicar la selección mediante torneo:

a) El método determinístico: se escoge el número de invididuos a se-leccionar, se eligen estos de manera aleatoria y luego se comparancon base en la aptitud. Este esquema puede manejar tanto proble-mas de minimización como de maximización sin necesidad de cambiosestructurales en la función de aptitud, además de poderse paralelizarfácilmente [Bac00].

b) El método probabilístico: similar al anterior, excepto que se generanvalores aleatorios que tendrán mayor probabilidad de seleccionar elindividuo más apto.

Una característica de la PG es que utiliza intensivamente métodos aleatoriosy métodos probabilísticos. En diferentes procedimientos se deben generar aleato-riamente, valores de un tipo y un rango seleccionable por parte del usuario.

En el caso de la selección de un individuo para aplicar un operador genéticopor ejemplo, PG realiza lo que se denomina torneo. Selecciona aleatoriamenteun individuo y luego otro, y los pone a competir. Para ello, genera un númeroaleatorio entre 1 y el tamaño de la población. El entero retornado indica cual esel primer individuo seleccionado. Repite el proceso, cuidando de no seleccionarel mismo individuo. Una vez que se tienen los dos individuos para el torneo,se pueden aplicar varios métodos para determinar cual es el ganador: uno deellos consiste en competir directamente basados en la aptitud. El otro métodoconsiste en normalizar las aptitudes en la escala (0, 1) para luego hallar un valoraleatorio entre 0 y 1. El individuo que corresponda al rango donde cae el valoraleatorio, es el individuo seleccionado.

23

Otro caso similar ocurre cuando se trata de seleccionar cual operador evo-lutivo aplicar al individuo. Cada operador evolutivo tiene una probabilidad deocurrencia ubicada en el rango [0, 1]. En todo caso, la suma de las probabilidadesconsideradas debe ser 1. Se segmenta el intervalo [0, 1] y a cada probabilidad sele asigna un segmento dentro de ese valor (tal como una ruleta). Se genera unvalor aleatorio, y se verifica a qué operador evolutivo corresponde el intervalodonde cae dicho valor, para retornarlo como operador seleccionado.

Ejemplo 1.1 Este ejemplo utiliza el método de la ruleta para seleccionar unoperador evolutivo. Si PX = Prob. de Cruce, PC = Prob. de Reproducción oClonación y PM = Prob. de Mutación, entonces si se tienen los valores paralas probabilidades: PX = 0,95, PC = 0,03, PM = 0,02. Los rangos se puedenestablecer: cruce = 0− 0, 95; clonacion = 0,95− 0, 98; mutacion = 0,98− 1. Sies el caso que por ejemplo, se genere un valor aleatorio de 0, 961, entonces eloperador seleccionado es la clonación.

Para seleccionar individuos el proceso es análogo, pero en este caso se tra-baja con un valor de probabilidad del individuo i, que se puede llamar Pi y cuyovalor está asociado a la aptitud del mismo. Una vez asignados los valores deprobabilidad para cada individuo de la población, o para cada individuo que par-ticipa en un torneo, el programa continúa de manera similar a la que se acabade mostrar.

Criterio de Terminación. La población continuará evolucionando hastatanto no se cumpla un criterio que nos diga o bien que ha pasado una cantidadde generaciones excesiva, o se ha logrado un individuo que aproxima suficiente-mente bien al conjunto de datos de entrenamiento y validación. En cualquierade los dos casos, el programa devuelve el mejor individuo encontrado hasta elmomento.

24

2. Generación de Árboles de Decisión con PG.

En este capítulo se va a explorar una técnica que combinan la aplicación deárboles de decisión, los cuales van a ser generados mediante técnicas de GP:Por una parte, se aplican los árboles de decisión como una representación de unconjunto de reglas que se pueden extraen de unos datos de entrenamiento. Porotra parte, se trata de utilizar la programación genética como mecanismo paragenerar y buscar un buen árbol; esto es, un árbol que represente un conjuntode reglas que clasifiquen correctamente los datos de entrenamiento, validacióny los nuevos datos que lleguen.

Bajo esta perspectiva, se reducen o eliminan sustancialmente algunos de losproblemas inherentes a los árboles de decisión utilizando algoritmos como el ID3o C4.5. Por ejemplo, se reduce el sesgo inductivo, por cuanto la programacióngenética explora más libremente.

Existen trabajos en esta área, tanto teóricos como de aplicación práctica, porejemplo [Llo07] quienes presentan alguna teoría y aplicaciones con el algoritmoGALE (Genetic and Artificial Life Environment) para evolución paralela deárboles de decisión. En [Dim06] se presenta una propuesta de técnicas evolutivaspara construir árboles de decisión generalizados.

El esquema que se va a trabajar es el de generar un diseño conceptual de unsistema evolutivo que permita trabajar con árboles de decisión, que incorpore lastécnicas básicas, aunque tenga posibilidad de crecimiento futuro. Al incorporarla menor cantidad de heurísticas posibles, se espera observar el proceso evolutivode los árboles en condiciones de máxima “libertad” posible.

2.1. Tamaño del Espacio de Búsqueda

A continuación se propone una manera de estimar el tamaño del espaciode búsqueda para la solución de problemas mediante árboles de decisión paraatributos binarios. La expresión se ha desarrollado inductivamente. Ello se basaen algunos supuestos:

1. Inicialmente se supone, por simplicidad, que todos los atributos son detipo binario.

2. Cada árbol se puede llenar con plena libertad. Esto incluye, al menosteóricamente, que se puedan generar árboles con un único nodo, el nodoraíz, y que obviamente su valor debe corresponder a uno de los valores declasificación.

3. Se supone que se tiene una tabla de patrones, y que en ella se identifi-can |A| atributos diferentes. Cada uno de ellos puede tener una cantidaddiferente de valores posibles para sus atributos. Sea vAi el conjunto de losvalores que puede tomar un atributo Ai, y sea |vAi | la cantidad de dichosatributos.

4. Sea rL la cantidad de ramas por nivel L. Para el nivel 0 se toma r0 = 1,y para los nodos siguientes, se toma r1 = 2, r2 = 4.

25

5. Para el primer nivel, el nodo raíz, se tienen |A| +∣∣∣T∣∣∣ maneras distintas,

donde∣∣∣T∣∣∣ es la cantidad de tipos de nodo terminal que se dispone.

6. El nivel máximo que puede alcanzar el árbol, sin repetir atributos enun recorrido cualquiera es |A| , siendo el nodo raiz el nodo 0. Las opcionespara escoger un nodo determinado en cada nivel L son de:(|A| − L+

∣∣∣T∣∣∣)

Mientras que las opciones para llenar desde el nodo raiz hasta los nodosde un nivel L, dada una selección previa del nodo raíz, son de:

(|A| − (L− 2))L! ·(|A| − (L− 1) +

∣∣∣T∣∣∣)rL−1

7. La cantidad aproximada de árboles puede estimarse como 2L! · 3rL−1 ·|A|+

∣∣∣T∣∣∣ . Esto no indica que sean árboles diferentes, ya que muchos de

dichos árboles serán equivalentes entre sí, disminuyendo la cantidad deárboles diferentes. Sin embargo, esta expresión da una idea aproximadade la magnitud del espacio de búsqueda.

Ejemplo 2.1 Se dispone de 2 atributos binarios y 2 clasificaciones posibles. Sedesea calcular cuantos árboles distintos se pueden generar.

Se tiene |A| = 2, el nivel máximo P = 2,∣∣∣T∣∣∣ = 2.

Para llenar el nodo raíz L = 0 se dispone de |A|+∣∣∣T∣∣∣ = 4 opciones. Además

r0 = 122! ∗ 32 ∗ 2 + 2 = 74

Ejemplo 2.2 Se dispone de 3 atributos binarios y 2 clasificaciones posibles. Sedesea estimar cuantos árboles distintos se pueden generar.

Se tiene |A| = 3, el nivel máximo P = 3,∣∣∣T∣∣∣ = 2.

Para llenar el nodo raíz L = 0 se dispone de |A|+∣∣∣T∣∣∣ = 5 opciones. Además

r0 = 123! ∗ 34 ∗ 3 + 2 = 15554

Estos ejemplos muestran como el espacio de búsqueda crece enormementecon pequeños cambios en la cantidad de atributos o de clases. En los ejemplosde esta sección se han considerado además que todos los atributos tienen valoresbinarios, lo que reduce además el espacio de búsqueda, si bien en los problemasreales es común que se encuentren atributos que pueden tomar 3 o más valores.La aridad de las funciones, en la expresión que se ha utilizado para la estimación,afecta los exponentes y por tanto tiene un impacto alto en la cantidad de árbolesque se pueden encontrar. Es por ello que la búsqueda o verificación del mejorárbol no puede hacerse de manera exhaustiva en casos reales, por el alto costocomputacional que ello implica.

26

2.2. Aplicación de la PG a los Árboles de Decisión.

Como todo problema abordado mediante la técnica de la PG, la generaciónde árboles de decisión mediante requiere definir lo siguiente:

1. Seleccionar el mecanismo de representación de los árboles de decisión enPG..

2. Conjunto de nodos terminales. Estos corresponden a las diferentes clasesque se pueden extraer de la tabla de patrones de entrada.

3. Conjunto de Nodos no terminales. Estos corresponden a los diferentesatributos, que se extraen habitualmente de los encabezados de las colum-nas de la base de datos o tabla de patrones.

La solución del problema se aborda desde el paradigma de la programaciónorientada a objetos y metodologías y herramientas relacionadas, tal como lo esUML, ya que esta última permite un modelamiento conceptual tanto del prob-lema como de la solución. Se presentará en esta sección algunas generalidadesque permitan interpretar mejor algunos segmentos de código que se presentan.

En primera instancia, se requiere modelar como va a interactuar un usuariocon el sistema final. Al examinar esta interacción, lo que se conoce como casode uso general, y se observa en la figura 8.

Cada uno de los óvalos muestra una función u operación principal, que re-quiere una descripción más detallada. Dentro de los productos finales que seobtienen a partir de los diagramas de casos de uso se encuentran los principalesalgoritmos y por tanto las diferentes funciones que se incluirán en el programa.Además, el diagrama general de casos de uso sirve de ayuda al momento dedefinir la estructura del programa principal.

Es así como a partir del diagrama de la figura 8, se puede expandir la infor-mación de cada uno de ellos. El desarrollo de las técnicas de modelamiento conUML por una parte sugieren algunas clases, y la traducción algorítmica den-tro del lenguaje final seleccionado y la estructura de clases decidida finalmenteorigina un código.

Es neceario definir como se va a representar el árbol de decisión a evolu-cionar dentro de la PG. En la figura 9, los recuadros son nodos y las flechasson apuntadores; al observar la estructura del nodo padre, se ve que solo tiene3 apuntadores: al propio padre, al primer hijo y al hermano.

Luego al observar cómo se relaciona un nodo con los demás nodos que con-forman un árbol se tiene la mecánica de ciertas funciones que requieren recorrerlos nodos de un árbol.: Las funciones que ubican nodos Por ejemplo, el nodopadre solo puede conocer al nodo hijo 2 a través del nodo hijo 1.

La solución se puede ver en la figura 10. No es un gráfico UML, pretendemostrar no solo los objetos y sus relaciones entre sí, sino algunas de las funcionesque se requieren para el correcto funcionamiento del programa final.

Por una parte, el entorno evalúa a cada árbol de decisión. Para ello, elprograma debe leer la base de datos original para luego construir las tablas de

27

Usuario

Cargar Datos

Cargar Parametros

evolucionar

Modificar Parametros

Generar Poblacion

Aplicar Operador Evolutivo

Evaluar Poblacion

Aplicar Torneo

Aplicar Elitismo

Mutar

Clonar

Cruzar

<<include>>

Terminar Evolucion

<<extend>>

Figura 8: Diagrama general de casos de uso.

datos de entrenamiento o validación. El programa debe examinar la base dedatos original para extraer de allí los diferentes atributos, y para cada atributodebe identificar y extraer cada uno de los valores posibles. Con esta informaciónse llena un objeto de tipo DT (Figura 10)

La tabla DT es examinada cada vez que se desea construir un árbol dedecisión, con el fin de determinar el número máximo de nodos que puede cor-responder a cada atributo. Por ejemplo, para un atributo A, se tienen i valoresposibles. La última columna Y corresponde a la clase que se debe asignar acada patrón de entrada para los datos de entrenamiento y validación. En esteejemplo, se tienen k clases diferentes para ser asignadas a cada patrón. Bajoesta perspectiva, evaluar un árbol es en gran manera equivalente a realizar cadauno de los recorridos que indica el patrón de datos, del árbol partiendo del nodoraiz. Cuando se encuentra una clasificación (nodo terminal), se contrasta con laclase presente en el patrón de entrenamiento. Si coinciden, se anota un acierto

28

NodoPadre

Nod

o H

ijo

Nodo Hermano

Nod

o P

adre

NodoHijo 1

NodoHijo 2

Nulo

NuloNodo Raiz

NuloNulo

Figura 9: Estructura computacional de un nodo raiz con dos hijos.

(hit [Koz92]). Una posible medida final de la aptitud es la propuesta en 1.4.

2.2.1. Ciclo Evolutivo General

El caso de uso evolucionar representa el ciclo principal del programa en elcual se tiene una población de árboles de decisión en evolución. Se ha definido deforma bastante abstracta en primera instancia, aunque iteraciones posterioreslo deben detallar y mejorar. El flujo de eventos de este caso de uso se expresaen los algoritmos 2.1 y 2.2. El primero es una versión general de los algoritmosevolutivos que se aplicar muy bien al caso de la PG, mientras que el segundocorresponde de manera general a la propuesta de Koza [Koz92] con algunasmodificaciones y simplificaciones.

Algoritmo 2.1 (Algoritmo Evolucionario Básico)Describe el ciclo principal de la PG, según modelo propuesto en [Bac00].

Input: µ, λ, θι, θr, θm, θ, F (t)θι: parámetros de configuración de condiciones de terminación.ι(P (t), θι) condición de terminación ι que dependen de P (t) y θι

Output: a∗, el mejor individuo encontrado durante la ejecución.P ∗, la mejor población encontrada.

29

Objeto de Clase Entorno(CDTEnv)

Prueba o Atributo (nodo)Resultado de prueba (ramas)...

a1

a2

a3

…ai

b1

b2

b3

…bi

Y1

Y2

Y3

…Y i

A B Y Atributos Extraidos

Valores Posibles Extraidos

Tamaño de PoblacionProbabilidad OperadoresProbabilidad Nodos

…

Objetos de Clase CParam

Estructura DT

Tabla de Datos para Entrenamiento (S)

Tabla de Datos para Validación (V)

Base de Datos Original

Patrones para:Entrenamiento (S) Validación (V)

Archivo de Parámetros

Objetos de Clase Arbol(CDTree)

Datos del mejorParámetros Evolución...

evaluaSelecciona

Y aplicaOperador Evolutivo

carga

consulta

consulta

alimenta

Resultadosevaluación

Figura 10: Estructura inicial propuesta de la solución.

1. t←− 0/* genera población inicial e inicializa */2. P (t)←− inicialice(µ)3. F (t)←− inicialice(P (t), µ)4. Mientras Que (ι(P (t), θι) �= true) haga5. P ′(t) ←− cruzar(P (t), θr)6. P ′′(t)←−mutar(P ′(t), θm)7. F (t)←− evaluar(P ′′(t), λ)8. P (t+ 1)←− seleccionar(P ′′(t), F (t), µ, θ)9. t←− t+ 110. Fin Mientras

11. devuelve a∗, P ∗

En este algoritmo [Bac00] la población P (t) está conformada por µ individu-os, P ′(t) por κ individuos y P ′′(t) por λ individuos. Al observar el pseudocódigo,se puede observar que P (t) es la población en la generación actual, mientras queP (t+ 1) indica una nueva generación en formación (offspring). P ′(t) es la sub-población obtenida por cruce, mientras que P ′′(t) es la población obtenida pormutación de individuos cruzados. Una diferencia clara respecto del diagrama deflujo de la figura 4 consiste en que en este último P ′′(t) ←− mutar(P ′(t), θm)se aplica a los individuos resultantes del cruce, pero se encuentran esquemas en

30

los cuales P ′′(t)←−mutar(P (t), θm) teniendo en cuenta que se debe controlarla relación entre los tamaños de las poblaciones µ y λ.

El algoritmo 2.1 muestra la inicialización de t, de P (t) con tamaño µ y dela función de evaluación. El criterio de teminación t depende de gran cantidadde parámetros, que son representados por θt. Luego entra en el ciclo principal,donde el sistema puede operar con la selección, el cruce o la mutación, quedepende de otra cantidad de parámetros.

En el algoritmo se tiene que si λ = κ = µ. Si κ = µ.indica que no hay cruce,y si κ = λ no hay mutación. El operador de selección selecciona µ individuos deP ′′(t) de acuerdo con los valores de aptitud F (t).

Se considerará ahora la generación de la población inicial con el métodogrow [Koz92]. Sin embargo, mediante nuevas instricciones si-entonces o case,se pueden incorporara nuevos algoritmos de generación de la población inicial(full, ramped half-half [Koz92]). Básicamente, el algoritmo de generación de lapoblación inicial consiste en un ciclo for con µ iteraciones, para cada uno delos individuos de la población.

En este escrito se trabaja una versión modificada, equivalente a la versiónpropuesta por Koza, de acuerdo con la figura 3. En este algoritmo, la poblacióninicial se evalúa con el fin de verificar si efectivamente uno de los individuosgenerados hace cumplir con la condición de terminación ι(P (t), θι) y por lo tantono se continúa con el proceso evolutivo. Si se continúa la evolución, se realizaun proceso de selección que da como resultado un conjunto de individuos a loscuales se les debe aplicar el operador evolutivo, uno a la vez, hasta completaruna nueva generación.

Algoritmo 2.2 (Algoritmo Evolucionario Básico)Describe el ciclo principal de la PG.

Input: µ, λ, θι, θr, θm, θ, F (t)θι: parámetros de configuración de condiciones de terminación.ι(P (t), θι) : condición de terminación ι que depende de P (t) y de θι.Φ = {φc, φm, φr...} : conjunto de operadores evolutivos

Output: a∗, el mejor individuo encontrado durante la ejecución.P ∗, la mejor población encontrada.

1. t←− 0/* genera población inicial y la inicializa */2. P (t)←− inicialice(µ)3. F (t)←− inicialice(P (t), µ)4. F (t), a∗ ←− evaluar(P (t), µ)5. Mientras_Que (ι(P (t), θι) �= true) haga6. a′1 ←− clonar(a

∗) /*elitismo*/7. Para cada a′i con i = 2 hasta µ8. operador = ruleta(Φ)9. {a1, ...} ←− seleccionar(P (t), F (t), µ, θ)10. si operador = cruzar entonces

11. (a′i, a′j)←− cruzar({a1, ..., aφ}, θr)

31

12. si operador = mutar entonces

13. a′k ←− mutar(ak, θm)14. Fin_para15. F (t)←− evaluar(P (t))16. t←− t+ 117. Fin_Mientras18. devuelve a∗, P ∗

Para codificar finalmente este algoritmo, se debe tener en cuenta la repre-sentación del árbol de decisión dentro de la PG. La estructrua de árbol de losindividuos en PG facilita de manera inherente el diseño de funciones recursivasde creación, eliminación y en general, manipulación. Aún cuando computacional-mente las funciones recursivas tienen más exigencia de recursos computacionales(stack por ejemplo), son funciones más compactas en su diseño.

Listado 2.1 (Programa Principal) Ciclo principal/*pPop, pNewPopulation son apuntadores a la población actual y nueva*//*pEnv es un apuntador a un objeto de tipo entorno*/1. int main(int argc, char ∗ argv[])2. g.generation = INITIAL;3. pPop = new CDTree[g.population];4. pNewPopulation = new CDTree[g.population];5. for (ind = 0; ind < g.population; ind++)6. (pPop)− > fillTree(pPop+ ind, ...); /*completa recursivamente*/7. ...8. while (g.generation < pEnv− > getMaxGeneration())9. pEnv− > setNumBestTree(pEnv− > evalPopulation()); /*evalua*/10. if (pEnv− > getStopCriteria() == true)11. ... /*termina evolución*/12. newInd = 0;13. pEnv− > clone(pEnv− > getNumBestTree(), newInd);14. newInd++;15. while (newInd < pEnv− > getPopulation())16. geneticOperator = pEnv− > operatorSel();17. if (geneticOperator == CROSS)18. /*...cruzar individuos19. else if (geneticOperator == REPRODUCTION)20. /*...clonar individuo*/21. else if (geneticOperator ==MUTATION)22. /*... mutar individuo*/23. g.generation++;24. delPopulation();25. pEnv− > setNumBestTree(pEnv− > evalPopulation());26. return pEnv− > getNumBestTree();

32

En el listado 2.1, la función fillTree() es una función recursiva que vagenerando de una manera aleatoria o probabilística (según los parámetros) cadauno de los µ individuos que conforman la población. La función evalPopulation()igualmente evalúa cada uno de los árboles de decisión de manera recursiva.

2.2.2. Generación de la Población Inicial.

Se disponen de diferentes maneras de generar la población inicial, se describeel algoritmo y su expresión en C++ para una función que genera la poblacióninicial utilizando el método grow.

Algoritmo 2.3 (Grow)Algoritmo recursivo GROW para generar población inicial.

Input: θp : profundidad máxima inicial,F = {f1, ..., fm} : funciones primitivasT = {t1, ..., tm} : nodos terminalesa′ ←− seleccionar probabilisticamente una raiz fi ∈ F

Output: a : individuo de P

/* ciclo principal de generación de la población inicial:/* para individuo = 1 hasta µ/* a′ ←− seleccionar probabilisticamente raiz fi ∈ F/* a ←− grow(a′, altura );/* fin_para1. grow(a, altura)2. Si altura = θp entonces3. devuelve a′′ ←− seleccionar probabilisticamente nodo ti ∈ T4. Si no entonces

5. n←− seleccionar probabilisticamente tipo de nodo F o T6. si n ∈ F7. a′ ←− seleccionar probabilisticamente fi ∈ F8. nueva_altura = altura+ 19. repetir según aridad de fi10. grow(a′, nueva_altura)11. fin repetir

12. si n ∈ T13. devuelve a′ ←− seleccionar probabilisticamente ti ∈ T

Al examinar este pseudocódigo, se observa que el método grow genera losindividuos de la población inicial de manera libre, y podrían crecer bastante enprofundidad de no ser por uno de los parámetros iniciales, que limita la pro-fundidad máxima para cada árbol generado inicialmente. La presión evolutivaposterior es la que tiende a controlar que los árboles no sean demasiado grandes,aunque no se excluye la posibilidad de que dicho límite se imponga a la fuerzamediante codificación.

La codificación en C++ se puede realizar como se observa en el listado 2.2,donde idx es el índice que corresponde a una determinada función o terminal

33

según una tabla de funciones y terminales; la variable level indica el nivel a quese encuentran los nodos que se están completando en ese momento, y pN y pTson apuntadores a la estructura árbol y la estructura DT respectivamente.

Listado 2.2 (Generación de Población Inicial)1. createDTree(CDTree ∗ pN,DT ∗ pT, int idx, int level) {2. if (pN ! = NUL_)3. { switch(idx) {4. case TERMINAL:5. pN->setNDT(0);6. pN->setLblValueIdx(randGenerator(0, (pT->arity)-1));

...}7. if (idx > TERMINAL){8. level++;9. pN− > insChild(newCDTree); //inserta hijo10. if (level >= g.maxLevel) {TypeN = TERMINAL;}11. else {TypeN = (randGenerator(TY PE_1, LAST ));}12. pN->createDTree(pN->getChild(), pT, TypeN, level);}13. if (idx > UNARY ){14. pN = pN− > getChild(); //se desplaza15. for (n = 2;n <= idx;n++) {16. pN− > insBrother(newCDTree);17. if (level >= g.maxLevel) {TypeN = TERMINAL; }18. else {TypeN = randGenerator(TERMINAL, g.maxLevel); } }19. pN=pN->getBrother();20. /*llamada recursiva:*/21 pN->createDTree(pN->getChild(), pT, TypeN, level); } }22. else { /*ERROR*/ } }

2.2.3. Operadores Evolutivos y Mecanismos de Selección

El primer operador evolutivo al que se hace referencia es al operador de se-lección, que se presentó previamente en la sección 1.6.1. La implementación quese expone en el algoritmo 2.4 corresponde a la implementación del método deltorneo con ruleta. El algoritmo 2.4 es una implementación abstracta del mecan-ismo de selección generl para individuos, correspondiente al esquema propuestopor [Bac00].

Algoritmo 2.4 (Selección [Bac00])Describe un mecanismo de seleccion para PG.

Input: µ, λ, q, P (t) ∈ Iµ, P ′(t) ∈ Iλι , F (t)s : Iλ → Iµ,m : Iκ → Iλ, r : Iµ → Iκ

Output: P ′′(t) = {a′′1 , a′′2 , ..., a

′′µ} ∈ I

µ

1. para i←− 1 hasta µ2. a′′i (t)←− ssel(P (t), P

′(t), F (t), q)3. devolver {a′′1(t), ..., a

′′µ(t)}

34

La implementación del mecanismo general de selección se basa en un pro-cedimiento aleatorio o probabilístico, o una combinación de ambos.

Algoritmo 2.5 (Seleccionar)Describe el procedimiento general de selección de individuos.

Input: P (t) = {a1, ...aµ}

Output: a′′ ∈ P ′′(t)

/* La función torneo(s, a1, ..., ai) se explica en los algoritmos 2.7 y 2.8*/1. a1, ...ai ∈ I

µ ←− aleatorio(1, µ)2. a′ ←− torneo(s, a1, ..., ai)3. devuelve a′

Para determinar cual operador evolutivo se va a aplicar a la población depadres en un momento determinado, también se puede utilizar un método similara la ruleta. Esto implica que cada operador evolutivo tiene un porcentaje deprobabilidad de ocurrir, y mediante la ruleta se determina cual operador será elque se aplique en última instancia.

Algoritmo 2.6 (Ruleta)Describe el procedimiento de la ruleta PG.

Input: Pr = Distribución de probabilidad de individuosOutput: a′′ = P ′′(t)

1. ruleta(Pr)2. n←− 13. suma←− Pr(n)4. azar(0, 1)5. Mientras Que suma < azar6. n←− (n+ 1)7. suma←− suma+ Pr(n)8. Fin Mientras

9. devuelve(n)

Algoritmo 2.7 (Torneo Determinístico)Describe el mecanismo de torneo determinístico para PG.s = tamaño del torneo.Input: P (t) ∈ Iλ, s ∈ {1, 2, ..., λ}Output: P ′(t)

1. torneo(s, a1, ..., aλ)2. para i←− 1 hasta λ3. a′i(t)←−mejor de s individuos de P (t)4. devolver {a′1(t), ..., a

′λ(t)}

35

Algoritmo 2.8 (Torneo Probabilístico)Describe el mecanismo de torneo probabilístico para PG.s = tamaño del torneoInput: P (t) ∈ Iλ, s ∈ {1, 2, ..., λ}Output: P ′(t)

1. torneo(s, a1, ..., aλ)2. para i←− 1 hasta λ3. a′i(t)←− ruleta(P (r))4. devolver a′1(t), ..., a

′λ(t)

La implementación del torneo determinístico se encuentra en el listado 2.3.

Listado 2.3 (Selección de Individuos)1. tournament() {/*selección aleatoria de individuos para torneo*//*int indA, indB: número de individuo dentro de población*/2. int indA = randGenerator(0, p.populationSize− 1);3. int indB = randGenerator(0, p.populationSize− 1);/*si es torneo determinístico*/4. if (getEval(indA) > getEval(indB))5. { return indA; }6. else return indB; }

Algoritmo 2.9 (Cruce)Describe el mecanismo de cruce para PG.

Input: a, b ∈ P (t) ∈ Iλ

Output: a′, b′ ∈ P ′(t)

(a′, b′)←− cruce(a, b)/* Las funciones subarbol(arbol, posicion), y la función *//* insertar(arbos, subarbol, posicion) devuelven árboles completo *//* La función eliminar(arbos, posicion) devuelve un árbol incompleto *//* La funcion aleatorio(min,max) devuelve valor aleatorio con*//* distribución uniforme dentro del rango (min,max).*/1. ςa ←− aleatorio(1, longitud(a))2. ςb ←− aleatorio(1, longitud(b))3. a′′ ←− subarbol(a, ςa)4. b′′ ←− subarbol(b, ςb)5. a′ ←− eliminar(a, ςa)6. b′ ←− eliminar(b, ςb)7. a′ ←− insertar(a, b′′, ςa)8. b′ ←− insertar(b, a′′, ςb)

En el algoritmo 2.9, para las funciones subarbol, eliminar e insertar, la es-tructura de detallada de los algoritmos depende entre otros factores del lenguajede programación y la metodología que se empleo dentro del lenguaje selecciona-do. La función subarbol() extrae un subárbol válido de una posición válida de

36

un árbol dado. la función eliminar() devuelve el árbol de entrada tras eliminarun subárbol completo de una posición válida dentro del mismo. Por lo tanto,eliminar() devuelve un árbol incompleto y que debe ser llenado en el puntode eliminación para que sea válido. La función insertar() copia un subárbolválido en una posición válida de un árbol. Por lo tanto, el algoritmo debe com-binar eliminar() con insertar() para que no se pierda la validez sintáctica oestructural de los árboles. El código en C++ se encuentra en el listado 2.4.

Listado 2.4 (Cruce) ...1. cross(CDTree ∗pA,CDTree ∗pB, int hA, int hB){2. CDTree * pSPrA, * pSPrB, * pSHA,* pSHB;/*selecciona aleatoriamente puntos de cruce*/3. crossPointA = randGenerator(2, getPopSizes(prA)− 1);4. crossPointB = randGenerator(2, getPopSizes(prB)− 1);/*ubica apuntadores a nodos en puntos de cruce*/5. pSPrA = pPop− > findNode(pPop+ prA, crossPointA, 0);6. pSPrB = pPop− > findNode(pPop+ prB, crossPointB, 0);7. pSHA = pNewPop− > findNode(pNewPop+ hA, crossPointA, 0);8. pSHB = pNewPop− > findNode(pNewPop+ hB, crossPointB, 0);/*funcion que intercambia apuntadores a subarboles:*//*(lineas 5,6,7,8 algoritmo 2.9)*/9. interxSubTree(pNewPop+ hA, pSHA, pPop+ prB, pSPrB);

Algoritmo 2.10 (Mutación)Describe el mecanismo de mutación para PG.

Input: a, b ∈ P (t) ∈ Iλ

Output: a′, b′ ∈ P ′(t)

(a′)←− mutacion(a)/* insertar(arbos, subarbol, posicion) devuelven árboles completo *//* La función eliminar(arbos, posicion) devuelve un árbol incompleto *//* La funcion aleatorio(min,max) devuelve valor aleatorio con*//* distribución uniforme dentro del rango (min,max).*/1. ςa ←− aleatorio(1, longitud(a))2. a′ ←− eliminar(a, ςa)3. a′ ←− insertar(a, b′′, ςa)

La traducción a código en C++ da como resultado el listado 2.5.

Listado 2.5 (Mutacion)mutate(intm){1. CDTree* pMutant, * pNode, * pNodePM, * pCh, * pTem;2. mutNode = randGenerator(2,mutantSize));3. pNode = (pMutant)− > findNode(pMutant,mutNode, 0);/*ubica no-

do*/4. level = pNode− > getLevel();/*nivel del nodo a mutar*/5. numCh = pNode− > getNumChild();

37

6. pNodePM = pNode− > getParent();7. idx = randGenerator(0, g.numLabels);/*asigna atributo a nodo*/8. pTem = newCDTree;9. pTem− > createDTree(pTem, pDTable, idx, level);10. if (numCh == 1){11. pNodePM− > insChild(pTem);12. pTem− > setBrother(pNode− > getBrother()); }13. else if (numCh > 1){14. pCh = pNodePM− > getChild();15. while(pCh− > getNumChild() < numCh− 1){16. pCh = pCh− > getBrother(); }17. pCh− > insBrother(pTem);18. pTem− > setBrother(pNode− > getBrother()); }19. else{/ ∗ERROR ∗ /};

Dentro de los algoritmos más importantes para la evolución se encuentra elque determina la función de aptitud F (t). En PG la representación de un indi-viduo es usualmente una función, un programa o en el presente caso de interés,un árbol de decisión que se puede transformar en una disyunción de conjun-ciones de expresiones si-entonces. Los resultados de la evaluación del árbol soncomparados mediante alguna función de error con los resultados esperados paracada patrón de datos de entrenamiento y validación. La función de evaluaciónpuede retornar un valor que indica que tanto cumple el árbol con la clasificaciónesperada. Dicho valor es utilizado para guiar el proceso de selección, principal-mente en la escogencia de los padres a los cuales se les podrá aplicar cualquierade los operadores evolutivos.

2.2.4. Evaluación de los Árboles de Decisión

La evaluación del árbol es un aspecto decisivo en el proceso evolutivo, yaque es la que le da la dirección adecuada en busca de los individuos más aptos,de la manera más rápida y menos parsimoniosa posible.

Algoritmo 2.11 (Evaluar)1. leer patrón2. realizar el recorrido según el patrón3. mientras que (recorrido existe)4. si (nodo = terminal)5. si (clasificacion arbol = clasificacion patrón)6. aciertos = aciertos+ 17. retorna aciertos

2.2.5. Diseño General de la Solución

De acuerdo con esto, el exámen del problema ha sugerido una estructura declases que se ha simplificado para el presente ejercicio de la siguiente manera:

38

1. Clase CDTree: clase que define la estructura y operaciones de los árbolesde decición, que son los individuos a evolucionar.

2. Clase CDTEnv: clase que define la estructura y operaciones del entorno,que ejerce influencia sobre los individuos de la clase CDTree seleccionandoalgunos de ellos y permitiendo su influencia en la nueva generación.

3. Clase CParam: clase auxiliar que define el objeto encargado de almace-nar y verificar la consistencia de los parámetros que guían la generaciónde la población inicial y de la evolución en general.

4. Estructura DT: estructura auxiliar que permite el almacenamiento deinformación relativa a cada uno de los nodo.

La clase CDTree representa los objetos a evolucionar, los árboles de decisión.La clase CDTree intenta definirlos de manera adecuada para que su manipu-lación sea sencilla y clara. El concepto se basa en la idea de árboles n-arios.La aridad de cada nodo del árbol tiene que ver con la cantidad de valores quepuede tomar un atributo determinado. Este diseño tiene algunas implicacionesa la hora de diseñar los algoritmos: por una parte, cada nodo conoce de maneradirecta a su primer nodo hijo, a su hermano inmediatamente siguiente, y a supadre. Esto implica que por ejemplo, si un nodo tiene al menos tres hijos, paraacceder al hijo 3 debe acceder primero al nodo hijo, y desplazarse a través de éstevisitando al hermano siguiente y luego al siguiente. Los principales atributos yfunciones de la clase CDTree se observan en la figura 11.

La clase CDTree contiene principalmente:

Un apuntador a un objeto tipoDT , que es la tabla que contiene el resumende caractarísticas de la tabla de decisión,

Un valor nDT que informa cual entrada de la tabla de atributos es la queutiliza el nodo considerado. Al aplicar este valor al apuntador pDTable,le da la posibilidad de acceder a toda la información relacionada con elatributo propio del nodo: el nombre del atributo, la aridad, los posiblesvalores, etc.

La clase CDTEnv representa al entorno evolutivo, donde se observan susatributos y funciones principales. Se le puede considerar como un objeto decategoría más alta que el propio árbol o individuo; tiene a su cargo dirigir laevolución de acuerdo con un conjunto de parámetros elegidos. Se encarga porlo tanto de:

Cargar los archivos de parámetros y de datos. Debe verificar si los parámet-ros están dentro de rango.

Generar la población inicial de acuerdo con los parámetros que la con-trolan.

Evaluar cada individuo de la población,

39

CDTree

-pDTable: DT-nDT: int-lblValueIdx: int-pChild: CDTree-pParent: CDTree-pBrother: CDTree-numChild: int

+setPDTable(: DT): void+getPDTable(): DT+setNDT(: int): void+getNDT(): int+setLblValueIdx(: int): void+getLblValueIdx(): int+getChild(): CDTree+insChild(: CDTree): void+getParent(): CDTree+setParent(: CDTree): void+getBrother(): CDTree+insBrother(: CDTree): void+setBrother(: CDTree): void+setNumChild(: int): void+getNumChild(): int+createDTree(: CDTree, : DT, : int, : int): void+findNode(: CDTree, : int, : int): CDTree

Figura 11: Clase CDTree (árbol n-ario)

Aplicar torneo para decidir cuales individuos participaran en la formaciónde una nueva generación,

Aplicar operadores evolutivos y

Decidir cuando terminar el proceso evolutivo.

Un objeto de la clase CDTEnv contendrá principalmente:

Un apuntador a un objeto tipoDT , que es la tabla que contiene el resumende caractarísticas de la tabla de decisión,

Un apuntador a la población actual pPop,

Un apuntador a la población de la generación siguiente,

Valores generales recolectados durante el proceso de evaluación de la población:longitud de cada individuo (árbol), nivel máximo, cual individuo es elmejor y el resultado de la evaluación del mejor, entre otros.

Se disponen de algunas clases y estructuras auxiliares, cuya función es apuyara las dos clases principales en algunas tareas. Por una parte, estas clases le dan

40

CDTEnv

-pDTable: DT-pPop: CDTree-pNewPop: CDTree-popSizes: int-popLevels: int-popEvals: double-numBest: int-evalBest: double-levelBest: int

+setPDTable(: DT): void+getPDTable(): DT+setPop(): void+getPop(): CDTree+setPopSizes(: int, : int): void+getPopSizes(: int): int+setPopLevels(: int, : int): void+getPopLevels(: int): int+setPopEvals(: int, : double): void+getPopEvals(: int): double+evalPopulation(): int+setEval(: int): void

+getEval(: int): double+setNumBest(: int): void+getNumBest(): int+setEvalBest(: double): void

+getEvalBest(): double+setLevelBest(: int): void+getLevelBest(): int+operatorSel(): int+tournament(): int+delDSubTree(: CDTree): void+mutate(: int): void+clone(: CDTree, : CDTree): void+cross(: int, : int, : int, : int): void+interxSubTree(: CDTree, : CDTree, : CDTree, : CDTree): void+dataLoad(): void+setStopCriteria(: int): int+getStopCriteria(): int

Figura 12: Clase CDTEnv (entorno evolutivo).

al sistema la capacidad de almacenar y modificar datos y parámetros de manerasegura.

La clase CParam, cuyos valores y funciones principales se observan en lafigura 13, está encargada de almacenar y verificar la consistencia de los parámet-ros que guían la generación de la población inicial y guiar la evolución. Le dacapacidad al sistema de modificar estos datos de manera segura. Sus principalesvalores son:

populationSize: Tamaño de la población. Almacena la cantidad de indi-viduos que debe tener la población. La versión final del programa verificaque sea un valor consistente.

terminalProb: Durante los procesos de generación de la población inicial ymutación, se generan nuevos individuos. Para cada nodo del árbol, se debedecidir si este será un nodo terminal o no-terminal. El valor terminalProb

41

CParam

-populationSize: int-terminalProb: double-crossProb: double-mutationProb: double-cloneProb: double

Figura 13: Clase Parametros

indica la probabilidad de que el nuevo nodo sea de tipo terminal. El nodono-terminal tendrá una probabilidad 1-terminalProb.

crossProb, mutationProb, cloneProb: indican la probabilidad de que eloperador evolutivo cruce, mutación y clonación respectivamente, sean se-leccionados. Cuando la clase CDTEnv (el entorno) lanza los dados bus-cando un valor aleatorio entre 0 y 1 para decidir cual operador evolutivoaplica, el valor que obtiene al lanzar los dados se verifica contra los rangosde valores de estas probabilidades, en el proceso llamado ruleta. Se debecumplir la condición crossProb+mutationProb+ cloneProb = 1

En cuanto a la estructura DT , se tiene que una copia de esta candidata aclase, es referenciada y sus valores actualizados dentro de cada uno de los nodosdel árbol. El objetivo es que cada nodo lea estos valores de la tabla que contieneel resumen de caractarísticas de la tabla de decisión, y los actualice internamente(para evitar llamar permanentemente al apuntador a la tabla DT ). Esta clasecontendrá los valores: tipo de nodo, el nombre del atributo, la aridad, y losvalores posibles del atributo. El tipo de nodo es un valor de T o F , según elnodo sea terminal o no terminal.

42

3. Conclusiones

Este es un trabajo de tipo exploratorio, y es necesario implementar final-mente el modelo conceptual para verificar su utilidad. Sin embargo, dada larelativamente larga trayectoria de aplicación de la PG en diversas áreas, se es-pera que se tenga un resultado aceptable.

Se debe considerar que el sistema propuesto intenta ser lo más simple posi-ble, incorporando la menor cantidad de heurísticas de búsqueda, limitación debúsqueda o cualquier restricción posible para examinar los resultados obtenidostras una exploración libre del espacio de búsqueda compuesto por árboles dedecisión que solucionan un problema.

Aún cuando el sistema no incorpore heurísticas de uso actual en PG, su es-tructura permite adaptarse a nuevos requerimientos y condiciones. Por ejemplo,se puede imponer la restricción de que ningún árbol duplique atributos en unnuevo nodo, al momento de la generación inicial. Sin embargo, puede ser compli-cado e improductivo verificar que al aplicar un operador evolutivo, ningún nododel subárbol sea repetido al insertar o cruzar un nodo. Es más, esto podría en unmomento dado hacer imposible que continúe la evolución o hacerla extremada-mente lenta. Por supuesto que finalmente será necesario imponer restriccionescon alguna heurística, pero la exploración libre permitirá observar cómo son losárboles de decisión generados siguiendo estos lineamientos.

Por estos dos motivos, libertad de exploración y facilidad de evolución, elsistema no ha incorporado inicialmente ningún control sobre la evolución.

Por otra parte, los individuos que forman parte de la población en los prob-lemas de programación genética, representan de una manera muy natural losárboles de decisión, lo cual facilitará y simplificará la implementación final.

Pueder ser interesante además, considerar hacia un futuro la implementaciónde estrategias para permitir que el sistema de PG genere árboles de decisiónoblicuos o multivariados [Llo07].

Un esquema similar de clases y funciones aquí presentado ha sido utiliza-do por el autor del presente trabajo para implementar un sistema de regresiónsimbólica funcional, así que se espera que con la implementación de algunosmódulos generales, el programa quede totalmente operativo. El sistema final-mente debe entregar como resultado el conjunto de reglas, como programa, quepermitan la aplicación sencilla del modelo resultante a un nuevo conjunto dedatos para clasificación.

43

Referencias

[Llo07] X. Llorá, J. Garrel, Evolution of Decision Trees. Universidad RamonLlull, {xevil,josepmg}@salleURL.edu

[Mar87] Autores Varios, Inteligencia Artificial. Boixareu Editores, Madrid.(1987).

[Kec01] V. Keckman. Learning and Soft Computing. MIT Press, USA (2001).

[Roa06] C. Roach, Building Decision Trees in Python.http://www.onlamp.com/pub/a/python/2006/02/09/ai_decision_trees.html.(2006).

[Rus96] S. Russell, P. Norvig, Inteligencia Artificial. Prentice-Hall, México.(1996).

[Joa07] T. Joachims. Notas de Clase. Cornell University. (2007).

[Gue04] A. Guerra, Aprendizaje Automático: Árboles de Decisión.www.uv.mx/aguerra. (2004).

[Koz92] J. Koza, Genetic Programming. (1992).

[Dim06] D. Dimitrescu, A. Joó, Generalized Decision Trees Built with Evolu-tionary Techniques. Universidad Babes-Bolyai, Universidad Sapientia,Rumania.

[Mit97] T. Mitchell, Machine Learning. McGraw-Hill, New York (1997).

[May88] E. Mayr, Toward a New Philosophy of Biology: Observations of anEvolutionist. Belknap, Cambridge-MA (1988).

[Bac00] T. Bäck, Evolutionary Algorithms in Theory and Practice..Oxford, NewYork (2000).

[Gol89] D. Goldberg, Genetic Algorithms in Search, Optimization and MachineLearning. Addisson-Wesley, Reading-MD (1989).

[Luk01] S. Luke, L. Panait, A Survey and Comparison of Tree Generation Al-gorithms. Internet (2001)

44