CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DO
Transcrição
CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DO
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 Análise dos resultados ............................................................................... 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.7.1 Análise dos resultados ............................................................................... 48 5.8 INFLUÊNCIA DO FEROMÔNIO.................................................................. 48 5.8.1 Análise dos resultados ............................................................................... 49 5.9 SENSIBILIDADE DO ANT-MINER AO AJUSTE DE PARÂMETROS ...... 50 5.9.1 Análise dos resultados ............................................................................... 51 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: • 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. 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: • a é o número total de atributos; • 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 5.6.1 Análise dos resultados 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 5.7.1 Análise dos resultados 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 5.8.1 Análise dos resultados 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 5.9.1 Análise dos resultados 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º: