論文の概要: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering

• arxiv url: http://arxiv.org/abs/2002.11661v3
• Date: Thu, 22 Oct 2020 15:18:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 14:53:15.552836
• Title: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering
• Title（参考訳）: 階層クラスタリングにおける厳密な推論のためのデータ構造とアルゴリズム
• Authors: Craig S. Greenberg, Sebastian Macaluso, Nicholas Monath, Ji-Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, Andrew McCallum
• Abstract要約: 本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。 我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
• 参考スコア（独自算出の注目度）: 41.24805506595378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical clustering is a fundamental task often used to discover meaningful structures in data, such as phylogenetic trees, taxonomies of concepts, subtypes of cancer, and cascades of particle decays in particle physics. Typically approximate algorithms are used for inference due to the combinatorial number of possible hierarchical clusterings. In contrast to existing methods, we present novel dynamic-programming algorithms for \emph{exact} inference in hierarchical clustering based on a novel trellis data structure, and we prove that we can exactly compute the partition function, maximum likelihood hierarchy, and marginal probabilities of sub-hierarchies and clusters. Our algorithms scale in time and space proportional to the powerset of $N$ elements which is super-exponentially more efficient than explicitly considering each of the (2N-3)!! possible hierarchies. Also, for larger datasets where our exact algorithms become infeasible, we introduce an approximate algorithm based on a sparse trellis that compares well to other benchmarks. Exact methods are relevant to data analyses in particle physics and for finding correlations among gene expression in cancer genomics, and we give examples in both areas, where our algorithms outperform greedy and beam search baselines. In addition, we consider Dasgupta's cost with synthetic data.
• Abstract（参考訳）: 階層的クラスタリングは、系統樹、概念の分類、がんのサブタイプ、粒子物理学における粒子崩壊のカスケードなど、データに有意義な構造を発見するためにしばしば用いられる基本的なタスクである。 通常、近似アルゴリズムは階層的クラスタリングの組合せ数のために推論に使用される。 既存の手法とは対照的に、新しいトレリスデータ構造に基づく階層クラスタリングにおける \emph{exact} 推論のための新しい動的プログラミングアルゴリズムを提案し、サブ階層とクラスタの分割関数、最大極大階層、限界確率を正確に計算できることを証明した。 我々のアルゴリズムは、各(2n-3)を明示的に考慮するよりも超指数的に効率的であるn$要素のパワーセットに比例する時間と空間でスケールする。 階層の可能性がある また、正確なアルゴリズムが実現不可能になった大きなデータセットに対しては、他のベンチマークと比較可能なスパーストレリスに基づく近似アルゴリズムを導入します。 厳密な手法は粒子物理学におけるデータ解析や、がんゲノム学における遺伝子発現の相関に関係しており、我々のアルゴリズムが欲望やビーム探索のベースラインを上回っている分野の例を示す。 さらに,合成データによるDasguptaのコストも考慮する。

関連論文リスト

• FLASC: A Flare-Sensitive Clustering Algorithm [0.0]
  本稿では,クラスタ内の分岐を検知してサブポピュレーションを同定するアルゴリズムFLASCを提案する。 アルゴリズムの2つの変種が提示され、ノイズの堅牢性に対する計算コストが取引される。 両変種は計算コストの観点からHDBSCAN*と類似してスケールし,安定した出力を提供することを示す。
  論文  参考訳（メタデータ） (2023-11-27T14:55:16Z)
• Fast Approximation of Similarity Graphs with Kernel Density Estimation [12.321755440062732]
  我々は,データポイントのセットである$X$から類似性グラフを構築するための新しいアルゴリズムをmathbbRd$に提示する。 提案アルゴリズムはカーネル密度推定問題に基づいており,任意のカーネル関数に適用可能である。
  論文  参考訳（メタデータ） (2023-10-21T00:32:47Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity [0.0]
  そこで本研究では,クラスタの自然な階層化を実現する,近接クラスタリングアルゴリズムを提案する。 集約的および分割的階層的クラスタリングアルゴリズムとは対照的に,我々のアプローチはアルゴリズムの反復的な動作に依存しない。
  論文  参考訳（メタデータ） (2022-03-15T16:03:42Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• 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)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences [0.0]
  本稿では,2つのエンティティが共有する特徴が単なるチャンスに起因する確率を定量化するエンティティ間の相似性に基づく階層的クラスタリングアルゴリズムを提案する。 アルゴリズムのパフォーマンスは n 個のエンティティの集合に適用された場合$O(n2)$であり、その結果はそれらのエンティティの接続を示すデンドログラムである。
  論文  参考訳（メタデータ） (2020-04-27T23:30:18Z)

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

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