UNIVERSIDADE FEDERAL DO RIO GRANDE DO SULINSTITUTO DE INFORMTICAPROGRAMA DE PS-GRADUAO EM COMPUTAODANIELA SCHERER DOS SANTOSBee clustering: um Algoritmo paraAgrupamento de Dados Inspirado emInteligncia de EnxamesDissertao apresentada como requisito parcialpara a obteno do grau deMestre em Cincia da ComputaoProfa. Dra. Ana L. C. BazzanOrientadorPorto Alegre, abril de 2009CIP CATALOGAO NA PUBLICAOdos Santos, Daniela SchererBee clustering: um Algoritmo para Agrupamento de DadosInspirado em Inteligncia de Enxames / Daniela Scherer dos San-tos. Porto Alegre: PPGC da UFRGS, 2009.89 p.: il.Dissertao (mestrado) Universidade Federal do Rio Grandedo Sul. Programa de Ps-Graduao em Computao, Porto Ale-gre, BRRS, 2009. Orientador: Ana L. C. Bazzan.1. Inteligncia Articial, Sistemas Multiagente, IntelignciadeEnxames, AgrupamentoDistribudodeDados, Organizaode Colnias de Abelhas. I. Bazzan, Ana L. C.. II. Ttulo.UNIVERSIDADE FEDERAL DO RIO GRANDE DO SULReitor: Prof. Carlos Alexandre NettoVice-Reitor: Prof. Rui Vicente OppermannPr-Reitor de Ps-Graduao: Prof. Aldo Bolten LucionDiretor do Instituto de Informtica: Prof. Flvio Rech WagnerCoordenador do PPGC: Prof. lvaro Freitas MoreiraBibliotecria-chefe do Instituto de Informtica: Beatriz Regina Bastos HaroSUMRIOLISTA DE ABREVIATURAS E SIGLAS. . . . . . . . . . . . . . . . . . . . 5LISTA DE SMBOLOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9RESUMO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 INTRODUO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.1 Motivao e objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.2 Organizao dos captulos . . . . . . . . . . . . . . . . . . . . . . . . . . 152 AGRUPAMENTO DE DADOS . . . . . . . . . . . . . . . . . . . . . . . 162.1 Tipos de atributos e ndices de similaridade . . . . . . . . . . . . . . . . 172.1.1 Atributos contnuos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.2 Atributos binrios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.1.3 Atributos discretos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Mtodos de agrupamento de dados . . . . . . . . . . . . . . . . . . . . . 192.2.1 Mtodos hierrquicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.2 Mtodos baseados em particionamento. . . . . . . . . . . . . . . . . . . 212.3 Mtodos para avaliar a qualidade de um agrupamento de dados . . . . 212.3.1 Medida de avaliao externa . . . . . . . . . . . . . . . . . . . . . . . . 222.3.2 Medida de avaliao interna . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Concluso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 INTELIGNCIA DE ENXAMES . . . . . . . . . . . . . . . . . . . . . . 243.1 Organizao de cemitrios. . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 Diviso de trabalho em insetos sociais . . . . . . . . . . . . . . . . . . . 263.3 Modelo de recrutamento em colnias de formigas. . . . . . . . . . . . . 273.4 Modelo de recrutamento em colnias de abelhas . . . . . . . . . . . . . 273.5 Concluso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 TRABALHOS RELACIONADOS . . . . . . . . . . . . . . . . . . . . . 304.1 Algoritmos inspirados em inteligncia de enxames . . . . . . . . . . . . 304.1.1 Algoritmos inspirados em ACO . . . . . . . . . . . . . . . . . . . . . . . 304.1.2 Algoritmos inspirados em organizaes de cemitrios . . . . . . . . . . . 354.1.3 Algoritmos inspirados por outros comportamentos baseados em intelign-cia de enxames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.2 Algoritmos distribudos . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.3 Outros algoritmos relacionados . . . . . . . . . . . . . . . . . . . . . . . 514.3.1 Algoritmo para ensemble distribudo . . . . . . . . . . . . . . . . . . . . 514.3.2 MOCLE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.3.3 K-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.3.4 Average Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.4 Estudo comparativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.5 Concluso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585 ABORDAGEM PROPOSTA . . . . . . . . . . . . . . . . . . . . . . . . 595.1 Tomada de deciso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.1.1 Deciso sobre abandonar um agente . . . . . . . . . . . . . . . . . . . . 615.1.2 Deciso sobre trocar de grupo . . . . . . . . . . . . . . . . . . . . . . . . 625.1.3 Deciso sobre recrutar agentes . . . . . . . . . . . . . . . . . . . . . . . 635.1.4 Deciso sobre aceitar um convite . . . . . . . . . . . . . . . . . . . . . . 655.2 Algoritmo bee clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 656 VALIDAO DA ABORDAGEM PROPOSTA . . . . . . . . . . . . . . 686.1 Aplicao I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.1.1 Experimentos e resultados . . . . . . . . . . . . . . . . . . . . . . . . . 696.1.2 Comportamento dos agentes . . . . . . . . . . . . . . . . . . . . . . . . 746.1.3 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2 Aplicao II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.2.1 Descrio do cenrio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776.2.2 Formao de grupos via bee clustering . . . . . . . . . . . . . . . . . . . 786.2.3 Experimentos e resultados . . . . . . . . . . . . . . . . . . . . . . . . . 816.2.4 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827 CONCLUSO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84REFERNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86LISTA DE ABREVIATURAS E SIGLASA2CA Adaptive Ant-Clustering AlgorithmACA Ant Clustering AlgorithmACO Ant Colony OptimizationACOC Ant Colony Optimization for ClusteringCSIM Clustering Algorithm based on Swarm Intelligence and K-meansI-PACE Improved Probabilistic Ant based Clustering for Distributed DatabasesMACC A Multiagent, Multiobjective Clustering AlgorithmMOCLEMulti-objective Clustering EnsembleSACA Standard Ant Clustering AlgorithmLISTA DE SMBOLOS Gravidade da tarefa Limiar Intervalo de tempo Parmetro que controla o nmero de iteraes do algoritmoA Conjunto de agentes/dados[A[ Tamanho do conjunto Ac Centride de um grupoC Classe de um objetoD Nmero de agentes danandoe(C, k) Ecincia entre a classe C e o grupo kF F-measurek GrupoK Nmero de gruposl Nmero de objetos da classe C dentro do grupo km Nmero de objetos na classe Cn Nmero de objetos no grupo kp(C, k) Preciso entre a classe C e o grupo kPa Probabilidade de abandonar um agentePd Probabilidade de danarPv Probabilidade de visitar um agenteR ndice RandS=d, v, w Conjunto de estados de um agente (d= danando; v = visitando; w =assistindo uma dana)S Estmulot TempoT TarefaU Utilidade de um grupovar Varincia intra-clusterV AgrupamentoX Conjunto de atributos dos agentes/dados[X[ Nmero de atributos do agente/dadoZ Estrutura conhecida de um conjunto de dadosLISTA DE FIGURASFigura 2.1: Passos para o agrupamento de dados. . . . . . . . . . . . . . . . . . 17Figura 2.2: Exemplo de dendrograma . . . . . . . . . . . . . . . . . . . . . . . 20Figura 5.1: Processo de agrupamento realizado pelo algoritmo bee clustering . . 60Figura 6.1: Quantidade de agentes em cada estadoS= w, v, d durante umasimulao do algoritmo bee clustering. . . . . . . . . . . . . . . . . 74Figura 6.2: Nmero de agentes no grupo 7 durante uma simulao do algoritmobee clustering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75Figura 6.3: Nmero de agentes no grupo 0 durante uma simulao do algoritmobee clustering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76Figura 6.4: Mapa Kobe usado nos experimentos . . . . . . . . . . . . . . . . . . 78LISTA DE TABELASTabela 4.1: Comparao entre os algoritmos de grupamento de dados. (1) Aplica-o, (2) Representao grca, (3) Parmetros, (4) Denio a prioride informaes, (5) Viso do ambiente, (6) Utilizao de elementoscentralizadores, (7) Algoritmo Hbrido. . . . . . . . . . . . . . . . . 57Tabela 5.1: Principais parmetros do algoritmo bee clustering . . . . . . . . . . . 61Tabela 6.1: Resumo das bases de dados utilizadas. . . . . . . . . . . . . . . . . . 69Tabela 6.2: Mdia do F-measure e ndice Rand e desvio padro sobre 60 repeti-es para os algoritmos K-means, Ant-based clustering, Average link,I-PACE e Bee clustering. . . . . . . . . . . . . . . . . . . . . . . . . 71Tabela 6.3: Mdia do ndice Rand resultante de 30 repeties para os algoritmosK-means, Average link, MOCLE e Bee clustering. . . . . . . . . . . . 73Tabela 6.4: Atributos utilizados no processo de agrupamento dos agentes no ce-nrio da RoboCup Rescue . . . . . . . . . . . . . . . . . . . . . . . 79Tabela 6.5: Pontuaoobtidade10repetiesdassimulaes: beeclusteringorientado pelo tempo ( = 30), bee clustering orientado por evento( = 30) e greedy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82RESUMOAgrupamento de dados o processo que consiste em dividir um conjunto de dados emgrupos de forma que dados semelhantes entre si permaneam no mesmo grupo enquantoque dados dissimilares sejam alocados em grupos diferentes. Tcnicas tradicionais deagrupamento de dados tm sido usualmente desenvolvidas de maneira centralizada de-pendendo assim de estruturas que devem ser acessadas e modicadas a cada passo doprocesso de agrupamento. Alm disso, os resultados gerados por tais mtodos so de-pendentes de informaes que devem ser fornecidas a priori como por exemplo nmerode grupos, tamanho do grupo ou densidade mnima/mxima permitida para o grupo. Opresente trabalho visa propor o bee clustering, um algoritmo distribudo inspirado princi-palmente em tcnicas de inteligncia de enxames como organizao de colnias de abe-lhas e alocao de tarefas em insetos sociais, desenvolvido com o objetivo de resolvero problema de agrupamento de dados sem a necessidade de pistas sobre o resultado de-sejado ou inicializao de parmetros complexos. O bee clustering capaz de formargrupos de agentes de maneira distribuda, uma necessidade tpica em cenrios de siste-mas multiagente que exijam capacidade de auto-organizao sem controle centralizado.Os resultados obtidos mostram que possvel atingir resultados comparveis as aborda-gens centralizadas.Palavras-chave: Inteligncia Articial, Sistemas Multiagente, Inteligncia de Enxames,Agrupamento Distribudo de Dados, Organizao de Colnias de Abelhas.ABSTRACTBee Clustering: a clustering algorithm inspired by swarm intelligenceClustering can be dened as a set of techniques that separate a data set into groupsof similar objects. Data items within the same group are more similar than objects ofdifferent groups. Traditional clustering methods have been usually developed in a cen-tralized fashion. One reason for this is that this form of clustering relies on data structuresthat must be accessed and modied at each step of the clustering process. Another issuewith classical clustering methods is that they need some hints about the target clustering.These hints include for example the number of clusters, the expected cluster size, or theminimum density of clusters. In this work we propose a clustering algorithm that is in-spired by swarm intelligence techniques such as the organization of bee colonies and taskallocation among social insects. Our proposed algorithm is developed in a decentralizedfashion without any initial information about number of classes, number of partitions,and size of partition, and without the need of complex parameters. The bee clusteringalgorithm is able to form groups of agents in a distributed way, a typical necessity in mul-tiagent scenarios that require self-organization without central control.The performanceof our algorithm shows that it is possible to achieve results that are comparable to thosefrom centralized approaches.Keywords:Articial Intelligence, Multiagent Systems, Swarm Intelligence, DistributedClustering, Bee Colony Organization.121 INTRODUOO processo de agrupar objetos, pessoas, animais, entre outros, realizado pelos sereshumanos em seu dia a dia de acordo com seus prprios esquemas e critrios, geralmente,com o objetivo de facilitar a realizao de alguma tarefa futura que exija o manuseio detais itens agrupados.Agrupar dados consiste em separ-los em grupos homogneos de forma que objetosque pertencem ao mesmo grupo sejam mais similares entre si do que objetos que perten-cem a grupos diferentes. A necessidade deste agrupamento surge de forma natural emmuitos campos de estudos como Biologia, Cincias Sociais, Medicina, entre outros (AN-DERBERG, 1973). Como exemplos pode-se citar: um problema que ocorre regularmentena rea de cincias sociais onde deve-se agrupar dados provenientes de questionrios deuma pesquisa para se obter o perl scio-econmico e poltico de uma populao; identi-cao de espcies animais e vegetais um exemplo encontrado na disciplina de Biologia;em bioinformtica na anlise de dados de expresso gnica onde necessria a identi-cao de padres entre milhares de genes na tentativa de elucidar as funes que estesdesempenham no organismo.As tcnicas de agrupamento de dados normalmente so dependentes de domnio, ouseja,dicilmente se encontrar uma tcnica genrica,aplicvel de maneira satisfatriaa todos os tipos de dados e em todos os contextos. Por este motivo, existem diversastcnicas e estas so de grande utilidade em diversas reas.Recentemente, muitos trabalhos tm sido desenvolvidos destacando a ecincia deabordagens estocsticas baseadas em colnias de insetos sociais (formigas, abelhas, ves-pas e cupins) para resolver problemas complexos. Estes problemas envolvem, por exem-plo, a otimizao combinatorial como o problema do caixeiro viajante (DORIGO; GAM-BARDELLA, 1997), oproblemadeatribuioquadrtica(GAMBARDELLA; TAIL-LARD;DORIGO, 1998), oproblemaderoteamento(CARO;DORIGO, 1997), entreoutros.Inteligncia de enxames (Swarm Intelligence) a denominao aplicada a tentativade desenvolvimento de algoritmos ou instrumentos para soluo distribuda de problemasinspirando-se no comportamento coletivo de colnias de insetos sociais e outras socieda-des de animais (BONABEAU; THERAULAZ; DORIGO, 1999). Algoritmos inspiradosem insetos sociais so caracterizados pela interao entre um grande nmero de agentesque percebem e modicam seu ambiente localmente.Agrupamento de dados um dos problemas no qual a rea de inteligncia de enxamespode sugerir heursticas interessantes. Diversos algoritmos para agrupamento de dadosinspirados em insetos sociais tm sido propostos com o objetivo de melhorar os resultadosobtidos com as tcnicas tradicionais.No presente trabalho apresenta-se o bee clustering, umalgoritmo para agrupamento de13dados inspirado principalmente em tcnicas de inteligncia de enxames como organiza-o de colnias de abelhas e alocao de tarefas em insetos sociais. O algoritmo propostoinspira-se no comportamento das abelhas para formar grupos de agentes que representamdados a serem agrupados. Tal comportamento conhecido como recrutamento. Na natu-reza, as abelhas viajam para longe da colmia com o objetivo de coletar nctar. Quandoeste encontrado, elas retornam para a colmia no s com o nctar coletado mas tam-bm com informaes sobre a fonte onde o encontraram. De posse dessas informaesas abelhas iniciam o processo de recrutamento de outras abelhas para coletarem alimentonesta mesma fonte de nctar. Este recrutamento realizado atravs de uma dana, conhe-cida como dana do recrutamento, um comportamento no qual uma abelha comunica adireo, distncia e qualidade de uma fonte de nctar para outras abelhas (CAMAZINE;SNEYD, 1991).Estadanadorecrutamentoutilizadapelobeeclusteringparaformargruposdeagentes. Para isso, cada agente comporta-se como uma abelha e representa um objetoa ser agrupado. Neste algoritmo as abelhas danam para recrutar novos indivduos paraparticiparem de seus grupos. Atravs deste comportamento, os agentes do algoritmo socapazes de se organizar em grupos de acordo com suas caractersticas (ou do objeto querepresenta) ou habilidades e de maneira distribuda. Isto constitue-se um fator importanteem sistemas multiagente onde os agentes no possuem conhecimento global sobre todo oambiente e precisam executar atividades sem qualquer tipo de controle centralizado.Durante o agrupamento os agentes precisam tomar decises sobre participar ou no deum grupo segundo o grau de utilidade deste agente em relao ao seu prprio grupo. Paraajudar os agentes neste processo de tomada de deciso encontrou-se inspirao no traba-lho apresentado em Agogino e Tumer (2006), onde os autores desenvolveram um mtodode ensemble de agrupamento baseado em agentes atravs da computao distribuda deuma utilidade global de um agrupamento. No bee clustering utilizou-se o clculo de umautilidade que representa a qualidade de um grupo, para que o agente pudesse decidir setroca ou no de grupo.Baseando-se nestes conceitos, o algoritmo bee clustering capaz de formar grupos deagentes com caractersticas, habilidades ou especialidades similares ou complementares.A seguir descreve-se os principais aspectos que motivaram o desenvolvimento da pre-sente pesquisa, bem como os objetivos atingidos.1.1 Motivao e objetivosDevido a grande quantidade de dados, os quais precisam ser manipulados e proces-sados por meio de computadores, o problema de agrupamento de dados pode ser vistocomo um problema de otimizao apresentando uma complexidade de ordem exponen-cial. Mtodosdeforabruta, comoenumerartodosospossveisgruposeescolheramelhor congurao so simplesmente inviveis.O nmero de maneiras de se combinar n objetos de um conjunto de dados que sedeseja agrupar em k grupos um nmero Stirling de segunda ordem 1. Este nmero podeser gerado pela denio recursiva (ANDERBERG, 1973):S(n, k) = 1, para k > 0 e n = kS(n, 0) = 0, para n 0S(n, k) = S(n1, k 1) +kS(n1, k), para 0 < k < n1trata-se do nmero de maneiras de se particionar um conjunto com n elementos em k subconjuntosdisjuntos e no-vazios.14Com o intuito de ilustrar o crescimento exponencial do nmero de solues poss-veis para um problema de agrupamento, pode-se exemplicar trs objetos a, b e c. Aoagrupar-se este conjunto em apenas um grupo tem-se abc;em dois grupos obtem-sea, bc, ab, c e ac, b; e em trs gupos tem-se a, b, c (ANDERBERG, 1973). Masse, por exemplo, possui-se 25 objetos os quais deseja-se dividir em 5 grupos, o nmeroStirling de segunda ordem neste caso :S(5)25= 2.436.684.974.110.751.Se considerarmos que o nmero de grupos desconhecido, o nmero de possibilidades a soma dos nmeros Stirling de segunda ordem. Ento, no caso de 25 objetos:j=25j=1Sj25 > 41018Ficaclaroumaenormequantidadedegruposquenopodemsercomputadosemumtempo aceitvel, mesmo para pequenas bases de dados.Noprocessodeagrupamento, abuscapelamelhorsoluonoespaodesoluesviveis um problema NP-Difcil. Diante de uma grande quantidade de possveis cami-nhos para agrupar dados, natural a existncia de um grande nmero de tcnicas paraagrupamentos. No entanto, mtodos tradicionais tm sido desenvolvidos seguindo umaabordagem centralizada, necessitando que os dados estejam localizados em um nico lo-cal, o que inviabiliza sua aplicao em contextos como, por exemplo, a Internet, onde osdados encontram-se distribudos por razes de tamanho, privacidade, dinamicidade, entreoutros. Alm disso, tcnicas centralizadas dependem de estruturas de dados que precisamser acessadas e modicadas em cada passo da operao de agrupamento, criando assimum ponto nico de falha no algoritmo.Outro inconveniente que pode ser visto em mtodos clssicos de agrupamento de da-dos que muitos destes algoritmos necessitam de algumas pistas sobre o agrupamentodesejado, como por exemplo, o nmero de grupos que devero ser gerados, o tamanhoesperado para cada grupo ou mesmo a densidade mxima ou mnima dos grupos.A motivao deste trabalho para o desenvolvimento de um algoritmo distribudo paraagrupamento de dados vem tambm de aplicaes relacionadas a sistemas multiagente.Nestes sistemas, agentes que desejam cooperar para realizar uma tarefa qualquer devemter um meio de encontrar grupos de outros agentes de acordo com algum critrio paraexecutar tal tarefa de maneira eciente. Por exemplo, em um cenrio complexo compostopor muitos agentes com diferentes especialidades e habilidades, estes agentes devem, demaneira distribuda, formar grupos entre si para realizar suas atividades em times com oobjetivo de atingir o melhor resultado possvel proveniente desta organizao.Agrupamento de agentes baseando-se em caractersticas e habilidades similares, oumesmo complementares, pode ser visto como um problema de agrupamento de dados econstitui-se o foco deste trabalho.O principal objetivo do presente trabalho a apresentao do algoritmo bee clusteringpara resolver o problema de agrupamento de dados de uma maneira descentralizada e semqualquer informao inicial relacionada ao resultado desejado ou mesmo a necessidadedo uso de parmetros complexos.151.2 Organizao dos captulosOs captulos deste trabalho esto dispostos da seguinte maneira: no Captulo2 abor-dado o problema de agrupamento de dados. So descritos os tipos de atributos e ndicesde similaridade utilizados no processo, bem como os mtodos de agrupamento existen-tes. J no Captulo 3 apresenta-se uma breve introduo sobre inteligncia de enxamesdestacando-se alguns conceitos que so necessrios para o entendimento da importnciade sua aplicao na soluo de problemas distribudos, descreve-se os principais compor-tamentos utilizados no desenvolvimento de algoritmos de agrupamento de dados inspi-rados em insetos sociais e detalha-se o comportamento de interesse do presente trabalhoencontrado nas colnias de abelhas.O Captulo 4 dedicado s abordagens para solucionar o problema de agrupamentoque esto relacionadas ao algoritmo proposto. Estas abordagens encontram-se divididasem: algoritmos inspirados em inteligncia de enxames, algoritmos distribudos e outrosalgoritmos relacionados. No nal deste captulo apresenta-se uma anlise comparativadestes algoritmos, realizada de acordo com um critrio determinado.No Captulo 5 descreve-se o algoritmo bee clustering proposto neste trabalho. Faz-se uma descrio sobre as decises que os agentes devem tomar durante o processo deexecuo do algoritmo e as solues encontradas para apoiar estas tomadas de decises.O Captulo6 apresenta a validao do mtodo bem como os resultados obtidos aps doistipos distintos de aplicao: uma utilizando-se bases de dados de domnio pblico, dasquais se conhece seu correto agrupamento e outra utilizando-se o ambiente de simulaoRoboCup Rescue que se traduz parcialmente no problema de agrupar agentes que devemoperar de forma colaborativa.Finalmente, o Captulo7 apresenta as concluses do presente trabalho e aponta pos-sveis direes de pesquisas futuras relacionadas ao algoritmo proposto.162 AGRUPAMENTO DE DADOSAgrupamento dedados o nomedado aoconjunto de tcnicasque tmpor obje-tivo separar objetos em grupos. Esta separao deve ocorrer de forma que os elementosde um conjunto sejam mutuamente similares e, preferencialmente, muito diferentes doselementos dos outros conjuntos (BERKHIN, 2002; ANDERBERG, 1973).As tcnicas de agrupamento de dados podem ser vistas como um meio de aprendi-zado no supervisionado (WITOLD, 2005; JAIN; MURTY; FLYNN, 1999; BERKHIN,2002) servindo para extrair caractersticas escondidas dos dados e desenvolver hiptesesa respeito de sua natureza. Neste ltimo caso, tais mtodos podem ser particularmentevaliosos em casos onde o resultado nal seja inesperado, ou seja, algo em que nunca setenha pensado (ANDERBERG, 1973).Jain, Murty e Flynn (1999) apontam alguns passos para realizar a tarefa de agrupa-mento de dados:1. Modelo de representao: opcionalmente inclui extrao e/ou seleo de caracte-rsticas;2. Denio de um modelo de medida de similaridade/dissimilaridade apropriado aodomnio dos dados;3. Agrupamento;4. Abstrao dos dados (se necessrio);5. Atribuio de sada (se necessrio).A seqncia dos trs primeiros passos encontra-se ilustrada na gura2.1. A primeiraetapa inclui a denio dos atributos a serem levados em considerao no processo deagrupamento dos dados. neste momento que se realiza o pr-processamento dos dados,como por exemplo normalizaes, e se dene a forma de representao destes dados, aqual, na maioria dos casos, realizada por uma matriz de objetos. Os tipos de atributosexistentes so descritos a seguir na subseo2.1.O prximo passo envolve a denio de um modelo de similaridade/dissimilaridade.Trata-se de uma mtrica usada para quanticar a similaridade entre os dados analisados.Este modelo deve ser denido de acordo com o tipo de atributo escolhido na etapa anteriore tambm ser discutido na subseo2.1.A etapa seguinte refere-se aplicao de um algoritmo de agrupamento apropriadopara o conjunto de dados. Existem diversos algoritmos que podem ser aplicados nestaetapa. Os algoritmos de agrupamento de interesse para este trabalho encontram-se descri-tos no Captulo 4.17Em seguida, tem-se as etapas de abstrao dos dados e atribuio de sada. Abstraode dados um processo de extrao da representao compacta e simples de um conjuntode dados. Simplicando-se, trata-se de uma descrio compacta de cada grupo formado.Esta etapa til em tomadas de deciso pois descreve de maneira simples e intuitiva osgrupos tornando fcil a compreenso humana.Figura 2.1: Passos para o agrupamento de dados (JAIN; MURTY; FLYNN, 1999)2.1 Tipos de atributos e ndices de similaridadePara agrupar os dados de um conjunto necessrio encontrar algum ou alguns pa-rmetros que quantiquem o grau de associatividade entre eles. Esta tarefa realizadana primeira etapa do processo de agrupamento de dados, onde se dene os atributos quesero utilizados para realizar o agrupamento. Para isso, necessrio um profundo conhe-cimento dos tipos de dados que sero trabalhados.Denidos os atributos, necessrio tambm escolher as medidas de similaridades quepodero ser utilizadas para a vericao do grau de semelhana existente entre eles. Estaescolha est diretamente associada ao tipo de atributo com o qual se est trabalhando.A seguir apresenta-se uma classicao para os tipos de atributos proposta por Ander-berg (1973) e alguns possveis mtodos para o clculo dos ndices de similaridade.2.1.1 Atributos contnuosOs atributos contnuos podem assumir qualquer valor em (WITOLD, 2005). Comoexemplospode-secitardistncia, peso, altura, quantidade, temperatura, entreoutros.Cada objeto representado por um vetor de dimenso igual ao nmero de atributos naseremconsideradosecadaelementodovetorexpressanumericamenteamedidadecada atributo.Para atributos contnuos, a mtrica mais popular para se calcular a similaridade oudissimilaridade a distncia Euclidiana (JAIN; MURTY; FLYNN, 1999):d(x, y) =ni=1(xiyi)2Outras mtricas tambm podem ser utilizadas para os atributos contnuos. Entre elaspode-se citar:Distncia City Block:d(x, y) =ni=1[ xixy[18Distncia Minkowski:d(x, y) =pni=1(xiyi)p,p>0Distncia Camberra:d(x, y) =ni=1[ xixy[xi +yi,xi e yi so positivos2.1.2 Atributos binriosOs atributos binrios podem assumir exatamente dois valores. Como exemplos pode-se citar (sim, no) como respostas em um questionrio, (F, M) sexo feminino ou mascu-lino, entre outros. Para exemplicar as mtricas utilizadas para o clculo de similaridadeconsidera-se dois vetores binrios x e y que consistem de duas strings [xk] e [yk] de dadosbinrios. Para compar-las admite-se as seguintes ocorrncias:a = nmero de ocorrncias quando xk = yk = 1;b = nmero de ocorrncias quando xk = 1 e yk = 0;c = nmero de ocorrncias quando xk = 0 e yk = 1;d = nmero de ocorrncias quando xk = yk = 0..Segundo Witold (2005), estes quatro nmeros podem ser organizados em uma matriz2x2 tambm chamada de tabela de contingncia:1 01 a b0 c dCom base nestas quatro entradas pode-se encontrar diversas medidas de similaridadede acordo com as seguintes mtricas apontadas na literatura (WITOLD, 2005; KOGAN;NICHOLAS; TEBOULLE, 2006; JAIN; DUBES, 1988):A mtrica mais simples obedece a seguinte frmula:d(x, y) =a+da+b+c +dMtrica de similaridade de Russel e Rao:d(x, y) =aa+b+c +dCoeciente de Jaccard: envolve o caso onde xi = yi = 1d(x, y) =aa+b+cCoeciente de Rogers e Tanimoto:d(x, y) =a+da+d+2(b+c)192.1.3 Atributos discretosOs atributos discretos assumem um determinado nmero de estados (JAIN; DUBES,1988). Por exemplo, para um conjunto de dados sobre as caractersticas fsicas de umgrupo de pessoas, o atributo cor dos olhos um atributo discreto que pode assumir umentre vrios estados (castanho escuro, castanho claro, preto, azul, verde).Quando se trabalha com atributos discretos, a comparao normalmente realizadavericando-seseosatributossodemesmoestadoouno. Sendoassim, Anderberg(1973) estendeu o uso das mtricas utilizadas em atributos binrios para atributos discre-tos com um novo mtodo de pesagem:na+d o nmero de atributos de mesmo estado nos dois objetos;nb+c o nmero de atributos de estados diferentes nos dois objetos.A mtrica mais simples pode ser calculada de acordo com a equao:d(x, y) =na+dna+d +nb+cPode-se tambm utilizar o coeciente de Rogers e Tanimoto:d(x, y) =na+dna+d +2nb+c2.2 Mtodos de agrupamento de dadosDiferentestcnicasparaagrupamentodedadossodescritasnaliteratura. Novasabordagens vo surgindo de acordo com a rea de aplicao, no entanto, no existemtcnicas que possam ser universalmente aplicveis (JAIN; MURTY; FLYNN, 1999).Anderberg (1973) relaciona duas categorias de mtodos para agrupamento de dados,os hierrquicos e os no hierrquicos, o qual tambm conhecido como mtodos baseadosem particionamento. Estas categorias sero discutidas a seguir.2.2.1 Mtodos hierrquicosOs mtodos de agrupamentos hierrquicos produzemuma srie de parties aninhadasformando uma hierarquia de grupos, ou seja, uma rvore de grupos denominada dendro-grama (BERKHIN, 2002; ANDERBERG, 1973; KOGAN; NICHOLAS; TEBOULLE,2006). Cada nvel da hierarquia representa uma separao do conjunto de dados em umconjunto de grupos. A gura2.2 mostra um exemplo de dendrograma resultante do agru-pamento de cinco itens (A, B, C, D e E). O topo um grupo contendo todos os cinco itens.Os demais grupos representados pela gura so [A], [B,C,D,E], [B,C] e [D,E].Kogan, NicholaseTeboulle(2006)apontamvantagensedesvantagensemseusarmtodos de agrupamento hierrquico. Dentre as vantagens pode-se citar:exibilidade com relao a granularidade;facilidade de manusear qualquer tipo de similaridade;aplicabilidade para qualquer tipo de atributo.ComodesvantagensdosmtodoshierrquicosKogan, NicholaseTeboulle(2006)relacionam os seguintes:20Figura 2.2: Exemplo de dendrogramadiculdade em escolher um critrio de parada correto;a maioria dos algoritmos no so capazes de corrigir uma associao incorreta pois,no revisitam grupos j construdos.Outra desvantagem que deve ser apontada o fato da estrutura utilizada para repre-sentar os grupos, os dendrogramas, no serem adequadas quando se est trabalhando comuma grande quantidade de dados. Grandes dendrogramas, com vrios nveis, so estrutu-ras de difcil compreenso.Os mtodos hierrquicos so geralmete aplicados em reas biolgicas, sociais e nascincias comportamentais devido a necessidade da construo de taxonomias (JAIN; DU-BES, 1988). Estes so divididos em duas categorias - aglomerativos e divisivos (KOGAN;NICHOLAS; TEBOULLE, 2006; ANDERBERG, 1973), as quais sero discutidas a se-guir.2.2.1.1 AglomerativosOs mtodos hierrquicos aglomerativos seguem uma abordagem botton-up onde cadaitem a ser agrupado tratado inicialmente como um grupo de um nico elemento quesucessivamente une-se ao grupo mais prximo, ou seja, mais similar, de acordo com umamtrica, formando outros grupos no decorrer das iteraes.Existemtrs tiposdemtricaspara severicara distnciaentredois grupos(WI-TOLD, 2005; ROMESBURG, 2004):ligao simples: a distncia entre dois grupos dada pela distncia entre os seuspontos mais prximos. Pode ser chamada tambm de neighbour clustering. Trata-se de um mtodo guloso, que tende a buscar primeiro os objetos mais prximos edeixar os mais distantes em segundo plano;ligao mdia: a distncia entre dois grupos dada pela distncia entre seus centri-des. Seu problema est no fato de que cada vez que um grupo muda, seu centridedeve ser recalculado, bem como a distncia para todos os outros grupos;ligao completa: a distncia entre dois grupos a distncia entre seus pontos maisdistantes.A seguir pode-se vericar os passos do algoritmo que descreve o funcionamento domtodo aglomerativo:211. Fazer um grupo para cada elemento;2. Encontrar pares de grupos mais similares de acordo com uma medida de similari-dade entre grupos;3. Fundir estes pares de grupos emum grupo maior e recalcular a distncia deste grupopara todos os outros elementos;4. Repetir os passos 2 e 3 at restar um nico grupo.Em cada passo do algoritmo, os dois grupos mais prximos so unidos. O processo repetido at se ter um nico grupo de dados ou at alcanar um certo limiar pr-denido(WITOLD, 2005).Um importante representante deste mtodo de agrupamento de dados o conhecidoalgoritmo Average link que ser apresentado na Seo 4.3.2.2.1.2 DivisivosOs mtodos hierrquicos divisivos,tambm conhecidos como top-down,trabalhamde forma oposta aos aglomerativos. O processo inicia com o conjunto inteiro de itens aserem agrupados, sendo considerados como um nico grupo, e prossegue dividindo-osem pequenos grupos. Em cada iterao remove-se o elemento que ca mais distante docentride do grupo. O processo interrompido quando houver apenas grupos de ele-mentos isolados. Considerando-se a natureza do processo, esta abordagem apresenta-secomputacionalmente ineciente (WITOLD, 2005).2.2.2 Mtodos baseados em particionamentoO problema de agrupamento de dados baseado em particionamento pode ser formal-mente declarado como segue (JAIN; DUBES, 1988):Dados n objetos a serem agrupados em k grupos:parte-se de um agrupamento inicial;calcula-se os pontos mdios (centrides) dos grupos;realiza-se uma iterao realocando-se os objetos entre os grupos de acordocom as distncias entre os objetos e esses pontos mdios.Os mtodos baseados em particionamento tentam maximizar as distncias entre ospontos mdios dos grupos e minimizar a distncia entre os elementos de ummesmo grupo.Estessoapropriadosemaplicaesenvolvendograndesconjuntosdedados, le-vando vantagens sobre os mtodos hierrquicos j que para uma maior quantidade de da-dos a construo de um dendrograma computacionalmente proibitiva (JAIN; MURTY;FLYNN, 1999).UmimportanteeamplamenteusadoalgoritmorepresentantedestemtodooK-means, o qual ser descrito na Seo4.3.2.3 Mtodos para avaliar a qualidade de um agrupamento de dadosValidar um agrupamento de dados signica avaliar os resultados obtidos atravs deuma anlise realizada de maneira quantitativa e objetiva (JAIN; DUBES, 1988). Com a22existncia de uma grande variedade de tcnicas de agrupamento de dados natural queexistam tambm um certo nmero de medidas de avaliao quantitativa destas tcnicas.Uma completa relao e descrio dos critrios para investigar a qualidade de um agrupa-mento pode ser encontrado em(JAIN; DUBES, 1988). No presente trabalho apresenta-sesomente as medidas de avaliao utilizadas para avaliar o resultado gerado pelo algoritmoproposto, as quais sero descritas nas prximas subsees.2.3.1 Medida de avaliao externaOprimeirogrupodefunesdeavaliaoanalticasdisponveisparaaanlisedeagrupamento aquele desenvolvido para os problemas emque o nmero correto de grupose a classicao correta para cada dado so conhecidos.Existem alguns ndices que podem ser empregados para a avaliao externa de umagrupamento. Quando a estrutura real dos dados conhecida, o nmero de grupos oprimeiro indicador de desempenho do algoritmo, no caso desta informao no ter sidodada a priori como o que ocorre em diversas abordagens para agrupamento de dados.Compara-se ento a quantidade de grupos gerada pelo algoritmo de agrupamento com onmero de grupos real para o conjunto que est sendo analisado.Uma outra medida conhecida baseada no conhecimento prvio da distribuio dosrtulos das classes C dos dados a serem agrupados.Trata-se do ndice F-measure o qualcombina as idias de preciso e cobertura para comparar o resultado obtido pelo algoritmode agrupamento dos dados com a distribuio real de classes destes dados. Para cadagrupo k relacionado a uma classe C calculado:preciso(C, k) =ln, cobertura(C, k) =lm,onde l o nmero de objetos da classe C dentro do grupo k, n o nmero total de objetosdentro do grupo k e m o nmero de objetos na classe C.O ndice F-measure da classe C e do grupo k calculado de acordo com a Equao2.1.F(C, k) = 2 preciso(C, k) cobertura(C, k)preciso(C, k) +cobertura(C, k), (2.1)O ndice F-measure total para um agrupamento computado pela Equao2.2, a qualresulta valores no intervalo [0,1] e deve ser maximizada. [A[ o tamanho do conjunto dedados.F =m[A[maxF(C, k) (2.2)Outros mtodos que geralmente so aplicados na avaliao de um agrupamento so osndices baseados nas estatsticas sobre a concordncia, positiva ou negativa, na associaode pares de objetos aos grupos. O ndice Rand penaliza as associaes diferentes de paresdeobjetosaocompararoagrupamentogeradocomacorretaclassicaodabasededados.Dado um agrupamento gerado Vcuja estrutura previamente conhecida Z, calcula-se o ndice Rand (R) de acordo com a Equao 2.3, onde as quantidades a, b, o, z socomputadas para todos os possveis pares de dados x e y e seu respectivo grupo kZ(x),kZ(y), kV(x), e kV(y). R limitado ao intervalo [0,1] e deve ser maximizado.23R =a+za+b+o+z, (2.3)com:a =x, y[kZ(x) = kZ(y) kV(x) = kV(y),b =x, y[kZ(x) = kZ(y) kV(x) ,= kV(y),o =x, y[kZ(x) ,= kZ(y) kV(x) = kV(y),z =x, y[kZ(x) ,= kZ(y) kV(x) ,= kV(y).O ndice R resultar em 1 somente quando o agrupamento gerado for exatamente iguala estrutura real conhecida. Por outro lado, pequenos valores resultantes de R indicam umaumento na falta de concordncia entre estas duas estruturas.2.3.2 Medida de avaliao internaAs medidas de avaliao interna medema qualidade do agrupamento gerado baseando-se apenas no conjunto de dados originais. Estas medidas so normalmente usadas quandoa estrutura real dos dados no conhecida.Existem alguns ndices que podem ser empregados para a avaliao interna de umagrupamento. Entre os mais conhecidos destaca-se a varincia intra-cluster, o qual serabordado no presente trabalho por se tratar da medida utilizada para avaliar a qualidadedo grupo pelo algoritmo proposto.A varincia intra-cluster var(V) de um agrupamento V baseada na minimizao dosomatrio das distncias entre os elementos e os centrides de seus grupos. var(V) dadapela Equao 2.4, onde K o nmero de grupos, n o nmero de elementos dentro dogrupo k, ck o centride do grupo k e d(i, ck) a funo de distncia empregada entre oelemento i e o centride ck.var(V) =Kk=1(kV)ni=1(ik)d(i, ck) (2.4)Quanto menor o valor resultante de var(V), melhor o agrupamento gerado.2.4 ConclusoNeste captulo apresentou-se conceitos relacionados a rea de agrupamento de dados.Moustrou-se as etapas para se realizar um agrupamento, bem como os tipos de atributosque podem ser manipulados e os ndices de similaridade que devem ser utilizados duranteo processo de acordo com estes atributos. Finalmente, descreveu-se alguns mtodos paravalidao do agrupamento gerado por um algoritmo.No prximo captulo apresenta-se uma breve introduo sobre inteligncia de enxa-mesdestacando-sealgunsconceitosquesonecessriosparaoentendimentodarele-vnciadesuaaplicaonasoluodeproblemasdistribudoseconsequentementenodesenvolvimento do algoritmo proposto.243 INTELIGNCIA DE ENXAMESOs insetos sociais - formigas, abelhas, vespas e cupins - tm sido objeto de estudos dediversos cientistas principalmente devido ao seu sucesso ecolgico.Este sucesso justi-cado pela ecincia de seu trabalho em conjunto. Um inseto pode ter apenas algumascentenas de clulas cerebrais, mas a sua organizao capaz de maravilhas arquitetnicas,de elaborar sistemas de comunicao e de resistir s terrveis ameaas da natureza (RUS-SEL; NORVIG, 1995). Sua capacidade coletiva emerge da interao com o ambiente eentre os indivduos, embora estes tenham uma cognio limitada. O repertrio individualdos insetos limitado e, no entanto, produz, em conjunto, um resultado surpreendente.Inteligncia de enxames (Swarm Intelligence) a denominao aplicada a tentativade desenvolvimento de algoritmos ou instrumentos para soluo distribuda de problemasinspirando-se no comportamento coletivo de colnias de insetos sociais e outras socieda-des de animais. Pesquisadores tm muitas razes para achar o estudo de inteligncia deenxames atrativo pois, oferece um caminho alternativo para o desenvolvimento de siste-mas inteligentes por possuir autonomia, emergncia e controle distribudo (BONABEAU;THERAULAZ; DORIGO, 1999).Como exemplos naturais de inteligncia de enxames pode-se citar a construo deninhos pelo trmites ou sociedades de abelhas, a atividade forrageadora das formigas, adiviso de trabalho e alocao de tarefas nas colnias de formigas, o transporte coopera-tivo de comida, a seleo de melhor fonte de nctar pelas abelhas, entre outros. O que hde comum nestes comportamentos so algumas caractersticas destacadas a seguir:exibilidade: a colnia pode responder perturbaes internas e desaos externos;controle distribudo: na colnia no existe um indivduo centralizador que direcionaa realizao das tarefas, a organizao emerge das interaes entre os constituintesdo sistema e entre os indivduos e o ambiente;robustez: um colapso individual no provoca a falha do sistema;auto-organizao: caminhos para as solues so emergentes e no pr-denidos.Solues para diferentes tipos de problemas tm sido encontradas usando heursticasbaseadas em comportamento de formigas e outros insetos. Em Bonabeau, Theraulaz eDorigo(1999)soapontadosalgunsalgoritmosparasoluodeproblemasinspiradosno comportamento de insetos sociais. Um exemplo Ant Colony Optimization (ACO),uma meta-heurstica que usa formigas articiais para encontrar solues para problemasde otimizao combinatorial. O algoritmo inspira-se no comportamento observado emcolnias de formigas,que estabelecem coletivamente a menor rota entre uma fonte de25alimento e seu ninho por meio de trilhas de feromnio deixadas ao longo do caminho(DORIGO; DI CARO; GAMBARDELLA, 1999). Dentre as aplicaes do algoritmo,pode-se citar o roteamento de veculos, a colorao de grafos e o roteamento em redes decomunicao, entre outros.Uma outra metfora aplicada diz respeito a alocao de tarefas, processo que ajustao nmero de formigas operrias engajadas em cada tarefa de forma apropriada a situ-ao corrente (GORDON, 1996). Em sociedades de insetos, diferentes atividades sofrequentemente realizadas simultaneamente por indivduos especialistas. Este fenmeno chamado diviso de trabalho e mostra-se mais eciente do que se as tarefas fossemrealizadas sequencialmente por indivduos no especializados.Nareadeagrupamentodedadospode-seencontrardiversostrabalhosutilizandointeligncia de enxames com o objetivo de melhorar os resultados obtidos com as tcnicastradicionais. Os principais comportamentos inspiradores destes trabalhos so a metforade organizao de cemitrios e a escolha do menor caminho mediante depsito de umhormnio denominado feromnio. Ambos so comportamentos apresentados na naturezapor colnias de formigas reais.Aseguir, descreve-seosprincipaiscomportamentosutilizadosemalgoritmosparaagrupamento de dados, organizao de cemitrios e escolha do menor caminho, junta-mente com outro comportamento, a diviso de trabalho, utilizado pelo algoritmo propostocomo inspirao para ajudar os agentes no processo de tomada de deciso sobre recrutaroutros agentes para fazer parte de seus grupos. A Seo 3.4 apresenta a dana do re-crutamento, um comportamento exibido pelas abelhas de uma colnia, o qual inspirou oprocesso de formao de grupos utilizado pelo algoritmo neste trabalho.3.1 Organizao de cemitriosDiversas espcies de formigas separam os corpos de formigas mortas, formando umcemitrio, ouagrupamsuaslarvasemdiversaspilhas. Estecomportamentosimplestem incentivado diversos autores (BONABEAU; THERAULAZ; DORIGO, 1999; MON-MARCH; SLIMANE; VENTURINI, 1999; VIZINE et al., 2005) a desenvolver novasabordagens para solucionar o problema de agrupamento de dados.Grande parte dos algoritmos para agrupamento de dados inspirados em insetos sociaispartem de uma abordagem apresentada por Bonabeau, Theraulaz e Dorigo (1999). Estaabordagem deu origem ao Ant Clustering Algorithm (ACA). Seu mecanismo, inspiradona construo de cemitrios, contm formigas gentes que movem-se aleatoriamente emum grid bidimensional e quando encontram-se com um objeto (tambm distribudo alea-toriamente no mesmo grid) tm uma grande probabilidade de colet-lo se este localiza-seem uma regio com pouca concentrao de outros objetos. Da mesma forma, a probabili-dade de depositar um objeto em um determinado local alta se a formiga estiver em umarea que contm muitos objetos. A idia geral que dados isolados devem ser coletados eposteriormente depositados em uma outra posio onde mais dados daquele tipo estejampresentes.Formalmente pode-se denir que a probabilidade pp de um agente (formiga) coletarum objeto dada pela Equao 3.1, onde f a frao de objetos percebidos na vizinhanado agente, ou seja, pode ser visto como a viso que cada formiga possui, k1 um limiarconstante.26pp =_k1k1 + f_2(3.1)Quandof k1, pp prximo de 1, ou seja, a probabilidade de coletar um objeto altaquando no h muitos outros objetos na vizinhana. pp prximo de 0 quandof k1,ou seja, diculta a remoo dos objetos de locais onde h uma certa concentrao.Por outro lado, a probabilidade pd de um agente depositar um objeto que est carre-gando dada pela Equao 3.2, onde k2 outro limiar constante.pd =_fk2 + f_2(3.2)Baseando-se nestas simples regras os agentes conseguem formar grupos de objetossemelhantes.Para se utilizar este modelo como uma ferramenta de agrupamento de dados neces-srio denir f como uma funo do problema a ser tratado. No contexto de robtica,por exemplo, f foi denida como o nmero Nde objetos encontrados durante as lti-mas T unidades de tempo dividido pelo maior nmero possvel de objetos que podem serencontrados durante T.3.2 Diviso de trabalho em insetos sociaisNa natureza, nas colnias de insetos sociais diferentes atividades so frequentementerealizadassimultaneamenteporindivduosespecialistas. Estefenmenoconhecidocomo diviso de trabalho. A especializao permite aos indivduos uma maior ecinciana realizao das tarefas por conhec-las e possuir habilidades para realiz-las (BONA-BEAU; THERAULAZ; DORIGO, 1999).Para explicar este comportamento de diviso de trabalho exibido pelos insetos soci-ais, existem alguns modelos tericos e matemticos. Em Bonabeau, Theraulaz e Dorigo(1999, Captulo 3), descrito um modelo que depende de um limiar de resposta que cadaindivduo possui associado ao estmulo para realizar determinada tarefa. Sendo assim,um indivduo tende a executar uma tarefa quando o estmulo S para execut-la ultrapassaseu limiar associado. O limiar de resposta , expresso em unidades de intensidade deestmulo, uma varivel interna que determina a tendncia de um indivduo, respondendoao estmulo S, realizar a tarefa associada.A Equao3.3 mostra a funo para o clculo da probabilidade (T), ou tendncia, deum indivduo atender a resposta a um estmulo.T =S2iS2i +2i(3.3)Se o valor do limiar S a probabilidade do indivduo realizar a tarefa tende a 0. Poroutro lado, se o valor do limiar S a probabilidade Ttende a 1. No entanto, quando = S a probabilidade exatamente12.Utilizou-se este modelo de estmulo resposta no algoritmo proposto como um meca-nismo a ser utilizado pelo agente na tomada de deciso. Tal aplicao ser posteriormentedetalhada na Seo5.1.273.3 Modelo de recrutamento em colnias de formigasMuitas espcies de formigas apresentam um comportamento interessante quando es-to procurando por alimento: elas depositam uma substncia qumica, chamada ferom-nio, ao longo do caminho entre o ninho e a fonte de alimento, formando trilhas. Outrasformigas, atradas por este feromnio, seguem esta trilha e tambm encontram a fonte.Este processo no qual uma formiga guiada para uma fonte por meio da trilha de ferom-nio denominado recrutamento (BONABEAU; THERAULAZ; DORIGO, 1999).O Ant colony optimization (ACO) (DORIGO; MANIEZZO; COLORNI, 1996) umaclasse de algoritmos baseadas em insetos sociais que tem suas origens no comportamentode recrutamento. Os algoritmos ACO foram inspirados por uma experincia usando col-nias de formigas reais na qual, mediante a apresentao de dois possveis caminhos doninho at uma fonte de alimento, aps determinado tempo, a maioria das formigas seleci-onava o caminho mais curto para atingir o alimento desejado. A emergncia do comporta-mento de seleo do caminho mais curto ocorre devido a forma de comunicao indiretaentre as formigas por meio das trilhas de feromnio (DORIGO; DI CARO, 1999). Essacomunicao indireta via ambiente denominada stigmergia. Maiores detalhes sobre otema podem ser encontrados em Camazine et al. (2003).No ACO, a principal tarefa de uma formiga encontrar o menor caminho entre umpar de nodos em um grafo, no qual o problema adequadamente mapeado. Desta forma,G = (N, E) um grafo conectado com n = [N[ nodos. De maneira simplicada, o algo-ritmo ACO pode ser usado para encontrar uma soluo para o problema de caminho maiscurto denido no grafo G, onde a soluo um caminho no grafo conectando um nodofonte s a um nodo destino d. Para cada arco (i, j) do grafo, associada uma variveli j chamada trilha de feromnio articial. A quantidade de feromnio na trilha propor-cional a utilidade de usar o arco para construir uma boa soluo. Cada formiga aplica,passo-a-passo, uma poltica de deciso construtiva para construir a soluo do problema.Aregra de deciso de uma formiga k localizada emumnodo i usa a trilha de feromnioi j para calcular a probabilidade pki j de escolher o nodoj Ni como o prximo nodo paravisitar. Ento:pki j =_i jsej Ni0 sej/ NiEnquanto constroem uma soluo, formigas depositam uma quantidade constante de feromnio nos arcos por onde passam. Considerando-se uma formiga que no tempo tmove-se de um nodo i para um nodo j, a atualizao do feromnio i j ocorre como segue:i j(t) i j(t) + (3.4)Assim, o uso de um arco conectando um nodo i ao nodoj aumenta a probabilidade deoutras formigas usarem este mesmo arco no futuro.Com o objetivo de fazer com que asformigas explorem diferentes arcos durante todo o processo de busca, foi adicionado umcomportamento de evaporao do feromnio. Desta forma, (1), onde [0,1]em cada iterao do algoritmo.3.4 Modelo de recrutamento em colnias de abelhasO principal comportamento de interesse do presente trabalho encontra-se nas colniasde abelhas e chama-se dana do recrutamento. As abelhas de uma colnia selecionam28coletivamente a melhor fonte de nctar disponvel usando regras comportamentais muitosimples. Durante o processo de procura por alimento as abelhas viajam at 10 km longede sua colmia pra coletar nctar. Aps encontr-lo, cada abelha retorna para a colmiacom informaes sobre a fonte do nctar coletado e pode apresentar trs possveis com-portamentos:compartilhar informaes sobre a fonte do nctar coletado por meio da dana dorecrutamento,um comportamento no qual uma abelha comunica para suas com-panheiras a direo, distncia e qualidade da fonte encontrada tentando recrut-laspara tambm forragearem naquela fonte;continuar coletando nctar na mesma fonte sem tentar recrutar outras abelhas;abandonar a fonte de nctar encontrada e posicionar-se em uma rea dentro da col-mia, denominada pista de dana, a m de observar companheiras que esto dan-ando para suas fontes de nctar e ser atrada para forragear em uma outra fonte.Em Seeley, Camazine e Sneyd (1991) os autores apresentaram um experimento mos-trando como o processo de recrutamento acontece. Duas fontes de nctar so apresentadaspara uma colnia de abelhas: fonte A e fonte B (a qual melhor). Foi vericado que, pas-sados alguns minutos, toda a colnia concentra sua atividade de coleta na fonte B, aquelaque possui nctar de melhor qualidade. O experimento mostrou que a deciso de cadaabelha baseada em informaes limitadas sobre a fonte de nctar que foi visitada. Noentanto, embora simples, este comportamento faz com que a colnia selecione a fonte demelhor qualidade.Baseando-se nestas informaes, Camazine e Sneyd (1991) desenvolveram um mo-delo matemtico que demonstra como as propriedades do sistema emergem de interaesentre os agentes. Este modelo baseado em agentes com as seguintes probabilidades:PXA e PXB: probabilidade de abandonar as fontes de nctar A e B respectivamente;PDA e PDB: probabilidade de executar a dana para recrutar companheiras para asfonte de nctar A e B respectivamente, onde PD = 1PX;PFA e PFB: probabilidade de atender ao convite de uma abelha danarina pra forra-gear nas fonte A e B respectivamente. PFA e PFB so calculadas de acordo com asEquaes 3.5 e 3.6 , onde dA e dB indicam a proporo de tempo que as abelhasdanam para as fontes A e B respectivamente, DA e DB representam o nmero deabelhas forrageando nas fontes A e B respectivamente.PFA =DAdADAdA +DBdB(3.5)PFB =DBdBDAdA +DBdB(3.6)Omodelo matemtico proposto emCamazine e Sneyd (1991) reete o comportamentoobservado em colnias de abelhas na natureza. Aps determinados ciclos de tempo osagentes do modelo agrupam-se nas fontes de maior qualidade.293.5 ConclusoNo presente captulo apresentou-se conceitos relacionados a inteligncia de enxames,descreveu-se os dois principais comportamentos utilizados em pesquisas relacionadas aagrupamento de dados inspirados em insetos sociais e detalhou-se o comportamento deinteresse deste trabalho, a dana de recrutamento das abelhas, o qual inspirou o desenvol-vimento do algoritmo proposto.A capacidade de agrupamento encontrada nas colnias de abelhas durante o processodecoletadealimentosmostracomoumcomportamentososticadoemergedaintera-o entre seres bastante simples. Os mecanismos utilizados pelas abelhas na atividadede recrutamento sero aplicados na soluo do problema de agrupamento de dados noalgoritmo proposto no Captulo5.304 TRABALHOS RELACIONADOSO presente captulo rene alguns algoritmos para agrupamento de dados, relaciona-dos ao algoritmo proposto, que foram investigados para o desenvolvimento do presentetrabalho. A apresentao destes trabalhos encontra-se dividida em trs categorias:Algoritmos inspirados por inteligncia de enxames;Algoritmos distribudos;Algoritmos para ensemble de agrupamento.No nal deste captulo encontra-se uma comparao entre todos os algoritmos apre-sentados destacando-se suas principais caractersticas.4.1 Algoritmos inspirados em inteligncia de enxamesNesta seo apresenta-se alguns algoritmos relacionados ao bee clustering que tam-bm so inspirados por inteligncia de enxames. Tais algoritmos encontram-se subdi-vididos em trs categorias de acordo com a inspirao biolgica utilizada: algoritmosinspirados em ACO, algoritmos inspirados em organizaes de cemitrios e algoritmosinspirados em outros comportamentos relacionados com inteligncia de enxames.4.1.1 Algoritmos inspirados em ACOA primeira classe de algoritmos para agrupamento de dados a ser apresentada aquelaque utiliza como inspirao biolgica o comportamento de recrutamento exibido por al-gumas colnias de formigas. Tal comportamento encontra-se descrito na Seo 3.3. Aseguir, ento, apresenta-se alguns exemplos de algoritmos inspirados em ACO para resol-ver o problema de agrupamento de dados.4.1.1.1 Algoritmo ShelokarUm importante representante dos algoritmos inspirados em ACO utilizados para agru-pamentos o algoritmo proposto por Shelokar, Jayaraman e Kulkarni (2004). Como osautores no deram um nome ao seu algoritmo, no presente trabalho ele ser referenciadocomo algoritmo Shelokar.O algoritmo Shelokar depende de trilhas de feromnio para guiar formigas de formaque elas selecionem um grupo para cada objeto. Uma busca local necessria para me-lhorar a soluo a cada iterao antes da trilha de feromnio ser alterada. O valor da trilhade feromnio dado por i j no nodo (i, j). Onde i o objeto ej o grupo. No algoritmo,31formigas visitam os dados um de cada vez, sequencialmente, e selecionam um grupo parao objeto considerando unicamente a concentrao de feromnio.O algoritmo considera R agentes (formigas) para construir solues. Um agente co-mea com um vetor de solues vazio S de tamanho N (nmero de objetos para agrupar).O valor atribudo aos elementos de S representa o nmero do grupo para o qual o objeto associado.No incio do algoritmo a matriz de feromnio de tamanho N K(K= nmero degrupos), inicializada com pequenos valores de 0. Para gerar uma soluo S, a formigaseleciona o nmero do grupo da seguinte maneira:usando a probabilidade q0: o grupo com concentrao mxima de feromnio es-colhido. q0 um nmero denido a priori, 0 < q0 < 1. Os resultados apresentadospelo autor foram simulados com q0 = 0, 98;usando uma distribuio estocstica, pi j, com probabilidade (1q0). Onde,pi j =i jKk=1ikj = 1, ..., K (4.1)onde pi j a probabilidade do objeto i participar do grupoj.A qualidade da soluo construda pela formiga medida de acordo com a seguintefuno objetivo:MinF(w, m) =Kj=1Ni=1nv=1wi j | xivmjv|2(4.2)tal queKj=1wi j = 1, i = 1,..., N (4.3)Ni=1wi j = 1, j = 1,..., K (4.4)onde xiv o valor do vthatributo do ithobjeto, m uma matriz de centros de tamanho Kn,n o nmero de atributos, mjv a mdia dos valores dos vthatributos de todos os objetosno grupoj, w uma matriz de pesos de tamanho N K, wi j um peso associado do objetoxi com o grupoj o qual pode ser atribudo da seguinte maneira:wi j =_1 se o objeto i est contido no grupoj0 seno(4.5)onde i = 1,..., N, j = 1,..., Kmjv pode ser calculado de acordo com a equao abaixo:mjv = Nt=1wi jxivNt=1wi j, j = 1,..., K, v = 1,..., n (4.6)O algoritmo Shelokar ainda realiza uma busca local em L solues geradas pelas for-migas. L representa as 20% melhores solues do total de solues. Antes da busca local,32as formigas so organizadas em ordem crescente de acordo com o valor resultante naequao 4.2.Apsabuscalocal, amatrizdeferomnioalteradaconsiderandoasLmelhoressolues entre os R membros de acordo com a seguinte equao:i j(t +1) = (1)i j(t) +Ll=1li j, i = 1, ..., N, j = 1,..., K (4.7)onde apersistnciadatrilhaquerespeitaointervalo[0, 1]e(1 )ataxadeevaporao do feromnio. Valores de mais altos, indicam que as informaes coletadasnas iteraes passadas so esquecidas mais rapidamente. A quantidade li j igual a 1/Flse o grupoj atribudo ao ithelemento da soluo construda pela formiga l, seno 0. A soluo tima aquela que minimiza o valor da funo objetivo, equao 4.2. Ovalor da melhor soluo na memria ser alterado para o valor da soluo obtida comoa melhor soluo da iterao se esta obtiver com a funo objetivo um valor mais baixoque a melhor soluo na memria.Desta forma, o algoritmo Shelokar executa repetidamente os trs passos a seguir atum valor mximo de iteraes:1. gerao de novas R solues pelas formigas usando a informao da trilha de fe-romnio modicada originada das iteraes anteriores;2. realizao de uma busca local;3. alterao da matriz de feromnios.O algoritmo foi testado em base de dados reais e articiais e comparado com aborda-gens inspiradas em algoritmos genticos e busca tabu. Segundo os autores, o algoritmoShelokar mostrou-se uma abordagem vivel e uma eciente heurstica para o grupamentode dados, j que resultou em solues de boa qualidade em aceitvel tempo de processa-mento.Como pode ser visto, o algoritmo apresenta exatamente a mesma limitao impostapelo k-means, necessidade de denio a priori do nmero de grupos em que o conjuntode dados ser particionado, alm de depender de informaes disponveis em vrias es-truturas de dados.4.1.1.2 ACOCOutro exemplo de algoritmo para agrupamento de dados inspirado no modelo do ACO o Ant Colony Optimization for Clustering (ACOC) (KAO; CHENG, 2006). Dado umconjuntodedadoscontendomobjetoscomnatributoseumnmerodegrupospr-determinado (g) o ACOC encontra um agrupamento timo. O algoritmo possui comomodelo de espao de soluo um grafo que representa a matriz de objetos que devem seragrupados. O nmero de linhas igual a m e o nmero de colunas igual a g. Se um nodo denotado por N(i, j) signica que o objeto i ser atribudo ao grupoj. No grafo, cadaformiga move-se de um nodo para outro, depositando feromnio nos nodos e construindouma soluo. Os nodos com mais feromnio sero mais atrativos para as outras formigas.Em cada passo, uma formiga seleciona aleatoriamente um objeto no agrupado e o adi-ciona a um novo nodo considerando a intensidade do feromnio e a distncia euclidianaentre o objeto a ser agrupado e cada centro de grupo armazenado na matriz de centros (Ck)carregada pela formiga. Cada formiga possui, alm da matriz de centros, uma lista que33representa sua memria (tbk), para evitar que um objeto seja agrupado mais de uma vezpor uma formiga. Quando esta lista est cheia, signica que a formiga completou a cons-truo da soluo. A formiga tambm mantm uma matriz de feromnio para armazenaros valores.O algoritmo ACOC pode ser resumido nos seguintes passos:1. Inicializao da matriz de feromnios: os elementos da matriz de feromnio (PM)so inicializados arbitrariamente com valores baixos (0);2. Inicializao de todas as variveis internas das formigas: para cada formiga, ressetaa lista de memria (tbk), a matriz de centros (Ck), de tamanho gn, e a matriz depesos (Wk), de tamanho mg, onde k = 1 R. R o total de formigas, R m;3. Seleo de um objeto: cada formiga seleciona aleatoriamente um objeto i que noest em sua lista de memria (tbk);4. Seleo de um grupoj para o objeto i:para determinar j, duas estratgias podemser aplicadas:(a) Explorao: permite que formigas movam-se de maneira gulosa para um nodocujo produto do nvel de feromnio e o valor da heurstica sejam os mais altos.j =_arg maxuNi[(i, u)][nk(i, u)] se q qoS seno(4.8)onde Ni o conjunto de g nodos nos quais o objeto i pode ser colocado,q um valor probabilstico gerado aleatoriamente, q0 um valor probabilsticodenido a priori, umparmetro especicando o relativo peso de nki j, >0.nki j = 1/dk(i, j) e um valor heurstico de N(i, j) para uma formiga k. O valorde S escolhido de acordo com a Equao4.9.Pk(i, j) =[(i, u)][nk(i, u)]gj=1[(i, u)][nk(i, u)](4.9)A distncia entre o objeto i e o centroj de uma formiga k, dk(i, j), denidopela distncia euclidiana:dk(i, j) =nv=1(xivckjv)2(4.10)onde ckjv refere-se ao atributo v do centroj da formiga k, xiv o valor do vthatributo do ithobjeto.(b) Sondagem: distribui probabilidades para nodos candidatos, e deixa a formigaescolher um deles de maneira estocstica de acordo com a equao 4.9. Onodo mais promissor aquele que tiver a mais alta probabilidade.Para escolher entre as duas possveis estratgias, as formigas utilizam a equao4.8.345. Alterao da informao da formiga: alterar a lista de memria (tbk),matriz depesos (wk) usando a equao 4.11 e a matriz de centros (Ck) usando a equao4.12.wi j =_1 se o objeto i1,...,m agrupado no grupoj1,...,g0 seno(4.11)Cj = mi=1wi jXimi=1wi j(4.12)ondej = 1, ..., g, X a matriz de objetos de tamanho mn, wi j o peso associadode xi com cj, xi o vetor do ithobjeto e xi Rn, cj o vetor dojthcentro de grupoe cj Rn.6. Vericao da lista de memria de cada formiga: checar se a lista de memria decada formiga est cheia. Se est cheia, vai para o passo 7, seno volta para o passo3;7. Clculo da funo objetivo: calcular o valor da funo objetivo de cada formiga,Jk, de acordo com a seguinte equao:MinimizeJ(W,C) =mi=1gj=1wi j|XiCj| (4.13)onde|XiCj| =nv=1(xivcjv)2(4.14)Aps, classica-se as R formigas em ordem crescente de Jk. A melhor soluo chamada de melhor soluo da iterao e comparada com a melhor soluoencontrada proveniente de outras iteraes. A melhor das duas ser a nova melhorsoluo encontrada. Oresultado da comparao armazenado para posteriormenteser comparado com outras melhores solues encontradas nas iteraes.8. Alterao da trilha de feromnio: alterar a matriz de feromnio (PM). A regra dealterao global aplicada e somente as formigas elitistas podem adicionar ferom-nio no nal de cada iterao.9. Vericao da condio de parada: se o nmero de iteraes exceder o nmeromximo permitido, ento o algoritmo pra e retorna a melhor soluo encontrada,seno, volta para o passo 2.OalgoritmoACOCrepresentaumaextensodoalgoritmopropostoporShelokar,Jayaraman e Kulkarni (2004), explicado anteriormente, onde a diferena signicante exis-tente entre os dois que o ACOC no limita-se unicamente ao agrupamento baseado naquantidade de feromnio, ele tambm leva em considerao a distncia euclidiana entreo objeto e o centro de uma formiga. Esta caracterstica faz com que o ACOC se destaquena qualidade das solues produzidas.O testes foram realizados pelos autores com bases de dados reais e articiais. Seusresultados, comparados com aqueles obtidos com o algoritmo Shelokar e K-means, mos-traram que embora seu desempenho seja bem inferior ao K-means, as solues geradasforam melhores. J com relao ao algoritmo Shelokar, o ACOC mostrou-se melhor emdesempenho e nas solues construdas.35Uma decincia vericada no algoritmo ACOC com relao ao emprego, para cadaformiga, de uma memria para evitar que um objeto seja agrupado mais de uma vez.Desta forma as formigas deixam de ter um conhecimento puramente local, como ocorrecom formigas reais, para apresentarem um conhecimento do sistema em um nvel maisglobal. Em Johnson (2003) o fato da ignorncia ser uma caracterstica e no um defeito apontado como um dos princpios para se obter sucesso global por meio de conhecimentolocal. Johnson (2003) menciona ainda que melhor se construir sistemas descentralizadoscom elementos simples densamente interconectados e deixar que o comportamente maissosticado ocorra aos poucos.4.1.2 Algoritmos inspirados em organizaes de cemitriosOutra classe de algoritmos a ser apresentada no presente trabalho aquela que utilizacomo inspirao biolgica o comportamento de organizao de cemitrios, tambm exi-bido por algumas colnias de formigas. A maioria dos algoritmos para agrupamento dedados que so inspirados em inteligncia de enxames costumam utilizar este tipo de com-portamento natural como inspirao. Tal comportamento encontra-se descrito na Seo3.1. Aseguir, encontram-sedetalhadosalgunsalgoritmosinspiradosnestecomporta-mento.4.1.2.1 SACALumer e Faieta (1994) desenvolveram o algoritmo Standard Ant Clustering Algorithm(SACA) inspirado no algoritmo ACA, apresentado na Seo 3.1. Os dados que deve-riam ser agrupados foram tomados em um espao Euclidiano de dimenso L, L. Comoambiente os autores utilizaram uma grade bi-dimensional com vizinhana unitria.A funof calculada pela seguinte equao:f (Xi) =_1S2xjViz(sxs)_1d(Xi,Xj)_sef > 00 seno(4.15)ondef (Xi) a medida da similaridade mdia do item Xi em relao a outro item Xj navizinhana de Xj, [0, 1] um fator que dene a escala de dissimilaridade, d(Xi, Xj) [0, 1] a distncia Euclidiana entre os dados Xi e Xj em seus espaos originais, e S2 otamanho da vizinhana local (normalmente S2 [9, 25]).No SACA, as probabilidades de um agente coletar e depositar um objeto so dadaspelas equaes 4.16 e 4.17 respectivamente.pp(Xi) =_k1k1 + f (Xi)_2(4.16)pd(Xi) =_2 f (Xi) sef (Xi) < k20 sef (Xi) k2s(4.17)Da mesma forma que no algoritmo ACA, k1 e k2 so limiares constantes.Uma das maiores diculdades em aplicar o SACA para resolver problemas complexosvem do fato de que ele gera um nmero de grupos que bem maior que a quantidadenecessria. Alm disso, o algoritmo geralmente no estabiliza em uma soluo, ou seja,ca constantemente construindo e desconstruindo grupos durante suas iteraes.A seguir,apresenta-se o algoritmo A2CA desenvolvido com o intuito de superar osproblemas anteriormente mencionados.364.1.2.2 A2CAEm Vizine et al. (2005) proposto o Adaptive Ant-Clustering Algorithm (A2CA), umalgoritmo para agrupamento de dados com o objetivo de melhorar os resultados j obtidoscom o algoritmo SACA.O A2CA , alm de ter sido inspirado no comportamento de agrupamento de corpospelas formigas, tambm buscou inspirao no comportamento dos cupins que enquantoesto construindo seu ninho, depositam feromnio nas pores de terra empilhadas, ser-vindo como sinal de reforo para outros cupins empilharem mais terra na mesma regio.Outra inspirao biolgica leva em considerao o fato de que as formigas no se limi-tam a perceber somente suas vizinhas imediatas, elas tm um poder de alcance um poucomaior que varia no tempo e de formiga para formiga.Da mesma forma que no SACA, a idia geral do algoritmo consiste em um grid comobjetos alocados aleatoriamente e formigas caminhando aleatoriamente para tentar agru-par os objetos que so mais similares respeitando aqueles dois comportamentos, citadosanteriormente, de coletar e depositar um determinado objeto em uma posio do grid.Para superar alguns problemas encontrados no SACA, o A2CA prope trs modica-es:1. um decaimento de k1 (limiar que no SACA era constante):a cada ciclo (10000 passos) k1 sofre umdecaimento geomtrico: k10.98k1 (k1min = 0.001)2. um campo de viso progressiva:o algoritmo SACA dene um campo de viso xo para a formiga, o que podealgumas vezes causar comportamentos inapropriados por no permitir a dis-tino entre grupos de diferentes tamanhos. Uma rea de percepo pequena,implica em uma pequena percepo dos grupos em um nvel global. Por outrolado, uma grande rea de percepo pode ser ineciente nas iteraes iniciais.Sendo assim, o A2CA prope um campo de viso progressivo, ou seja, quandoa formiga percebe um grande grupo ela incrementa o seu campo de viso s2iem ns unidades at alcanar seu valor mximo. Portanto, s2i um parmetroespecco para cada formiga que ser dinamicamente e independentementealterado enquanto o algoritmo executado. Assim, sef (Xi) > e s2 s2maxento s2s2+ns. Os autores sugerem s2max = 77 e = 0.6.3. uma heurstica inspirada no processo de feedback positivo 1por meio de feromniodepositado pelos cupins quando esto realizando a tarefa de construo de ninhos:o algoritmo prope a adio de uma varivel (i) associada com cada posioi do grid, tal que a quantidade de feromnio naquela exata posio torna-seuma funo de presena ou ausncia de um objeto em i. A formiga articialadicionar feromnio no objeto que est transportando e este ser transferidopara a posio do grid quando o objeto for depositado. Durante cada iterao,o feromnio (i) de cada clula dogridevapora de acordo com uma taxaxa. A probabilidade de uma formiga pegar um objeto do grid inversamente1so simples regras comportamentais que executadas pelos agentes, e mediante a obteno de bons re-sultados, fazem com que os demais agentes tambm passem a atuar segundo estas regras. Maiores detalhespodem ser encontrados em Camazine et al. (2003).37proporcional quantidade de feromnio da posio do objeto e densidadede objetos ao redor de i. A abordagem proposta aumenta a probabilidade dedesconstruo de grupos pequenos e de alocao de objetos em grupos maisdensos. Desta forma, as probabilidades de coletar e depositar um objeto emumadeterminadaposioidogrid, sodadaspelasequaes4.18e4.19respectivamente.pp(i) =1f (i)(i)_k1k1 + f (i)_2(4.18)pd(i) = f (i)(i)_f (i)k2 + f (i)_2(4.19)onde, f (i) a funo dependente da densidade de objetos.A taxa na qual o feromnio evapora em cada posio do grid calculada de acordocom: (i) (i) 0.99.Para a validao do algoritmo os autores tambm utilizaram bases de dados reais earticiais, comparando os seus resultados com o algoritmo SACA. Segundo os autores,o A2CA conseguiu superar o SACA demonstrando robustez para classicar os dados deuma base em um nmero correto de grupos, baixa variao nos resultados, e estabilizaoaps um nmero xo de iteraes automaticamente denidas pelo algoritmo.Os autores do A2CA preocuparam-se em proporcionar a apresentao dos resultadosobtidos de maneira visual em um grid bidimensional, o que, segundo eles, pode ajudar ousurio a lidar com a sobrecarga de informaes.A caracterstica acima mencionada pode ser apontada como vantagem somente se oalgoritmo estiver tratando uma base de dados relativamente pequena. Caso contrrio arepresentao dos grupos em um grid bidimensional car invivel.4.1.2.3 AntClassMonmarch, Slimane e Venturini (1999) desenvolveram o algoritmo denominado Ant-Class com o objetivo de agrupar dados numricos sem a necessidade de se denir a prioriquantos grupos sero necessrios, como ocorre com o K-means.No AntClass as formigas esto aptas a criar, construir e destruir pilhas de objetos.Uma pilha consiste de uma coleo de pelo menos dois objetos.O algoritmo base (Algoritmo 1) inspira-se no comportamento de organizao de ce-mitrios, ou seja, o de coletar e depositar um objeto em determinada posio.Algorithm 1: Algoritmo base AntClassInicialize aleatoriamente as formigas no grid ; 1repeat 2foreach formiga anti do 3Move anti ; 4if anti no est carregando nenhum objeto then 5Procedure 1 ; 6else 7Procedure 2 ; 8until critrio de parada; 938NoAntClassasformigasnomovimentam-sedeformatotalmentealeatriacomoocorre em outros algoritmos. O Move, mostrado no algoritmo 1, indica que a formigaseleciona uma entre oito possveis direes e ento com uma probabilidade Pdirection elacontinua na direo selecionada ou gera aleatoriamente uma nova direo.As formigas do algoritmo AntClass podem visualizar tanto objetos quanto pilhas deobjetos a serem agrupados. Quando uma formiga visualiza uma pilha H para agrupar, aqual possui mais que dois objetos, ela coleta o objeto mais dissimilar, Odissim, desde quesua dissimilaridade respeite a seguinte restrio:D(Odissim(H), Ocenter(H))Dmean(H)> Tremoveonde Ocenter(H) e Dmean(H) so calculados segundo as Equaes 4.20 e 4.21 respecti-vamente.Ocenter(H) =1nHOiHOi(4.20)Dmean(H) =1nHOiHD(Oi, Ocenter(H)) (4.21)nH a quantidade de objetos na pilha, D a distncia Euclidiana e Tremove [0.1, 0.2] ovalor mnimo de dissimilaridade necessrio para remover um objeto de uma pilha.Procedure 1 ColetarObjetoRotular as 8 c posies vizinhas a anti como inexploradas; 1repeat 2foreachci do 3if ci est ocupado com um objeto O then 4Pegue O com probabilidade Pload; 5else if ci est ocupado com uma pilha H com dois objetos then 6Remova um dos dois objetos com probabilidade Pdestroy; 7else if ci est ocupado com uma pilha H com mais que dois objetos then 8if (D(Odissim(H),Ocenter(H))Dmean(H)> Tremove) then9Remova o objeto mais dissimilar Odissim(H) ; 10Rotular ci como explorado; 11until todas as posies tenham sido exploradas ou um objeto tenha sido coletado; 12Por outro lado, quando uma formiga est carregando um objeto, ela verica as oitoposies ao redor de sua posio corrente e considera trs possveis casos:se a posio est vazia: ento a formiga possui uma probabilidade Pdrop de depositaro objeto;se a posio contm somente um objeto O/: a formiga depositar o objeto O em O/e criar uma pilha de dois objetos contanto que a seguinte restrio seja satisfeita:D(O, O/)Dmax< Tcreate39onde Tcreate o mximo valor de dissimilaridade permitido para criar uma pilha dedois objetos, e Dmax calculado de acordo com a Equao4.22. seguinte equao:Dmax(H) = maxOi,OjHD(Oi, Oj) (4.22)se a posio contm uma pilha H: neste caso a formiga adiciona o objeto O em Hcontanto que:D(O, Ocenter(H)) < D(Odissim(H), Ocenter(H))Procedure 2 DepositarObjetoRotular as 8 c posies vizinhas a anti como inexploradas; 1repeat 2foreach ci = 1, ..., 8 do 3if ci est vazio then 4Deposite O com probabilidade Pdrop; 5else if ci est ocupado com um objeto O/ then 6if (D(O,O/)Dmax) < Tcreate then7Deposite O em O/ para criar uma pilha; 8else if ci est ocupado com uma pilha H then 9if D(O, Ocenter(H)) < D(Odissim(H), Ocenter(H)) then 10Deposite O em H ; 11Rotular ci como explorado; 12until todas as posies tenham sido exploradas ou um objeto tenha sido 13depositado;UmaoutracaractersticaimportantedoAntClassestrelacionadaamemrialocaldecadaformiga. Destaforma, quandoumaformigaencontraumapilhaHqualquer,ela armazena em sua memria a sua localizao, Ocenter(H), D(ODissim(H), Ocenter(H)) equando est carregando um objeto, ela busca em sua memria por uma pilha no qual elapoderia depositar aquele objeto. Se ela encontra, ento a memria desta pilha ativada ea formiga vai at a sua posio. Se a formiga no depositar o objeto em outras pilhas queencontrar no caminho, ento ela depositar o objeto na pilha alvo, desde que ela aindaesteja vlida, ou seja, no tenha sido destruda ou muito modicada por outra formiga.A memria da formiga possui quatro posies. Sendo assim, quando uma nova pilha encontrada e a sua memria est cheia, as pilhas mais velhas so substitudas pela novafazendo com que a formiga esquea as pilhas antigas. Esta memorizao foi adicionada aformiga com o intuito de aumentar e acelerar a atribuio de objetos as pilhas.O desempenho do AntClass mostrou-se ineciente com as caracterstica apresentadasanteriormente, j que sua convergncia alm de ser longa era difcil de ser atingida. Sendoassim, os autores combinaram o algoritmo K-means a sua abordagem com o intuito decorrigir os erros de agrupamento cometidos pelas formigas e tambmagrupar rapidamentee ecientemente os objetos no agrupados por elas.40A combinao do K-means com o algoritmo realizado pelas formigas mostrou-se v-lida pelo fato de corrigir diversas classicaes realizadas de maneira incorreta. No en-tanto, deixou a desejar no sentido de que o nmero de grupos gerados foi sempre supe-restimado. Isto fez com que os autores introduzissem uma outra abordagem inspirada emagrupamentos hierrquicos.Desta forma, aps ser executado o algoritmo baseado no comportamento das formigase o algoritmo K-means, uma verso modicada do algoritmo das formigas executadapara completar o processo. A modicao proposta foi simplesmente que ao invs delidar com coleta e depsito de objetos, agora as formigas trabalham na coleta e depsitode pilhas inteiras diminuindo assim o nmero de grupos gerados.A adio deste terceiro passo ao algoritmo AntClass fez com que pequenos erros declassicao voltassem a acontecer. Para solucionar este problema os autores introduzi-ram um outro passo adicional ao algoritmo, rodando novamente o K-means. Sendo assim,o algoritmo AntClass constitue-se de quatro passos:1. o algoritmo baseado no comportamento de formigas;2. algoritmo K-means usando o agrupamento inicial fornecido pelas formigas;3. o algoritmo das formigas modicado, onde elas carregam pilhas inteiras de objetosao invs de um nico objeto;4. e novamente o K-means.O AntClass foi aplicado pelos autores em bases de dados numricos reais e articiaise comparado com K-means e ISODATA (BALL; HALL, 1965), uma verso melhoradado K-means. Como resultado, o AntClass se mostrou superior aos demais ao realizar umagrupamento de melhor qualidade.OalgoritmoAntClassnorequerqualquerinformaoinicial sobreoparticiona-mento, o que constitue uma importante vantagem. Entretanto dependente de uma sriede parmetros gerados em um intervalo pr-determinado pelos autores. Isto poderia serum problema se todos os agentes do modelo assumissem os mesmos valores. No en-tanto, a abordagem de agentes heterogneos aplicada ao algoritmo parece ter superadoeste inconveniente.4.1.2.4 CSIMUm outro algoritmo, denominado Clustering Algorithm based on Swarm Intelligenceand K-means (CSIM) e inspirado na organizao de cemitrios, encontrado em Bin etal. (2002). O CSIM foi desenvolvido com o propsito de agrupar documentos. Ele traba-lha de maneira semelhante ao algoritmo ACA apresentado em (BONABEAU; THERAU-LAZ; DORIGO, 1999). Sendo assim, o processo de agrupamento ocorre baseando-se nasprobabilidades de coletar e depositar objetos em determinadas posies formando gruposde objetos similares.Para cada documento oi em uma coleo de documentos k, V o conjunto de palavrasnicas encontrado em k e m =[V[. O vetor Oi = (wi1, wi2, wi3, ..., wim) representa o docu-mento oi, onde wi j a freqncia da palavra wj no documento oi. O CSIM detalhadono Algoritmo 4.Para medir a similaridade entre um par de documentos, o CSIM usa a seguinte equa-o:sim(oi, oj) = wi1wj1 +... +wimwjm[oi[ [oj[(4.23)41Algorithm 4: Algoritmo base CSIMantNumber o nmero total de formigas; 1n o nmero de iteraes; 2 um coeciente de similaridade; 3pr uma probabilidade gerada aleatoriamente; 4k um limiar constante; 5Inicializar o coeciente , antNumber, n, k e demais parmetros necessrios; 6Atribuir um par de coordenadas (x, y) para cada objeto; 7Inicializar as antNumber formigas e atribuir a cada uma um objeto; 8repeat 9foreachj = 1, ..., antNumber do 10Computar a similaridade do objeto dentro de uma regio local com raio r de 11acordo com a equao 4.26;if formiga est descarregada then 12Calcular a probabilidade Pp de coletar o objeto de acordo com a 13equao 4.24;Comparar Pp com a probabilidade Pr; 14if (Pp < Pr) then 15a formiga no coletar este objeto; 16outro objeto aleatoriamente atribudo a formiga; 17else 18a formiga coleta o objeto e troca seu estado para carregada; 19um novo par de coordenadas passado como posio pra formiga; 20else if formiga est carregada then 21Calcular a probabilidade Pd de depositar o objeto de acordo com a 22equao 4.25;if (Pp > Pr) then 23a formiga depositar o objeto; 24outro objeto aleatoriamente atribudo a formiga; 25um novo par de coordenadas passado como posio pra 26formiga;else 27um novo par de coordenadas passado como posio pra 28formiga;a formiga continua com o mesmo objeto; 29until n; 3042onde (wi1, ..., wim) indica o documento oi e (wj1, ..., wjm) indica o documento oj.As probabilidades de coletar e depositar um objeto so calculadas de acordo com asequaes 4.24 e 4.25 respectivamente.Pp =___1 f (oi) 01k f (oi) 0 < f (oi) 1k0 f (oi) > 1k(4.24)Pd =___1 f (oi) 1kk f (oi) 0 < f (oi) 1k0 f (oi) 0(4.25)onde k um limiar constante ef (oi) calculado de acordo com a seguinte equao:f (oi) =ojNeigh(r)_110(1sim(di, dj))_(4.26) [1, 10] um coeciente de similaridade, di e dj so calculados pelas equaes 4.27 e4.28 respectivamente.[di[ =mk=1w2ik(4.27)[dj[ =mk=1w2jk(4.28)Da mesma maneira que o AntClass, o CSIM emprega o algoritmo K-means para me-lhorar os resultados obtidos. Desta forma, composto de duas fases:1. um conjunto inicial de grupos formado pelo algoritmo base (Algoritmo 4);2. em seguida o mtodo K-means empregado otimizando os resultados.O CSIM foi testado em trs bases de documentos reais e comparado com o K-meanse CSI (BIN; ZHONGZHI, 2001). Os resultados mostraram um melhor desempenho doCSIM em relao aos demais algoritmos no domnio de agrupamento de documentos.4.1.2.5 Algoritmo baseado em mltiplas colnias de formigasEm Yang e Kamel (2006) proposto um algoritmo que, alm da organizao de cemi-trios, imita o comportamento cooperativo de colnias de formigas, onde diversas col-nias trabalham paralelamente e independentemente cooperando mutuamente atravs datroca de informaes para encontrar uma soluo otimizada. O algoritmo consiste deduas partes: uma onde diversas colnias de formigas, independentes, usando o algoritmobsico ACA (BONABEAU; THERAULAZ; DORIGO, 1999), agrupam um conjunto deobjetos e outra onde uma formiga rainha junta os agrupamentos das diferentes colnias.Os algoritmos 5, 6 e 7 descrevem todo o procedimento envolvido neste mtodo deagrupamento de dados.Oalgoritmoconsistedemltiplascolniasdeformigastrabalhandoparalelamenteparaproduziromelhoragrupamentopossveldeumconjuntodedados. Ascolniasso heterogneas com quatro tipos diferentes de possveis determinao dos parmetros(coeciente de similaridade), v (velocidade da formiga) (coeciente de dissimilari-dade):43Algorithm 5: Agrupamento inspirado em mltiplas colniasN o nmero de colnias de formigas; 1antNumber o nmero de formigas em cada colnia; 2Inicializar os coecientes N, M, antNumber e demais parmetros necessrios; 3repeat 4Agrupamento baseado em formigas(); 5until N; 61. constante: todas as formigas possuem os mesmos valores para os parmetros;2. aleatrio: os valores so distribudos aleatoriamente entre [1, valor mximo];3. aleatoriamente dividido: metade das formigas assume um determinado valor en-quanto que a outra metade assume outro;4. aleatoriamente diminudo: os parmetros iniciam com valores altos que vo de-caindo gradativamente de maneira aleatria.A probabilidade de uma formiga descarregada, movendo-se aleatoriamente, coletarum objeto calculada pela equao 4.29 enquanto que a probabilidade de uma formigadepositar o objeto que est carregando calculada pela equao 4.30, ondef (oi), denotaa similaridade entre o objeto i e os demais objetos localizados na vizinhana da formiga,e pode ser calculada pela equao 4.31 ou 4.32. Z a matriz de similaridade nxn, umcoeciente de dissimilaridade e um coeciente de similaridade. Se receber um valormuito alto, resultar em uma tendncia maior dos objetos carem no mesmo grupo. Poroutro lado, quando recebe um valor baixo, a similaridade diminuir e pode ocasionarum resultado extremo de muitos grupos separados.Pp(oi) = 1sigmoid( f (oi)) (4.29)Pd(oi) = sigmoid( f (oi)) (4.30)ondesigmoid(x) =11+ecxcx uma varivel que pode acelerar a convergncia do algoritmo quando incrementada.Durante o procedimento de agrupamento, podem haver alguns objetos muito dissimilaresde todos os outros elementos. As formigas tendem a car bloqueadas tentando posicionarestes objetos diminuindo a velocidade da convergncia do algoritmo. Quando isto ocorre,o parmetro cx pode ser alterado para um valor maior com o objetivo de ajudar as formigasa depositarem estes objetos dissimilares nos prximos estgios do algoritmo.f (oi) =oiNeighsxs(r)_1d(oi, oj)_(4.31)f (oi) =oiNeighsxs(r)_Z[i, j]_(4.32)44Algorithm 6: Agrupamento baseado em formigas()Mm o nmero mximo de iteraes; 1Atribuir aleatoriamente um objeto para cada formiga que est descarregada; 2repeat 3foreachj = 1, ..., antNumber do 4if Agrupamento inspirado em mltiplas colnias (Algoritmo 5) then 5Computar a similaridade do objeto dentro de uma regio local de 6acordo com a equao 4.31;else if Agrupamento agregado (Algoritmo7) then 7Computar a similaridade do objeto de acordo com a equao 4.32; 8if formiga est descarregada then 9Calcular a probabilidade Pp de coletar o objeto de acordo com a 10equao 4.29;Comparar Pp com a probabilidade Pr; 11if (Pp < Pr) then 12a formiga no coletar este objeto; 13outro objeto aleatoriamente atribudo a formiga; 14else 15a formiga coleta o objeto e troca seu estado para carregada; 16move o objeto para uma nova posio; 17else if formiga est carregada then 18Calcular a probabilidade Pd de depositar o objeto de acordo com a 19equao 4.30;if (Pp > Pr) then 20a formiga depositar o objeto; 21a formiga troca seu estado para descarregada; 22outro objeto aleatoriamente atribudo a formiga; 23else 24a formiga continua com o mesmo objeto movendo-o para uma nova 25posio;until Mn; 26Algorithm 7: Agrupamento agregado()M o nmero mximo de iteraes; 1repeat 2Coletar o resultado do agrupamento gerado em (Algorithm 5); 3Computar a matriz de adjacncia H de acordo com a equao 4.34; 4Calcular a matriz de similaridades Z de acordo com a equao 4.33 e envi-la 5de volta para cada colnia de formiga;Selecionar um agrupamento como grupo de dados atual para a colnia de 6formigas de acordo com uma das estratgias: KP, CE, ou LO;foreach i = 1, ..., N do 7Agrupamento baseado em formigas(); 8until M; 945A tarefa da formiga rainha agregar os agrupamentos gerados pelas diversas col-nias e calcular uma nova matriz de similaridade de acordo com a equao 4.33. O =(o1, o2, ..., on) representa um conjunto de objetos, e um agrupamento destes n objetos emk grupos pode ser representado com um vetor Nn. r so os grupos de agrupamentos,que a formiga rainha precisa analisar, com o qthagrupamento (q)tendo k(q)grupos. Anova matriz de similaridades enviada para cada colnia, a qual continuar a re-agrupar,s que usando esta nova informao e um novo conjunto de dados. Este novo conjunto dedados escolhido de acordo com as seguintes estratgias:KP(keepingpredecessor): Cadacolniacontinuacomseultimoagrupamentoresultante ;CE (circular exchange): Cada colnia escolhe o ltimo agrupamento resultante dasua colnia vizinha pela direita (ou esquerda);LO(lowest outliers): Cada colnia escolhe o conjunto de dados resultante do ltimoagrupamento, com o nmero mais baixo de objetos muito dissimilares dos demais.Este procedimento repetido at que os agrupamentos resultantes no tenham maismodicaes.Z = 1rHHT(4.33)onde a matriz HT a transposio da matriz H, Z a matriz esparsa nxn.H = (H(1)...H(r)) (4.34)Para validar o algoritmo, os autores utilizaram bases de dados reais e articiais. OsresultadosobtidosmostraramqueoalgoritmoobteveumdesempenhosuperioraoK-means e ao algoritmo Shelokar. No entanto, o algoritmo apresenta uma limitao comrelao a necessidade de se determinar a priori o nmero de colnias e tambm quanto adeterminao de seus parmetros.4.1.3 Algoritmos inspirados por outros comportamentos baseados em intelignciade enxamesOutros comportamentos, alm dos citados anteriormente nas sees 3.1 e 3.3, soutilizados como inspirao para o desenvolvimento de solues para o problema de agru-pamento de dados.A seguir sero descritos alguns destes algoritmos e suas respectivas inspiraes bio-lgicas.4.1.3.1 AntClustEm Labroche, Monmarch e Venturini (2002) proposto o algoritmo AntClust, umnovo mtodo para resolver o problema de agrupamento de dados baseado na modelagemdo sistema de reconhecimento qumico de formigas. Este sistema permite que formigaspercebam as diferenas entre companheiras e intrusas, e ento criem grupos homogneosdeindivduosquecompartilhamomesmoodor. Ocomportamentoocorreemquatrodistintos nveis de anlise para cada formiga:1. A existncia de um odor qumico, parcialmente construdo pela formiga, depen-dente da espcie e do ambiente;462. Um mecanismo de recepo qumica, o qual permite a percepo do odor qumicode outras formigas;3. Um modelo de referncia que indica o tipo de odor que uma companheira de ninhodeveria possuir. Este modelo aprendido e continuamente alterado;4. Um conjunto de regras de decises que dispara comportamentos de acordo com asimilaridade entre os modelos de referncia e o odor percebido em uma formiga.De maneira simplicada, a cada iterao do algoritmo AntClust duas formigas, seleci-onadas aleatoriamente, encont