CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DO

Transcrição

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial
DISSERTAÇÃO
apresentada ao CEFET-PR
para obtenção do título de
MESTRE EM CIÊNCIAS
por
RAFAEL STUBS PARPINELLI
UM ALGORITMO BASEADO EM COLÔNIAS DE
FORMIGAS PARA CLASSIFICAÇÃO EM DATA MINING
Banca Examinadora:
Presidente e Orientador:
Prof. Dr. HEITOR SILVÉRIO LOPES
CEFET-PR
Examinadores:
Prof. Dr. MAURÍCIO FERNANDES FIGUEIREDO
UEM
Prof. Dr. ALEX ALVES FREITAS (co-orientador)
PUC
Prof. Dr. LUIZ CARLOS DE ABREU RODRIGUES
Curitiba, 17 de Agosto de 2001.
CEFET-PR
RAFAEL STUBS PARPINELLI
UM ALGORITMO BASEADO EM COLÔNIAS DE FORMIGAS PARA
CLASSIFICAÇÃO EM DATA MINING
Dissertação apresentada ao Programa de PósGraduação em Engenharia Elétrica e Informática
Industrial do Centro Federal de Educação
Tecnológica do Paraná, como requisito parcial
para a obtenção do título de “Mestre em
Ciências” – Área de Concentração: Informática
Industrial
Orientador: Prof. Dr. Heitor Sivério Lopes
Co-orientador: Prof. Dr. Alex Alves Freitas
Curitiba
2001
AGRADECIMENTOS
Aos professores do CPGEI, pelos ensinamentos.
Aos orientadores e amigos Heitor e Alex, pelo apoio e direcionamento na pesquisa.
Aos colegas de laboratório, Cézar, Célia, Miguel, Valfredo, Heitor, Igor, Ivana e
Alceo, pela agradabilíssima convivência.
Aos amigos Igor, Rosalba, Cézar, Célia, Elaine, Morgana, Mauren, Edson, Fernando,
Shirata, Robson, Charles e Celso, pelos vários momentos alegres de descontração.
Aos meus queridos pais, Jair e Natalina, minhas irmãs Roberta, Rejane e Carolina, e à
todos meus parentes (avós, avôs, tios, tias, primos, primas, ...), pelo total apoio.
iii
iv
SUMÁRIO
LISTA DE ILUSTRAÇÕES.................................................................................. vi
LISTA DE TABELAS........................................................................................... vii
LISTA DE ABREVEATURAS E SIGLAS........................................................ viii
RESUMO ................................................................................................................ ix
ABSTRACT .............................................................................................................. x
1
INTRODUÇÃO ....................................................................................................... 1
1.1 MOTIVAÇÃO................................................................................................... 1
1.2 OBJETIVO ........................................................................................................ 2
1.3 DESCRIÇÃO DO CONTEÚDO....................................................................... 3
2
OTIMIZAÇÃO POR COLÔNIAS DE FORMIGAS .......................................... 5
2.1 INSETOS SOCIAIS .......................................................................................... 5
2.2 COLÔNIAS DE FORMIGAS REAIS............................................................... 8
2.3 COLÔNIAS DE FORMIGAS ARTIFICIAIS................................................... 9
2.3.1 Similaridades e diferenças com as colônias reais ...................................... 10
2.3.2 Desenvolvimento de um algoritmo ACO................................................... 13
3
DATA MINING...................................................................................................... 15
3.1 DESCOBERTA DE CONHECIMENTO........................................................ 15
3.2 CARACTERÍSTICAS DOS ALGORITMOS DE DATA MINING ................ 15
3.3 TAREFA DE CLASSIFICAÇÃO ................................................................... 18
3.4 BIAS INDUTIVO - DEFINIÇÃO.................................................................... 20
4
UM
ALGORITMO
DE
COLÔNIA
DE
FORMIGAS
PARA
CLASSIFICAÇÃO EM DATA MINING.................................................................... 21
4.1 UMA VISÃO GERAL DO ANT-MINER........................................................ 21
4.2 CONSTRUÇÃO DAS REGRAS .................................................................... 25
4.3 FUNÇÃO HEURÍSTICA ................................................................................ 26
4.4 PODA DAS REGRAS..................................................................................... 28
4.5 ATUALIZAÇÃO DO FEROMÔNIO ............................................................. 29
4.5.1 Aumento da quantidade de feromônio nos termos usados.................... 30
4.5.2 Decréscimo da quantidade de feromônio nos termos não usados......... 31
4.6 USANDO AS REGRAS DESCOBERTAS .................................................... 32
4.7 PARÂMETROS DO SISTEMA...................................................................... 32
v
5
RESULTADOS E ANÁLISES ............................................................................. 35
5.1 BASES DE DADOS E MÉTODO DE DISCRETIZAÇÃO UTILIZADO..... 35
5.2 PARÂMETROS DO SISTEMA UTILIZADOS NOS EXPERIMENTOS .... 37
5.3 CRITÉRIOS DE AVALIAÇÃO...................................................................... 38
5.4 ALGORITMOS UTILIZADOS NA COMPARAÇÃO DOS RESULTADOS ..
................................................................................................................... 40
5.4.1 Algoritmo C4.5 ......................................................................................... 40
5.4.2 Algoritmo CN2 .......................................................................................... 41
5.4.3 Algoritmo MLP-BP ................................................................................... 41
5.5 TAXA DE ACERTO....................................................................................... 42
5.5.1 Análise dos resultados ............................................................................... 42
5.6 SIMPLICIDADE DAS REGRAS DESCOBERTAS...................................... 44
5.6.1.1 Ant-Miner vs. C4.5 ............................................................................. 45
5.6.1.2 Ant-Miner vs. CN2.............................................................................. 46
5.7 INFLUÊNCIA DA PODA NO ALGORITMO ANT-MINER ......................... 47
5.8 INFLUÊNCIA DO FEROMÔNIO.................................................................. 48
5.9 SENSIBILIDADE DO ANT-MINER AO AJUSTE DE PARÂMETROS ...... 50
6
CONCLUSÕES E TRABALHOS FUTUROS ................................................... 53
REFERÊNCIAS BIBLIOGRÁFICAS........................................................................ 55
vi
LISTA DE ILUSTRAÇÕES
1. Formigas encontrando o caminho mais curto ao redor de um obstáculo............................. 8
2. Exemplo de tarefa de classificação .................................................................................... 19
3. Uma descrição do algoritmo Ant-Miner............................................................................. 22
4. Descrição do procedimento de poda .................................................................................. 29
5. Exemplo de árvore de decisão produzida na discretização de um atributo contínuo ........ 37
vii
viii
LISTA DE TABELAS
1. Bases de dados utilizadas nos experimentos...................................................................... 35
2. Taxa de acerto (%) do Ant-Miner, C4.5, CN2 e MLP-BP ................................................. 42
3. Simplicidade das listas de regras descobertas pelo Ant-Miner, C4.5 e CN2 ..................... 44
4. Resultados do Ant-Miner sem podar as regras................................................................... 47
5. Resultados do Ant-Miner sem a influência do feromônio.................................................. 49
6. Taxa de acerto do Ant-Miner com diferentes valores para os parâmetros ......................... 51
ix
x
LISTA DE ABREVISTURAS E SIGLAS
ACO
-
Ant Colony Optimization (Otimização por Colônias de
Formigas)
Ant-Miner
-
Ant Colony-based Data Miner (Minerador de Dados baseado em
Colônias de Formigas)
C4.5
-
Algoritmo de indução de regras
CN2
-
Algoritmo de indução de regras
FN
-
Falso Negativo
FP
-
Falso Positivo
KDD
-
Knowledge Discovery in Databases (Descoberta de
Conhecimento em Bases de Dados)
Max_casos_n_cobertos -
Número máximo de casos não cobertos no conjunto de
treinamento
Min_casos_por_regra
-
Número mínimo de casos cobertos por cada regra
MLP-BP
-
Multi Layer Perceptron with Back-Propagation (Perceptron
Multi Camadas com Retro-Propagação do Erro)
N/A
-
Não Avaliado
Num_formigas
-
Tamanho da população de formigas
Num_regras_converg
-
Teste de convergência das formigas
RNA
-
Rede Neural Artificial
UCI
-
University of California at Irvine (Universidade da Califórnia)
VN
-
Verdadeiro Negativo
VP
-
Verdadeiro Positivo
xi
xii
RESUMO
Este trabalho propõe um algoritmo para descoberta de regras de classificação chamado
Ant-Miner (Minerador de Dados baseado em Colônias de Formigas - Ant Colony-based Data
Miner). O objetivo do Ant-Miner é extrair conhecimento de bases de dados. Conhecimento
este que é representado na forma de regras de classificação. Para isto, fez-se uma revisão da
literatura sobre a recente área de pesquisa chamada Ant Colony Optimization, a qual se baseia
no comportamento de colônias de formigas reais. Revisou-se também a literatura sobre alguns
conceitos de data mining. Com o intuito de comparar os resultados do sistema aqui proposto,
foram utilizados três outros algoritmos. Um primeiro baseado em Redes Neurais Artificiais do
tipo multi-camadas com retro-propagação do erro (MLP-BP – Multi Layer Perceptron with
Back-Propagation), para análise e comparação somente da taxa de acerto. E dois outros
algoritmos de indução de regras bastante citados e conhecidos na literatura, C4.5 e CN2, para
análise e comparação da taxa de acerto e da simplicidade do conjunto de regras descobertas. O
Ant-Miner foi aplicado a oito bases de dados de domínio público e os resultados foram
comparados com os obtidos pelos outros três algoritmos citados. Os resultados obtidos
permitem concluir que: o Ant-Miner é competitivo com os outros algoritmos utilizados na
comparação, com respeito à taxa de acerto, e as regras descobertas pelo Ant-Miner são, na
maioria dos experimentos, muito mais simples do que as descobertas pelo C4.5 e pelo CN2.
xiii
ABSTRACT
This work proposes an algorithm for data mining called Ant-Miner (Ant Colony-based
Data Miner). The goal of Ant-Miner is to extract knowledge from data. This discovered
knowledge is expressed in the form of IF-THEN classification rules. The algorithm is inspired
by both research on the behavior of real ant colonies (Ant Colony Optimization) and some
data mining concepts and principles. We compare the performance of Ant-Miner in eight
public domain data sets using three others algorithms: an Neural Network-based (Multi Layer
Perceptron with Back-Propagation) to analyze the accuracy rate only; and two others rule
induction algorithms, C4.5 and CN2, both well-known data mining algorithms. The results
provide evidence that: Ant-Miner is competitive with the three algorithms with respect to
predictive accuracy; and the rule lists discovered by Ant-Miner are considerably simpler
(smaller) than those discovered by C4.5 and CN2.
xiv
1
CAPÍTULO 1
INTRODUÇÃO
1.1 MOTIVAÇÃO
Recentemente tem havido um grande interesse na área de data mining, onde o objetivo
geral é descobrir conhecimento que não é apenas correto, mas também compreensível e
interessante para o usuário (FAYYAD, PIATETSKY-SHAPIRO e SMYTH, 1996; FREITAS
e LAVINGTON, 1998). O interesse na extração deste conhecimento é fazer com que o
usuário entenda os resultados produzidos pelo sistema e combine-os com seu próprio
conhecimento para tomar uma decisão melhor informado, ao invés de confiar cegamente em
um sistema com resultados incompreensíveis.
Em uma base de dados pode-se ter vários atributos que se correlacionam entre si e o
usuário desconhecer este fato. Com o uso de técnicas de data mining é possível gerar regras
que correlacionem estes atributos simplificando a análise da base em questão.
Em data mining, o conhecimento descoberto é frequentemente representado na forma
de regras de previsão (ou classificação) do tipo:
SE <condições> ENTÃO <classe>
A parte <condições> é o antecedente da regra e contém uma combinação lógica de
atributos previsores, na forma: termo1 E termo2 E ... . Cada termo é uma tripla <atributo,
operador, valor>, tal como <Gênero = feminino>. A parte <classe> é o consequente da regra
e contém a classe prevista para os casos (objetos ou registros) cujos atributos previsores
satisfazem a parte <condições> da regra.
Em essência, a tarefa de classificação consiste em associar cada caso a uma classe,
dentre um grupo pré-definido de classes, baseado em valores de alguns atributos (chamados
de atributos previsores) para o caso.
O uso de algoritmos baseados em colônias de formigas – Ant-based Algorithms ou,
como é mais frequentemente citado, Ant Colony Optimization (ACO) – (DORIGO,
COLORNI e MANIEZZO, 1996) como método para descobrir/induzir regras de classificação,
no contexto de data mining, é uma área de pesquisa ainda muito pouco explorada.
Atualmente, o único trabalho baseado em colônias de formigas desenvolvido para data mining
e que se tem conhecimento é um algoritmo para clustering (MONMARCHE, 1999), que é,
2
com certeza, uma tarefa de data mining bastante diferente da tarefa de classificação
apresentada neste trabalho. Também, em CORDÓN, CASILLAS e HERRERA (2000) foi
proposto um outro tipo de sistema baseado em colônia de formigas para descoberta de regras.
Entretanto, neste trabalho as regras geradas são regras fuzzy, usadas em um sistema de
controle fuzzy, ao invés de regras de classificação no espírito de data mining.
Acredita-se que o desenvolvimento de algoritmos baseados em colônias de formigas
aplicados a data mining seja uma área de pesquisa promissora, pois um sistema baseado em
colônias de formigas envolve agentes simples (formigas) que cooperam uns com os outros
para alcançar um comportamento emergente e unificado, produzindo um sistema robusto
capaz de encontrar soluções de alta qualidade para problemas com grande espaço de busca.
No contexto da descoberta de regras, um sistema baseado em colônias de formigas tem a
habilidade de desenvolver uma busca flexível e robusta para uma boa combinação das
condições lógicas envolvendo os valores dos atributos previsores.
Outro fato motivador é que grande parte dos trabalhos realizados na área de data
mining foram desenvolvidos utilizando algoritmos do tipo árvores de decisão ou indução de
regras determinísticos. Estes algoritmos são do tipo subida-de-colina (hill-climbing) onde
pode ocorrer do algoritmo apenas encontrar pontos de máximos locais e não o máximo global.
A utilização do paradigma ACO como técnica para indução de regras de classificação procura
amenizar este problema, visto que esta abordagem possui um componente estocástico que
favorece uma busca global sobre o espaço de busca do problema. Neste trabalho é investigada
a eficácia da técnica ACO aplicada à descoberta de regras de classificação do tipo SEENTÃO em comparação com os algoritmos determinísticos.
1.2 OBJETIVO
O presente trabalho tem como objetivo aplicar o paradigma de Otimização por
Colônias de Formigas (ACO) a data mining, mais especificamente para a tarefa de
classificação, com o intuito de extrair conhecimento na forma de regras do tipo SE-ENTÃO
para auxílio à tomada de decisão.
Por ser uma área de pesquisa ainda muito pouco explorada no contexto de data
mining, este trabalho tem por objetivo desenvolver um novo algoritmo de ACO para
descoberta de regras de classificação e também divulgar esta vertente de pesquisa,
contribuindo com uma nova aplicação do paradigma ACO.
3
1.3 DESCRIÇÃO DE CONTEÚDO
Esta dissertação está organizada em seis capítulos. No Capítulo 2 faz-se uma revisão
da literatura sobre a heurística de Otimização por Colônias de Formigas, partindo-se desde o
seu surgimento recente, até suas aplicações atuais. O Capítulo 3 revisa os tipos de tarefas de
data mining e alguns conceitos. O Capítulo 4 descreve em detalhes o desenvolvimento do
algoritmo aqui proposto – Ant-Miner. No Capítulo 5 relatam-se os resultados obtidos e
algumas discussões. E, finalmente, o Capítulo 6 apresenta as conclusões e trabalhos futuros.
4
5
CAPÍTULO 2
OTIMIZAÇÃO POR COLÔNIAS DE FORMIGAS
2.1 INSETOS SOCIAIS
Insetos que vivem em colônias, tais como as formigas, abelhas, vespas e cupins,
seguem suas próprias agendas de tarefas independentemente uns dos outros. Entretanto,
quando estes insetos atuam em conjunto (como uma comunidade), eles são capazes de
solucionar problemas complexos de seus cotidianos através de cooperação mútua. Problemas
como selecionar e coletar materiais, encontrar e estocar comida, que requerem planejamentos
sofisticados, são resolvidos por colônias de insetos sem nenhum tipo de supervisor ou
controlador. Este comportamento coletivo que surge de um grupo de insetos sociais tem sido
chamado de “Inteligência de Enxames – Swarm Inteligence” (BONABEAU, DORIGO e
THERAULAZ, 1999). Alguns comportamentos observados e estudados atualmente em
insetos sociais são:
•
a forma que se organizam para agrupar e ordenar larvas e corpos;
•
a maneira que constróem seus ninhos e colméias;
•
a maneira como se organizam para procurar alimentos;
•
como é feita a divisão de trabalho no ambiente em que vivem; e
•
como se organizam para transportar materiais.
Uma colônia de insetos é um sistema descentralizado que soluciona problemas de
grandes proporções, como citado anteriormente, fazendo-se uso de entidades muito simples
que interagem entre si. As principais características destes sistemas são a flexibilidade e a
robustez com os quais solucionam os problemas: a flexibilidade permite a adaptação da
colônia às mudanças do ambiente, enquanto que a robustez permite que a tarefa em
andamento seja concluída mesmo com uma possível falha de alguns indivíduos.
Um dos mecanismos que dá suporte no entendimento da cooperação entre os insetos
está fenotipicamente determinado através das diferenças físicas entre os indivíduos. Por
exemplo, em espécies polimórficas de formigas, a divisão de trabalho pode ocorrer de forma
que dois ou mais tipos físicos diferentes de operários coexistam na mesma colônia. Na espécie
6
Pheidole, operários mais jovens são menores e morfologicamente diferentes dos operários
adultos e realizam tarefas diferentes: enquanto que os adultos, com mandíbulas muito mais
desenvolvidas, cortam pedaços de folhas ou defendem o ninho, os operários jovens alimentam
as larvas ou limpam o ambiente. Na ausência ou insuficiência de operários jovens, os adultos
são estimulados a realizar as tarefas usualmente cumpridas pelos mais jovens, demostrando
um alto grau de plasticidade na divisão de trabalho dentro da colônia.
Muitas das atividades coletivas realizadas por insetos sociais são auto-organizáveis
não necessitando de diferenças morfológicas entre os indivíduos. Estas atividades se
caracterizam por interações a nível microscópico (através de substâncias químicas por
exemplo) em muitas espécies de formigas e que fazem surgir padrões macroscópicos como,
por exemplo, a definição das rotas entre fontes de alimentos e o ninho.
Um sistema auto-organizável é um sistema que possui mecanismos que condicionam o
surgimento de padrões a nível global através da interação entre os componentes que o
constituem. Estes componentes interagem entre si tendo como base unicamente uma
informação local, sem nenhuma referência ao padrão global a ser encontrado (solução do
problema). Como, por exemplo, o comportamento global (melhor rota) das formigas que
buscam por alimento e que emerge a partir de trilhas de feromônio1 (informação local). Sob
auto-organizaçao se define três conceitos/características básicas (BONABEAU, DORIGO e
THERAULAZ, 1999):
•
Realimentação positiva (amplificação – positive feedback) – que promove a
criação de padrões/soluções. Um exemplo de realimentação positiva é o
recrutamento para busca de alimento, que pode ser na forma de trilhas de
feromônio em algumas espécies de formigas ou danças em colônias de abelhas;
•
Realimentação negativa (negative feedback) – a qual contrabalança a
realimentação positiva, ajudando a estabilizar o padrão coletivo sendo buscado. A
realimentação negativa pode ser na forma de saturação, exaustão ou competição.
No exemplo da busca por alimento em colônias de formigas, a realimentação
negativa pode se originar através da exaustão da fonte de alimento, competição
entre fontes de alimentos ou evaporação das trilhas de feromônio;
1
Feromônio é uma substância química utilizada como meio de comunicação entre indivíduos de uma mesma
espécie.
7
•
Flutuações (aleatoriedade) – as quais são de grande importância pois tornam o
sistema mais hábil para descobrir novas soluções (melhor exploração do espaço de
busca).
Para que uma colônia de insetos se auto-organize na realização de determinada tarefa,
é necessário que tais insetos interajam entre si: tais interações podem ser diretas ou indiretas.
Interações diretas ocorrem na forma de contatos através das antenas, troca de comida ou
líquido, contato mandibular, contato visual, etc.. Interações indiretas são mais sutis: dois
indivíduos interagem indiretamente quando um deles modifica o ambiente e o outro responde
às novas características do ambiente em um instante de tempo seguinte. Tais interações
indiretas são chamadas de estigmergia (um comportamento individual modifica o ambiente, o
qual modifica o comportamento de outros indivíduos) (BONABEAU, DORIGO e
THERAULAZ, 1999; DORIGO, MANIEZZO E COLORNI, 1991; DORIGO, DI CARO e
GAMBARDELLA, 1999).
A estigmergia está diretamente associada com o fator de flexibilidade da colônia. Isto
porque quando o ambiente muda devido a alguma perturbação externa, os insetos respondem
naturalmente a esta perturbação, como se fosse uma modificação causada pela atividade da
colônia. Ou seja, a colônia coletivamente responde a perturbações externas com indivíduos
exibindo o mesmo comportamento. No contexto de agentes (insetos) artificiais, este tipo de
flexibilidade é de grande valia pois significa que os agentes podem responder a perturbações
sem a necessidade de serem reprogramados para lidar com a perturbação específica.
Alguns exemplos resultantes da combinação de estigmergia com auto-organização
podem ser vistos em BONABEAU, DORIGO e THERAULAZ (1999): no recrutamento de
formigas, aonde as trilhas de feromônio deixadas pelas formigas são uma forma de modificar
o ambiente para se comunicar com as outras formigas que seguem estas trilhas; modificando o
ambiente na limpeza do ninho, onde a resposta dos outros indivíduos às novas características
do ambiente pode ser no não engajamento de novos operários para a limpeza, estando livres
para desempenhar outras tarefas; e na engenharia que surge nas construções dos ninhos e
colméias. Em todos estes casos o ambiente serve como meio de comunicação.
Dentre os comportamentos observados em insetos sociais, a busca por alimento é o
que possui maior aplicabilidade em problemas do mundo real. Na sequência, a Subseção 2.2
explica com maiores detalhes como surge este comportamento em colônias de formigas reais
e na Subseção 2.3 é detalhado como colônias de formigas artificiais fazem uso deste
comportamento para aplicações computacionais.
8
2.2 COLÔNIAS DE FORMIGAS REAIS
Formigas são capazes de encontrar a rota mais curta entre uma fonte de alimento e o
seu ninho sem o uso de informação visual, sendo capazes também de se adaptar a mudanças
no meio (DORIGO, COLORNI e MANIEZZO, 1996).
Um dos principais problemas estudados pelos entomologistas2 é compreender como
que animais quase cegos, tais como as formigas, conseguem encontrar o caminho mais curto
entre sua colônia e uma fonte de alimento. Foi descoberto que, para trocar informação sobre
qual caminho deve ser seguido, as formigas se comunicam umas com as outras através de
trilhas de feromônio. O movimento das formigas deixa uma certa quantidade de feromônio no
chão, marcando o caminho com uma trilha desta substância. O comportamento coletivo que
emerge é uma forma de processo autocatalítico3 que, quanto mais formigas seguirem uma
trilha, mais atrativa esta trilha se tornará para ser seguida por outras formigas. Este processo
pode ser descrito como um laço de alimentação positiva, onde a probabilidade de uma formiga
escolher um caminho aumenta com o número de formigas que passaram por aquele caminho
anteriormente (BONABEAU, DORIGO e THERAULAZ, 1999; DORIGO, COLORNI e
MANIEZZO, 1996; DORIGO e GAMBARDELLA, 1997; DORIGO, DI CARO e
GAMBARDELLA, 1999; STÜTZLE e DORIGO, 1999).
A idéia básica deste processo é ilustrado na Figura 1. Na figura mais à esquerda as
formigas se movem em linha reta do ninho para a fonte de alimento e vice-versa. A figura do
centro ilustra o que acontece logo após um obstáculo ser colocado no caminho entre a fonte de
alimento e o ninho. Para contornar o obstáculo, cada formiga, aleatoriamente, tem de escolher
Ninho
Ninho
Ninho
Comida
Comida
Comida
Figura 1: Formigas encontrando o caminho mais curto ao redor
de um obstáculo
2
Entomologistas são pesquisadores que estudam comportamentos em insetos.
Um processo autocatalítico (i.e. realimentação positiva) é um processo que se ‘auto-reforça’, de forma a causar
uma convergência muito rápida e, se nenhum mecanismo de limitação for contraposto, pode causar uma
‘explosão’.
3
9
entre virar para a esquerda ou para a direita (com uma distribuição de probabilidade de 50%50%). Todas as formigas se movem aproximadamente com a mesma velocidade e depositam
feromônio na trilha aproximadamente à mesma taxa. Entretanto, as formigas que,
probabilisticamente, escolherem virar para a esquerda (direção ninho Æ comida) irão
percorrer a trilha de feromônio mais rapidamente, enquanto que as formigas que optaram por
contornar o obstáculo pela direita seguirão um caminho mais longo, demorando mais para
contornar o obstáculo. O mesmo ocorre com as formigas que estiverem fazendo o caminho
(comida Æ ninho). Como resultado, o feromônio é acumulado mais rapidamente no caminho
mais curto ao redor do obstáculo. Visto que as formigas preferem seguir trilhas com grandes
quantidades de feromônio, eventualmente todas as formigas convergirão para o caminho mais
curto ao redor do obstáculo, como mostrado na figura da direita. Este processo no qual uma
formiga é influenciada a seguir determinado caminho em direção a uma fonte de alimento por
outra formiga ou por uma trilha de feromônio é uma forma de estigmergia conhecida como
recrutamento.
2.3 COLÔNIAS DE FORMIGAS ARTIFICIAIS
Um algoritmo de Colônias de Formigas (Ant-based Algorithms ou, como é mais
frequentemente citado, Ant Colony Optimization – ACO) é um sistema baseado em agentes
que simula o comportamento natural das formigas na procura por alimentos desenvolvendo
mecanismos de cooperação e aprendizado. A metodologia ACO foi proposta por DORIGO,
COLORNI e MANIEZZO (1996) como uma nova heurística para resolver problemas de
otimização combinatorial.
Existem diversos problemas de otimização combinatorial na área de Pesquisa
Operacional que são da classe NP, isto é, não existem algoritmos limitados polinomialmente
que resolvam estes problemas. Em situações práticas, estes problemas são muito difíceis de
serem resolvidos por algoritmos exatos, pois seu espaço de busca é muito grande,
desencorajando o uso de métodos de busca exaustiva. Uma alternativa para a solução destes
problemas é a utilização de métodos heurísticos, os quais abandonam a certeza da busca em
favor de heurísticas que aumentem a probabilidade de efetuar um movimento rápido em
direção à meta final. Dentre estes métodos encontra-se a heurística ACO.
A metodologia ACO tem sido aplicada a uma variedade de problemas de otimização
combinatorial tais como: o problema do caixeiro viajante (DORIGO e GAMBARDELLA,
10
1997), associação quadrática (MANIEZZO e COLORNI, 1999), roteamento de veículos
(BULLNHEIMER, HARTL e STRAUSS, 1997), escalonamento job shop (COLORNI,
DORIGO, MANIEZZO et al., 1994), coloração de mapas (COSTA e HERTZ, 1997), dentre
outras. Em data mining, a heurística ACO tem sido recentemente aplicada à tarefa de
classificação (PARPINELLI, LOPES e FREITAS, 2001a, 2001b e 2001c) e à de clustering
(MONMARCHE, 1999). ACO tem sido aplicada também no aprendizado de regras para
controle fuzzy (CORDÓN, CASILLAS e HERRERA, 2000). Esta nova heurística tem se
mostrado robusta, podendo ser aplicada a vários problemas de otimização combinatorial sem
sofrer muitas alterações, como por exemplo, para o problema de associação quadrática e o
problema de escalonamento de tarefas; e versátil, podendo ser aplicada à versões similares do
mesmo problema, como por exemplo, para o problema do caixeiro viajante simétrico e
assimétrico. Além disso, a estrutura dos algoritmos ACO é altamente adequada para
processamento paralelo (BULLNHEIMER, KOTSIS e STRAUSS, 1998; STÜTZLE, 1998).
Um ponto importante em se tratando de ACO é o fato de ser uma heurística baseada
em população. Isto é vantajoso pois permite ao sistema usar o processo de realimentação
positiva entre os agentes como mecanismo de busca. De passagem, é interessante mencionar
que atualmente tem havido um interesse crescente no desenvolvimento de algoritmos para
descoberta de regras de classificação que se baseiam em outras heurísticas baseadas em
população – principalmente algoritmos evolucionários (ARAÚJO, LOPES e FREITAS, 1999
e 2000; BOJARCZUK, LOPES e FREITAS, 1999 e 2000; FIDELIS, LOPES e FREITAS ,
1999 e 2000; FREITAS, 1997; 1999 e 2001; NODA, FREITAS e LOPES, 1999).
2.3.1 Similaridades e diferenças com as colônias reais
Os algoritmos ACO, como dito anteriormente, originaram-se do estudo do
comportamento da busca por alimento em formigas reais e fazem uso de (DORIGO,
COLORNI e MANIEZZO, 1996; DORIGO, DI CARO e GAMBARDELLA, 1999):
•
uma colônia de indivíduos que cooperam entre si;
•
uma trilha de feromônio artificial para comunicação local;
•
uma sequência de movimentos locais para formar os caminhos;
•
uma política de decisão probabilística que faz uso somente da informação local.
11
Estes itens são detalhados a seguir:
•
Cooperação entre os indivíduos da colônia. Como nas colônias reais, os algoritmos
ACO são compostos por uma população, ou colônia, de entidades (formigas)
concorrentes e assíncronas, que cooperam globalmente entre si para encontrar uma boa
solução para o problema em questão. Mesmo que a complexidade do problema seja tal
que prejudique a busca da formiga por soluções de alta qualidade, o resultado da
cooperação entre os indivíduos da colônia como um todo normalmente produz
soluções de alta qualidade. Como em uma colônia real, normalmente as formigas
conseguem encontrar um caminho entre seu ninho e uma fonte de alimento. Esta
cooperação entre os indivíduos da colônia surge através da informação que eles
concorrentemente lêem/escrevem nos ‘estados do problema’ (explicado no próximo
item) que visitam;
•
Trilhas de feromônio. As formigas artificiais modificam alguns aspectos no ambiente
em que ‘vivem’ assim como as formigas reais também o fazem. Enquanto as formigas
reais depositam uma substância química, feromônio, as formigas artificiais modificam
algumas informações numéricas armazenadas localmente no estado do problema que
estão visitando. Por analogia, esta informação numérica é chamada de trilha de
feromônio artificial, ou somente trilha de feromônio. Assim como as formigas reais, as
formigas artificiais têm preferência probabilística por caminhos com maior quantidade
de feromônio. Desta forma, caminhos mais curtos tendem a ter altas taxas de
crescimento em suas quantidades de feromônio. Em algoritmos ACO as trilhas de
feromônio são os únicos canais de comunicação entre as formigas. Usualmente, um
mecanismo de evaporação, similar a evaporação real do feromônio, modifica a
informação da quantidade de feromônio o tempo todo. A evaporação do feromônio
permite que a colônia de formigas vagarosamente esqueça seu passado, podendo
direcionar sua busca para novas soluções sem a influência das decisões tomadas
tempos atrás;
•
Busca por caminhos curtos e uso de movimentos locais. Tanto as formigas reais
quanto as formigas artificiais compartilham uma mesma tarefa: encontrar um caminho
mais curto (de custo mínimo) que junte a origem (ninho) com um destino (fontes de
comida). As formigas reais e artificiais não ‘pulam’ de um estado para outro, elas
andam através de estados adjacentes no espaço de busca. A exata definição de estado e
adjacência são específicas para cada problema que se esteja aplicando o algoritmo;
12
•
Regra de transição de estado probabilística e ‘míope’ (visão de curto alcance). As
formigas artificiais, assim como as reais, constróem soluções aplicando uma regra de
transição probabilística para se mover através dos estados adjacentes. Como para as
formigas reais, as formigas artificiais fazem uso somente da informação local, não
podendo ‘olhar para frente’ para prever possíveis estados. Sendo assim, esta regra de
transição é completamente local, no espaço e no tempo. A regra de transição é uma
função composta pela informação previamente conhecida do problema, representada
pelas especificações do mesmo (equivalente à estrutura do terreno para formigas
reais), e pelas modificações locais no ambiente (trilhas de feromônio) provocadas
pelas formigas no passado.
As formigas artificiais têm também algumas características que não são encontradas
nas colônias de formigas reais (BONABEAU, DORIGO e THERAULAZ, 1999; DORIGO,
COLORNI e MANIEZZO, 1996):
•
Formigas artificiais vivem em um mundo discreto e seus movimentos consistem de
transições de estados discretos para estados discretos;
•
Formigas artificiais têm um estado interno. Este estado particular contém a memória
das ações passadas de determinada formiga;
•
Formigas artificiais depositam quantidades de feromônio em função da qualidade da
solução encontrada. Somente algumas poucas espécies de formigas reais depositam
quantidades de feromônio conforme a qualidade das fontes de alimentos encontradas;
•
O momento em que as formigas artificiais atualizam/depositam o feromônio nas trilhas
depende do problema e frequentemente não reflete o comportamento das colônias
reais. Por exemplo, em muitos casos as formigas artificiais atualizam as trilhas de
feromônio somente depois de terem gerado uma solução.
Resumindo, a idéia básica é que, quando uma dada formiga tiver de escolher entre dois
ou mais caminhos, o caminho que tiver sido mais frequentemente escolhido por outras
formigas no passado terá uma maior probabilidade de ser escolhido por esta formiga para ser
seguido. Sendo assim, trilhas com grandes quantidades de feromônio se tornam sinônimos de
caminhos mais curtos.
13
2.3.2 Desenvolvimento de um algoritmo ACO
Em essência, um algoritmo ACO (Ant Colony Optimization) executa iterativamente
um loop contendo dois procedimentos básicos, que são:
•
Um procedimento especificando como as formigas constróem ou modificam as
soluções do problema a ser resolvido; e
•
Um procedimento para a atualização das trilhas de feromônio.
A construção ou modificação de uma solução é feita de maneira probabilística. A
probabilidade de se adicionar um novo item à solução parcial corrente é dada por uma função
heurística dependente do problema (η) e da quantidade de feromônio (τ) depositada pelas
formigas no passado. A atualização das trilhas de feromônio é implementada como uma
função que depende de uma taxa de evaporação do feromônio e da qualidade da solução
produzida. Para implementar um ACO, primeiro deve-se definir (BONABEAU, DORIGO e
THERAULAZ, 1999):
•
Uma representação apropriada do problema, o qual deve permitir às formigas
incrementalmente construir ou modificar soluções através do uso de uma regra
probabilística de transição baseada na quantidade de feromônio na trilha e em uma
heurística local;
•
Um método para forçar a construção de soluções válidas (por exemplo, soluções que
são válidas em uma determinada situação do mundo real) correspondentes à definição
do problema;
•
Uma função heurística (η) que mede a qualidade dos itens que podem ser adicionados
à solução parcial atual;
•
Uma regra para atualização do feromônio, a qual especifica como modificar a
quantidade de feromônio na trilha (τ);
•
Uma regra probabilística de transição baseada no valor da função heurística (η) e no
conteúdo da trilha de feromônio (τ).
14
15
CAPÍTULO 3
DATA MINING
3.1 DESCOBERTA DE CONHECIMENTO
Os métodos tradicionais que não fazem uso de sistemas computacionais, utilizados
para transformar a informação armazenada em bases de dados em conhecimento necessitam
de análise e interpretação manuais. À medida que uma base de dados cresce
exponencialmente, torna-se ineficiente, inviável e impraticável a análise manual. O aumento
da capacidade de análise, neste caso, pode ser obtido com o aumento do número de pessoas
alocadas para a tarefa em questão ou com o aumento do número de pessoas com maior
capacidade de análise. Não é realista supor que se possa aumentar a capacidade de análise na
mesma proporção que cresce a complexidade do problema.
O processo como um todo, da descoberta de conhecimento em bases de dados, é
chamado de KDD (Knowledge Discovery in Databases – Descoberta de Conhecimento em
Bases de Dados), enquanto que o processo de data mining é um passo em particular deste
processo. O processo de KDD inclui, além de data mining, passos como a preparação inicial
da informação, sua seleção, filtragem, introdução de conhecimento já obtido e
interpretação/consolidação dos resultados (FAYYAD, PIATETSKY-SHAPIRO e SMYTH,
1996).
O KDD envolve várias áreas de pesquisa tais como bancos de dados, reconhecimento
de padrões, inteligência artificial, estatística e visualização de dados, incorporando teorias,
algoritmos e métodos destas áreas.
O processo de data mining se propõe a descobrir conhecimento novo a partir de
informações armazenadas em uma base de dados. A decisão de quanto o modelo reflete ou
não conhecimento útil é feita no processo interativo do KDD, onde o julgamento humano é
necessário.
3.2 CARACTERÍSTICAS DOS ALGORITMOS DE DATA MINING
16
Uma grande variedade de algoritmos de data mining têm sido descritos na literatura,
os quais podem ser baseados em técnicas estatísticas determinísticas, buscas heurísticas, redes
neurais artificiais, algoritmos genéticos, programação genética, etc.. Especificamente, pode-se
dizer que os algoritmos de data mining consistem da composição de três componentes: o
modelo, o critério de escolha e o algoritmo de busca (FAYYAD, PIATETSKY-SHAPIRO e
SMYTH, 1996).
Existem dois fatores relevantes a respeito do modelo: a função do modelo e a forma de
representação do modelo. As funções (ou tarefas) mais comuns são:
•
Classificação. Atribui a cada objeto (registro) uma classe, dentre um conjunto de
classes pré-definidas. Como essa função é a abordada neste trabalho, ela será descrita
em mais detalhes na Seção 3.3;
•
Regressão. Mapea os dados para uma variável de valor real. De modo análogo à
classificação, atribui a cada objeto um valor de um atributo especial, chamado
atributo-meta. Porém, o atributo-meta é numérico, podendo assumir valores contínuos;
ao contrário da classificação, onde o atributo meta é categórico, podendo assumir
apenas as classes pré-definidas;
•
Agrupamento (clustering). Mapea os dados em grupos ou classes. Esta tarefa se
diferencia da classificação pelo fato destes grupos serem determinados pelo algoritmo
e não pré-definidos como na classificação;
•
Sumarização. Fornece uma descrição compacta de um subgrupo da base de dados;
•
Modelagem de dependência. Descreve dependências significativas entre atributos.
Esta tarefa é uma generalização da tarefa de classificação, no sentido que nesta tarefa
há vários (mais de um) atributos-meta;
•
Associação ou análise de relacionamento entre atributos. Determina as relações entre
os campos de uma base de dados. Difere da modelagem de dependência
principalmente pelo fato de não buscar regras previsoras;
•
Análise de sequência. Modela padrões sequenciais com o objetivo de obter o estado do
processo gerando a sequência ou para extrair e mostrar desvios e tendências.
As formas de representação dos modelos mais comuns incluem árvores de decisão e
regras SE-ENTÃO, modelos lineares, modelos não-lineares, modelos baseados em exemplos,
e modelos de dependência gráfica probabilística. A flexibilidade do modelo e sua
interpretação são determinados diretamente pela escolha de uma das representações
17
previamente citadas. Geralmente, os modelos mais complexos tendem a representar melhor os
dados, mas também criam dificuldades no momento de interpretar os resultados, como ocorre
em redes neurais. O algoritmo de busca é escolhido de acordo com o tipo particular de modelo
ou tipos de modelos com o qual se está trabalhando e um critério de preferência (bias).
Algumas características desejáveis para um algoritmo de data mining são:
Que o algoritmo:
•
Descubra conhecimento compreensível, normalmente definido como sendo regras
expressas em um alto nível de abstração;
•
Tenha alto grau de autonomia, necessário para descobrir conhecimento previamente
desconhecido pelo usuário;
•
Seja eficiente no processo de descoberta de conhecimento, necessária para lidar com
grandes bancos de dados;
•
Seja integrado com bancos de dados, o que também é importante para lidar com
grandes bancos de dados.
A compreensibilidade do conhecimento geralmente é associada à simplicidade
sintática. Isso significaria que quanto menor a complexidade da regra descoberta em termos
de número de condições, mais compreensível é a regra. Entretanto, esse conceito não é
totalmente correto pois, em algumas aplicações, regras simples com apenas um atributo no
antecedente podem tornar a regra descoberta genérica demais a ponto de invalidar sua
condição como informação útil. Considerando um exemplo simples, em uma base de dados
com características do corpo humano é possível descobrir regras como: SE (é bípede) ENTÃO
(é homem), mas haveriam também as mulheres e até mesmo as aves sendo englobadas por
essa regra. Além disso, o quanto o conhecimento deve ser compreensível depende de cada
aplicação. Por exemplo, embora regras compreensíveis sejam essenciais em medicina (uma
vez que vidas humanas estão em jogo) e em aplicações financeiras, a compreensibilidade
tende a ser menos importante do que a porcentagem de previsões corretas.
A principal motivação para descobrir regras de fácil compreensão está no fato de que
em data mining o resultado é geralmente analisado por seres humanos. Uma melhor
interpretação representa uma melhor utilização do conhecimento descoberto. Por outro lado,
se os resultados forem usados diretamente por um sistema de computador, sem envolver, no
processo de transição, uma interpretação humana, a compreensibilidade não é tão relevante.
18
Outro fator que influencia a compreensibilidade é a forma escolhida para representar
os dados. A linguagem escolhida obviamente depende do usuário final ao qual os dados serão
passados. Por exemplo, considere-se dados médicos para o diagnóstico de pacientes com certa
patologia. Para um médico experiente, as informações podem ser apresentadas na forma de
números, por exemplo, quantidade de insulina no sangue, pois ele possui capacidade para
interpretar os dados nessa forma, enquanto que talvez um médico ainda em fase de residência
compreenderá muito melhor se os resultados aparecerem discretizados como alto-risco,
médio-risco e baixo-risco. Note-se que, para escolher qual abordagem seguir, deve-se achar
um bom balanceamento entre o quanto de precisão se quer e o grau de simplicidade desejado.
3.3 TAREFA DE CLASSIFICAÇÃO
O termo classificação pode cobrir qualquer contexto no qual alguma decisão ou
previsão é feita tendo como base a informação disponível em dado momento. Um algoritmo
de classificação é a ferramenta para fazer tais julgamentos em novas situações. Neste trabalho
considera-se uma definição mais restrita de classificação. Assume-se que o problema se
concentra na construção de um algoritmo que será aplicado a uma sequência de casos (objetos
ou registros), sendo que cada novo caso deve ser associado a uma classe, de um grupo prédefinido de classes, tomando como base a observação dos atributos ou características de cada
caso (FREITAS e LAVINGTON, 1998). A construção de um algoritmo de classificação
(classificador), partindo-se de uma base de dados onde as classes verdadeiras dos casos são
conhecidas, pode ser conhecida também por outros termos como reconhecimento de padrões,
discriminação ou por aprendizado supervisionado (para diferenciar do aprendizado nãosupervisionado ou clustering, no qual as classes são deduzidas partindo-se dos dados).
Dentre as aplicações nas quais a tarefa de classificação é fundamental, podem ser
citados processos mecânicos, por exemplo, ordenação de cartas por uma máquina de
postagem; atribuição de créditos a clientes em bases financeiras; e diagnósticos preliminares
de patologias. De fato, alguns dos problemas que surgem na ciência, indústria e comércio
podem ser vistos como problemas de classificação ou decisão usando dados complexos e
frequentemente muito extensos.
Um exemplo simples da tarefa de classificação é visto na Figura 2 (FREITAS e
LAVINGTON, 1998). Neste exemplo, cada linha da base de dados (Figura 2a) representa um
registro mostrando se determinado cliente comprou ou não certo produto (um livro, por
19
exemplo). Cada registro é composto por três atributos previsores – Sexo, País e Idade – e um
atributo-meta (comprar ou não o produto). Com base nestes dez casos registrados, a Figura 2b
a) Dados de entrada para um sistema de classificação
Sexo
País
Idade
Comprar (meta)
Masc.
França
25
Sim
Masc.
Inglaterra
21
Sim
Fem.
França
23
Sim
Fem.
Inglaterra
34
Sim
Fem.
França
30
Não
Masc.
Alemanha
21
Não
Masc.
Alemanha
20
Não
Fem.
Alemanha
18
Não
Fem.
França
34
Não
Masc.
França
55
Não
b) Regras de classificação descobertas a partir dos dados de
entrada
SE (País = “Alemanha”)
ENTÃO (Comprar = “Não”)
SE (País = “Inglaterra”)
ENTÃO (Comprar = “Sim”)
SE (País = “França” E Idade ≤ 25)
ENTÃO (Comprar = “Sim”)
SE (País = “França” E Idade > 25)
ENTÃO (Comprar = “Não”)
Figura 2: Exemplo de tarefa de classificação
mostra quatro regras de classificação que podem ser possivelmente descobertas por algum
algoritmo de indução de regras. Note-se que o atributo “Sexo” compõe nenhuma regra. Isto
porque tem um baixo poder de previsão, sendo irrelevante para a classificação.
Na tarefa de classificação a base de dados geralmente é dividida em dois subconjuntos:
um conjunto de treinamento (onde a classe é conhecida) e um conjunto de teste (onde a classe
é desconhecida pelo algoritmo de data mining). As regras descobertas pelo classificador são
avaliadas no conjunto de teste não vistos durante o treinamento (CHEN, HAN e YU, 1996).
Esse é um ponto importante, pois se as regras descobertas fossem avaliadas no conjunto de
treinamento, o qual foi usado para guiar a descoberta das regras, a estimativa de qualidade
20
(precisão preditiva) das regras seria otimista demais. O desafio é prever a classe de casos nos
dados de teste, não vistos durante o treinamento.
3.4 BIAS INDUTIVO - DEFINIÇÃO
Tendo-se um conjunto de amostras de dados, a quantidade de hipóteses (formas de
abstrair conhecimento) que implicam essas amostras é potencialmente infinito. Um bias
(tendência) é qualquer critério (explícito ou implícito), utilizado para favorecer uma hipótese
ou outra, com exceção de consistências com os dados. Desta forma, todo algoritmo de
aprendizado indutivo possui um bias – sem bias não há indução (MITCHELL, 1980). Existem
dois tipos de bias indutivo:
•
Bias de representação – É a forma de representação do conhecimento gerado pelo
algoritmo de indução. Por exemplo, a maioria dos algoritmos de indução de regras não
consegue descobrir regras que comparam dois atributos diferentes, como SE (Atrib1 >
Atrib2) ... .
•
Bias de busca (ou preferência) – No caso de indução de regras, este bias é
implementado pela função de avaliação das regras e pelo método de busca.
21
CAPÍTULO 4
UM ALGORITMO BASEADO EM COLÔNIAS DE FORMIGAS PARA
CLASSIFICAÇÃO EM DATA MINING
Neste capítulo será discutido em detalhes o algoritmo ACO proposto para a descoberta
de regras de classificação, chamado Ant-Miner (Ant Colony-based Data Miner). O capítulo é
subdividido em sete partes: uma descrição geral do Ant-Miner, a construção das regras, a
função heurística, a poda das regras, a atualização do feromônio, o uso das regras descobertas
para classificar novos casos e os parâmetros do sistema (PARPINELLI, LOPES e FREITAS,
2001a, 2001b e 2001c).
4.1 UMA VISÃO GERAL DO ANT-MINER
Em um algoritmo ACO cada formiga incrementalmente constrói/modifica uma
solução para determinado problema alvo. No caso deste trabalho o problema alvo é a
descoberta de regras de classificação. Como mencionado no Capítulo 1, cada regra de
classificação tem a forma:
SE < termo1 E termo2 E ...> ENTÃO <classe>
Cada termo é uma tripla <atributo, operador, valor>, onde valor é um valor
pertencendo ao domínio de atributo. O elemento operador na tripla é um operador relacional.
A atual versão do Ant-Miner pode lidar somente com atributos categóricos, sendo o elemento
operador na tripla sempre “=”. Atributos contínuos (valores reais) são discretizados como um
passo de pré-processamento (KOHAVI e SAHAMI, 1996) (este processo é mais detalhado na
Subseção 5.1). A parte <classe> é o consequente da regra e contém a classe prevista para os
casos (objetos ou registros) em que os atributos previsores satisfazem a parte <termo1 E
termo2 E ...>, que são as condições que compõem a regra.
Uma descrição de alto nível do Ant-Miner é mostrada na Figura 3. Ant-Miner segue
uma sequência de passos para descobrir uma lista ordenada de regras de classificação que
cubra todos ou quase todos os casos de treinamento. No início do processo de descoberta das
regras a lista que armazenará as regras é uma lista vazia e o conjunto de treinamento é
composto por todos os casos de treinamento. No inicio do laço ENQUANTO, todas as trilhas
(estados do problema) são inicializadas com a mesma quantidade de feromônio. Cada iteração
22
do laço ENQUANTO, correspondente ao número de execuções do laço REPITA-ATÉ,
descobre uma regra de classificação. Esta regra é adicionada à lista de regras descobertas, e os
casos de treinamento que são corretamente cobertos por esta regra (i.e. os casos que
satisfazem o antecedente da regra e têm a classe prevista pelo seu consequente) são removidos
do conjunto de treinamento. Este processo é iterativamente executado enquanto o número de
casos de treinamento for maior do que um parâmetro especificado pelo usuário, chamado
Max_casos_n_cobertos (casos não cobertos no conjunto de treinamento).
ConjuntoTreinamento = {todos os casos de treinamento };
ListaDeRegras = []; /* lista das regras é inicializada como lista vazia */
ENQUANTO (ConjuntoTreinamento > Max_casos_n_cobertos)
i = 1; /* índice de cada formiga */
j = 1; /* índice do teste de convergência */
Inicialize todas trilhas com a mesma quantidade de feromônio;
REPITA
Anti começa com uma regra vazia e incrementalmente constrói uma regra de
classificação Ri, adicionando um termo por vez à regra atual;
Pode a regra Ri;
Atualize o feromônio de todas as trilhas, incrementando o feromônio na trilha
seguida pela formiga Anti (proporcionalmente a qualidade da regra Ri) e
decrementando o feromônio nas outras trilhas (simulando a evaporação do
feromônio);
SE (Ri for igual a Ri – 1) /* atualiza teste de convergência */
ENTÃO j = j + 1;
SENÃO j = 1;
FIM-SE
i = i + 1;
ATÉ (i ≥ Num_formigas) OU (j ≥ Num_regras_converg)
Escolha a melhor regra Rm dentre todas as regras Ri construídas pelas formigas;
Adicione a regra Rm na ListaDeRegras;
ConjuntoTreinamento = ConjuntoTreinamento - {grupo de casos corretamente
cobertos por Rm};
FIM-ENQUANTO
Adicione a regra padrão na última posição de ListaDeRegras;
Figura 3: Uma descrição do algoritmo Ant-Miner
Cada iteração do laço REPITA-ATÉ da Figura 3 engloba três passos: a construção da
regra, a poda da regra e a atualização do feromônio, discutidos nas próximas subseções.
No primeiro passo, construção da regra (Subseção 4.2), cada formiga Anti começa com
uma regra vazia, i.e. uma regra com nenhum termo em seu antecedente, e adiciona um termo
por vez à sua regra parcial. A regra parcial construída por uma formiga corresponde ao
caminho parcial seguido por esta formiga. Similarmente, a escolha de um termo para ser
adicionado na regra parcial corresponde à escolha de uma direção para onde o caminho atual
23
será estendido, dentre todas as possíveis direções (todos os termos que podem ser adicionados
à regra parcial).
A escolha do termo a ser adicionado à regra parcial da formiga depende de dois
fatores: da função heurística dependente do problema (η) e da quantidade de feromônio (τ)
associada a cada termo, que serão discutidas em detalhes nas próximas subseções – 4.3 e 4.5,
respectivamente.
Uma formiga adiciona termos um-a-um à sua regra até que esteja incapaz de continuar
construindo sua regra. Esta situação pode surgir em duas situações:
•
Quando todos os termos ainda não adicionados à regra fizerem com que esta cubra um
número
de
casos
menor
que
um
limiar
especificado
pelo
usuário,
Min_casos_por_regra (número mínimo de casos cobertos por cada regra); ou
•
Quando todos os atributos já tiverem sido usados pela formiga. Desta forma não
haverá mais atributos para serem adicionados ao antecedente da regra. Notificando que
cada atributo pode ocorrer somente uma vez em cada regra, para evitar regras
inválidas, como por exemplo: “SE (Sexo = masculino) E (Sexo = feminino) ...”.
Quando um destes dois critérios de parada for satisfeito, significa que a formiga Anti
construiu a regra Ri (completou um caminho) e, a princípio, poder-se-ia utilizar esta regra para
classificação. Na prática, entretanto, é desejável podar a regra descoberta (segundo passo do
algoritmo) para remover termos irrelevantes que podem ter sido desnecessariamente inseridos
na regra. Estes termos irrelevantes podem ter sido inseridos na regra devido a variações
estocásticas no procedimento de seleção dos termos e/ou devido ao uso de uma função
heurística local ou míope – que considera somente um atributo por vez, ignorando interações
entre atributos. O método de poda usado no Ant-Miner é descrito na Subseção 4.4.
Como terceiro passo do algoritmo, a quantidade de feromônio em cada trilha é
atualizada. Esta atualização do feromônio é feita de acordo com a qualidade da regra Ri
construída pela formiga Anti. Desta forma, as outras formigas começam a construir suas regras
usando as novas quantidades de feromônio para guiar sua busca. Este processo é repetido até
que uma das duas condições seguintes sejam alcançadas:
•
O número de regras construídas for maior ou igual do que um limiar especificado pelo
usuário – Num_formigas (indica o tamanho da população de formigas); ou
24
•
Quando a atual formiga Anti tiver construído uma regra que é exatamente a mesma do
que a regra construída pelas Num_regras_converg (variável utilizada no teste de
convergência das formigas) formigas anteriores, onde Num_regras_converg representa
o número de regras usadas para o teste de convergência das formigas. Este teste de
convergência detecta se as formigas já convergiram para a mesma regra construída,
que é equivalente a convergir para o mesmo caminho em colônias de formigas reais.
Uma vez concluído o laço REPITA-ATÉ, a melhor regra dentre as regras descobertas
pelas formigas é adicionada à lista de regras descobertas, e o sistema inicia uma nova iteração
do laço ENQUANTO, reinicializando todas as trilhas com a mesma quantidade de feromônio.
A cada iteração do laço ENQUANTO, todos os casos corretamente cobertos pela regra
descoberta são removidos do conjunto de treinamento, e outra iteração é iniciada. Sendo
assim, o algoritmo Ant-Miner é chamado novamente para achar uma regra no conjunto de
treinamento reduzido. Este processo é repetido por quantas iterações forem necessárias para
achar as regras que cubram o máximo de casos no conjunto de treinamento. Mais
precisamente, o processo citado é repetido enquanto o número de casos não cobertos no
conjunto
de
treinamento
for
maior
do
que
um
limiar
predefinido,
chamado
Max_casos_n_cobertos (número máximo de casos não cobertos no conjunto de treinamento).
Quando o número de casos no conjunto de treinamento for menor do que ou igual a
Max_casos_n_cobertos a busca por regras é cessada. As regras descobertas são armazenadas
em uma lista ordenada de regras (na ordem em que foram descobertas). O sistema adiciona
uma regra padrão na última posição da lista de regras. A regra padrão tem um antecedente
vazio (sem condições) e tem um consequente predizendo a classe da maioria presente nos
casos de treinamento que não foram cobertos por nenhuma das regra. Caso as regras
descobertas pelo Ant-Miner cubram totalmente os casos de treinamento, a regra padrão gerada
no final da lista de regras terá o consequente predizendo a classe da maioria presente no
conjunto de treinamento como um todo. Esta regra padrão é automaticamente aplicada se
nenhuma das regras na lista gerada cobrir um novo caso sendo classificado.
Uma vez estando completa a lista de regras, o sistema está finalmente pronto para
classificar os casos do conjunto de teste (não vistos durante o treinamento). Para fazer isto o
sistema aplica as regras descobertas, na ordem em que são dispostas na lista (Subseção 4.6). A
primeira regra que cobrir o caso é aplicada, ou seja, o caso é associado à classe predita pelo
consequente da regra acionada.
25
4.2 CONSTRUÇÃO DAS REGRAS
Considere termoij como sendo uma condição da regra, na forma Ai = Vij, onde Ai é o iésimo atributo e Vij é o j-ésimo valor do domínio de Ai. A probabilidade de termoij ser
escolhido para ser adicionado à regra parcial de uma formiga é dada pela Equação 1:
η ij × τ ij (t)
;
P =
ij
 bm

a
∑ x m ×  ∑ η mn × τ mn(t) 
n = 1

m=1


(1)
onde:
•
ηij é o valor de uma função heurística dependente do problema para o termoij. Quanto
maior o valor de ηij, maior é a relevância do termoij para a classificação, e maior é a
probabilidade deste ser escolhido para fazer parte do antecedente de uma regra. Esta
função é discutida na próxima seção. Por enquanto basta mencionar que o valor desta
função é sempre o mesmo para um dado termo, sem levar em consideração quais
termos já ocorrem na regra parcial atual e qual foi o caminho seguido pelas formigas
anteriormente;
•
τij(t) é a quantidade de feromônio associada a um termoij no tempo t e corresponde à
quantidade de feromônio atualmente disponível na posição i,j da trilha sendo seguida
pela formiga. Como discutido antes, quanto melhor a qualidade da regra construída
por uma formiga, maior será a quantidade de feromônio adicionado nos segmentos da
trilha visitada por esta formiga. Desta forma, com o passar do tempo, os melhores
segmentos de trilha – i.e. os melhores termos (pares atributos-valores) – terão grandes
quantidades de feromônio, aumentando a probabilidade de serem escolhidos por outras
formigas. A quantidade de feromônio τij(t), assim como o componente heurístico ηij,
são independentes dos termos que já ocorrem na regra parcial da formiga. Porém, a
quantidade de feromônio é inteiramente dependente dos caminhos seguidos pelas
formigas anteriormente, fazendo surgir uma forma indireta de comunicação, conforme
mostrado no Capítulo 2, como sendo uma forma de estigmergia. Quando a primeira
formiga começa a construir sua regra, todas posições i,j nas trilhas (todos termoij, ∀i,j)
têm a mesma quantidade de feromônio. Entretanto, logo que uma formiga termina seu
26
caminho (constrói uma regra), as quantidades de feromônio em cada posição i,j
visitada pela formiga é atualizada;
•
a é o número total de atributos;
•
xm recebe valor 1 se o atributo Ai ainda não foi usado pela formiga atual, ou valor 0
caso contrário;
•
bm é o número de valores no domínio do m-ésimo atributo.
Um dado termoij é escolhido para ser adicionado à regra parcial atual de uma formiga
com probabilidade proporcional ao valor da Equação 1, sujeito a duas restrições:
•
O atributo Ai não pode estar ocorrendo na regra parcial da formiga. Note-se que para
satisfazer esta restrição as formigas devem “lembrar” quais termos (pares de atributosvalores) estão presentes em suas regras parciais no instante t. Esta pequena quantidade
de “memória” é uma das diferenças entre as formigas artificiais e as reais, como
discutido anteriormente;
•
Um termoij não pode ser adicionado à regra parcial atual se esta adição fizer com que a
regra parcial estendida cubra menos do que uma quantidade pré-definida de casos,
chamada de Min_casos_por_regra, como mencionado antes.
Uma vez que o antecedente da regra esteja completo, o sistema escolhe o consequente
da regra (i.e. a classe prevista pela regra) que maximiza a qualidade da mesma. Isto é feito
associando ao consequente da regra a classe da maioria entre os casos cobertos por ela.
4.3 FUNÇÃO HEURÍSTICA
Para cada termo que pode ser adicionado à regra atual, Ant-Miner calcula o valor ηij de
uma função heurística que é uma estimativa da qualidade deste termo, com respeito a sua
habilidade de melhorar a precisão preditiva da regra. Esta função heurística é baseada na
Teoria de Informação (COVER e THOMAS, 1991). Mais precisamente, o valor de ηij para
um termoij envolve a medida de entropia (ou quantidade de informação) associada com o
termo. Para cada termoij da forma Ai=Vij – onde Ai é o i-ésimo atributo e Vij é o j-ésimo valor
pertencente ao domínio de Ai – sua entropia é dada pela Equação 2:
27
(
)
(
)
k
H(W|Ai = Vij ) = − ∑ P(w|Ai = Vij ) × log 2 P(w|Ai = Vij ) ;
w=1
(2)
onde:
•
W é o atributo-meta (i.e., o atributo cujo domínio consiste das classes sendo previstas);
•
k é o número de classes;
•
P(w|Ai=Vij) é a estimativa de probabilidade condicional de se observar a classe w
tendo-se observado Ai = Vij, a qual é computada com base no conjunto de treinamento
inteiro.
Quanto maior for o valor de H(W|Ai=Vij), mais uniformemente as classes estão
distribuídas e menor será a probabilidade de uma formiga escolher o termoij para ser
adicionado à sua regra parcial. É desejável normalizar o valor da função heurística, para
facilitar seu uso na Equação 1, combinando a função heurística e a quantidade de feromônio.
Para implementar tal normalização, usou-se o fato de que o valor de H(W|Ai=Vij) varia na
seguinte faixa: 0 ≤ H(W|Ai=Vij) ≤ log2(k), onde k é o número de classes.
Desta forma, a função heurística normalizada baseada na teoria de informação é dada
pela Equação 3:
ηij =
log 2 k − H(W|Ai = Vij )
 bm

