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

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

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.




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

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia