論文の概要: Exact and Approximate Hierarchical Clustering Using A*

• arxiv url: http://arxiv.org/abs/2104.07061v1
• Date: Wed, 14 Apr 2021 18:15:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-16 15:09:07.307631
• Title: Exact and Approximate Hierarchical Clustering Using A*
• Title（参考訳）: A*を用いたエクササイズと近似階層クラスタリング
• Authors: Craig S. Greenberg, Sebastian Macaluso, Nicholas Monath, Avinava Dubey, Patrick Flaherty, Manzil Zaheer, Amr Ahmed, Kyle Cranmer, Andrew McCallum
• Abstract要約: クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
• 参考スコア（独自算出の注目度）: 51.187990314731344
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical clustering is a critical task in numerous domains. Many approaches are based on heuristics and the properties of the resulting clusterings are studied post hoc. However, in several applications, there is a natural cost function that can be used to characterize the quality of the clustering. In those cases, hierarchical clustering can be seen as a combinatorial optimization problem. To that end, we introduce a new approach based on A* search. We overcome the prohibitively large search space by combining A* with a novel \emph{trellis} data structure. This combination results in an exact algorithm that scales beyond previous state of the art, from a search space with $10^{12}$ trees to $10^{15}$ trees, and an approximate algorithm that improves over baselines, even in enormous search spaces that contain more than $10^{1000}$ trees. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks. We describe how our method provides significantly improved theoretical bounds on the time and space complexity of A* for clustering.
• Abstract（参考訳）: 階層的クラスタリングは、多くのドメインにおいて重要なタスクです。 多くのアプローチはヒューリスティックスに基づいており、その結果のクラスタリングの性質はポストホックで研究されている。 しかし、いくつかのアプリケーションでは、クラスタリングの品質を特徴付けるために使用できる自然なコスト関数がある。 このような場合、階層的クラスタリングは組合せ最適化問題と見なすことができる。 そこで我々は,A*検索に基づく新しいアプローチを提案する。 我々は、a* と新しい \emph{trellis} データ構造を組み合わせることで、強制的に大きい探索空間を克服する。 10^{12}$ツリーの探索空間から10^{15}$ツリーの探索空間、そして10^{1000}$ツリーを含む巨大な探索空間でさえもベースラインを上回る近似アルゴリズムまで、この組み合わせによって、以前の状態を超える正確なアルゴリズムが実現されます。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。 本稿では,クラスタリングにおけるA*の時間と空間の複雑さに関する理論的境界について述べる。

関連論文リスト

• Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
  表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。 木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-10-19T14:02:42Z)
• GBMST: An Efficient Minimum Spanning Tree Clustering Based on Granular-Ball Computing [78.92205914422925]
  多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。 粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。 いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
  論文  参考訳（メタデータ） (2023-03-02T09:04:35Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity [0.0]
  そこで本研究では,クラスタの自然な階層化を実現する,近接クラスタリングアルゴリズムを提案する。 集約的および分割的階層的クラスタリングアルゴリズムとは対照的に,我々のアプローチはアルゴリズムの反復的な動作に依存しない。
  論文  参考訳（メタデータ） (2022-03-15T16:03:42Z)
• An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
  階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。 本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
  論文  参考訳（メタデータ） (2021-08-13T03:03:56Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)
• Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
  本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。 我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
  論文  参考訳（メタデータ） (2020-02-26T17:43:53Z)

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

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