On the Global Solution of Soft k-Means
This paper presents an algorithm to solve the Soft k-Means problem globally. Unlike Fuzzy c-Means, Soft k-Means (SkM) has a matrix factorization-type objective and has been shown to have a close relation with the popular probability decomposition-type clustering methods, e.g., Left Stochastic Clustering (LSC). Though some work has been done for solving the Soft k-Means problem, they usually use an alternating minimization scheme or the projected gradient descent method, which cannot guarantee global optimality since the non-convexity of SkM. In this paper, we present a sufficient condition for a feasible solution of Soft k-Means problem to be globally optimal and show the output of the proposed algorithm satisfies it. Moreover, for the Soft k-Means problem, we provide interesting discussions on stability, solutions non-uniqueness, and connection with LSC. Then, a new model, named Minimal Volume Soft k-Means (MVSkM), is proposed to address the solutions non-uniqueness issue. Finally, experimental results support our theoretical results.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
R 1 -PCA: Rotational Invariant L 1 -norm Principal Component Analysis for Robust Subspace Factorization
Principal component analysis (PCA) mini- mizes the sum of squared errors (L 2 -norm) and is sensitive to the presence of outliers. We propose a rotational invariant L 1 -norm PCA (R 1 -PCA). R 1 -PCA is similar to PC…
ClusteringData Clustering using a Hybrid of Fuzzy C-Means and Quantum-behaved Particle Swarm Optimization
Fuzzy clustering has become a widely used data mining technique and plays an important role in grouping, traversing and selectively using data for user specified applications. The deterministic Fuzzy C-Means (FCM) algori…
ClusteringQuantizationGlobal $k$-means$++$: an effective relaxation of the global $k$-means clustering algorithm
The $k$-means algorithm is a prevalent clustering method due to its simplicity, effectiveness, and speed. However, its main disadvantage is its high sensitivity to the initial positions of the cluster centers. The global…
ClusteringA cutting plane algorithm for globally solving low dimensional k-means clustering problems
Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common such methods. There is a variety of approximate algorithms for the k-means problem, b…
Clusteringglobal-optimizationData-Native Global Optimization for Big Data K-means Clustering
Big data clustering remains challenging: the Minimum Sum-of-Squares Clustering (MSSC) problem underlying K-means is NP-hard, and existing methods either reach poor local minima or require prohibitive metaheuristic hybrid…