Dynamic local search for clustering with unknown number of clusters
Ismo Kärkkäinen, Pasi Fränti · 2003
Dynamic clustering problems can be solved by finding several clustering solutions with different number of clusters, and by choosing the one that minimizes a given evaluation function. This kind of brute force approach is general, but not very efficient. We propose a new dynamic local search that solves the number and location of the clusters jointly. The algorithm uses a set of basic operations, such as cluster addition, removal and swapping. The clustering is found by the combination of a trial-and-error approach of local search, and the local optimization capability of the generalized Lloyd algorithm. The algorithm finds the results 30 times faster than the brute force approach.