論文の概要: Towards Optimal Lower Bounds for k-median and k-means Coresets
- arxiv url: http://arxiv.org/abs/2202.12793v1
- Date: Fri, 25 Feb 2022 16:13:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-28 17:32:04.898404
- Title: Towards Optimal Lower Bounds for k-median and k-means Coresets
- Title（参考訳）: k中間とk平均のコアセットに対する最適下界に向けて
- Authors: Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris
Schwiegelshohn
- Abstract要約: 計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。
我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
- 参考スコア（独自算出の注目度）: 25.713987341159918
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a set of points in a metric space, the $(k,z)$-clustering problem
consists of finding a set of $k$ points called centers, such that the sum of
distances raised to the power of $z$ of every data point to its closest center
is minimized. Special cases include the famous k-median problem ($z = 1$) and
k-means problem ($z = 2$). The $k$-median and $k$-means problems are at the
heart of modern data analysis and massive data applications have given raise to
the notion of coreset: a small (weighted) subset of the input point set
preserving the cost of any solution to the problem up to a multiplicative $(1
\pm \varepsilon)$ factor, hence reducing from large to small scale the input to
the problem.
In this paper, we present improved lower bounds for coresets in various
metric spaces. In finite metrics consisting of $n$ points and doubling metrics
with doubling constant $D$, we show that any coreset for $(k,z)$ clustering
must consist of at least $\Omega(k \varepsilon^{-2} \log n)$ and $\Omega(k
\varepsilon^{-2} D)$ points, respectively. Both bounds match previous upper
bounds up to polylog factors. In Euclidean spaces, we show that any coreset for
$(k,z)$ clustering must consists of at least $\Omega(k\varepsilon^{-2})$
points. We complement these lower bounds with a coreset construction consisting
of at most $\tilde{O}(k\varepsilon^{-2}\cdot \min(\varepsilon^{-z},k))$ points.
- Abstract（参考訳）: 計量空間内の点の集合が与えられたとき、$(k,z)$-clustering 問題は、中心と呼ばれる一連の $k$ の点を見つけることから成り、すべてのデータ点から最も近い中心までの距離の合計は最小化される。
特殊な例としては、有名なk-メディア問題(z = 1$)やk-means問題(z = 2$)がある。
k$-median と $k$-means 問題は現代のデータ分析の中心であり、大量のデータアプリケーションによってコアセットの概念が生まれている: 入力点集合の小さな(重み付けされた)サブセットは、問題の解のコストを乗法的な $(1 \pm \varepsilon)$ factor まで保ち、その結果、問題への入力を大規模から小規模に削減する。
本稿では,様々な距離空間におけるコア集合の下限の改良について述べる。
n$ポイントと2倍の定数$d$を持つ2倍のメトリクスからなる有限メトリクスでは、$(k,z)$クラスタリングのための任意のコアセットは、それぞれ$\omega(k \varepsilon^{-2} \log n)$と$\omega(k \varepsilon^{-2} d)$ポイントでなければならない。
両方の境界は、ポリログ因子までの以前の上限と一致する。
ユークリッド空間において、任意の coreset for $(k,z)$ clustering は少なくとも $\omega(k\varepsilon^{-2})$ points でなければならない。
これらの下界を、少なくとも$\tilde{O}(k\varepsilon^{-2}\cdot \min(\varepsilon^{-z},k))$点からなるコアセット構成で補う。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
$ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。
我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。
我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
論文 参考訳（メタデータ） (2024-07-03T16:49:28Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - On Generalization Bounds for Projective Clustering [3.4490841399255823]
ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。
中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
論文 参考訳（メタデータ） (2023-10-13T14:15:54Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Improved Coresets for Euclidean $k$-Means [24.850829728643923]
1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。
本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
論文 参考訳（メタデータ） (2022-11-15T14:47:24Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。