New heuristics for minimum sum-of-squares clustering
Heuristic, VNS, MSSC, Clustering.
Due to the large volume of data generated by the growth of applications that provide
new information, both in volume and variety, more efficient techniques are required to
classify and processes them. A widely used technique is data grouping whose aim is to
extract characteristics of the entities dividing them into homogeneous and/or well separated subsets. Many different criteria can be used to express the data classification. Among them, a commonly used criteria is the minimun sum-of-squares clustering (MSSC). In this criterion, entities are elements in n-dimensional Euclidean space. The data clustering
problem by MSSC is NP-hard, then heuristics are extremely useful techniques for this
type of problem. This work proposes new heuristics, based on the general variable neighborhood search (GVNS). Also proposed in this work is the adaptation of the heuristic reformulation descent (RD) to the MSSC problem, in the form of two variants, unapplied to this problem before in literature. The computational experiments show that the GVNS
variants proposed in this work present better results, in large instances, than the current state of the art for this problem.