Conjuntos de sujeción axial EAMM-A TOC Bookmark Conjuntos ...
Algoritmos que combinan conjuntos aproximados y ...
Transcript of Algoritmos que combinan conjuntos aproximados y ...
Universidad Central “Marta Abreu” de Las Villas
Facultad de Matemática, Física y Computación
Centro de Estudios de Informática
Departamento de Computación
Algoritmos que combinan conjuntos
aproximados y optimización basada en colonias
de hormigas para la selección de rasgos.
Extensión a múltiples fuentes de datos.
Tesis en opción al título de Doctor en Ciencias Técnicas
Especialidad Informática
Autor: MSc. Yudel Rodrigo Gómez Díaz
Tutores: Dr. Rafael Esteban Bello Pérez
Dra. Ann Nowé
Santa Clara, 2010
DEDICATORIA
¡Todo este trabajo está dedicado a mi familia!
… y eso incluye a mis amigos.
A la memoria de mis seres queridos.
AGRADECIMIENTOS
Estoy eternamente agradecido a todas las personas que me han
ayudado a llegar a este momento.
Afortunadamente en el camino he encontrado mucha gente a quien he dicho
innumerables veces "gracias", pero no puedo nombrarlas todas aquí…
se llevan un agradecimiento anónimo.
A mis colegas del Laboratorio de Inteligencia Artificial y del Departamento.
A los estudiantes que durante años han trabajado conmigo.
A Fidel Sanz, quien me introdujo en el mundo de la computación.
Al profesor y amigo Grau, imprescindible.
To my advisor and also friend Ann Nowé for her effort and courage.
A Bello quien no sólo es tutor, también es el padre de este proyecto.
A mi esposa.
Y al impulso de toda mi vida: mis padres.
SÍNTESIS
En muchos dominios de aplicación, las fuentes de datos se encuentran esparcidas con grandes
volúmenes de información y no es factible centralizar los datos en un único repositorio con la
finalidad de descubrimiento de conocimiento. En este contexto de datos y sistemas distribuidos
la Minería de Datos Distribuida es la disciplina que dedica el estudio a esta problemática. Un
elemento clave en estos procesos es la correcta selección de los atributos principales que
describen los datos. Sin embargo, hay determinados argumentos que demuestran aspectos en este
campo donde la ciencia aún no ha dado respuestas concluyentes.
Como una cuestión importante en esta investigación se ha explicado y validado como combinar
con eficiencia la Optimización mediante Colonias de Hormigas (Ant Colony Optimization,
ACO) y la Teoría de Conjuntos Aproximados (Rough Set Theory, RST) para obtener algoritmos
de selección rasgos que operen en contexto distribuido o no. Un análisis del comportamiento del
algoritmo ha establecido criterios sobre los parámetros, y se ofrecen alternativas para agilizar su
tiempo de ejecución.
El fundamento del contexto distribuido está basado en la cooperación entre subsistemas que
comparten algún tipo de información sobre los datos que operan. En esta tesis se ha extendido la
metaheurística ACO convirtiéndola en ACO multicolonias mediante intercambios de feromona;
donde cada colonia representa un algoritmo ACO resolviendo un problema con un
comportamiento colaborativo entre hormigas de otras colonias mediante intercambios
"frecuentes" de feromona.
Los algoritmos obtenidos han sido aplicados con éxitos al problema de predicciones de infarto
agudo del miocardio en pacientes cardiópatas.
ABSTRACT
In several application domains the data source are distributed storing a lot of information and it is
not viable to centralize all data in one main repository to knowledge discovering. In this context
involving distributed data and systems, Distributed Data Mining is the field dedicated to study
these topics. A key question in these processes is the right selection of the main attributes
describing the data. However, there are specific studies showing concerns in this field, where
science has not given conclusive answers. As important issue, in this research, it has been
explained and validated how to efficiently combine Ant Colony Optimization with Rough Set
Theory to create feature selection algorithms working in distributed or not distributed context.
An experimental study has been carried out to evaluate the algorithms, and establishing rules of
thumb for setting its parameters. A statistic analysis of these algorithms has originated some
criteria about algorithms' parameters, and two alternatives are offered to speed-up the runtime.
The principle of distributed context is based on cooperation among subsystems sharing some
kind of information about the working data. In this research, it has been established how to
extend ACO becoming in a multi-colony ACO by means of interchanges of pheromone. Each
colony represents an ACO algorithm solving a problem with collaborative behavior among ants
from other colonies by means of “frequent” interchanges of pheromone.
The algorithms proposed have been successfully applied to predict acute heart attack in
cardiopaths.
Tabla de Contenido
Síntesis .......................................................................................................................................................... 1
Abstract ......................................................................................................................................................... 4
INTRODUCCIÓN ............................................................................................................................................. 1
1 Métodos de selección de rasgos y sus componentes ......................................................................... 11
1.1 Selección de rasgos en el contexto del aprendizaje automatizado .................................................. 12
1.2 Conjuntos aproximados .................................................................................................................... 18
1.3 Inteligencia Colectiva aplicada al problema de selección de rasgos ................................................ 23
Optimización basada en Colonias de Hormigas .................................................................................. 24
ACO Multicolonias............................................................................................................................... 31
1.4 Consideraciones parciales ................................................................................................................. 31
2 Inteligencia colectiva aplicada a la selección de rasgos ...................................................................... 33
2.1 Solución al problema de selección de rasgos. Algoritmo ACO-RST-FSP ........................................... 33
2.2 Estrategias de ahorro del tiempo de ejecución en la implementación ACO .................................... 47
2.2.1 Codificación de la función de evaluación ................................................................................... 47
2.2.2 Decremento de la exploración ................................................................................................... 51
2.3 Solución al problema de la selección de rasgos sobre múltiples fuentes de datos. El algoritmo
D.ACO-RST-FSP ........................................................................................................................................ 56
2.4 Consideraciones parciales ................................................................................................................. 64
3 Caso de estudio: "El problema de cardiopatías"................................................................................. 65
3.1 Descripción del problema ................................................................................................................. 66
3.2 Algoritmos de selección de rasgos presentados aplicados al problema de cardiopatías ................. 71
3.3 Solución al pronóstico de infarto agudo del miocardio con un clasificador ..................................... 74
3.4 Consideraciones parciales ................................................................................................................ 80
CONCLUSIONES ........................................................................................................................................... 81
RECOMENDACIONES ................................................................................................................................... 83
REFERENCIAS ............................................................................................................................................... 84
PRODUCCIÓN CIENTÍFICA DEL AUTOR SOBRE EL TEMA DE LA TESIS .......................................................... 95
Anexos ......................................................................................................................................................... 97
Anexo 1. Características de los conjuntos de datos ................................................................................ 97
Anexo 2. Resultados experimentales de la estrategia de ahorro ........................................................... 98
Introducción
1
INTRODUCCIÓN
“We are drowning in information but starving for knowledge.”
– John Naisbitt
En los últimos años se ha producido un importante crecimiento de las bases de datos en todas las
áreas del conocimiento humano. Este incremento, cuantitativo y cualitativo, se posibilita gracias
principalmente al progreso en las tecnologías para la adquisición y almacenamiento de los datos.
A la vez, estos beneficios han superado significativamente nuestra capacidad de analizarlos,
resumirlos y obtener conocimiento de estos. Existen diversos dominios donde se almacenan
grandes volúmenes de información en bases de datos centralizadas y distribuidas, como por
ejemplo bibliotecas digitales, archivos de imágenes, centros de investigaciones en
bioinformática, cuidados médicos, finanzas e inversión, fabricas, redes de telecomunicación, etc.
Es conocida la frase: "los datos en bruto raramente son beneficiosos directamente". Su verdadero
valor se basa en la habilidad para extraer información útil, la toma de decisiones o la exploración
y la comprensión del fenómeno gobernante en la fuente de datos. En muchos dominios, el
análisis de datos fue tradicionalmente un proceso manual. Analistas familiarizados con los datos,
con la ayuda de técnicas estadísticas, proporcionaban resúmenes y generaban informes. Sin
embargo, tal enfoque cambió como consecuencia del crecimiento del volumen de datos y la
diferenciación cualitativa de estos. Cuando la escala de manipulación de datos, exploración e
inferencia va más allá del alcance de la estadística clásica, se necesita la ayuda de nuevas
técnicas y herramientas computacionales para el descubrimiento y el análisis de la información.
En el centro de esta problemática se encuentra el proceso de descubrimiento de conocimiento,
conocido en la comunidad como Descubrimiento de Conocimiento en Bases de datos (del inglés
Knowledge Discovery in Databases, KDD) (Fayyad, Piatetsky-Shapiro, & Smyth, 1996). Según
Fayyad, KDD es el proceso global no trivial de identificar patrones válidos, novedosos,
potencialmente útiles y comprensibles a partir de los datos. Un paso particular en este proceso es
la Minería de Datos (Data Mining, DM), como la aplicación de algoritmos específicos para la
Introducción
2
extracción de patrones y relaciones dentro de los datos permitiendo la creación de modelos, es
decir, representaciones abstractas de la realidad.
El objetivo de la minería de datos es extraer conocimiento de los datos. Este es un campo
interdisciplinario cuyo centro está en la intersección de aprendizaje automatizado, estadísticas y
bases de datos; con la meta de descubrir conocimiento no sólo preciso sino entendible. La DM
comenzó a desarrollarse a partir de grandes volúmenes de información, esencialmente como
técnicas de análisis de los datos, o a decir de Kargupta (Kargupta, 2003), como la necesidad de
metodologías de análisis inteligente de datos que puedan descubrir conocimiento útil de los
mismos.
En diversos dominios de aplicación, los datos se encuentran distribuidos en varios nodos
ubicados en sitios geográficamente esparcidos. En muchos de estos entornos se encuentran
fuentes de información con grandes volúmenes de datos y múltiples unidades de cómputo. En
estos casos, por lo general, no es posible o factible centralizar todos los datos del sistema de
información distribuido en un único repositorio, con el propósito de realizar tareas de minería de
datos, debido a restricciones económicas, técnicas o legales.
Con las nuevas aplicaciones en contextos distribuidos a las que aplicar técnicas de DM sobre
múltiples fuentes de datos surge el, aún emergente, campo de la Minería de Datos Distribuida
Distribuida (Distributed Data Mining, DDM) (Aflori & Leon, 2004; Aounallah & Mineau, 2007;
Park & Kargupta, 2002; Ye, 2003), muy activo, con una atención creciente desde su comienzo y
todavía surgiendo como un problema computacional fundamental. Un primer paso en el
desarrollo de soluciones en este campo es identificar, formalmente, cómo estaban distribuidos
los datos. En DDM las fuentes de datos se pueden clasificar en homogéneas o heterogéneas. En
las homogéneas las diferentes fuentes de datos representan exactamente la misma información
con los mismos rasgos. En las heterogéneas las diferentes fuentes de datos que almacenan la
información están representadas por conjuntos de rasgos diferentes, posiblemente con algunos
rasgos comunes.
Un sistema en DDM involucra varios subsistemas (vistos como sistemas más reducidos que
están interrelacionados y establecen algún mecanismo de comunicación) e inmersos, en obtener
un modelo o esquema. Existen varias alternativas, pero este trabajo se enmarca en un medio
Introducción
3
donde no se pueden agrupar todos los datos para llevar a cabo la tarea de minería. El modelo que
se presenta trata con conjuntos de datos homogéneos. El fundamento del contexto distribuido
está basado en la cooperación entre subsistemas que comparten algún tipo de información acerca
de los conjuntos de datos sobre los que operan, para llegar a un mejor resultado.
Paralelamente, el asunto de la privacidad está creciendo en importancia en un rol protagónico en
las aplicaciones emergentes de minería de datos (Silva, Giannella, Bhargava, Kargupta, &
Klusch, 2005). Por ejemplo, considere un consorcio de diferentes bancos que quiere colaborar
para detectar fraudes, entonces un sistema de minería de datos centralizado parece requerir la
recolección de todos los datos de cada banco en un mismo lugar; pero esto evidentemente
amenaza la privacidad. Sin embargo, ello no es necesario si la minería de datos distribuida es la
tecnología elegida. Los sistemas en DDM pueden ser capaces de aprender modelos desde fuentes
de datos distribuidas sin intercambiar los datos en sí, lo cual satisface en el ejemplo, las dos
pretensiones: la detección central de fraudes y la preservación de la privacidad de cada una de las
transacciones de datos de los bancos involucrados. Un desafío considerable consiste en encontrar
qué tipo de meta-información1 debe ser compartida para lograr este propósito.
Otra técnica relacionada con DDM es la Minería de Datos Paralela (parallel data mining, PDM);
un sistema de minería de datos paralelo es un sistema fuertemente acoplado en el que se incluyen
máquinas de memoria compartida, máquinas de memoria distribuida, o un híbrido entre estas dos
arquitecturas, que en sentido general se caracterizan por contar con una red de interconexión
muy rápida. Por el contrario, un sistema de DDM es un sistema ligeramente acoplado; en tales
sistemas se incluye también sistemas distribuidos geográficamente sobre una red de área ancha
similar a Internet (Palancar, 2004).
Según (Provost, 1999) algunas de las principales ideas que surgen de los trabajos existentes
sobre la minería de datos distribuidos son las siguientes: (i) Distribuir el espacio de búsqueda
puede ser problemático. (ii) Operar sobre las instancias distribuidas puede ser efectivo y muy
eficiente. (iii) La colaboración entre procesos distribuidos permite realizar minería efectiva,
incluso sin un control centralizado.
1 Entiéndase como información sobre los datos o sobre el comportamiento del algoritmo en cuestión.
Introducción
4
Existen dos técnicas principales para la cooperación que han sido particularmente eficaces. En la
primera los procesadores pueden funcionar de manera independiente sobre subconjuntos de los
datos y a continuación combinar sus modelos. En la segunda un procesador puede también
compartir el conocimiento potencial al ser descubierto, con el fin de obtener las opiniones de los
otros procesadores (por ejemplo, sus evaluaciones estadísticas). Esta última técnica es la que más
se ajusta al trabajo presentado, debido a la existencia de la voluntad de cooperación entre los
subsistemas, la manera de colaboración encontrada consiste en enviar sólo información de los
datos (metadatos) de un procesador a otro.
Un paso importante en el descubrimiento de conocimiento en general, es preparar los datos para
la DM, de igual forma si se trata de DDM. El pre-procesamiento de datos en DDM debe
funcionar de manera que la distribución de los datos sea una fortaleza, no una debilidad. Puede
considerarse que muchas de las técnicas de pre-procesamiento de datos centralizados pueden ser
directamente aplicadas sin descargar todos los conjuntos de datos hacia un solo sitio (Kargupta,
2003). Dentro de los procesos o tareas más notables del preprocesamiento se destaca la elección
correcta de las características, propiedades o atributos que caracterizan los datos. Teóricamente
el tener más atributos daría más poder discriminatorio; sin embargo, la experiencia con
algoritmos de aprendizaje ha demostrado que no es siempre así, detectándose algunos problemas:
tiempos de ejecución muy elevados, aparición de muchos atributos redundantes y/o irrelevantes,
y la degradación en el error de la clasificación.
El planteamiento anterior da lugar a investigaciones en la creación de métodos de selección de
rasgos. Las investigaciones relacionadas con esta temática intentan reducir el espacio de
hipótesis en los conjuntos de datos2 en tareas concretas, con una pretensión de encontrar
subconjuntos de atributos que proporcionen un mejor rendimiento de los algoritmos de
aprendizaje. Existen en la literatura, un gran número de propuestas para resolver el conocido
problema de selección de rasgos, aunque no se ha encontrado aún un algoritmo para realizar esta
tarea obteniendo resultados globales óptimos. La búsqueda de subconjuntos óptimos de atributos
para realizar el proceso de aprendizaje, dada su complejidad computacional, se basa en una
2 Conjuntos de datos es el término más apropiado encontrado para la traducción de la expresión data set
comúnmente usada en aprendizaje automatizado.
Introducción
5
busqueda heurística, y tal como plantea el Teorema No Free Lunch(Wolpert & Macready, 1997),
no existe un método que garantice ser mejor que los demás, lo que conlleva la continua aparición
de nuevos métodos o la aplicación de selección de rasgos en nuevos entornos. A la vez, la
complejidad que implica la solución de este problema da indicios de que una solución universal
no será encontrada.
El problema de la selección de rasgos en contexto distribuido, en general, es similar al problema
clásico de selección de rasgos, pero existe la expectativa de desarrollar algoritmos para la
selección de rasgos que consigan ser más eficientes, y más eficaces, que los obtenidos en un
ambiente no distribuido con el mismo objetivo.
En general, todo algoritmo de selección de rasgos consta de dos componentes básicos: función
de evaluación y método de búsqueda o generación de subconjuntos. La variedad de técnicas de
selección de rasgos está dada precisamente por la diversidad de algoritmos utilizados como
métodos de búsqueda en la generación de los subconjuntos candidatos o la exploración del
espacio de búsqueda como otra interpretación y las disímiles variantes de evaluación de estos
subconjuntos. Los algoritmos estudiados en esta tesis utilizan la combinación de la Optimización
basada en Colonias de Hormigas, como método de búsqueda, y una medida de la Teoría de
Conjuntos Aproximados, como función de evaluación.
La Optimización basada en Colonias de Hormigas es una metaheurística poblacional que
puede ser usada para encontrar soluciones aproximadas a problemas complejos de optimización
discreta (Marco Dorigo & Stutzle, 2004). En ACO, durante cada ciclo, un número de hormigas
artificiales construyen secuencialmente soluciones de una forma combinada aleatoria y golosa.
Cada hormiga selecciona el próximo elemento a ser incorporado en su solución parcial actual
sobre la base de alguna evaluación heurística y la cantidad de feromona asociada con este
elemento. La heurística provee el valor de una solución candidata específica. La feromona
representa la memoria del sistema, y está relacionada con la presencia de ese elemento en
soluciones previamente construidas (de esta forma la intensidad del rastro de feromona está
relacionado con cuantas hormigas habían decidido anteriormente seguir ese camino). La
aleatoriedad (el hecho de hacer algún tipo de selección al azar) es usada para facilitar la
construcción de una variedad de soluciones diferentes. Se define una distribución de
Introducción
6
probabilidad sobre todos los elementos que pueden ser incoporados a la solución parcial actual
favoreciendo los mejores elementos. En particular, un elemento con una buena evaluación
heurística y un alto nivel de feromona es más propenso a ser seleccionado.
Cada vez que una hormiga selecciona un elemento actualiza el nivel de feromona de éste,
primero substrayendo una fracción de su valor, imitando la evaporación de la feromona y luego
adicionando un nuevo valor. Cuando todas las hormigas han construido una solución completa,
el procedimiento se reinicia manteniendo los valores del nivel de feromona actualizado. Esto es
repetido para un número prestablecido de ciclos o hasta algún otro criterio de parada.
La Teoría de Conjuntos Aproximados fue introducida por Z. Pawlak en 1982 (Pawlak, 1982).
La filosofía de los conjuntos aproximados se basa en la suposición de que con todo objeto de un
universo está asociada una cierta cantidad de información, expresada por medio de algunos
atributos que describen el objeto (J. Bazan & Son, 2003). En esta teoría, la estructura de
información básica es el Sistema de Información; esto es, una tabla de datos representando un
universo de ejemplos (objetos, entidades, situaciones o estados) descritos por atributos, donde
uno de estos atributos tiene un carácter distintivo indicando la decisión tomada en ese estado o
situación o definiendo la clase de un objeto.
Un aspecto importante en la RST es la reducción de atributos basada en el concepto de reductos.
Un reducto es un conjunto reducido de atributos que preserva la partición del universo (Jensen,
2005; Komorowski & Pawlak, 1999; Zhong & Dong, 2001). El problema de encontrar reductos
ha sido tema de varias investigaciones (Alpigini, Peters, Skowronek, & Zhong, 2002; Swiniarski
& Skowron, 2003; Ziarko, 2002). La reducción de atributos a través de los conjuntos
aproximados se basa en comparaciones generadas por conjuntos de atributos siguiendo ciertas
particularidades que son detalladas en epígrafes posteriores. En la construcción de un reducto se
seleccionan atributos de manera sucesiva hasta que se obtenga un conjunto reducido tal que
provea la misma calidad de la clasificación supervisada que el original. Un conjunto de datos
puede tener varios reductos. Un objetivo importante en el cálculo de reductos es encontrar un
subconjunto mínimo de éstos; o sea, un subconjunto reducto con mínima cardinalidad
(Thangavel & Pethalakshmi, 2009).
Introducción
7
Formulación del problema
Muchas de las investigaciones en el aprendizaje inductivo se concentran en problemas con
cantidades, relativamente pequeñas o medianas, de datos y concentradas en un único conjunto de
datos. Como se ha planteado, con el auge de las redes de computadoras y el desarrollo de
Internet, la magnitud de los datos y su localización física en posibles ambientes geográficamente
distribuidos, demanda métodos de aprendizaje acorde a estos nuevos dominios de problemas del
mundo real. Entre las acciones principales comprendidas están el pre-procesamiento de los datos
y la obtención de modelos de clasificación y/o pronóstico. Un elemento clave que incluye el pre-
procesamiento es la selección de los rasgos principales que describen los datos. Lo planteado
constituye una problemática que la ciencia aún no ha dado respuestas concluyentes, por lo que se
formula el siguiente problema de investigación:
Los métodos existentes actualmente no han resuelto totalmente la selección de atributos con un
costo computacional adecuado y hasta el momento el problema de la selección de rasgos en
ambientes distribuidos no ha sido abordado suficientemente. Esto afecta a los algoritmos de
aprendizaje automatizado encargados de extraer el conocimiento inherente a los datos.
El problema de investigación se concretó en las siguientes preguntas de investigación:
¿Si se combina la metaheurística Optimización basada en Colonias de Hormigas con elementos
de la Teoría de Conjuntos Aproximados, se lograrán buenos resultados con alta eficiencia en el
proceso de selección de atributos relevantes en ambientes distribuidos?
¿Qué efecto provoca en el proceso de selección de rasgos, el uso de información adicional
proveniente de subsistemas que efectúan la misma tarea, en un contexto distribuido con
colaboración?
¿Qué resultados o ventajas pueden alcanzarse al emplear las propuestas presentadas, en la
selección de rasgos para la realización de pronósticos en algunas aplicaciones concretas, aún
cuando hayan sido competitivamente estudiados, pero no en forma distribuida?
La respuesta a la tercera pregunta de investigación pretende ser ejemplificada con una aplicación
específica a la predicción de Infarto Masivo del Miocardio (IMA) entre enfermos de cardiopatías
Introducción
8
de la provincia de Villa Clara. La investigación tiene antecedentes, con resultados muy positivos
en el pronóstico con un preprocesamiento estadístico, excelente y envidiable, de selección
(transformación de rasgos) con el cual se pretende competir, aprovechando las nuevas técnicas y
el ambiente distribuido.
Del planteamiento del problema y la formulación de las preguntas de investigación emerge el
siguiente
Objetivo general:
Diseñar métodos de selección de rasgos, combinando la Optimización basada en Colonias de
Hormigas y la Teoría de Conjuntos Aproximados en problemas de aprendizaje supervisado tanto
en contexto local como distribuido que permitan encontrar, una o varias, colecciones reducidas
de atributos, capaces de representar la información necesaria para el aprendizaje, y en última
instancia, facilitar su aplicación ante nuevos casos.
Este objetivo anterior se desglosa en los siguientes objetivos específicos:
1. Formular un algoritmo que combine Optimización basada en Colonias de Hormigas y la
Teoría de Conjuntos Aproximados para selección de rasgos mejorando la eficiencia con
respecto al costo en tiempo de ejecución.
2. Proponer una variante del algoritmo formulado en el objetivo específico anterior para
resolver el problema de la selección de rasgos en contexto distribuido.
3. Valorar la aplicación de los algoritmos propuestos en la solución de un problema de
aplicación, concretamente, la selección de riesgos relevantes para el pronóstico de infarto
agudo del miocardio en pacientes con cardiopatías.
Después de haber construido el marco teórico se formularon las siguientes hipótesis de
investigación:
H1: La combinación de la metaheurística Optimización basada en Colonias de Hormigas con
elementos de la Teoría de Conjuntos Aproximados permite lograr un nuevo algoritmo de
selección de rasgos suficientemente efectivo, y la introducción de estrategias en la
Introducción
9
implementación de la búsqueda que ejecutan las hormigas en la metaheurística ACO mejora la
eficiencia del algoritmo, al menos, preservando la calidad de las soluciones.
H2: El uso de información adicional, que refiere el funcionamiento del algoritmo, proveniente de
subsistemas que efectúan el proceso de selección de rasgos en un contexto distribuido, con
colaboración, perfecciona la calidad global del sistema.
Novedad científica
La novedad científica radica en la creación de métodos de selección de rasgos con alternativas
para elevar su eficiencia, tanto en contexto local como distribuido, basados en la combinación de
la metaheurística Optimización basada en Colonias de Hormigas y la Teoría de Conjuntos
Aproximados.
El valor práctico está relacionado con la obtención de dos algoritmos de selección de rasgos
que pueden ser utilizados, en general, en el preprocesamiento de conjuntos de datos. Como
ejemplo de aplicación concreta, se muestra la selección de rasgos en el pronóstico de infarto
masivo del miocardio en pacientes con cardiopatías.
Como valor social se considera que el trabajo realizado promueve el desarrollo de nuevas
investigaciones en el campo de la minería de datos, particularmente en la temática de selección
de rasgos y fomenta la experimentación en la búsqueda de mejores soluciones. Es, además,
fuente de estudio para estudiantes de las carreras afines.
De otra parte, los resultados obtenidos en la selección de riesgos para el pronóstico de infarto
masivo del miocardio, tienen sobre todo, una importancia social, porque permiten que dicho
pronóstico esté al alcance de los médicos del Nivel Primario de Salud, sin las complicaciones
matemáticas de criterios diagnósticos anteriores y sin embargo, fiabilidad compatible con ellos.
La tesis que se presenta está estructurada en tres capítulos:
El Capítulo 1 realiza un análisis crítico sobre la selección de atributos relevantes en el contexto
del aprendizaje automatizado. Se describen, además, los aspectos fundamentales de la
Introducción
10
metaheurística Optimización basada en Colonias de Hormigas y la Teoría de los Conjuntos
Aproximados.
En el Capítulo 2 se proponen dos métodos para la selección de rasgos: el primero combina la
metaheurística Optimización basada en Colonias de Hormigas y la Teoría de los Conjuntos
Aproximados con dos variantes para reducir el tiempo de ejecución y el segundo es una variante
para enfrentar el problema en contexto distribuido.
En el Capítulo 3 se validan los resultados teóricos de la investigación en el preprocesamiento de
los datos y se ilustra la aplicación al problema de pronóstico de IMA en pacientes cardiópatas a
partir de factores de riesgo correlacionados.
Este documento culmina con las conclusiones, recomendaciones, referencias bibliográficas, la
producción científica del autor sobre el tema de la tesis, y algunos anexos considerados
convenientes.
Capítulo 1: Métodos de selección de rasgos y sus componentes
11
1 Métodos de selección de rasgos y sus componentes
Hay varios factores que motivan la inserción de un paso de reducción de dimensionalidad en una
variedad de sistemas de solución de problemas (Carreira-Perpinñan, 2001). La reducción de
dimensionalidad se debe a la preferencia por los modelos más sencillos frente a los más
complejos. Esta preferencia ha sido utilizada con bastante frecuencia en la ciencia moderna y
tiene sus orígenes en el denominado Principio de la Navaja de Occam (Occam’s Razor)
(Gamberger & Lavrac., 1997). Existen dos formas de reducir la dimensión del espacio de datos
de entrada en la dirección vertical. Una de estas consiste en extraer rasgos construyendo
combinaciones lineales y no lineales de una dimensión menor a la de la entrada original, este
proceso se denomina extracción de rasgos. La otra se fundamenta en seleccionar los rasgos a
partir de su capacidad de generalización, y se nombra selección de rasgos.
Aunque la extracción de rasgos no es el tema central de esta investigación, se ofrece una visión
general de esta técnica con el propósito de mostrar la principal diferencia entre estos métodos.
Cuando se aplica la extracción de rasgos se trata de encontrar la mejor combinación de rasgos,
lineal o no lineal, para satisfacer un criterio de reducción de dimensionalidad. Existen métodos
de extracción de rasgos que usan Análisis de Componentes Principales (Principal Component
Analysis, PCA) (Devijver & Kittler, 1982a; Xue, Godden, Gao, & Bajorath, 1999) , Análisis de
Componentes Principales combinada con Recocido Simulado(Meiri & Zahavi, 2006), Regresión
Dinámica Discriminante (HDR), Análisis de Componentes Independientes (Comon, 1994;
Hyvarinen & Oja, 2000), Multidimensional Scaling (MDS) (Cox & Cox, 1994) y Mínimos
Cuadrados Parciales (PLS). Probablemente la técnica más ampliamente utilizada en extracción
de rasgos sea PCA (Duda, Hart, & Stork, 2001). Consiste en construir nuevos rasgos no
correlacionados llamados factores maximizando la varianza. La eficiencia de estos métodos ha
sido demostrada en un rango amplio de dominios de aplicaciones, pero la interpretación de los
nuevos rasgos no es obvia y requiere un esfuerzo importante del usuario.
Capítulo 1: Métodos de selección de rasgos y sus componentes
12
La selección de rasgos o atributos se ha convertido en el foco de muchas investigaciones en áreas
de aplicación. Estas áreas incluyen con especial relevancia el Reconocimiento de Patrones
(Devijver & Kittler, 1982b; Jain & Zongker, 1997; Siedlecki & Sklansky, 1988), el Aprendizaje
Automatizado (Liu & Yu, 2005; Ruiz, Aguilar-Ruiz, & Riquelme, 2004), clasificación de textos
(Chouchoulas & Shen, 2001; Forman, 2003; Santiesteban & Pons, 2003; Zhang, Zhang, & Yang,
2003), detección de intrusos (W. Lee, Stolfo, & Mok, 2000; Lorenzo-Fonseca, et al., 2009;
Tsang & Kwong, 2006) y la Bioinformática (Inza, naga, Blanco, & Cerrolaza, 2004; Saeys, Inza,
& Larrañaga, 2007).
1.1 Selección de rasgos en el contexto del aprendizaje automatizado
La selección de rasgos consiste en encontrar el subconjunto de atributos del conjunto de datos
original que mejor describe los objetos del dominio; tiene como meta reducir la dimensionalidad
del conjunto de rasgos a través de la selección del subconjunto de rasgos de mejor desempeño
bajo algún criterio de clasificación (Liu & Motoda, 2007). Este proceso de selección se hace
eliminando rasgos irrelevantes y redundantes (D. Bell & Wang, 2000; Blum & Langley, 1997),
proveyendo así una mejor representación de la información original reduciendo
significativamente el costo computacional y contribuirá a una mejor generalización del algoritmo
de aprendizaje. Normalmente este proceso está presente en las etapas previas de las principales
tareas de la minería de datos, ya sean supervisadas o no (Liu & Yu, 2005).
Definición 1 (Selección de atributos) Si A es el conjunto de todos los atributos, hacer selección
de atributos es escoger un subconjunto )(APS . Donde )(AP es el conjunto potencia de A, es
decir, el conjunto formado por todos los subconjuntos de elementos de A.
La selección de atributos se puede considerar como un problema de búsqueda (Langley, 1994;
Siedlecki & Sklansky, 1988) en un espacio de estados, donde cada estado corresponde con un
subconjunto de atributos, y este espacio engloba todos los posibles subconjuntos que se pueden
generar ( 12 n para n atributos). Claramente, una búsqueda exhaustiva no es práctica ni para
conjuntos de datos de mediano tamaño (Blum & Langley, 1997). El proceso de selección de
atributos puede entenderse como el recorrido de dicho espacio hasta encontrar un estado
(combinación de atributos) que optimice alguna función definida sobre un conjunto de atributos.
Capítulo 1: Métodos de selección de rasgos y sus componentes
13
Los procedimientos de selección de rasgos constan de dos componentes principales: la función
de evaluación y el método de generación de subconjuntos (basado en un proceso de búsqueda).
Según la naturaleza de la función de evaluación los algoritmos de selección de rasgos pueden
dividirse en tres categorías: filtros, envolventes (del inglés "wrapper") (Langley, 1994), y
empotrados (Blum & Langley, 1997). La primera categoría incluye los algoritmos en los que la
selección de atributos se realiza como un preprocesado independiente de la fase de inducción,
por lo que puede entenderse como un filtrado de los atributos. En los métodos de tipo
envolvente, la selección de atributos y el algoritmo de aprendizaje no son elementos
independientes, ya que la selección hace uso del proceso de inducción para evaluar la calidad de
cada conjunto de atributos seleccionados en cada momento. Los métodos empotrados al igual
que los envolventes involucran al algoritmo de aprendizaje como parte del proceso de selección.
Los empotrados realizan la selección durante el proceso de entrenamiento y cuentan con su
propio algoritmo de selección, como ocurre en los algoritmos que generan árboles de decisión,
utilizan sólo aquellos atributos necesarios para obtener una descripción consistente con el
conjunto de aprendizaje. Por otra parte, otra técnica que también evalúa rasgos es la ponderación
(pesado) de rasgos (feature ranking, feature weighting) (Chu, Keerthi, Ong, & Ghahramani,
2006; Kira & Rendell., 1992; Lorenzo-Fonseca, et al., 2009; Saeys, Degroeve, & Peer, 2006a,
2006b; Weston, Mukherjee, Chapelle, Pontil, & Poggio., 2001; Wettschereckk, Aha, & Mohri,
1997). Estos métodos en particular, en lugar de decidir si un rasgo se considera o no (selector
con imagen 1,0 ), se asigna una importancia a la relevancia del rasgo (usualmente en el
intervalo [0,1]).
Tanto filtros como envolventes hacen uso de estrategias de búsqueda para explorar el espacio de
todas las posibles combinaciones de rasgos, que normalmente es demasiado grande para ser
explorado exhaustivamente. Según estas estrategias los métodos de selección obtienen otra
clasificación: las búsquedas completas, heurísticas y aleatorias. Dentro de las primeras se
encuentran aquellas que tienen complejidad exponencial pero aseguran la obtención del
subconjunto óptimo bajo un criterio dado. Las heurísticas a diferencia de las completas recorren
sólo una porción del espacio de búsqueda, y por tanto no aseguran la obtención del óptimo
aunque el coste computacional es mucho menor. Las estrategias aleatorias se basan en visitar
diferentes regiones del espacio de búsqueda sin un orden claramente predefinido.
Capítulo 1: Métodos de selección de rasgos y sus componentes
14
Estrategias de búsqueda
Liu y otros (Dash & Liu, 1997; Liu & Motoda, 1998; Liu & Motoda, 2008; Liu & Yu, 2005)
realizan una propuesta de clasificación de las estrategias de búsquedas agrupadas en tres
categorías: completa, heurística y aleatoria. En cuanto a los criterios de evaluación, dividen el
tipo filtro en varias categorías dependiendo de qué propiedades se extraen de los mismos. De esta
forma, la clasificación que establecen de las funciones de evaluación es la siguiente: medidas de
distancia, medidas de información, medidas de dependencia, medidas de consistencia. Y además,
las medidas basadas en la tasa de error de un clasificador (correspondientes a las de tipo
wrapper).
En este tópico se hace revisión actual al estado del arte de selección de atributos, teniendo en
cuenta varias revisiones generales y los estudios previos realizados por: (Belanche, Molina, &
Nebot, 2002; Dash & Liu, 1997; Guyon & Eliseeff, 2003; Guyon & Elisseeff, 2006; Kohavi &
John, 1997; Liu & Yu, 2005). A continuación se analizan algoritmos que siguen algunos de estos
enfoques y técnicas.
El método B&B (Branch and Bound) propuesto por Narendra y Fukunaga(Narendra &
Fukunaga, 1977), selecciona un subconjunto lo más pequeño posible, cuya evaluación esté por
debajo del umbral establecido. El método es una variación de la búsqueda en profundidad
dirigida hacia atrás. La medida de evaluación tiene que ser monótona, entre las más utilizadas
están: la distancia de Mahalanobis, la función discriminante, el criterio de Fisher, la distancia de
Bhattacharya, y la divergencia. El usuario debe dar valor a un parámetro que se utiliza para
limitar las ramas en las que buscar (poda), lo que es un inconveniente.
MDLM (Minimum Description Length Method) (Sheinvald, Dom, & Niblack, 1990). En este
algoritmo, si los atributos en un subconjunto V se pueden expresar como una función
independiente de la clase F de otro subconjunto de atributos U (U y V juntos completan el
conjunto de atributos), entonces una vez se conocen los valores de los atributos en U, el
subconjunto de atributos V no se necesita. El algoritmo busca exhaustivamente todos los posibles
subconjuntos y como salida muestra el subconjunto que satisface el criterio de evaluación
MDLC (minimum description length criterion).
Capítulo 1: Métodos de selección de rasgos y sus componentes
15
Focus (Almuallim & Dietterich, 1992) empieza con el conjunto vacío y lleva a cabo una
búsqueda exhaustiva a lo ancho (breadth-first) hasta encontrar un subconjunto mínimo
consistente que prediga las clases puras. Este método rinde mejor cuando el número de atributos
relevantes respecto al total es pequeño, en otro caso, su coste exponencial lo hace inviables. No
maneja bien el ruido debido a su énfasis en la consistencia (Navarro, 2001). Existe una variante
del algoritmo para reducir su coste, Focus-2 (Almuallim & Dietterich, 1994), que utiliza una cola
donde se almacena una parte del espacio de búsqueda.
ABB (Automatic Branch and Bound) (Liu, Motoda, & Dash, 1998) es una modificación de B&B
donde el límite es determinado automáticamente. En (Dash, Liu, & Motoda, 2000) se señala que
toma mucho tiempo aun para un número moderado de atributos irrelevantes. En general, ABB
expande el espacio de búsqueda rápidamente al principio pero su coste exponencial lo acaba
haciendo prohibitivo.
El algoritmo RELIEF (Kira & Rendell, 1992) asigna un peso a cada atributo y selecciona los
atributos cuyo peso supera un umbral prefijado. Se inspira en el aprendizaje basado en casos e
intenta obtener los atributos más relevantes estadísticamente. Un número determinado de veces
toma aleatoriamente una instancia y para cada una de éstas busca dos vecinos, el más cercano de
la misma clase y el de clase distinta. El peso asociado a un atributo se modifica a partir de la
distancia euclídea entre el valor del atributo de la instancia y el valor del mismo atributo de los
vecinos encontrados. Cuando el número de instancias es pequeño, se realiza el proceso para cada
una de las instancias, por esto en ocasiones se clasifica como secuencial y en otras oportunidades
como en (Molina, Belanche, & Nebot, 2002) la organización de la búsqueda aparece como
aleatoria. En (Caruana & Freitag, 1994) se concluye que el problema con Relief se debe al uso de
la distancia como criterio de consistencia (la distancia euclídea no puede ser utilizada en
cualquier contexto). Además determinar el umbral supone un problema.
Kononenko (Kononenko, 1994) propone una versión mejorada, ReliefF; la diferencia radica en
tomar k instancias más parecidas en lugar de una. Otra variante es la propuesta de Liu y otros
(Liu, Motoda, & Yu, 2002) soportada en árboles kd–tree, y para el cálculo de la distancia, se
escoge un sólo ejemplo de los posibles dentro de cada hoja del árbol.
Capítulo 1: Métodos de selección de rasgos y sus componentes
16
SFS (Sequential Floating Search) (Pudil, Novovicová, & Kittler, 1994) es un algoritmo
secuencial bidireccional (con versiones hacia adelante SFFS y hacia atrás SBFS). En cada paso
de selección de atributos, se realiza un paso hacia adelante añadiendo un atributo, y un paso
hacia atrás, donde se suprime aquel atributo cuya ausencia hace que mejore el resto del
subconjunto escogido hasta él. Permite utilizar cualquier criterio de evaluación, aunque el más
usual es la distancia de Bhattacharyya. Ha recibido muy buenas críticas para problemas de
pequeña y mediana escala (Kudo, Somol, Pudil, Shimbo, & Sklansky, 2000). La desventaja
principal es que debe especificarse el tamaño deseado del subconjunto solución.
El algoritmo SFG (Sequential Forward Generation) (Doak, 1992) puede proporcionar un
ranking, donde los atributos se encuentran situados según el orden de inclusión en el conjunto
solución, realiza el ordenamiento según el criterio de información.
El algoritmo FCBF (Fast Correlation-Based Filter) creado por Yu y Liu (Yu & Liu, 2004), se
basa en el concepto de Markov blanket (M) –definido en ese mismo trabajo–, se eliminan
progresivamente los atributos redundantes con M. clase. Este método es muy rápido, pero sus
resultados dependen en gran medida de un parámetro que se utiliza para analizar sólo aquellos
atributos más correlacionados con la clase. Si se le asigna un valor muy pequeño, normalmente
se obtienen grandes subconjuntos que no contienen atributos redundantes y son relevantes con
respecto a la clase. Si se desea obtener subconjuntos más pequeños, se disminuirá bastante su
poder predictivo.
El algoritmo MIFS (Battiti, 1994) aplica información mutua para seleccionar un subconjunto de
atributos que será la entrada de un clasificador mediante redes neuronales. El algoritmo se basa
en calcular la información mutua de cada atributo con la clase y entre cada par de atributos. En el
algoritmo se selecciona inicialmente el atributo con mayor información mutua con la clase y
luego se van añadiendo atributos al conjunto de los ya seleccionados. El algoritmo termina
cuando se ha seleccionado un número predeterminado de atributos.
CFS (Correlation–based Feature Selection) (M. Hall, 2000) intenta obtener el conjunto de
atributos más correlacionado con la clase y con menos correlación entre sí. Se le puede asociar
con distintas técnicas de búsqueda, siendo Best First la más utilizada.
Capítulo 1: Métodos de selección de rasgos y sus componentes
17
POE-ACC (Mucciarde & Gose, 1971) es un algoritmo que genera un ranking de atributos
ordenados basándose en la suma ponderada de la probabilidad del error (POE) y el coeficiente de
correlación medio (ACC), y como criterio de parada se requiere un número de atributos.
VCC (K.Wang & Sundaresh, 1998), se basa en el Vertical Compactness Criterion, la búsqueda
que emplean es un híbrido entre la búsqueda en profundidad y en anchura basándose en las
definiciones de inconsistencias. El subconjunto que se selecciona es el de menor
dimensionalidad que no supere un umbral fijado por el usuario.
Liu y Setiono (Liu & Setiono, 1996) proponen el algoritmo LVF (Las Vegas Filter), consiste en
generar aleatoriamente conjuntos de atributos e ir seleccionando en cada momento aquel que
tenga el menor número de atributos y cuyo promedio de inconsistencia sea menor que el umbral
fijado por el usuario. Otro parámetro importante a fijar es el número de subconjuntos que se
comprueban. Si este número es muy bajo es improbable obtener el mejor subconjunto, mientras
que si es muy alto se realizarán muchas comprobaciones sobre subconjuntos después de
encontrar el mejor. Estos dos parámetros constituyen una debilidad.
Generalmente LVF al principio proporciona resultados rápidamente, y a continuación los mejora
de forma muy lenta. El algoritmo QBB (Quick Branch and Bound) (Liu & Motoda, 1998)
soluciona este problema combinando los algoritmos LVF y ABB. Comienza utilizando LVF para
generar un conjunto de atributos que se utiliza como conjunto inicial en el algoritmo ABB y que
refina la búsqueda realizada por LVF
Balamurugan y Rajaram (Balamurugan & Rajaram, 2009) proponen un algoritmo basado en el
teorema de Bayes que determina y elimina los atributos dependientes dentro de un conjunto de
datos, reduciendo consecuentemente el conjunto de atributos. La dependencia de dos atributos es
medida por las probabilidades condicionales del atributo clase dado por los valores de los
atributos calculadas por el teorema de Bayes. Define dos atributos dependientes si la diferencia
entre sus probabilidades condicionales satisface un umbral predefinido. El mayor hándicap es
precisamente determinar este umbral.
Gadat y Younes en (Gadat & Younes, 2007) proponen el algoritmo OFW (Optimal Feature
Weighting) que asigna pesos a cada rasgo en relación con su importancia con la clase. El
conjunto total de pesos es obtenido por un algoritmo de gradiente descendiente estocástico y
Capítulo 1: Métodos de selección de rasgos y sus componentes
18
optimizado por un algoritmo de aprendizaje basado en SVM a partir del conjunto de
entrenamiento como ha sido utilizado por Sun y Li en (Sun & Li, 2006). Las comparaciones de
este método se han establecido con otros métodos que utilizan alguna combinación de filtro con
Support Vector Machine (SVM) como F+SVM de Chen y Lin (Y. W. Chen & Lin, 2006),
FS+SVM de Lal y otros (Lal, Chapelle, & Schölkopf, 2006). Este algoritmo es más competitivo
que otros basados puramente en SVM, pero precisamente la incorporación de un clasificador en
el proceso introduce un gasto de tiempo que puede ser evitado si en su lugar se utilizara alguna
componente estadística como información mutua (mutual information).
Una tendencia dirigida a superar las limitaciones de los métodos existentes ha sido implementar
la selección de rasgos usando métodos de búsqueda basados en el uso de Inteligencia Colectiva
(Swarm Intelligence). Al usar metaheurísticas poblacionales, estos métodos tienen la ventaja de
encontrar una mayor cantidad de subconjuntos de rasgos, lo cual es de interés en diversas
aplicaciones. Entre éstos se pueden mencionar los que usan Optimización con Enjambres de
Partículas (Particle Swarm Optimization, PSO) (Firpi & Goodman, 2004; Wang, Yang, Teng,
Xia, & Jensen, 2007) y las técnicas de Optimización con Colonias de Hormigas (Ant Colony
Optimization, ACO) (Al-Ani, 2005; Y. Chen, Miao, & Wang, 2010; Jensen & Shen, 2003, 2005;
Ke, Feng, & Ren, 2008). En este contexto se sitúan los estudios realizados en esta investigación
(Bello, Nowé, Caballero, Gómez, & Vrancx, 2005; Gómez, Bello, Nowé, Puris, & García, 2008)
1.2 Conjuntos aproximados
La Teoría de Conjuntos Aproximados fue introducida por Z. Pawlak en 1982 (Pawlak, 1982,
1991). Se basa en aproximar cualquier concepto, un subconjunto duro del dominio como por
ejemplo, una clase en un problema de clasificación supervisada, por un par de conjuntos exactos,
llamados aproximación inferior y aproximación superior del concepto. Con esta teoría es posible
tratar tanto datos cuantitativos como cualitativos, y no se requiere eliminar las inconsistencias
previas al análisis; respecto a la información de salida puede ser usada para determinar la
relevancia de los atributos, generar las relaciones entre ellos (Choubey, 1996; Chouchoulas &
Shen, 1999; Greco & Inuiguchi, 2003; Grzymala-Busse & Siddhaye, 2004; Miao & Hou, 2003;
Midelfart & Komorowski, 2003; Piñero & Arco, 2003; Sugihara & Tanaka, 2006; Tsumoto,
Capítulo 1: Métodos de selección de rasgos y sus componentes
19
2003; Zhao & Zhang, 2003). La inconsistencia describe una situación en la cual hay dos o más
valores en conflicto para ser asignados a una variable (Parsons, 2006).
Sobre los Conjuntos Aproximados se han manifestado diversos autores, los cuales ven esta teoría
como la mejor herramienta para modelar la incertidumbre cuando esta se manifiesta en forma de
inconsistencia, y como una nueva dirección en el desarrollo de teorías sobre la información
incompleta (Grabowski, 2003; Skowron, 1999; Skowron & Peters, 2003). La principal ventaja
que tiene el análisis de datos basado en RST es que para operar este no requiere parámetros
adicionales además de los datos de entrada (Düntsch & Gediga., 2000). En este epígrafe se
describirán los conceptos fundamentales de los Conjuntos Aproximados para el enfoque clásico.
Principales definiciones de la Teoría de los Conjuntos Aproximados
La filosofía de los conjuntos aproximados se basa en la suposición de que con todo objeto x de
un universo U está asociada una cierta cantidad de información (datos y conocimiento),
expresado por medio de algunos atributos que describen el objeto (J. G. Bazan & Szczuka, 2005;
Komorowski & Pawlak, 1999).
Diversos modelos computacionales operan sobre colecciones de datos. En cada caso esta
colección tiene sus características, sobre todo organizativas, y recibe una denominación
particular. Por ejemplo, para un Gestor de Bases de Datos esa colección es una base de datos,
para una Red Neuronal Artificial es un conjunto de entrenamiento. En el caso de la Teoría de los
Conjuntos Aproximados la estructura de información básica es el Sistema de Información.
Definición 2. Sistema de Información y sistema de decisión.
Sea un conjunto de atributos naaaA ,,, 21 y un conjunto U no vacío llamado universo de
ejemplos (objetos, entidades, situaciones o estados) descritos usando los atributos ia ; al par
AU , se le denomina Sistema de Información3(Komorowski & Pawlak, 1999). Si a cada
elemento de U se le agrega un nuevo atributo d llamado decisión, indicando la decisión tomada
en ese estado o situación, entonces se obtiene un Sistema de decisión }{, dAU , donde
Ad .
3 Esta definición es independiente a la definición de Sistema de Información de Shannon
Capítulo 1: Métodos de selección de rasgos y sus componentes
20
Definición 3. Función de información
A cada atributo ai se le asocia un dominio vi. Se tiene una función VUxAf : ,
},,{ 21 pvvvV tal que ji vaxf , para cada UxAai , llamada función de información
(Komorowski & Pawlak, 1999).
El atributo de decisión d induce una partición del universo U de objetos. Sea el conjunto de
enteros l,1 , ixdUxX i )(: , entonces lXX ,1 es una colección de clases de
equivalencias, llamadas clases de decisión, donde dos objetos pertenecen a la misma clase si
ellos tienen el mismo valor para el atributo decisión.
Se dice que un atributo Aai separa o distingue un objeto x de otro y, y se escribe
yxaSepara i ,, , si y solo si se cumple:
ii ayfaxf ,, (1.1)
La relación de separabilidad se basa en la comparación de los valores de un atributo, para lo cual
se ha usado la igualdad (o desigualdad) estricta. Sin embargo, es posible usar una condición de
comparación menos estricta definida de esta forma:
iii ayfaxfyxaSepara ,,,, (1.2)
Definición 4. Relación de inseparabilidad
A cada subconjunto de atributos B de A AB está asociada una relación binaria de
inseparabilidad denotada por R, la cual es el conjunto de pares de objetos que son inseparables
uno de otros por esa relación (Komorowski & Pawlak, 1999)
BaayfaxfUxUyxR iii ,,:, (1.3)
Una relación de inseparabilidad (indiscernibility relation) que sea definida a partir de formar
subconjuntos de elementos de U que tienen igual valor para un subconjunto de atributos B de A,
AB , es una relación de equivalencia.
Capítulo 1: Métodos de selección de rasgos y sus componentes
21
Los conceptos básicos de la RST son las aproximaciones inferiores y superiores de un
subconjunto UX . Estos conceptos fueron originalmente introducidos con referencia a una
relación de inseparabilidad R. Sea R una relación binaria definida sobre U la cual representa la
inseparabilidad, se dice que R(x) significa el conjunto de objetos los cuales son inseparables de x.
Así, yRxUyxR :)( . En la RST clásica, R es definida como una relación de equivalencia;
es decir, es una relación binaria UUR que es reflexiva, simétrica y transitiva. R induce una
partición de U en clases de equivalencia correspondiente a R(x), xU.
La aproximación de un conjunto UX , usando una relación de inseparabilidad R, ha sido
inducida como un par de conjuntos llamados aproximaciones R-inferior y R-superior de X. Se
considera en esta tesis una definición de aproximaciones más general, la cual maneja cualquier
relación reflexiva R’. Las aproximaciones R’-inferior ( )('* XR ) y R’-superior ( )('* XR ) de X
están definidas respectivamente como se muestra en las expresiones (1.4) y (1.5).
XxRXxXR )(':)('* (1.4)
Xx
xRXR
)(')('* (1.5)
Teniendo en cuenta las expresiones definidas en (1.4) y (1.5), se define la región límite de X para
la relación R’ (J. S. e. a. Deogun, 1995):
XRXRXBN B *
* '' (1.6)
Si el conjunto BNB es vacío entonces el conjunto X es exacto respecto a la relación R’. En caso
contrario, XBN B , el conjunto X es inexacto o aproximado con respecto a R’.
El uso de relaciones de similitud ofrece mayores posibilidades para la construcción de las
aproximaciones; sin embargo, se tiene que pagar por esta mayor flexibilidad, pues es más difícil
desde el punto de vista computacional buscar las aproximaciones relevantes en este espacio
mayor (Pal & Skowron, 1999)
Capítulo 1: Métodos de selección de rasgos y sus componentes
22
Usando las aproximaciones inferior y superior de un concepto X se definen tres regiones para
caracterizar el espacio de aproximación: la región positiva que es la aproximación R’-inferior,
la región límite que es el conjunto BNB y la región negativa (NEG(X)) que es la diferencia entre
el universo y la aproximación R’-superior. Los conjuntos R’*(X) (denotado también como
POS(X)), R’*(X), BNB(X) y NEG(X) son las nociones principales de la Teoría de Conjuntos
Aproximados.
Un aspecto importante en la Teoría de los Conjuntos Aproximados es la reducción de atributos
basada en el concepto de reductos. Un reducto es un conjunto reducido de atributos que preserva
la partición del universo (Komorowski & Pawlak, 1999; Zhong & Dong, 2001). El uso de
reductos en la selección y reducción de atributos ha sido ampliamente estudiado (Y. Caballero &
Bello, 2006; Yaile Caballero, Bello, Arco, Garcia, & Ramentol, 2010; Kohavi & Frasca, 1994;
Komorowski & Pawlak, 1999; Lazo, Shulcloper, & cabrera, 2001; Pal & Skowron, 1999;
Santiesteban & Pons, 2003; Zhong & Dong, 2001).
Medidas de inferencia clásicas de la Teoría de los Conjuntos Aproximados
La Teoría de los Conjuntos Aproximados ofrece algunas medidas para analizar los sistemas de
información (Arco & Bello, 2006; Skowron, 1999; Skowron & Peters, 2003). A continuación se
muestran las dos principales utilizadas en esta tesis. En las expresiones se emplean las
aproximaciones R’-inferior ( )('* XR ) y R’-superior ( )('* XR ) de X, definidas en las expresiones
(1.4) y (1.5) respectivamente.
Precisión de la aproximación. Un conjunto aproximado X puede ser caracterizado
numéricamente por el coeficiente llamado precisión de la aproximación, donde X denota la
cardinalidad de X, X . Observe la expresión (1.7).
)('
)(')(
*
*
XR
XRX (1.7)
Obviamente, 10 x . Si 1)( x X es duro (exacto), si 1)( x , X es aproximado (vago,
inexacto), siempre respecto al conjunto de atributos considerado (Skowron, 1999)
Capítulo 1: Métodos de selección de rasgos y sus componentes
23
Considerando que lXXY ,1 son las clases disjuntas del sistema de decisión, se define la
medida:
Calidad de aproximación de la clasificación. Este coeficiente describe la inexactitud de las
clasificaciones aproximadas:
U
XR
Y
l
i
i 1
* )('
)( (1.8)
La medida calidad de la clasificación expresa la proporción de objetos que pueden estar
correctamente clasificados en el sistema. Si ese coeficiente es igual a 1, entonces el sistema de
decisión es consistente, en otro caso es inconsistente (Skowron, 1999).
1.3 Inteligencia Colectiva aplicada al problema de selección de rasgos
La Inteligencia Colectiva (también llamada inteligencia de enjambre) es un paradigma
inteligente, distribuido e innovador para la solución de problemas de optimización que
originalmente tomó su inspiración en ejemplos biológicos de enjambres. Dentro de esta familia
de algoritmos existen dos bien representativos que han sido aplicados en esta investigación: la
Optimización mediante Enjambres de Partículas (Kennedy & Eberhart, 1995) incorpora el
comportamiento de enjambre observado en bandas de pájaros, cardúmenes de peces o enjambres
de abejas, de las que surgió la idea. Y la Optimización mediante Colonias de Hormigas (M.
Dorigo, Birattari, & Stutzle, 2006; Marco Dorigo & Stutzle, 2004) tiene que ver con sistemas
inteligentes artificiales, que son inspirados a partir de observar el comportamiento de las
hormigas reales en la búsqueda de comida, los cuales son usados para resolver problemas de
optimización discretos. Son métodos poblacionales que realizan un proceso constructivo y
estocástico guiado por rastros de feromona4 que va depositando cada hormiga, dando una medida
de cuán deseado ha sido un determinado camino, y a través de una función de visibilidad que
evalúa la calidad del desplazamiento. Es un ejemplo clásico de comunicación indirecta, que
4 Sustancia química olorosa que depositan las hormigas en su recorrido. La intensidad de esta sustancia disminuye a
través de un proceso de evaporación que ocurre en el tiempo de manera constante.
Capítulo 1: Métodos de selección de rasgos y sus componentes
24
ocurre cuando un individuo altera el medio en que se desarrolla y los otros son capaces de captar
estos cambios siguiendo así la idea original sobre la que están basados los algoritmos de
inteligencia de enjambre.
Estudios recientes (Abraham, Grosan, & Ramos, 2006; Parpinelli, Lopes, & Freitas, 2002)
sugieren que las técnicas de minería de datos y de inteligencia colectiva pueden ser usadas
conjuntas para diversos problemas reales de minería de datos, especialmente cuando otros
métodos podrían ser muy costosos o difíciles de implementar.
Optimización basada en Colonias de Hormigas
Los algoritmos ACO son procesos iterativos. En cada iteración se "lanza" una colonia de m
hormigas y cada una de las hormigas de la colonia construye una solución al problema. Las
hormigas construyen las soluciones de manera probabilística, guiándose por un rastro de
feromona artificial y por una información calculada a priori de manera heurística. Éstos
algoritmos son esencialmente métodos constructivos: en cada iteración del algoritmo, cada
hormiga construye una solución al problema recorriendo un grafo. Cada arista del grafo, que
representa los posibles caminos que la hormiga puede tomar, tiene asociados dos tipos de
información que guían el movimiento de la hormiga:
Información heurística, mide la preferencia heurística de moverse desde el nodo i
hasta el nodo j; es decir, la preferencia a recorrer la arista aij. Se denota por ηij. Las
hormigas no modifican esta información durante la ejecución del algoritmo.
Información de los rastros artificiales de feromona, mide la “deseabilidad aprendida”
del movimiento de i a j. Imita de forma numérica a la feromona real que depositan las
hormigas naturales. Esta información se modifica durante la ejecución del algoritmo
dependiendo de las soluciones encontradas por las hormigas. Se denota por τij.
El modo de operación básico de un algoritmo ACO (M. Dorigo, et al., 2006; Marco Dorigo &
Stutzle, 2004) es como sigue: las m hormigas (artificiales) de la colonia se mueven,
concurrentemente y de manera asíncrona, a través de los estados adyacentes del problema (que
puede representarse en forma de grafo con ponderaciones o sin ellas). Este movimiento se realiza
siguiendo una regla de transición que está basada en la información local disponible en las
Capítulo 1: Métodos de selección de rasgos y sus componentes
25
componentes (nodos). Esta información local incluye la información heurística y memorística
(rastros de feromona) para guiar la búsqueda. Las hormigas construyen incrementalmente
soluciones al moverse por el grafo de construcción. Opcionalmente, las hormigas pueden
depositar feromona cada vez que crucen un arco (conexión) mientras que construyen la solución
(actualización en línea paso a paso de los rastros de feromona). Una vez que cada hormiga ha
generado una solución, ésta se evalúa y el agente puede depositar una cantidad de feromona en
dependencia de la calidad de su solución (actualización en línea de los rastros de feromona).
Esta información guiará la búsqueda de las otras hormigas de la colonia en el futuro. Además, el
modo de operación genérico de un algoritmo ACO incluye dos procedimientos adicionales, la
evaporación de los rastros de feromona y las acciones del demonio. La evaporación de feromona
la lleva a cabo el entorno y se usa como un mecanismo que evita el estancamiento en la búsqueda
y permite que las hormigas busquen y exploren nuevas regiones del espacio. Las acciones del
demonio constituyen una funcionalidad opcional (que no tiene un contrapunto natural) para
implementar tareas desde una perspectiva global que no pueden llevar a cabo las hormigas por la
perspectiva local que ofrecen. Ejemplos son: observar la calidad de todas las soluciones
generadas y depositar una nueva cantidad de feromona adicional sólo en las componentes
asociadas a algunas soluciones, o aplicar un procedimiento de búsqueda local a las soluciones
generadas por las hormigas antes de actualizar los rastros de feromona. En ambos casos el
demonio reemplaza la actualización en línea a posteriori de feromona y el proceso pasa a
llamarse actualización fuera de línea de rastros de feromona.
En ACO el significado de los rastros de feromona y la función heurística o de visibilidad
dependen totalmente del problema a resolver. En el caso específico de los rastros de feromona,
cuando se está en presencia de un problema de secuenciación (Viajante de Comercio (M. Dorigo
& L.M. Gambardella, 1997; M. Dorigo & L. M. Gambardella, 1997), Asignación Cuadrática
(Gambardella, Taillard, & Dorigo, 1999), entre otros), donde el orden en que aparecen las
componentes en una solución influye en la calidad de ésta, los rastros de feromona son asociados
a los arcos del grafo, con el objetivo de premiar las buenas secuencias de componentes5. Por otra
parte, en problemas de asignación (Selección de Rasgos (Bello, et al., 2005), Partición de
5 Mide la deseabilidad de la colonia por una determinada secuencia de nodos.
Capítulo 1: Métodos de selección de rasgos y sus componentes
26
Conjuntos (Crawford & Castro, 2006), entre otros) donde los cambios de posición entre
componentes de una solución no influyen en la calidad de la misma, los rastros de feromona son
asociados a los nodos del grafo6.
La estructura general (Marco Dorigo & Stutzle, 2004) de ACO es como sigue:
Procedimiento metaheurística ACO;
Actividades Programadas
Construir Soluciones de las Hormigas
Actualizar Feromonas
Evaporación de la Feromona
Acciones del Demonio (opcional)
Fin de las Actividades Programadas
Fin del Procedimiento
Figura 1 Procedimiento general de ACO
Este procedimiento se anida en el siguiente procedimiento iterativo:
Paso1: Inicializar los valores de feromona
iteracionActual=1
Paso2: Repetir
Procedimiento metaheurística ACO
iteracionActual = iteracionActual +1
Hasta que: criterio de parada
Figura 2 Estructura genérica de ACO
Para los métodos de ACO existen distintos criterios de parada (M. Dorigo & Stutzle, 2003), en
esta investigación sólo se tomó como criterio de parada cuando se alcanza una cantidad máxima
de iteraciones o ciclos.
6 Mide la deseabilidad de la colonia por un estado en específico, no interesa de donde fue alcanzado.
Capítulo 1: Métodos de selección de rasgos y sus componentes
27
Observando las aplicaciones actuales de ACO, se pueden identificar algunas directivas sobre
cómo solucionar problemas utilizando esta metaheurística (M. Dorigo, et al., 2006). Estas
directivas se pueden resumir en las seis tareas de diseño que se enumeran a continuación:
1. Representar el problema como un conjunto de componentes (nodos) y transiciones
(aristas) a través de un grafo que será recorrido por las hormigas para construir
soluciones.
2. Definir de manera apropiada en base a las características del problema, el significado de
los rastros de feromona .
3. Definir de manera apropiada la preferencia heurística o función de visibilidad
asociada a cada componente o transición.
4. Si es posible, implementar una búsqueda local eficiente para mejorar las soluciones
obtenidas por ACO.
5. Escoger un algoritmo de ACO específico y aplicarlo al problema que hay que solucionar
teniendo en cuenta las características propias de cada uno de estos algoritmos.
6. Refinar los parámetros del algoritmo de ACO seleccionado.
Dentro de los algoritmos de ACO las diferencias fundamentales radican en la regla de transición
que utilizan para la construcción de las soluciones y en el tratamiento que le dan a los rastros de
feromona. Debido a esto, aparecen en la literatura distintos algoritmos ACO.
La familia de algoritmos basados en colonia de hormigas.
Entre los algoritmos ACO disponibles para problemas de optimización combinatoria (M. Dorigo
& Blum, 2005) se encuentran: el Sistema de Hormigas (Ant System, AS) (M. Dorigo, Maniezzo,
& Colorni, 1996), el Sistema de Colonia de Hormigas (Ant Colony System, ACS) (M. Dorigo &
L. M. Gambardella, 1997), el Sistema de Hormigas Máximo-Mínimo (Max-Min Ant System,
MMAS) (T. Stützle & Hoos, 2000), entre otros. ACO comienza a tener la madurez tecnológica
adecuada para su utilización en problemas reales, como puede apreciarse en la publicación del
libro (Marco Dorigo & Stutzle, 2004).
Capítulo 1: Métodos de selección de rasgos y sus componentes
28
A continuación se presenta una pequeña descripción de los algoritmos Sistema de Hormigas y,
Sistema de Colonia de Hormigas debido a que fueron seleccionados para llevar a cabo este
trabajo.
El Sistema de Hormigas, desarrollado por Dorigo en su tesis doctoral en 1992 (Marcos Dorigo,
1992), fue el primer algoritmo de ACO. Su versión actual (Ant Cycle) apareció conjuntamente
con otras variantes de este, como el Sistema de Hormigas Densidad (Ant Density) y Sistema de
Hormigas Cantidad (Ant Quantity). El AS se caracteriza por el hecho de que, la actualización de
feromona se realiza una vez que todas las hormigas han completado sus soluciones, y se lleva a
cabo como sigue: todos los rastros de feromona se reducen en un factor constante,
implementándose de esta manera la evaporación de feromona según la ecuación (1.9)
1,0,1 ijij tt (1.9)
donde ρ se conoce como constante de evaporación y es la encargada de reducir los rastros de
feromona para evitar el estancamiento de las soluciones y tij la cantidad de feromona asociada al
arco aij.
A continuación, cada hormiga de la colonia deposita una cantidad de feromona en función de la
calidad de su solución, según la ecuación (1.10),
k
ij
k
ijij Sattt (1.10)
donde ))(( kk SCft , representa la cantidad de feromona a depositar por la hormiga k en cada
arco ija de su solución encontrada ( kS ). Este valor depende de la calidad de la solución )( kSC .
Las soluciones en el AS se construyen como sigue. En cada paso de construcción, una hormiga k
escoge ir al siguiente nodo con una probabilidad que se calcula como:
Capítulo 1: Métodos de selección de rasgos y sus componentes
29
k
i
Nj
ijij
ijijk
ij Njsip
ki
(1.11)
donde k
iN es el vecindario alcanzable por la hormiga k cuando se encuentra en el nodo i. Los
parámetros y beta controlan el proceso de búsqueda. Para 0 se tiene una búsqueda
heurística estocástica clásica, mientras que para 0 sólo el valor de la feromona tiene efecto.
Un valor de 1 lleva a una rápida situación de convergencia (M. Dorigo, Caro, &
Gambardella, 1999). El vector k
ijP contiene las probabilidades de movimiento calculadas para
los nodos de la vecindad ( k
iN ) de la hormiga k. El valor ij representa el elemento (i, j) en la
matriz de feromona y ij se denomina función de visibilidad o función heurística y mide la
calidad de un nodo j a partir del nodo i.
El Sistema de Colonia de Hormigas, es uno de los primeros sucesores del AS que introduce
tres modificaciones importantes con respecto a dicho algoritmo ACO:
1. Utiliza una regla de transición distinta y más agresiva, denominada regla proporcional
pseudo-aleatoria. Sea k una hormiga situada en el nodo r, 1,00 q un parámetro y q un
valor aleatorio en el mismo intervalo, el siguiente nodo j se elige como:
0 simax qqj ijijNj ki
(1.12)
En caso contrario se utiliza la regla probabilística del AS (ecuación (1.11)).
Como puede observarse, la regla tiene una doble intención: cuando 0qq , utiliza en gran
medida el conocimiento disponible (explotar), eligiendo la mejor opción con respecto a la
información heurística y los rastros de feromona. Sin embargo, si 0qq se aplica una
exploración controlada, tal como se hace en el AS.
2. Las hormigas aplican una actualización en línea paso a paso de los rastros de feromona que
favorece la generación de soluciones distintas a las encontradas.
Capítulo 1: Métodos de selección de rasgos y sus componentes
30
Cada vez que una hormiga viaja por una arista ija , aplica la regla:
)0()1( ttt ijij (1.13)
donde ]1,0( es un segundo parámetro de decremento de feromona. Como puede verse, la
regla de actualización en línea paso a paso incluye tanto la evaporación de feromona como
la actualización de la misma.
3. Se realiza una actualización fuera de línea de los rastros de feromona (acción del demonio),
donde el ACS sólo considera una hormiga concreta, la que generó la mejor solución global,
Smejor-global7.
La actualización de la feromona se lleva a cabo evaporando primero estos rastros en todas las
conexiones utilizadas por la mejor hormiga global (es importante recalcar que, en el ACS, la
evaporación de la feromona sólo se aplica a las conexiones de la solución, que es también la
usada para depositar feromona) tal como sigue:
globalmejorijijij Satt )1( (1.14)
A continuación se deposita feromona a los arcos que pertenecen a la mejor solución
encontrada hasta el momento usando la regla:
globalmejorijijij Sattt (1.15)
donde ))(( globalmejorSCft , es decir la cantidad de feromona está en dependencia de la
calidad de la mejor solución encontrada hasta el momento )( globalmejorSC .
En general, las soluciones obtenidas con la metaheurística ACO suelen ser de una calidad
moderada. Esto se debe a que estos algoritmos se inclinan hacia una mayor exploración del
espacio de búsqueda, por lo que es razonable aplicarle diversos algoritmos de búsqueda local
7Aunque en algunos trabajos iniciales se consideraba también una actualización basada en la mejor hormiga de la
iteración, en ACS casi siempre se aplica la actualización basada en la mejor global.
Capítulo 1: Métodos de selección de rasgos y sus componentes
31
(Crawford & Castro, 2006; M. Dorigo, et al., 2006; Heinonen & Pettersson, 2007; Huang &
Liao, 2008) o alguna estrategia para agregarle un mayor grado de explotación de las soluciones
encontradas (Naimi & Taherinejad, 2009; Wong & See, 2009; Wu, Zhao, Ren, & Quan, 2009).
ACO Multicolonias
Una dirección en las investigaciones de ACO es dividir la población de hormigas en varias
colonias. Estas colonias trabajan juntas para resolver colectivamente problemas de optimización.
Este enfoque ofrece buenas oportunidades para explorar grandes espacios de búsqueda
(Aljanaby, Ku-Mahamud, & Norwawi, 2010; Jong & Wiering, 2001).
Hay muy pocas variantes de ACO multicolonias propuestas (Melo, Pereira, & Costa, 2010).
Varias de estas son especialmente implementadas para paralelizar ACO (Marco Dorigo &
Stutzle, 2004; Ellabib, Calamai, & Basir, 2007; Janson, Merkle, & Middendorf, 2005;
Middendorf, Reischle, & Schmeck, 2002); o para resolver problemas de optimización multi-
objetivo (Angus & Woodward, 2009; García-Martínez, Cordón, & Herrera, 2007). Dos ejemplos
recientes de estas variantes son los siguientes trabajos.
Middendorf, Reischle y Schmeck (Middendorf, et al., 2002) propusieron la idea de usar varias
colonias de hormigas paralelizadas sobre varios procesadores. Las colonias tienen que
intercambiar información después de completar un cierto número de iteraciones.
Ortega y otros autores (Ortega, Oliva, Ferland, & Cepeda, 2009) obtienen un sistema para el
problema de Rutas para Vehículos con Ventanas de Tiempo y Programación de la Carga con un
Ant Colony System multi-colonias que minimiza dos funciones objetivos: el número de
vehículos y la longitud total del recorrido.
1.4 Consideraciones parciales
De la revisión bibliográfica realizada sobre selección de rasgos relevantes se concluye que estos
métodos no satisfacen completamente las necesidades sobre el pre-procesamiento de los datos,
concretamente en la reducción de dimensionalidad. Se ha mostrado que no hay métodos que se
ajusten a toda clase de problemas; por tanto, resulta sugerente la combinación de nuevos
Capítulo 1: Métodos de selección de rasgos y sus componentes
32
enfoques. A la vez, la revisión de algoritmos de construcción de reductos existentes muestra que
la mayoría de estos articulan estrategias de búsquedas y heurísticas de selección de atributos, lo
que conduce a una tendencia de introducir nuevos algoritmos constantemente.
El uso de información suministrada por el usuario es esencial para algunos algoritmos existentes
en la literatura y esto es un inconveniente significativo. Ciertos métodos de selección de rasgos
requieren que se especifique de antemano los niveles de ruido permisibles. Algunos métodos
simplemente realizan una ponderación (pesado) de los rasgos y dejan al usuario seleccionar su
propio conjunto. En ocasiones esta elección se deja bajo el criterio de un umbral o por el número
de rasgos a ser seleccionados. Todas estas variantes requieren que el usuario tome una decisión
basado en su (posiblemente deficiente) propio criterio.
La calidad de un método de selección de rasgo puede medirse por varios indicadores, como la
calidad de la clasificación en los envolventes, u otros como la longitud del subconjunto más
corto encontrado, e incluso la cantidad de subconjuntos encontrados cuando el método
proporciona una variedad de soluciones.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
33
2 Inteligencia colectiva aplicada a la selección de rasgos
2.1 Solución al problema de selección de rasgos. Algoritmo ACO-RST-FSP
Como se analizó antes el problema de selección de rasgos es un ejemplo de un problema de
optimización discreto difícil, por eso resulta conveniente proponer algoritmos basados en
metaheurísticas. El método que se propone en esta investigación se clasifica como “filtro”,
utiliza ACO como procedimiento de generación de subconjuntos y como función de evaluación
de la calidad de los subconjuntos la medida calidad de la clasificación de la Teoría de los
Conjuntos Aproximados. Durante la ejecución del algoritmo cada hormiga construye un
subconjunto de rasgos hasta que este alcance un valor de la calidad de la clasificación igual al
calculado para el conjunto de todos los rasgos, es decir, hasta formar un reducto.
Cuando se usa ACO para resolver el problema de selección de rasgos la representación del grafo
es ligeramente diferente al TSP. Este problema puede ser modelado de la siguiente forma. Sea
nfaaaA ,...,, 21 un conjunto de nf rasgos. Este conjunto puede ser representado como un grafo
bidireccional fuertemente conexo en el cual los nodos simbolizan rasgos. Los valores de la
feromona i están asociados a los nodos ia . Esta es una diferencia entre nuestro enfoque y el
propuesto por Jensen and Shen (Jensen & Shen, 2003). En la propuesta de Jensen y Shen la
feromona es asociada con los arcos lo cual es común en ACO. La cantidad de feromona en el
arco ji aa está en función del grado de dependencia del atributo ja sobre ia . En el enfoque
planteado en esta tesis la feromona se asocia a los nodos. La cantidad de feromona está en
función de la dependencia del rasgo asociado a este nodo en correspondencia con todos los otros
rasgos. Como resultado la feromona asociada al nodo ia representa la contribución absoluta de
este rasgo a un subconjunto, en lugar de la contribución de ia dado el hecho de que ja ha sido el
rasgo previo incluido en el subconjunto. Jensen en su tesis de doctorado (Jensen, 2005) cambió
el enfoque y asoció la feromona a los nodos.
Al comenzar el algoritmo, en el primer paso, cada hormiga k se asigna a un nodo, luego ésta
puede moverse a cualquier nodo en el grafo ( ik aB , donde kB es el subconjunto que la
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
34
hormiga k construye). Las hormigas realizan una selección hacia adelante (forward selection) en
la cual cada hormiga k expande su subconjunto kB paso a paso adicionando nuevos rasgos; para
realizar esto, cada hormiga k busca todos los rasgos en kBA (donde A es el conjunto de
rasgos) y selecciona el próximo rasgo entre éstos para incluirlo en kB de acuerdo con la regla del
modelo ACO en uso. Ésta es la regla proporcional seudoaleatoria en ACS. La calidad de la
aproximación de la clasificación, una medida de RST, dada por la expresión (1.8), se utiliza
como función heurística por la metaheurística ACO. Este valor también se usa para determinar si
el subconjunto kB es un reducto.
El algoritmo propuesto, nombrado ACO-RST-FSP, está basado en la variante "Ant Colony
System". A continuación se establecen varios aspectos del mismo:
a) Modo de funcionamiento de las hormigas.
En esta solución cada hormiga construye un subconjunto de rasgos paso a paso. Estos
subconjuntos son denotados por kB , donde k denota la hormiga k. En el paso inicial de cada
ciclo las hormigas se asocian a nodos de acuerdo a la regla descrita en el siguiente punto b). En
cada paso siguiente, las hormigas seleccionan otro rasgo para incluir en sus subconjuntos. Cada
nodo ia tiene asociado un valor de feromona i .
b) Distribución (posicionamiento) inicial de las hormigas.
La distribución de hormigas en cada ciclo depende de la relación entre el número de hormigas
(m) y la cantidad de rasgos (nf). En (Bello, et al., 2005) se propone el siguiente conjunto de
reglas para establecer esta relación:
i) Si m<nf, realizar una distribución inicial aleatoria de las hormigas.
ii) Si m=nf, cada hormiga es asociada a cada nodo (rasgo).
iii) Si m>nf, las primeras nf hormigas son distribuidas según (ii), y el resto según (i).
c) Regla proporcional seudoaleatoria.
El algoritmo ACO usa como función heurística ( ) para evaluar un subconjunto B la calidad de
aproximación de la clasificación ( YB B ), buscando subconjuntos B tales que
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
35
YY AB . La siguiente regla proporcional pseudoaleatoria usa este valor y el rastro de
feromona en la forma:
casootroenI
qqsiYi i
k aBi 0max
(2.1)
donde I es seleccionado según la expresión (2.2):
k
j
BAaaBj
aBj
k
j
j
k
k BAaifY
Y
Baif
aBp
kj
jk
jk
*
*
0
, (2.2)
d) Valor inicial del rastro de feromona.
Para calcular el valor inicial de feromona se considera la alternativa de asignar un valor aleatorio
0i , i=1,…,nf
e) Criterio de parada de las hormigas.
Una hormiga alcanza el criterio de parada cuando termina su actividad en un ciclo. Cada hormiga
adiciona un rasgo cada vez a su subconjunto parcial kB hasta alcanzar la condición
YY AB .
f) Criterio de parada del algoritmo.
Para los métodos de ACO existen distintos criterios de parada (M. Dorigo & Stutzle, 2003). El
proceso de buscar subconjuntos B es una secuencia de ciclos (NC=1, 2, …NCmáx). En cada ciclo
todas las hormigas construyen su conjunto B. El proceso termina cuando NC = NCmáx.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
36
Algoritmo ACO-RST-FSP:
Entrada: Conjunto de datos que describen mediante rasgos distintos objetos e incluye un
atributo clase.
Salida: Colección de reductos.
P0:
PSC Falso
NC 1
Calcular 0i i=1,…,nf (valor inicial del rastro de feromona)
Repetir
P1: Estado inicial para cada ciclo.
Cada hormiga k es asociada con un atributo ia , k=1,…,m, y ik aB
de acuerdo con las reglas establecidas en 2.1 b).
FalsoASCk , k=1,…,m
P2: Repetir
para k=1,…,m hacer
si FalsoASCk entonces
Seleccionar el nuevo rasgo *
ia para adicionar a kB
*
i
kk aBB (de acuerdo la regla proporcional pseudoaleatoria
dada en (2.1), donde *
ia fue el último rasgo adicionado)
01 iii (actualización local de feromona)
Actualizar ASCk criterio de parada de la hormiga k.
fin_si
fin_para
Hasta que verdaderoASCk para todas las hormigas.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
37
P3: Después que todas las hormigas han terminado:
Seleccionar la mejor solución kB , y para todo k
i Ba hacer
Yk
Bii 1
1 NCNC
Actualizar PSC
Hasta que PSC = verdadero
Considerando que el esfuerzo computacional para calcular la aproximación inferior o superior es
2lnfO , donde l es el número de atributos según (D Bell & Guan, 1998; J. S. Deogun, 1998),
se estima que la complejidad de este algoritmo como 22 nnfmncO donde n es la cantidad de
objetos en el sistema de información; cuando la cantidad de hormigas es igual al número de
rasgos la complejidad es 23 nnfncO .
Evaluación del algoritmo
El objetivo de este estudio experimental es evaluar el algoritmo y determinar reglas para
establecer los parámetros. Se ha evaluado el funcionamiento del algoritmo con diferentes
combinaciones de parámetros y se ha comparado según los resultados en cuanto a longitud del
reducto más corto, cuántas veces se encontró el reducto más corto, cantidad de reductos
encontrados y la longitud promedio de los mismos; definiendo la longitud de un reducto como el
número de rasgos incluidos. En la validación del algoritmo a estos resultados se les ha
denominado indicadores de salida.
Ajuste de parámetros.
Se estudiaron los parámetros que intervienen en el algoritmo ACO-RST-FSP con influencia de
manera determinante en los indicadores que se obtienen de aplicar dicho algoritmo. Estos
resultan de gran importancia cuando se desea obtener algún valor específico o resultados óptimos
en los indicadores de salida, pues de la forma de variar los disímiles parámetros se derivan los
resultados en éstos. Según las conclusiones que se arribe del estudio se pueden hacer sugerencias
al usuario sobre los parámetros que se deben utilizar para obtener los resultados esperados. Un
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
38
listado de los parámetros fundamentales de este algoritmo, con una breve descripción de su
significado se puede observar en la Tabla 1.
Tabla 1 Parámetros del algoritmo ACO-RST-FSP.
Parámetros Breve descripción
]1,0( parámetro de decremento de feromona, en la regla de
actualización en línea paso a paso
constante de evaporación, es la encargada de reducir
los rastros de feromona
valor inicial de la feromona
k número de hormigas
NC número de ciclos
controla el proceso de búsqueda basado en la fuerza
del rastro de feromonas.
controlan el proceso de búsqueda basado en la fuerza
de la heurística
0q
determina el carácter del algoritmo, exploratorio o de
explotación.
En particular se estudia el comportamiento de los parámetros y 0q debido a su influencia en
el balance entre exploración y explotación, como se ha mostrado en el estudio del
comportamiento del algoritmo en otros problemas (Amir, Badr, & Farag, 2007; Anghinolfi,
Boccalatte, Paolucci, & Vecchiola, 2008; Melo, et al., 2010), además en una revisión completa
del estudio de los parámetros de ACO (Thomas Stützle, et al., 2010). Si el algoritmo sigue una
política de mayor exploración, dado por 0q , se esperan buenos resultados en los indicadores
referidos a cantidades de reductos encontrados, pues el algoritmo hace énfasis en encontrar
mayor cantidad de soluciones lo que se traduce en más reductos, mientras que el parámetro
influye sobre la heurística del algoritmo, por lo que esto debe influir mayormente en el indicador
referente a la longitud de los reductos, que es un indicador de calidad de la solución.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
39
A partir de esta decisión se realizaron experimentos variando el valor de los parámetros y 0q .
Para éstos se escogen los valores 1 y 5 para , y 0.3 y 0.9 para 0q . El rango de posibles valores
que pueden tomar estos parámetros es amplio; luego, se han tomado estos valores para analizar la
influencia de la heurística cuando no se resalta su valor y otro que le proporcionará más
importancia. Para determinar el carácter del algoritmo se escogen esos valores pues el parámetro
oscila en el rango de 0 a 1, durante el funcionamiento del algoritmo se escogen números al azar
en este mismo rango y se comparan con el valor fijado para 0q , para valores bajos se establece
un carácter exploratorio y para valores altos de explotación; siguiendo estas ideas se fijan valores
cercanos a los extremos del intervalo. En todos los caso se fijó el valor de alpha ( 1 ) y para
los valores iniciales de 0i (feromona) se asignaron valores aleatorios. Los algoritmos con las
combinaciones de valores para los parámetros son aplicados a conjuntos de datos (ver Anexo 1
para un resumen de las características de estos) del “Repositorio UCI” (Blake & Merz, 1998),
cada experimento se repite 10 veces (debido al fuerte carácter probabilístico del algoritmo), de
estos valores se calcula la mediana (es un estadístico más potente que el promedio) y el resultado
de las medianas se utiliza en las comparaciones.
En (Bello, et al., 2005) se proponen las siguientes reglas para determinar el número de hormigas
como una función de la cantidad de rasgos nffk . En este caso se usó la clasificación del
problema de selección de rasgos dada en (Kudo & Sklansky, 2000), donde se clasifican en tres
categorías: pequeña escala si 19,0nf , mediana escala si 49,20nf y escala grande si
50nf .
R1: Si 19 ,0nf entonces nfk
R2: Si 49,20nf entonces
[Si 24666.0 nf entonces 24k , sino nfRoundk 66.0 ]
R3: Si 50nf entonces
[Si 335.0 nf entonces 33k , sino nfRoundk 5.0 ]
donde xRound denota el entero más cercano a x.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
40
La Tabla 2 presenta el comportamiento del algoritmo para diferentes conjuntos de datos del
repositorio, en esta se describen: los nombres de los conjuntos de datos con los que se realizó el
experimento, así como el número de rasgos de cada objeto, el número de hormigas que se
utilizaron en cada uno de los conjuntos y los resultados para las variantes de los parámetros del
algoritmo. La simbología n1(n2) denota n1 reductos con n2 rasgos (sólo se muestra información
sobre reductos de longitud mínima), TR es la cantidad resultante de reductos y TPR la longitud
promedio de los reductos obtenidos.
Tabla 2 Comparación del algoritmo con diferentes valores de parámetros para conjuntos de datos
del “Repositorio UCI”.
Data base na k ACO-RST-FSP
(β=5, q0=0.9)
ACO-RST-FSP
(β=5, q0=0.3)
ACO-RST-FSP
(β=1, q0=0.3)
ACO-RST-FSP
(β=1, q0=0.9)
Breast
Cancer Jenk 9 9
5(4)
TR=10.5
TPR=4.41
6(4)
TR=17
TPR=4.36
6(4)
TR=18.5
TPR=4.29
6(4)
TR=14
TPR=4.44
Breast-w 8 8
8(5)
TR= 9
TPR= 5.05
9(5)
TR= 11
TPR= 5.00
9(5)
TR= 12
TPR= 5.00
9(5)
TR= 10
TPR= 5.00
Dermatology 34 24
8.5(9)
TR= 184.5
TPR=10.63
30.5(10)
TR= 352.5
TPR=11.20
4(9)
TR= 343.5
TPR=11.56
6(9)
TR= 167
TPR=10.98
HeartJen 13 13
1(6)
TR= 11.5
TPR= 7
1(6)
TR= 16.5
TPR= 6.99
1(6)
TR= 19.5
TPR= 7.08
1(6)
TR= 12
TPR= 6.96
LedJen 24 24
1(5)
TR= 1.5
TPR= 5
1(5)
TR= 6
TPR= 5
1(5)
TR= 13.5
TPR= 5.5
1(5)
TR= 2.5
TPR= 5
LungJen 56 33
12(4)
TR= 308.5
TPR= 5.88
11.5(4)
TR= 629,5
TPR= 5.52
7.5(4)
TR= 604.5
TPR= 5.79
13.5(4)
TR= 323.5
TPR= 5.84
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
41
Ionosphere 34 24
15(7)
TR=129
TPR=8.70
9(7)
TR=355
TPR=10.66
6(7)
TR=342
TPR=11.39
19(7)
TR=160
TPR=8.59
Mushroom 21 24
3(4)
TR=54
TPR=5.16
3(4)
TR=128
TPR=5.97
2(4)
TR=117
TPR=6.08
3(4)
TR=51
TPR=5.26
Con los resultados mostrados en la tabla anterior se realiza un análisis estadístico. De acuerdo
con las peculiaridades que presentan las poblaciones se utilizan pruebas de comparaciones no
paramétricas, pues las muestras no siguen una distribución normal y están relacionadas. Primero
se aplica un test de Iman-Davemport como una variante del test de Friedman, en caso de que
existan diferencias significativas en el grupo se utilizará una variante del test de Holm para
comparaciones par a par (García & Herrera, 2008).
Para llegar a conclusiones de la relación existente entre los parámetros y los indicadores de
salida, se llevó a cabo una comparación entre los datos de cada una de las muestras para los
distintos indicadores. En esta comparación primero se verifica si existe significación entre las
variables y luego se examinan dos tablas. En una se analizan los rangos de las poblaciones; estos
rangos destacan el comportamiento de las muestras, resultando con mejor comportamiento la que
menor rango tenga. En la otra se contrasta el resultado del test de Holm entre todas las muestras
par-a-par para determinar entre cuales existen diferencias significativas. En el caso que no exista
significación entre las muestras la primera de las tablas puede mostrar tendencias a seguir por las
poblaciones con respecto al indicador de salida correspondiente. Al realizar el análisis estadístico
se obtuvieron los resultados.
El indicador que describe el total de reductos calculados presenta un valor de Iman-Davenport
con el cual se obtiene 3.9099E-8 como valor ajustado y como este es menor que 0.05 (margen de
error permitido), se puede decir que existen diferencias significativas en grupo de control. En la
Tabla 3 se muestran los valores de los promedios de los rangos de las poblaciones.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
42
Tabla 3 Promedio de rangos de las muestras
Algoritmos Rangos
Total de reductos calculados (B=5 0q =0.9) 3.75
Total de reductos calculados (B=1 0q =0.9) 3.25
Total de reductos calculados (B=1 0q =0.3) 1.5
Total de reductos calculados (B=5 0q =0.3) 1.5
En la Tabla 4 se muestra la comparación entre los algoritmos de las poblaciones dos a dos,
utilizando la variante del test de Holm, se puede determinar si se acepta o rechaza la hipótesis de
igualdad entre las muestras (si el valor p es menor o igual que el margen de error permitido, dado
por el test de Holm, la hipótesis es rechazada, en caso contrario se acepta)
Tabla 4 Resultados del test de Holm
i Algoritmos valor p Holm
1 Total de reductos calculados (B=5 0q =0.9) vs.
Total de reductos calculados (B=1 0q =0.3)
4.9088E-4 0.0083
2 Total de reductos calculados (B=5 0q =0.9) vs.
Total de reductos calculados (B=5 0q =0.3)
4.9088E-4 0.01
3 Total de reductos calculados (B=1 0q =0.9) vs.
Total de reductos calculados (B=1 0q =0.3)
0.0067 0.0125
4 Total de reductos calculados (B=1 0q =0.9) vs.
Total de reductos calculados (B=5 0q =0.3)
0.0067 0.0167
5 Total de reductos calculados (B=5 0q =0.9) vs.
Total de reductos calculados (B=1 0q =0.9)
0.4386 0.025
6 Total de reductos calculados (B=1 0q =0.3) vs.
Total de reductos calculados (B=5 0q =0.3)
1.0 0.05
Con las combinaciones de valores para los parámetros 1 , 3.00 q y 5 , 3,00 q , se
encuentra una diferencia significativa entre el total de los reductos encontrados entre estos
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
43
valores y los demás, lo que hace notar que si el valor de 0q es bajo, se encuentran más reductos,
sin tener en cuenta el valor de , este comportamiento es atribuido al carácter exploratorio de
ACO cuando 0q es bajo, con lo cual se encuentran mayor diversidad en las soluciones
encontradas.
El indicador que describe la longitud de reductos más cortos obtiene de la aplicación del tests de
Iman-Davenport con valores de 0.973, lo que indica que no existe diferencia significativa entre
las muestras; por tanto sólo se puede plantear que estas van a seguir una tendencia descrita según
los resultados presentados en la Tabla 5. En esta tabla se muestran los valores de los promedios
de los rangos de las poblaciones.
Tabla 5 Promedio de rangos de las muestras
Algoritmos Rangos
Total de reductos calculados (B=5 0q =0.9) 2.4375
Total de reductos calculados (B=1 0q =0.9) 2.4375
Total de reductos calculados (B=1 0q =0.3) 2.4375
Total de reductos calculados (B=5 0q =0.3) 2.6875
Con esta combinación de parámetros el algoritmo tiende a encontrar reductos más pequeños
cuando el valor de 0q es alto o el de es bajo; es decir, cuando el algoritmo trabaja más
intensificando la explotación de manera que se considera más la experiencia acumulada por las
hormigas.
El indicador que describe la cantidad de reductos más cortos obtiene de la aplicación del test de
Iman-Davenport el valor 0.34292, lo que indica que no existe diferencia significativa entre las
muestras por lo que estas van a seguir una tendencia descrita en la Tabla 6. En esta tabla se
muestran los valores de los promedios de los rangos de las poblaciones.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
44
Tabla 6 Promedio de rangos de los algoritmos.
Algoritmos Rangos
Total de reductos calculados (B=5 0q =0.9) 2.625
Total de reductos calculados (B=1 0q =0.9) 2.0
Total de reductos calculados (B=1 0q =0.3) 3.125
Total de reductos calculados (B=5 0q =0.3) 2.25
Con estos posibles parámetros el algoritmo tiende a encontrar mayor cantidad de reductos más
pequeños cuando el valor de 0q es alto y el de es bajo.
Se puede concluir que entre las cuatro variaciones de parámetros la combinación de parámetros
1 , 3.00 q es la que proporciona mejores resultados.
Comparación con otros métodos
Para establecer una comparación del algoritmo propuesto con otros establecidos en la literatura
se evalúa un grupo escogido de algoritmos de selección de rasgos con una colección de
conjuntos de datos del “Repositorio UCI”. Esta selección se ha hecho sobre la base de tomar
algoritmos que en su forma de construir el subconjunto –solución– de atributos sea similar a la
propuesta de esta tesis, sean algoritmos poblacionales y/o utilicen la RST. Aún así esta selección,
se sabe, es una representación muy pequeña de la amplia variedad de métodos existentes.
En la Tabla 7 se muestran los resultados de la evaluación de los algoritmos. Para cada conjunto
de datos se indica el número de rasgos del conjunto de datos original que describe a cada objeto
y la cantidad de hormigas que fueron utilizadas en la aplicación del ACO-RST-FSP, y a
continuación los resultados de los algoritmos identificados en la primera fila por el nombre
reconocido en la literatura.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
45
Primeramente se enumeran los resultados de los métodos que obtienen reductos:
SAVGeneticReducer, TS-PSO-RST-FS y PSORSFS. Luego se detallan los resultados para el
resto de los algoritmos.
SAVGeneticReducer (Vinterbo & Øhrn, 2000) es un algoritmo que encuentra reductos utilizando
Algoritmos Genéticos como método de búsqueda, ha sido evaluado tomando la implementación
del sistema ROSETTA (Øhrn, 1999; Øhrn, Komorowski, Skowron, & Synak., 1998). TS-PSO-
RST-FS (Bello, Gómez, Caballero, Nowe, & Falcón, 2009; Gómez, et al., 2008) y PSORSFS
(Wang, et al., 2007) son algoritmos poblacionales basados en la combinación de PSO y RST, con
lo cual son de utilidad al comparar sus resultados con el algoritmo ACO-RST-FSP. TS-PSO-
RST-FS fue evaluado con el código original del algoritmo. Los resultados de PSORSFS fueron
tomados de la publicación referida y una implementación en MATLAB. Las soluciones
reportadas para este último algoritmo, a pesar de ser poblacional, se refieren a la mejor solución
encontrada.
Las características de los métodos Best-First, Greedy Stepwise y Genetic Algorithms son
descritos en (Witten & Frank, 2005), y su implementación ha sido tomada del programa WEKA
(Mark Hall, et al., 2009); estos métodos de búsqueda se combinaron con dos funciones de
evaluación de subconjuntos (i-CfsSubsetEval, ii-ConsistencySubsetEval) (Mark Hall, et al.,
2009) obteniéndose 6 variantes.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
46
Tabla 7 Comparación entre algoritmos de selección de rasgos
Conjuntos de
datos na m
AC
O-R
ST
-FS
P
SA
VG
enet
icR
edu
cer
TS
-PS
O-R
ST
-FS
PS
OR
SF
S
Best-First Greedy
Stepwise
Genetic
Algorithms
i ii i ii i ii
Breast Cancer
Jenk 10 10 6(4) 6(4) 6(4.6) (4) 1(9) 1(8) 1(9) 1(8) 1(9) 1(7)
Breast-w 9 9 9(5) 8(5) 7(5) - 1(8) 1(5) 1(8) 1(5) 1(8) 1(5)
Dermatology 34 24 4(9) 1(10) 5(12.6) (12) 1(19) 1(11) 1(19) 1(11) 1(11) 1(11)
heartJen 13 13 1(6) 1(6) 6(6.8) (6) 1(6) 1(8) 1(6) 1(8) 1(6) 1(7)
LedJen discreto 24 24 1(5) 1(5) 1(5) (5) 1(12) 1(5) 1(12) 1(5) 1(12) 1(9)
LungJen discreto 56 33 7(4) 8(4) 6(4) (4) 1(12) 1(4) 1(12) 1(4) 1(21) 1(13)
Ionosphere 34 24 6(7) 5(7) 5(7) (8) 1(12) 1(4) 1(12) 1(4) 1(9) 1(17)
Mushroom 21 24 2(4) 2(4) 2(4) (4) 1(4) 1(5) 1(4) 1(5) 1(5) 1(6)
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
47
2.2 Estrategias de ahorro del tiempo de ejecución en la implementación
ACO
2.2.1 Codificación de la función de evaluación
Recientemente el análisis del tiempo de ejecución de la metaheurística ACO ha sido estudiado,
pero los esfuerzos han sido limitados a clases específicas de problemas o a versiones
simplificadas del algoritmo, en particular al estudio de una pieza del algoritmo como la
influencia de la feromona (Doerr, Neumann, Sudholt, & Witt, 2007; Neumann & Witt, 2006).
Sin embargo, un elemento que introduce un alto costo computacional es el cálculo de la
evaluación de la función heurística. Como es sugerido en la literatura (Droste, Jansen, &
Wegener, 2002; Gutjahr, 2007), este trabajo se enfoca en el análisis del tiempo de ejecución por
el número necesario de invocaciones a la función de evaluación.
Las hormigas seleccionan el próximo nodo de acuerdo con las expresiones (2.1) o (2.2),
dependiendo si se trata de una variante utilizando el Sistema de Hormigas o el Sistema de
Colonias de Hormigas, invocando la función heurística para calcular la calidad de los nodos.
Para funciones heurísticas sencillas, con baja complejidad computacional no es necesario
estudiar el tiempo de ejecución incluyendo análisis de la heurística. Pero para funciones
heurísticas con alta complejidad computacional, estas tienen gran influencia en la complejidad
del modelo y del tiempo de ejecución. Por tanto, se propone clasificar los problemas que pueden
ser resueltos con la metaheurística ACO tomando en cuenta la forma de la función de evaluación
heurística: las que toman sólo información acerca del próximo nodo, tales como la distancia a la
próxima ciudad en el TSP, tomando un nodo cada vez para evaluar la heurística; y las otras, las
que toman no sólo el próximo nodo a incluir en la solución sino la lista tabú que permanece en la
hormiga, tales como el problema de cubrimiento de conjuntos. En este último caso la
información heurística depende del próximo nodo y el subconjunto de nodos ya visitados por la
hormiga; como se puede tener información acerca de estos subconjuntos de nodos se pueden
evitar evaluaciones replicadas y ahorrar una gran cantidad de tiempo de ejecución.
Como solución, en esta investigación se propone usar una estructura de datos que almacena
todos los subconjuntos evaluados y su calidad (el valor heurístico) calculada; luego, cada
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
48
llamada a la función primero busca el subconjunto en la estructura de datos. Si el subconjunto es
encontrado el valor asociado es retornado sino la función heurística es evaluada y ambos, el
nuevo subconjunto y su valor son almacenados en la estructura de datos para su uso futuro.
Resultados experimentales
Para evaluar el efecto de la introducción de esta nueva estrategia se ejecutó el algoritmo y se
contaron, en cada ciclo, la cantidad de veces que la función heurística, dado por la expresión
(1.8), fue evaluada (columna ii, Tabla 8), cuantas veces se encontró en la lista el valor heurístico
ya calculado, esto es cuantas veces se encontró el subconjunto buscado ya calculado y
almacenado en la estructura de datos (columna iii, Tabla 8); la suma de estas dos cantidades
corresponden al total de subconjuntos candidatos evaluados (columna iv, Tabla 8). Este
experimento fue llevado a cabo con diferentes conjuntos de datos del Repositorio UCI (Blake &
Merz, 1998). La Tabla 8 muestra los resultados obtenidos para el conjunto de datos
“Dermatology” evaluado para 15 ciclos con 15 hormigas. Otras réplicas del experimento fueron
llevadas a cabo con los conjuntos de datos Heart-disease, Ledjen, y Lung-cancer para 15 ciclos,
teniendo en todos los casos un comportamiento similar, ver Anexo 2.
Tabla 8 Número de subconjuntos evaluados en cada ciclo.
Ciclo
(i)
Calculados
Expresión (1.8)
(ii)
Almacenados en la
estructura de datos
(iii)
Total de subconjuntos
candidatos
(iv)
1 3426 11673 15099
2 2664 7940 10604
3 1993 6498 8491
4 2238 13125 15363
5 1385 10221 11606
6 1432 14936 16368
7 1566 11806 13372
8 1055 9985 11040
9 752 11541 12293
10 950 9472 10422
11 592 12836 13428
12 729 11687 12416
13 502 17314 17816
14 709 11234 11943
15 349 9079 9428
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
49
En el gráfico de la Figura 3 se representa la información de la Tabla 8. La columna ii de la tabla,
graficada como una línea de puntos, representa el número de veces que la función heurística fue
evaluada por la expresión (1.8). La línea de trazos, columna iii de la tabla, representa el número
de subconjuntos que ya habían sido evaluados y se encontraban almacenados en la estructura de
datos. La línea continua, columna iv de la tabla, representa la totalidad de los subconjuntos a ser
evaluados.
Figura 3 Evaluaciones de subconjuntos
El número total de candidatos que necesitan ser evaluados por ciclo muestra un comportamiento
oscilatorio debido al carácter estocástico de la metaheurística ACO.
Como puede ser observado a partir del gráfico, en cada nuevo ciclo el número de evaluaciones
de la expresión (1.8) tiende a decrecer. La línea de puntos decrece con el número de ciclos.
Nótese que esta línea corresponde a la diferencia entre la línea de trazos discontinuos y la línea
sólida. Esto ocurre debido al creciente número de subconjuntos encontrados dentro de la
estructura de datos durante la ejecución del algoritmo; considerando que la expansión de esta
estructura de datos y la complejidad de encontrar un subconjunto de datos para recuperar la
calidad de este subconjunto dentro de ésta no será nunca más costoso que evaluar la expresión
(1.8).
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
50
El hecho de que progresivamente más subconjuntos son evaluados tomando la información
encontrada en la estructura de datos en lugar de evaluar la función heurística dada por la
expresión (1.8) hace que el costo computacional en tiempo decrezca. El análisis de complejidad
apoya lo que ha sido indicado anteriormente:
Sea:
I el número de iteraciones del algoritmo, n cantidad de hormigas, l número de rasgos
originales, m cantidad de objetos en el conjunto de datos, c número de clases en el sistema
de decisión original y s la cantidad de elementos almacenados en la estructura de datos.
La complejidad para ACO-FS (Jensen & Shen, 2005) )( lnIO
La complejidad de evaluar la expresión (3) )( 22 mlcO
La complejidad de encontrar un subconjunto en la estructura de datos (en forma de lista)
)( slO
El número de elementos almacenados en la lista se incrementa dinámicamente de acuerdo al
carácter estocástico de la familia de algoritmos ACO. En los primeros ciclos el crecimiento será
rápido, pero luego ésta crecerá más lentamente porque muchos subconjuntos ya estarán en la
lista. En cada ciclo el mayor número de elementos en la lista es del orden 2ln , luego 2mc
tiene un orden mayor que nl , en consecuencia la complejidad para evaluar la expresión (1.8)
tiene un orden mayor que buscar un conjunto en la lista.
Por estas razones, es presumible que el tiempo de corrida esperado hasta alcanzar la solución
optimal es de un orden más favorable usando la estrategia propuesta.
Otro aspecto interesante a tomar en cuenta es el análisis comparativo del espacio de búsqueda
explorado por el algoritmo ACO-RST-FSP versus un método exhaustivo. La Tabla 9 muestra
cálculos realizados para un grupo de conjuntos de datos del Repositorio UCI. Las columnas (iii)
y (iv) ilustran el número de rasgos en los reductos encontrados por el algoritmo ACO-RST-FSP,
la columna (iii) longitud promedio y la (iv) longitud del reducto más corto encontrado. Las
columnas (v) y (vi) representan el número de subconjuntos evaluados por ACO-RST-FSP para
obtener reductos; y la columna (vii) representa la cantidad de subconjuntos que debe evaluar un
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
51
método exhaustivo, esto es la cantidad de nodos del espacio de búsqueda que deben ser visitados.
Los valores de la columna (vii) son calculados según la expresión (2.3)
Tabla 9 Espacio de búsqueda: algoritmo ACO-RST-FSP vs. método exhaustivo
Conjuntos
de datos Rasgos
Reductos ACO-RST-FSP Búsqueda
exhaustiva
Longitud
promedio
Longitud
más corta
Calculados
expresión
(1.8)
Almacenados
estructura de
datos
Espacio de
búsqueda
(i) (ii) (iii) (iv) (v) (vi) (vii)
Heart 13 10.2 7 943 33020 10057645
Led 24 7.7 5 2802 622160 5368224
Lung 56 5.7 4 21310 731118 8984416
Breast
Cancer 9 5.4 4 251 7442 3609
Dermatology 34 20.6 10 26291 646980 4.956E+14
MIN
l
llongitudosSubconjuntNodosNúmero1
)(_ (2.3)
donde:
Subconjuntos(longitud=l) es el número de subconjuntos con l rasgos y MIN es el
número de rasgos en el subconjunto más corto.
En general para conjuntos de datos de tamaño medio y grande el espacio de búsqueda de un
método exhaustivo hasta alcanzar una solución óptima será mucho mayor que el espacio
explorado por el método heurístico.
2.2.2 Decremento de la exploración
El enfoque planteado sigue el propuesto en (Bello, Gómez, Nowé, & García, 2007; Gómez, et
al., 2008) y (Cáceres, 2009). Está basado en la idea de dividir el proceso de búsqueda hecho por
las hormigas en dos etapas, tal que en la primera etapa se alcancen resultados preliminares y
luego sean usados para construir los estados iniciales para la segunda etapa. En el problema de
selección de rasgos, esto significa que subconjuntos de rasgos generados en la primera etapa son
subcojuntos (reductos) potenciales usados como población inicial en la segunda etapa.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
52
La aplicación de esta estrategia aporta una disminución considerable de la exploración en el
espacio de soluciones. La Figura 4 muestra el espacio de soluciones para un conjunto de datos
con 5 atributos (A-E) predictores; se destaca la búsqueda realizada por una hormiga, los atributos
seleccionados en la primera etapa (región marcada con trazo discontinuo) y el espacio de
búsqueda en la segunda etapa (región marcada con trazo continuo sólido). Gráficamente puede
observarse la reducción del espacio de búsqueda de la hormiga una vez que en la primera etapa
seleccionó los atributos C y D, quedando descartadas todas las combinaciones que están fuera de
la región enmarcada con trazo continuo.
Con el propósito de aplicar el enfoque de dos etapas es necesario establecer como inicializar
algunos parámetros. Establecer el factor de proporción r tiene una alta influencia en la eficiencia
global del algoritmo. Valores cercanos a 1 producen subconjuntos próximos a la definición de
reductos en la primera etapa.
ABCDE
A B C D E
AE BE CD CE DE
ABC ABD ABE BCD BCE CDE
ABCD ABCE BCDE ACDE
AB AC AD BC BD
ACE ACD ADE BDE
ABDE
Figura 4 Exploración de las hormigas en el algoritmo TS-ACS-RST-FSP
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
53
El número de hormigas y el número de ciclos por etapa es calculado de acuerdo con el valor de r,
esto es, sea m la cantidad de hormigas a utilizar y NCMax el número de ciclos a realizar, estos
valores son divididos para cada etapa de la siguiente forma: primera etapa { rmm 1 y
rNCNC max1max }, y segunda etapa { )1(2 rmm y )1(max2max rNCNC }. Además, se
debe definir que es una solución parcial en la primera etapa. En este caso, el valor de referencia
es la medida de calidad de la aproximación de la clasificación YA , donde A es el conjunto de
todos los atributos, y las hormigas tienen que construir subconjuntos de rasgos con una calidad
de aproximación igual a Yr A . En la segunda etapa se buscan soluciones al problema
original por tanto los subconjuntos tienen que obtener el valor YA .
En otras palabras, en la primera etapa m1 hormigas estarán buscando subcojuntos de rasgos con
calidad de aproximación de la clasificación igual a Yr A durante NCmax1. En la segunda
etapa, m2 hormigas realizan NCmax2 ciclos usando subconjuntos resultantes de la primera etapa
como estados iniciales con el propósito de generar reductos.
Algoritmo TS-ACS-RST-FS:
Entrada: Conjunto de datos que describen mediante rasgos distintos objetos e incluye un
atributo clase.
Salida: Colección de reductos.
Parámetros: r,naNCmaxq atributos) (número ,ciclos) de totalnúmero(,,, 0
P0:
Calcular la cantidad de hormigas (m) según el número de rasgos (na)
Calcular la calidad de la aproximación de la clasificación usando la
totalidad de los rasgos YA
P1: Etapa 1
Calcular el valor de los parámetros para la primera etapa
maxmax1 NCrNC
mrm 1
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
54
YrY AB 1
Aplicar el algoritmo ACO-RST-FSP
Reductos_Candidatos subconjuntos seleccionados por ACO-RST-FSP
P1: Etapa 2
Calcular los valores de los parámetros para la segunda etapa
12 maxmaxmax NCNCNC
12 mmm
YY AB 2
Aplicar el algoritmo ACO-RST-FSP
En cada ciclo, para cada hormiga, tomar aleatoriamente un
subconjunto del grupo de reductos candidatos y asignarlo como
subconjunto inicial.
Fin
Resultados Experimentales
Se desarrolló un estudio comparativo del algoritmo TS-ACS-RST-FS respecto al ACO-RST-
FSP. En los experimentos, se han usado los siguientes valores para el parámetro r
8.0,6.0,5.0,36.0,3.0,2.0 . El efecto de esta proporción r fue estudiada en tres aspectos: la
longitud de los reductos, la cantidad total de reductos calculados y el tiempo de cómputo. Cada
algoritmo fue ejecutado 10 veces y los resultados son promediados sobre estas 10 corridas.
En la Tabla 10, se presenta el estudio realizado para el conjunto de datos Breast-Cancer del
Repositorio UCI, el número de rasgos es 9 y se utilizaron 9 hormigas. En las columnas 4 y 5 la
información es presentada de la siguiente forma: en la primera fila, son presentados los
resultados obtenidos por el algoritmo ACO-RST-FSP (total de reductos calculados/tiempo); en
el resto de las filas se presenta el resultado producido por el algoritmo TS-ACS-RST-FS
(porciento de reductos calculados/porciento de tiempo) respecto a los resultados mostrados en la
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
55
primera fila. Por ejemplo el algoritmo TS-ACS-RST-FS con r=0.3, =5 y q0=0.9 obtuvo un
promedio de 50.9 reductos (109% respeto a 46.7 reductos) en sólo 71 segundos (31% respecto a
228s). Estos resultados son muy interesantes porque TS-ACS-RST-FS permite obtener una
cantidad igual o mayor de reductos en menor tiempo que el algoritmo ACO-RST-FSP.
A partir de los experimentos realizados es posible observar que el costo de tiempo en el
algoritmo TS-ACS-RST-FS es muy bajo. De esta ventaja se propone una segunda idea:
incrementar la cantidad de hormigas para producir una mayor exploración del espacio de
búsqueda. Se llevaron a cabo experimentos en los cuales el número de hormigas se incrementó
por los factores 1.2,8.1,5.1,33.1 . En la última fila de la Tabla 10 se muestra los resultados con
valor 2.1. La relación es establecida respecto a la cantidad de reductos y el tiempo empleado en
el cálculo. Por ejemplo, cuando el número de hormigas es incrementado a m1.2
( 1991.2 m ), el algoritmo TS-ACS-RST-FS obtiene 124% del número de reductos respecto
a la cantidad de reductos obtenidas por el algoritmo ACO-RST-FSP en sólo el 67% del tiempo
usado por este último para =5 y q0=0.9; y se usó r=0.3 porque este es el valor que muestra los
mejores resultados experimentales.
Puede apreciarse cómo el índice de proporción de 0.3 produce los mejores resultados. Esta
asignación obtiene una cantidad de reductos cercana a la de su original ACO-RST-FSP, pero
utilizando un porciento mucho menor del tiempo. Resultados similares fueron obtenidos usando
otros conjuntos de datos. Esto es un resultado esperado porque este valor de índice de
proporción (0.3) ofrece un buen balance entre ambas etapas; un alto número de hormigas y ciclos
en la segunda etapa permite al algoritmo realizar una amplia exploración del espacio de
búsqueda a partir de subconjuntos (que gozan de cierta calidad) tomados como estados iniciales.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
56
Tabla 10 Comparación entre ACO-RST-FSP y varias alternativas
de TS-ACS-RST-FS (NCmax1=6, NCmax2=15)
Algoritmo m1 m2 beta=5
q0=0.9
beta=1
q0=0.3
ACO-RST-FSP -- -- 46.7 / 228s 123 / 274s
TS-ACS
rate=0.2 2 7 60% / 34% 70% / 49%
TS-ACS
rate=0.3 3 6 109% / 31% 73% / 37%
TS-ACS
rate=0.36 3 6 105% / 25% 77% / 31%
TS-ACS
rate=0.5 4 5 100% / 22% 73% / 26%
TS-ACS
rate=0.6 5 4 65% / 13% 50% / 20%
TS-ACS
rate=0.8 7 2 33% / 27% 31% / 26%
TS-ACS
rate=0.3
m=2.1*m=19
6 13 124%/67% 103%/83%
2.3 Solución al problema de la selección de rasgos sobre múltiples fuentes
de datos. El algoritmo D.ACO-RST-FSP
El problema de la selección de rasgos sobre múltiples fuentes de datos también nombrado
problema de la selección de rasgos en contexto distribuido, en general, es similar al problema
clásico de selección de rasgos, pero en este hay varias fuentes de datos donde los algoritmos son
aplicados con el mismo objetivo. El modelo que se presenta trata con conjuntos de datos
homogéneos y un grupo de subsistemas con disposición de colaborar para realizar la tarea, pero
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
57
imposibilitados de compartir los datos, tanto por restricciones de transmisión de los datos como
por cuestiones de privacidad sobre éstos.
Como solución se propone un nuevo algoritmo inspirado en la idea del ACS multi-tipo de Nowé,
Verbeeck, y Vrancx (Nowé, Verbeeck, & Vrancx, 2004).
Algoritmo D.ACO-RST-FSP:
Entrada:
- Cada colonia recibe un conjunto de datos
- Enlace con el resto de las colonias.
- Frecuencia de intervalo de intercambios del grafo de feromona
Salida: Colección de reductos.
P0:
Inicializar parámetros
Intercambiar grafo de feromona entre las colonias
Repetir
Iteración Iteración + 1
P1:
Para cada colonia
Construir sus soluciones según el principio de ACS utilizando las
fórmulas (2.4) y (2.5)
P2:
if Iteración = Intervalo_de_intercambios
Intercambiar grafo de feromona
Hasta alcanzar criterio de para en todas las colonias
La principal idea es realizar la tarea de selección de rasgos en los conjuntos de datos en la misma
forma que lo hace el algoritmo ACO-RST-FSP, pero ahora tomando en cuenta la experiencia
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
58
ganada en el resto de los subsistemas realizando la misma tarea. La experiencia ganada se
expresa mediante el rastro de feromona y se trasmite a las demás colonias. De esta manera, el
algoritmo tiene su propio rastro de feromona y conoce el rastro dejado por hormigas de colonias
colaborativas. Adicionalmente, las colonias intercambian su rastro "frecuentemente".
De manera similar al ACS multi-tipo se extiende la fórmula de transición probabilística (2.1)
como sigue en (2.4) y la regla seudo-aleatoria proporcional (2.2) como sigue en (2.5).
caso otroen ticaprobabilísecuación lasegún selección
si maxarg 0qqYj
s
jaBjNl jkk
i
(2.4)
k
j
BAa
s
jaBj
s
jaBj
k
j
j
k
k BAaY
Y
Ba
aBp
kj
jk
jk
si
si0
,
(2.5)
En estas fórmulas, s
j representa la cantidad promedio de rastro de feromona perteneciente a
otras s colonias en el nodo j. Este es el promedio de todos los rastros de feromona dejado por
otras hormigas en diferentes colonias realizando la misma tarea para otros conjuntos de datos. La
potencia indica la sensibilidad de las hormigas para seguir su propia experiencia o la
experiencia ganada por el resto de las colonias. Este es un parámetro a ser estudiado; pero
claramente si a es asignado valor cero las hormigas calcularán la probabilidad basada en la
heurística del problema y la feromona de su propia colonia, tal como el algoritmo original siendo
ignorado el rastro de feromona de las otras colonias. Si es incrementado, la probabilidad de
seleccionar un nodo se convertiría cada vez más dependiente de la experiencia del resto de las
colonias.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
59
Evaluación del algoritmo
Para realizar experimentos y evaluar este algoritmo se escogieron varios conjuntos del
Repositorio UCI para ser particionados y simular el ambiente distribuido construyendo un
escenario de prueba desde el punto de vista teórico-práctico siguiendo la idea expuesta en (Jasso-
Luna, Sosa-Sosa, & Lopez-Arevalo, 2008) y (Martens, Backer, Haesen, Baesens, & Holvoet,
2006). Se dividió cada conjunto de datos en cuatro partes, con el fin de que cada una de estas
partes simule un nuevo conjunto de datos y poder aplicar el algoritmo distribuido como se
muestra en la Tabla 11. Para realizar las divisiones de los conjuntos de datos se utilizó el filtro
"Stratified Remove Folds" de Weka, que mantiene la distribución de objetos por clases.
Para establecer una comparación entre el algoritmo ACO-RST-FSP y su variante para contexto
distribuido D.ACO-RST-FSP estos fueron ejecutados sobre los conjuntos de datos haciendo 10
réplicas y tomando la mediana de los resultados como medida de comparación en cada uno de
los indicadores tomados, en todos los casos a los parámetros fueron asignados los valores
1.1,9.0,5,1 0 q , con intercambios del grafo de feromona cada 5 ciclos.
En la Tabla 11 las particiones (valores 1-4) se refieren a los nuevos conjuntos de datos que
resultan de la división del original del Repositorio UCI. La decisión se toma según el valor de los
indicadores. Primeramente se analiza la longitud del reducto más corto (columna i), luego el
número de veces que se encontró el reducto más corto (columna ii), seguidamente la cantidad
total de reductos encontrados (columna iii), y finalmente la longitud promedio de los reductos
(columna iv). La columna (v) establece si la variante supera para el conjunto de datos a la
variante original. A partir de un análisis basado en la Tabla 11 se determina cómo la variante
distribuida supera la original (local).
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
60
Tabla 11 Comparación ACO-RST-FSP vs. D.ACO-RST-FSP
Conjunto de
datos Partición
ACO-RST-FSP D.ACO-RST-FSP
(v)
(i) (ii) (iii) (iv) (i) (ii) (iii) (iv)
Bre
ast-
w
1 3 4 5 3.20 3 7 9 3.22 +
2 3 3 13 3.76 3 4 9 3.55 +
3 3 5 9 3.44 3 8 10 3.20 +
4 3 6 10 3.40 3 5 14 3.64 -
Vote
1 5 1 9 6.44 5 8 11 5.45 +
2 4 4 9 5.66 4 4 9 4.77 +
3 3 1 8 5.00 3 1 19 4.63 +
4 5 6 10 5.40 5 5 6 5.16 -
Veh
icle
1 12 4 4 12.00 12 4 5 12.20 +
2 10 1 12 11.08 10 1 12 11.01 +
3 11 9 21 11.67 11 8.5 21.5 11.80 -
4 11 1 12 11.92 11 1 10 11.90 -
Ajuste de parámetros
El algoritmo D.ACO-RST-FSP, igual que su variante original en contexto local es sensible a la
influencia de varios parámetros, los comunes han sido explicados anteriormente. En este se
incluyen nuevos parámetros propios del contexto al que pertenece el algoritmo, ver Tabla 12.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
61
Tabla 12 Parámetros del algoritmo D.ACO-RST-FSP
Parámetros Breve Descripción
NI Número de intercambios del grafo de feromona
Controla el promedio de las feromonas del resto de
las colonias
De estos nuevos parámetros, resulta de mucho interés el estudio de que actúa directamente
sobre el intercambio de información, expresando cada cuantas iteraciones va a ocurrir el
intercambio de metadatos. Para estudiar su efecto se llevó a cabo un experimento, realizando
intercambios al 20%, 10% y 5% del total de los ciclos. Para las experimentaciones realizadas –
con 100 ciclos– esto significa que el número de iteraciones a los cuales se efectúa un
intercambio, toma valores de 5, 10 y 20 ciclos.
Este algoritmo tiene un marcado carácter estocástico, por lo cual se realiza el mismo proceso
que en la validación explicado en tópicos precedentes, en el sentido de replicar un mismo
experimento 10 veces y tomar la mediana de los indicadores como el valor a comparar. De forma
similar se aplica la validación estadística de las muestras para cada uno de los indicadores,
aplicando las mismas pruebas que en el tópico anterior. Las tablas que se describen a
continuación contienen el mismo tipo de información que las mostradas para el algoritmo en
contexto local.
El indicador que describe el total de reductos calculados presenta un valor de 0.00903 al aplicar
el test de Iman-Davemport como valor de significación, por tanto existen diferencias
significativas. En la Tabla 13 se muestran los valores de los rangos de las poblaciones.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
62
Tabla 13 Promedio de rangos de las muestras
Algoritmos Rangos
Total de reductos calculados cada 5 ciclos 2.125
Total de reductos calculados cada 10 ciclos 1.578125
Total de reductos calculados cada 20 ciclos 2.296875
En la Tabla 14 se muestra la comparación entre las poblaciones, utilizando el test de Holm para
las comparaciones.
Tabla 14 Resultados del test de Holm
i Algoritmos p Holm
1 Total de reductos calculados cada 10 ciclos vs.
Total de reductos calculados cada 20 ciclos
0.00404 0.01666
2 Total de reductos calculados cada 5 ciclos vs.
Total de reductos calculados cada 10 ciclos
0.02871 0.025
3 Total de reductos calculados cada 5 ciclos vs.
Total de reductos calculados cada 20 ciclos
0.49177 0.05
Los resultados del algoritmo con intercambio al 10% del total de ciclos es significativamente
mayor encontrando reductos que los obtenidos del algoritmo con intercambio al 5% del total de
ciclos, mientras que con respecto a la variante calculada al 20% del total de ciclos no ofrece
diferencias significativas, lo que demuestra la importancia del intercambio de información de
forma periódica.
El indicador que describe la longitud de reductos más cortos obtiene de la aplicación del test de
Iman-Davenport 0.56389, lo que indica que no existe diferencia significativa entre las muestras
por lo que estas van a seguir una tendencia descrita en la Tabla 15.
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
63
Tabla 15 Promedio de rangos de los algoritmos
Algoritmos Rangos
Total de reductos calculados cada8 5 ciclos 1.921875
Total de reductos calculados cada 10 ciclos 1.921875
Total de reductos calculados cada 20 ciclos 2.15625
El algoritmo tiende a encontrar reductos más pequeños cuando el intercambio ocurre al 10% y al
20% del total de ciclos. Esto puede estar dado por el resultado del indicador anterior, pues si son
encontrados más reductos, existe la posibilidad de encontrar los más cortos.
El indicador que describe la cantidad de reductos más cortos obtiene de la aplicación del test de
Iman-Davenport el valor 0.94836, lo que indica que no existe diferencia significativa entre las
muestras por lo que estas van a seguir una tendencia descrita en la Tabla 16.
Tabla 16 Promedio de rangos de los algoritmos
Algoritmos Rangos
Total de reductos calculados9 cada 5 ciclos 2.03125
Total de reductos calculados cada 10 ciclos 1.953125
Total de reductos calculados cada 20 ciclos 2.015625
El algoritmo tiende a encontrar mayor cantidad de los reductos más cortos cuando el intercambio
ocurre al 10% del total de ciclos.
Como conclusión se puede observar que para obtener los mejores resultados se debe establecer
un intercambio al 10% del total de ciclos.
8 Refiriéndose a las longitudes más cortas
9 Refiriéndose a la cantidad de reductos con la longitud más corta
Capítulo 2: Inteligencia colectiva aplicada a la selección de rasgos
64
2.4 Consideraciones parciales
1. La combinación de la metaheurística ACO con la medida de calidad de la clasificación de
la RST permite obtener un algoritmo de selección de rasgos competitivo con respecto a
otros métodos y tiene la ventaja de encontrar varios subconjuntos de rasgos durante su
ejecución.
2. El trabajo de investigación muestra que la relación entre los parámetros beta ( ) y 0q
tiene un impacto fuerte en la cantidad de subconjuntos generados por el algoritmo ACO-
RST-FSP. También esta relación influye sobre el número de rasgos seleccionados (un
fuerte indicador de calidad).
3. Como una cuestión importante en esta investigación se ha explicado y validado cómo
extender el algoritmo propuesto para el caso de datos distribuidos, para lo cual la
metaheurística ACO se convierte en un ACO multicolonias con intercambios de
feromona; donde cada colonia representa un algoritmo ACO resolviendo un problema
con un comportamiento colaborativo entre hormigas de otras colonias mediante
intercambios "frecuentes" de feromona. Este enfoque para el caso distribuido incrementa
la calidad de los reductos encontrados.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
65
3 Caso de estudio: "El problema de cardiopatías"
En sentido amplio, el término cardiopatía puede englobar a cualquier padecimiento del corazón o
del resto del sistema cardiovascular. En sentido estricto, se suele denominar cardiopatía, a las
enfermedades propias de las estructuras del corazón. Las enfermedades cardiovasculares son la
primera causa de muerte en el mundo. Según informes de la Organización Mundial de la Salud
más del 75% de estas muertes de origen cardiovascular corresponden a la cardiopatía isquémica.
El Infarto Agudo del Miocardio (IMA) obedece a diversas causas, pero se reconoce que los
factores de riesgo tienen una importancia decisiva en su aparición y/o empeoramiento una vez
que acontece el evento cardiovascular. La mayor probabilidad para seguir disminuyendo su
incidencia descansa justamente en la prevención de los factores que originan la presentación
clínica de la enfermedad.
El estudio de los factores de riesgo en cardiópatas con técnicas de minería de datos distribuida ha
sido abordado recientemente en Cuba (Wilford, Rosete, & Rodríguez, 2009a, 2009b). En estos
trabajos los autores desarrollaron un estudio experimental, basado en un análisis comparativo
entre los resultados del análisis de datos centralizados y del análisis de datos distribuidos
homogéneos, para el análisis de las coronariografías realizadas a pacientes con cardiopatía
isquémica. Como resultado obtuvieron un modelo de clasificación (reglas de decisión) de las
coronariografías, identificando las características que afectan el comportamiento de la variable
complicaciones en este tipo de proceder quirúrgico e identificaron asociaciones importantes entre
los factores de riego presentes en los pacientes con esta patología.
La causa de muerte por problemas del corazón en nuestro país ocupa un lugar relevante
desfavorablemente. El IMA es la primera causa de muerte en Cuba. En principio todas las
acciones preventivas son bienvenidas. Contar con un software que permita hacer un pronóstico
efectivo de personas propensas a sufrir un infarto agudo del miocardio resulta de utilidad; si se
suma que este pronóstico se puede lograr con un grupo de preguntas al paciente y apenas un
reducido grupo de pruebas clínicas elementales, como la medición de la presión arterial, el
beneficio que reporta es considerable.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
66
En esta tesis se intenta hacer un pronóstico de IMA tomando en cuenta una base de casos
disponible con un grupo de pacientes, todos con alguna cardiopatía; pero un grupo sufrió un
infarto con posterioridad al diagnóstico de la misma y otro grupo no lo ha sufrido. Las variables
predictivas son factores de riesgo reconocidos en la literatura y detallados en la Tabla 17. La
expectativa es que, una vez realizado el aprendizaje, al arribar un paciente se pueden obtener los
valores para estas variables y realizar un proceso de clasificación clásico determinando si el
paciente es propenso o no a sufrir un IMA. Se plantea como hipótesis que el pronóstico puede
ganar mayor calidad si se toman en cuenta datos de pacientes obtenidos en otras clínicas
(municipios vecinos) que colaboran ofreciendo información sobre casos clínicos anteriores o
colaterales.
Puede declararse abiertamente como alcance, y a la vez, limitaciones, de esta investigación, que
no se buscan diferencias en espacio-tiempo. Las mediciones han sido realizadas en un corte
transversal de tiempo y por tanto en todo caso, desconociendo como pueden variar en el tiempo
Desde el punto de vista biomédico se trata de un reto fuerte debido a que, los factores de riesgo
de IMA entre cardiópatas tienen un cierto carácter general, e independiente del espacio físico y
del tiempo. Sin embargo, los datos reales no arrojan resultados totalmente homogéneos. Según el
estudio realizado este riesgo puede variar con algunas características locales y además (por el
momento no investigada) a lo largo del tiempo.
3.1 Descripción del problema
Concretamente en esta investigación se cuenta con datos de tres municipios de Villa Clara que se
han escogido (Camajuaní, Caibarién y Remedios). Por tanto, se pretende un pronóstico de IMA a
partir de los datos de la clínica del municipio donde arribe el paciente, o a partir de la
colaboración de la información entre los tres municipios, para reducir el sesgo ocasional posible
en los datos de éstos. Los datos almacenados tienen la misma estructura descrita y se resumen
para los tres municipios en la siguiente Tabla 17.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
67
Tabla 17 Descripción de las variables de la base de casos de IMA entre cardiópatas
Variable Nombre de la variable Valores posibles
X0 Municipio Camajuaní, Caibarién,
Remedios
X1 Grupo Clase:
Infartados, No infartados
X2 Número consecutivo (eliminada)
X3 Iniciales del paciente (eliminada)
X4 Sexo F/M
X5 Edad un valor entero
X6 Raza B/N
X7 Antecedentes de IMA Sí o No
X8 Angina de pecho Sí o No
X9 Otras formas de cardiopatías Sí o No
X10 Fuma Sí o No
X11 Tiempo de fumador “No fuma”, “1-5 años”,
“6-10 años” ó “Más de 10”
X12 Fuma cigarrillos Sí o No
X13 Fuma tabacos Sí o No
X14 Fuma pipa Sí o No
X15 Cantidad de cigarros "Ninguno", "Hasta 10",
"De 11 a 20" o "Más de 20"
X16 HTA Sí o No
X17 Grado de HTA “Sin HTA”, “Grado I”,
“Grado II”, “Grado III”
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
68
X18 Tiempo de HTA “Sin HTA”, “10 o menos”,
“11-20 años” o “Más de 20”
X19 Antec. de diabetes M. Sí o No
X20 Tipo de diabetes “Sin diabetes”, “I” o “II”
X21 Tiempo de diabetes (en años)
X22 Obesidad Sí o No
X23 Sedentarismo Sí o No
X24 Practica ejercicio Sí o No
X25 Pertenece a círculo Sí o No
X26 Hiperlipoprotenimia Sí o No
X27 Tipo hiperlipoprotenimia “Sin hip”, “I”, “II”, “III”,
“IV”, “V”
X28 Ingestión de bebidas
alcohólicas
“Nunca”,
“Esporádicamente”,
“Frecuentemente”
X29 Stress en el hogar Sí o No
X30 Stress en el trabajo Sí o No
X31 Stress en otro lugar Sí o No
El problema de reducción de dimensionalidad para clasificar el riesgo de IMA entre cardiópatas
fue abordado anteriormente en cada municipio por separado usando técnicas estadísticas que
hacían una transformación de los datos iniciales recogidos en nuevas variables continuas o
componentes principales (PCA, acrónimo en inglés de Principal Component Analysis) y luego el
estudio de clasificación con dichas componentes utilizando análisis discriminante (Grau, 2009).
La razón de utilizar el análisis factorial de componentes principales se deriva obviamente de la
naturaleza de los datos. Obsérvese que:
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
69
Para evaluar el riesgo de fumar se mide:
- Si fuma o no
- Tiempo de fumador
- Si fuma cigarrillos o no
- Si fuma tabacos o no
- Si fuma en pipa o no
- Cantidad promedio de cigarros que fuma diariamente
Para evaluar el riesgo de HTA se mide:
- Si es hipertenso o no
- Grado de hipertensión arterial
- Tiempo de HTA (a partir de su diagnóstico)
Para evaluar riesgo de diabetes se mide:
- Si hay antecedentes patológicos personales de diabetes o no
- Tipo de diabetes
- Tiempo de diabetes desde su diagnóstico
Para evaluar el “sedentarismo” se mide:
- Obesidad (sí o no)
- Sedentarismo en el trabajo u hogar (sí o no)
- Si practica ejercicio (sí o no)
- Si pertenece a un círculo de abuelos (sí o no)
Es obvio que estas variables están correlacionadas por grupos, más precisamente, hay un
subgrupo de variables fuertemente correlacionadas entre sí que apuntan al hábito de fumar; otro
grupo de variables correlacionadas entre sí que apuntan al riesgo de HTA; otro que apunta al
riesgo por Diabetes Mellitus; y otro al sedentarismo. Matemáticamente, se trata de un conjunto
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
70
de rasgos para el cual hay fuertes correlaciones entre parejas de variables, pero bajas
correlaciones parciales entre parejas de ellas, lo que eleva la medida de Kaiser-Meyer-Olkin
(KMO) de la “adecuacidad” de una muestra para la efectividad del análisis de componentes
principales, porque debe permitir agruparlas adecuadamente.
Efectivamente, el análisis de componentes principales en cada municipio, encontró 10 u 11
“factores” con ligeras diferencias entre los tres municipios; pero en todos ellos se agruparon
automáticamente las variables esperadas, de manera que las mediciones del hábito de fumar se
agruparon en un solo factor, los asociados a la diabetes en otro, los asociados a la HTA en otro,
etc. Los resultados se resumen en "la matriz de componentes rotadas", Figura 5.
Matriz de componentes rotadaa
-.926
-.911
.899
.891
.508
.402
-.973
.967
.939
-.914
.912
.697
-.918
.892
.882
-.983
.983
.804
.733
-.574 -.578
.830
-.685 .501
.723
.686
-.766
.709
.451 .480
-.413
FUMA
FUMA CIGARRILLOS
TIEMPO DE FUMADOR
CANTIDAD DE
CIGARROS
SEXO
INGESTION DE BEBIDAS
ALCOHOLICAS
ANTEC. DE DIABETES M.
TIPO DE DIABETES
TIEMPO DE DIABETES
PRACTICA EJERCICIO
SEDENTARISMO
OBESIDAD
HTA
GRADO DE HTA
TIEMPO DE HTA
TIPO
HIPERLIPOPROTENIMIA
HIPERLIPOPROTENIMIA
EDAD
STRESS EN EL TRABAJO
PERTENECE A CIRCULO
ANGINA DE PECHO
OTRAS FORMAS
FUMA TABACOS
FUMA PIPA
ANTECEDENTES DE IMA
STRESS EN OTRO
LUGAR
STRESS EN EL HOGAR
RAZA
1 2 3 4 5 6 7 8 9 10
Componentes principales
Método de extracción: Análisis de Componentes principales.
Método de rotación: Varimax con nomralización de Kaiser.
La rotación convergió en 11 iteraciones.a.
Figura 5 Matriz de componentes rotadas
El aprendizaje supervisado posterior con Análisis Discriminante a partir de los factores, en lugar
de las variables originales, produjo resultados muy buenos, sobre todo teniendo en cuenta que se
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
71
trataba de distinguir clases (existencia o no de IMA) entre sujetos, todos cardiópatas; ver "la
matriz de confusión", Tabla 18 . En detalle, todo esto puede ser consultado en (Grau, 2009).
Tabla 18 Análisis discriminante: matriz confusión (Camajuaní)
Matriz de confusióna
281 43 324
17 95 112
86.7 13.3 100.0
15.2 84.8 100.0
GRUPO
Con IMA
Sin IMA
Con IMA
Sin IMA
Count
%
Grupos
reales
Con IMA Sin IMA
Grupos predichos
Total
86.2% de los casos originales f ueron clasif icados
correctamente.
a.
La solución previa de este problema, de riesgo de IMA, por la vía estadística clásica, constituye
una “meta alta” a superar, y por ello intencionalmente escogida como patrón para evaluar
rigurosamente nuestros métodos de selección de rasgos. En el siguiente tópico se trata entonces
de aplicar el algoritmo ACO-RST-FSP, y su variante en un entorno distribuido D.ACO-RST-
FSP, sobre estos datos.
3.2 Algoritmos de selección de rasgos presentados aplicados al problema
de cardiopatías
Teniendo en cuenta las características de los datos, es viable la aplicación de los algoritmos
creados y descritos en esta tesis. Un detalle a tener presente es el atributo edad, al manejarlo
como un valor entero pueden aplicarse los algoritmos, sin embargo discretizar este valor puede
elevar la eficiencia de los algoritmos y facilitar el modelo obtenido por algunos clasificadores.
De los datos caracterizados en la Tabla 17, al manipular cada conjunto de datos según su
municipio la variable municipio (X0) carece de sentido, además las variables número consecutivo
(X2) e iniciales del paciente (X3) fueron eliminadas intencionalmente por considerarse que no
tienen un valor semántico considerable, en cambio pueden atentar contra el desempeño de los
algoritmos de aprendizaje y en la calidad de las soluciones.
"Como obtener el mejor subconjunto de rasgos es un problema NP-duro, los algoritmos de
selección de rasgos generalmente utilizan heurísticas en la selección. Por tanto, es importante
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
72
evaluar empíricamente el comportamiento de estos algoritmos. Sin embargo, esta evaluación
necesita ser multicriterios, es decir, esta debe tomar en cuenta varias propiedades, como la
exactitud de predicción del clasificador utilizando el subconjunto de atributos seleccionado, así
como también la reducción en el número de rasgos"(H. D. Lee, Monard, Voltolini, Prati, &
Chung, 2006). También en (Balamurugan & Rajaram, 2009) se toma el número de rasgos para
comparar la calidad de un nuevo método de selección de rasgos con otros establecidos en la
literatura con un funcionamiento similar. De igual forma comprueban la factibilidad del
subconjunto de rasgos obtenido evaluando los resultados en varios clasificadores como ID3,
C4.5, NB, SVM y NN.
Siguiendo el planteamiento de Lee y autores y las prácticas de Balamurugan y Rajaram en esta
aplicación el algoritmo ha sido validado tomando en cuenta el número de atributos presente en
los reductos y su efecto al aplicar un clasificador.
Al aplicar los algoritmos ACO-RST-FSP (contexto local o no distribuido) y D.ACO-RST-FSP
(contexto distribuido), con los mejores parámetros ( 100,3.0,1,1 0 ciclosNúmeroq ,
con intercambios cada 10 ciclos «10% del total» en el distribuido) resultantes de las
validaciones estadísticas realizadas y el ajuste de parámetro realizado en el capítulo 2, se
obtuvieron resultados favoreciendo al algoritmo D.ACO-RST-FSP, ver Tabla 19.
Tabla 19 Resultados de los algoritmos de selección de rasgos propuestos
aplicados al caso de estudio de cardiopatías.
Indicadores
de salida Municipios ACO-RST-FSP D.ACO-RST-FSP
Longitud del
reducto más
corto
Camajuaní 5 5
Caibarién 6 6
Remedios 4 4
Cantidad de Camajuaní 14 14
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
73
reductos más
cortos
Caibarién 1 2
Remedios 1 4
Total de
reductos
calculados
Camajuaní 39 84
Caibarién 79 87
Remedios 99 133
Desde el punto de vista de la aplicación, se puede observar en primer lugar, las ventajas que
brinda la selección de rasgos previa con ACO sin o con distribución, respecto a la selección
(transformación) de rasgos originales hecha anteriormente con PCA:
1. La longitud de los reductos más cortos seleccionados en cualquiera de las alternativas
ensayadas de ACO es menor que el número de factores o componentes principales
detectados por PCA.
2. En cualquiera de los municipios, los reductos son subconjuntos de las variables
originales, fácilmente medibles en una consulta, sin necesidad de cálculos especiales. Las
dimensiones o componentes principales de PCA, necesitan de un cálculo en una
computadora.
3. El cálculo de las componentes principales puede exigir un análisis y un cálculo específico
por municipios, al menos hasta ahora. Cierto es que podría modelarse usando datos de
más municipios, pero ¿todos ellos? o ¿cuánto una muestra de, por ejemplo, tres de los
municipios de los 15 municipios puede ser representativa de todos? La detección de los
reductos con intercambio distribuido de información brinda más confiabilidad a la
selección general de los reductos, porque evita singularidades (ruidos) en un municipio
en particular, compensándolo con los vecinos.
4. La selección de varios reductos de longitud mínima, facilita a los usuarios finales, la
elección, de diferentes subconjuntos de preguntas, ante posible ausencia de información
de algunas de ellas.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
74
5. La selección general de los reductos, en forma distribuida, con intercambio de
información, aplicables, por ejemplo, a varios (o todos) los municipios de una provincia,
facilita evidentemente la aplicación de esta metodología de detección de riesgo de IMA,
de manera uniforme en el MINSAP en diferentes localidades.
En definitiva, la selección de reductos por la vía de ACO conduce a una selección de variables
más simple y aplicable, con mayor grado de generalidad que PCA. Pero la validación final
supone comparar los resultados de la clasificación que se puede obtener a partir de estos reductos
contrastándola con las componentes principales obtenidas por la estadística clásica.
3.3 Solución al pronóstico de infarto agudo del miocardio con un
clasificador
Después de aplicar los algoritmos de selección de rasgos presentados sobre los conjuntos de
datos originales de los tres municipios y obtener una colección de subconjuntos de atributos, de
la aplicación del algoritmo en contexto no distribuido y distribuido. Se realizó una comparación
de precisión de la clasificación (tomando como criterio el porciento de objetos bien clasificados).
En esta comparación se evalúa el resultado de la clasificación tomando en cuenta: todos los
atributos de los conjuntos de datos originales, una transformación de rasgos clásica basada en
PCA y luego aplicar una clasificación basada en Análisis Discriminante, y dos variantes de
subconjuntos de atributos luego de aplicar los algoritmos ACO-RST-FSP y D.ACO-RST-FSP.
Estas dos últimas realizadas con el clasificador Naïve-Bayes (NB).
Variante 1:
El algoritmo ACO-RST-FSP encontró un reducto común (X4, X5, X9, X15, X18, X28) a las
tres clínicas:
( sexo, edad, otras formas de cardiopatías, cantidad de cigarros, tiempo de HTA,
ingestión de bebidas alcohólicas )
El algoritmo D.ACO-RST-FSP también encontró un reducto común
(X5, X8, X9, X15, X18, X28) a las tres clínicas:
(edad, otras formas de cardiopatías, cantidad de cigarros, tiempo de HTA,
ingestión de bebidas alcohólicas)
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
75
Variante 2:
Escoger de cada clínica, de sus reductos calculados por ACO-RST-FSP, el más corto:
Camajuaní: X4, X5, X7, X8, X9
(sexo, edad, antecedentes de IMA, angina de pecho, otras formas de cardiopatías)
Caibarién: X5, X8, X9, X15, X18, X28
(edad, angina de pecho, otras formas de cardiopatías, cantidad de cigarros,
tiempo de HTA, ingestión de bebidas alcohólicas)
Remedios: X5, X7, X8, X9
(edad, antecedentes de IMA, angina de pecho, otras formas de cardiopatías)
Escoger de cada clínica, de sus reductos calculados por D.ACO-RST-FSP, el más corto:
Camajuaní: X5, X7, X8, X9, X25
(edad, antecedentes de IMA, angina de pecho, otras formas de cardiopatías
pertenece a círculo)
Caibarién: X5, X8, X9, X15, X18, X28
(edad, angina de pecho, otras formas de cardiopatías, cantidad de cigarros,
tiempo de HTA, ingestión de bebidas alcohólicas)
Remedios: X5, X7, X8, X9
(edad, antecedentes de IMA, angina de pecho, otras formas de cardiopatías)
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
76
Tabla 20 comparación de precisión de la clasificación.
Municipios
PC
A y
Anál
isis
Dis
crim
inan
te
Naïve-Bayes
Reducto común Reducto más corto Todos
atributos No
distribuido
(local)
Distribuido
No
distribuido
(local)
Distribuido
Camajuaní 86.2% 85.23% 87.50% 91.59% 92.73% 91.36%
Caibarién 84.3% 83.86% 85.91% 88.41% 88.18% 86.59%
Remedios 83.8% 82.26% 94.84% 93.87% 93.87% 91.29%
Puede apreciarse (Tabla 20) que la exactitud de la clasificación consecuente con partir de los
reductos detectados y utilizando Naïve-Bayes, tiene una efectividad al menos comparable con la
obtenida por el método clásico de Análisis Discriminante desde las componentes principales. La
pretensión no era superar la exactitud. La meta era igualarla y esto se logra. Las ventajas 1 a 5
enunciadas anteriormente en la selección de los rasgos, y quizás otras de carácter práctico, por
ejemplo, estabilidad en el tiempo (por probar), además del espacio (ya probada), avalan los
resultados.
Puede resultar interesante estudiar el comportamiento del clasificador no sólo por la precisión de
la clasificación, también observando la matriz de confusión. En el problema que se resuelve es
muy conveniente que la precisión de los pacientes que se pronostican con IMA y en realidad lo
padecen sea alta. En la Tabla 21 se observan porcientos elevados de este indicador en las
columnas correspondientes a cálculos de clasificación realizados con los reductos obtenidos.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
77
Tabla 21 Matriz de confusión, municipio Camajuaní.
PC
A y
An
ális
is
Dis
crim
inan
te
Naïve-Bayes
Reducto común Reducto más corto Todos
atributos No
distribuido
(local)
Distribuido
No
distribuido
(local)
Distribuido
Grupos i ii i ii i ii i ii i ii i ii
Can
tid
ad i 281 43 298 21 315 11 314 0 327 0 315 0
ii 17 95 44 77 44 70 37 89 32 81 38 87
%
i 86.7 13.3 93.4 6.6 96.6 3.4 100 0 100 0 100 0
ii 15.2 84.8 36.4 63.6 38.6 61.4 29.4 70.6 28.3 71.7 30.4 69.6
i – Con IMA,
ii – Sin IMA,
filas representan los grupos reales, columnas representa grupos predichos
Desde el punto de vista práctico-asistencial, puede celebrarse la facilidad en la recolección de los
datos, para llegar a un pronóstico; pero según lo expuesto, podría objetarse, que finalmente,
habría que aplicar un clasificador como NB u otro clasificador para hacer la predicción de riesgo
de IMA en un nuevo caso, a partir de cada reducto, y que esto reclama en definitiva, el uso de
una computadora. La objeción sólo es teóricamente válida: Si se trata de clasificación, se puede
obtener una red bayesiana o un árbol de decisión que pueden ser fácilmente sustituidos por un
conjunto de reglas, que pronostican la probabilidad de riesgo de IMA ante un conjunto de
evidencias (Chávez, 2009). Tales reglas se resumen fácilmente en una tabla impresa de apenas
una hoja, aplicable entonces, desde un nivel primario de salud. Así son bienvenidos éstos, entre
otros resultados, relacionados con la problemática.
La Figura 6 muestra el árbol obtenido por el clasificador ID3 cuando se usa el reducto X5, X8,
X9, X15, X18, X28 como conjunto de atributos. La calidad de la clasificación con este árbol es de
90.6% (objetos bien clasificados), esta no es la mejor de las clasificaciones obtenidas con ID3.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
78
De hecho, en este la variable edad ha sido discretizada para facilitar la visualización. El
propósito de presentar este clasificador basado en un árbol es mostrar cómo se puede obtener un
grupo simple de reglas expuestas en forma de tabla útil para hacer un pronóstico de IMA a
pacientes cardiópatas.
Figura 6 Árbol de decisión generado por ID3 a partir de un reducto
A partir de este árbol y representando los posibles caminos desde la raíz hasta las hojas se puede
confeccionar el siguiente conjunto de reglas representado en la Tabla 22.
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
79
Tabla 22 Representación de un árbol de decisión en forma de reglas
Edad A
ngin
a de
pec
ho
Otr
as
card
iopat
ías
Tiempo de
HTA
Cantidad
de cigarros
Ingestión de bebidas
alcohólicas IMA
menos 45 sí - - - SÍ
sí no - - - SÍ
no no - - - NO
más 45 sí - - - SÍ
no sí Sin HTA Ninguno NO
Hasta 10 Nunca NO
Esporádicamente SÍ
Frecuentemente NO
De 11 a 20 - SÍ
Más de 20 - NO
10 ó menos Ninguno Nunca SÍ
Esporádicamente SÍ
Frecuentemente NO
Hasta 10 - NO
De 11 a 20 - SÍ
Más de 20 - SÍ
11-20 años Ninguno - SÍ
Hasta 10 - NO
De 11 a 20 - SÍ
Más de 20 - SÍ
Más de 20 - - SÍ
Capítulo 3: Caso de estudio: "El problema de cardiopatías"
80
3.4 Consideraciones parciales
1. Con la aplicación en los conjuntos de datos de cardiopatía se obtuvieron tres resultados
trascendentales:
a. Se eliminaron rasgos dependientes entre sí, lo que facilitó aplicar clasificadores
que exigen independencia entre los rasgos. La selección de rasgos no requirió la
transformación complicada de ellos en componentes principales.
b. Las combinaciones de subconjuntos de variables (la colección de reductos) que
resultaron, facilitan a especialistas cardiólogos qué preguntas realizar. Cualquiera
de los reductos de longitud mínima es un subconjunto de preguntas acerca de
variables originales con potencia suficiente para un buen pronóstico.
c. Ambas variantes (no distribuido o distribuido) encontraron un reducto (diferente
en cada variante) común, lo que facilita la aplicación de un algoritmo de
clasificación en contexto distribuido. De hecho, ello facilita la aplicación general
del pronóstico en diferentes localidades, minimizando los sesgos que puedan
aparecer entre ellas, a partir de la información de municipios vecinos.
La detección de reductos comunes en varios municipios logra evadir los “sesgos municipales”, y
obtener “reductos-consenso”, que permiten, de una forma unificada, obtener los mejores
resultados en la aplicación de técnicas de clasificación, con facilidades evidentes para su
implementación práctica generalizada por el MINSAP.
Conclusiones
81
CONCLUSIONES
Como resultado de esta investigación se crearon dos nuevos algoritmos de selección de rasgos;
los cuales, combinando la Optimización basada en Colonias de Hormigas y la Teoría de
Conjuntos Aproximados, proporcionan a investigadores otras alternativas que permitan encontrar
varios subconjuntos reducidos de atributos, capaces de representar la información necesaria en
problemas de aprendizaje supervisado tanto en contexto local como distribuido. Particularmente
se encontraron buenas soluciones al aplicar estos algoritmos en el pronóstico de personas
propensas a sufrir un infarto agudo del miocardio cuando sufren alguna cardiopatía;
cumpliéndose de esta forma el objetivo general planteado, ya que:
1. Con la introducción de estrategias en la codificación de la función de evaluación y el
decremento de la exploración en el espacio de soluciones los algoritmos que se proponen
en la tesis, para selección de rasgos, logran aumento significativo de la enficiencia con
respecto al costo en tiempo de ejecución.
2. Como una cuestión importante en esta investigación se ha explicado y validado cómo
extender el algoritmo original ACO-RST-FSP a partir de un ACO multicolonias con
intercambios "frecuentes" de feromona, donde cada colonia representa un algoritmo ACO
resolviendo un problema con un comportamiento colaborativo entre hormigas de otras
colonias; convirtiéndolo en un novedoso algoritmo de selección de rasgos en contexto
distribuido.
3. Los algoritmos propuestos han sido aplicados, con resultados favorables, en la solución
del problema de la selección de riesgos relevantes para el pronóstico de infarto agudo del
miocardio en pacientes con cardiopatías. De las conclusiones de esta aplicación se
destaca que:
a. La detección de reductos comunes logra evadir los “sesgos municipales”, y
obtener “reductos-consenso”, que permiten obtener de forma unificada buenos
resultados al aplicar técnicas de clasificación, facilitando la generalización de su
implementación práctica.
Conclusiones
82
b. Cualquiera de los reductos de longitud mínima facilitan a especialistas
cardiólogos qué preguntas realizar acerca de variables originales con potencia
suficiente para un buen pronóstico.
Recomendaciones
83
RECOMENDACIONES
1. Adaptar el algoritmo D.ACO-RST-FSP utilizando una heurística más informada desde el
punto de vista de aprovechar información sobre los datos en fuentes de datos distribuidas.
2. Analizar el efecto de una actualización controlada de la feromona tanto en su rol como
metainformación compartida por los algoritmos en contexto distribuido como estrategia
de búsqueda local en la construcción de los reductos.
3. A partir de que ambos algoritmos (no distribuido o distribuido) encuentran reductos
comunes, se recomienda la aplicación de un algoritmo de clasificación en contexto
distribuido.
4. Estudiar el efecto de otros valores para las combinaciones de los parámetros ,,, 0q
Referencias
84
REFERENCIAS
Abraham, A., Grosan, C., & Ramos, V. (Eds.). (2006). Swarm Intelligence in Data Mining (Vol.
34): Springer.
Aflori, C., & Leon, F. (2004). Efficient Distributed Data Mining using Intelligent Agents. Paper
presented at the Proceedings of the 8th International Symposium on Automatic Control
and Computer Science.
Al-Ani, A. (2005). Feature subset selection using ant colony optimization. Int. Journal of
Computational Intelligence, 2, 53-58.
Aljanaby, A., Ku-Mahamud, K. R., & Norwawi, N. M. (2010). Interacted Multiple Ant Colonies
Optimization Approach to Enhance the Performance of Ant Colony Optimization
Algorithms. Computer and Information Science, 3(1), 1-29.
Almuallim, H., & Dietterich, T. (1992). Efficient algorithms for identifying relevant features.
Paper presented at the 9th Canadian Conferece on Artificial Intelligence.
Almuallim, H., & Dietterich, T. (1994). Learning boolean concepts in the presence of many
irrelevant features. Artificial Intelligence, 69(1-2), 279-305.
Alpigini, J. J., Peters, J. F., Skowronek, J., & Zhong, N. (Eds.). (2002). Rough Sets and Current
Trends in Computing: Third International Conference, RSCTC 2002 (Vol. LNCS 2475).
Malvern, PA, USA: Springer.
Amir, C., Badr, A., & Farag, I. (2007). A fuzzy logic controller for ant algorithms. Computing
and Information Systems, 11(2), 26-34.
Anghinolfi, D., Boccalatte, A., Paolucci, M., & Vecchiola, C. (2008). Performance evaluation of
an adaptive ant colony optimization applied to single machine scheduling. Paper
presented at the Simulated Evolution and Learning, 7th International Conference, SEAL
2008.
Angus, D., & Woodward, C. (2009). Multiple objective ant colony optimisation. . Swarm
Intelligence, 3, 69-85.
Aounallah, M., & Mineau, G. W. (2007). Distributed Data Mining: Why Do More Than
Aggregating Models. Paper presented at the Proceedings of the 20th International Joint
Conference on Artificial Intelligence.
Arco, L., & Bello, R. (2006). On clustering validity measures and the Rough Set Theory. Paper
presented at the 5th Mexican International Conference on Artificial Intelligence, IEEE
Computer Society Press
Balamurugan, S. A. A., & Rajaram, R. (2009). Effective and Effcient Feature Selection for
Large-scale Data Using Bayes' Theorem. International Journal of Automation and
Computing, 6(1), 62-71.
Battiti, R. (1994). Using mutual information for selecting features in supervised neural net
learning. IEEE Transaction on Neural Networks, 5(4), 537-550.
Referencias
85
Bazan, J., & Son, N. H. (2003). A View on Rough Set Concept Approximations. Rough Sets,
Fuzzy Sets, Data Mining, and Granular Computing. Paper presented at the 9th
International Conference, RSFDGRC2003, Chongqing, China.
Bazan, J. G., & Szczuka, M. (2005). The Rough Set Exploration System. Transactions on Rough
Sets III(Lecture Notes in Computer Science 3400), 37-56.
Belanche, L., Molina, L. C., & Nebot, A. (2002). Feature Selection Algorithms: A Survey and
Experimental Evaluation. Paper presented at the 2002 IEEE International Conference on
Data Mining (ICDM’02), Maebashi City, Japan.
Bell, D., & Guan, J. (1998). Computational methods for rough classification and discovery.
Journal of ASIS, 49(5), 403-414.
Bell, D., & Wang, H. (2000). A formalism for relevance and its application in feature subset
selection. . Machine Learning, , 41(2), 175-195.
Bello, R., Gómez, Y., Caballero, Y., Nowe, A., & Falcón, R. (2009). Rough Sets and Evolutionary
Computation to Solve the Feature Selection Problem. In A. Abraham, R. Falcon & R. Bello
(Eds.), Rough Set Theory: A True Landmark in Data Analysis (Vol. 174, pp. 235-260):
Springer Berlin / Heidelberg.
Bello, R., Gómez, Y., Nowé, A., & García, M. M. (2007). Two Step Particle Swarm
Optimization to Solve the Feature Selection Problem. Paper presented at the Seventh
International Conference on Intelligent Systems Design and Applications.
Bello, R., Nowé, A., Caballero, Y., Gómez, Y., & Vrancx, P. (2005). A Model based on Ant
Colony System and Rough Set Theory to Feature Selection. Paper presented at the
Genetic and Evolutionary Computation Conference (GECCO05), Washington DC, USA.
Blake, C. L., & Merz, C. J. (1998). UCI repository of machine learning databases. from
http://www.ics.uci.edu/~mlearn/MLRepository.html:
Blum, A., & Langley, P. (1997). Selection of relevant features and examples in machine
learning. Artificial Intelligence, 97(1-2), 245-271.
Caballero, Y., & Bello, R. (2006). Two new feature selection algorithms with Rough Sets Theory.
Paper presented at the Artificial Intelligence in Theory and Practice, IFIP 19th World
Computer Congress, Santiago, Chile.
Caballero, Y., Bello, R., Arco, L., Garcia, M. M., & Ramentol, E. (2010). Knowledge Discovery
Using Rough Set Theory. In J. Koronacki, Z. W. Ras, S. T. Wierzchon & J. Kacprzyk
(Eds.), Advances in Machine Learning I (Vol. 262, pp. 367-383): Springer.
Cáceres, A. Y. P. (2009). Desarrollo de meta-heurísticas poblacionales para la solución de
problemas complejos. Universidad Central "Marta Abreu" de Las Villas, Santa Clara.
Carreira-Perpinñan, M. A. (2001). Continuous latent variable models for dimensionality
reduction and sequential data reconstruction., University of Sheffield, UK.
Caruana, R., & Freitag, D. (1994). Greedy attribute selection. Paper presented at the 11th Int.
Conf. on Machine Learning.
Referencias
86
Chávez, M. d. C. (2009). Modelos de redes bayesianas en el estudio de secuencias genómicas y
otros problemas biomédicos. Universidad Central "Marta Abreu" de Las Villas, Santa
Clara, Cuba.
Chen, Y., Miao, D., & Wang, R. (2010). A rough set approach to feature selection based on ant
colony optimization. Pattern Recognition Letters, 31, 226-233.
Chen, Y. W., & Lin, C. J. (2006). Combining SVMs with various feature selection strategies.
Feature extraction, foundations and applications: Springer-Verlag, Berlin.
Choubey, S. K. (1996). A comparison of feature selection algorithms in the context of rough
classifiers. Paper presented at the Fifth IEEE International Conference on Fuzzy Systems.
Chouchoulas, A., & Shen, Q. (1999). A rough set-based approach to text classification. Lectures
Notes in Artificial Intelligence, 1711, 118-127.
Chouchoulas, A., & Shen, Q. (2001). Rough set-aided keyword reduction for text categorisation.
Applied Artificial Intelligence, 15(9), 843-873.
Chu, W., Keerthi, S. S., Ong, C. J., & Ghahramani, Z. (2006). Bayesian Support Vector
Machines for Feature Ranking and Selection. Studies in Fuzziness and Soft Computing,
Volume 207, 403-418.
Comon, P. (1994). Independent component analysis: A new concept. Signal Processing, 36, 287-
314.
Cox, T. F., & Cox, M. A. A. (1994). Multidimensional Scaling. London: Chapman & Hall.
Crawford, B., & Castro, C. (2006). Ant Colonies using Arc Consistency Techniques for the Set
Partitioning Problem. LNAI 4183, 45-55.
Dash, M., & Liu, H. (1997). Feature selection for classification. Intelligent Data Analysis, 1(1-4),
131-156.
Dash, M., Liu, H., & Motoda, H. (2000). Consistency based feature selection. Paper presented at
the Pacific-Asia Conf. on Knowledge Discovery and Data Mining.
Deogun, J. S. (1998). Feature selection and effective classifiers. Journal of ASIS, 49(5), 423-434.
Deogun, J. S. e. a. (1995). Exploiting upper approximations in the rough set methodology. Paper
presented at the First International Conference on Knowledge Discovery and Data
Mining, Canada.
Devijver, P., & Kittler, J. (1982a). Pattern Recognition: A Statistical Approach. Prentice Hall.
Devijver, P., & Kittler, J. (1982b). Statistical Pattern Recognition.: Prentice Hall, London, GB.
Doak, J. (1992). An evaluation of feature selection methods and their application to computer
security. Davis, California: University of California, Department of Computer Science.
Doerr, B., Neumann, F., Sudholt, D., & Witt, C. (2007). On the Runtime Analysis of the 1-ANT
ACO Algorithm. Paper presented at the GECCO 2007.
Dorigo, M. (1992). Optimization, Learning and Natural Algorithms (in Italian). PhD thesis.,
Politecnico di Milano.
Referencias
87
Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. Computational
Intelligence, 1(4), 28-39.
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: a survey. Theory and Computer
Science, 344(2-3), 243-278.
Dorigo, M., Caro, G. D., & Gambardella, L. M. (1999). Ant algorithms for discrete optimization.
Artificial Life, 5(2), 137-172.
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem.
Biosystems, 43(2), 73-81.
Dorigo, M., & Gambardella, L. M. (1997). Ant Colony System: A cooperative learning approach
to the traveling salesman problem. IEEE Transactions on Evolutionary Computation,
1(1), 53-66.
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The Ant System: Optimization by a colony of
cooperating agents. IEEE Transactions on Systems Man, and Cybernetics, Part B 26(1),
29-41.
Dorigo, M., & Stutzle, T. (2003). The ant colony optimization metaheuristic algorithms,
applications, and advances. In F.Glover & G. A. Kochenberger (Eds.), Handbook of
Metaheuristics (pp. 251-258): Kluwer.
Dorigo, M., & Stutzle, T. (2004). Ant Colony Optimization. Cambridge Massachussetts: MIT
Press.
Droste, S., Jansen, T., & Wegener, I. (2002). On the analysis of the (1+1) evolutionary
algorithm. Theoretical Computer Science, 276, 51-81.
Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern Classification (2nd Edition): Wiley-
Interscience.
Düntsch, I., & Gediga., G. (2000). Rough Set Data Analysis: A road to non-invasive knowledge
discovery.: Methodos Publishers (UK).
Ellabib, I., Calamai, P., & Basir, O. (2007). Exchange strategies for multiple ant colony system.
Information Sciences: an International Journal, 177(5), 1248-1264.
Fayyad, U., Piatetsky-Shapiro, G., & Smyth, P. (1996). From data mining to knowledge
discovery in databases. Artificial Intelligence Magazine, 17(3), 37-54.
Firpi, H., & Goodman, E. (2004). Swarmed feature selection. Paper presented at the Proceedings
of the 33rd Applied Imagery Pattern Recognition Workshop (AIPR 2004).
Forman, G. (2003). An extensive empirical study of feature selection metrics for text
classification. Journal of Machine Learning Research, 3, 1289-1305.
Gadat, S., & Younes, L. (2007). A Stochastic Algorithm for Feature Selection in Pattern
Recognition. Journal of Machine Learning Research 8, 509-547.
Gambardella, L. M., Taillard, È. D., & Dorigo, M. (1999). Ant colonies for the Quadratic
Assigment Problem. Journal of the Operational Research Society, 50(2), 167-176.
Referencias
88
Gamberger, D., & Lavrac., N. (1997). Conditions for ocam’s razor applicability and noise
elimination. Paper presented at the 9th European Conf. on Machine Learning.
García-Martínez, C., Cordón, O., & Herrera, F. (2007). A taxonomy and an empirical analysis of
multiple objective ant colony optimization algorithms for the bi-criteria tsp. European
Journal of Operational Research, 180 (1), 116-148.
García, S., & Herrera, F. (2008). An Extension on “Statistical Comparisons of Classifiers over
Multiple Data Sets” for all Pairwise Comparisons. Journal of Machine Learning
Research, 9, 2677-2694.
Gómez, Y., Bello, R., Nowé, A., Puris, A., & García, M. M. (2008). Two Step Swarm
Intelligence to Solve the Feature Selection Problem. Journal of Universal Computer
Science., Vol. 14(No. 15), pp. 2582-2596.
Grabowski, A. (2003). Basic Properties of Rough Sets and Rough Membership Function.
Journal of Formalized Mathematics, 15.
Grau, R. (2009). Estadística Aplicada con Ayuda de Paquetes de Software. Editorial
Universitaria de Guadalajara, Segunda edición.
Greco, S., & Inuiguchi, M. (2003). Rough Sets and Gradual Decision Rules. Rough Sets, Fuzzy
Sets, Data Mining, and Granular Computing. Paper presented at the 9th International
Conference, RSFDGRC2003, Chongqing, China.
Grzymala-Busse, J. W., & Siddhaye, S. (2004). Rough set approaches to rule induction from
incomplete data. Paper presented at the 10th International Conference on Information
Processing and Management of Uncertainty in Knowledge-Bases systems IPMU2004,
Perugia, Italy.
Gutjahr, W. J. (2007). First steps to the runtime complexity analysis of ant colony optimization. .
Computers and Operations Research.
Guyon, I., & Eliseeff, A. (2003). An Introduction to Variable and Feature Selection. Journal of Machine
Learning Research, 3, 1157–1182.
Guyon, I., & Elisseeff, A. (2006). An Introduction to Feature Extraction Feature Extraction:
Foundations and Applications (Vol. 207, pp. 1-25).
Hall, M. (2000). Correlation-based feature selection for discrete and numeric class machine
learning. Paper presented at the 17th International Conference on Machine Learning.
Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009). The
WEKA Data Mining Software: An Update. SIGKDD Explorations, 11(1), 10-18.
Heinonen, J., & Pettersson, F. (2007). Hybrid ant colony optimization and visibility studies
applied to a job-shop scheduling problem Applied Mathematics and Computation,
187(2), 989-998.
Huang, K. L., & Liao, C. J. (2008). Ant colony optimization combined with taboo search for the
job shop scheduling problem. Computers and Operations Research, 35( 4), 1030-1046.
Referencias
89
Hyvarinen, A., & Oja, E. (2000). Independent Component Analysis: A Tutorial. Neural
Networks, 13, 411-430.
Inza, I., naga, P. L., Blanco, R., & Cerrolaza, A. (2004). Filter versus wrapper gene selection
approaches in dna microarray domains. Artificial Intelligence in Medicine, 31, 91-103.
Jain, A., & Zongker, D. (1997). Feature selection: evaluation, application, and small sample
performance. IEEE Transactions on Pattern Analisys and Machine Intelligence., 19(2),
153-158.
Janson, S., Merkle, D., & Middendorf, M. (2005). Parallel Ant Colony Algorithms. In J. W. Sons
(Ed.), Parallel Metaheuristics (pp. 171-201).
Jasso-Luna, O., Sosa-Sosa, V., & Lopez-Arevalo, I. (2008). Global Classifier for Confidential
Data in Distributed Datasets. Paper presented at the Mexican International Conference
on Artificial Intelligence.
Jensen, R. (2005). Combining rough and fuzzy sets for feature selection. University of
Edinburgh.
Jensen, R., & Shen, Q. (2003). Finding Rough Set Reducts with Ant Colony Optimization. Paper
presented at the UK Workshop on Computational Intelligence.
Jensen, R., & Shen, Q. (2005). Fuzzy-Rough Data Reduction with Ant Colony Optimization.
Fuzzy Set and System, 149, 5-20.
Jong, J., & Wiering, M. (2001). Multiple ant colony system for the bus-stop allocation problem.
Paper presented at the Thirteenth Belgium-Netherlands Conference on Artificial
Intelligence (BNAIC'01).
K.Wang, & Sundaresh, S. (1998). Selecting features by vertical compactness of data. Feature
extraction, construction and selection. (pp. 71-84): Kluwer Academic Publishers.
Kargupta, H. (2003). Distributed Data Mining: Algorithms, systems and applications. In N. Ye
(Ed.), Data Mining Handbook.
Ke, L., Feng, Z., & Ren, Z. (2008). An efficient ant colony optimization approach to attribute
reduction in rough set theory. Pattern Recognition Letters, 29, 1351-1357.
Kennedy, J., & Eberhart, R. C. (1995). Particle swarm optimization. Paper presented at the IEEE
International Conference on Neural Networks, Piscataway, New York, USA.
Kira, K., & Rendell, L. (1992). A practical approach to feature selection. Paper presented at the
9th Int. Conf. on Machine Learning.
Kira, K., & Rendell., L. A. (1992). The feature selection problem: traditional methods and a new
algorithm. Paper presented at the AAAI-92.
Kohavi, R., & Frasca, B. (1994). Useful Feature Subsets and Rough Set Reducts. Paper presented
at the Third International Workshop on Rough Sets and Soft Computing.
Kohavi, R., & John, G. H. (1997). Wrappers for Feature Subset Selection. Artificial Intelligence,
97, 273-324.
Referencias
90
Komorowski, J., & Pawlak, Z. (1999). "Rough Set: A tutorial.". Rough Fuzzy Hybridization: A
new trend in decision making, 3-98.
Kononenko, I. (1994). Estimating attributes: Analysis and estensions of relief. Paper presented at
the European Conference on Machine Learning., Vienna.
Kudo, M., & Sklansky, J. (2000). Comparison of algorithms that select features for pattern
classifiers. . Pattern Recognition Letters, 33, 25-41.
Kudo, M., Somol, P., Pudil, P., Shimbo, M., & Sklansky, J. (2000). Comparison of classifier
specific feature selection algorithms. . Paper presented at the SSPR/SPR.
Lal, T. N., Chapelle, O., & Schölkopf, B. (2006). Combining a filter method with svms. Feature
extraction, foundations and applications: Springer-Verlag, Berling.
Langley, P. (1994). Selection of relevant features in machine learning. Paper presented at the
Procs. of the AAAI Fall Symposium on Relevance.
Lazo, M., Shulcloper, J. R., & cabrera, E. A. (2001). An overview of the evolution of the concept of
testor. Pattern Recognition, 34(4), 753-762.
Lee, H. D., Monard, M. C., Voltolini, R. F., Prati, R. C., & Chung, W. F. (2006). A Simple
Evaluation Model for Feature Subset Selection Algorithms. Inteligencia Artificial,
Revista Iberoamericana de Inteligencia Artificial, 32, 09-17.
Lee, W., Stolfo, S., & Mok, K. (2000). Adaptive intrusion detection: A data mining approach. AI
review, 14(6), 533-567.
Liu, H., & Motoda, H. (1998). Feature Selection for Knowledge Discovery and Data Mining:
Editorial Kluwer Academic Publishers.
Liu, H., & Motoda, H. (2007). Computational Methods of Feature Selection (Chapman &
Hall/Crc Data Mining and Knowledge Discovery Series): Chapman & Hall/CRC.
Liu, H., & Motoda, H. (Eds.). (2008). Computational Methods of Feature Selection. : Chapman
and Hall/CRC Press.
Liu, H., Motoda, H., & Dash, M. (1998). A monotonic measure for optimal feature selection.
Paper presented at the European Conf. on Machine Learning.
Liu, H., Motoda, H., & Yu, L. (2002). Feature selection with selective sampling. Paper presented
at the 19th International Conference on Machine Learning.
Liu, H., & Setiono, R. (1996). A probabilistic approach to feature selection: a filter solution.
Paper presented at the 13th International Conference on Machine Learning.
Liu, H., & Yu, L. (2005). Toward integrating feature selection algorithms for classification and
clustering. IEEE Trans. On knowledge and data enginnering., 17(3), 1-12.
Lorenzo-Fonseca, I., Maciá-Pérez, F., Mora-Gimeno, F. J., Lau-Fernández, R., Gil-Martínez-
Abarca, J. A., & Marcos-Jorquera, D. (2009). Intrusion Detection Method Using Neural
Networks Based on the Reduction of Characteristics. Paper presented at the IWANN
2009.
Referencias
91
Martens, D., Backer, M. D., Haesen, R., Baesens, B., & Holvoet, T. (2006). Ants Constructing
Rule-Based Classifiers. In A. Abraham, C. Grosan & V. Ramos (Eds.), Swarm
Intelligence in Data Mining (pp. 21-44).
Meiri, R., & Zahavi, J. (2006). Using simulated annelaling to optimize the feature selection
problem in marketing application. European Journal of Operational Research, 171(3),
842-858.
Melo, L., Pereira, F., & Costa, E. (2010). MC-ANT: a Multi-colony Ant Algorithm. Paper
presented at the Artificial Evolution (EA'09), Strasbourg, France.
Miao, D., & Hou, L. (2003). An Application of Rough Sets to Monk’s Problems Solving. Rough
Sets, Fuzzy Sets, Data Mining, and Granular Computing. Paper presented at the 9th
International Conference, RSFDGRC2003, Chongqing, China.
Middendorf, M., Reischle, F., & Schmeck, H. (2002). Multi Colony Ant Algorithms. Journal of
Heuristics (special issue on Parallel Meta-heuristics), 8(3), 305-320.
Midelfart, H., & Komorowski, J. (2003). Learning rough set classifiers from gene expression and
clinical data. Fundamenta Informaticae, 53, 155-183.
Molina, L., Belanche, L., & Nebot, A. (2002). Feature selection algorithms: A survey and
experimental evaluation. Paper presented at the International Conference on Data
Mining, ICDM-02.
Mucciarde, A., & Gose, E. (1971). A comparison of seven techniques for choosing subsets of
pattern recognition properties. IEEE Transactions on Computer, C-20(9), 1023-1031.
Naimi, H. M., & Taherinejad, N. (2009). New robust and efficient ant colony algorithms: Using
new interpretation of local updating process. Expert Systems with Applications, 36(1),
481-488.
Narendra, P., & Fukunaga, K. (1977). A branch and bound algorithm for feature subset selection.
. IEEE Transactions on Computer, C-26(9), 917-922.
Navarro, J. J. L. (2001). Selección de atributos en aprendizaje automático basada en teoría de la
información., Universidad de Las Palmas de Gran Canaria.
Neumann, F., & Witt, C. (2006). Runtime analysis of a simple Ant Colony Optimization
algorithm. Paper presented at the Proceeding of ISAAC ’06.
Nowé, A., Verbeeck, K., & Vrancx, P. (2004). Multi-type Ant Colony: The Edge Disjoint Paths
Problem. Paper presented at the Ants 2004, Brussels, Belgium.
Øhrn, A. (1999). Discernibility and Rough Sets in Medicine: Tools and Applications., Norwegian
University of Science and Technology, Department of Computer and Information
Science.
Øhrn, A., Komorowski, J., Skowron, A., & Synak., P. (1998). The ROSETTA software system.
In L. Polkowski & A. Skowron (Eds.), Rough Sets in Knowledge Discovery 1:
Methodology and Applications. Studies in Fuzziness and Soft Computing (Vol. 19, pp.
572-576). Heidelberg, Germany: Physica-Verlag.
Referencias
92
Ortega, P., Oliva, C., Ferland, J., & Cepeda, M. (2009). Multiple Ant Colony System for a VRP
with Time Windows and Scheduled Loading. Revista chilena de ingeniería, 17(3), 393-
403.
Pal, S. K., & Skowron, A. (1999). Rough Fuzzy Hybridization: A New Trend in Decision-
Making.
Palancar, J. H. (2004). Estado actual de la aplicación de la computación paralela a la Minería de
Datos.
Park, B., & Kargupta, H. (2002). Distributed Data Mining: Algorithms, Systems, and
Applications. In E. N. Ye (Ed.), The Handbook of Data Mining: Lawrence Erlbaum
Associates.
Parpinelli, R. S., Lopes, H. S., & Freitas, A. A. (2002). Data Mining with an Ant Colony
OptimizationAlgorithm. IEEE Transactions on Evolutionary Computation, 6, 321--332.
Parsons, S. (2006). Current approaches to handling imperfect information in data and
knowledges bases. IEEE Transaction On knowledge and data enginnering.
Pawlak, Z. (1982). Rough sets. International Journal of Information & Computer Sciences 11,
341-356.
Pawlak, Z. (1991). Rough Sets: Theoretical Aspects of Reasoning About Data. Dordrecht:
Kluwer Academic Publishing.
Piñero, P., & Arco, L. (2003). Two New Metrics for Feature Selection in Pattern Recognition.
Lectures Notes in Computer Science (LNCS 2905), 488-497.
Provost, F. (1999). Distributed Data Mining: Scaling up and beyond.
Pudil, P., Novovicová, J., & Kittler, J. (1994). Floating search methods in feature selection.
Pattern Recognition Letters, 15(11), 1119-1125.
Ruiz, R., Aguilar-Ruiz, J., & Riquelme, J. (2004). Wrapper for ranking feature selection. Paper
presented at the 5th International Conference on Intelligent Data Engineering and
Automated Learning (IDEAL’04).
Saeys, Y., Degroeve, S., & Peer, Y. V. d. (2006a). Feature Ranking Using an EDA-based
Wrapper Approach. StudFuzz 192, 243-257.
Saeys, Y., Degroeve, S., & Peer, Y. V. d. (2006b). Feature ranking using an EDA-based wrapper
approach; pp. 243-257 Towards a New Evolutionary Computation: Advances in Estimation of
Distribution Algorithms: Springer-Verlag Berlin Heidelberg.
Saeys, Y., Inza, I., & Larrañaga, P. (2007). A review of feature selection techniques in
bioinformatics. Bioinformatic, 23(19), 2507-2517.
Santiesteban, Y., & Pons, A. (2003). LEX: un nuevo algoritmo para el cálculo de los testores típicos.
Revista Ciencias Matemáticas, 21(1), 85 - 95.
Sheinvald, J., Dom, B., & Niblack, W. (1990). A modelling approach to feature selection. Paper
presented at the 10th Int. Conf. on Pattern Recognition.
Referencias
93
Siedlecki, W., & Sklansky, J. (1988). On automatic feature selection. Int. Journal of Pattern
Recognition and Artificial Intelligence., 2, 197-220.
Silva, J. C. d., Giannella, C., Bhargava, R., Kargupta, H., & Klusch, M. (2005). Distributed data
mining and agents. Engineering Applications of Artificial Intelligence, 18(7), 791-807.
Skowron, A. (1999). New directions in Rough Sets, Data Mining, and Granular Soft Computing.
Paper presented at the 7th International Workshop (RSFDGRC'99), Japan.
Skowron, A., & Peters, J. F. (2003). Rough Sets: Trends and Challenges. Paper presented at the
Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing 9th International
Conference, RSFDGRC 2003.
Stützle, T., & Hoos, H. (2000). MAX-MIN Ant System. Future Generation Computer Systems,
16(8), 889-914.
Stützle, T., López-Ibañez, M., Pellegrini, P., Maur, M., Oca, M. M. d., Birattari, M., et al. (2010).
Parameter Adaptation in Ant Colony Optimization. IRIDIA - Technical Report Series.
ISSN 1781-3794, TR/IRIDIA/2010-002.
Sugihara, K., & Tanaka, H. (2006). Rough Sets approach to information systems with interval
decision values in evaluation problems. Paper presented at the The International
Symposium on Fuzzy and Rough Sets. ISFUROS2006, Santa Clara, Cuba.
Sun, Y., & Li, J. (2006). Iterative relief for feature weighting. Paper presented at the 23rd
International Conference on Machine Learning.
Swiniarski, R. W., & Skowron, A. (2003). Rough set methods in feature selection and
recognition. . Pattern Recognition Letters., 24(6), 833-849.
Thangavel, K., & Pethalakshmi, A. (2009). Dimensionality reduction based on rough set theory:
A review. Applied Soft Computing, 9, 1-12.
Tsang, C.-H., & Kwong, S. (2006). Ant Colony Clustering and Feature Extraction for Anomaly
Intrusion Detection. In A. Abraham, C. Grosan & V. Ramos (Eds.), Swarm Intelligence
in Data Mining.
Tsumoto, S. (2003). Automated extraction of hierarchical decision rules from clinical databases
using rough set model. Expert systems with Applications, 24, 189-197.
Vinterbo, S., & Øhrn, A. (2000). Minimal approximate hitting sets and rule templates
International Journal of Approximate Reasoning, 25(2), 123-143.
Wang, X., Yang, J., Teng, X., Xia, W., & Jensen, R. (2007). Feature selection based on rough
sets and particle swarm optimization. Pattern Recognition Letters, 28(4), 459-471.
Weston, J., Mukherjee, S., Chapelle, O., Pontil, M., & Poggio., T. (2001). Feature selection in
SVMs. . In T. Leen, T. Dietterich, and V. Tresp (Ed.), Advances in Neural Information
Processing Systems. (Vol. 13): MIT Press.
Wettschereckk, D., Aha, D. W., & Mohri, T. (1997). A review and empirical evaluation of
feature weighting methods for a class of lazy learning algorithms. Artificial Intelligence
Review, 11(1-5), 273-314.
Referencias
94
Wilford, I., Rosete, A., & Rodríguez, A. (2009a). Análisis de Información Clínica mediante
técnicas de Minería de Datos. RevistaeSalud, 5(20),
Wilford, I., Rosete, A., & Rodríguez, A. (2009b). Aplicación de la Minería de Datos para el
análisis de información clínica. Estudio Experimental en cardiopatías isquémicas. Revista
Cubana de Informática Médica, 9(1).
Witten, I. H., & Frank, E. (2005). Data Mining: Practical Machine Learning Tools and
Techniques. (2nd ed.): Morgan Kaufmann.
Wolpert, D. H., & Macready, W. G. (1997). No Free Lunch Theorems for Optimization. IEEE
Transactions of Evolutionary Computation, 1, 67-82.
Wong, K. Y., & See, P. C. (2009). A new minimum pheromone threshold strategy (MPTS) for
max-min ant system Jornal Applied Soft Computing, 9(3), 882-888.
Wu, Z., Zhao, N., Ren, G., & Quan, T. (2009). Population declining ant colony optimization
algorithm and its applications. Expert Systems with Applications, 36(3), 6276-6281.
Xue, L., Godden, J., Gao, H., & Bajorath, J. (1999). Identification of a Preferred Set of
Molecular Descriptors for Compound Classification Based on Principal Component
Analysis. J. Chem. Inf. Comput. Sci., 39, 669-704.
Ye, N. (Ed.). (2003). The handbook of data mining. New Jersey: Lawrence Erlbaum Associates,
Inc., Publishers.
Yu, L., & Liu, H. (2004). Effient feature selection via analysis of relevance and redundancy.
Journal of machine learning research, 5, 1205-1224.
Zhang, S., Zhang, C., & Yang, Q. (2003). Data preparation for data mining. . Applied Artificial
Intelligence, 17((5-6)), 375-381.
Zhao, Y., & Zhang, H. (2003). Classification Using the Variable Precision Rough Set. Rough
Sets, Fuzzy Sets, Data Mining, and Granular Computing. Paper presented at the 9th
International Conference, RSFDGRC2003, Chongqing, China.
Zhong, N., & Dong, J. (2001). Using Rough sets with heuristics for feature selection. Journal of
Intelligent Information Systems 16, 199-214.
Ziarko, W. (2002). Rough set approaches for discovering rules and attribute dependencies. In W.
Klösgen & J. M. Zytkow (Eds.), Handbook of data mining and knowledge discovery (pp.
328-339): Oxford University Press, Inc.
Producción científica del autor sobre el tema de la tesis
95
PRODUCCIÓN CIENTÍFICA DEL AUTOR SOBRE EL TEMA DE LA TESIS
REVISTAS INTERNACIONALES
1. Yudel Gómez, Rafael Bello, Ann Nowé, Amilkar Puris, María M. García. Two Step Swarm Intelligence to Solve the Feature Selection Problem. Journal of Universal Computer Science, Vol. 14(15). p: 2582—2596. 2008. ISSN 0948-695x Online edition: ISSN 0948-6968
CONGRESOS INTERNACIONALES
2. Yudel Gómez, Rafael Bello, Ann Nowé, Frank Bosmans. Multi-colony ACO and Rough Set Theory to Distributed Feature Selection Problem. Sigeru Omatu, Miguel Rocha, José Bravo, Florentino Fernández Riverola, Emilio Corchado, Andrés Bustillo, Juan M. Corchado (Eds.): Distributed Computing, Artificial Intelligence, Bioinformatics, Soft Computing, and Ambient Assisted Living, 10th International Work-Conference on Artificial Neural Networks, IWANN 2009 Workshops, Salamanca, Spain, June 10-12, 2009. Proceedings, Part II. LNCS 5518 Springer 2009, ISBN 978-3-642-02480-1. ISSN 0302-9743 (Print) 1611-3349 (Online)
3. Yudel Gómez, Rafael Bello, Ann Nowé, Frank Bosmans. Speeding-up ACO implementation by decreasing the number of heuristic function evaluations in feature selection problem. Juan M. Corchado, Juan Francisco de Paz, Miguel Rocha, Florentino Fernández Riverola (Eds.): 2nd International Workshop on Practical Applications of Computational Biology and Bioinformatics, Salamanca, Spain, 22th-24th October 2008. Advances in Soft Computing 49 Springer 2009, ISBN 978-3-540-85860-7. ISSN 1615-3871 (Print) 1860-0794 (Online)
4. Rafael Bello, Yudel Gómez, Yailé Caballero, Ann Nowé and Rafael Falcón. Rough Sets and Evolutionary Computation to Solve the Feature Selection Problem. A. Abraham, R. Falcon, and R. Bello (Eds). Rough Set Theory: A True Landmark in Data Analysis. Studies in Computational Intelligence, Vol. 174 p. 235-260. Springer Berlin / Heidelberg. 2009. ISBN: 978-3-540-89920-4. ISSN 1860-949X (Print) 1860-9503 (Online).
5. Rafael Bello, Yudel Gómez, Ann Nowé, María M. García. Two Step Particle Swarm Optimization to Solve the Feature Selection Problem. 7th International
Producción científica del autor sobre el tema de la tesis
96
Conference on Intelligent Systems Design and Applications ISDA’07. Río Janeiro, Brasil. 2007.
6. Rafael Bello, Ann Nowé, Yailén Caballero, Yudel Gómez, Peter Vrancx. A Model Based on Ant Colony System and Rough Set Theory to Feature Selection. Hans-Georg Beyer, Una-May O'Reilly (Eds.): Genetic and Evolutionary Computation Conference, GECCO 2005, Proceedings, Washington DC, USA, June 25-29, 2005. ACM 2005, ISBN 1-59593-010-8.
7. Rafael Bello, Amilkar Puris, Rafael Falcón, Yudel Gómez: Feature Selection through Dynamic Mesh Optimization. José Ruiz-Shulcloper, Walter G. Kropatsch (Eds.): Progress in Pattern Recognition, Image Analysis and Applications, 13th Iberoamerican Congress on Pattern Recognition, Havana, Cuba, September 9-12, 2008. Proceedings LNCS 5197, Springer, ISBN 978-3-540-85919-2
8. Yudel Gómez, Rafael Bello, Ann Nowé. Runtime reduction in feature selection problem when ACO-RST model is used. XIV Latin Ibero-American Congress on Operations Research (CLAIO 2008). Cartagena, Colombia. 2008.
9. Rafael Bello, Ann Nowé, Yailén Caballero, Yudel Gómez, Peter Vrancx. Using Ant Colony System Meta-heuristic and Rough Set Theory to Feature Selection. 6th Metaheuristics International Conference MIC2005. Vienna, Austria. 2005.
10. Rafael Bello, Ann Nowé, Yailén Caballero, Yudel Gómez. Using ACO and Rough Set Theory to Feature Selection. WSEAS MultiConference in Lisbon: EVOLUTIONARY COMPUTING 2005. Lisbon, Portugal. 2005.
CONGRESOS NACIONALES
11. Yudel Gómez, Enrique Casanovas, Rafael Bello, Ann Nowé. Distributed Data Mining Applied to Feature Selection Problem. In VII Congreso Nacional de Reconocimiento de Patrones, RECPAT 2009. 2009. Santiago de Cuba: Ediciones UO. ISBN: 978-959-207-381-4
12. Yudel Gómez, Rafael Bello, Ann Nowé. Saving computational time in feature selection problem when ACO-RST model is used. FIE’08. Santiago de Cuba, Cuba. 2008.
13. Yudel Gómez, Ricardo Grau, Enrique Casanovas, Rafael Bello, Ann Nowé. Técnicas de selección de rasgos aplicadas al pronóstico de infarto agudo del miocardio en pacientes cardiópatas. VII Conferencia Internacional de Ciencias Empresariales. III Simposio Internacional de Informática Empresarial (Business Informatics). Editorial Feijóo. ISBN: 978-959-250-606-0
Anexos
97
ANEXOS
Anexo 1. Características de los conjuntos de datos
Conjuntos de
Datos.
Número
Clases
Número
Instancias
Rasgos Atributos a eliminar
Total Numéricos Nominales
Breast Cancer 2 699 10 9 1 1(6-Bare_Nuclei)
Dermatology 6 358 34 33 1 -
Mushroom 2 8124 23 0 23 1(11-stalk-root)
Segment 7 2310 20 19 1 -
Vowel 11 990 14 13 1 -
Splice 3 3190 62 0 62 1(1-Instance_name)
LedJen 10 2000 24 0 24 -
Vehicle 4 846 19 18 1 -
Ionosphere 2 351 35 34 1 -
Breast Cancer
W 2 699 9 9 0 -
HeartJen 2 294 14 0 14 -
LungJen 5 56 32 0 56 -
La columna atributos a eliminar se refiere a los rasgos que han sido eliminados de los conjuntos
de datos para poder aplicar los algoritmos. Para Breast Cancer y Mushroom se han eliminado
debido a que tenían ausencia de información en un número considerable de objetos. El rasgo
Instance_name fue eliminado de Splice porque constituye un identificador de objetos, con las
consecuencias negativa que esto influye sobre métodos de aprendizaje automatizado.
Anexos
98
Anexo 2. Resultados experimentales de la estrategia de ahorro
HeartJen
Tabla A2.1: Número de subconjuntos evaluados en cada ciclo
Ciclo
(i)
Calculados
Expresión (1.8)
(ii)
Almacenados en la
estructura de datos
(iii)
Total de subconjuntos
candidatos
(iv)
1 1372 2029 2835
2 385 2301 2615
3 415 1842 2117
4 45 1533 1696
5 265 2255 2538
6 35 1666 1840
7 190 1842 2068
8 55 1752 1939
9 150 1904 2127
10 70 2162 2393
11 0 1715 1886
12 165 2443 2723
13 0 1783 1961
14 25 1878 2071
15 55 1862 2060
Figura A2.1: Evaluaciones de subconjuntos
Anexos
99
LedJen
Tabla A2.2: Número de subconjuntos evaluados en cada ciclo
Ciclo
(i)
Calculados
Expresión (1.8)
(ii)
Almacenados en la
estructura de datos
(iii)
Total de subconjuntos
candidatos
(iv)
1 7225 14118 17008
2 1449 11526 11733
3 483 8134 8203
4 1596 10514 10742
5 399 9106 9163
6 602 7424 7510
7 49 6914 6921
8 0 7052 7052
9 259 9250 9287
10 0 6778 6778
11 56 7080 7088
12 0 10830 10830
13 588 10280 10364
14 329 10624 10671
15 105 9732 9747
Figura A2.2: Evaluaciones de subconjuntos
Anexos
100
LungJen
Tabla A2.3: Número de subconjuntos evaluados en cada ciclo
Ciclo
(i)
Calculados
Expresión (1.8)
(ii)
Almacenados en la
estructura de datos
(iii)
Total de subconjuntos
candidatos
(iv)
1 32436 66734 82327
2 30282 50866 60711
3 24108 64105 74303
4 14665 75848 85737
5 14525 60312 68625
6 7308 49072 55127
7 5418 65348 72734
8 5817 69657 77536
9 9100 63815 71626
10 6860 73733 82184
11 4011 43138 48082
12 1169 50592 55834
13 7476 71056 79336
14 1435 67238 74187
15 3136 80943 89530
Figura A2.3: Evaluaciones de subconjuntos