論文の概要: An Information-theoretic Perspective of Hierarchical Clustering
- arxiv url: http://arxiv.org/abs/2108.06036v1
- Date: Fri, 13 Aug 2021 03:03:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-16 20:34:07.299336
- Title: An Information-theoretic Perspective of Hierarchical Clustering
- Title（参考訳）: 階層的クラスタリングの情報理論的展望
- Authors: Yicheng Pan, Feng Zheng, Bingchen Fan
- Abstract要約: 階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。
本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
- 参考スコア（独自算出の注目度）: 30.896561720088954
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A combinatorial cost function for hierarchical clustering was introduced by
Dasgupta \cite{dasgupta2016cost}. It has been generalized by Cohen-Addad et al.
\cite{cohen2019hierarchical} to a general form named admissible function. In
this paper, we investigate hierarchical clustering from the
\emph{information-theoretic} perspective and formulate a new objective
function. We also establish the relationship between these two perspectives. In
algorithmic aspect, we get rid of the traditional top-down and bottom-up
frameworks, and propose a new one to stratify the \emph{sparsest} level of a
cluster tree recursively in guide with our objective function. For practical
use, our resulting cluster tree is not binary. Our algorithm called HCSE
outputs a $k$-level cluster tree by a novel and interpretable mechanism to
choose $k$ automatically without any hyper-parameter. Our experimental results
on synthetic datasets show that HCSE has a great advantage in finding the
intrinsic number of hierarchies, and the results on real datasets show that
HCSE also achieves competitive costs over the popular algorithms LOUVAIN and
HLP.
- Abstract（参考訳）: 階層クラスタリングの組合せコスト関数はDasgupta \cite{dasgupta2016 Cost}によって導入された。
Cohen-Addadらによって一般化されている。
\cite{cohen2019hierarchical} を許容関数(admissible function)という一般形式に拡張する。
本稿では,emph{information-theoretic}の観点から階層的クラスタリングを調べ,新しい目的関数を定式化する。
これら2つの視点の関係も確立する。
アルゴリズム的な側面では、従来のトップダウンおよびボトムアップフレームワークを廃止し、目的関数をガイドして再帰的にクラスタツリーの \emph{sparsest} レベルを階層化する新しいフレームワークを提案する。
実用上、私たちのクラスタツリーはバイナリではありません。
HCSEと呼ばれるアルゴリズムは,超パラメータなしで自動的に$k$を選択する新しい機構により,$k$レベルのクラスタツリーを出力する。
合成データセットに対する実験結果から,HCSEは本質的な階層数を見つける上で大きな優位性を示し,実データを用いた結果,HCSEはアルゴリズムLOUVAINとHLPの競合コストも達成できることがわかった。
関連論文リスト
- Hierarchical Clustering via Local Search [0.0]
階層クラスタリングのための局所探索アルゴリズムを提案する。
任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
論文 参考訳（メタデータ） (2024-05-24T23:46:24Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs [7.616556723260849]
本稿では,Dasguptaのコスト関数に対する2つの効率的な階層クラスタリング(HC)アルゴリズムを提案する。
明確なクラスタ構造を持つ任意の入力グラフ$G$に対して、我々の設計したアルゴリズムは、入力サイズが$G$でほぼ直線的に実行される。
設計したアルゴリズムは、より少ない実行時間で、より優れたHCツリーを生成する。
論文 参考訳（メタデータ） (2023-06-16T16:31:46Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。
クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。
このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文 参考訳（メタデータ） (2023-05-24T11:05:12Z) - Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
階層クラスタリングのための2時間近似アルゴリズムを提案する。
本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
論文 参考訳（メタデータ） (2021-12-16T17:52:04Z) - Learning Hierarchical Graph Neural Networks for Image Clustering [81.5841862489509]
本稿では,画像の集合を未知の個数にクラスタリングする方法を学ぶ階層型グラフニューラルネットワーク(GNN)モデルを提案する。
我々の階層的なGNNは、階層の各レベルで予測される連結コンポーネントをマージして、次のレベルで新しいグラフを形成するために、新しいアプローチを用いています。
論文 参考訳（メタデータ） (2021-07-03T01:28:42Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Data Structures & Algorithms for Exact Inference in Hierarchical
Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。
我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文 参考訳（メタデータ） (2020-02-26T17:43:53Z) - Scalable Hierarchical Clustering with Tree Grafting [66.68869706310208]
Grinchは、大規模で非階層的な階層的クラスタリングと一般的なリンク関数のための新しいアルゴリズムである。
Grinchは、リンケージ関数を持つクラスタリングのための分離性という新しい概念によって動機付けられている。
論文 参考訳（メタデータ） (2019-12-31T20:56:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。