Na Figura 18 é possível observar o comportamento do algoritmo para todas as medidas de avaliação propostas.
Surgimento ou Desaparecimento de Grupos
Os resultados dos testes de surgimento e desaparecimento de grupos resultaram no compor- tamento esperado, ou seja, ao se eliminar um grupo inteiro os grupos restantes não são impac- tados e os agrupamentos já formados continuam voando sem apresentar variações. Quando
um grupo surge novamente há um rápido impacto, pois vários Boids são incluídos em uma única iteração. Em poucas iterações, os Boids recém incluídos passam a voar em grupo estabi- lizando o resultado como um todo.
Movimentação no Espaço
Apesar da base Ruspini ter seus grupos claramente isolados, existem alguns poucos objetos que, com as devidas atualizações em seus atributos, podem mudar de grupo ao longo da exe- cução do algoritmo. Apesar de raro para esta base, este comportamento pôde ser observado esporadicamente, quando após a atualização de seus atributos alguns objetos passaram a voar ao lado de outro grupo. Os objetos com maiores chances de alteração de grupos são os conti- dos dentro da área em destaque na Figura 17. Devido à proximidade entre eles na distribuição no plano 2D, é possível que seus atributos sejam suficientemente alterados a ponto de troca- rem de grupo.
Figura 17: Objetos com maiores chances de alteração de grupo durante as iterações.
Inclusão/Exclusão de Objetos
Os resultados de inclusão e exclusão de objetos também ocorreram conforme o esperado: ao remo- ver um objeto da base o restante dos grupos não sofre impactos significativos, mantendo os agru- pamentos já existentes. Ao se incluir novamente um objeto, este passa a voar isoladamente no ambi- ente até encontrar seu grupo correto. É possível que um objeto voe temporariamente ao lado de um grupo incorreto se este grupo for o primeiro a ser percebido durante o voo do Boid recém incluído. Porém, ao se encontrar com o grupo correto o Boid abandona o grupo incorreto e passa a fazer parte do grupo correto.
Figura 18: Dinâmica do algoritmo dcBoids para a base de dados Ruspini ao longo das iterações.
Os gráficos das medidas de avaliação para a base de dados Ruspini mostram, em todos os casos, uma estabilização que antecede a aplicação das técnicas de atualização da base de da-
dos. O algoritmo responde adequadamente às atualizações, sendo capaz de manter a estrutura já encontrada para os grupos sem grandes perturbações pelos objetos que têm seus atributos atualizados. Em todas as execuções o desaparecimento/surgimento de grupos é a atualização que mais interfere nas medidas de avaliação gerando os picos e vales que podem ser observa- dos na Figura 18(b)-(f) a partir da iteração de número 350, quando ocorre a reinclusão dos objetos no ambiente. Conforme discutido, esta perturbação ocorre pelo fato de que os objetos são reinseridos em posições aleatórias no ambiente e isto faz que o cálculo das medidas de atualização sofra interferências até que o algoritmo volte a se estabilizar. Na Figura 18Figura(a) é possível observar uma pequena variação no número de grupos na iteração de número 300. Nesta iteração ocorre a exclusão de um grupo inteiro, o que reduz o número de grupos de quatro para três. Esta exclusão não causa perturbações nos outros gráficos, pois os três grupos restantes continuam voando na formação alcançada até o momento.
4.3.2.3 Resultados K-Médias
Na Figur é possível observar os resultados obtidos para o agrupamento proposto pelo algorit- mo k-médias, k = 4. Estes resultados também mostram uma estabilização bastante rápida de todas as medidas de avaliação. Como esta base contém quatro classes claramente separadas, os centroides também representam bem seus grupos, fazendo com que as variações introduzi- das na base não gerem interferências nas medidas de avaliação. Na Figur(a) observa-se uma linha reta, que indica que o algoritmo sempre terá k grupos presentes em sua execução. Na Figur(b)-(f) observa-se uma queda nas medidas de desempenho a partir da iteração 300, quando um grupo é excluído. Após a iteração 350, quando os objetos do grupo são devolvidos à base, o algoritmo reinicia a estabilização até atingir novamente o agrupamento ótimo. Os resultados finais para o dcBoids e para o k-médias foram os mesmos em relação à qualidade dos agrupamentos. O dcBoids consegue atingir o mesmo número de clusters que o k-médias, mesmo sem conhecer esta informação à priori e, além disso, responde bem às atualizações dos objetos, mostrando uma resposta em tempo real e evidenciando que as alterações nos objetos são percebidas pelos Boids imediatamente após sua ocorrência.
Figura 19: Dinâmica do algoritmo k-médias para a base Ruspini ao longo das iterações.
4.3.3 BASE YEAST
A base Yeast consiste em um conjunto de dados de expressão gênica formado por 205 objetos que representam proteínas de leveduras, contendo vinte atributos cada um. Estes 205 objetos estão alocados em quatro clusters distintos de acordo com a localização das proteínas.
4.3.3.1 Caso Estático
Na Tabela 7 são apresentados os resultados do agrupamento em ambiente estático para a base de dados Yeast. Diferentemente das duas primeiras bases, esta base apresenta algumas classi- ficações incorretas e é possível perceber que para todas as medidas de avaliação, o desempe- nho do dcBoids foi superior, em termos absolutos, do que o k-médias.
Tabela 7: Desempenho dos algoritmos dcBoids e k-médias quando aplicados a base de dados Yeast.
dcBoids k-médias k 4.3 0.67 (4, 6) 4 0 (4, 4) Índice de Dunn 0.81 0.03 (0.76, 0.84) 0.76 0 (0.76, 0.76) Acurácia (%) 80.1 1.59 (78, 82) 76.5 0 (76.5, 76.5) Pureza 0.95 0.02 (0.91, 0.97) 0.92 0 (0.92, 0.92) Entropia 0.12 0.01 (0.11, 0.16) 0.15 0 (0.15, 0.15) Índice de Jaccard 0.66 0.02 (0.63, 0.69) 0.62 0 (0.62, 0.62)
A Figura 20 apresenta uma configuração inicial e final típica para a base de dados Yeast.
Figura 20: Iterações inicial e final para o agrupamento da base Yeast.
4.3.3.2 Caso Dinâmico
Figura 21: Dinâmica do algoritmo dcBoids para a base Yeast ao longo das iterações.
Os resultados obtidos para a base de dados Yeast evidenciam que o algoritmo proposto é ca- paz de convergir e encontrar os quatro grupos na maioria de suas execuções. Porém, apesar de convergir para o número correto de grupos, os resultados para esta base, diferentemente das duas primeiras, apresentam algumas classificações incorretas. Estas classificações incorretas podem ser observadas na Figura 20, pois as cores dos Boids são definidas antes do início da execução com base nos clusters corretos. Assim, grupos com mais de uma cor indicam que classificações incorretas foram realizadas. Figura 21(a) é possível observar que o número de grupos chega muito próximo a quatro, mas a estabilização não é tão evidente quanto nas bases Ruspini e Animais. Na Figura 21(b)-(f) pode-se perceber também que os valores das medidas de avaliação não conseguem alcançar seus valores máximos, como ocorre nas duas primeiras bases de dados. Os resultados, porém, são consistentes com o que é mostrado na Figura 20, onde, por meio da coloração dos Boids, percebe-se que algumas classificações são feitas in- corretamente.
Apesar de o algoritmo não conseguir alcançar a classificação com 100% de acerto, o funcio- namento geral do algoritmo se mantém no mesmo padrão das bases apresentadas anteriormen- te. Ou seja, a exclusão/inclusão de grupos continua sendo a dinâmica que causa maiores per- turbações nas medidas de avaliação, enquanto a atualização de objetos isolados promove pou- cas variações no funcionamento do algoritmo. Os picos e vales observados na iteração 350 representam o momento exato em que os grupos são reapresentados ao algoritmo e as itera- ções seguintes mostram a convergência do mesmo.
4.3.3.3 Resultados K-Médias
A Figura 22 apresenta o comportamento do algoritmo k-médias para a base Yeast, k = 4.
Figura 22: Dinâmica do algoritmo k-médias para a base Yeast ao longo das iterações.
Os resultados para o algoritmo k-médias seguem o mesmo padrão dos testes anteriores em relação à estabilidade. Na Figura 22(a) observa-se que o número de grupos se mantém em
quatro por toda a execução do algoritmo. Na Figura 22(b)-(f) observa-se o mesmo padrão comportamental já apresentado para as bases anteriores, ou seja, o algoritmo estabiliza e, após isso, as dinâmicas são aplicadas, causando a variação nos resultados, a qual é seguida por um novo período de estabilização. A aplicação das dinâmicas ocorre na iteração de número 300. Nesta iteração percebe-se os maiores picos e vales para exclusão e inclusão de grupos, os quais se mantêm até a iteração 350, quando os grupos são novamente inseridos na base. Am- bos algoritmos atingem resultados similares, porém, de acordo com os valores apresentados na Tabela 7 e com os gráficos da Figura 22, é possível perceber que o dcBoids obteve resulta- dos ligeiramente superiores ao k-médias em relação às medidas de avaliação.
4.3.4 BASE WINE
A base Wine é formada por dados resultantes da análise química de vinhos produzidos em uma mesma região da Itália, porém derivados a partir de três cultivares diferentes. A análise determinou as quantidades de diversos componentes encontrados em cada tipo de vinho. Esta base de dados possui 178 objetos com 13 atributos e está dividida em três grupos.
4.3.4.1 Caso Estático
Na Tabela 8 são apresentados os resultados médios fornecidos pelos algoritmos para a base de dados Wine.
Tabela 8: Desempenho dos algoritmos dcBoids e k-médias quando aplicados a base de dados Wine. dcBoids k-médias k 3.2 0.42 (3, 4) 3.0 0 (3, 3) Índice de Dunn 0.79 0.02 (0.76, 0.82) 0.76 0 (0.76, 0.76) Acurácia (%) 94.8 1.13 (93, 96) 95.5 0 (95.5, 95.5) Pureza 0.96 0.01 (0.93, 0.97) 0.94 0 (0.94, 0.94) Entropia 0.12 0.01 (0.11, 0.14) 0.13 0 (0.13, 0.13) Índice de Jaccard 0.9 0.01 (0.88, 0.92) 0.89 0 (0.89, 0.89)
Os resultados dessa tabela mostram que os algoritmos possuem desempenho praticamente idêntico para a base de dados Wine. Em valores absolutos, as médias atingidas pelo dcBoids foram melhores, porém esta diferença não é estatisticamente significativa. A Figura 23 apre- senta uma configuração inicial e final típica do dcBoids aplicado à base Wine.
4.3.4.2 Caso Dinâmico
A Figura 24 apresenta o comportamento das medidas de avaliação do algoritmo dcBoids para a base Wine.
Figura 24: Dinâmica do algoritmo dcBoids para a base Wine ao longo das iterações.
Os resultados apresentados nas tabelas e gráficos para a base Wine mostram que o algoritmo foi capaz de identificar os grupos com alto percentual de acerto. A Figura 23 apresenta algu-
mas classificações incorretas, porém é possível ver claramente que três grandes grupos foram identificados.
Apesar de apresentar comportamentos que não são completamente estáveis, a Figura 24 apre- senta picos e vales que seguem o mesmo padrão comportamental das bases apresentadas até o momento. Na Figura 24(a) pode-se observar que o número de grupos chega muito próximo do valor três já a partir da iteração 250. Após a iteração 350, observa-se um vale, que indica que um grupo foi reinserido pelo algoritmo. Na Figura 24(b)-(f) pode-se constatar que o mesmo comportamento apresentado nas demais bases se repete, ou seja, os picos e vales representam a exclusão/inclusão de grupos e as perturbações menores ficam por conta da atualização dos objetos isolados. Além disso, é possível observar nestes gráficos que o nível de classificação correta chega bastante próximo ao que seria o ideal para esta base.
4.3.4.3 Resultados K-Médias
Figura 25: Dinâmica do algoritmo k-médias para a base Wine ao longo das iterações.
Os resultados para o algoritmo k-médias são bastante similares aos resultados obtidos pelo dcBoids. A estabilização do algoritmo é atingida rapidamente, até que na iteração de número 300 são aplicadas as dinâmicas de atualização da base. Na Figura 25(a) observa-se que o nú- mero de grupos se mantém em três durante toda a execução do algoritmo. Na Figura 25(b)-(f) tem-se comportamentos similares aos do dcBoids, com as perturbações mais evidentes ocor- rendo na exclusão e reinclusão de grupos na base de dados. Comparando aos gráficos e à tabe- las de resultados do dcBoids e do k-médias, verifica-se que ambos algoritmos apresentam pra- ticamente o mesmo desempenho, com diferenças muito pequenas nas medidas de avaliação.
4.3.5 BASE DIABETES
A base de dados Pima Indians Diabetes, ou simplesmente Diabete, tem como origem traba- lhos realizados no National Institute of Diabetes and Digestive and Kidney Diseases (Instituto Nacional de Diabetes e Doenças Digestivas e do Rim) dos Estados Unidos e foi consolidada no ano de 1990. A base possui um total de 768 objetos, cada um com oito atributos. A base possui dois clusters, um para os pacientes positivos para o diabetes e ou para os negativos. 4.3.5.1 Caso Estático
Na Tabela 9 são apresentados os resultados do agrupamento em ambiente estático para a base de dados Diabetes.
Tabela 9: Desempenho dos algoritmos dcBoids e k-médias quando aplicados a base de dados Diabetes. dcBoids k-médias k 2.1 0.31 (2, 3) 2 0 (2, 2) Índice de Dunn 0.69 0.2 (0.67, 0.72) 0.68 0 (0.68, 0.68) Acurácia (%) 80.8 1.84 (79, 84) 67 0 (67, 67) Pureza 0.77 0.01 (0.75, 0.79) 0.64 0 (0.64, 0.64) Entropia 0.29 0.01 (0.27, 0.31) 0.41 0 (0.41, 0.41) Índice de Jaccard 0.76 0.04 (0.67, 0.81) 0.59 0 (0.59, 0.59)
A Figura 26 apresenta uma configuração inicial e final, respectivamente, para a base Diabetes.
4.3.5.2 Caso Dinâmico
A Figura 27 apresenta o comportamento do dcBoids aplicado a base Diabetes.
Figura 27: Dinâmica do algoritmo dcBoids para a base Diabetes ao longo das iterações.
Os resultados para a base Diabetes mostram estabilização e bons resultados das medidas de avaliação. Esta foi a base de dados avaliada com a maior quantidade de objetos e, na maioria dos casos, o algoritmo convergiu para o número ideal de dois grupos. Para esta base de dados observou-se resultados do dcBoids superiores aos obtidos pelo k-médias. Para todas as medi- das de avaliação o dcBoids atingiu melhores valores, tanto para as médias quanto para os va-
lores mínimos e máximos. A inclusão/exclusão de grupos continua tendo o maior impacto nas medidas de avaliação, gerando perturbações que podem ser observadas nos picos e vales exis- tentes nos gráficos da Figura 27. Como visto na Figura 27(a), o algoritmo estabiliza no núme- ro ótimo de grupos já a partir da iteração 250, a qual se mantém até a iteração 350, na qual um grupo recém excluído é devolvido ao algoritmo. A Figura 27(b)-(f) apresenta perturbações dentro do padrão para as dinâmicas aplicadas.
4.3.5.3 Resultados K-Médias
Na Figura 28 estão apresentados os resultados do algoritmo k-médias para a base Diabetes, k = 2.
Figura 28: Dinâmica do algoritmo k-médias para a base Diabetes ao longo das iterações.
O algoritmo k-médias possui estabilização rápida para a base de dados Diabetes, porém atinge valores bem abaixo do ótimo para esta base de dados e um pouco abaixo dos valores obtidos pelo dcBoids. A aplicação das dinâmicas de atualização gera perturbações que seguem o mesmo padrão das outras bases já apresentadas. Na Figura 28(a) observa-se o que o número de grupos se mantém em dois durante toda a execução do algoritmo. A Figura 28(b)-(f) apre- senta estabilização até a iteração de número 300, quando é feita a aplicação das dinâmicas. Mais uma vez a exclusão/inclusão dos grupos gera as maiores perturbações, enquanto a atua- lização isolada causa pequeno impacto no desempenho do algoritmo.
4.3.6 BASE ECOLI
A base de dados Ecoli contem dados sobre a localização celular proteínas. Os 336 objetos que constituem esta base possuem um total de sete atributos. A base está separada em oito clusters diferentes.
4.3.6.1 Caso Estático
Na Tabela 10 são apresentados os resultados do agrupamento em ambiente estático para a base de dados Ecoli.
Tabela 10: Desempenho dos algoritmos dcBoids e k-médias quando aplicados a base de dados Ecoli. dcBoids k-médias k 5.2 0.63 (5, 7) 8 0 (8, 8) Índice de Dunn 0.78 0.02 (0.75, 0.82) 0.75 0 (0.75, 0.75) Acurácia (%) 66 1.7 (63, 68) 61 0 (61, 61) Pureza 0.86 0.01 (0.84, 0.87) 0.81 0 (0.81, 0.81) Entropia 0.26 0.03 (0.23, 0.32) 0.34 0 (0.34, 0.34) Índice de Jaccard 0.68 0.01 (0.66, 0.69) 0.59 0 (0.59, 0.59)
A Figura 29 apresenta uma configuração inicial e final típica para o dcBoids aplicado à base de dados Ecoli.
4.3.6.2 Caso Dinâmico
A Figura 30 apresenta o comportamento do dcBoids ao longo do tempo para a base Ecoli.
O algoritmo dcBoids consegue convergir para valores ligeiramente melhores que o algoritmo k-médias, porém, ambos ficam com uma acurácia em torno de 60%. Para esta base de dados, o dcBoids teve os piores resultados em relação ao número de grupos. Na maioria dos casos, foram identificados seis grupos ao invés de oito. Dos oito grupos desta base, existem três gru- pos consideravelmente pequenos (contendo 2, 2 e 5 objetos, respectivamente). Como estes grupos não são suficientemente diferenciados dos demais, eles acabam sendo absorvidos pe- los grupos maiores e o algoritmo estabiliza em cinco grupos ao invés de oito. O valor oito é sempre obtido para algoritmo k-médias, pois este é o valor inserido para o parâmetro k. Figura 30(a) observa-se que para o algoritmo dcBoids o valor dos grupos chega muito próximo ao ideal, que seria 8, partindo do valor inicial de 336. Porém, devido à grande discrepância de tamanho entre os grupos, os três menores grupos acabam sendo absorvidos pelos maiores. Como pode ser observado na Figura 30(b)-(f), a evolução das medidas continua seguindo o mesmo padrão de todas as bases apresentadas anteriormente. As dinâmicas aplicadas a objetos isolados causam um impacto bastante pequeno no agrupamento, enquanto a inclusão/exclusão continua gerando as maiores perturbações observadas.
4.3.6.3 Resultados K-Médias
Figura 31: Dinâmica do algoritmo k-médias para a base Ecoli ao longo das iterações.
O algoritmo k-médias tem uma rápida estabilização para a base de dados Ecoli, porém em valores bem abaixo do ótimo para esta base de dados. A base Ecoli foi a base com o maior número de grupos testada, mas estes grupos têm uma quantidade desbalanceada de objetos: enquanto o maior grupo possui 143 objetos, dois grupos possuem apenas dois objetos cada. Os resultados para o algoritmo k-médias seguem o mesmo padrão comportamental dos testes anteriores em relação à convergência. Na Figura 31(a) observa-se que o número de grupos se mantém em oito por toda a execução do algoritmo. Na Figura 31(b)-(f) observa-se o mesmo padrão já apresentado nas bases anteriores, ou seja, o algoritmo atinge um ponto de estabili- dade, após o qual as dinâmicas são aplicadas causando perturbação nos resultados seguida por um novo período de estabilização. A aplicação das dinâmicas ocorre na iteração de número 300. Nesta iteração percebe-se os picos e vales característicos que representam a exclusão e a inclusão de grupos, os quais se mantêm até a iteração 350, quando os grupos são novamente inseridos na base. Após a reinserção, a convergência volta a acontecer, até que se atinja uma nova estabilização. Apesar de ambos os algoritmos não terem atingido o ótimo, suas soluções foram bastante próximas.
5 CONCLUSÕES E TRABALHOS FUTUROS
A mineração de dados é uma linha de pesquisa bastante ampla, envolvendo tarefas como a- grupamento, classificação, estimação, associação e detecção de anomalias. Dentre essas, o agrupamento de dados vem recebendo grande atenção ao longo dos últimos anos devido ao grau de complexidade envolvido nesta tarefa e à sua ampla aplicabilidade prática. A maior parte dos algoritmos que vêm sendo investigados em agrupamento enfatiza a determinação correta dos agrupamentos da base de dados, considerando, normalmente, que se conhece a priori o número de grupos da base. Além disso, o foco de aplicação destes algoritmos tem sido em dados estáticos, ou seja, dados invariantes no tempo.
Dentre os novos algoritmos para agrupamento de dados, muitos são desenvolvidos com algu- ma inspiração em fenômenos naturais, como redes neurais, sistemas imunológicos e inteligên- cia de enxame. Estes algoritmos apresentam como vantagens, de maneira geral, um processa- mento paralelo e distribuído, robustez a pequenas perturbações e a realização de atualizações no processo de busca que seguem heurísticas independentes de informações mais sofisticadas sobre a função objetivo.
Essa dissertação propôs um algoritmo de agrupamento de dados variantes no tempo baseado na técnica de Vida Artificial denominada algoritmo de Boids e originalmente proposta para simular o comportamento de agentes, como pássaros e peixes, se movimentando em um espa- ço de dimensão 2D ou 3D. O algoritmo proposto aqui foi denominado de dcBoids (Dynamic Clustering Boids) e possui como características centrais a capacidade de resolver problemas de agrupamento de dados em ambientes variantes no tempo, a determinação automática do número de grupos existentes na base, a visualização das relações entre os objetos, e a quanti- zação vetorial da base. O dcBoids explora as propriedades inerentes ao algoritmo de Boids e modifica as regras de atualização dinâmica da posição dos Boids para que elas incorporem naturalmente a capacidade dos agentes em representar e agrupar os objetos da base.
O desempenho do dcBoids foi comparado ao clássico algoritmo das k-médias em seis bases de dados distintas da literatura, tanto em ambientes estáticos, quanto em ambientes dinâmicos. Neste segundo caso foram testadas dinâmicas envolvendo a inserção e remoção de grupos inteiros da base, a movimentação de objetos pelo espaço e a inserção e remoção de objetos da