Download Algoritmo h brido de extracci on de reglas usando algoritmos gen

Algoritmo hbrido de extraccion de reglas usando algoritmos
geneticos y arboles de clasicacion
Marcelo Mendoza
Mayo del 2000
Resumen
Este reporte presenta un algoritmo hbrido de extraccion de reglas para la clasicacion de
patrones sonoros. Se considera como herramienta de clasicacion a los arboles binarios de clasicacion. Se usa a los algoritmos geneticos como una estrategia de busqueda de manera tal que
el arbol binario discrimine acertadamente los patrones sonoros. El integrar ambas herramientas
permite encontrar un desempe~no de clasicacion satisfactorio. Los resultados experimentales que
se muestran son fruto de la aplicacion de esta metodologa a un problema de clasicacion de
patrones de sonido en ambiente industrial del cual se desconocen modelos fsicos que permitan
implementar un metodo alternativo.
1 Introduccion
Un problema clasico de clasicacion de patrones radica en la busqueda de una tecnica eciente y
robusta que permita discriminar entre los patrones objetivos y otros elementos, satisfaciendo algunos
criterios de desempe~no. Este problema puede enfrentarse con distintas tecnicas, entre ellas los arboles
de clasicacion [ver Breinman y Friedman, 1984]. El problema no es como clasicar en s, sino el
como extraer reglas de clasicacion que son desconocidas. Existen una innidad de problemas de
clasicacion de patrones en los cuales es muy difcil establecer reglas, debido a la carencia de una
base de conocimiento acerca del comportamiento de los patrones ante cambios en las variables de
operacion del sistema. Estos problemas de alta complejidad han sido tratados desde el interes
existente para encontrar mejores tecnicas de clasicacion de textura de imagenes mediante el uso de
algoritmos hbridos basados en estrategias de busqueda como Algoritmos Geneticos [ver Michalewicz,
1996], siendo siempre un problema la minimizacion de las caractersticas usadas y el robustecimiento
de los resultados ante ruido [ver Vafaie y De Jong, 1994]. Esto genero el planteamiento del problema
de induccion de reglas usando Multiestrategias de Busqueda [ver Michalski, 1994]. Al determinar la
importancia de la data de entrenamiento se introdujeron algunas variaciones en el aprendizaje de
reglas secuenciales incluyendo pasos de entrenamiento intermedio aplicados al campo de la robotica,
planteando algoritmos de induccion de reglas como el AQ15 [ver De Jong et al, 1995]. Finalmente se
ha tratado el prolema de clasicacion de patrones en imagenes satelitales y faciales usando arboles
binarios y algoritmos geneticos [ver Bala et al, 1995]. El problema de clasicacion de patrones
sonoros en sistemas de alta complejidad y en presencia de ruido destructivo ha sido un problema no
abordado desde esta perspectiva.
Este informe tecnico propone una metodologa para encontrar reglas de clasicacion a partir de la
seleccion de caractersticas fsicas de los elementos. Mediante un algoritmo genetico se implementa
la busqueda de umbrales de caracterizacion de informacion clasicando con arboles de decision,
deteniendose la busqueda cuando se satisfaga un criterio de desempe~no. La integracion de arboles y
algoritmos geneticos permiten evaluar en cada poblacion el desempe~no de la clasicacion generada
por la poblacion de umbrales de caracterizacion y de acuerdo a esta evaluacion proseguir la busqueda.
Por lo anterior, el problema de extraccion de reglas se reduce a un problema standard de optimizacion
1
N
N1
N2
N4
N3
N7
N5
N6
N8
Figura 1: A rbol binario de clasicacion
sin restricciones. La caracterizacion de la data de entrenamiento se realiza usando Transformada
de Fourier y Transformada Wavelets. Los resultados son mostrados de acuerdo al desempe~no de
clasicacion que ha sido denido como criterio de parada.
2 Denicion del problema
El problema que se quiere solucionar es la busqueda y clasicacion de patrones sonoros generados
por impactos destructivos en una maquinaria industrial. La induccion de reglas que puedan diferenciar entre impactos destructivos y no destructivos constituye una valiosa informacion que perimtira
modicar las variables de operacion que gereran el comportamiento agresivo. El medio de adquisicion de datos es muy desfavorable ya que las se~nales de sonido presentan ruido destructivo causados
por los fenomenos de ruido ambiente y ruido de medicion (saturaciones). Por esto es muy difcil
deducir reglas de clasicacion del tipo de material que genera el impacto. Intuitivamente se tiene
alguna idea de cuales variables de operacion afectan los patrones de sonido pero este conocimiento
no es suciente para establecer reglas de clasicacion que permitan dise~nar arboles de decision con
un desempe~no aceptable.
Se propone como metodo de clasicacion a los A rboles Binarios, por su facilidad de implementacion
computacional y por su robusto desempe~no en clasicacion. Se utilizara como tecnica de busqueda
de umbrales de clasicacion un Algoritmo Genetico en su version standard.
3 Estrategias de solucion
3.1 A rboles Binarios de Clasicacion
Un individuo perteneciente a una poblacion es caracterizable a partir de un conjunto de medidas que
representan el valor de la caracterstica asociada al individuo. Esta informacion puede agruparse
como un vector de medidas Xi = (xi1 ; xi2 ; : : : ; xip ) asociado al individuo i-esimo. Una regla de
clasicacion es una funcion talque:
d(xi ) = j
(1)
de manera que xi 2 clasej asigna a cada individuo una clase en base a su vector de medidas. Una
regla se construye a partir de la division del espacio de informacion mediante particiones binarias,
como se muestra en la gura 1. Los nodos terminales se simbolizan con cuadrados y los nodos
intermedios con crculos. Cada nodo terminal contiene individuos que pertenecen a la misma clase.
Son etapas clave en el dise~no de un arbol la seleccion de las particiones y el criterio para determinar
nodos terminales. Una particion se realiza para disminuir la heterogeneidad en una poblacion. Para
ello se somete al individuo a una medicion que permite cuanticar la homogeneidad del nodo respecto
2
Figura 2: Algoritmo Genetico en su version standard
de la clase asociada. La cuanticacion se realiza mediante una medida de impureza considerando
una proporcion de elementos p( jt ) en el nodo t que pertenecen a la clase j, de manera que:
1
j
it(p( ); : : : ; p( )) 0
t
t
8p( kt ) 2 [0; 1]
it(1; 0; 0; : : : ; 0) = it(0; 1; 0; : : : ; 0) = : : : = it(0; 0; 0; : : : ; 1) = 0
(2)
(3)
donde it(p( 1t ); : : : ; p( jt )) es una medida de impureza maxima y simerica. La bondad de l;a particion
s se mide a traves del decrecimiento de impureza denido por:
i(s; t) = it ; (pl itl) ; (pr itr)
(4)
donde pl y pr son la proporcion de elementos asignados al nodo tl y tr y itl e itr son las medidas
de impureza asociadas a los nodos izquierdo y derecho, respectivamente. La particion optima del
nodo es aquella que es capaz de generar subregiones de informacion homogeneas y que causa un
decrecimiento de impureza maximo Di(s ; t). Un nodo sera declarado terminal si no reeja un
decrecimiento signicativo de la impureza, i.e.:
i(s ; t) < (5)
donde representa una medida de la frondosidad del arbol y siempre es positiva.
3.2 Algoritmos Geneticos
Los algoritmos geneticos son tecnicas de busqueda inteligente de soluciones posibles evaluadas en
cada iteracion con una funcion de desempe~no. Un algoritmo genetico en su version standard consiste
basicamente en:
Generar una poblacion inicial.
Evaluar cada individuo.
Mantener el mejor.
Seleccionar individuos para generar una nueva poblacion.
Cruzamiento de individuos.
Mutacion de genes.
3
Figura 3: Caracterizacion de la data de entrenamiento
La poblacion inicial consistira en un conjunto de reglas de clasicacion. Usaremos el algoritmo
genetico para originar reglas de clasicacion usando la evaluacion de los arboles a partir de las reglas
generadas. La funcion de evaluacion debe ser proporcional a la capacidad de discriminar entre
impactos objetivo y otros. A partir de la data de entrenamiento se conoce el numero de elementos
objetivo con que se cuenta. De acuerdo a lo anterior, la funcion de evaluacion esta dada por:
f (eval) =
PNn=1 coincidencias
individuosn
n
N
(6)
donde N es el numero de ramas del arbol, coincidenciasn es la cantidad de individuos bien clasicados
en la n-esima rama e individuosn es la cantidad total de individuos de la n-esima rama.
3.3 Caracterizacion de la data de entrenamiento
Se considerara un vector de medidas de tama~no 3. Sus componentes seran:
Amplitud de la se~nal.
Densidad de energa espectral de la se~nal.
Peak de la se~nal en el nivel d1 de la Transfortmada Discreta de Wavelets.
4
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1: Posicion con un elemento
2: Posicion vacia
Figura 4: Clasicacion de se~nales de sonido con un arbol binario
Las razones para escoger estas componentes son que representan a la se~nal en tres espacios distintos:
espacio temporal, espacio frecuencial y espacio temporal/escalar.
El peak del impacto sera detectado y almacenado en un registro.
La densidad de energa espectral sera calculada implementando una algoritmo de FFT . La integral
de energa se implementara mediante el metodo de integracion numerica rectangular:
I
=
Zb
a
f (x)dx =
h
2 (F1 + 2f2 + 2f3 + : : : + 2fn + fn+1) + E
(7)
De acuerdo a los analisis con Wavelets realizados con la data de entrenamiento, seleccionaremos al
Wavelets de Daubechies 2. La descomposicion discreta de las se~nales se realizara con un nivel (banco
de ltros de un paso). Se detectara el peak de la se~nal d1 (detalle de primer nivel) y tambien se
almacenara en un registro.
4 Algoritmo hbrido de extraccion de reglas
Se utilizara un Algoritmo Genetico standard para la busqueda de coecientes de clasicacion que
maximicen la funcion de evaluacion. La funcion de evaluacion debe ser estricta de acuerdo al siguiente
criterio: nuestro problema de clasicacion consiste en la diferenciacion entre una clase
de patrones objetivo y otros elementos (impactos destrucitvos e impactos tolerables). Por lo
anterior, no es admisible clasicar fuera de esta clase a elementos objetivo. Sin embargo, en este
primer intento se aceptara clasicar dentro de esta clase a elementos que no lo son.
Si se forma una pila de elementos, el problema de clasicacion se reduce a lo expuesto en la gura 4.
En ella se muestra una clasicacion mediante un arbol binario. Las posiciones marcadas con un '1'
corresponden a impactos clasicados en esa rama y en ese orden. Las posiciones marcadas con '0'
5
Figura 5: Algoritmo hbrido de extraccion de reglas
estan vacias. A modo de ilustracion supongamos que a partir de las pruebas de laboratorio se sabe
que los 5 primeros elementos corresponden a patrones objetivo. De acuerdo a lo anterior, el arbol ha
clasicado erroneamente el elemento encerrado, ya que lo muestra como un elemento perteneciente
a la misma clase de los 5 primeros. Si consideramos como tness de cada individuo la evaluacion
de su clasicacion, podemos aplicar los metodos tradicionales de seleccion, cruzamiento y mutacion
para generar nuevas poblaciones de individuos que permitan encontrar arboles asociados capaces de
discriminar mas elementos de los patrones objetivo, como muestra la gura 5.
5 Resultados experimentales
Se utilizo un Algoritmo Genetico standard (elitismo, seleccion, cruzamiento y mutacion), con 100
individuos por generacion, 0.8 de probabilidad de cruce y 0.15 de mutacion. El objetivo del experimento es extraer una regla de clasicacion de impactos destructivos que permita detectar en
el total de los casos la presencia de impactos de este tipo, siendo tolerable los errores de clasicar
como impactos destructivos a algunos impactos que sean de otros elementos. La data original de
laboratorio conformo una base de datos de 70 impactos distribuidos de la siguiente manera:
TIPO DE MATERIAL
CANTIDAD
acero (destructivo)
20
magnetita (no destructivo)
25
huevillo (no destructivo)
15
otros (no destructivo)
10
Debido a la alta cantidad de individuos pertenencientes a cada poblacion, el algoritmo se estabilizo
en torno a una solucion tras solo 3 iteraciones. El tness del individuo mejor evaluado es de 0.86, lo
que quiere decir que de los 70 impactos, 7 fueron mal clasicados, o sea, confundidos con acero. La
distribucion de este error se muestra en la siguiente tabla:
6
TIPO DE MATERIAL BIEN CLASIFICADOS MAL CLASIFICADOS ERROR %
acero
20
0
0
magnetita
20
5
20
huevillo
15
0
0
otros
8
2
20
Como se puede observar en la tabla anterior, el mejor individuo ha generado un arbol de clasicacion
que es capaz de distinguir todos los impactos de acero. Sin embargo, ha clasicado como acero a 5
impactos de magnetita y 2 de otros elementos. Si bien este resultado no es el mmejor, es aceptable,
ya que a partir de esta experiencia se puede inferir una regla de clasicacion que permita detectar
todos los impactos destructivos.
6 Conclusiones
Dados los objetivos iniciales del problema de clasicacion, los resultados experimentales pueden
ser considerados como satisfactorios. La deteccion de impactos destructivos es buena y solo resta
disminuir aun mas la cantidad de impactos no diferenciados de la clase objetivo. Sin embargo, aun
hay muchos topicos que investigar como los siguientes:
Incluir busquedas inteligentes de parametros como Tabu Search o Simulted Annealing.
Incluir como una variable de optimizacion mas la cantidad de variables fsicas de caracterizacion de la data y su posicion relativa en el arbol.
Incluir modicaciones en la funcion de evaluacion como ndices de entropa e impureza.
La estrategia mostrada representa una alternativa interesante para la resolucion de muchos problemas
de clasicacion de patrones de alta complejidad, por lo que es de interes evaluar su desempe~no en
problemas como Imagen Satelital (GIS), Facial Image registration y Reconocimiento de Voz.
7 Referencias
[Bala et al, 1995] J. Bala, J. Huang, H. Vafaie, K. DeJong y H. Wechsler, Hybrid Learning Using
Genetic Algorithms and Decision Trees for Pattern Classication, en IJCAI conference, 19 al 25 de
Agosto de 1995.
[Breinman y Friedman, 1984] L. Breinman y J. Friedman, Clasication and regression trees, en
Wadsworth International Group Series, 1984.
[De Jong et al, 1995], K. De Jong, M. Potter y J. Grefenstette, A Coevolutionary Approach to
Learning Sequential Decision Rules, en Genetic Algorithms: Proceedings of the Sixth International
Conference (ICGA95), Julio 15-19, Pittsburg, Pennsylvania USA, Morgan Kaufmann, 1995.
[Michalewicz, 1996] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs,
Tercera Edicion, Springer, 1996.
[Michalski, 1994] R. Michalski, Inferential Theory of Learning: Developing Foundations for Multistrategy Learning en Machine Learning: A Multistrategy Approach, Vol. IV, R.S. Michalski y G.
Tecuci (Eds.), Morgan Kaufmann, San Mateo, CA, 1994.
[Vafaie y De Jong, 1994] H. Vafaie y K. De Jong, Improving the Performance of a Rule Induction
System Using Genetic Algorithms, en Machine Learning: A Multistrategy Approach, Vol. IV, R.S.
Michalski y G. Tecuci (Eds.), Morgan Kaufmann, San Mateo, CA, 1994.
7