a
∑ x m ×  ∑ log 2 k − H(W|Am = V mn ) 
n = 1

m=1


;
(3)
onde:
•
•
xm recebe valor 1 se o atributo Ai ainda não foi usado pela formiga atual, ou valor 0
caso contrário;
•
bm é o número de valores no domínio do m-ésimo atributo.
Note que o valor de H(W|Ai=Vij) para o termoij é sempre o mesmo, desconsiderando o
conteúdo da regra no qual o termo ocorre. Desta forma, para ganhar tempo computacional, o
valor de H(W|Ai=Vij) para todos termoij, é computado como um passo de pré-processamento.
28
Com respeito à função heurística 3, tem-se ainda mais dois detalhes a serem citados.
Primeiro, se o valor Vij do atributo Ai não ocorrer no conjunto de treinamento, então o valor de
H(W|Ai=Vij) recebe o valor máximo de log2(k). Isto corresponde a associar ao termoij o menor
poder preditivo possível. Segundo, se todos os casos tendo Ai=Vij pertencerem à mesma
classe, então H(W|Ai=Vij) = 0. Isto corresponde a associar ao termoij o maior poder preditivo
possível.
4.4 PODA DAS REGRAS
A poda de regras é uma técnica comum utilizada em data mining (BREWLOW e
AHA, 1997). Como mencionado antes, o principal objetivo de podar uma regra é remover
termos irrelevantes que podem ter sido indesejavelmente incluídos nela. A poda de regras
aumenta potencialmente o poder preditivo das mesmas, ajudando a evitar seu overfitting4 aos
casos de treinamento. Outra motivação para podar as regras é a melhora na simplicidade, visto
que uma regra curta (com poucas condições) é, em geral, mais facilmente interpretável pelo
usuário do que uma regra muito longa.
O procedimento de poda das regras é executado para cada formiga logo que esta acaba
de completar a construção da regra. A estratégia de busca para o procedimento de poda das
regras no Ant-Miner é muito similar ao procedimento de poda sugerido por QUINLAN
(1987), apesar do critério de qualidade da regra usado nos dois procedimentos serem bastante
diferentes um do outro.
A idéia básica é se remover iterativamente um termo por vez da regra enquanto este
processo estiver melhorando a qualidade da regra. Este processo é melhor descrito no
algoritmo da Figura 4. Na primeira iteração do processo de poda, a formiga está com a regra
completa. O procedimento remove temporariamente cada um dos termos da regra – um de
cada vez – e calcula a qualidade da regra resultante, usando a função de qualidade definida
pela Equação 5. Este passo pode envolver uma re-atribuição da classe prevista pela regra,
visto que uma regra podada pode ter como classe da maioria, em seus casos cobertos, uma
classe diferente da regra antes da poda. O termo removido que obtiver uma melhor qualidade
da regra será o termo efetivamente removido, completando a primeira iteração. Na próxima
iteração o procedimento remove novamente o termo que resultar no maior aumento da
4
Overfitting ocorre quando as regras descobertas se ajustam em demasia às peculiaridades dos dados de
treinamento, podendo reduzir a taxa de acerto nos dados de teste ainda não vistos.
29
qualidade da regra, e assim por diante. Este processo é repetido até que a regra tenha somente
um termo ou até que não haja nenhum termo cuja remoção resulte em uma melhora da
qualidade da regra.
ENQUANTO (Número de condições na regra > 1)
PARA i = 1 to (Número de condições na regra)
Medir qualidade da regra após remover i-ésima condição;
FIM-PARA
SE todas remoções de condições testadas diminuíram a qualidade da regra
ENTÃO Abandonar loop e sair dessa rotina
SENÃO Remover condição j, j na faixa de 1 a (número de condições da
Regra), que resultou em maior aumento de qualidade;
Decrementar o contador do número de condições;
Determinar classe prevista pela regra reduzida;
FIM-ENQUANTO
Figura 4: Descrição do procedimento de poda
4.5 ATUALIZAÇÃO DO FEROMÔNIO
Lembre-se que cada termoij corresponde a uma posição em algum caminho que pode
ser seguido por uma formiga. A cada iteração do laço ENQUANTO do algoritmo da Figura 3,
todos os termoij são inicializados com a mesma quantidade de feromônio. Em outras palavras,
quando o sistema é inicializado e a primeira formiga começa sua busca, todos os caminhos
têm a mesma quantidade de feromônio.
A quantidade inicial de feromônio depositado em cada posição do espaço de busca é
inversamente proporcional ao número de valores de todos os atributos, e é definida pela
Equação 4:
1
τ ij (t = 0 ) = a
;
∑ bi
i=1
onde:
•
•
bi é o número de possíveis valores que podem ser tomados pelo atributo Ai.
(4)
30
O valor retornado por esta equação é normalizado, o que facilita seu uso na Equação 1,
que combina seu valor com o valor da função heurística.
Cada vez que uma formiga constrói e poda uma regra (um caminho completo) (veja o
algoritmo da Figura 3), a quantidade de feromônio em todas as posições de todos os caminhos
deve ser atualizada. A atualização do feromônio tem duas idéias básicas:
•
A quantidade de feromônio associado com cada termoij que ocorre na regra construída
pela formiga (depois da poda) é aumentada em função da qualidade da regra
descoberta;
•
A quantidade de feromônio associado com cada termoij que não occore na regra é
decrementada, simulando o fenômeno de evaporação do feromônio em colônias de
formigas reais.
4.5.1 Aumento da quantidade de feromônio nos termos usados
Aumentar a quantidade de feromônio associado com cada termoij que ocorre na regra
construída corresponde a aumentar a quantidade de feromônio no caminho completado pela
formiga. No contexto de descoberta de regras, isto corresponde a incrementar a probabilidade
do termoij ser escolhido por outras formigas no futuro, visto que o termo foi proveitoso pela
formiga atual. Este aumento é proporcional à qualidade da regra construída pela formiga –
quanto melhor for a regra, maior será o aumento na quantidade de feromônio para cada termoij
pertencente à regra.
A qualidade da regra construída pela formiga, denotada por Q, é computada pelo
produto: Q = sensibilidade × especificidade (HAND, 1997; LOPES, COUTINHO e LIMA,
1997), e é definido na Equação 5 (a primeira parcela da fórmula corresponde a sensibilidade e
a segunda a especificidade):
Q=
onde:
VP
VN
×
;
VP + FN FP + VN
(5)
31
•
VP (verdadeiro positivo) é o número de casos no conjunto de treinamento cobertos
pela regra que têm a classe prevista pela regra;
•
FP (falso positivo) é o número de casos no conjunto de treinamento cobertos pela
regra que possuem a classe diferente da classe prevista pela regra;
•
FN (falso negativo) é o número de casos no conjunto de treinamento que não são
cobertos pela regra, mas que têm a classe prevista pela regra;
•
VN (verdadeiro negativo) é o número de casos no conjunto de treinamento que não
são cobertos pela regra e que não têm a classe prevista pela regra.
Note que VP e VN representam as classificações corretas, enquanto FP e FN
representam as classificações errôneas. A qualidade é definida como o produto de
sensibilidade e especificidade para forçar o Ant-Miner a descobrir regras com alto valor desses
dois termos ao mesmo tempo, já que seria fácil (porém indesejável) maximizar o valor de um
desses termos às custas de minimizar o valor do outro.
Q varia dentro da faixa 0 ≤ Q ≤ 1 e, quanto maior o valor de Q, melhor é a qualidade
da regra. A atualização do feromônio para um termoij é executada de acordo com a Equação 6,
para todos os termoij que ocorrem na regra.
τ ij(t + 1 ) = τ ij(t) + τ ij(t) × Q, ∀i,j ∈ R ;
(6)
onde R é o conjunto dos termos que ocorrem na regra construída pela formiga no tempo t.
Desta forma, para todos termoij que ocorrem na regra construída pela formiga, a
quantidade de feromônio é aumentada por uma fração da quantidade atual de feromônio, e
esta fração é diretamente proporcional a Q.
4.5.2 Decréscimo da quantidade de feromônio nos termos não usados
Como mencionado antes, a quantidade de feromônio associado a cada termoij que não
ocorre na regra construída pela formiga tem que ser diminuída para simular o fenômeno da
evaporação do feromônio que ocorre nos sistemas fórmicos reais.
No Ant-Miner, a evaporação do feromônio é implementada de maneira indireta. Mais
precisamente, o efeito da evaporação do feromônio para termos não utilizados pela formiga é
32
alcançado através da normalização do valor de cada quantidade de feromônio τij(t). Esta
normalização é realizada pela divisão do valor de cada τij(t) pela soma de todos τij(t), ∀i,j.
Para observar como isto implementa a evaporação do feromônio, note-se que quando
uma regra é construída, somente os termos usados pela formiga na regra construída tem sua
quantidade de feromônio aumentada pela Equação 6. Desta forma, no passo da normalização
do feromônio, a quantidade de feromônio de um termo não usado será computada pela divisão
de seu valor atual (não modificado pela Equação 6) pela soma total do feromônio de todos os
termos (o qual está aumentado devido à aplicação da Equação 6 aos termos usados pela
formiga). O efeito final será a redução da quantidade normalizada de feromônio para cada
termo não usado. Os termos usados terão, com certeza, suas quantidades normalizadas de
feromônio aumentadas devido à aplicação da Equação 6.
4.6 USANDO AS REGRAS DESCOBERTAS
Para classificar os casos de teste, não vistos durante o treinamento, as regras
descobertas são aplicadas na ordem em que elas foram descobertas (lembre-se que as regras
são armazenadas em uma lista ordenada de regras). A primeira regra que cobrir o novo caso
sendo classificado é aplicada – i.e., o caso é associado à classe prevista pelo consequente da
regra disparada.
É possível que nenhuma regra do grupo de regras descobertas cubra o novo caso sendo
classificado. Nesta situação o novo caso é classificado por uma regra padrão que
simplesmente prediz a classe da maioria no grupo de casos não cobertos no conjunto de
treinamento, i.e., o grupo de casos que não são cobertos por nenhuma regra descoberta.
O procedimento verificado nos dois parágrafos anteriores é utilizado para calcular a
taxa de acerto da lista de regras descobertas nos casos de teste. Esta medida é simplesmente a
divisão dos casos corretamente classificados pelo total de casos no conjunto de teste.
4.7 PARÂMETROS DO SISTEMA
O sistema desenvolvido possui quatro parâmetros que são ajustados pelo usuário:
33
•
Número de formigas (Num_formigas): Este é também o número máximo de regras
candidatas construídas e podadas durante uma iteração do laço ENQUANTO do
algoritmo da Figura 3, visto que cada formiga constrói uma única regra. Em cada
iteração, a melhor regra construída é considerada uma regra descoberta. Note-se que
quanto maior Nun_formigas, mais regras candidatas serão avaliadas por iteração,
porém o sistema se tornará mais lento;
•
Número mínimo de casos por regra (Min_casos_por_regra): Cada regra deve cobrir
pelo menos Min_casos_por_regra casos, para forçar um grau de certeza de
generalidade nas regras descobertas. Isto ajuda a evitar um overfitting aos dados de
treinamento;
•
Número
máximo
de
casos
não
cobertos
no
conjunto
de
treinamento
(Max_casos_n_cobertos): O processo de descoberta de regras é iterativamente
realizado até que o número de casos de treinamento não cobertos por qualquer regra
for menor do que ou igual a este limiar;
•
Número
de
regras
usadas
para
testar
a
convergência
das
formigas
(Num_regras_converg): Se a formiga atual tiver construído uma regra que é
exatamente igual às regras construídas pelas (Num_regras_converg) formigas
anteriores, o sistema conclui que as formigas convergiram para uma única regra
(caminho). A iteração atual do laço ENQUANTO do algoritmo da Figura 3 é parada e
outra iteração é iniciada.
34
35
CAPÍTULO 5
RESULTADOS E ANÁLISES
Neste capítulo são descritas as bases de dados utilizadas na avaliação do sistema
desenvolvido, bem como as decisões tomadas durante a fase de experimentos, detalhes de
execução (tais como os parâmetros escolhidos e os métodos de treinamento e teste) e os
resultados e análises propriamente ditos.
5.1 BASES DE DADOS E MÉTODO DE DISCRETIZAÇÃO UTILIZADO
Os experimentos foram realizados utilizando oito bases de dados de domínio público,
disponíveis no repositório da Universidade da Califórnia (UCI – University of California at
Irvine) (AHA e MURPHY, 1994).
As principais características das bases de dados usadas nos experimentos estão
sumarizadas na Tabela 1. A primeira coluna desta tabela identifica a base de dados, enquanto
que as outras colunas indicam, respectivamente, o número de casos registrados, o número de
atributos categóricos, o número de atributos contínuos e o número de classes da base.
Tabela 1: Bases de dados utilizadas nos experimentos
Base de dados
Ljubljana breast
cancer
Wisconsin breast
cancer
tic-tac-toe
dermatology
hepatitis
Cleveland heart
disease
Nursery
Votes
#casos
#atrib. categ. #atrib. contin.
#classes
286
9
-
2
683
-
9
2
958
366
155
9
33
13
1
6
2
6
2
303
8
5
5
12960
435
8
16
-
5
2
A base de dados Ljubljana Breast Cancer foi apresentada pela primeira vez em
CLARK e NIBLETT (1987) e contém 286 registros, cada um com 9 atributos e a meta é
determinar os pacientes que terão reincidência do câncer de mama.
36
A base Wisconsin breast cancer foi apresentada pela primeira vez em
MANGASARIAN, SETIONO e WOLBERG (1990) e é composta por 683 registros, cada um
com 9 atributos e a meta é determinar se os pacientes possuem câncer de mama maligno ou
benigno.
Tic-tac-toe foi apresentada pela primeira vez por AHA (1991) e é composta por 958
registros, cada um com 9 atributos e a meta é prever o melhor movimento no “jogo da velha”.
A base dermatology foi apresentada por DEMIROZ, GOVENIR e ILTER (1998) e
contém 366 registros, cada um com 34 atributos. A meta é determinar se o paciente possui
alguma das seis possíveis patologias dérmicas registradas nesta base.
Hepatitis foi primeiramente apresentada por DIACONIS e EFRON (1983) e contém
155 casos, cada um com 19 atributos. O objetivo desta base é tentar prever, com base nos
atributos previsores, se determinado paciente tem chances de vida ou não diante da hepatite.
A base Cleveland heart disease foi apresentada por DETRANO et al. (1989) e possui
303 casos, cada um com 13 atributos previsores. O objetivo é determinar se o paciente possui
distúrbios no coração.
A base Nursery foi apresentada por OLAVE, RAJKOVIC e BOHANEC (1989) e
possui 12960 casos observados, cada um com 8 atributos previsores. O objetivo da aplicação
em cima desta base é a previsão do grau de necessidade de famílias para ganhar vagas em
creches.
A base de dados Votes foi primeiramente apresentada por SCHLIMMER (1987) e é
composta por 435 registros, cada um representado pela observação de 16 atributos previsores.
O objetivo desta base é prever se determinado candidato é democrata ou republicano (eleições
nos EUA).
Como mencionado anteriormente, Ant-Miner descobre regras somente em bases de
dados compostas por atributos categóricos. Devido a este fato, os atributos contínuos são
discretizados como um passo de pré-processamento. Esta discretização é feita com o auxílio
do algoritmo de discretização C4.5-Disc, descrito em KOHAVI e SAHAMI (1996). Este
método simplesmente usa o algoritmo C4.5 (QUINLAN, 1993) para discretizar os atributos
contínuos. Em essência, para cada atributo a ser discretizado é extraído dos casos de
treinamento uma base de dados reduzida contendo somente dois atributos: o atributo a ser
discretizado e o atributo meta (classe). O C4.5 é então aplicado a esta base de dados reduzida,
construindo uma árvore de decisão na qual todos os nós internos referem-se ao atributo sendo
discretizado. Cada caminho na árvore de decisão corresponde à definição de um intervalo
categórico produzido pelo C4.5. A Figura 5 ilustra um exemplo onde um atributo contínuo
37
“Idade” está sendo utilizado na geração de uma árvore de decisão para previsão de duas
classes – classe “1” e classe “2”. A partir desta árvore defini-se cinco intervalos discretos – 042, 43-49, 50-56, 57-59, 60-∞ – que passam a ser os valores do atributo “Idade”, tornando-o
um atributo discreto.
Idade > 59 : 2
Idade ≤ 59 :
|
Idade > 56 : 1
|
Idade ≤ 56 :
|
|
Idade ≤ 42 : 2
|
|
Idade > 42 :
|
|
|
Idade ≤ 49 : 1
|
|
|
Idade > 49 : 2
Figura 5: Exemplo de árvore de decisão produzida na
discretização de um atributo contínuo
Em todas as bases de dados, os casos que possuem atributos com valores faltando
foram mantidos inalterados. Nestes casos o sistema aproveita os valores que ocorrem no caso
e descarta os atributos que possuem valores faltando (sendo denotados pelo símbolo ‘?’ na
base). Em data mining existem outras formas de tratar os valores de atributos que estejam
incompletos. Como por exemplo, completar com o valor mais frequente verificado do atributo
na base, ou simplesmente retirar os casos que possuam atributos com valores faltando.
5.2 PARÂMETROS DO SISTEMA UTILIZADOS NOS EXPERIMENTOS
Em todos os experimentos relatados nas Subseções 5.5, 5.6, 5.7 e 5.8, os parâmetros
utilizados no sistema foram:
•
Num_formigas = 3000;
•
Min_casos_por_regra = 10;
•
Max_casos_n_cobertos = 10;
•
Num_regras_converg = 10.
38
É interessante notar que mesmo com os parâmetros acima não otimizados, foram
produzidos resultados muito bons, como serão relatados nas próximas subseções. O fato dos
parâmetros do Ant-Miner não terem sido otimizados para as bases de dados utilizadas faz a
comparação ser justa com os resultados obtidos pelos outros algoritmos, que também não
tiveram seus parâmetros otimizados. De passagem, vale a pena dizer que esta forma justa de
comparação não é frequentemente vista na literatura: o que ocorre muitas vezes são dos
autores relatarem os resultados comparando uma versão com parâmetros otimizados dos seus
algoritmos com uma versão não otimizada de outros algoritmos. Isto faz a comparação menos
justa. De qualquer forma, na Subseção 5.9 são relatados alguns experimentos avaliando a
sensibilidade do Ant-Miner a mudanças nos valores de alguns parâmetros.
Há uma advertência na interpretação do valor de Num_formigas. Este parâmetro define
o número máximo de formigas por iteração do laço ENQUANTO do algoritmo da Figura 3.
Na prática, muito menos formigas são necessárias para completar uma iteração, visto que uma
iteração é considerada terminada quando Num_regras_converg sucessivas formigas
convergem para o mesmo caminho (regra). Nos experimentos relatados, o número atual de
formigas por iteração é da ordem de 1500, ao invés de 3000.
5.3 CRITÉRIOS DE AVALIAÇÃO
Os resultados foram obtidos sob dois critérios de avaliação: precisão preditiva (taxa de
acerto nos casos de teste) e simplicidade das regras descobertas.
Para o critério da taxa de acerto deseja-se obter regras que possam prever situações
futuras. Para isto é necessário utilizar os dados disponíveis de modo a simular esta situação.
Uma maneira de simular situações futuras é a divisão da base de dados em dados de
treinamento e dados de teste. Apesar desta abordagem fornecer dados de teste (não vistos
durante o treinamento) para o algoritmo Ant-Miner, esta acaba por diminuir os dados
disponíveis para o treinamento. O método utilizado para minimizar as perdas pela partição da
base de dados e explorar mais amplamente as características dos casos é a validação cruzada
(WEISS e KULIKOWSKI, 1991).
A validação cruzada consiste em se dividir aleatoriamente a base de dados em
partições de tamanhos iguais (ou aproximadamente iguais) e alternar qual das partições é
utilizada para teste e quais são utilizadas para treinamento. Nos experimentos foi utilizada
validação cruzada com fator 10, isto é, as bases de dados são divididas de forma aleatória em
39
10 partições e o algoritmo Ant-Miner é executado 10 vezes. A cada execução, 9 partições
compõem a base de treinamento e a outra partição compõe a base de teste. Com os resultados
(taxa de acerto nos casos de teste) das 10 vezes em que o algoritmo é executado, extrai-se a
média aritmética destes resultados que será relatada como sendo a taxa de acerto das regras
descobertas.
Com relação à simplicidade da lista de regras descobertas, os resultados são obtidos,
como é usual na literatura, através da contagem do número de regras descobertas e do número
total de termos (condições) nos antecedentes de toda a lista de regras descoberta.
Todos os resultados foram obtidos utilizando um Pentium II PC com clock de 333
MHz e 128 MB de memória principal. Ant-Miner foi desenvolvido em linguagem C e obteve
praticamente o mesmo tempo de processamento (da ordem de segundos para cada base de
dados) dos outros algoritmos para obtenção dos resultados.
É interessante mencionar que a segunda versão do Ant-Miner, implementada em
linguagem C, é cerca de três ordens de magnitude (i.e., milhares de vezes) mais rápida do que
a primeira versão implementada em MatLab com a mesma funcionalidade.
Nos resultados obtidos, Tabelas 2, 3, 4 e 5, os valores que estão a esquerda do símbolo
“±” são as médias dos resultados e os valores que estão a direta são os desvios-padrão dos
resultados correspondentes. Para calcular as médias e os desvios-padrão, foram utilizadas as
Equações (7), (8) e (9), como segue, para cálculo da média (M), variância (var) e desviopadrão (sd), respectivamente:
M =
var =
1 r
∑ acc(hi ) ;
r i =1
1 1 r
(acc(hi ) − M )2  ;
∑

