論文の概要: A Nearly Tight Analysis of Greedy k-means++

• arxiv url: http://arxiv.org/abs/2207.07949v1
• Date: Sat, 16 Jul 2022 13:49:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-19 18:36:08.504895
• Title: A Nearly Tight Analysis of Greedy k-means++
• Title（参考訳）: Greedy k-means++の近距離解析
• Authors: Christoph Grunau, Ahmet Alper \"Oz\"udo\u{g}ru, V\'aclav Rozho\v{n}, Jakub T\v{e}tek
• Abstract要約: k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。 我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
• 参考スコア（独自算出の注目度）: 1.452875650827562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The famous $k$-means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the $k$-means problem in practice. The algorithm is very simple: it samples the first center uniformly at random and each of the following $k-1$ centers is then always sampled proportional to its squared distance to the closest center so far. Afterward, Lloyd's iterative algorithm is run. The $k$-means++ algorithm is known to return a $\Theta(\log k)$ approximate solution in expectation. In their seminal work, Arthur and Vassilvitskii [SODA 2007] asked about the guarantees for its following \emph{greedy} variant: in every step, we sample $\ell$ candidate centers instead of one and then pick the one that minimizes the new cost. This is also how $k$-means++ is implemented in e.g. the popular Scikit-learn library [Pedregosa et al.; JMLR 2011]. We present nearly matching lower and upper bounds for the greedy $k$-means++: We prove that it is an $O(\ell^3 \log^3 k)$-approximation algorithm. On the other hand, we prove a lower bound of $\Omega(\ell^3 \log^3 k / \log^2(\ell\log k))$. Previously, only an $\Omega(\ell \log k)$ lower bound was known [Bhattacharya, Eube, R\"oglin, Schmidt; ESA 2020] and there was no known upper bound.
• Abstract（参考訳）: ArthurとVassilvitskiiの有名な$k$-means++アルゴリズム(SODA 2007)は、実際に$k$-meansの問題を解決する最も一般的な方法である。 アルゴリズムは非常に単純で、最初の中心をランダムに一様にサンプリングし、次に示す$k-1$センターのそれぞれが、常に最も近い中心への2乗距離に比例してサンプリングされる。 その後、ロイドの反復アルゴリズムが実行される。 k$-means++アルゴリズムは期待値の$\Theta(\log k)$近似解を返すことが知られている。 Arthur and Vassilvitskii [SODA 2007] は、以下の変種に対する保証について尋ねた: すべてのステップにおいて、我々は1つではなく$$$ell$の候補センターをサンプリングし、新しいコストを最小限に抑えるものを選ぶ。 これはまた、人気のscikit-learnライブラリ(pedregosa et al.; jmlr 2011)で$k$-means++を実装する方法でもある。 我々は、大げさな $k$-means++ に対して、ほぼ一致する下界と上界を示し、それが $o(\ell^3 \log^3 k)$-approximation アルゴリズムであることを証明する。 一方、下界の$\Omega(\ell^3 \log^3 k / \log^2(\ell\log k))$を証明する。 以前は$\Omega(\ell \log k)$下限のみが知られている(Bhattacharya, Eube, R\"oglin, Schmidt; ESA 2020)。

関連論文リスト

• 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? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• A Faster $k$-means++ Algorithm [11.428775569173638]
  ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。 我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
  論文  参考訳（メタデータ） (2022-11-28T08:17:12Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
  Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。 私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
  論文  参考訳（メタデータ） (2021-07-02T02:07:12Z)
• Almost Tight Approximation Algorithms for Explainable Clustering [16.22135057266913]
  本稿では,Dasguptaらによって提案された最近の説明可能なクラスタリングの枠組みについて考察する。 具体的には、$k$-meansと$k$-mediansの問題に焦点をあて、ほぼ上と下の境界を提供する。
  論文  参考訳（メタデータ） (2021-07-01T23:49:23Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Adapting $k$-means algorithms for outliers [1.9290392443571387]
  我々は、$k$-means問題に対して、複数の単純なサンプリングベースのアルゴリズムを、外れ値を持つ設定に適応する方法を示す。 我々のアルゴリズムは、目的関数に対して$O(varepsilon)$-approximationを行いながら、$(varepsilon)z$outliersを出力する。
  論文  参考訳（メタデータ） (2020-07-02T14:14:33Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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