論文の概要: Parallelization of the K-Means Algorithm with Applications to Big Data Clustering

• arxiv url: http://arxiv.org/abs/2405.12052v1
• Date: Mon, 20 May 2024 14:18:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-21 13:05:04.712702
• Title: Parallelization of the K-Means Algorithm with Applications to Big Data Clustering
• Title（参考訳）: K平均アルゴリズムの並列化とビッグデータクラスタリングへの応用
• Authors: Ashish Srivastava, Mohammed Nawfal,
• Abstract要約: LLoydのアルゴリズムを使ったK-Meansクラスタリングは、与えられたデータセットをKの異なるクラスタに分割する反復的なアプローチである。 このプロジェクトでは2つの異なるアプローチを比較します。
• 参考スコア（独自算出の注目度）: 0.23020018305241333
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The K-Means clustering using LLoyd's algorithm is an iterative approach to partition the given dataset into K different clusters. The algorithm assigns each point to the cluster based on the following objective function \[\ \min \Sigma_{i=1}^{n}||x_i-\mu_{x_i}||^2\] The serial algorithm involves iterative steps where we compute the distance of each datapoint from the centroids and assign the datapoint to the nearest centroid. This approach is essentially known as the expectation-maximization step. Clustering involves extensive computations to calculate distances at each iteration, which increases as the number of data points increases. This provides scope for parallelism. However, we must ensure that in a parallel process, each thread has access to the updated centroid value and no racing condition exists on any centroid values. We will compare two different approaches in this project. The first approach is an OpenMP flat synchronous method where all processes are run in parallel, and we use synchronization to ensure safe updates of clusters. The second approach we adopt is a GPU based parallelization approach using OpenACC wherein we will try to make use of GPU architecture to parallelize chunks of the algorithm to observe decreased computation time. We will analyze metrics such as speed up, efficiency,time taken with varying data points, and number of processes to compare the two approaches and understand the relative performance improvement we can get.
• Abstract（参考訳）: LLoydのアルゴリズムを使ったK-Meansクラスタリングは、与えられたデータセットをKの異なるクラスタに分割する反復的なアプローチである。 このアルゴリズムは以下の目的関数 \[\ \min \Sigma_{i=1}^{n}||x_i-\mu_{x_i}||^2\] に基づいて各点をクラスタに割り当てる。 このアプローチは基本的には期待最大化ステップとして知られている。 クラスタリングには、各イテレーションにおける距離を計算するための広範な計算が含まれており、データポイントの数が増加するにつれて増加する。 これは並列処理のスコープを提供する。 しかし、並列プロセスでは、各スレッドが更新されたセントロイド値にアクセスでき、任意のセントロイド値にレース条件が存在しないことを保証する必要がある。 このプロジェクトでは2つの異なるアプローチを比較します。 最初のアプローチはOpenMPフラット同期方式で、すべてのプロセスが並列に実行される。 2つ目のアプローチは、OpenACCを使ったGPUベースの並列化アプローチです。 スピードアップ、効率、さまざまなデータポイントでかかった時間、そして2つのアプローチを比較して得られる相対的なパフォーマンス改善を理解するためのプロセスの数などを分析します。

関連論文リスト

• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [8.15681999722805]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• Linear time Evidence Accumulation Clustering with KMeans [0.0]
  この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。 分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。 k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
  論文  参考訳（メタデータ） (2023-11-15T14:12:59Z)
• Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds [0.23633885460047763]
  相関クラスタリング問題に対する並列アルゴリズムについて検討する。 目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。 現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。 3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T12:32:49Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• 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)
• Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
  SVMのような機械学習モデルは、シーケンスのペア間の距離/相似性の定義を必要とする。 厳密な手法により分類性能は向上するが、計算コストが高い。 本稿では,その予測性能を向上させるために,近似カーネルの性能を改善する一連の方法を提案する。
  論文  参考訳（メタデータ） (2022-09-11T22:44:19Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。 従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。 我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
  論文  参考訳（メタデータ） (2021-06-08T23:13:27Z)
• Determinantal consensus clustering [77.34726150561087]
  本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。 DPPは部分集合内の中心点の多様性を好んでいる。 DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
  論文  参考訳（メタデータ） (2021-02-07T23:48:24Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Ball k-means [53.89505717006118]
  Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。 高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
  論文  参考訳（メタデータ） (2020-05-02T10:39:26Z)

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

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