論文の概要: Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling
- arxiv url: http://arxiv.org/abs/2504.20982v1
- Date: Tue, 29 Apr 2025 17:51:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-02 19:15:55.02699
- Title: Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling
- Title（参考訳）: 均一サンプリングによるk平均クラスタリングのための確率的に高速なランダム化および量子アルゴリズム
- Authors: Tyler Chen, Archan Ray, Akshay Seshadri, Dylan Herman, Bao Bach, Pranav Deshpande, Abhishek Som, Niraj Kumar, Marco Pistoia,
- Abstract要約: 本稿では、単純なランダム化されたミニバッチの$k$-meansアルゴリズムと、古典的アルゴリズムにインスパイアされた量子アルゴリズムについて述べる。
我々の改善は、$k$-means問題の特定の対称性を保存する一様サンプリングの注意深い使用による。
- 参考スコア（独自算出の注目度）: 3.0522144048108513
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $k$-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the $k$-means algorithm is that each iteration requires time linear in the number of data points, which can be expensive in big data applications. This was improved in recent works proposing quantum and quantum-inspired classical algorithms to approximate the $k$-means algorithm locally, in time depending only logarithmically on the number of data points (along with data dependent parameters) [$q$-means: A quantum algorithm for unsupervised machine learning; Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; Do you know what $q$-means?, Doriguello, Luongo, Tang]. In this work, we describe a simple randomized mini-batch $k$-means algorithm and a quantum algorithm inspired by the classical algorithm. We prove worse-case guarantees that significantly improve upon the bounds for previous algorithms. Our improvements are due to a careful use of uniform sampling, which preserves certain symmetries of the $k$-means problem that are not preserved in previous algorithms that use data norm-based sampling.
- Abstract（参考訳）: k$-meansアルゴリズム(Lloydのアルゴリズム)は、ラベルのないデータをクラスタリングするために広く使われている手法である。
k$-meansアルゴリズムの重要なボトルネックは、各イテレーションがデータポイントの数を線形にする必要があることだ。
量子と量子にインスパイアされた古典的アルゴリズムを局所的に近似するために、局所的に$k$-meansアルゴリズムを提案する最近の研究において、(データ依存パラメータとともに)データポイントの数に対数的にのみ依存するように改良された[$q$-means: 教師なし機械学習のための量子アルゴリズム; Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; q$-means, Doriguello, Luongo, Tang]。
本稿では,従来のアルゴリズムにインスパイアされた量子アルゴリズムと,単純なランダム化されたミニバッチの$k$-meansアルゴリズムについて述べる。
我々は,従来のアルゴリズムのバウンダリを大幅に改善するケース保証を証明した。
我々の改善は、データ標準サンプリングを使用する以前のアルゴリズムでは保存されていない$k$-means問題の特定の対称性を保存する一様サンプリングの注意深い使用による。
関連論文リスト
- Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation [0.0]
この論文は、1D$k$-meansクラスタリングの理論と実践を橋渡しし、効率的で健全なアルゴリズムを提供する。
ベンチマークでは、大規模なデータセットのScikit-learnと比較して、4500倍のスピードアップが示されている。
論文 参考訳（メタデータ） (2024-12-19T09:03:39Z) - Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳（メタデータ） (2024-07-15T20:04:06Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [45.810803542748495]
Kerenidis, Landman, Luongo, Prakash (NeurIPS')によって提案された量子アルゴリズムの改良版を提案する。
我々のアルゴリズムは、先行研究の量子線型代数プリミティブに頼るのではなく、QRAMを用いて単純な状態を作成する。
また、$varepsilon$-$k$-meansに対して、$Obigで実行される"dequantized"アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Are Easy Data Easy (for K-Means) [0.0]
本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。
シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
論文 参考訳（メタデータ） (2023-08-02T09:40:19Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Global $k$-means$++$: an effective relaxation of the global $k$-means
clustering algorithm [0.20305676256390928]
k$-meansアルゴリズムは、その単純さ、有効性、スピードから、一般的なクラスタリング手法である。
本稿では,高品質クラスタリングソリューションを効果的に取得する手段として,emphglobal $k$-meanstexttt++クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-22T13:42:53Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。