論文の概要: An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering

• arxiv url: http://arxiv.org/abs/2006.12592v1
• Date: Mon, 22 Jun 2020 20:02:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 05:47:08.690768
• Title: An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering
• Title（参考訳）: 凸クラスタリングのための効率的な平滑近似勾配アルゴリズム
• Authors: Xin Zhou, Chunlei Du, and Xiaodong Cai
• Abstract要約: 最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。 最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。 本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
• 参考スコア（独自算出の注目度）: 2.5182813818441945
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cluster analysis organizes data into sensible groupings and is one of fundamental modes of understanding and learning. The widely used K-means and hierarchical clustering methods can be dramatically suboptimal due to local minima. Recently introduced convex clustering approach formulates clustering as a convex optimization problem and ensures a globally optimal solution. However, the state-of-the-art convex clustering algorithms, based on the alternating direction method of multipliers (ADMM) or the alternating minimization algorithm (AMA), require large computation and memory space, which limits their applications. In this paper, we develop a very efficient smoothing proximal gradient algorithm (Sproga) for convex clustering. Our Sproga is faster than ADMM- or AMA-based convex clustering algorithms by one to two orders of magnitude. The memory space required by Sproga is less than that required by ADMM and AMA by at least one order of magnitude. Computer simulations and real data analysis show that Sproga outperforms several well known clustering algorithms including K-means and hierarchical clustering. The efficiency and superior performance of our algorithm will help convex clustering to find its wide application.
• Abstract（参考訳）: クラスタ分析はデータを合理的なグループ分けに整理し、理解と学習の基本的なモードの1つである。 広く使われているk平均と階層的クラスタリング法は、局所的な極小さのため劇的に最適である。 最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化し、グローバルな最適解を保証する。 しかしながら、乗算器の交互方向法(admm)や交互最小化アルゴリズム(ama)に基づく最先端の凸クラスタリングアルゴリズムは、大きな計算とメモリ空間を必要とするため、アプリケーションを制限することができる。 本稿では,凸クラスタリングのための非常に効率的な平滑化近位勾配アルゴリズム(sproga)を開発した。 我々のSprogaはADMMやAMAベースの凸クラスタリングアルゴリズムよりも1～2桁高速です。 Sprogaが要求するメモリ空間は、ADMMとAMAが要求するメモリ空間よりも1桁以下である。 計算機シミュレーションと実データ解析により、SprogaはK平均や階層クラスタリングなど、よく知られたクラスタリングアルゴリズムよりも優れていることが示された。 このアルゴリズムの効率性と優れた性能は、凸クラスタリングによる広い応用の発見に役立つだろう。

関連論文リスト

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Hybridization of K-means with improved firefly algorithm for automatic clustering in high dimension [0.0]
  最適なクラスタ数を求めるため,PCAを用いてSilhouette法とElbow法を実装した。 Fireflyアルゴリズムでは、全個体群は自動的にサブ集団に分割され、収束速度を減少させ、局所的なミニマにトラップされる。 本研究は,自動クラスタリングのためのK-meansとODFAモデルを組み合わせた改良型ホタルを提案する。
  論文  参考訳（メタデータ） (2023-02-09T18:43:10Z)
• Regularization and Optimization in Model-Based Clustering [4.096453902709292]
  k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。 一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。 これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
  論文  参考訳（メタデータ） (2023-02-05T18:22:29Z)
• Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering [1.0589208420411012]
  本稿では,クラスタ融合と高効率更新方式を用いた反復アルゴリズムCCMMによる凸クラスタリングを提案する。 現在のデスクトップコンピュータでは、CCMMは、7次元空間に100万以上のオブジェクトを含む凸クラスタリング問題を効率的に解決する。
  論文  参考訳（メタデータ） (2022-11-03T15:07:51Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Certifying clusters from sum-of-norms clustering [13.747619681451875]
  本稿では,近似解から正しいクラスタ割り当てを同定し,証明するクラスタリングテストを提案する。 提案手法では, クラスタ割り当てが, 十分に多くの繰り返しを経て, 原始二重経路追従アルゴリズムによって保証されることが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-06-19T20:26:26Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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