論文の概要: Multi-Swap $k$-Means++

• arxiv url: http://arxiv.org/abs/2309.16384v2
• Date: Fri, 25 Oct 2024 18:14:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 16:00:55.990689
• Title: Multi-Swap $k$-Means++
• Title（参考訳）: Multi-Swap $k$-Means++
• Authors: Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis,
• Abstract要約: Arthur and Vassilvitskii (SODA 2007)の$k$-means++アルゴリズムは、人気のある$k$-meansクラスタリングの目的を最適化するための実践者の選択アルゴリズムであることが多い。 Lattanzi氏とSohler氏(ICML)は、$k$-means++を$O(k log log k)$で拡張して、$k$-meansクラスタリング問題に$c$-approximationをもたらすよう提案した。
• 参考スコア（独自算出の注目度）: 30.967186562175893
• License:
• Abstract: The $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular $k$-means clustering objective and is known to give an $O(\log k)$-approximation in expectation. To obtain higher quality solutions, Lattanzi and Sohler (ICML 2019) proposed augmenting $k$-means++ with $O(k \log \log k)$ local search steps obtained through the $k$-means++ sampling distribution to yield a $c$-approximation to the $k$-means clustering problem, where $c$ is a large absolute constant. Here we generalize and extend their local search algorithm by considering larger and more sophisticated local search neighborhoods hence allowing to swap multiple centers at the same time. Our algorithm achieves a $9 + \varepsilon$ approximation ratio, which is the best possible for local search. Importantly we show that our approach yields substantial practical improvements, we show significant quality improvements over the approach of Lattanzi and Sohler (ICML 2019) on several datasets.
• Abstract（参考訳）: Arthur と Vassilvitskii の $k$-means++ アルゴリズム (SODA 2007) は、よく使われる $k$-means クラスタリングの目的を最適化するための実践者の選択アルゴリズムであり、期待して$O(\log k)$-approximation を与えることが知られている。 高品質なソリューションを得るために、Lattanzi氏とSohler氏(ICML 2019)は、$k$-means++を$O(k \log \log k)$で拡張することを提案した。 ここでは、より大規模で洗練された地域検索地区を考慮し、複数のセンターを同時に置き換えることにより、その局所検索アルゴリズムを一般化し、拡張する。 本アルゴリズムは,局所探索に最適な近似比を9+\varepsilon$で達成する。 重要なことは、我々のアプローチが実質的な改善をもたらすことを示し、いくつかのデータセット上でのLattanziとSohler(ICML 2019)のアプローチに対して、大幅な品質改善を示す。

関連論文リスト

• 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)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52: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)
• A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
  k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。 我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
  論文  参考訳（メタデータ） (2022-07-16T13:49:07Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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