論文の概要: Fast Distributed k-Means with a Small Number of Rounds

• arxiv url: http://arxiv.org/abs/2201.13217v1
• Date: Mon, 31 Jan 2022 13:27:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-01 18:22:32.541289
• Title: Fast Distributed k-Means with a Small Number of Rounds
• Title（参考訳）: 少量のラウンドを持つ高速分散k-mean
• Authors: Tom Hess, Ron Visbord, Sivan Sabato
• Abstract要約: 分散環境でのk-meansクラスタリングのための新しいアルゴリズムを提案する。 本アルゴリズムは,コーディネータの計算能力にのみ依存するコスト近似係数と多数の通信ラウンドを保証する。
• 参考スコア（独自算出の注目度）: 19.495806969497583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new algorithm for k-means clustering in a distributed setting, where the data is distributed across many machines, and a coordinator communicates with these machines to calculate the output clustering. Our algorithm guarantees a cost approximation factor and a number of communication rounds that depend only on the computational capacity of the coordinator. Moreover, the algorithm includes a built-in stopping mechanism, which allows it to use fewer communication rounds whenever possible. We show both theoretically and empirically that in many natural cases, indeed 1-4 rounds suffice. In comparison with the popular k-means|| algorithm, our approach allows exploiting a larger coordinator capacity to obtain a smaller number of rounds. Our experiments show that the k-means cost obtained by the proposed algorithm is usually better than the cost obtained by k-means||, even when the latter is allowed a larger number of rounds. Moreover, the machine running time in our approach is considerably smaller than that of k-means||. Code for running the algorithm and experiments is available at https://github.com/selotape/distributed_k_means.
• Abstract（参考訳）: 本稿では,k-meansクラスタリングのための新しいアルゴリズムを提案する。このアルゴリズムでは,複数のマシンに分散し,コーディネータがこれらのマシンと通信して出力クラスタリングを計算する。 本アルゴリズムは,コーディネータの計算能力にのみ依存するコスト近似係数と多数の通信ラウンドを保証する。 さらにこのアルゴリズムには,通信ラウンドを可能な限り少なくすることができる,ストップ機構が組み込まれている。 理論的にも経験的にも、多くの自然の場合、実際には1-4ラウンドで十分であることを示す。 一般的なk-means||アルゴリズムと比較して、我々の手法はより大きいコーディネータ容量を利用してより少ないラウンドを得ることができる。 実験の結果,提案アルゴリズムにより得られたk平均コストは,後者のラウンド数が多い場合でも,k平均|のコストよりも高いことがわかった。 さらに,本手法の機械走行時間はk-means|よりもかなり小さい。 アルゴリズムと実験を実行するコードは、https://github.com/selotape/distributed_k_meansで入手できる。

関連論文リスト

• 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 Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Using MM principles to deal with incomplete data in K-means clustering [0.0]
  K平均クラスタリングアルゴリズムは、単純なアルゴリズムと高速収束のために広く利用されている。 主に、データの対称性を復元するためにMMの原理を適用し、K平均がうまく動作するようにします。
  論文  参考訳（メタデータ） (2022-12-23T14:50:57Z)
• An enhanced method of initial cluster center selection for K-means algorithm [0.0]
  K-meansアルゴリズムの初期クラスタ選択を改善するための新しい手法を提案する。 Convex Hullアルゴリズムは、最初の2つのセントロイドの計算を容易にし、残りの2つは、以前選択された中心からの距離に応じて選択される。 We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data。
  論文  参考訳（メタデータ） (2022-10-18T00:58:50Z)
• 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)
• K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect the Number of Clusters [0.12313056815753944]
  本稿では,k-meansに基づく改良された階層型アルゴリズムであるk-splitsを紹介する。 提案手法の主な利点は,精度と速度である。
  論文  参考訳（メタデータ） (2021-10-09T23:02:57Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Relational Algorithms for k-means Clustering [17.552485682328772]
  本稿では,関係アルゴリズムモデルにおいて効率的なk平均近似アルゴリズムを提案する。 実行時間は潜在的に$N$よりも小さくなり、リレーショナルデータベースが表すデータポイントの数はクラスタ化される。
  論文  参考訳（メタデータ） (2020-08-01T23:21:40Z)

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

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