論文の概要: Certifying clusters from sum-of-norms clustering

• arxiv url: http://arxiv.org/abs/2006.11355v2
• Date: Thu, 8 Jul 2021 06:13:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 04:33:36.711277
• Title: Certifying clusters from sum-of-norms clustering
• Title（参考訳）: sum-of-normsクラスタリングによるクラスタ認証
• Authors: Tao Jiang, Stephen Vavasis
• Abstract要約: 本稿では,近似解から正しいクラスタ割り当てを同定し,証明するクラスタリングテストを提案する。 提案手法では, クラスタ割り当てが, 十分に多くの繰り返しを経て, 原始二重経路追従アルゴリズムによって保証されることが保証されていることを示す。
• 参考スコア（独自算出の注目度）: 13.747619681451875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sum-of-norms clustering is a clustering formulation based on convex optimization that automatically induces hierarchy. Multiple algorithms have been proposed to solve the optimization problem: subgradient descent by Hocking et al., ADMM and ADA by Chi and Lange, stochastic incremental algorithm by Panahi et al. and semismooth Newton-CG augmented Lagrangian method by Sun et al. All algorithms yield approximate solutions, even though an exact solution is demanded to determine the correct cluster assignment. The purpose of this paper is to close the gap between the output from existing algorithms and the exact solution to the optimization problem. We present a clustering test that identifies and certifies the correct cluster assignment from an approximate solution yielded by any primal-dual algorithm. Our certification validates clustering for both unit and multiplicative weights. The test may not succeed if the approximation is inaccurate. However, we show the correct cluster assignment is guaranteed to be certified by a primal-dual path following algorithm after sufficiently many iterations, provided that the model parameter $\lambda$ avoids a finite number of bad values. Numerical experiments are conducted on Gaussian mixture and half-moon data, which indicate that carefully chosen multiplicative weights increase the recovery power of sum-of-norms clustering.
• Abstract（参考訳）: Sum-of-normsクラスタリングは、自動的に階層を誘導する凸最適化に基づくクラスタリングの定式化である。 最適化問題を解決するために複数のアルゴリズムが提案されている: hocking et al., admm and ada by chi and lange, stochastic incremental algorithm by panahi et al., semismooth newton-cg augmented lagrangian method by sun et al。 すべてのアルゴリズムは、正確な解が正しいクラスタ割り当てを決定するために要求されたとしても、近似解が得られる。 本論文の目的は,既存のアルゴリズムの出力と最適化問題に対する厳密な解とのギャップを埋めることである。 本稿では,任意の原始双対アルゴリズムによって得られる近似解から正しいクラスタ割り当てを特定し,証明するクラスタリングテストを提案する。 認証は,単位重みと乗法重みのクラスタリングを検証する。 近似が不正確な場合、テストは成功しない。 しかし、モデルパラメータ$\lambda$が有限個の悪い値を避けることを条件として、十分に多くの繰り返しの後にアルゴリズムを従えば正しいクラスタ割り当てが保証されることを示す。 ガウス混合と半月データについて数値実験を行い, 選抜された乗法重みがノルムクラスタリングの回復力を増加させることを示した。

関連論文リスト

• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。 現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。 本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-29T07:24:11Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Regularization and Optimization in Model-Based Clustering [4.096453902709292]
  k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。 一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。 これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
  論文  参考訳（メタデータ） (2023-02-05T18:22:29Z)
• 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 with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects [0.0]
  Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。 この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。 本稿では,本手法の計算的側面について考察する。
  論文  参考訳（メタデータ） (2021-02-02T10:39:27Z)
• An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
  最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。 最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。 本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
  論文  参考訳（メタデータ） (2020-06-22T20:02:59Z)
• Efficient Path Algorithms for Clustered Lasso and OSCAR [0.0]
  本稿では,クラスタリングされたLassoとOSCARのための効率的な経路アルゴリズムを提案する。 提案アルゴリズムは数値実験において既存のアルゴリズムよりも効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-06-16T07:43:57Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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