論文の概要: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
- arxiv url: http://arxiv.org/abs/2106.05610v1
- Date: Thu, 10 Jun 2021 09:29:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-11 14:43:38.401396
- Title: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
- Title（参考訳）: ほぼ線形時間における階層的凝集グラフクラスタリング
- Authors: Laxman Dhulipala, David Eisenstat, Jakub {\L}\k{a}cki, Vahab Mirrokni,
Jessica Shi
- Abstract要約: エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
- 参考スコア（独自算出の注目度）: 1.5644420658691407
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the widely used hierarchical agglomerative clustering (HAC)
algorithm on edge-weighted graphs. We define an algorithmic framework for
hierarchical agglomerative graph clustering that provides the first efficient
$\tilde{O}(m)$ time exact algorithms for classic linkage measures, such as
complete- and WPGMA-linkage, as well as other measures. Furthermore, for
average-linkage, arguably the most popular variant of HAC, we provide an
algorithm that runs in $\tilde{O}(n\sqrt{m})$ time. For this variant, this is
the first exact algorithm that runs in subquadratic time, as long as
$m=n^{2-\epsilon}$ for some constant $\epsilon > 0$. We complement this result
with a simple $\epsilon$-close approximation algorithm for average-linkage in
our framework that runs in $\tilde{O}(m)$ time. As an application of our
algorithms, we consider clustering points in a metric space by first using
$k$-NN to generate a graph from the point set, and then running our algorithms
on the resulting weighted graph. We validate the performance of our algorithms
on publicly available datasets, and show that our approach can speed up
clustering of point datasets by a factor of 20.7--76.5x.
- Abstract（参考訳）: エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
我々は階層的凝集グラフクラスタリングのためのアルゴリズムフレームワークを定義し、完全リンクやwngmaリンクなどの古典的なリンケージ測度のための最初の効率的な$\tilde{o}(m)$時間厳密なアルゴリズムを提供する。
さらに、hacの最も一般的な変種である平均リンクに対して、$\tilde{o}(n\sqrt{m})$ timeで動作するアルゴリズムを提供する。
この変種に対して、これは、ある定数 $\epsilon > 0$ に対して$m=n^{2-\epsilon}$ の四進時間で実行される最初の正確なアルゴリズムである。
私たちは、$\tilde{o}(m)$時間で実行されるフレームワークの平均リンクに対して、単純な$\epsilon$-close approximationアルゴリズムでこの結果を補完します。
アルゴリズムの適用例として、まず$k$-NNを用いて、点集合からグラフを生成し、その結果の重み付きグラフ上でアルゴリズムを実行することで、計量空間内のクラスタリングポイントを考察する。
公開データセット上でのアルゴリズムの性能を検証し,20.7～76.5倍の速度でポイントデータセットのクラスタリングを高速化できることを示す。
関連論文リスト
- Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳（メタデータ） (2024-07-15T20:04:06Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Fast and Simple Spectral Clustering in Theory and Practice [7.070726553564701]
スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。
電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。
合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
論文 参考訳（メタデータ） (2023-10-17T02:31:57Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - 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) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。
提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
論文 参考訳（メタデータ） (2023-01-01T10:57:36Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。