論文の概要: Universal NP-Hardness of Clustering under General Utilities

• arxiv url: http://arxiv.org/abs/2603.00210v1
• Date: Fri, 27 Feb 2026 13:08:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-03 19:50:56.112018
• Title: Universal NP-Hardness of Clustering under General Utilities
• Title（参考訳）: 一般用途におけるクラスタリングの普遍的NP-Hardness
• Authors: Angshul Majumdar,
• Abstract要約: 有限距離空間上の多変数時間計算可能分割ユーティリティを動機付ける共通最適化コアを定式化する。 k-means、GMMs、DBSCAN、スペクトルクラスタリング、親和性伝播を含む10の主要なパラダイムをUPPフレームワークにマッピングすることで、それぞれのパラダイムがこの基本的障害を継承することを示した。
• 参考スコア（独自算出の注目度）: 11.62669179647184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.
• Abstract（参考訳）: クラスタリングは教師なし学習において中心的な原始的であるが、実際は、出力が不安定で表現、ハイパーパラメータ、初期化に非常に敏感なヒューリスティックに支配されている。 既存の理論的結果は、主に客観的なものであり、これらの振る舞いを統一レベルでは説明しない。 普遍クラスタリング問題(UCP:Universal Clustering Problem)を定義することにより、共通最適化コアを定式化し、有限距離空間上の多項式時間計算可能分割ユーティリティの最大化を行う。 グラフカラー化による2つの独立した多項式時間削減と3つの集合による正確な被覆(X3C)によるUPPのNP硬度を証明した。 k-means、GMMs、DBSCAN、スペクトルクラスタリング、親和性伝播を含む10の主要なパラダイムをUPPフレームワークにマッピングすることで、それぞれのパラダイムがこの基本的な難易度を継承することを示した。 この結果から, 局所的最適化法や階層クラスタリングにおけるグリージーなマージオーダトラップなど, 特性的障害モードの統一的な説明が得られた。 最後に、クラスタリングの制約は、相互作用する計算的制約とてんかん性制約を反映し、安定性を意識した目的へのシフトと、明示的な保証を伴う相互作用駆動型定式化を動機付けていることを示す。

関連論文リスト

• Deep Incomplete Multi-View Clustering via Hierarchical Imputation and Alignment [15.396375506151102]
  本稿では,階層的な命令処理と4つのキーコンポーネントのアライメントを統合する,新しいディープIMVCフレームワークを提案する。 ベンチマーク実験により、我々のフレームワークは、様々なレベルの欠落下で優れたパフォーマンスを達成することが示された。
  論文  参考訳（メタデータ） (2026-01-14T00:46:00Z)
• Optimal Graph Clustering without Edge Density Signals [11.198418635553976]
  本稿では,Popularity-Adjusted Block Model(PABM)に基づくグラフクラスタリングの理論的限界を確立する。 本研究の主な貢献は,PABMによるクラスタリングにおける最適誤差率の評価である。 合成データセットと実データセットの両方に関する数値実験により、$k2$固有ベクトルを組み込んだスペクトルクラスタリングアルゴリズムが従来のスペクトルアプローチより優れていることを確認した。
  論文  参考訳（メタデータ） (2025-10-24T17:24:26Z)
• Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective [52.662463893268225]
  自己教師付きヘテロジニアスグラフ学習(SHGL)は様々なシナリオにおいて有望な可能性を示している。 既存のSHGLメソッドには2つの大きな制限がある。 ランクと二重整合性制約によって強化された新しいフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-12-01T09:33:20Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Memetic Differential Evolution Methods for Semi-Supervised Clustering [0.8681835475119588]
  MDEClustの半教師付き最小二乗クラスタリング(MSSC)問題に対する拡張を提案する。 我々の新しいフレームワークであるS-MDEClustは、最適な実現可能なソリューションを生成するために設計された最初のメメカティックな方法論である。
  論文  参考訳（メタデータ） (2024-03-07T08:37:36Z)
• Anchor-based Multi-view Subspace Clustering with Hierarchical Feature Descent [46.86939432189035]
  階層的特徴Descentを用いたアンカーベースマルチビューサブスペースクラスタリングを提案する。 提案手法は最先端技術より一貫して優れている。
  論文  参考訳（メタデータ） (2023-10-11T03:29:13Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  半負のテンソル因子分解(Semi-NTF)に基づく新しいマルチビュークラスタリングを開発する。 本モデルは、ビュー間の関係を直接考慮し、ビュー間の補完情報を利用する。 さらに,提案手法の最適化アルゴリズムを提案し,そのアルゴリズムが常に定常KKT点に収束することを数学的に証明する。
  論文  参考訳（メタデータ） (2023-03-29T14:54:19Z)
• Simple and Scalable Algorithms for Cluster-Aware Precision Medicine [0.0]
  共同クラスタリングと埋め込みに対するシンプルでスケーラブルなアプローチを提案する。 この新しいクラスタ対応の埋め込みアプローチは、現在の共同埋め込みとクラスタリング法の複雑さと限界を克服する。 当社のアプローチでは,ユーザが希望するクラスタ数を選択する必要はなく,階層的にクラスタ化された埋め込みの解釈可能なデンドログラムを生成する。
  論文  参考訳（メタデータ） (2022-11-29T19:27:26Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。 このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。 このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
  論文  参考訳（メタデータ） (2022-09-27T19:04:36Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。 本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
  論文  参考訳（メタデータ） (2022-05-17T01:41:06Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

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

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