論文の概要: Fast and Simple Spectral Clustering in Theory and Practice
- arxiv url: http://arxiv.org/abs/2310.10939v1
- Date: Tue, 17 Oct 2023 02:31:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 18:02:24.104537
- Title: Fast and Simple Spectral Clustering in Theory and Practice
- Title（参考訳）: 理論と実践における高速で単純なスペクトルクラスタリング
- Authors: Peter Macgregor
- Abstract要約: スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。
電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。
合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
- 参考スコア（独自算出の注目度）: 7.070726553564701
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spectral clustering is a popular and effective algorithm designed to find $k$
clusters in a graph $G$. In the classical spectral clustering algorithm, the
vertices of $G$ are embedded into $\mathbb{R}^k$ using $k$ eigenvectors of the
graph Laplacian matrix. However, computing this embedding is computationally
expensive and dominates the running time of the algorithm. In this paper, we
present a simple spectral clustering algorithm based on a vertex embedding with
$O(\log(k))$ vectors computed by the power method. The vertex embedding is
computed in nearly-linear time with respect to the size of the graph, and the
algorithm provably recovers the ground truth clusters under natural assumptions
on the input graph. We evaluate the new algorithm on several synthetic and
real-world datasets, finding that it is significantly faster than alternative
clustering algorithms, while producing results with approximately the same
clustering accuracy.
- Abstract（参考訳）: スペクトルクラスタリングは、グラフ$g$で$k$クラスタを見つけるように設計された人気で効果的なアルゴリズムである。
古典的なスペクトルクラスタリングアルゴリズムでは、グラフラプラシアン行列の$k$固有ベクトルを用いて、$g$の頂点を$\mathbb{r}^k$に埋め込む。
しかし、この埋め込みの計算は計算コストが高く、アルゴリズムの実行時間を支配している。
本稿では、電力法により計算された$O(\log(k))$ベクトルを用いた頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。
頂点埋め込みはグラフのサイズに関してほぼ線形時間で計算され、アルゴリズムは入力グラフ上の自然な仮定の下で基底真理クラスタを確実に回復する。
合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
関連論文リスト
- Dynamic Spectral Clustering with Provable Approximation Guarantee [7.6676757797831225]
本論文は, クラスタ構造が緩やかな条件下では, 最終グラフ$G_T$のクラスタはスペクトルクラスタリングアルゴリズムの動的変種によってよく近似できることを示した。
合成と実世界の両方のデータセットに関する実験的研究により、我々の設計したアルゴリズムの実用性がさらに裏付けられる。
論文 参考訳（メタデータ） (2024-06-05T11:16:55Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。