Qualitative properties of the minimum sum-of-squares clustering problem. (1st September 2020)

• Record Type: Journal Article
• Authors: Cuong, Tran Hung; Yao, Jen-Chih; Yen, Nguyen Dong
• Is Part Of: Optimization. Volume 69:Number 9(2020)
• Page Start: 2131
• Page End: 2154
• Publication Date: 2020-09-01
• Subjects: Clustering problem -- local and global solutions -- attraction sets -- solution existence -- stability properties; 68T10 -- 68Q25 -- 68W40 -- 90C26 -- 90C90; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1778685
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : Fundamental qualitative properties of the minimum sum-of-squares clustering problem are established in this paper. We prove that the problem always has a global solution and, under a mild condition, the global solution set is finite. Moreover, the components of each global solution can be computed by an explicit formula. Based on a new concept of non-trivial local solution, we get necessary conditions for a system of centroids to be such a local solution. Interestingly, these necessary conditions are also sufficient ones. Finally, it is proved that the optimal value function is locally Lipschitz, the global solution map is locally upper Lipschitz, and the local solution map has the Aubin property, provided that the original data points are distinct. The obtained complete characterizations of the non-trivial local solutions allow one to understand better the performance of not only the k -means algorithm, but also of other solution methods for the problem in question.