Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes at least $\Omega(k^2)$. We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Scalable Kernel Clustering: Approximate Kernel k-means
Kernel-based clustering algorithms have the ability to capture the non-linear structure in real world data. Among various kernel-based clustering algorithms, kernel k-means has gained popularity due to its simple iterati…
ClusteringA Distributed and Approximated Nearest Neighbors Algorithm for an Efficient Large Scale Mean Shift Clustering
In this paper we target the class of modal clustering methods where clusters are defined in terms of the local modes of the probability density function which generates the data. The most well-known modal clustering meth…
ClusteringDeep-seeded Clustering for Emotion Recognition from Wearable Physiological Sensors
According to the circumplex model of affect, an emotional response could characterized by a level of pleasure (valence) and intensity (arousal). As it reflects on the autonomic nervous system (ANS) activity, modern weara…
ClusteringDecision MakingEmotion Recognitionfeature selectionScalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
Kernel $k$-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear $k$-means clustering algorithm. However, kernel $k$-means clustering is computationally ex…
ClusteringScalable Initialization Methods for Large-Scale Clustering
In this work, two new initialization methods for K-means clustering are proposed. Both proposals are based on applying a divide-and-conquer approach for the K-means|| type of an initialization strategy. The second propos…
Clustering