r  r − 1 i −1

sd = var ;
(7)
(8)
(9)
onde:
•
r é o número de partições determinado pela validação cruzada;
•
acc(hi) é a taxa de acerto obtida referente a partição hi.
As Subseções 5.5 e 5.6 relatam os resultados obtidos com o Ant-Miner e com os outros
algoritmos, referentes à taxa de acerto e à simplicidade das listas de regras descobertas. Nas
40
Subseções 5.7, 5.8 e 5.9 são relatados os experimentos referentes à influência do
procedimento de poda no algoritmo Ant-Miner, à influência do feromônio no resultado do
sistema e à sensibilidade do Ant-Miner ao ajuste de alguns parâmetros com relação à taxa de
acerto, respectivamente.
5.4 ALGORITMOS UTILIZADOS NA COMPARAÇÃO DOS RESULTADOS
Os resultados obtidos com o Ant-Miner foram comparados com três outros algoritmos:
dois algoritmos de indução de regras, C4.5 (QUINLAN, 1993) e CN2 (CLARK e NIBLETT,
1989; CLARK e BOSWELL, 1991), e um algoritmo baseado em redes neurais artificiais
multi-camadas com retro-propagação do erro (MLP-BP – Multi Layer Perceptron with BackPropagation). Para o primeiro critério de avaliação, taxa de acerto, os três algoritmos citados
foram utilizados. Para o segundo critério, simplicidade das regras descobertas, somente os
algoritmos de indução de regras foram utilizados, visto que a rede neural não gera nenhuma
forma explicita de representação de conhecimento compreensível, funcionando como uma
caixa preta. As subseções seguintes descrevem algumas características básicas de
funcionamento dos algoritmos utilizados na comparação dos resultados.
5.4.1 Algoritmo C4.5
Como visto, as regras descobertas pelo Ant-Miner são organizadas na forma de uma
lista ordenada de regras. Já o algoritmo C4.5 gera uma árvore de decisão aonde cada caminho
entre o nó raiz até um nó folha representa uma regra descoberta. Cada regra é armazenada na
forma de uma lista desordenada de regras, criando um conjunto de regras. Para classificar um
caso ainda não visto durante o treinamento, o C4.5 aplica o conjunto de regras de forma que a
regra que cobrir o caso é aplicada.
No algoritmo C4.5 não existe nenhum mecanismo para permitir que a qualidade da
regra descoberta seja utilizada como um feedback para a construção de outras regras. Este
feedback (usando o mecanismo de feromônio) é a maior característica dos algoritmos
inspirados em colônias de formigas. Além disso, Ant-Miner executa uma busca estocástica
enquanto que o C4.5 executa uma busca determinística. Isto deixa o Ant-Miner mais robusto a
41
problemas como ruído5 na base de dados e interação entre atributos, aumentando a
probabilidade de se encontrar um ótimo global (ao invés de um sub-ótimo local) no espaço de
busca do problema.
Tanto o Ant-Miner quanto o C4.5 descobrem regras expressas na mesma forma de
conhecimento (regras do tipo SE-ENTÃO). Nas terminologias de data mining e aprendizado
de máquina, pode se dizer que ambos os algoritmos têm o mesmo bias de representação, mas
diferentes bias de busca (ou preferência) (Seção 3.4).
5.4.2 Algoritmo CN2
Em essência o funcionamento do algoritmo CN2 é o seguinte: CN2 cria uma lista de
regras de maneira incremental descobrindo uma regra por vez. A cada regra descoberta o CN2
adiciona esta regra ao final de uma lista de regras, remove os casos corretamente cobertos por
ela dos casos de treinamento e chama novamente o procedimento de descoberta de regras
para os casos de treinamento reduzido. Note que esta estratégia é a mesma utilizada pelo AntMiner. Além disso, tanto o Ant-Miner quanto o CN2 constróem uma regra partindo-se de uma
regra vazia e incrementalmente adicionam um termo por vez a regra sendo criada.
Como o algoritmo C4.5, o algoritmo CN2 não possui nenhum mecanismo para
permitir que a qualidade da regra descoberta seja utilizada como um feedback para a
construção de outras regras. Este feedback pode ser considerado a principal diferença entre o
Ant-Miner e o CN2. Além disso, como o C4.5, CN2 executa uma busca determinística.
A comparação entre os resultados obtidos com o Ant-Miner e CN2 é particularmente
interessante devido ao fato de ambos os algoritmos descobrirem uma lista ordenada de regras.
Em contraste com o C4.5 que descobre um conjunto de regras. Tanto o Ant-Miner quanto o
CN2 descobrem regras expressas na mesma forma de conhecimento (regras SE-ENTÃO),
implicando que as diferenças nos desempenhos dos algoritmos são refletidas pelas diferenças
nas estratégias de busca de cada um. Novamente, nas terminologias de data mining e
aprendizado de máquina, pode-se dizer que ambos os algoritmos têm o mesmo bias de
representação, mas diferentes bias (ou preferência) de busca.
5.4.3 Algoritmo MLP-BP
5
Ruídos podem ocorrer na forma de valores de atributos previsores faltando ou no momento da criação da base
42
O sistema baseado em Redes Neurais Artificiais (RNAs) do tipo MLP-BP (Multilayer
Perceptron com Back-Propagation) é um modelo de RNA que se caracteriza por ser multicamadas com ativação do tipo feed-forward (não recorrente), e com aprendizado
supervisionado6 por retro-propagação do erro (FAUSETT, 1994). Este sistema funciona como
uma caixa preta (black box) onde o usuário recebe simplesmente o resultado da rede neural
indicando a qual classe o caso é classificado. O conhecimento é expresso na codificação dos
pesos da rede, tornando-se incompreensível para o usuário.
5.5 TAXA DE ACERTO
Os resultados comparando a taxa de acerto entre o Ant-Miner e os demais algoritmos
estão relatados na Tabela 2.
Tabela 2: Taxa de acerto (%) do Ant-Miner, C4.5, CN2 e MLP-BP
Base de dados
Ljubljana breast
cancer
Wisconsin
breast cancer
tic-tac-toe
dermatology
hepatitis
Cleveland heart
disease
nursery
votes
Ant-Miner
Taxa de Acerto (%)
C4.5
CN2
MLP-BP
75.28 ± 2.24
73.34 ± 1.07
67.69 ± 3.59
74.53 ± 2.46
96.04 ± 0.93
95.02 ± 0.10
94.88 ± 0.88
96.34 ± 0.59
73.04 ± 2.53
94.29 ± 1.20
90.00 ± 3.11
83.18 ± 0.57
89.05 ± 0.20
85.96 ± 0.35
97.38 ± 0.52
90.38 ± 1.66
90.00 ± 2.50
72.80 ± 1.87
59.99 ± 2.32
85.00 ± 2.50
59.67
± 2.50
58.33 ± 0.24
57.48 ± 1.78
53.03 ± 2.26
83.77
96.38
± 1.24
± 1.11
82.72 ± 4.15
94.78 ± 0.08
99.07 ± 0.11
93.78 ± 0.69
N/A
N/A
* N/A: Não avaliado
5.5.1 Análise dos resultados
(i.e. erros de digitação) por exemplo.
No treinamento supervisionado os padrões a serem reconhecidos (casos de treinamento) são apresentados à
rede neural juntamente com a resposta que a rede deve fornecer ao reconhecer novamente este mesmo padrão.
6
43
Como visto na Subseção 5.3, um dos critérios de avaliação do sistema é a taxa de
acerto, obtida por intermédio de um processo de validação cruzada.
Consideremos primeiro a análise da segunda e terceira colunas da Tabela 2, Ant-Miner
vs. C4.5. Com base nos resultados obtidos, o Ant-Miner descobriu regras com uma melhor
taxa de acerto do que o C4.5 em sete bases de dados: Ljubljana breast cancer, Wisconsin
breast cancer, dermatology, hepatitis, Cleveland heart disease, Nursery e Votes. Em duas
destas bases de dados, dermatology e hepatitis, a diferença foi relativamente grande: 94.29% e
90.00% para o Ant-Miner e 89.05% e 85.96% para o C4.5, respectivamente. Nas outras três
bases os resultados foram similares com uma pequena superação por parte do Ant-Miner.
Em uma única base de dados, tic-tac-toe, o C4.5 descobriu regras com melhor taxa de
acerto do que o Ant-Miner. Nesta base a diferença foi relativamente grande: 73.04% para o
Ant-Miner e 83.18% para o C4.5. Neste caso verifica-se que o Ant-Miner sacrificou a taxa de
acerto para melhorar a simplicidade do conjunto de regras (discutido em detalhes na próxima
subseção). Visto os resultados, pode-se concluir que o Ant-Miner é competitivo com o C4.5
em termos de taxa de acerto.
Consideremos agora a análise dos resultados obtidos com o Ant-Miner e CN2,
respectivamente a segunda e quarta colunas da Tabela 2. Os resultados mostraram que em
cinco bases de dados, Ljubljana breast cancer, Wisconsin breast cancer, dermatology,
Cleveland heart disease e Votes, o Ant-Miner descobriu regras com maior taxa de acerto do
que o CN2. Em quatro destas cinco bases, Ljubljana breast cancer, Wisconsin breast cancer,
dermatology e Votes, as diferenças foram significativas com 75.28%, 96.04%, 94.29% e 96.38
para o Ant-Miner e 67.69%, 94.88%, 90.38% e 93.78% para o CN2, respectivamente. Na
outra base, Cleveland heart disease, o Ant-Miner superou com pouca diferença: 59.67% para
o Ant-Miner e 57.48% para o CN2. Em uma base de dados, hepatitis, os resultados foram
iguais: 90.00% de acerto para ambos os algoritmos.
Nas bases de dados tic-tac-toe e Nursery, CN2 obteve uma expressiva diferença
positiva em relação ao resultado obtido pelo Ant-Miner: 97.38% e 99.07% para o CN2 e
73.04% e 83.77% para o Ant-Miner, respectivamente. Mais uma vez, Ant-Miner sacrificou a
taxa de acerto para melhorar a simplicidade do conjunto de regras descobertas (discutido em
detalhes na próxima subseção).
Por fim, a análise da taxa de acerto entre o Ant-Miner e o sistema MLP-BP. Na Tabela
2, segunda e quinta colunas, os resultados mostram que nas bases de dados Ljubljana breast
cancer, Wisconsin breast cancer e tic-tac-toe, os dois sistemas obtiveram praticamente a
44
mesma taxa de acerto: 75.28%, 96.04% e 73.04% para o Ant-Miner e 74.53%, 96.34% e
72.80% para MLP-BP, respectivamente.
Nas outras três bases, dermatology, hepatitis e Cleveland heart disease, Ant-Miner
obteve uma significativa diferença positiva: 94.29%, 90.00% e 59.67% para Ant-Miner e
59.99%, 85.00% e 53.03% para MLP-BP, respectivamente.
Visto os resultados, conclui-se que o Ant-Miner é competitivo com os algoritmos
utilizados na comparação em termos de taxa de acerto, ressaltando novamente que nenhum
dos métodos utilizaram valores otimizados para seus parâmetros, fazendo assim a comparação
o mais justa possível.
5.6 SIMPLICIDADE DAS REGRAS DESCOBERTAS
Os resultados comparando a simplicidade da lista das regras descobertas pelo AntMiner e pelos outros algoritmos estão relatados na Tabela 3. A primeira coluna desta tabela
discrimina a base de dados. As colunas dois a quatro mostram o número médio de regras
descobertas pelo Ant-Miner, C4.5 e CN2, respectivamente. Nas colunas cinco a sete são
mostrados o número médio de condições presentes nos conjuntos de regras descobertas pelo
Ant-Miner, C4.5 e CN2, respectivamente.
Tabela 3: Simplicidade das listas de regras descobertas pelo Ant-Miner, C4.5 e CN2
No. de regras
Base de
dados
Ljubljana
breast cancer
Wisconsin
breast cancer
tic-tac-toe
dermatology
hepatitis
Cleveland
heart disease
Nursery
Votes
No. de condições
Ant-Miner
C4.5
CN2
Ant-Miner
C4.5
CN2
7.10 ± 0.31
6.2 ± 1.40
55.40 ± 2.07
9.10 ± 0.38
12.8 ± 3.27
122.60 ± 4.38
6.20 ± 0.25 11.1 ± 0.48
18.60 ± 0.45
12.20 ± 0.74
44.1 ± 2.49
44.50 ± 1.94
8.50 ± 0.62 83.0 ± 4.70
7.30 ± 0.15 23.2 ± 0.66
3.40 ± 0.16 4.4 ± 0.31
39.70 ± 2.52
18.50 ± 0.47
7.20 ± 0.25
10.00 ± 2.14 384.2 ± 24.46 115.20 ± 7.81
23.10 ± 0.93 91.7 ± 3.54
45.70 ± 1.23
8.20 ± 0.68
8.5 ± 1.01
11.40 ± 0.42
9.50 ± 0.92 49.0 ± 3.13
42.40 ± 0.71
16.20 ± 0.81 183.4 ± 12.98 118.30 ± 2.25
14.30 ±
0.81
5.00 ± 0.00
615.10 ±
8.81
5.9 ± 0.10
132.50 ± 2.05 15.70 ± 1.24
18.90 ± 0.54
7.70 ± 0.61
-
364.90 ± 7.59
19.3 ± 0.59
57.90 ± 2.47
45
Para analisar os resultados obtidos com relação à simplicidade das regras descobertas,
como visto na Subseção 5.3, esta foi medida, como é usual na literatura, pelo número de
regras descobertas e pelo número total de termos (condições) nos antecedentes de todas as
regras descobertas.
Para simplificar a análise da tabela, será dada maior ênfase no número de regras, visto
que a análise dos resultados para o número de termos é praticamente a mesma.
5.6.1.1 Ant-Miner vs. C4.5
Analisando a segunda e terceira colunas (Ant-Miner e C4.5, respectivamente)
referentes ao número de regras, em quatro das oito bases de dados, Ljubljana breast cancer,
Wisconsin breast cancer, hepatitis e Votes, os números de regras descobertas foram
praticamente os mesmos para ambos algoritmos. Porém, a complexidade das regras (número
de condições) nas bases Ljubljana breast cancer, Wisconsin breast cancer e Votes, foram
relativamente maiores para o algoritmo C4.5: para a base Ljubljana breast cancer, Ant-Miner
descobriu 7.1 regras com 9.1 termos, enquanto que o C4.5 obteve 6.2 regras com 12.8 termos;
para a base Wisconsin breast cancer, Ant-Miner descobriu 6.2 regras com 12.2 termos no
conjunto, enquanto que o C4.5 encontrou 11.1 regras com 44.1 termos; e na base Votes, o AntMiner descobriu 5.0 regras com 7.7 termos, enquanto que o C4.5 encontrou 5.9 regras com
19.3 termos.
Nas bases, tic-tac-toe, dermatology, Cleveland heart disease e Nursery, a diferença
entre o número de regras descobertas pelo Ant-Miner e o C4.5 foram bastante significativas,
como segue.
Na base de dados tic-tac-toe, o Ant-Miner descobriu uma compacta lista com 8.5
regras, enquanto que o C4.5 descobriu 83.0 regras. Nesta base o C4.5 alcançou uma taxa de
acerto significativamente melhor. Isto conclui que o Ant-Miner sacrificou a taxa de acerto
para melhorar a simplicidade das regras descobertas. Isto parece ser um compromisso
razoável, visto que em várias aplicações de data mining a simplicidade de um conjunto de
regras tende a ser muito mais importante do que sua taxa de acerto. Na verdade, existem
vários algoritmos de indução de regras que são explicitamente projetados para melhorar a
simplicidade do conjunto de regras a ser descoberto, mesmo que para isto reduza a taxa de
acerto (BOHANEC e BRATKO, 1994; BREWLOW e AHA, 1997; CATLETT, 1991).
46
Nas bases de dados dermatology e Cleveland heart disease, o Ant-Miner descobriu 7.3
e 9.5 regras, respectivamente, enquanto que o C4.5 descobriu 23.2 e 49.0 regras,
respectivamente. Na base Nursery, Ant-Miner descobriu uma compacta lista com 14.3 regras,
enquanto que o C4.5 descobriu o incrível número de 615.1 regras. Nestes casos a grande
simplicidade do conjunto de regras descoberta pelo Ant-Miner foi alcançada sem sacrificar a
taxa de acerto. Na base dermatology o Ant-Miner obteve uma taxa de acerto
significativamente melhor, enquanto que nas bases Cleveland heart disease e Nursery, as
taxas de acerto foram praticamente as mesmas para os dois algoritmos, como analisado na
subseção anterior.
Há entretanto, uma advertência na interpretação dos resultados da Tabela 3 em relação
ao C4.5. As regras descobertas pelo Ant-Miner são organizadas na forma de uma lista
ordenada de regras. Isto significa que, para uma regra ser aplicada a um caso de teste, as
regras anteriores a ela na lista não devem cobrir o caso. Como resultado, as regras descobertas
pelo Ant-Miner não são tão modulares e independentes como as regras descobertas pelo C4.5.
Isto resulta em um efeito que reduz um pouco a simplicidade das regras descobertas pelo AntMiner, em comparação com as regras descobertas pelo C4.5. Porém, em todos os casos, este
efeito parece ser perfeitamente compensado pelo fato de que, geralmente, o tamanho da lista
de regras descobertas pelo Ant-Miner é muito menor do que o tamanho do conjunto de regras
descobertas pelo C4.5. Desta forma, parece seguro dizer que, geralmente, as regras
descobertas pelo Ant-Miner são mais simples do que as regras descobertas pelo C4.5, sendo
isso um ponto importante no contexto de data mining.
5.6.1.2 Ant-Miner vs. CN2
Analisando a segunda e quarta colunas da Tabela 3 (Ant-Miner e CN2,
respectivamente) referentes ao número de regras, verifica-se que em todas as oito bases de
dados utilizadas nos experimentos, as listas de regras geradas pelo Ant-Miner são mais
simples – com menos regras e menos condições – do que as listas de regras descobertas pelo
CN2. Em sete das oito bases, Ljubljana breast cancer, Wisconsin breast cancer, tic-tac-toe,
dermatology, Cleveland heart disease, Nursery e Votes, a diferença entre os resultados foram
bastante expressivos, como segue.
Nas bases de dados Ljubljana breast cancer e Nursery, Ant-Miner descobriu listas de
regras cerca de 10 vezes mais simples do que as descobertas pelo CN2.
47
Nas bases Wisconsin breast cancer, tic-tac-toe, dermatology, Cleveland heart disease
e Votes, Ant-Miner descobriu listas cerca de quatro vezes mais simples do que as encontradas
pelo CN2.
Na base de dados hepatitis, Ant-Miner descobriu regras mais simples do que as
encontradas pelo CN2, mas as diferenças não foram tão grandes quanto as obtidas nas outras
bases.
Considerando os dois critérios de avaliação, taxa de acerto e simplicidade das listas de
regras, os resultados mostraram que os dois algoritmos (Ant-Miner e CN2) são competitivos
em termos de taxa de acerto, apesar da superioridade do CN2 na base tic-tac-toe ser mais
significante estatisticamente do que a superioridade do Ant-Miner em quatro outras bases. Em
termos da simplicidade das regras descobertas, em todos os casos o Ant-Miner descobriu listas
de regras muito mais simples (pequenas) do que as listas de regras descobertas pelo CN2.
5.7 INFLUÊNCIA DA PODA NO ALGORITMO ANT-MINER
Para analisar a influência da poda, o algoritmo Ant-Miner foi executado sem o
procedimento de poda, mantendo-se inalterados todos os outros procedimentos descritos no
algoritmo da Figura 3. Para fazer uma comparação justa entre o Ant-Miner com e sem poda,
os experimentos sem o procedimento de poda usaram os mesmos parâmetros especificados na
Subseção 5.2, e também foram submetidos ao procedimento de validação cruzada com fator
10 para todas as bases de dados descritas na Tabela 1. Os resultados do Ant-Miner sem o
procedimento de poda estão relatados na Tabela 4.
Tabela 4: Resultados do Ant-Miner sem podar as regras
Base de
dados
Ljubljana
breast cancer
Wisconsin
breast cancer
tic-tac-toe
dermatology
hepatitis
Cleveland
heart disease
Nursery
Votes
Taxa de acerto
(%)
No. De regras
No. de condições
70.69 ± 3.87
19.60 ± 0.22
63.8 ± 1.61
95.74 ± 0.74
22.8 ± 0.20
130.6 ± 0.84
76.83 ± 2.27
83.05 ± 1.94
92.5 ± 2.76
68.8 ± 0.32
25.9 ± 0.31
6.8 ± 0.13
238.7 ± 2.56
436.8 ± 4.08
40.9 ± 0.70
54.82 ± 2.56
21.8 ± 0.20
94.3 ± 1.42
83.71 ± 0.70
91.75 ± 1.64
852.30 ± 2.89
33.00 ± 0.21
4069.50 ± 17.94
256.80 ± 2.40
48
Primeiramente será analisada a influência da poda das regras na precisão preditiva do
Ant-Miner. Comparando a segunda coluna da Tabela 4 com a segunda coluna da Tabela 2, vêse que o Ant-Miner sem o procedimento de poda obteve uma menor taxa de acerto do que o
Ant-Miner com o procedimento de poda em quatro bases de dados, Ljubljana breast cancer,
dermatology, Cleveland heart disease e Votes. A redução da taxa de acerto foi mais
expressiva na base dermatology, aonde o Ant-Miner sem a poda obteve 83.05% enquanto que
o Ant-Miner com poda obteve 94.29%.
Por outro lado, Ant-Miner sem o procedimento de poda obteve uma taxa de acerto um
pouco maior em duas bases de dados, tic-tac-toe e hepatitis. Nas bases, Wisconsin breast
cancer e Nursery, a precisão preditiva com e sem o procedimento de poda foram praticamente
as mesmas.
Nas oito bases de dados utilizadas nos experimentos, a poda das regras mostrou ser
mais benéfica do que maléfica, considerando a taxa de acerto. O fato da poda reduzir a taxa de
acerto em algumas bases, mas não em todas as bases, não é um resultado surpreendente, pois
o procedimento de poda é uma forma de bias indutivo (RAO, GORDON e SPEARS, 1995;
SCHAFFER, 1993 e 1994) e qualquer bias indutivo pode ser adequado para algumas bases de
dados e inadequado para outras.
Com respeito à simplicidade das listas de regras descobertas, comparando os
resultados da terceira e quarta colunas da Tabela 4 com a segunda e quinta colunas da Tabela
3, nota-se que, para todas as oito bases de dados, as listas de regras descobertas pelo AntMiner sem o procedimento de poda – Tabela 4 – são muito mais complexas, ou seja, possuem
maior número de regras e termos, do que as listas de regras encontradas pelo Ant-Miner com
poda. Assim, conclui-se que o procedimento de poda das regras é essencial para melhorar a
compreensibilidade das regras descobertas pelo Ant-Miner.
5.8 INFLUÊNCIA DO FEROMÔNIO
Para analisar a influência do feromônio no Ant-Miner, o algoritmo foi executado
atribuindo à quantidade de feromônio um valor constante para todos os pares de atributosvalores durante toda execução do algoritmo. Mais precisamente, τij(t) = 1, ∀ i, j, t, durante um
processo completo do Ant-Miner, sendo o procedimento de atualização do feromônio
49
removido do algoritmo da Figura 3. Lembre-se que uma formiga escolhe um termo para
adicionar à sua regra parcial com base na Equação 1. Desta forma, todos os termos candidatos
(pares de atributos-valores) terão o mesmo valor de quantidade de feromônio, fazendo com
que a formiga escolha um termoij com probabilidade ηij, deixando o procedimento de busca
por regras no Ant-Miner ser guiado somente pela informação heurística definida na Equação
3. Todos os outros procedimentos do algoritmo foram mantidos inalterados.
Novamente, para fazer uma comparação justa entre Ant-Miner com e sem feromônio,
os experimentos realizados sem a influência usaram os parâmetros especificados na Subseção
5.2, e submetidos também a validação cruzada com fator 10 aplicado às oito bases de dados
descritas na Tabela 1. Os resultados do Ant-Miner sem a influência do feromônio são
relatados na Tabela 5.
Tabela 5: Resultados do Ant-Miner sem a influência do feromônio
Base de
dados
Ljubljana
breast cancer
Wisconsin
breast cancer
tic-tac-toe
dermatology
hepatitis
Cleveland
heart disease
Nursery
Votes
Taxa de Acerto
(%)
No. de regras
No. de condições
75.17 ± 3.22
6.60 ± 0.30
7.5 ± 0.50
93.84 ± 0.82
5.90 ± 0.23
9.00 ± 0.39
67.37 ± 2.96
88.16 ± 2.68
85.00 ± 3.63
9.30 ± 0.56
7.50 ± 0.16
3.30 ± 0.15
10.00 ± 1.01
22.30 ± 0.73
5.10 ± 0.50
54.70 ± 3.12
9.30 ± 0.26
15.00 ± 0.63
73.95 ± 1.30
95.00 ± 1.36
14.50 ± 1.05
5.00 ± 0.00
16.00 ± 1.55
5.90 ± 0.40
Comparando a segunda coluna desta tabela com a segunda coluna da Tabela 2, vê-se
que o Ant-Miner sem influência do feromônio obteve uma menor taxa de acerto do que o AntMiner com influência do feromônio em quase todas as oito bases de dados. A única exceção
foi na base Ljubljana breast cancer, aonde a taxa de acerto foi quase a mesma para ambas as
versões do algoritmo.
Com respeito à simplicidade das listas de regras descobertas, não houve muita
diferença entre os resultados obtidos com o Ant-Miner com e sem influência do feromônio,
como pode ser visto comparando a terceira e quarta colunas da Tabela 5 com a segunda e
quinta colunas da Tabela 3.
50
Com estes resultados conclui-se que o uso de um procedimento para atualização de
feromônio é importante para melhorar a precisão preditiva das regras descobertas pelo AntMiner, principalmente quando a atualização do feromônio interage com a informação
heurística definida pela Equação 3. Outro ponto importante é que esta melhora da precisão
preditiva
associada
com
a
atualização
do
feromônio
é
obtida
sem
sacrificar
desnecessariamente a simplicidade das regras descobertas.
5.9 SENSIBILIDADE DO ANT-MINER AO AJUSTE DE PARÂMETROS
Foi investigada também a sensibilidade do Ant-Miner para diferentes valores de alguns
parâmetros. Como descrito na Subseção 4.7, Ant-Miner possui quatro parâmetros:
•
Número de formigas (Num_formigas);
•
Número mínimo de casos por regra (Min_casos_por_regra);
•
Número
máximo
de
casos
não
cobertos
usadas
para
testar
no
conjunto
de
treinamento
(Max_casos_n_covertos);
•
Número
de
regras
a
convergência
das
formigas
(Num_regras_converg).
Dentre estes quatro parâmetros, foi considerado que os dois mais importantes são
Min_casos_por_regra e Max_casos_n_cobertos, porque estão diretamente relacionados ao
grau de generalidade das regras descobertas pelo Ant-Miner, o qual pode ter um efeito
significante na taxa de acerto e na simplicidade das regras descobertas.
Para analisar a influência destes dois parâmetros, o Ant-Miner foi executado com
valores diferentes para estes dois parâmetros. Nos experimentos três valores diferentes foram
utilizados para cada um dos parâmetros: 5, 10 e 15. Todas as combinações possíveis dos
valores foram consideradas com o Ant-Miner executando uma vez para cada combinação.
Note-se que uma destas combinações, Min_casos_por_regra = 10 e Max_casos_n_cobertos =
10, foi a combinação utilizada em todos os experimentos relatados nas subseções anteriores.
O resultado dos experimentos estão relatados na Tabela 6. A primeira coluna desta
tabela indica o valor dos dois parâmetros (primeiro o valor de Min_casos_por_regra e depois
o valor de Max_casos_n_cobertos). Cada uma das outras colunas se refere a determinada base
51
de dados específica, sendo que cada célula indica a taxa de acerto média do Ant-Miner para a
correspondente combinação de valores dos parâmetros.
Tabela 6: Taxa de acerto do Ant-Miner com diferentes valores para os parâmetros
5, 5
5, 10
5, 15
10, 5
10, 10
10, 15
15, 5
15, 10
15, 15
Ljubl. breast
cancer
77.06
74.76
74.48
75.50
75.05
75.42
74.08
74.16
75.35
Wisc. breast
tic-tac-toe dermatology
cancer
95.75
74.01
93.93
95.03
73.29
96.05
94.74
75.75
95.30
94.58
72.00
94.05
94.45
76.00
94.39
95.92
73.80
92.62
95.61
73.35
94.39
95.17
72.08
95.02
95.17
73.53
94.96
Hepatitis
91.25
91.25
78.75
92.50
91.25
80.00
77.50
77.50
76.25
Clev. Heart
Disease
55.12
58.79
57.39
57.21
59.42
58.12
58.03
59.97
59.15
Nursery
Votes
76.70
76.71
77.99
74.41
77.70
80.41
78.04
78.48
80.67
95.89
94.52
95.19
95.65
96.05
95.63
95.63
96.07
96.07
Como pode ser visto, Ant-Miner tem pouca sensibilidade à variação dos parâmetros,
para quase todas as bases de dados, ou seja, na maioria das bases a taxa de acerto não sofreu
grandes variações. A única exceção é na base hepatitis, onde a taxa de acerto do Ant-Miner
varia de 76.25% a 92.5%, dependendo dos valores dos parâmetros.
Como esperado, nenhuma combinação de valores é a melhor para todas as bases de
dados. De fato, cada combinação de valores para os parâmetros tem alguma influência sob o
bias indutivo do Ant-Miner, sendo que nenhum bias indutivo é melhor para todos
experimentos (RAO et al., 1995; SCHAFFER, 1993; SCHAFFER, 1994).
Vale a pena enfatizar que os resultados da Tabela 6 foram relatados somente para
analisar a robustez do Ant-Miner às variações de alguns de seus parâmetros. Estes resultados
não foram utilizados para otimizar o desempenho do sistema para cada base de dados, de
forma a realizar uma comparação justa entre o Ant-Miner e os outros algoritmos utilizados na
comparação dos resultados.
52
53
CAPÍTULO 6
CONCLUSÕES E TRABALHOS FUTUROS
Este trabalho apresentou um algoritmo para descoberta de regras denominado AntMiner (Ant Colony-based Data Miner – Minerador de Dados baseado em Colônias de
Formigas). O objetivo do Ant-Miner é extrair de bases de dados regras para a tarefa de
classificação. O algoritmo é baseado na pesquisa realizada sobre o comportamento das
colônias de formigas reais bem como sobre alguns conceitos e princípios de data mining.
Os resultados foram obtidos a partir de oito bases de dados de domínio público e
foram comparados com três outros algoritmos: um primeiro baseado em Redes Neurais
Artificiais do tipo multi-camadas com retro-propagação do erro (MLP-BP – Multi Layer
Perceptron com Back-Propagation), para análise e comparação somente da taxa de acerto; e
dois outros algoritmos de indução de regras muito citados e conhecidos na literatura, C4.5 e
CN2, para análise e comparação da taxa de acerto e da simplicidade do conjunto de regras
descobertas.
Os resultados mostraram que, considerando a taxa de acerto, o Ant-Miner se mostrou
competitivo com os outros algoritmos utilizados na comparação. Considerando a simplicidade
das regras descobertas (número de regras e de termos), Ant-Miner encontrou listas de regras
muito mais simples do que as encontradas pelos outros algoritmos na grande maioria dos
experimentos. Desta forma, o uso do Ant-Miner como ferramenta para extração de
conhecimento se torna vantajosa pois aumenta a compreensibilidade do conhecimento
descoberto, uma vez que o principal objetivo da aplicação deste conhecimento é o suporte à
tomada de decisão para um usuário humano (como visto na Introdução).
Com os experimentos realizados sem o procedimento de poda, conclui-se que a poda
das regras é essencial para melhorar a compreensibilidade (número de termos) das regras
descobertas pelo Ant-Miner.
Através dos resultados obtidos com o Ant-Miner executado sem a influência do
feromônio, concluiu-se que o uso de um procedimento para atualização de feromônio é
importante para melhorar a precisão preditiva das regras descobertas, principalmente quando
o feromônio interage com a informação heurística do problema. Vale a pena ressaltar que esta
melhora na precisão preditiva associada com a presença do feromônio é obtida sem sacrificar
a simplicidade das regras descobertas.
54
Os resultados obtidos, verificando a sensibilidade do Ant-Miner aos ajustes dos
parâmetros, Min_casos_por_regra e Max_casos_n_cobertos, mostraram que Ant-Miner é
robusto aos valores desses parâmetros, e que nenhuma combinação de valores é a melhor para
todas as bases de dados. Isto porque cada combinação de valores para estes parâmetros
influencia de forma diferente o bias indutivo do Ant-Miner.
Algumas direções de pesquisa para este trabalho podem ser:
•
Estender o Ant-Miner para lidar automaticamente com atributos contínuos, ao invés de
requerer que este tipo de atributo seja discretizado em um passo de pré-processamento;
•
Investigar o desempenho do Ant-Miner perante outras formas de funções heurísticas e
estratégias de atualização do feromônio;
•
Com relação às bases de dados, existem dois caminhos a serem explorados: o teste
com um número maior de bases de dados e de maior tamanho e a geração de bases de
dados artificiais para estudar a interação entre atributos e comprovar a eficácia do AntMiner de forma mais controlada;
•
Estender Ant-Miner para minerar dados que variam dinamicamente durante a execução
do algoritmo. Cabe ressaltar que, (BONABEAU, DORIGO e THERAULAZ, 1999)
sugerem que algoritmos de colônia de formigas, devido à sua flexibilidade e robustez,
são particularmente vantajosos em problemas cujos dados mudam dinamicamente;
•
Aplicar Ant-Miner em outras tarefas de data mining, tal como modelagem de
dependência.
55
REFERÊNCIAS BIBLIOGRÁFICAS
AHA, D. W., Incremental constructive induction: an instance-based approach. Proceedings of
the Eighth International Workshop on Machine Learning, San Francisco: Morgan
Kaufmann, p. 117-121, 1991.
AHA, D. W., MURPHY, P. M., UCI Repository of machine learning databases.
(http://www.ics.uci.edu/~mlearn/MLRepository.html), Department of Information and
Computer Science, University of California at Irvine, 1994.
ARAÚJO, D. L. A., LOPES, H. S., FREITAS, A. A., A parallel genetic algorithm for rule
discovery in large databases. Proceedings of the IEEE Systems, Man and Cybernetics
Conference, Tokyo, Japan, v. 3, p. 940-945, 1999.
ARAÚJO, D. L. A., LOPES, H. S., FREITAS, A. A., Rule discovery with a parallel genetic
algorithm. In: Proceedings of GECCO2000, Genetic and Evolutionary Computation
Conference, Workshop Program, Las Vegas, USA, p. 89-92, 2000.
BOHANEC, M., BRATKO, I., Trading accuracy for simplicity in decision trees. Machine
Learning, v. 15, p. 223-250, 1994.
BOJARCZUK, C. C., LOPES, H. S., FREITAS, A. A., Discovering comprehensible
classification rules using genetic programming: a case study in a medical domain.
Proceedings of GECCO-99, Genetic and Evolutionary Computation Conference,
Orlando, USA, v. 2, p. 953-958, 1999.
BOJARCZUK, C. C., LOPES, H. S., FREITAS, A. A., Genetic programming for knowledge
discovery in chest pain diagnosis. IEEE Engineering in Medicine and Biology
Magazine, v. 19, n. 4, p. 38-44, july/august, 2000.
BONABEAU, E., DORIGO, M., THERAULAZ, G., Swarm Intelligence: From Natural to
Artificial Systems. New York: Oxford University Press, 1999.
BREWLOW, L. A., AHA, D. W., Simplifying decision trees: a survey. The Knowledge
Engineering Review, v. 12, n. 1, p. 1-40, 1997.
56
BULLNHEIMER, B., HARTL, R. F., STRAUSS, C., An improved ant system algorithm for
the vehicle routing problem. Proceedings of the Sixth Viennese Workshop on Optimal
Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna
(Austria), May 21-23, 1997.
BULLNHEIMER, B., KOTSIS, G., STRAUSS, C., Parallelization strategies for the ant
system. In: De Leone, R., Murli, A., Pardalos, P., Toraldo, G. (Eds.), High Performance
Algorithms and Software in Nonlinear Optimization; Dordrecht : Kluwer, v. 24, p. 87100, 1998.
CATLETT, J., Overpruning large decision trees. Proceedings of the 12th International Joint
Conference on Artificial Intelligence, Sydney, Australia, 1991.
CHEN, M. S., HAN, J., YU P. S., Data mining: an overview from database perspective. In:
Proceedings of the IEEE Transactions on Knowledge and Data Engineering, v. 8, p.
866-883, 1996.
CLARK, P., NIBLETT, T., Induction in noisy domains. Progress in Machine Learning -
Proceedings of the 2nd European Working Session on Learning, Bled, Yugoslavia,
Sigma Press, p. 11-30, 1987.
CLARK, P., NIBLETT, T., The CN2 induction algorithm. Machine Learning, v. 3, p. 261284, 1989.
CLARK, P., BOSWELL, R., Rule induction with CN2: some recent improvements.
Proceedings of the European Working Session on Learning (EWSL-91), Lecture Notes
in Artificial Intelligence, Berlin: Springer-Verlag, v. 482, p. 151-163, 1991.
COLORNI, A., DORIGO, M., MANIEZZO, V., TRUBIAN, M., Ant system for job-shop
scheduling. Proceedings of JORBEL - Belgian Journal of Operations Research,
Statistics and Computer Science, v. 34, n. 1, p. 39-53, 1994.
CORDÓN, O., CASILLAS, J., HERRERA, F., Learning fuzzy rules using ant colony
optimization. Proceedings of ANTS’2000 – From Ant Colonies to Artificial Ants:
Second International Workshop on Ant Algorithms, p. 13-21, 2000.
COSTA, D., HERTZ, A., Ants can colour graphs. In: Proceedings of Journal of the
Operational Research Society, v. 48, p. 295-305, 1997.
57
COVER, T. M., THOMAS, J. A., Elements of Information Theory. New York: John Wiley
& Sons, 1991.
DEMIROZ, G., GOVENIR, H. A., ILTER, N., Learning differential diagnosis of eryhematosquamous diseases using voting feature intervals. Artificial Intelligence in Medicine,
1998.
DETRANO, R., JANOSI, A., STEINBRUNN, W., PFISTERER, M., SCHMID, J.,
SANDHU, S., GUPPY, K., LEE, S., FROELICHER, V., International application of a new
probability algorithm for the diagnosis of coronary artery disease. American Journal of
Cardiology, v. 64, p. 304-310, 1989.
DIACONIS, P., EFRON, B., Computer-intensive methods in statistics. Scientific American,
v. 248, 1983.
DORIGO M., MANIEZZO, V., COLORNI, A., Positive feedback as a search strategy.
Technical Report n. 91-016, Politecnico di Milano, Italy, 1991.
DORIGO, M., COLORNI A., MANIEZZO V., The ant system: optimization by a colony of
cooperating agents. Proceedings of the IEEE Transactions on Systems, Man, and
Cybernetics-Part B, v. 26, n. 1, p. 1-13, 1996.
DORIGO M., GAMBARDELLA L. M., Ant colonies for the traveling salesman problem.
BioSystems, v. 43, p. 73-81, 1997.
DORIGO, M., DI CARO, G., GAMBARDELLA., L. M., Ant algorithms for discrete
optimization. Artificial Life, v. 5, n. 2, p. 137-172, 1999.
FAUSETT, L., Fundamentals of Neural Networks: Architectures, Algorithms, and
Applications. New Jersey: Prentice-Hall, 1994.
FAYYAD, U. M., PIATETSKY-SHAPIRO, G., SMYTH, P., From data mining to knowledge
discovery: an overview. In: Fayyad, U. M., Piatetsky-Shapiro, G., Smyth P., Uthurusamy,
R. (Eds.), Advances in Knowledge Discovery & Data Mining, Cambridge: AAAI/MIT,
p. 1-34, 1996.
FIDELIS, M. V., LOPES, H. S., FREITAS, A. A., Um algoritmo genético para descobrir
regras de classificação em data mining. Anais do XIX Congresso Nacional da Sociedade
58
Brasileira de Computação - IV Encontro Nacional de Inteligência Artificial (ENIA),
Rio de Janeiro (RJ), Brasil, p. 17-30, 1999.
FIDELIS, M. V., LOPES, H.S., FREITAS, A. A., Discovering comprehensible classification
rules using a genetic algorithm. Proceedings of CEC-2000, Conference on Evolutionary
Computation, La Jolla, USA, v. 1, p. 805-811, 2000.
FREITAS, A. A., A genetic programming framework for two data minning tasks:
classification and generalized rule induction. Genetic Programming 1997: Proceedings
of the 2nd Annual Conference, Stanford, USA, p. 96-101, 1997.
FREITAS, A. A., LAVINGTON, S. H., Mining Very Large Databases with Parallel
Processing. London: Kluwer, 1998.
FREITAS, A. A., A genetic algorithm for generalized rule induction. In: R. Roy et al.
Advances in Soft Computing – Engineering Design and Manufacturing, (Proc. WSC3,
3rd On-Line World Conference on Soft Computing, hosted on the Internet, July 1998.)
Berlin: Springer-Verlag, p. 340-353, 1999.
FREITAS, A. A., A survey of evolutionary algorithms for data mining and knowledge
discovery. To appear in: Ghosh, A., Tsutsui, S. (Eds.), Advances in Evolutionary
Computation, Berlin: Springer-Verlag, 2001.
HAND, D., Construction and Assessment of Classification Rules. New York: John Wiley
& Sons, 1997.
KOHAVI, R., SAHAMI, M., Error-based and entropy-based discretization of continuous
features. Proceedings of 2nd International Conference Knowledge Discovery and Data
Mining, p. 114-119, 1996.
LOPES, H. S., COUTINHO, M. S., LIMA, W. C., An evolutionary approach to simulate
cognitive feedback learning in medical domain. In: Sanchez, E., Shibata, T., Zadeh, L.A.
(Eds.), Genetic Algorithms and Fuzzy Logic Systems. Singapore: World Scientific, p.
193-207, 1997.
MANGASARIAN, O. L., SETIONO, R., WOLBERG, W. H., Pattern recognition via linear
programming: theory and application to medical diagnosis. In: Coleman, T. F., Li, Y.
59
(Eds.), Large-scale Numerical Optimization, Philadelphia: SIAM Publications, p. 22-30,
1990.
MANIEZZO, V., COLORNI, A., The ant system applied to the quadratic assignment
problem. Proceedings of the IEEE Transactions on Knowledge and Data Engineering,
1999.
MITCHELL, T. M., The need for biases in learning generalizations (1980). Reprinted in:
Shavlik, J. W. and Dietterich, T. G. (Eds.), Readings in Machine Learning, Morgan
Kaufmann, p. 184-191, 1990.
MONMARCHE, N., On data clustering with artificial ants. In: Freitas, A. A. (Ed.), Data
Mining with Evolutionary Algorithms, Research Directions – Papers from the AAAI
Workshop. AAAI Press, p. 23-26, 1999.
NODA, E., FREITAS, A. A., LOPES, H. S., Discovering interesting prediction rules using a
genetic algorithm. Proceedings of CEC-99, Congress on Evolutionary Computation,
Washington, USA, v. 2, p. 1322-1329, 1999.
OLAVE, M., RAJKOVIC, V. e BOHANEC, M., An application for admission in public
school systems. In: Snellen, I. Th. M., van de Donk, W. B. H. J., Baquiast, J.-P. (Eds.),
Expert Systems in Public Administration, p. 145-160, New York: Elsevier Science
Publishers, 1989.
PARPINELLI, R. S., LOPES, H. S., FREITAS, A. A., An ant colony based system for data
mining: applications to medical data. In: Spector, L., Goodman, E., Wu, A., Langdon,
W.B., Voigt, H.-M., Gen, M., Sem, S., Dorigo, M., Pezeshk, S., Garzon, M., Burke, E.
(Eds.), Proceedings of GECCO-2001, Genetic and Evolutionary Computation
Conference, San Francisco, CA: Morgan Kaufmann Publishers, p. 791-800, 2001a.
PARPINELLI, R. S., LOPES, H. S., FREITAS, A. A., An ant colony algorithm for
classification rule discovery. To appear in: Abbas, H. A., Sarker, R. A., Newton, C. S.
(Eds.) Data Mining: A Heuristic Approach, Idea Group Publishing, p. 190-208, 2001b.
PARPINELLI, R. S., LOPES, H. S., FREITAS, A. A., Data mining with an ant colony
algorithm, [submetido para publicação no IEEE Transactions on Evolutionary
Computation], 2001c.
60
QUINLAN, J. R., Generating production rules from decision trees. Proceedings of the 10th
International Joint Conference on Artificial Intelligence, Milan, Italy, p. 304-307,
1987.
QUINLAN, J. R., C4.5: Programs for Machine Learning. San Francisco: Morgan
Kaufmann, 1993.
RAO, R. B., GORDON, D., SPEARS, W., For every generalization action, is there really an
equal and opposite reaction? Analysis of the conservation law for generalization
performance. Proceedings of 12th International Conference on Machine Learning, San
Mateo, CA: Morgan Kaufmann, p. 471-479, 1995.
SCHAFFER, C., Overfitting avoidance as bias. Machine Learning, v. 10, p. 153-178, 1993.
SCHAFFER, C., A conservation law for generalization performance. Proceedings of 11th
International Conference on Machine Learning, San Mateo, CA: Morgan Kaufmann, p.
259-265, 1994.
SCHLIMMER, J. C., Concept Acquisition Through Representational Adjustment.
Doctoral dissertation, Department of Information and Computer Science, University of
California, at Irvine, CA, 1987.
STÜTZLE, T., Parallelization strategies for ant colony optimization. In: Eiben, A. E., Bäck,
T., Schoenauer, M., Schwefel, H.-P. (Eds.), Proceedings of Parallel Problem Solving
from Nature - PPSN-V, Amsterdam the Netherland, Springer-Verlag, (LNCS, v.1498), p.
722-731, 1998.
STÜTZLE, T., DORIGO, M., ACO algorithms for the traveling salesman problem. In:
Miettinen, K., Makela, M., Neittaanmaki, P., Periaux, J. (Eds.), Evolutionary Algorithms
in Engineering and Computer Science, New York: John Wiley & Sons, p. 163-183,
1999.
WEISS, S. M., KULIKOWSKI, C. A., Computer Systems That Learn. San Francisco:
Morgan Kaufmann, 1991.
RESUMO:
Este trabalho propõe um algoritmo para descoberta de regras de classificação
chamado Ant-Miner (Minerador de Dados baseado em Colônias de Formigas - Ant Colonybased Data Miner). O objetivo do Ant-Miner é extrair conhecimento de bases de dados.
Conhecimento este que é representado na forma de regras de classificação. Para isto, fez-se
uma revisão da literatura sobre a recente área de pesquisa chamada Ant Colony
Optimization, a qual se baseia no comportamento de colônias de formigas reais. Revisou-se
também a literatura sobre alguns conceitos de mineração de dados. Com o intuito de
comparar os resultados do sistema aqui proposto, foram utilizados três outros algoritmos.
Um primeiro baseado em Redes Neurais Artificiais do tipo multi-camadas com retropropagação do erro (MLP-BP – Multi Layer Perceptron com Back-Propagation), para
análise e comparação somente da taxa de acerto. E dois outros algoritmos de indução de
regras muito citados e conhecidos na literatura, C4.5 e CN2, para análise e comparação da
taxa de acerto e da simplicidade do conjunto de regras descobertas. O Ant-Miner foi
aplicado a seis bases de dados de domínio público e os resultados foram comparados com
os obtidos pelos outros três algoritmos citados. Os resultados obtidos permitem concluir
que: o Ant-Miner é competitivo com os outros algoritmos utilizados na comparação, com
respeito à taxa de acerto, e o conjunto de regras descobertas pelo Ant-Miner é, na maioria
dos experimentos, mais simples do que as descobertas pelo C4.5 e pelo CN2.
PALAVRAS-CHAVE
Colônias de Formigas Artificiais, Mineração de Dados, Descoberta de Conhecimento,
Indução de Regras, Classificação
ÁREA/SUB-ÁREA DE CONHECIMENTO
1.03.00.00 – 7 Ciência da Computação
1.03.03.04 – 9 Sistemas de Informação
2001
Nº:

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DO

Transcrição

Documentos relacionados

Aplicando o Algoritmo Ant-Q na Priorização de Requisitos de

Apresentação do PowerPoint - Laboratório Associado de

Formigueiro Antworks

Ficha Técnica D´FIM GEL FORMICIDA

Fatores que dificultam o controle das formigas cortadeiras

Relação entre altura e número de folhas de duas espécies de

Clique aqui e faça o da Bula em PDF

Etiqueta Baythion Gel

Diagramas Nassi Schneiderman

Como á imos em aulas anteriores, as tentati as de compreensão de

Decompositores (Fungos e Bactérias) Os decompositores são seres