| Revista: | Revista brasileira de estatistica |
| Base de datos: | CLASE |
| Número de sistema: | 000350216 |
| ISSN: | 0034-7175 |
| Autores: | Brito, Jose Andre de Moura1 Ochi, Luiz Satoru Brito, Luciana Roque Montenegro, Flavio Marcelo Tavares |
| Instituciones: | 1Escola Nacional de Ciencias Estatisticas, Rio de Janeiro. Brasil |
| Año: | 2010 |
| Periodo: | Ene-Dic |
| Volumen: | 71 |
| Número: | 234 |
| Paginación: | 75-100 |
| País: | Brasil |
| Idioma: | Portugués |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, teórico |
| Resumen en inglés | 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 |
| Resumen en portugués | 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 |
| Disciplinas: | Matemáticas, Ciencias de la computación |
| Palabras clave: | Matemáticas puras, Teoría de la computación, Algoritmos, Clusters, K-medoides |
| Texto completo: | Texto completo (Ver PDF) |
