論文の概要: Consistency of Lloyd's Algorithm Under Perturbations
- arxiv url: http://arxiv.org/abs/2309.00578v1
- Date: Fri, 1 Sep 2023 16:45:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-04 12:49:03.379776
- Title: Consistency of Lloyd's Algorithm Under Perturbations
- Title（参考訳）: 摂動下におけるロイドアルゴリズムの整合性
- Authors: Dhruv Patel and Hui Shen and Shankar Bhamidi and Yufeng Liu and Vladas
Pipiras
- Abstract要約: ロイドのアルゴリズムは最も広く使われているクラスタリングアルゴリズムの1つである。
準ガウス混合のサンプルに対するロイドのアルゴリズムの誤クラスタリング速度は、$O(log(n))$ iterationsの後に指数関数的に有界であることを示す。
- 参考スコア（独自算出の注目度）: 11.56433365648479
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the context of unsupervised learning, Lloyd's algorithm is one of the most
widely used clustering algorithms. It has inspired a plethora of work
investigating the correctness of the algorithm under various settings with
ground truth clusters. In particular, in 2016, Lu and Zhou have shown that the
mis-clustering rate of Lloyd's algorithm on $n$ independent samples from a
sub-Gaussian mixture is exponentially bounded after $O(\log(n))$ iterations,
assuming proper initialization of the algorithm. However, in many applications,
the true samples are unobserved and need to be learned from the data via
pre-processing pipelines such as spectral methods on appropriate data matrices.
We show that the mis-clustering rate of Lloyd's algorithm on perturbed samples
from a sub-Gaussian mixture is also exponentially bounded after $O(\log(n))$
iterations under the assumptions of proper initialization and that the
perturbation is small relative to the sub-Gaussian noise. In canonical settings
with ground truth clusters, we derive bounds for algorithms such as
$k$-means$++$ to find good initializations and thus leading to the correctness
of clustering via the main result. We show the implications of the results for
pipelines measuring the statistical significance of derived clusters from data
such as SigClust. We use these general results to derive implications in
providing theoretical guarantees on the misclustering rate for Lloyd's
algorithm in a host of applications, including high-dimensional time series,
multi-dimensional scaling, and community detection for sparse networks via
spectral clustering.
- Abstract（参考訳）: 教師なし学習の文脈では、ロイドのアルゴリズムは最も広く使われているクラスタリングアルゴリズムの1つである。
これは、基底真理クラスタを用いた様々な設定下でのアルゴリズムの正確性を調査する多くの研究に影響を与えている。
特に2016年、Lu と Zhou は、亜ガウス混合からの$n$独立サンプルに対するロイドのアルゴリズムの誤クラスタリング速度は、アルゴリズムの適切な初期化を仮定して$O(\log(n))$反復の後に指数関数的に有界であることを示した。
しかし、多くのアプリケーションでは、真のサンプルは観測されず、適切なデータ行列上のスペクトルメソッドのような前処理パイプラインを通じてデータから学習する必要がある。
準ガウス混合の摂動サンプルに対するロイドのアルゴリズムの誤クラスタリング速度は、適切な初期化の仮定の下での$O(\log(n))$繰り返しの後に指数関数的に有界であり、その摂動は準ガウス雑音と比較して小さいことを示す。
地上の真理クラスタを持つ標準設定では、$k$-means$++$のようなアルゴリズムのバウンダリを導出し、優れた初期化を見つけ、その結果、クラスタリングの正しさにつながる。
sigclustのようなデータから派生したクラスタの統計学的意義を計測するパイプラインにおいて,結果の意義を示す。
これらの一般的な結果を用いて、スペクトルクラスタリングによるスパースネットワークの高次元時系列、多次元スケーリング、コミュニティ検出などを含む一連のアプリケーションにおいて、ロイズアルゴリズムの誤クラスタリング率に関する理論的保証を提供する。
関連論文リスト
- A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。
汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。
MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
論文 参考訳（メタデータ） (2024-07-19T08:29:12Z) - Heteroskedastic Tensor Clustering [20.979358557219953]
我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。
まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。
我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
論文 参考訳（メタデータ） (2023-11-04T02:50:40Z) - A Modular Spatial Clustering Algorithm with Noise Specification [0.0]
細菌ファームアルゴリズムは、閉じた実験農場の細菌の成長にインスパイアされている。
他のクラスタリングアルゴリズムとは対照的に、我々のアルゴリズムはクラスタリング中に除外されるノイズの量を規定する機能も備えている。
論文 参考訳（メタデータ） (2023-09-18T18:05:06Z) - Scalable Clustering: Large Scale Unsupervised Learning of Gaussian
Mixture Models with Outliers [5.478764356647437]
本稿では,損失最小化に基づくロバストなクラスタリングアルゴリズムを提案する。
これはアルゴリズムが高い確率で高い精度を得るという理論的保証を提供する。
実世界の大規模データセットの実験では、アルゴリズムの有効性が示されている。
論文 参考訳（メタデータ） (2023-02-28T14:39:18Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model [12.868722327487752]
行列値の観測を行うために低ランク混合モデル(LrMM)を提案する。
ロイドのアルゴリズムと低ランク近似を統合して計算効率のよいクラスタリング法を設計する。
本手法は,実世界のデータセットにおける文献上の他者よりも優れる。
論文 参考訳（メタデータ） (2022-07-11T03:16:10Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳（メタデータ） (2020-11-18T16:40:45Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Randomized Spectral Clustering in Large-Scale Stochastic Block Models [13.366036495177923]
統計的観点からランダム化されたスケッチアルゴリズムを用いてスペクトルクラスタリングについて検討する。
弱い条件下では、ランダム化されたスペクトルクラスタリングアルゴリズムは、元のスペクトルクラスタリングアルゴリズムと同じ理論的境界に導かれる。
Rclustと呼ばれる新しいRパッケージが開発され、一般に公開されている。
論文 参考訳（メタデータ） (2020-01-20T04:15:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。