Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers

• URL: http://arxiv.org/abs/2302.14599v1
• Date: Tue, 28 Feb 2023 14:39:18 GMT
• Title: Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers
• Authors: Yijia Zhou, Kyle A. Gallivan, Adrian Barbu
• Abstract summary: This paper introduces a provably robust clustering algorithm based on loss minimization. It provides theoretical guarantees that the algorithm obtains high accuracy with high probability. Experiments on real-world large-scale datasets demonstrate the effectiveness of the algorithm.
• Score: 5.478764356647437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is a widely used technique with a long and rich history in a variety of areas. However, most existing algorithms do not scale well to large datasets, or are missing theoretical guarantees of convergence. This paper introduces a provably robust clustering algorithm based on loss minimization that performs well on Gaussian mixture models with outliers. It provides theoretical guarantees that the algorithm obtains high accuracy with high probability under certain assumptions. Moreover, it can also be used as an initialization strategy for $k$-means clustering. Experiments on real-world large-scale datasets demonstrate the effectiveness of the algorithm when clustering a large number of clusters, and a $k$-means algorithm initialized by the algorithm outperforms many of the classic clustering methods in both speed and accuracy, while scaling well to large datasets such as ImageNet.

Related papers

• GBCT: An Efficient and Adaptive Granular-Ball Clustering Algorithm for Complex Data [49.56145012222276]
  We propose a new clustering algorithm called granular-ball clustering (GBCT) via granular-ball computing. GBCT forms clusters according to the relationship between granular-balls, instead of the traditional point relationship. As granular-balls can fit various complex data, GBCT performs much better in non-spherical data sets than other traditional clustering methods.
  arXiv  Detail & Related papers  (2024-10-17T07:32:05Z)
• From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection [12.993073967843292]
  We study a problem in a semi-supervised setting, with an unknown ground-truth clustering. We introduce a notion of size generalization for clustering algorithm accuracy. We use a subsample of as little as 5% of the data to identify which algorithm is best on the full dataset.
  arXiv  Detail & Related papers  (2024-02-22T06:53:35Z)
• A provable initialization and robust clustering method for general mixture models [6.806940901668607]
  Clustering is a fundamental tool in statistical machine learning in the presence of heterogeneous data. Most recent results focus on optimal mislabeling guarantees when data are distributed around centroids with sub-Gaussian errors.
  arXiv  Detail & Related papers  (2024-01-10T22:56:44Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  Subset selection is a fundamental problem that can play a key role in identifying smaller portions of the training data. We develop a novel factor 3-approximation algorithm to compute subsets based on the weighted sum of both k-center and uncertainty sampling objective functions.
  arXiv  Detail & Related papers  (2023-12-17T04:41:07Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Research on Efficient Fuzzy Clustering Method Based on Local Fuzzy Granular balls [67.33923111887933]
  In this paper, the data is fuzzy iterated using granular-balls, and the membership degree of data only considers the two granular-balls where it is located. The formed fuzzy granular-balls set can use more processing methods in the face of different data scenarios.
  arXiv  Detail & Related papers  (2023-03-07T01:52:55Z)
• How to Use K-means for Big Data Clustering? [2.1165011830664677]
  K-means is the simplest and most widely used algorithm under the Euclidean Minimum Sum-of-Squares Clustering (MSSC) model. We propose a new parallel scheme of using K-means and K-means++ algorithms for big data clustering.
  arXiv  Detail & Related papers  (2022-04-14T08:18:01Z)
• Divide-and-conquer based Large-Scale Spectral Clustering [8.545202841051582]
  We propose a divide-and-conquer based large-scale spectral clustering method to strike a good balance between efficiency and effectiveness. The proposed method achieves lower computational complexity than most existing large-scale spectral clustering.
  arXiv  Detail & Related papers  (2021-04-30T15:09:45Z)
• Clustering of Big Data with Mixed Features [3.3504365823045044]
  We develop a new clustering algorithm for large data of mixed type. The algorithm is capable of detecting outliers and clusters of relatively lower density values. We present experimental results to verify that our algorithm works well in practice.
  arXiv  Detail & Related papers  (2020-11-11T19:54:38Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.