論文の概要: Correlation Clustering in Constant Many Parallel Rounds
- arxiv url: http://arxiv.org/abs/2106.08448v1
- Date: Tue, 15 Jun 2021 21:45:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 09:55:19.042007
- Title: Correlation Clustering in Constant Many Parallel Rounds
- Title(参考訳): 定数多並列ラウンドにおける相関クラスタリング
- Authors: Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovi\'c, Ashkan
Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
- Abstract要約: 相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。
本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。
我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
- 参考スコア(独自算出の注目度): 42.10280805559555
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Correlation clustering is a central topic in unsupervised learning, with many
applications in ML and data mining. In correlation clustering, one receives as
input a signed graph and the goal is to partition it to minimize the number of
disagreements. In this work we propose a massively parallel computation (MPC)
algorithm for this problem that is considerably faster than prior work. In
particular, our algorithm uses machines with memory sublinear in the number of
nodes in the graph and returns a constant approximation while running only for
a constant number of rounds. To the best of our knowledge, our algorithm is the
first that can provably approximate a clustering problem on graphs using only a
constant number of MPC rounds in the sublinear memory regime. We complement our
analysis with an experimental analysis of our techniques.
- Abstract(参考訳): 相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。
相関クラスタリングでは、符号付きグラフを入力として受信し、不一致の数を最小限に抑えるために分割する。
本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。
特に,本アルゴリズムでは,グラフ内のノード数にメモリサブリニアを持つマシンを使用し,一定数のラウンドのみを実行しながら定数近似を返却する。
我々の知る限り、我々のアルゴリズムは、サブ線形メモリシステムにおいて、一定数のMPCラウンドのみを用いてグラフ上のクラスタリング問題を確実に近似できる最初のアルゴリズムである。
我々は、我々の技術の実験的な分析で分析を補完する。
関連論文リスト
- Fast and Simple Spectral Clustering in Theory and Practice [7.070726553564701]
スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。
電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。
合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
論文 参考訳(メタデータ) (2023-10-17T02:31:57Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Massively-Parallel Heat Map Sorting and Applications To Explainable
Clustering [1.544681800932596]
我々は,クラスタ(ラベル)を保存しながら,点と次元を再順序付けし,マージする熱マップソート問題を導入する。
クラスタが接続されている場合、すなわち複数のクラスタに分割されず、2つのクラスタがマージされない場合、クラスタは保存される。
NP-hard特殊ケースに対する近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-14T07:53:52Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。
すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
論文 参考訳(メタデータ) (2022-06-15T16:25:27Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳(メタデータ) (2022-03-02T20:07:04Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳(メタデータ) (2021-11-30T05:40:14Z) - (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping [57.316437798033974]
本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。
我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。
一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
論文 参考訳(メタデータ) (2020-12-01T13:17:27Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳(メタデータ) (2020-08-18T16:22:06Z) - Flow-based Algorithms for Improving Clusters: A Unifying Framework,
Software, and Performance [0.0]
グラフ内のベクトル空間やノードのクラスタリングポイントは、統計データ解析においてユビキタスプリミティブである。
このクラスタ改善問題に対するアルゴリズムの原則に着目する。
ローカルGraphClustering Pythonパッケージでこれらのアルゴリズムの効率的な実装を開発します。
論文 参考訳(メタデータ) (2020-04-20T20:14:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。