Agosto 2014 vol. 1 num. 1 - XVII Simpósio de Pesquisa Operacional e Logística da Marinha

Artigo - Open Access.

Idioma principal

RESOLUÇÃO DO PROBLEMA DOS K-MEDOIDS VIA ALGORITMO GENÉTICO DE CHAVES ALEATÓRIAS VICIADAS

Brito, José André de Moura ; Semaan, Gustavo da Silva ; Brito, Luciana Roque ;

Artigo:

O presente trabalho propõe um novo algoritmo de otimização para a resolução do problema dos k-medoids. Um problema de agrupamento, onde dado um conjunto de n objetos com f atributos, e fixado o número de grupos, deve-se selecionar, dentre os n objetos, k objetos denominados medoids. Os demais objetos são alocados ao medoid correspondente mais próximo, segundo uma medida distância. Especificamente, o conjunto dos k medoids é definido de forma que a soma das distâncias dos demais objetos ao seu respectivo medoid seja a menor possível. De forma a resolver este problema, propõe-se no presente trabalho um algoritmo que utiliza os conceitos da metaheurística algoritmo genético de chaves aleatórias viciadas (biased random-key genetic algorithm - BRKGA) e um procedimento de reconexão por caminhos. A última seção traz alguns resultados computacionais para um conjunto de instâncias da literatura, reais e geradas artificialmente, considerando a aplicação do algoritmo proposto, de quatro algoritmos da literatura e de uma formulação exata.

Artigo:

This paper proposes a new Optimization Algorithm for the k-medoid Clustering Problem. In this problem, given a dataset X with n objects and f attributes and a fixed number of clusters (k), it is necessary to select k objects called medoids. Each medoid creates a new cluster and the remaining (n–k) objects should be placed into nearest of these clusters, according a distance measure. The goal is minimize the sum of distances between each object and the medoid of its group. This work presents a new algorithm that considers concepts of Biased Random-key Genetic Algorithm. Besides, an approach of path-relinking procedure is related. The computational experiments results are presented in the last section. It was used thirty instances, among well-known datasets of the literature and new datasets artificially constructed. The proposed heuristics are compared with five approaches (four algorithms and one exact method) and the presented algorithms are a alternative and effective way to solve the problem.

Download (PDF)

Palavras-chave: Algoritmos Genéticos, Chaves Aleatórias, Medoids, Análise de Agrupamentos, Processamento Paralelo, Genetic Algorithms,

Palavras-chave:

DOI: 10.5151/marine-spolm2014-125771

Referências bibliográficas
  • [1] Bean, J.C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA J. on Computing, 6, 154-160.
  • [2] Brito, J.A.M., Ochi L.S., Brito L.R. e Montenegro, F.M.T (2010). Um algoritmo para o agrupamento baseado em K-Medoids. Revista Brasileira de Estatística, 71, p. 75-99.
  • [3] Brito, J.A.M. e Semaan, G.S. (2013). Um Algoritmo Grasp Aplicado ao Problema dos k-Medoids. XLV Simpósio Brasileiro de Pesquisa Operacional, Natal. Anais do XLV Simpósio Brasileiro de Pesquisa Operacional.
  • [4] Chu, S.C., Roddick J.F and Pan J.S. (2008). Improved Search Strategies and Extensions to k-medoidsbased Clustering Algorithms. International Journal of Business Intelligence and Data Mining, 3, 2, 212-231.
  • [5] Church, R. (1978). Contrasts Between Facility Location Approaches and NonHierarquical Cluster Analysis. Paper presented at ORSA/TIMS Joint National Meeting, Los Langeles, California, nov. 1978.
  • [6] Cruz, M. D. (2010). O problema de clusterização automática, Tese de Doutorado, COPPE/UFRJ.
  • [7] Feo, T.A. e Resende, M.G.C. (1995). Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, pp. 109-133, 1995.
  • [8] Glover, F. e Kochenberger, G. A. (2002). “Handbook of Metaheuristic”, First Edition Norwell: K1uwer Academic Publishers, 2002.
  • [9] Gonçalves, J.R. e Resende, M.G.C. (2011). Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics, 17, 487-525.
  • [10] Han, J. and Ng, R. (2002). “CLARANS:A Method for Clustering Objects for Spatial DataMining. IEEE Transactions Knowledge of Data Enginnering 14(5), pp. 1003-1016.
  • [11] Hair, J.F, Black, W.C, Babin, B.J., Anderson, R.E. e Tatham, R.L. (2009). Análise Multivariada de Dados, Bookman, Sexta Edição.
  • [12] Johnson A.R. e Wichern D.W. (2002). Applied Multivariate Statistical Analysis. Prentice Hall. Fifth Edition.
  • [13] Kaufman L. e Rousseeuw P.J. (1989). Finding Groups in Data – An Introduction to Cluster Analysis. Wiley-Interscience Publication.
  • [14] Mingoti, S.A. (2007). Análise de Dados Através de Métodos de Estatística Multivariada – Uma Abordagem Aplicada, UFMG, 1ª Edição.
  • [15] Mulvey, J. and Cowder, H. (1979). Cluster Analysis: An Application of Lagrangian Relaxation. Management Science, 25, 329-340.
  • [16] Naldi, C. N. (2011). Técnicas de Combinação para Agrupamento Centralizado e Distribuído de Dados. Tese de Doutorado, USP - São Carlos.
  • [17] Park H.S. and Jun C.H. (2009). A Simple and Fast Algorithm for K-medoids Clustering. Expert Systems with Applications, 36, 2, 3336-3341.
  • [18] Rao, M.R. (1971). Cluster Analysis and Mathematical Programming. Journal of American Statistical Association, 66, 622-626.
  • [19] Semaan, G.S. (2013). Algoritmos para o Problema de Agrupamento Automático. Tese de Doutorado, UFF/IC.
  • [20] Sheng W. and Liu X. (2004). A Hybrid Algorithm for K-medoid Clustering of Large Data Sets. Congress on Evolutionary Computation, 1, 77-82.
  • [21] Spears, W.M e DeJong, K.A. (1991). On the virtues of parameterized uniform crossover. Em Proceedings of the Fourth International Conference on Genetic Algorithms, 230-236.
  • [22] Tryon, R. (1939). Cluster Analysis. Oxford, England: Edward Bros.
  • [23] Vinod, H. (1969). Integer Programming and Theory of Grouping. Journal of American Statistical Association, 64, 506-517.
  • [24] Zhang, Q. and Couloigner, I. (2005). A New Efficient k-medoid Algorithm for Spatial Clustering. Lecture Notes in Computer Science, v3482, 181-189.
Como citar:

Brito, José André de Moura; Semaan, Gustavo da Silva; Brito, Luciana Roque; "RESOLUÇÃO DO PROBLEMA DOS K-MEDOIDS VIA ALGORITMO GENÉTICO DE CHAVES ALEATÓRIAS VICIADAS", p. 50-61 . In: Anais do XVII Simpósio de Pesquisa Operacional e Logística da Marinha - SPOLM 2014. São Paulo: Blucher, 2014.
ISSN 2175-6295, ISBN: 2175-6295
DOI 10.5151/marine-spolm2014-125771

últimos 30 dias | último ano | desde a publicação


downloads


visualizações


indexações