論文の概要: A general theory for robust clustering via trimmed mean
- arxiv url: http://arxiv.org/abs/2401.05574v2
- Date: Fri, 2 Feb 2024 19:58:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 03:19:05.321755
- Title: A general theory for robust clustering via trimmed mean
- Title(参考訳): トリミング平均によるロバストクラスタリングの一般理論
- Authors: Soham Jana, Jianqing Fan, Sanjeev Kulkarni
- Abstract要約: 提案手法は,新しいトリミング平均型セントロイド推定器を用いたハイブリッドクラスタリング手法を導入し,誤ラベル保証を実現する。
その結果, 誤差がガウス以下の分布に従えば, ガウス以下のケースに還元されることがわかった。
これらの初期セントロイド推定値は,その後のクラスタリングアルゴリズムにおいて,最適な誤ラベル率を達成するのに十分であることを示す。
- 参考スコア(独自算出の注目度): 7.650319416775203
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a fundamental tool in statistical machine learning in the
presence of heterogeneous data. Many recent results focus primarily on optimal
mislabeling guarantees, when data are distributed around centroids with
sub-Gaussian errors. Yet, the restrictive sub-Gaussian model is often invalid
in practice, since various real-world applications exhibit heavy tail
distributions around the centroids or suffer from possible adversarial attacks
that call for robust clustering with a robust data-driven initialization. In
this paper, we introduce a hybrid clustering technique with a novel
multivariate trimmed mean type centroid estimate to produce mislabeling
guarantees under a weak initialization condition for general error
distributions around the centroids. A matching lower bound is derived, up to
factors depending on the number of clusters. In addition, our approach also
produces the optimal mislabeling even in the presence of adversarial outliers.
Our results reduce to the sub-Gaussian case when errors follow sub-Gaussian
distributions. To solve the problem thoroughly, we also present novel
data-driven robust initialization techniques and show that, with probabilities
approaching one, these initial centroid estimates are sufficiently good for the
subsequent clustering algorithm to achieve the optimal mislabeling rates.
Furthermore, we demonstrate that the Lloyd algorithm is suboptimal for more
than two clusters even when errors are Gaussian, and for two clusters when
errors distributions have heavy tails. Both simulated data and real data
examples lend further support to both of our robust initialization procedure
and clustering algorithm.
- Abstract(参考訳): クラスタリングは、異種データの存在下での統計機械学習の基本的なツールである。
最近の多くの結果は、サブガウシアンエラーのあるセントロイドの周りにデータが分散される場合の、最適なミスラベルの保証に重点を置いている。
しかし、制限付きサブガウシアンモデルはしばしば無効であり、様々な実世界のアプリケーションでは、centroids周辺に重いテール分布を示すか、堅牢なデータ駆動初期化で堅牢なクラスタリングを求める敵の攻撃に苦しむためである。
本稿では,新しい多変量トリミング平均型セントロイド推定を用いたハイブリッドクラスタリング手法を導入し,セントロイド周辺の一般誤差分布に対する弱初期化条件下での誤ラベル保証を実現する。
一致した下界が導出され、クラスタ数に依存する要因まで導出される。
さらに,本手法は,対向性外乱の存在下においても,最適な誤ラベルを生じさせる。
その結果,誤差がサブガウス分布に従う場合,サブガウス分布が減少する。
そこで本研究では,新しいデータ駆動型ロバスト初期化手法を提案するとともに,これらの初期センタロイド推定値が1つに近づくと,後続のクラスタリングアルゴリズムが最適誤ラベル率を達成するのに十分有効であることを示す。
さらに,誤差がガウス型であっても2クラスタ以上,誤差分布が重みを持つ2クラスタではロイドアルゴリズムが最適であることを示す。
シミュレーションデータと実データサンプルの両方が、ロバストな初期化手順とクラスタリングアルゴリズムの両方をサポートする。
関連論文リスト
- Near-Optimal Resilient Aggregation Rules for Distributed Learning Using
1-Center and 1-Mean Clustering with Outliers [26.363521367281706]
ビザンティンの機械学習は、予測不可能な欠陥によってかなりの注目を集めている。
分散学習におけるマシンのセキュア化の鍵は、レジリエントな集約メカニズムである。
論文 参考訳(メタデータ) (2023-12-20T08:36:55Z) - Robust and Automatic Data Clustering: Dirichlet Process meets
Median-of-Means [18.3248037914529]
本稿では,モデルに基づく手法とセントロイド方式の原理を統合することにより,効率的かつ自動的なクラスタリング手法を提案する。
クラスタリング誤差の上限に関する統計的保証は,既存のクラスタリングアルゴリズムよりも提案手法の利点を示唆している。
論文 参考訳(メタデータ) (2023-11-26T19:01:15Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Compound Batch Normalization for Long-tailed Image Classification [77.42829178064807]
本稿では,ガウス混合に基づく複合バッチ正規化法を提案する。
機能空間をより包括的にモデル化し、ヘッドクラスの優位性を減らすことができる。
提案手法は,画像分類における既存の手法よりも優れている。
論文 参考訳(メタデータ) (2022-12-02T07:31:39Z) - Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous
Data [16.153709556346417]
クラスタリングは広くデプロイされた学習ツールである。
iLA-SDPはEMよりも感度が低く、高次元データでは安定である。
論文 参考訳(メタデータ) (2022-09-29T21:03:13Z) - Clustering by the Probability Distributions from Extreme Value Theory [32.496691290725764]
本稿では,クラスタの分布をモデル化するためにk-meansを一般化する。
GPDを用いて各クラスタの確率モデルを確立する。
我々はまた、GEV (Generalized Extreme Value) k-means(一般化極値)(GEV)と呼ばれる単純なベースラインも導入する。
特に、GEV k-平均はクラスタ構造を推定することもでき、したがって古典的なk-平均に対して合理的に振る舞うことができる。
論文 参考訳(メタデータ) (2022-02-20T10:52:43Z) - Anomaly Clustering: Grouping Images into Coherent Clusters of Anomaly
Types [60.45942774425782]
我々は異常クラスタリングを導入し、その目標はデータを異常型の一貫性のあるクラスタにまとめることである。
これは異常検出とは違い、その目標は異常を通常のデータから分割することである。
パッチベースの事前訓練されたディープ埋め込みとオフザシェルフクラスタリング手法を用いた,単純で効果的なクラスタリングフレームワークを提案する。
論文 参考訳(メタデータ) (2021-12-21T23:11:33Z) - Decorrelated Clustering with Data Selection Bias [55.91842043124102]
本稿では,データ選択バイアスを伴うクラスタリングのためのデコリレーション正規化K-Meansアルゴリズム(DCKM)を提案する。
DCKMアルゴリズムは,選択バイアスによって生じる予期せぬ特徴相関を除去する必要があることを示す。
論文 参考訳(メタデータ) (2020-06-29T08:55:50Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳(メタデータ) (2020-06-22T21:12:31Z) - Robust M-Estimation Based Bayesian Cluster Enumeration for Real
Elliptically Symmetric Distributions [5.137336092866906]
データセットにおける最適なクラスタ数のロバストな決定は、広範囲のアプリケーションにおいて必須の要素である。
本稿では任意のReally Symmetric(RES)分散混合モデルで使用できるように一般化する。
サンプルサイズが有限であるデータセットに対して,ロバストな基準を導出するとともに,大規模なサンプルサイズでの計算コスト削減のための近似を提供する。
論文 参考訳(メタデータ) (2020-05-04T11:44:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。