論文の概要: Global Optimization for Cardinality-constrained Minimum Sum-of-Squares
Clustering via Semidefinite Programming
- arxiv url: http://arxiv.org/abs/2209.08901v3
- Date: Thu, 7 Sep 2023 16:12:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-08 18:07:51.482431
- Title: Global Optimization for Cardinality-constrained Minimum Sum-of-Squares
Clustering via Semidefinite Programming
- Title（参考訳）: 半有限計画法による最小二乗極小クラスタリングのグローバル最適化
- Authors: Veronica Piccialli, Antonio M. Sudoso
- Abstract要約: 最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。
本稿では,分枝切断法に基づく大域的最適化手法を提案する。
上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
- 参考スコア（独自算出の注目度）: 1.3053649021965603
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimum sum-of-squares clustering (MSSC), or k-means type clustering, has
been recently extended to exploit prior knowledge on the cardinality of each
cluster. Such knowledge is used to increase performance as well as solution
quality. In this paper, we propose a global optimization approach based on the
branch-and-cut technique to solve the cardinality-constrained MSSC. For the
lower bound routine, we use the semidefinite programming (SDP) relaxation
recently proposed by Rujeerapaiboon et al. [SIAM J. Optim. 29(2), 1211-1239,
(2019)]. However, this relaxation can be used in a branch-and-cut method only
for small-size instances. Therefore, we derive a new SDP relaxation that scales
better with the instance size and the number of clusters. In both cases, we
strengthen the bound by adding polyhedral cuts. Benefiting from a tailored
branching strategy which enforces pairwise constraints, we reduce the
complexity of the problems arising in the children nodes. For the upper bound,
instead, we present a local search procedure that exploits the solution of the
SDP relaxation solved at each node. Computational results show that the
proposed algorithm globally solves, for the first time, real-world instances of
size 10 times larger than those solved by state-of-the-art exact methods.
- Abstract（参考訳）: 最小二乗クラスタリング(MSSC)あるいはk平均型クラスタリング(k平均型クラスタリング)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。
このような知識は、ソリューションの品質だけでなく、パフォーマンスを向上させるためにも使われます。
本稿では,分枝切断法に基づく大域的最適化手法を提案する。
下界ルーチンに対しては、最近Rujeerapaiboonらによって提案された半定値プログラミング(SDP)緩和を用いる。
[SIAM J. Optim. 29(2), 1211-1239, (2019)]
しかし、この緩和は小規模インスタンスのみにブランチ・アンド・カット法で使用できる。
そこで,本研究では,インスタンスサイズやクラスタ数に応じて拡張可能な新しいSDP緩和法を提案する。
いずれの場合も多面体切断を加えることで境界を強化する。
相互に制約を課す分枝戦略に適合して、子どものノードに生じる問題の複雑さを軽減します。
上界に対しては,各ノードで解いたSDP緩和解を利用した局所探索手法を提案する。
計算結果によると,提案アルゴリズムは,最先端の正確な手法で解かれたものよりも10倍の大きさの実世界のインスタンスを,初めてグローバルに解いた。
関連論文リスト
- A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering [0.30693357740321775]
最小2乗クラスタリング問題(MSSC)は、$n$のデータポイントを$k$クラスタに分割する問題を指す。
カラム生成(CG)と動的制約集約(DCA)を組み合わせた大規模MSSCインスタンスの効率的な解法を提案する。
論文 参考訳（メタデータ） (2024-10-08T16:51:28Z) - 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) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - 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) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Clustering with Penalty for Joint Occurrence of Objects: Computational
Aspects [0.0]
Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。
この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。
本稿では,本手法の計算的側面について考察する。
論文 参考訳（メタデータ） (2021-02-02T10:39:27Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。
最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。
本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
論文 参考訳（メタデータ） (2020-06-22T20:02:59Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。