論文の概要: Tangles and Hierarchical Clustering

• arxiv url: http://arxiv.org/abs/2203.08731v1
• Date: Wed, 16 Mar 2022 16:23:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-17 15:22:04.157019
• Title: Tangles and Hierarchical Clustering
• Title（参考訳）: 絡み合いと階層的クラスタリング
• Authors: Eva Fluck
• Abstract要約: 三角形と階層分解を連結する中心双対定理は、部分モジュラリティが最大部分モジュラリティと呼ばれる別の性質に置き換わるときに成立することを示す。 階層的クラスタリング結果を表すデータ構造であるデンドグラムは,最大部分モジュラ接続関数とその三角形と等価であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour's graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe. In typical clustering applications these universes consist of points in some metric space. Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular. We then define a connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set. Lastly we generalize this correspondence for any hierarchical clustering. We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles. The idea of viewing tangles as clusters has first been proposed by Diestel and Whittle in 2016 as an approach to image segmentation. To the best of our knowledge, our result is the first that establishes a precise technical connection between tangles and clusters.
• Abstract（参考訳）: 我々は,robertson と seymour の graph minor project において中心的な役割を果たす構造グラフ理論の概念である tangles と階層的クラスタリングとの接続を確立する。 タングルはグラフに対してのみ定義することはできないが、実際にはある有限宇宙の部分集合上で定義される任意の接続函数に対して定義される。 典型的なクラスタリング応用では、これらの宇宙は計量空間内の点からなる。 接続関数は通常、サブモジュラーである必要がある。 これは、タングルと階層分解(いわゆる分岐分解)をつなぐ中心双対性定理が、部分モジュラリティが我々が極小と呼ぶ異なる性質に置き換えられる場合にも成り立つことを示す最初の貢献である。 次に、任意の距離空間における有限データセット上の接続関数を定義し、その接が、よく知られた単一リンケージクラスタリングアルゴリズムを同じデータセットに適用することによって得られるクラスタと一対一対応であることを証明する。 最後に,この対応を階層的クラスタリングに一般化する。 階層的クラスタリングの結果を表すデータ構造はデンドグラムと呼ばれ、最大サブモジュラー接続関数とその絡み合いと等価であることを示す。 トライアングルをクラスタとして見るというアイデアは、2016年にDiestelとWhittleによって画像セグメンテーションのアプローチとして初めて提案された。 私たちの知る限りでは、私たちの結果は、タングルとクラスタ間の正確な技術的接続を確立する最初のものです。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Contrastive Hierarchical Clustering [8.068701201341065]
  CoHiClustは、ディープニューラルネットワークに基づくContrastive Hierarchical Clusteringモデルである。 自己教師付き学習アプローチを採用することで、CoHiClustは、ラベル付きデータにアクセスせずに、ベースネットワークをバイナリツリーに蒸留する。
  論文  参考訳（メタデータ） (2023-03-03T07:54:19Z)
• flow-based clustering and spectral clustering: a comparison [0.688204255655161]
  本研究では,本質的なネットワーク構造を持つデータに対する新しいグラフクラスタリング手法を提案する。 我々は、ユークリッド特徴ベクトルを構築するために、データ固有のネットワーク構造を利用する。 以上の結果から,クラスタリング手法が特定のグラフ構造に対処できることが示唆された。
  論文  参考訳（メタデータ） (2022-06-20T21:49:52Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees [10.992467680364962]
  本稿では,機械学習応用におけるトライアングルの実用可能性を示す。 任意のデータセットのカットの集合が与えられたとき、トライアングルはこれらのカットを密集構造の方向を指し示すために集約する。 タングルを用いたクラスタリングのためのアルゴリズムフレームワークを構築し、様々な設定で理論的保証を証明し、広範囲なシミュレーションとユースケースを提供する。
  論文  参考訳（メタデータ） (2020-06-25T14:23:56Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  カーネル重み付けの観点からノード集約を再解釈する。 本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。 特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
  論文  参考訳（メタデータ） (2020-05-16T04:44:29Z)
• Order preserving hierarchical agglomerative clustering [0.0]
  このような順序データの階層的クラスタリングを順序保存する問題について検討する。 クラスタリングは類似性に基づいており、シングルリンケージや完全リンケージのような標準リンケージ関数を使用する。 最適な階層的クラスタリングは、元の相似度測度に最も近い超測度に対応する部分的デンドログラムとして定義される。
  論文  参考訳（メタデータ） (2020-04-26T21:58:53Z)

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

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