論文の概要: Characterizations of Admissible Objective Functions for Hierarchical Clustering

• arxiv url: http://arxiv.org/abs/2604.23628v1
• Date: Sun, 26 Apr 2026 09:44:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:07.470008
• Title: Characterizations of Admissible Objective Functions for Hierarchical Clustering
• Title（参考訳）: 階層クラスタリングのための許容対象関数の特性評価
• Authors: Ryuki Tsukuba, Kazutoshi Ando,
• Abstract要約: 階層クラスタリングのための新たな目的関数のクラスを導入し、クラスタ間相互作用を集約的類似性ではなく、最大で測定する。 これらの結果は階層的クラスタリングに関する新たな理論的洞察を与え、最適化のためのアルゴリズム保証の範囲を明確にする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical clustering is a fundamental task in data analysis, yet for a long time it lacked a principled objective function. Dasgupta [STOC 2016] initiated a formal framework by introducing a discrete objective function for cluster trees. This framework was subsequently expanded by Cohen-Addad et al. [J. ACM 2019], who introduced the notion of admissibility -- a criterion ensuring that, whenever the input similarities admit consistent hierarchical representations, the minimizers of an objective function recover them. They also provided a necessary and sufficient condition for admissibility within a broad class of objective functions, which we refer to as sum-type objective functions. Our contributions are twofold. First, we characterize admissible sum-type objective functions when the scaling function g is a symmetric polynomial of degree at most two, together with sufficient conditions in the degree-three case. For admissible objective functions in this class, we show that the recursive sparsest cut algorithm achieves an O($φ$)-approximation ratio, where $φ$ denotes the approximation factor of the sparsest cut subroutine. Second, we introduce a new class of objective functions for hierarchical clustering, which we term max-type objective functions, where cluster interactions are measured by maximum rather than aggregate similarity. For this class, we establish a general characterization of admissibility for arbitrary scaling functions g, and a complete characterization when g is a symmetric polynomial of degree at most two. These results provide new theoretical insights into admissible objective functions for hierarchical clustering and clarify the scope of algorithmic guarantees for optimizing them.
• Abstract（参考訳）: 階層的クラスタリングは、データ分析の基本的なタスクであるが、長い間、原則化された目的関数が欠如していた。 Dasgupta氏(STOC 2016)は、クラスタツリーに個別の客観的関数を導入することで、正式なフレームワークを開始した。 このフレームワークはその後、Cohen-Addad氏らによって拡張され(J. ACM 2019)、アクセシビリティの概念が導入された。 また、幅広い目的関数のクラスにおいて、必要十分かつ十分な許容条件を与え、これを和型目的関数(sum-type objective function)と呼ぶ。 私たちの貢献は2倍です。 まず、スケーリング関数 g が次数 2 の対称多項式であるときの許容和型目的関数と次数 3 の場合の十分条件を特徴付ける。 このクラスにおける許容対象関数に対して、再帰的スペルサストカットアルゴリズムはO($φ$)-近似比を達成し、$φ$はスペルサストカットサブルーチンの近似係数を表す。 第2に,階層的クラスタリングのための新たな目的関数のクラスを導入する。これは,クラスタ間相互作用を集約的類似性ではなく,最大値で測定する,最大値型客観関数(max-type objective function)と呼ぶ。 このクラスに対して、任意のスケーリング関数 g に対する許容性の一般的なキャラクタリゼーションと、g が次数 2 の対称多項式であるときの完全なキャラクタリゼーションを確立する。 これらの結果は階層的クラスタリングのための許容対象関数に関する新たな理論的洞察を与え、それらを最適化するためのアルゴリズム保証の範囲を明確にする。

関連論文リスト

• Universal NP-Hardness of Clustering under General Utilities [11.62669179647184]
  有限距離空間上の多変数時間計算可能分割ユーティリティを動機付ける共通最適化コアを定式化する。 k-means、GMMs、DBSCAN、スペクトルクラスタリング、親和性伝播を含む10の主要なパラダイムをUPPフレームワークにマッピングすることで、それぞれのパラダイムがこの基本的障害を継承することを示した。
  論文  参考訳（メタデータ） (2026-02-27T13:08:15Z)
• Convergence of a class of gradient-free optimisation schemes when the objective function is noisy, irregular, or both [4.258175645355975]
  本研究では,非滑らかで雑音の多い目的関数を最小化するために設計されたアルゴリズムのクラスについて検討する。 収束結果は、目的関数の正則性に関する非常に弱い仮定の下で得られる。 機械学習の難解な分類例を通して,これらのアルゴリズムと収束結果との関連について述べる。
  論文  参考訳（メタデータ） (2025-12-02T21:05:41Z)
• Interpetable Target-Feature Aggregation for Multi-Task Learning based on Bias-Variance Analysis [53.38518232934096]
  マルチタスク学習(MTL)は、タスク間の共有知識を活用し、一般化とパフォーマンスを改善するために設計された強力な機械学習パラダイムである。 本稿では,タスククラスタリングと特徴変換の交点におけるMTL手法を提案する。 両段階において、鍵となる側面は減った目標と特徴の解釈可能性を維持することである。
  論文  参考訳（メタデータ） (2024-06-12T08:30:16Z)
• 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)
• An Algorithm and Complexity Results for Causal Unit Selection [16.307996243413967]
  単位選択問題は、刺激を受ける際に望ましい振る舞いを示す可能性が最も高い、単位と呼ばれる物体を特定することを目的としている。 本稿では,幅広い因果的目的関数のクラスと完全に定義された構造因果的モデルに与えられた最適単位を求めるための,最初の正確なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-28T08:46:51Z)
• Expanding the class of global objective functions for dissimilarity-based hierarchical clustering [0.0]
  先行研究で研究された望ましい特性を満足する目的関数の幅広いクラスを導入する。 多くの一般的な集合的および分割的クラスタリング法は、これらの目的に対して欲求的なアルゴリズムであることが示されている。
  論文  参考訳（メタデータ） (2022-07-28T20:50:43Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• An objective function for order preserving hierarchical clustering [0.0]
  確率的部分順序の類似性に基づく階層的クラスタリングの理論と目的関数を提案する。 具体的には、元 $x le y$ が部分順序で与えられ、それぞれのクラスタ $[x]$ と $[y]$ が与えられたとき、その理論はクラスタ上で $[x]le'[y]$ となるような順序関係 $le'$ が得られる。
  論文  参考訳（メタデータ） (2021-09-09T13:35:01Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

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

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