論文の概要: Scaling Hierarchical Agglomerative Clustering to Billion-sized Datasets

• arxiv url: http://arxiv.org/abs/2105.11653v1
• Date: Tue, 25 May 2021 04:14:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-26 14:02:00.903499
• Title: Scaling Hierarchical Agglomerative Clustering to Billion-sized Datasets
• Title（参考訳）: 階層的な集約クラスタリングを数十億規模のデータセットにスケールアップする
• Authors: Baris Sumengen (1), Anand Rajagopalan (1), Gui Citovsky (1), David Simcha (1), Olivier Bachem (1), Pradipta Mitra (1), Sam Blasiak (1), Mason Liang (2), Sanjiv Kumar (1) ((1) Google Research, (2) 0x Labs)
• Abstract要約: 本稿では,並列クラスタを効率的にマージするための新しい戦略を用いて,HACの分散アルゴリズムであるReciprocal Agglomerative Clustering (RAC)を提案する。 大規模な実験では、RACは1時間以内で数十億のエッジで接続された数十億のデータポイント上のHAC階層を復元できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Hierarchical Agglomerative Clustering (HAC) is one of the oldest but still most widely used clustering methods. However, HAC is notoriously hard to scale to large data sets as the underlying complexity is at least quadratic in the number of data points and many algorithms to solve HAC are inherently sequential. In this paper, we propose {Reciprocal Agglomerative Clustering (RAC)}, a distributed algorithm for HAC, that uses a novel strategy to efficiently merge clusters in parallel. We prove theoretically that RAC recovers the exact solution of HAC. Furthermore, under clusterability and balancedness assumption we show provable speedups in total runtime due to the parallelism. We also show that these speedups are achievable for certain probabilistic data models. In extensive experiments, we show that this parallelism is achieved on real world data sets and that the proposed RAC algorithm can recover the HAC hierarchy on billions of data points connected by trillions of edges in less than an hour.
• Abstract（参考訳）: Hierarchical Agglomerative Clustering (HAC)は、最も古く、最も広く使われているクラスタリング手法の1つである。 しかし、HACは、基礎となる複雑さが少なくともデータポイントの数で二次的であり、HACを解くアルゴリズムが本質的にシーケンシャルであるため、大規模なデータセットにスケールすることが難しいことが知られている。 本稿では,クラスタを効率的に並列にマージするための新しい戦略を用いて,hacのための分散アルゴリズムである<reciprocal agglomerative clustering (rac)"を提案する。 理論的には、RACはHACの正確な解を回復する。 さらに、クラスタビリティと均衡性仮定の下では、並列性による全実行時の証明可能なスピードアップを示す。 また、これらのスピードアップは特定の確率的データモデルに対して達成可能であることを示す。 大規模な実験では、この並列性は実世界のデータセット上で達成され、提案したRACアルゴリズムは1時間以内で数十億のエッジで接続された数十億のデータポイント上のHAC階層を復元できることを示す。

関連論文リスト

• Data Aggregation for Hierarchical Clustering [0.3626013617212666]
  BETULAは、よく知られたBIRCHデータ集約アルゴリズムの数値的に安定したバージョンである。 これは、クラスタリングの品質に小さな損失しか与えずに、制約のあるリソースを持つシステムでHACを実行可能なものにするために使用できる。
  論文  参考訳（メタデータ） (2023-09-05T19:39:43Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• GBMST: An Efficient Minimum Spanning Tree Clustering Based on Granular-Ball Computing [78.92205914422925]
  多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。 粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。 いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
  論文  参考訳（メタデータ） (2023-03-02T09:04:35Z)
• Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering [1.0589208420411012]
  本稿では,クラスタ融合と高効率更新方式を用いた反復アルゴリズムCCMMによる凸クラスタリングを提案する。 現在のデスクトップコンピュータでは、CCMMは、7次元空間に100万以上のオブジェクトを含む凸クラスタリング問題を効率的に解決する。
  論文  参考訳（メタデータ） (2022-11-03T15:07:51Z)
• Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle [9.578056676899203]
  オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。 我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-17T08:51:19Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。 MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。 提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
  論文  参考訳（メタデータ） (2021-11-19T04:10:18Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Fair Algorithms for Hierarchical Agglomerative Clustering [17.66340013352806]
  Hierarchical Agglomerative Clustering (HAC)アルゴリズムは、現代のデータサイエンスで広く利用されている。 たとえデータセットが特定の保護されたグループに対するバイアスを含むとしても、これらのアルゴリズムが公平であることを保証することが不可欠である。 公平性制約を強制するHACを行うための公正アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-07T01:41:56Z)
• Probabilistic Partitive Partitioning (PPP) [0.0]
  クラスタリングアルゴリズムは一般に2つの一般的な問題に直面している。 彼らは異なる初期条件で異なる設定に収束する。 クラスタの数は、事前に任意に決めなければならない。
  論文  参考訳（メタデータ） (2020-03-09T19:18:35Z)

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

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