Local $K$-means: An Efficient Optimization Algorithm And Its Generalization
Until now, $k$-means is still one of the most popular clustering algorithms because of its simplicity and efficiency, although it has been proposed for a long time. In this paper, we considered a variant of $k$-means that takes the $k$-nearest neighbor ($k$-NN) graph as input and proposed a novel clustering algorithm called Local K-Means (LKM). We also developed a general model that unified LKM, KSUMS, and SC, and discussed the connection among them. In addition, we proposed an efficient optimization algorithm for the unified model. Thus, not only LKM but also SC can be optimized with a linear time complexity with respect to the number of samples. Specifically, the computational overhead is $O(nk)$, where $n$ and $k$ are denote the number of samples and nearest neighbors, respectively. Extensive experiments have been conducted on 11 synthetic and 16 benchmark datasets from the literature. The effectiveness, efficiency, and robustness to outliers of the proposed method have been verified by the experimental results.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
The k-means-u* algorithm: non-local jumps and greedy retries improve k-means++ clustering
We present a new clustering algorithm called k-means-u* which in many cases is able to significantly improve the clusterings found by k-means++, the current de-facto standard for clustering in Euclidean spaces. First we …
ClusteringHybrid data clustering approach using K-Means and Flower Pollination Algorithm
Data clustering is a technique for clustering set of objects into known number of groups. Several approaches are widely applied to data clustering so that objects within the clusters are similar and objects in different …
Clusteringglobal-optimizationLocally Adaptive Federated Learning
Federated learning is a paradigm of distributed machine learning in which multiple clients coordinate with a central server to learn a model, without sharing their own training data. Standard federated optimization metho…
Federated LearningEfficient Hill-Climber for Multi-Objective Pseudo-Boolean Optimization
Local search algorithms and iterated local search algorithms are a basic technique. Local search can be a stand along search methods, but it can also be hybridized with evolutionary algorithms. Recently, it has been show…
Evolutionary AlgorithmsLocal Network Community Detection with Continuous Optimization of Conductance and Weighted Kernel K-Means
Local network community detection is the task of finding a single community of nodes concentrated around few given seed nodes in a localized way. Conductance is a popular objective function used in many algorithms for lo…
Community DetectionLocal Community Detection