論文の概要: Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics

• arxiv url: http://arxiv.org/abs/2511.18056v1
• Date: Sat, 22 Nov 2025 13:20:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.605571
• Title: Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics
• Title（参考訳）: 二分木と超音波による階層的リンククラスタリング
• Authors: Maximilien Dreveton, Matthias Grossglauser, Daichi Kuroda, Patrick Thiran,
• Abstract要約: 本稿では,有効階層の概念を導入し,有効階層の集合上の部分順序を定義する。 我々は、データセットの類似性構造と一致した最大情報を符号化する最も有効な階層、すなわち階層の存在を証明した。 本稿では,まず二分木をリンク方式で構築し,その二分木に有効性を持たせるための単純な2ステップアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 11.198418635553976
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hierarchical clustering seeks to uncover nested structures in data by constructing a tree of clusters, where deeper levels reveal finer-grained relationships. Traditional methods, including linkage approaches, face three major limitations: (i) they always return a hierarchy, even if none exists, (ii) they are restricted to binary trees, even if the true hierarchy is non-binary, and (iii) they are highly sensitive to the choice of linkage function. In this paper, we address these issues by introducing the notion of a valid hierarchy and defining a partial order over the set of valid hierarchies. We prove the existence of a finest valid hierarchy, that is, the hierarchy that encodes the maximum information consistent with the similarity structure of the data set. In particular, the finest valid hierarchy is not constrained to binary structures and, when no hierarchical relationships exist, collapses to a star tree. We propose a simple two-step algorithm that first constructs a binary tree via a linkage method and then prunes it to enforce validity. We establish necessary and sufficient conditions on the linkage function under which this procedure exactly recovers the finest valid hierarchy, and we show that all linkage functions satisfying these conditions yield the same hierarchy after pruning. Notably, classical linkage rules such as single, complete, and average satisfy these conditions, whereas Ward's linkage fails to do so.
• Abstract（参考訳）: 階層的クラスタリングは、より深いレベルがよりきめ細かな関係を明らかにするクラスタのツリーを構築することによって、データのネスト構造を解明しようとする。 リンクアプローチを含む従来の手法は、以下の3つの大きな制限に直面している。 (i) たとえ存在しないとしても、常に階層を返します。 (ii)真の階層が非バイナリであっても、二分木に制限され、 (三)リンク機能の選択に非常に敏感である。 本稿では、有効な階層の概念を導入し、有効な階層の集合上で部分的な順序を定義することにより、これらの問題に対処する。 我々は、データセットの類似性構造と一致した最大情報を符号化する最も有効な階層、すなわち階層の存在を証明した。 特に、最も有効な階層は二項構造に制約されず、階層的な関係が存在しない場合には、星木に崩壊する。 本稿では,まず二分木をリンク方式で構築し,その二分木に有効性を持たせるための単純な2ステップアルゴリズムを提案する。 我々は,この手順がもっとも有効な階層を正確に復元する連鎖関数の必要十分条件を確立し,これらの条件を満たすすべてのリンク関数が,プルーニング後に同じ階層を生成することを示す。 特に、単一、完全、平均のような古典的な連鎖規則はこれらの条件を満たすが、ウォードの連鎖はそのような条件を満たさない。

関連論文リスト

• Hierarchical Transformers for Unsupervised 3D Shape Abstraction [29.488408094629545]
  我々は3次元形状のための新しい階層型ニューラルフィールド表現であるHiTを紹介する。 HiTは、教師なしの環境で、異なる形状のカテゴリにわたって粗い方法で一般的な階層を学習する。 55のShapeNetカテゴリにまたがる非教師なし形状分割タスクにより,その効果を実証する。
  論文  参考訳（メタデータ） (2025-10-31T01:19:05Z)
• The Geometry of Meaning: Perfect Spacetime Representations of Hierarchical Structures [0.0]
  3次元ミンコフスキー時空に階層構造を埋め込む高速アルゴリズムが存在することを示す。 我々の結果は、すべての離散データが3次元の完全な幾何学的表現を持っていることを示唆しているように思われる。
  論文  参考訳（メタデータ） (2025-05-07T20:41:06Z)
• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  そこで本研究では,様々なレベルで参照文書を整理し,表現するためのツリーベース手法を提案する。 我々の手法はReTreeverと呼ばれ、クエリと参照ドキュメントが同様のツリーブランチに割り当てられるように、バイナリツリーの内部ノード毎のルーティング関数を共同で学習する。 我々の評価では、ReTreeverは一般的に完全な表現精度を保っている。
  論文  参考訳（メタデータ） (2025-02-11T21:35:13Z)
• Integrating Hierarchical Semantic into Iterative Generation Model for Entailment Tree Explanation [7.5496857647335585]
  本稿では,HiSCG (Controller-Generator) の枠組みに基づいて文の階層的意味論を統合するアーキテクチャを提案する。 提案手法はEntailmentBankデータセットの3つの設定で同等のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2024-09-26T11:46:58Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Use All The Labels: A Hierarchical Multi-Label Contrastive Learning Framework [75.79736930414715]
  本稿では,すべての利用可能なラベルを活用でき,クラス間の階層的関係を維持できる階層型多言語表現学習フレームワークを提案する。 比較損失に階層的ペナルティを併用し,その階層的制約を強制する。
  論文  参考訳（メタデータ） (2022-04-27T21:41:44Z)
• Modeling Heterogeneous Hierarchies with Relation-specific Hyperbolic Cones [64.75766944882389]
  知識グラフにおける複数の階層的および非階層的関係を同時にモデル化できるKG埋め込みモデルであるConE(Cone Embedding)を提案する。 特に、ConEは双曲埋め込み空間の異なる部分空間における円錐包含制約を用いて、複数の異種階層をキャプチャする。 我々のアプローチでは、WN18RRで45.3%、DDB14で16.1%の新しい最先端hits@1が得られる(0.231 MRR)。
  論文  参考訳（メタデータ） (2021-10-28T07:16:08Z)
• Inducing a hierarchy for multi-class classification problems [11.58041597483471]
  分類的ラベルが自然な階層に従ったアプリケーションでは、ラベル構造を利用する分類方法は、そうでないものをしばしば上回る。 本稿では,フラット分類器に対する分類性能を向上できる階層構造を誘導する手法のクラスについて検討する。 原理シミュレーションと3つの実データアプリケーションにおいて、潜入階層の発見と精度向上のためのメソッドのクラスの有効性を実証する。
  論文  参考訳（メタデータ） (2021-02-20T05:40:42Z)
• Hierarchical community structure in networks [1.9981375888949475]
  本稿では,ネットワークにおける階層的コミュニティ構造に関する理論的研究を行う。 1) コミュニティ階層をどのように定義すべきか 2) ネットワークに階層構造の十分な証拠があるかどうかをどうやって判断するか?
  論文  参考訳（メタデータ） (2020-09-15T16:18:26Z)

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

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