論文の概要: No-substitution k-means Clustering with Adversarial Order
- arxiv url: http://arxiv.org/abs/2012.14512v1
- Date: Mon, 28 Dec 2020 22:35:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-19 12:28:06.353749
- Title: No-substitution k-means Clustering with Adversarial Order
- Title（参考訳）: 逆順序を持つ非置換k平均クラスタリング
- Authors: Robi Bhattacharjee and Michal Moshkovitz
- Abstract要約: 任意の順序で到着するデータセットのクラスタリングの難しさを定量化する新しい複雑性尺度を提案する。
我々の新しいアルゴリズムは、$textpoly(klog(n))$centerのみを取り、$textpoly(k)$-approximationです。
- 参考スコア（独自算出の注目度）: 8.706058694927613
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate $k$-means clustering in the online no-substitution setting
when the input arrives in \emph{arbitrary} order. In this setting, points
arrive one after another, and the algorithm is required to instantly decide
whether to take the current point as a center before observing the next point.
Decisions are irrevocable. The goal is to minimize both the number of centers
and the $k$-means cost. Previous works in this setting assume that the input's
order is random, or that the input's aspect ratio is bounded. It is known that
if the order is arbitrary and there is no assumption on the input, then any
algorithm must take all points as centers. Moreover, assuming a bounded aspect
ratio is too restrictive -- it does not include natural input generated from
mixture models.
We introduce a new complexity measure that quantifies the difficulty of
clustering a dataset arriving in arbitrary order. We design a new random
algorithm and prove that if applied on data with complexity $d$, the algorithm
takes $O(d\log(n) k\log(k))$ centers and is an $O(k^3)$-approximation. We also
prove that if the data is sampled from a ``natural" distribution, such as a
mixture of $k$ Gaussians, then the new complexity measure is equal to
$O(k^2\log(n))$. This implies that for data generated from those distributions,
our new algorithm takes only $\text{poly}(k\log(n))$ centers and is a
$\text{poly}(k)$-approximation. In terms of negative results, we prove that the
number of centers needed to achieve an $\alpha$-approximation is at least
$\Omega\left(\frac{d}{k\log(n\alpha)}\right)$.
- Abstract（参考訳）: 入力が \emph{arbitrary} 順に届くとき、オンラインの非置換設定で$k$-meansクラスタリングを調べる。
この設定では、点が次々に到達し、次の点を観測する前に現在の点を中心とするかどうかを即座に決定する必要がある。
決定は無効である。
目標は、センターの数と$k$-meansのコストを最小化することだ。
この設定における以前の作業は、入力の順序がランダムであるか、または入力のアスペクト比が境界であると仮定していた。
順序が任意であり、入力に仮定がない場合、任意のアルゴリズムが全ての点を中心としなければならないことが知られている。
さらに、境界アスペクト比が制限的すぎると仮定すると、混合モデルから生成された自然な入力は含まれない。
任意の順序で到着するデータセットのクラスタリングの難しさを定量化する新しい複雑性尺度を提案する。
我々は、新しいランダムアルゴリズムを設計し、複雑さを$d$とするデータに適用すると、アルゴリズムは$O(d\log(n) k\log(k))$centerを取り、$O(k^3)$-approximationであることを示す。
また、データが$k$ gaussian の混合のような ``natural" 分布からサンプリングされた場合、新しい複雑性測度は $o(k^2\log(n))$ に等しいことが証明される。
これは、これらの分布から生成されたデータに対して、我々の新しいアルゴリズムは$\text{poly}(k\log(n))$centerのみを取り、$\text{poly}(k)$-approximationであることを意味する。
負の結果に関して、$\alpha$-近似を達成するために必要な中心の数が少なくとも$\Omega\left(\frac{d}{k\log(n\alpha)}\right)$であることを証明する。
関連論文リスト
- 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - No-Substitution $k$-means Clustering with Low Center Complexity and
Memory [5.837881923712394]
中心複雑性を$Lower_36, k(X)$で有界なアルゴリズムを開発し、これは真の$O(1)$-近似であり、近似係数は$k$または$n$とは独立である。
このアルゴリズムは、$Lower_36, k(X)$で区切られた最初の既知のアルゴリズムであり、これは真の$O(1)$-近似であり、近似係数は$k$または$n$から独立している。
論文 参考訳（メタデータ） (2021-02-18T01:20:03Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。