論文の概要: Coreset Spectral Clustering

• arxiv url: http://arxiv.org/abs/2503.07227v1
• Date: Mon, 10 Mar 2025 12:14:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-11 15:45:25.976200
• Title: Coreset Spectral Clustering
• Title（参考訳）: Coreset Spectral Clustering
• Authors: Ben Jourdan, Gregory Schwartzman, Peter Macgregor, He Sun,
• Abstract要約: カーネル$k$-meansと正規化されたカット問題との接続を利用して、両方の利点を組み合わせます。 我々の主な成果は、コアセットグラフをクラスタリングして元のグラフの良質なラベル付けを推測するグラフのコアセットスペクトルクラスタリングアルゴリズムである。
• 参考スコア（独自算出の注目度）: 12.244933452638312
• License:
• Abstract: Coresets have become an invaluable tool for solving $k$-means and kernel $k$-means clustering problems on large datasets with small numbers of clusters. On the other hand, spectral clustering works well on sparse graphs and has recently been extended to scale efficiently to large numbers of clusters. We exploit the connection between kernel $k$-means and the normalised cut problem to combine the benefits of both. Our main result is a coreset spectral clustering algorithm for graphs that clusters a coreset graph to infer a good labelling of the original graph. We prove that an $\alpha$-approximation for the normalised cut problem on the coreset graph is an $O(\alpha)$-approximation on the original. We also improve the running time of the state-of-the-art coreset algorithm for kernel $k$-means on sparse kernels, from $\tilde{O}(nk)$ to $\tilde{O}(n\cdot \min \{k, d_{avg}\})$, where $d_{avg}$ is the average number of non-zero entries in each row of the $n\times n$ kernel matrix. Our experiments confirm our coreset algorithm is asymptotically faster on large real-world graphs with many clusters, and show that our clustering algorithm overcomes the main challenge faced by coreset kernel $k$-means on sparse kernels which is getting stuck in local optima.
• Abstract（参考訳）: Coresetsは、少数のクラスタを持つ大規模なデータセット上で、$k$-meansとカーネル$k$-meansのクラスタリング問題を解決するための、貴重なツールになっている。 一方、スペクトルクラスタリングはスパースグラフでうまく機能し、最近は多数のクラスタに効率的にスケールするように拡張されている。 カーネル$k$-meansと正規化されたカット問題との接続を利用して、両方の利点を組み合わせます。 我々の主な成果は、コアセットグラフをクラスタリングして元のグラフの良質なラベル付けを推測するグラフのコアセットスペクトルクラスタリングアルゴリズムである。 コアセットグラフ上の正規化カット問題に対する$\alpha$-approximationが元の$O(\alpha)$-approximationであることを証明する。 また、スパースカーネル上のカーネル$k$-meansに対する最先端コアセットアルゴリズムの実行時間を、$\tilde{O}(nk)$から$\tilde{O}(n\cdot \min \{k, d_{avg}\})$へと改善する。 実験により,多数のクラスタを持つ大規模実世界のグラフでは,コアセットアルゴリズムが漸近的に高速であることが確認された。

関連論文リスト

• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• 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)
• Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
  ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。 ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。 クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。 ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
  論文  参考訳（メタデータ） (2023-05-28T15:33:24Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation [24.166833799353476]
  カーネルグラフ上では$textitweighted edge sample$、カーネルグラフ上では$textitweighted walk$、行列で$textitweighted sample$からKernel Density Estimationへ効率よく還元する。 当社の削減は、それぞれのアプリケーションにおいて中心的な要素であり、それらが独立した関心事である可能性があると信じています。
  論文  参考訳（メタデータ） (2022-12-01T16:42:56Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
  Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。 k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。 我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-30T15:49:41Z)
• Online Coresets for Clustering with Bregman Divergences [11.650724544695498]
  bregman divergencesの幅広いサブセットに従って,クラスタ問題に対してオンライン環境でコアセットを作成するアルゴリズムを提案する。 特に、私たちのコアセットは、軽量コアセットBachem etと同様、小さな添加誤差を持っています。 アル 2018.
  論文  参考訳（メタデータ） (2020-12-11T17:39:21Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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