| Journal: | Revista brasileira de estatistica |
| Database: | CLASE |
| System number: | 000350216 |
| ISSN: | 0034-7175 |
| Authors: | Brito, Jose Andre de Moura1 Ochi, Luiz Satoru Brito, Luciana Roque Montenegro, Flavio Marcelo Tavares |
| Institutions: | 1Escola Nacional de Ciencias Estatisticas, Rio de Janeiro. Brasil |
| Year: | 2010 |
| Season: | Ene-Dic |
| Volumen: | 71 |
| Number: | 234 |
| Pages: | 75-100 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Analítico, teórico |
| English abstract | We describe a new algorithm to solve a classical clustering problem known as k-medoids problem. This problem is analogous to the k-means problem, which is commonly related to stratification in sample surveys. However, the centroids are now replaced by medoids, aiming to obtain more robust and homogeneous clusters. Given n objects with p attributes and a fixed number k of desired clusters, we must select k objects (medoids), in such a way to minimize the sum of distances from each one of the remaining (n-k) objects to its respective nearest medoid. Constraining the maximum number of objects per cluster, we obtain the capacitated k-medoids problem. The algorithm proposed in this paper is based on the ILS (Iterated Local Search) method. Computational results using IBGE demographic census reveal a reasonable performance of the algorithm in terms of computational time consumption and quality of the solutions |
| Portuguese abstract | Descreve-se um novo algoritmo para um problema clássico de agrupamento, conhecido como problema dos k-medoids. Esse problema é análogo ao problema das k-médias, cuja resolução encontra aplicação frequente na fase de estratificação em amostragem probabilística. Entretanto, substituem-se os centroides por medoids, objetivando-se obter agrupamentos mais homogêneos e robustos. Dados n objetos com p atributos e fixado um número k de agrupamentos, deve-se selecionar k objetos (medoids) de forma a minimizar a soma das distâncias de cada um dos (n-k) objetos restantes ao seu medoid mais próximo. Ao se limitar o número máximo de objetos por grupo, obtemos o chamado problema dos k-medoids capacitado. O algoritmo proposto neste trabalho é baseado no método ILS (Iterated Local Search). A partir de dados do censo demográfico do IBGE, resultados computacionais mostram um desempenho razoável do algoritmo em termos de tempo computacional e de qualidade das soluções obtidas |
| Disciplines: | Matemáticas, Ciencias de la computación |
| Keyword: | Matemáticas puras, Teoría de la computación, Algoritmos, Clusters, K-medoides |
| Full text: | Texto completo (Ver PDF) |
