Heuristics for minimizing the maximum within-clusters distance

Heuristics for minimizing the maximum within-clusters distance

Autor Fioruci, José Augusto Google Scholar
Toledo, Franklina M.b. Google Scholar
Nascimento, Mariá Cristina Vasconcelos Autor UNIFESP Google Scholar
Instituição Universidade de São Paulo (USP)
Universidade Federal de São Paulo (UNIFESP)
Resumo The clustering problem consists in finding patterns in a data set in order to divide it into clusters with high within-cluster similarity. This paper presents the study of a problem, here called MMD problem, which aims at finding a clustering with a predefined number of clusters that minimizes the largest within-cluster distance (diameter) among all clusters. There are two main objectives in this paper: to propose heuristics for the MMD and to evaluate the suitability of the best proposed heuristic results according to the real classification of some data sets. Regarding the first objective, the results obtained in the experiments indicate a good performance of the best proposed heuristic that outperformed the Complete Linkage algorithm (the most used method from the literature for this problem). Nevertheless, regarding the suitability of the results according to the real classification of the data sets, the proposed heuristic achieved better quality results than C-Means algorithm, but worse than Complete Linkage.
Palavra-chave clustering
heuristics
GRASP
minimization of the maximum diameter
Idioma Inglês
Data de publicação 2012-12-01
Publicado em Pesquisa Operacional. Sociedade Brasileira de Pesquisa Operacional, v. 32, n. 3, p. 497-522, 2012.
ISSN 0101-7438 (Sherpa/Romeo)
Publicador Sociedade Brasileira de Pesquisa Operacional
Extensão 497-522
Fonte http://dx.doi.org/10.1590/S0101-74382012005000023
Direito de acesso Acesso aberto Open Access
Tipo Artigo
SciELO S0101-74382012000300002 (estatísticas na SciELO)
Endereço permanente http://repositorio.unifesp.br/handle/11600/7427

Exibir registro completo




Arquivo

Nome: S0101-74382012000300002.pdf
Tamanho: 736.7KB
Formato: PDF
Descrição:
Abrir arquivo

Este item está nas seguintes coleções

Buscar


Navegar

Minha conta