論文の概要: Order preserving hierarchical agglomerative clustering
- arxiv url: http://arxiv.org/abs/2004.12488v3
- Date: Thu, 9 Sep 2021 13:39:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 13:10:06.761405
- Title: Order preserving hierarchical agglomerative clustering
- Title（参考訳）: 階層的凝集クラスタリングの秩序保存
- Authors: Daniel Bakkelund
- Abstract要約: このような順序データの階層的クラスタリングを順序保存する問題について検討する。
クラスタリングは類似性に基づいており、シングルリンケージや完全リンケージのような標準リンケージ関数を使用する。
最適な階層的クラスタリングは、元の相似度測度に最も近い超測度に対応する部分的デンドログラムとして定義される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partial orders and directed acyclic graphs are commonly recurring data
structures that arise naturally in numerous domains and applications and are
used to represent ordered relations between entities in the domains. Examples
are task dependencies in a project plan, transaction order in distributed
ledgers and execution sequences of tasks in computer programs, just to mention
a few. We study the problem of order preserving hierarchical clustering of this
kind of ordered data. That is, if we have $a < b$ in the original data and
denote their respective clusters by $[a]$ and $[b]$, then we shall have $[a] <
[b]$ in the produced clustering. The clustering is similarity based and uses
standard linkage functions, such as single- and complete linkage, and is an
extension of classical hierarchical clustering.
To achieve this, we define the output from running classical hierarchical
clustering on strictly ordered data to be partial dendrograms; sub-trees of
classical dendrograms with several connected components. We then construct an
embedding of partial dendrograms over a set into the family of ultrametrics
over the same set. An optimal hierarchical clustering is defined as the partial
dendrogram corresponding to the ultrametric closest to the original
dissimilarity measure, measured in the p-norm. Thus, the method is a
combination of classical hierarchical clustering and ultrametric fitting.
A reference implementation is employed for experiments on both synthetic
random data and real world data from a database of machine parts. When compared
to existing methods, the experiments show that our method excels both in
cluster quality and order preservation.
- Abstract（参考訳）: 部分順序と有向非巡回グラフは、多くのドメインやアプリケーションで自然に発生するデータ構造であり、ドメイン内のエンティティ間の順序関係を表現するために使用される。
例えば、プロジェクト計画におけるタスク依存、分散台帳におけるトランザクション順序、コンピュータプログラムにおけるタスクの実行シーケンスなどです。
このような順序データの階層的クラスタリングを順序保存する問題について検討する。
つまり、元のデータに$a < b$を持ち、それぞれのクラスタを$[a]$と$[b]$とすると、生成されたクラスタに$[a] < [b]$を持つことになる。
クラスタリングは類似性に基づいており、単一および完全リンクのような標準リンク関数を使用し、古典的な階層クラスタリングの拡張である。
これを実現するために、厳密に順序付けられたデータ上の古典的階層的クラスタリングの実行からの出力を部分的デンドログラム、いくつかの連結成分を持つ古典的デンドログラムのサブツリーとして定義する。
次に、ある集合上の部分デンドログラムの埋め込みを同じ集合上の超計量の族に構築する。
最適階層クラスタリングは、pノルムで測定された元の異種度測度に最も近い超メトリックに対応する部分デンドログラムとして定義される。
したがって、この方法は古典的階層クラスタリングとウルトラメトリックフィッティングの組み合わせである。
機械部品のデータベースから合成ランダムデータと実世界データの両方について実験を行うための参照実装を用いる。
既存の手法と比較した場合,本手法はクラスタ品質と順序保存に優れることが示された。
関連論文リスト
- Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。
クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。
このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文 参考訳（メタデータ） (2023-05-24T11:05:12Z) - Contrastive Hierarchical Clustering [8.068701201341065]
CoHiClustは、ディープニューラルネットワークに基づくContrastive Hierarchical Clusteringモデルである。
自己教師付き学習アプローチを採用することで、CoHiClustは、ラベル付きデータにアクセスせずに、ベースネットワークをバイナリツリーに蒸留する。
論文 参考訳（メタデータ） (2023-03-03T07:54:19Z) - Consistency between ordering and clustering methods for graphs [0.8594140167290096]
本稿では,複数のクラスタリングと順序付け手法の方法論的関係について検討する。
本稿では,ラベル連続度誤差と呼ばれる尺度を提案し,シーケンスとパーティション間の一貫性の度合いを一般化的に定量化する。
合成および実世界のデータセットに基づいて,オーダリング手法がモジュール構造を識別する範囲を評価する。
論文 参考訳（メタデータ） (2022-08-27T05:55:26Z) - Tangles and Hierarchical Clustering [0.0]
三角形と階層分解を連結する中心双対定理は、部分モジュラリティが最大部分モジュラリティと呼ばれる別の性質に置き換わるときに成立することを示す。
階層的クラスタリング結果を表すデータ構造であるデンドグラムは,最大部分モジュラ接続関数とその三角形と等価であることを示す。
論文 参考訳（メタデータ） (2022-03-16T16:23:48Z) - An objective function for order preserving hierarchical clustering [0.0]
このモデルは、分割階層クラスタリングのためのダスグプタコスト関数の拡張である。
最適解を見つけることはNPハードなので、相対的な性能保証が$O(log3/2n)$である時間近似を提供する。
論文 参考訳（メタデータ） (2021-09-09T13:35:01Z) - An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。
本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
論文 参考訳（メタデータ） (2021-08-13T03:03:56Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。
近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。
準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文 参考訳（メタデータ） (2020-01-06T23:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。