Fugu-MT 論文翻訳(概要): Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

論文の概要: Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

arxiv url: http://arxiv.org/abs/2306.09950v1
Date: Fri, 16 Jun 2023 16:31:46 GMT
ステータス: 処理完了
システム内更新日: 2023-06-19 13:02:20.064027
Title: Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs
Title（参考訳）: 高度にクラスタリングされたグラフのほぼ最適階層クラスタリング
Authors: Steinar Laenen, Bogdan-Adrian Manghiuc, He Sun
Abstract要約: 本稿では,Dasguptaのコスト関数に対する2つの効率的な階層クラスタリング(HC)アルゴリズムを提案する。明確なクラスタ構造を持つ任意の入力グラフ$G$に対して、我々の設計したアルゴリズムは、入力サイズが$G$でほぼ直線的に実行される。設計したアルゴリズムは、より少ない実行時間で、より優れたHCツリーを生成する。
参考スコア（独自算出の注目度）: 7.616556723260849
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function. For any input graph $G$ with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of $G$, and return an $O(1)$-approximate HC tree with respect to Dasgupta's cost function. We compare the performance of our algorithm against the previous state-of-the-art on synthetic and real-world datasets and show that our designed algorithm produces comparable or better HC trees with much lower running time.
Abstract（参考訳）: 本稿では,Dasguptaのコスト関数に対する2つの効率的な階層クラスタリングアルゴリズムを提案する。クラスタ構造を明確にした任意の入力グラフ$G$に対して、設計したアルゴリズムは、入力サイズが$G$でほぼ直線的に動作し、Dasguptaのコスト関数に関して$O(1)$-approximate HCツリーを返す。合成および実世界のデータセットにおける従来の最先端のアルゴリズムと比較し、設計したアルゴリズムがより少ない実行時間で比較またはより良いHC木を生成することを示す。

関連論文リスト

Fast Approximation of Similarity Graphs with Kernel Density Estimation [12.321755440062732]
我々は,データポイントのセットである$X$から類似性グラフを構築するための新しいアルゴリズムをmathbbRd$に提示する。提案アルゴリズムはカーネル密度推定問題に基づいており,任意のカーネル関数に適用可能である。
論文参考訳（メタデータ） (2023-10-21T00:32:47Z)
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)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文参考訳（メタデータ） (2022-06-17T09:24:41Z)
Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文参考訳（メタデータ） (2022-06-14T08:14:14Z)
Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
階層クラスタリングのための2時間近似アルゴリズムを提案する。本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
論文参考訳（メタデータ） (2021-12-16T17:52:04Z)
An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
論文参考訳（メタデータ） (2021-08-13T03:03:56Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文参考訳（メタデータ） (2021-06-10T09:29:05Z)
Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文参考訳（メタデータ） (2021-04-14T18:15:27Z)
Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文参考訳（メタデータ） (2021-04-02T16:05:00Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文参考訳（メタデータ） (2020-11-26T18:22:21Z)

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