COMBINATORIAL OPTIMIZATION HEURISTICS IN PARTITIONING WITH NON EUCLIDEAN DISTANCES

Resumen

ABSTRACT
We study some criteria that can be applied for the partitioning of a set of objects when non Euclidean distances are used; particularly, these criteria can be used when the data are described by binary variables. These criteria are based on aggregations that measure the homogeneity of a class and some are generalizations of variance or inertia. Properties of the criteria are studied and partitioning methods are proposed, based on metaheuristics of global optimization, such as simulated annealing and tabu search. Finally, comparative results on binary data are shown.

Key words: binary data, qualitative data, clustering, automatic classification, simulated annealing, tabu search, generalized inertia.

RESUMEN
Se estudian criterios que se pueden aplicar para particionar un conjunto de objetos cuando se usan distancias no euclídeas; en particular, los criterios pueden ser usados cuando los datos son descritos por variables binarias. estos criterios están basados en agregaciones que miden la homogeneidad de una clase y algunos son generalizaciones de la varianza o inercia. Se estudian algunas de las propiedades de los criterios de agregación y se proponen métodos de particionamiento basados en el uso de metaheurísticas de optimización global, como sobrecalentamiento simulado y búsqueda tabú. Finalmente, se muestran resultados comparativos sobre datos binarios.

Palabras clave: datos binarios, datos cualitativos, análisis de conglomerados, clasificación automática, búsqueda tabú, sobrecalentamiento simulado, inercia generalizada