論文の概要: Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
- arxiv url: http://arxiv.org/abs/2609.11173v1
- Date: Thu, 10 Sep 2026 07:20:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.242202
- Title: Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
- Title（参考訳）: 階層的クラスタリングは、リッチネス、一貫性、スケール不変性を両立させることができる
- Abstract要約: クラインバーグのImpossibility Theoremは、平らなクラスタリング法が3つの自然な公理を同時に満たすことができないことを示している。
平らなクラスタリング環境とは対照的に、これらの公理の階層的な類似性は共同で満足できることを示す。
我々は、よく区切られたクラスタに基づくメソッドや、単一リンクの非バイナリバージョンなど、いくつかの許容可能なメソッドを明示的に構築する。
- 参考スコア（独自算出の注目度）: 11.198418635553976
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite its ubiquity, clustering lacks a universally accepted definition of what is a cluster. Kleinberg's Impossibility Theorem formalizes this difficulty by showing that no flat clustering method can simultaneously satisfy three natural axioms: scale invariance, richness, and consistency. In this paper, we ask whether this impossibility persists when the output is a hierarchy rather than a single partition. We show that, in contrast to the flat clustering setting, the hierarchical analog of these axioms are jointly satisfiable. In fact, there exist uncountably many hierarchical clustering methods satisfying these axioms, which we call admissible. We explicitly construct several admissible methods, including methods based on well-separated clusters and a non-binary version of single linkage. For certain pairs of admissible methods, the hierarchy produced by one always refines that produced by the other. This refinement relation defines a partial order on the class of admissible methods. This partially ordered set has no greatest element and contains uncountably many pairwise incompatible maximal elements, revealing substantial diversity among admissible methods. Nevertheless, this diversity is constrained: every admissible method contains a hierarchy of sufficiently well-separated clusters, and every finite collection of admissible methods shares such a nontrivial common backbone.
- Abstract（参考訳）: その普遍性にもかかわらず、クラスタリングはクラスタとは何かという普遍的に受け入れられる定義を欠いている。
クラインバーグの不合理性定理は、平らなクラスタリング法が3つの自然な公理(スケール不変性、リッチネス、一貫性)を同時に満たすことができないことを示すことで、この難しさを公式化している。
本稿では,この不合理性が単一パーティションではなく,出力が階層構造である場合に持続するかどうかを問う。
平らなクラスタリング環境とは対照的に、これらの公理の階層的な類似性は共同で満足できることを示す。
実際、これらの公理を満たす階層的クラスタリング法が無数に存在する。
我々は、よく区切られたクラスタに基づくメソッドや、単一リンクの非バイナリバージョンなど、いくつかの許容可能なメソッドを明示的に構築する。
ある許容可能なメソッドのペアに対して、一方が生成する階層は常に他方が生成する階層を洗練させる。
この精製関係は許容可能なメソッドのクラスの部分順序を定義する。
この部分順序集合は極大元を持たず、可許容な方法の間でかなりの多様性を示す、対数的に非互換な極大元を無数に含んでいる。
しかしながら、この多様性は制約されている: すべての許容メソッドは十分に分離されたクラスタの階層を含み、任意の許容メソッドの有限コレクションはそのような非自明な共通バックボーンを共有する。
関連論文リスト
- Weight-Informed Self-Explaining Clustering for Mixed-Type Tabular Data [63.62853416081748]
WISEは表現、特徴重み付け、クラスタリング、解釈を統一するフレームワークである。
クラスタリングを駆動する同じプリミティブに根ざした、忠実で人間解釈可能な説明を生成する。
論文 参考訳（メタデータ） (2026-04-07T13:18:31Z) - Universal NP-Hardness of Clustering under General Utilities [11.62669179647184]
有限距離空間上の多変数時間計算可能分割ユーティリティを動機付ける共通最適化コアを定式化する。
k-means、GMMs、DBSCAN、スペクトルクラスタリング、親和性伝播を含む10の主要なパラダイムをUPPフレームワークにマッピングすることで、それぞれのパラダイムがこの基本的障害を継承することを示した。
論文 参考訳（メタデータ） (2026-02-27T13:08:15Z) - Topological Mixed States: Phases of Matter from Axiomatic Approaches [15.433292838001103]
閉量子系において、位相的順序は、ギャップ付き局所ハミルトニアンの基底状態の同値類を通して理解される。
ここでは、局所的回復可能性(i$)、長距離相関の欠如(ii$)、空間的均一性(iii$)という3つの公理に基づくアプローチを提案することにより、このギャップを埋める。
これらの公理から、トポロジカルデータの豊富な集合が自然に出現し、重要なことは、これらのデータは公理の緩和の下で堅牢である。
論文 参考訳（メタデータ） (2025-06-04T17:58:45Z) - Unextendibility, uncompletability, and many-copy indistinguishable ensembles [49.1574468325115]
任意の二分的純絡み合った状態の補集合は、最大濃度の非直交的拡張不可能な積基底(nUPB)を形成する積状態によって分散されることを示す。
また,混合状態の減少に伴い局所的不識別性が増大する多部構成多部構成不識別アンサンブルのクラスについても報告する。
論文 参考訳（メタデータ） (2023-03-30T16:16:41Z) - Rethinking Clustering-Based Pseudo-Labeling for Unsupervised
Meta-Learning [146.11600461034746]
教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。
このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。
このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
論文 参考訳（メタデータ） (2022-09-27T19:04:36Z) - Asymptotic Theory of Geometric and Adaptive $k$-Means Clustering [0.0]
我々は、ユークリッド空間における$k$-meansクラスタリングの一貫性に関するポラードの古典的な結果を再考する。
上に述べたすべてのクラスタリング手順が強く整合していることが示される。
論文 参考訳（メタデータ） (2022-02-27T18:56:41Z) - Towards Continuous Consistency Axiom [0.0]
機械学習分野、特にクラスタリングにおける新しいアルゴリズムの開発には、ラベル付きデータセットの可用性が必要である。
我々は、クラインバーグの内部整合公理を中心的整合公理に置き換える別の公理系を提案する。
我々は、新しいシステムが、自動調整された$k$を持つ$k$-meansの階層的なバージョンに適合していることを示し、矛盾しない。
論文 参考訳（メタデータ） (2022-02-12T08:25:01Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Local indistinguishability and incompleteness of entangled orthogonal
bases: Method to generate two-element locally indistinguishable ensembles [0.0]
両部量子系と多部量子系の絡み合った基底の非拡張性と非可逆性の性質を持つ状態の局所的不明瞭性。
我々は,情報共有アプリケーションにつながる可能性のある,拡張不可能なアンタングルベースの概念に基づいて,2要素アンサンブルを構築する方法を特定する。
論文 参考訳（メタデータ） (2020-08-04T15:04:27Z) - 3D Correspondence Grouping with Compatibility Features [51.869670613445685]
本稿では,3次元対応グルーピングのための簡易かつ効果的な手法を提案する。
目的は、局所幾何学的記述子を不整合と外接点にマッチングすることによって得られる初期対応を正確に分類することである。
本稿では,不整合と不整合を表わすために,互換性特徴(CF)と呼ばれる3次元対応の表現を提案する。
論文 参考訳（メタデータ） (2020-07-21T02:39:48Z) - Revealing consensus and dissensus between network partitions [0.0]
コミュニティ検出手法は、ネットワークを同様の特性を持つノードのグループに分割し、その大規模構造を明らかにする。
分布全体を要約する単一分割「ポイント推定」という形で、それらの間のコンセンサスを確立するための多くの方法が存在する。
ここでは、一般に、基底分布が不均一すぎるとき、そのような点から一貫した答えを得ることはできないことを示す。
我々は,分割の複雑な集団を,既存のコンセンサスだけでなく,人口の要素間の不一致を捉える方法で特徴付け,要約するために設計された,包括的手法のセットを提供する。
論文 参考訳（メタデータ） (2020-05-28T13:29:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。