Um Algoritmo de Construção e Busca Local para o Problema de Clusterização de Bases de Dados
DOI:
https://doi.org/10.5540/tema.2006.07.01.0109Resumo
O Problema de Clusterização de uma base de dados, embora já tenha sido bastante explorado por pesquisadores de áreas como matemática, estatística e computação, traz na maioria dos trabalhos apresentados, uma abordagem do caso em que o número de clusters é previamente fixado pelo usuário como um parâmetro de entrada. Entretanto, em muitas aplicações práticas o número de clusters é uma variável que deve ser determinada pelo algoritmo. Esta generalização é denotada por Problema de Clusterização Automática (PCA). Neste trabalho, apresentamos um algoritmo de construção e busca local através de sobreposição e inversão de janelas para o PCA e demonstramos sua eficiência comparado-o com um Algoritmo Genético que até então apresentava os melhores resultados para este tipo de problema.Referências
[1] B. Sanghamitra, M. Ujjwal, An evolutionary technique based on K-Means algorithm for optimal clustering, Information Sciences, 146 (2002), 221-237.
C.R. Dias e L.S. Ochi, Efficient evolutionary algorithms for the clustering problem in directed graphs, in Proc. of the IEEE Congress on Evolutionary Computation (IEEE-CEC), 2003 983-988.
F. Glover, Tabu Search - Part I, ORSA Journal on Computer, 1, No. 3 (1989), 190-206.
F. Hichem e K. Raghu, A robust algorithm for automatic extraction of an unknown number of clusters from noisy data, Pattern Recogniton Letters, 17, (1996) ,1223-1232.
G. Karypis, E. Han e V. Kumar, CHAMELEON: A hierarchical clustering algorithm using dynamic modeling, Computer, 32 (1998), 68-75.
J.H. Holland, “Adaptation in Nature and Artificial Systems”, University of Michigam Press - MI, 1975.
L.S. Ochi, M.J.F. Souza e N. Maculan, A GRASP - TABU SEARCH algorithm to solve a School Timetabling Problem, Combinatorial Optimization Book Se ries, Metaheuristics: Computer Decision - Making, (D.Z. Du and P.M. Pardalos, eds.), vol. 15, chapter 31, pp. 659-672, Kluwer, 2003.
T.A. Feo e M.G.C. Resende, Greedy Randomized Adaptative Search Procedures, Journal of Global Optmization, 6 (1995), 109-133.
Y.T. Lin e Y.B. Shiueng, A genetic approach to the automatic clustering problem, Pattern Recognition, 34 (2001), 415-424.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.