論文の概要: Bagged $k$-Distance for Mode-Based Clustering Using the Probability of
Localized Level Sets
- arxiv url: http://arxiv.org/abs/2210.09786v1
- Date: Tue, 18 Oct 2022 11:58:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 13:46:58.385316
- Title: Bagged $k$-Distance for Mode-Based Clustering Using the Probability of
Localized Level Sets
- Title(参考訳): 局所化レベルセットの確率を用いたモードベースクラスタリングのためのタグ付き$k$-Distance
- Authors: Hanyuan Hang
- Abstract要約: モードベースのクラスタリング(textitBDMBC)のためのtextitbagged $k$-distance というアンサンブル学習アルゴリズムを提案する。
理論的には、bagged $k$-distance, sub-sample size $s$, bagging rounds $B$, and the number of neighbors $k_L$ for the localized level set, BDMBC can achieve optimal convergence rate for mode estimation。
- 参考スコア(独自算出の注目度): 7.208515071018781
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose an ensemble learning algorithm named \textit{bagged
$k$-distance for mode-based clustering} (\textit{BDMBC}) by putting forward a
new measurement called the \textit{probability of localized level sets}
(\textit{PLLS}), which enables us to find all clusters for varying densities
with a global threshold. On the theoretical side, we show that with a properly
chosen number of nearest neighbors $k_D$ in the bagged $k$-distance, the
sub-sample size $s$, the bagging rounds $B$, and the number of nearest
neighbors $k_L$ for the localized level sets, BDMBC can achieve optimal
convergence rates for mode estimation. It turns out that with a relatively
small $B$, the sub-sample size $s$ can be much smaller than the number of
training data $n$ at each bagging round, and the number of nearest neighbors
$k_D$ can be reduced simultaneously. Moreover, we establish optimal convergence
results for the level set estimation of the PLLS in terms of Hausdorff
distance, which reveals that BDMBC can find localized level sets for varying
densities and thus enjoys local adaptivity. On the practical side, we conduct
numerical experiments to empirically verify the effectiveness of BDMBC for mode
estimation and level set estimation, which demonstrates the promising accuracy
and efficiency of our proposed algorithm.
- Abstract(参考訳): 本稿では,グローバルしきい値の変動密度に対して,すべてのクラスタを探索できる, \textit{probability of localized level sets} (\textit{plls}) と呼ばれる新しい測定法を提示することにより,モードベースクラスタリングのための \textit{bagged $k$- distance for mode-based clustering} (\textit{bdmbc}) というアンサンブル学習アルゴリズムを提案する。
理論的には、バッグ付き$k$- distance、サブサンプルサイズ$s$、バグングラウンドが$b$、最も近い隣人が$k_l$でローカライズされたレベルセットに対して、bdmbcはモード推定に最適な収束率を達成することができる。
比較的小さな$B$の場合、サブサンプルサイズ$s$は、各バッグラウンドでのトレーニングデータ$n$の回数よりもはるかに小さくなり、近隣の$k_D$の数を同時に削減できることがわかった。
さらに, ハウスドルフ距離の観点で pll のレベル集合推定のための最適収束結果を確立し, bdmbc が様々な密度の局所化レベル集合を見つけることができ, 局所的適応性が期待できることを示した。
実用面では,BDMBCのモード推定とレベルセット推定の有効性を実証的に検証する数値実験を行い,提案アルゴリズムの有望な精度と効率性を示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
我々は,ユーザのネットワーク上で動作する分散クラスタリングアルゴリズムのファミリーを開発する。
DGC-$mathcalF_rho$は、K$-meansやHuber Losといった一般的なクラスタリング損失に特化している。
DGC-$mathcalF_rho$のコンセンサス固定点は、全データ上の勾配クラスタリングの固定点と等価であることを示す。
論文 参考訳(メタデータ) (2024-02-02T10:44:42Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳(メタデータ) (2023-01-09T18:36:49Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。
我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
論文 参考訳(メタデータ) (2021-11-02T17:45:02Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-01T14:10:38Z) - Faster DBSCAN via subsampled similarity queries [42.93847281082316]
DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。
本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
論文 参考訳(メタデータ) (2020-06-11T18:57:54Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。