論文の概要: A Scalable Global Optimization Algorithm For Constrained Clustering

• arxiv url: http://arxiv.org/abs/2510.22519v1
• Date: Sun, 26 Oct 2025 04:01:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 19:54:32.52749
• Title: A Scalable Global Optimization Algorithm For Constrained Clustering
• Title（参考訳）: 制約クラスタリングのためのスケーラブルなグローバル最適化アルゴリズム
• Authors: Pedro Chumpitaz-Flores, My Duong, Cristobal Heredia, Kaixun Hua,
• Abstract要約: 制約付きクラスタリングは、クラスタリングのパフォーマンスと解釈可能性を改善するために、ペアワイズなマスタリンクと結び付きのない制約を使用する。 既存の混合整数最適化手法は小規模なデータセットに限られており、実用性は制限されている。 本稿では,必要結合されたサンプルをセントロイドベースの擬似サンプルに分解し,プルーネは幾何学的規則でリンクできない,分解可能な分岐結合フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 2.3915781021862332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constrained clustering leverages limited domain knowledge to improve clustering performance and interpretability, but incorporating pairwise must-link and cannot-link constraints is an NP-hard challenge, making global optimization intractable. Existing mixed-integer optimization methods are confined to small-scale datasets, limiting their utility. We propose Sample-Driven Constrained Group-Based Branch-and-Bound (SDC-GBB), a decomposable branch-and-bound (BB) framework that collapses must-linked samples into centroid-based pseudo-samples and prunes cannot-link through geometric rules, while preserving convergence and guaranteeing global optimality. By integrating grouped-sample Lagrangian decomposition and geometric elimination rules for efficient lower and upper bounds, the algorithm attains highly scalable pairwise k-Means constrained clustering via parallelism. Experimental results show that our approach handles datasets with 200,000 samples with cannot-link constraints and 1,500,000 samples with must-link constraints, which is 200 - 1500 times larger than the current state-of-the-art under comparable constraint settings, while reaching an optimality gap of less than 3%. In providing deterministic global guarantees, our method also avoids the search failures that off-the-shelf heuristics often encounter on large datasets.
• Abstract（参考訳）: 制約付きクラスタリングは、限られたドメイン知識を活用してクラスタリング性能と解釈可能性を向上させるが、ペアワイズなマスタリンクとナントリンクの制約を組み込むことはNPの難題であり、グローバルな最適化は難解である。 既存の混合整数最適化手法は小規模なデータセットに限られており、実用性は制限されている。 SDC-GBB(Sample-Driven Constrained Group-Based Branch-and-Bound)は,有意なサンプルをセントロイドベースの擬似サンプルやプルーネに分解し,収束を保ち,大域的最適性を保証する。 グループ化されたサンプルラグランジアン分解と、効率的な下界と上界の幾何学的除去規則を統合することにより、アルゴリズムは並列性を通じて高度にスケーラブルなk-Means制約付きクラスタリングを実現する。 実験結果から,提案手法は無リンク制約付き20,000サンプルとマスタリンク制約付き1,500,000サンプルのデータセットを扱えることがわかった。 決定論的大域的保証を提供することで、本手法は、既成のヒューリスティックが大規模なデータセットでよく遭遇する探索失敗を回避する。

関連論文リスト

• Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
  コクラスタリング(co-clustering)または双方向クラスタリング( two-way clustering)とも呼ばれるビクラスタリングは、データマトリックスの行と列を同時にパーティショニングすることで、コヒーレントパターンによるサブマトリクスを明らかにする。 我々は、オブジェクトが同一または異なるビクラスタに属するべきか否かを規定する制約付きビクラスタリング、すなわち、マスタリンクとナントリンクの制約について研究する。
  論文  参考訳（メタデータ） (2025-08-07T15:29:22Z)
• Graph Probability Aggregation Clustering [5.377020739388736]
  本稿では,グローバルクラスタリング対象関数と局所クラスタリング制約を統一するグラフベースのファジィクラスタリングアルゴリズムを提案する。 GPACフレームワーク全体は多制約最適化問題として定式化され、ラグランジアン法を用いて解くことができる。 合成,実世界,ディープラーニングのデータセットを用いて行った実験は,GPACがクラスタリング性能において既存の最先端手法を超えるだけでなく,計算効率も優れていることを示した。
  論文  参考訳（メタデータ） (2025-02-27T09:11:32Z)
• Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
  大規模未ラベルデータから学ぶための2つの戦略を提案する。 第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。 第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
  論文  参考訳（メタデータ） (2023-07-26T16:19:19Z)
• A Global Optimization Algorithm for K-Center Clustering of One Billion Samples [12.120865465650867]
  本稿では,K中心クラスタリング問題に対する実用的なグローバル最適化アルゴリズムを提案する。 クラスタ内の最大距離を最小化するために、クラスタの中心としてKサンプルを選択することを目的としている。 我々のアルゴリズムは、合成および実世界の全てのデータセットにおいて、目的関数を平均25.8%削減することができる。
  論文  参考訳（メタデータ） (2022-12-30T21:53:08Z)
• 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)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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