Fugu-MT 論文翻訳(概要): Improved Guarantees for k-means++ and k-means++ Parallel

論文の概要: Improved Guarantees for k-means++ and k-means++ Parallel

arxiv url: http://arxiv.org/abs/2010.14487v1
Date: Tue, 27 Oct 2020 17:46:00 GMT
ステータス: 処理完了
システム内更新日: 2022-10-02 13:10:47.061531
Title: Improved Guarantees for k-means++ and k-means++ Parallel
Title（参考訳）: k-means++とk-means++ parallelの保証の改善
Authors: Konstantin Makarychev, Aravind Reddy, Liren Shan
Abstract要約: k-means++とk-means++並列は、古典的なk-meansクラスタリング問題に対する一般的なアルゴリズムである。我々は、k-means++とk-means++の並列化に対する近似とbi-criteria近似の改善を示す。我々はk-means++と同じ近似保証を持つk-means++並列アルゴリズム(Exponential Race k-means++)を提案する。
参考スコア（独自算出の注目度）: 18.26254785549146
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++.
Abstract（参考訳）: 本稿では,k-means++とk-means++の並列性について検討する。我々は,k-means++ と k-means++ の並列化に関する新しい解析と改良された近似とbi-criteria近似の保証を示す。我々の結果は、これらのアルゴリズムが実際に非常によく機能する理由をより理論的に正当化する。また,k-means++ と同じ近似保証を持つ k-means++ parallel algorithm (exponential race k-means++) の新しい変種を提案する。

関連論文リスト

Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文参考訳（メタデータ） (2023-05-12T03:01:41Z)
Sketch-and-solve approaches to k-means clustering by semidefinite programming [14.930208990741132]
我々は,k-meansクラスタリングのPeng-Wei半定緩和を高速化するためのスケッチ・アンド・ソルジ手法を提案する。データが適切に分離された場合、k平均の最適なクラスタリングを特定する。そうでなければ、我々のアプローチは最適k-平均値に高信頼な下界を与える。
論文参考訳（メタデータ） (2022-11-28T19:51:30Z)
Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
SVMのような機械学習モデルは、シーケンスのペア間の距離/相似性の定義を必要とする。厳密な手法により分類性能は向上するが、計算コストが高い。本稿では,その予測性能を向上させるために,近似カーネルの性能を改善する一連の方法を提案する。
論文参考訳（メタデータ） (2022-09-11T22:44:19Z)
K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect the Number of Clusters [0.12313056815753944]
本稿では,k-meansに基づく改良された階層型アルゴリズムであるk-splitsを紹介する。提案手法の主な利点は,精度と速度である。
論文参考訳（メタデータ） (2021-10-09T23:02:57Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
Fast and Accurate $k$-means++ via Rejection Sampling [44.155614837392214]
k$-means++は時々大きなデータセットの処理が遅くなる。我々は$k$-means++シードのためのニア線形時間アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-12-22T09:14:41Z)
Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文参考訳（メタデータ） (2020-08-18T16:22:06Z)
Breathing K-Means: Superior K-Means Solutions through Dynamic K-Values [0.0]
我々は,広く知られているgreedy k-means++アルゴリズムによって得られる解を平均的に大幅に改善する呼吸k-meansアルゴリズムを提案する。これらの改善は、局所的誤差と実用性尺度に基づいて、周期的にセントロイドの数を増加・減少させる、新しい呼吸技術によって達成される。
論文参考訳（メタデータ） (2020-06-28T17:49:37Z)
k-means++: few more steps yield constant approximation [3.7468898363447654]
Arthur and Vassilvitskii (SODA 2007) の k-means++ アルゴリズムは k-means クラスタリング問題を解くための最先端のアルゴリズムである。最近、Lattanzi と Sohler (ICML) は k-means++ を O(k log k) 局所探索ステップで拡張し、k-means クラスタリング問題に一定の近似(期待)をもたらすことを提案した。
論文参考訳（メタデータ） (2020-02-18T18:28:25Z)

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