論文の概要: Adapting $k$-means algorithms for outliers
- arxiv url: http://arxiv.org/abs/2007.01118v2
- Date: Fri, 23 Sep 2022 14:26:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 14:44:16.056382
- Title: Adapting $k$-means algorithms for outliers
- Title（参考訳）: 外れ値に対する$k$-meansアルゴリズムの適用
- Authors: Christoph Grunau and V\'aclav Rozho\v{n}
- Abstract要約: 我々は、$k$-means問題に対して、複数の単純なサンプリングベースのアルゴリズムを、外れ値を持つ設定に適応する方法を示す。
我々のアルゴリズムは、目的関数に対して$O(varepsilon)$-approximationを行いながら、$(varepsilon)z$outliersを出力する。
- 参考スコア（独自算出の注目度）: 1.9290392443571387
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper shows how to adapt several simple and classical sampling-based
algorithms for the $k$-means problem to the setting with outliers.
Recently, Bhaskara et al. (NeurIPS 2019) showed how to adapt the classical
$k$-means++ algorithm to the setting with outliers. However, their algorithm
needs to output $O(\log (k) \cdot z)$ outliers, where $z$ is the number of true
outliers, to match the $O(\log k)$-approximation guarantee of $k$-means++. In
this paper, we build on their ideas and show how to adapt several sequential
and distributed $k$-means algorithms to the setting with outliers, but with
substantially stronger theoretical guarantees: our algorithms output
$(1+\varepsilon)z$ outliers while achieving an $O(1 /
\varepsilon)$-approximation to the objective function. In the sequential world,
we achieve this by adapting a recent algorithm of Lattanzi and Sohler (ICML
2019). In the distributed setting, we adapt a simple algorithm of Guha et al.
(IEEE Trans. Know. and Data Engineering 2003) and the popular $k$-means$\|$ of
Bahmani et al. (PVLDB 2012).
A theoretical application of our techniques is an algorithm with running time
$\tilde{O}(nk^2/z)$ that achieves an $O(1)$-approximation to the objective
function while outputting $O(z)$ outliers, assuming $k \ll z \ll n$. This is
complemented with a matching lower bound of $\Omega(nk^2/z)$ for this problem
in the oracle model.
- Abstract（参考訳）: 本稿では,数種類の単純なサンプリングベースアルゴリズムを$k$-means問題に適応させる方法について述べる。
最近、Bhaskara氏(NeurIPS 2019)は、古典的な$k$-means++アルゴリズムを外れ値の設定に適応する方法を示した。
しかし、それらのアルゴリズムは$o(\log (k) \cdot z)$ outliersを出力する必要があり、ここで$z$は真の outlier の数であり、$o(\log k)$-approximation guarantee of $k$-means++と一致する。
本稿では,それらのアイデアに基づいて,複数の逐次的および分散的な$k$-meansアルゴリズムをアウトレーヤ付き設定に適応させる方法を示すが,より強力な理論的保証が得られた:我々のアルゴリズムは,O(1 / \varepsilon)$-approximationを目標関数に達成しつつ,$(1+\varepsilon)z$outliersを出力する。
シーケンシャルな世界では、最近のアルゴリズムであるLattanziとSohler(ICML 2019)を適用することで、これを実現する。
分散環境では、Guha et al. (IEEE Trans. Know. and Data Engineering 2003) の単純なアルゴリズムと、人気のある$k$-means$\|$ of Bahmani et al. (PVLDB 2012) を適用する。
我々の手法の理論的応用は、動作時間$\tilde{O}(nk^2/z)$のアルゴリズムで、目標関数に対して$O(1)$-approximationを行い、$O(z)$outliersを出力し、$k \ll z \ll n$を仮定する。
これは、オラクルモデルにおけるこの問題に対する$\Omega(nk^2/z)$の一致する下界で補される。
関連論文リスト
- 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) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Improved Outlier Robust Seeding for k-means [3.9973713691377646]
逆ノイズや外れ値では、D2$サンプリングは、より遠方の外れ値から中心を選別する傾向にある。
サンプル分布として$D2$の単純な変種を提案する。
我々のアルゴリズムは、$O(k)$クラスタの代わりに正確に$k$クラスタを出力するように修正することもできる。
論文 参考訳（メタデータ） (2023-09-06T04:46:01Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。
我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
論文 参考訳（メタデータ） (2022-07-16T13:49:07Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。