Fugu-MT 論文翻訳(概要): Improved Outlier Robust Seeding for k-means

論文の概要: Improved Outlier Robust Seeding for k-means

arxiv url: http://arxiv.org/abs/2309.02710v1
Date: Wed, 6 Sep 2023 04:46:01 GMT
ステータス: 処理完了
システム内更新日: 2023-09-07 16:58:42.902735
Title: Improved Outlier Robust Seeding for k-means
Title（参考訳）: k-meansにおけるoutlier Robust Seedingの改良
Authors: Amit Deshpande and Rameshwar Pratap
Abstract要約: 逆ノイズや外れ値では、D2$サンプリングは、より遠方の外れ値から中心を選別する傾向にある。サンプル分布として$D2$の単純な変種を提案する。我々のアルゴリズムは、$O(k)$クラスタの代わりに正確に$k$クラスタを出力するように修正することもできる。
参考スコア（独自算出の注目度）: 3.9973713691377646
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The $k$-means is a popular clustering objective, although it is inherently non-robust and sensitive to outliers. Its popular seeding or initialization called $k$-means++ uses $D^{2}$ sampling and comes with a provable $O(\log k)$ approximation guarantee \cite{AV2007}. However, in the presence of adversarial noise or outliers, $D^{2}$ sampling is more likely to pick centers from distant outliers instead of inlier clusters, and therefore its approximation guarantees \textit{w.r.t.} $k$-means solution on inliers, does not hold. Assuming that the outliers constitute a constant fraction of the given data, we propose a simple variant in the $D^2$ sampling distribution, which makes it robust to the outliers. Our algorithm runs in $O(ndk)$ time, outputs $O(k)$ clusters, discards marginally more points than the optimal number of outliers, and comes with a provable $O(1)$ approximation guarantee. Our algorithm can also be modified to output exactly $k$ clusters instead of $O(k)$ clusters, while keeping its running time linear in $n$ and $d$. This is an improvement over previous results for robust $k$-means based on LP relaxation and rounding \cite{Charikar}, \cite{KrishnaswamyLS18} and \textit{robust $k$-means++} \cite{DeshpandeKP20}. Our empirical results show the advantage of our algorithm over $k$-means++~\cite{AV2007}, uniform random seeding, greedy sampling for $k$ means~\cite{tkmeanspp}, and robust $k$-means++~\cite{DeshpandeKP20}, on standard real-world and synthetic data sets used in previous work. Our proposal is easily amenable to scalable, faster, parallel implementations of $k$-means++ \cite{Bahmani,BachemL017} and is of independent interest for coreset constructions in the presence of outliers \cite{feldman2007ptas,langberg2010universal,feldman2011unified}.
Abstract（参考訳）: k$-meansは一般的なクラスタリングの目標だが、本質的には非ロバストであり、外れ値に敏感である。一般的なシードや初期化である$k$-means++は$D^{2}$サンプリングを使用し、証明可能な$O(\log k)$ approximation guarantee \cite{AV2007}が付属している。しかし、逆雑音や異常値が存在する場合、サンプリングした$d^{2}$は、異常値クラスタではなく遠く離れた外れ値から中心を選択する傾向が強いため、その近似は、異常値に対する$k$-means の解を保証しない。与えられたデータのうち、外れ値が一定の割合を占めると仮定すると、$D^2$のサンプリング分布において単純な変種が提案される。我々のアルゴリズムは、$O(ndk)$タイムで実行され、$O(k)$クラスタを出力し、最適値よりも極端に多くのポイントを破棄し、証明可能な$O(1)$近似を保証する。アルゴリズムは、o(k)$クラスタではなく、正確に$k$クラスタを出力するように変更することもでき、実行時間は$n$と$d$で線形に保たれます。これは、lpリラクゼーションと丸い \cite{charikar}, \cite{krishnaswamyls18}, \textit{robust $k$-means++} \cite{deshpandekp20} に基づく堅牢な $k$-means に対する以前の結果に対する改善である。実験結果から,本アルゴリズムの利点は,k$-means++~\cite{av2007},uniform random seeding,greedy sampling for $k$ means~\cite{tkmeanspp},ロバストな$k$-means++~\cite{deshpandekp20} を,従来の研究で使用した標準実世界および合成データセット上で示した。我々の提案は、$k$-means++ \cite{Bahmani,BachemL017} のスケーラビリティと高速な並列実装に容易に対応でき、outliers \cite{feldman2007ptas,langberg2010universal,feldman 2011unified} の存在下でコアセットの構築に独立した関心を持っている。

関連論文リスト

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)
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)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文参考訳（メタデータ） (2023-02-20T23:29:43Z)
Global $k$-means$++$: an effective relaxation of the global $k$-means clustering algorithm [0.20305676256390928]
k$-meansアルゴリズムは、その単純さ、有効性、スピードから、一般的なクラスタリング手法である。本稿では,高品質クラスタリングソリューションを効果的に取得する手段として,emphglobal $k$-meanstexttt++クラスタリングアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-11-22T13:42:53Z)
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)
Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文参考訳（メタデータ） (2021-10-05T09:33:49Z)
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)
Adapting $k$-means algorithms for outliers [1.9290392443571387]
我々は、$k$-means問題に対して、複数の単純なサンプリングベースのアルゴリズムを、外れ値を持つ設定に適応する方法を示す。我々のアルゴリズムは、目的関数に対して$O(varepsilon)$-approximationを行いながら、$(varepsilon)z$outliersを出力する。
論文参考訳（メタデータ） (2020-07-02T14:14:33Z)
Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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