論文の概要: FOSC-X: An Extended Framework for Optimal Local Cuts and Non-Horizontal Cluster Selection from Clustering Hierarchies

• arxiv url: http://arxiv.org/abs/2606.18972v1
• Date: Wed, 17 Jun 2026 11:54:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-18 17:16:51.148787
• Title: FOSC-X: An Extended Framework for Optimal Local Cuts and Non-Horizontal Cluster Selection from Clustering Hierarchies
• Title（参考訳）: FOSC-X:クラスタリング階層からの最適局所カットと非水平クラスタ選択のための拡張フレームワーク
• Authors: Connor Simpson, Ricardo J. G. B. Campello,
• Abstract要約: FOSC-Xは,階層樹の局所的,非水平的切断から,世界規模で最適なフラットクラスタリングを抽出するフレームワークである。 制約がなければ、動的プログラミングを使用してTop-M問題を時間内に解決できる。 FOSC-Xは, 単一溶液抽出法で見過ごされる代替クラスタリング構造を効率よく明らかにする。
• 参考スコア（独自算出の注目度）: 0.922437711289137
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Extracting a flat clustering solution from a hierarchy is a common task in practical cluster analysis and can be formulated as an optimisation problem. Existing approaches focus on finding a single optimal solution. We introduce FOSC-X, a framework for extracting the top-M globally optimal flat clusterings from local, non-horizontal cuts of a hierarchical cluster tree, while optionally enforcing constraints on the number of clusters. This enables automatic identification of multiple high-quality alternative clusterings that capture different aspects of the hierarchical structure. Without constraints, the top-M problem can be solved in polynomial time using dynamic programming, exploiting the property that locally optimal partial candidates within subtrees can be combined to form globally optimal solutions while automatically determining the number of clusters. However, this can lead to solutions with numbers of clusters that are ultimately undesirable -- e.g., too large to be meaningful or practically analysed within a particular application domain. Imposing cluster-count constraints breaks the optimality property underlying the unconstrained dynamic programming approach, since locally optimal partial candidates may no longer combine into feasible globally optimal solutions. FOSC-X addresses this challenge through a dynamic programming strategy that maintains compact sets of feasible candidates using lower and upper feasibility bounds while pruning infeasible or dominated combinations. The resulting method guarantees optimal rankings of the top-M solutions with linear-time complexity in the number of cluster nodes and dataset size, both with and without cluster-count constraints. Experiments show that FOSC-X efficiently reveals alternative clustering structures overlooked by single-solution extraction methods.
• Abstract（参考訳）: 階層構造から平坦なクラスタリング解を抽出することは、実際のクラスタ解析において一般的な課題であり、最適化問題として定式化することができる。 既存のアプローチでは、ひとつの最適なソリューションを見つけることに重点を置いています。 FOSC-Xは,階層的クラスタツリーの局所的,非水平的切断から,クラスタ数の制約を任意に実施しながら,グローバルに最適なフラットクラスタリングを抽出するフレームワークである。 これにより、階層構造の異なる側面をキャプチャする複数の高品質な代替クラスタリングの自動識別が可能になる。 制約がなければ、Top-M問題は動的プログラミングを用いて多項式時間で解くことができ、サブツリー内の局所最適部分的候補を結合して、クラスタ数を自動的に決定しながら、大域的最適解を形成するという特性を利用することができる。 しかし、これは最終的に望ましくない数のクラスタを持つソリューションにつながる可能性がある -- 例えば、特定のアプリケーションドメイン内で意味があり、実際に分析するには大きすぎる。 クラスタ数制約を課すことは、局所最適部分的候補がもはや可能なグローバル最適解に組み合わなくなるため、制約のない動的プログラミング手法の根底にある最適性を損なう。 FOSC-Xは、実現不可能または支配的な組み合わせを刈り上げながら、下位と上部の実現可能性境界を用いて、実現可能な候補のコンパクトなセットを維持する動的プログラミング戦略を通じて、この問題に対処する。 その結果,クラスタノード数とデータセットサイズにおいて,クラスタ数制約の有無に関わらず,線形時間で複雑なトップMソリューションの最適ランク付けが保証された。 実験により, FOSC-Xは単一溶液抽出法で見落とされた代替クラスタリング構造を効率よく明らかにした。

関連論文リスト

• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version) [50.41628860536753]
  本稿では,SCMax と呼ばれる自己教師型コンセンサス最大化による,新しい完全パラメータフリークラスタリングフレームワークを提案する。 本フレームワークは,階層的なクラスタリングとクラスタ評価を単一の統合プロセスで行う。
  論文  参考訳（メタデータ） (2025-11-12T11:17:17Z)
• Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images [51.95768218975529]
  ハイパースペクトル画像(HSI)の教師なし解析にサブスペースクラスタリングが広く採用されている。 近年のモデル対応深層空間クラスタリング手法では、O(n2)の複雑性を持つ自己表現行列の計算とスペクトルクラスタリングを含む2段階のフレームワークを用いることが多い。 本稿では,HSIクラスタリングを効率的に行うために,局所構造と非局所構造を協調的にキャプチャする,ベース表現に基づく拡張性のあるコンテキスト保存深層クラスタリング手法を提案する。
  論文  参考訳（メタデータ） (2025-06-12T16:43:09Z)
• Graph Probability Aggregation Clustering [5.377020739388736]
  本稿では,グローバルクラスタリング対象関数と局所クラスタリング制約を統一するグラフベースのファジィクラスタリングアルゴリズムを提案する。 GPACフレームワーク全体は多制約最適化問題として定式化され、ラグランジアン法を用いて解くことができる。 合成,実世界,ディープラーニングのデータセットを用いて行った実験は,GPACがクラスタリング性能において既存の最先端手法を超えるだけでなく,計算効率も優れていることを示した。
  論文  参考訳（メタデータ） (2025-02-27T09:11:32Z)
• Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
  ネットワークが与えられた場合、各ノードではなく、クラスタレベルでリソースを割り当てることによって、リソースの割り当てと使用効率が向上する。 本稿では,この制約付きクラスタリング問題を強化学習を用いて解く手法を提案する。 結果の節では,大規模インスタンスにおいても,アルゴリズムが最適に近い解を見つけることを示す。
  論文  参考訳（メタデータ） (2024-02-15T18:27:18Z)
• Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
  ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。 以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。 本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-29T21:27:21Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering [1.0589208420411012]
  本稿では,クラスタ融合と高効率更新方式を用いた反復アルゴリズムCCMMによる凸クラスタリングを提案する。 現在のデスクトップコンピュータでは、CCMMは、7次元空間に100万以上のオブジェクトを含む凸クラスタリング問題を効率的に解決する。
  論文  参考訳（メタデータ） (2022-11-03T15:07:51Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

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

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