論文の概要: A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering

• arxiv url: http://arxiv.org/abs/2410.06187v1
• Date: Tue, 8 Oct 2024 16:51:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-01 10:41:07.290184
• Title: A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering
• Title（参考訳）: 最小2乗総和クラスタリングのための動的制約アグリゲーションを用いた列生成アルゴリズム
• Authors: Antonio M. Sudoso, Daniel Aloise,
• Abstract要約: 最小2乗クラスタリング問題(MSSC)は、$n$のデータポイントを$k$クラスタに分割する問題を指す。 カラム生成(CG)と動的制約集約(DCA)を組み合わせた大規模MSSCインスタンスの効率的な解法を提案する。
• 参考スコア（独自算出の注目度）: 0.30693357740321775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The minimum sum-of-squares clustering problem (MSSC), also known as $k$-means clustering, refers to the problem of partitioning $n$ data points into $k$ clusters, with the objective of minimizing the total sum of squared Euclidean distances between each point and the center of its assigned cluster. We propose an efficient algorithm for solving large-scale MSSC instances, which combines column generation (CG) with dynamic constraint aggregation (DCA) to effectively reduce the number of constraints considered in the CG master problem. DCA was originally conceived to reduce degeneracy in set partitioning problems by utilizing an aggregated restricted master problem obtained from a partition of the set partitioning constraints into disjoint clusters. In this work, we explore the use of DCA within a CG algorithm for MSSC exact solution. Our method is fine-tuned by a series of ablation studies on DCA design choices, and is demonstrated to significantly outperform existing state-of-the-art exact approaches available in the literature.
• Abstract（参考訳）: 最小総和クラスタリング問題(MSSC)は、$k$-meansクラスタリングとも呼ばれ、各点と割り当てられたクラスタの中心の間の2乗ユークリッド距離の総和を最小化することを目的として、$n$のデータポイントを$k$クラスタに分割する問題を指す。 本稿では,大規模MSSCインスタンスを効率よく解くアルゴリズムを提案し,カラム生成(CG)と動的制約集約(DCA)を組み合わせることにより,CGマスター問題において考慮される制約数を効果的に削減する。 DCAはもともと、設定された分割制約の分割から得られる集約された制限されたマスター問題を利用して、設定された分割問題の縮退を減らすために考案された。 そこで本研究では,MSSC の厳密解に対する CG アルゴリズムにおける DCA の利用について検討する。 提案手法は, DCA設計選択に関する一連のアブレーション研究によって微調整され, 文献上利用可能な既存の最先端のアプローチを著しく上回ることを示す。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• A3S: A General Active Clustering Method with Pairwise Constraints [66.74627463101837]
  A3Sは、適応クラスタリングアルゴリズムによって得られる初期クラスタ結果に対して、戦略的にアクティブクラスタリングを調整する。 さまざまな実世界のデータセットにわたる広範な実験において、A3Sは、人間のクエリを著しく少なくして、望ましい結果を達成する。
  論文  参考訳（メタデータ） (2024-07-14T13:37:03Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
  ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。 以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。 本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-29T21:27:21Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。 本稿では,分枝切断法に基づく大域的最適化手法を提案する。 上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
  論文  参考訳（メタデータ） (2022-09-19T10:19:06Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)

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

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