Large Scale Clustering by Variable Neighborhood Search

Pierre Hansen and Nenad Mladenovic (GERAD and Ecole des Hautes Etudes Commerciales,Montreal)

Traditional clustering algorithms such as KMEANS or HMEANS give poor
results when applied to large data sets with many clusters. A new
metaheuristic, Variable Neighboorhood Search, is applied to large
scale clustering with various criteria: minimum sum of squares,
minimum sum of stars (the p-median problem) and minimum sum of
continuous stars (the multisource Weber problem).  Computational
results on problems with up to several thousand entities is reported