論文の概要: Fast and Accurate $k$-means++ via Rejection Sampling

• arxiv url: http://arxiv.org/abs/2012.11891v1
• Date: Tue, 22 Dec 2020 09:14:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-26 07:19:23.680785
• Title: Fast and Accurate $k$-means++ via Rejection Sampling
• Title（参考訳）: Rejection Smplingによる$k$-means++の高速化
• Authors: Vincent Cohen-Addad and Silvio Lattanzi and Ashkan Norouzi-Fard and Christian Sohler and Ola Svensson
• Abstract要約: k$-means++は時々大きなデータセットの処理が遅くなる。 我々は$k$-means++シードのためのニア線形時間アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 44.155614837392214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: $k$-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide adoption, $k$-means++ sometimes suffers from being slow on large data-sets so a natural question has been to obtain more efficient algorithms with similar guarantees. In this paper, we present a near linear time algorithm for $k$-means++ seeding. Interestingly our algorithm obtains the same theoretical guarantees as $k$-means++ and significantly improves earlier results on fast $k$-means++ seeding. Moreover, we show empirically that our algorithm is significantly faster than $k$-means++ and obtains solutions of equivalent quality.
• Abstract（参考訳）: $k$-means++ \cite{arthur2007k} は実装が容易で、優れた理論的保証と強力な経験的性能を持つクラスタリングアルゴリズムである。 広く採用されているにもかかわらず、$k$-means++は大規模なデータセットの処理が遅くなることがあるため、同様の保証でより効率的なアルゴリズムを得ることが自然な問題であった。 本稿では,$k$-means++ シードのための近似線形時間アルゴリズムを提案する。 興味深いことに、我々のアルゴリズムは$k$-means++と同じ理論的保証を取得し、高速な$k$-means++のシード結果を大幅に改善する。 さらに,本アルゴリズムは$k$-means++よりもはるかに高速であり,等価品質の解が得られることを示す。

関連論文リスト

• 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)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• 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)
• Multi-Swap $k$-Means++ [30.967186562175893]
  Arthur and Vassilvitskii (SODA 2007)の$k$-means++アルゴリズムは、人気のある$k$-meansクラスタリングの目的を最適化するための実践者の選択アルゴリズムであることが多い。 Lattanzi氏とSohler氏(ICML)は、$k$-means++を$O(k log log k)$で拡張して、$k$-meansクラスタリング問題に$c$-approximationをもたらすよう提案した。
  論文  参考訳（メタデータ） (2023-09-28T12:31:35Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• 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)
• A Faster $k$-means++ Algorithm [11.428775569173638]
  ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。 我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
  論文  参考訳（メタデータ） (2022-11-28T08:17:12Z)
• 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)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Improved Guarantees for k-means++ and k-means++ Parallel [18.26254785549146]
  k-means++とk-means++並列は、古典的なk-meansクラスタリング問題に対する一般的なアルゴリズムである。 我々は、k-means++とk-means++の並列化に対する近似とbi-criteria近似の改善を示す。 我々はk-means++と同じ近似保証を持つk-means++並列アルゴリズム(Exponential Race k-means++)を提案する。
  論文  参考訳（メタデータ） (2020-10-27T17:46:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。