Um Algoritmo de Construção e Busca Local para o Problema de Clusterização de Bases de Dados

Autores

  • S.S. Rosário
  • L.S. Ochi
  • L.M.A. Drummond

DOI:

https://doi.org/10.5540/tema.2006.07.01.0109

Resumo

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

2006-06-01

Como Citar

Rosário, S., Ochi, L., & Drummond, L. (2006). Um Algoritmo de Construção e Busca Local para o Problema de Clusterização de Bases de Dados. Trends in Computational and Applied Mathematics, 7(1), 109–118. https://doi.org/10.5540/tema.2006.07.01.0109

Edição

v. 7 n. 1 (2006)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.