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

Authors

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

DOI:

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

Abstract

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.

References

[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

Published

2006-06-01

How to Cite

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

Issue

Vol. 7 No. 1 (2006)

Section

Original Article

License

Copyright

Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.

Intellectual Property and Terms of Use

The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.

The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.