Fugu-MT 論文翻訳(概要): k-means++: few more steps yield constant approximation

論文の概要: k-means++: few more steps yield constant approximation

arxiv url: http://arxiv.org/abs/2002.07784v1
Date: Tue, 18 Feb 2020 18:28:25 GMT
ステータス: 処理完了
システム内更新日: 2022-12-30 20:45:02.690574
Title: k-means++: few more steps yield constant approximation
Title（参考訳）: k-means++: 定数近似を与えるステップはもっと少ない
Authors: Davin Choo, Christoph Grunau, Julian Portmann, V\'aclav Rozho\v{n}
Abstract要約: Arthur and Vassilvitskii (SODA 2007) の k-means++ アルゴリズムは k-means クラスタリング問題を解くための最先端のアルゴリズムである。最近、Lattanzi と Sohler (ICML) は k-means++ を O(k log k) 局所探索ステップで拡張し、k-means クラスタリング問題に一定の近似(期待)をもたらすことを提案した。
参考スコア（独自算出の注目度）: 3.7468898363447654
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant $\eps > 0$, with only $\eps k$ additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.
Abstract（参考訳）: Arthur and Vassilvitskii (SODA 2007) の k-means++ アルゴリズムは k-means クラスタリング問題を解くための最先端のアルゴリズムであり、期待して O(log k)-近似を与えることが知られている。最近、Lattanzi氏とSohler氏(ICML 2019)は、k-means++をO(k log log k)ローカル検索ステップで拡張し、k-meansクラスタリング問題に一定の近似(期待)をもたらすことを提案した。本稿では,任意の任意の小さな定数$\eps > 0$に対して,任意の局所探索ステップに$\eps k$を付加すれば,一定の近似保証(kの確率が高い)を達成でき,その論文の未解決問題を解消できることを示す。

関連論文リスト

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)
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)
Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文参考訳（メタデータ） (2022-04-20T07:14:21Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
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)
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-sums: another side of k-means [34.317086730703124]
本稿では, 数十年前からあるクラスタリング手法k-meansについて再検討する。 k平均の元々の歪み最小化モデルは、純粋な最小化法によって対処される。クラスタ内の対距離を最小化する新たなターゲット関数を示す。
論文参考訳（メタデータ） (2020-05-19T14:36:12Z)
Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文参考訳（メタデータ） (2020-05-02T10:39:26Z)

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