論文の概要: Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

• arxiv url: http://arxiv.org/abs/2008.05171v2
• Date: Tue, 1 Jun 2021 08:16:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-31 04:28:32.391124
• Title: Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms
• Title（参考訳）: 高速かつイーガーなk-メドイドクラスタリング: PAM, CLARA, CLARANSアルゴリズムのO(k)実行時改善
• Authors: Erich Schubert and Peter J. Rousseeuw
• Abstract要約: Partitioning Around Medoids (PAM) は非ユークリッドデータをクラスタリングするためのアルゴリズムである。 本稿では,アルゴリズムの第2フェーズ(SWAP)でO(k)倍の高速化を実現するPAMの修正を提案する。 k=100,200の実データを用いた実験では,元のPAM SWAPアルゴリズムと比較して,それぞれ458倍のスピードアップを観測した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering non-Euclidean data is difficult, and one of the most used algorithms besides hierarchical clustering is the popular algorithm Partitioning Around Medoids (PAM), also simply referred to as k-medoids clustering. In Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does not exist for arbitrary dissimilarities. PAM uses the medoid instead, the object with the smallest dissimilarity to all others in the cluster. This notion of centrality can be used with any (dis-)similarity, and thus is of high relevance to many domains and applications. A key issue with PAM is its high run time cost. We propose modifications to the PAM algorithm that achieve an O(k)-fold speedup in the second ("SWAP") phase of the algorithm, but will still find the same results as the original PAM algorithm. If we relax the choice of swaps performed (while retaining comparable quality), we can further accelerate the algorithm by eagerly performing additional swaps in each iteration. With the substantially faster SWAP, we can now explore faster initialization strategies, because (i) the classic ("BUILD") initialization now becomes the bottleneck, and (ii) our swap is fast enough to compensate for worse starting conditions. We also show how the CLARA and CLARANS algorithms benefit from the proposed modifications. While we do not study the parallelization of our approach in this work, it can easily be combined with earlier approaches to use PAM and CLARA on big data (some of which use PAM as a subroutine, hence can immediately benefit from these improvements), where the performance with high k becomes increasingly important. In experiments on real data with k=100,200, we observed a 458x respectively 1191x speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets, and in particular to higher k.
• Abstract（参考訳）: 非ユークリッドデータのクラスタリングは困難であり、階層的クラスタリング以外の最もよく使われるアルゴリズムの1つは、k-medoids clusteringとも呼ばれるPAM(Partitioning Around Medoids)である。 ユークリッド幾何学において、k-平均で使われる平均はクラスター中心に良い推定子であるが、任意の相似性には存在しない。 PAMは代わりにメドイドを使用し、クラスタ内の他のすべてのオブジェクトと最小の相同性を持つオブジェクトである。 この中心性の概念は任意の(dis-)類似性で使用することができ、したがって多くのドメインやアプリケーションに高い関係がある。 PAMの大きな問題は、高い実行時間コストである。 アルゴリズムの第2(SWAP)フェーズでO(k)倍の高速化を実現するPAMアルゴリズムの修正を提案するが、元のPAMアルゴリズムと同じ結果が得られる。 実行されたスワップの選択を緩和し(同等の品質を維持しながら)、各イテレーションで熱心にスワップを実行してアルゴリズムをさらに加速することができる。 スワップが大幅に速くなれば、より高速な初期化戦略を探せるようになります。 (i)古典的「BUILD」初期化がボトルネックとなり、 (二)当社のスワップは、開始条件の悪化を補うのに十分な速さです。 また,claraアルゴリズムとclaransアルゴリズムが提案する修正の利点を示す。 本研究におけるアプローチの並列化は研究されていないが,PAM と CLARA をビッグデータ上で使用するための従来のアプローチ(一部ではサブルーチンとして PAM を使用しているため,これらの改善の恩恵を受けられる)と組み合わせれば,高い k での性能がますます重要になる。 k=100,200の実データに対する実験では、元のPAM SWAPアルゴリズムと比較して458倍のスピードアップを観測し、PAMをより大きなデータセット、特に高いkに適用した。

関連論文リスト

• Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering [0.6215404942415159]
  我々は、新しい時系列クラスタリング(TSCL)アルゴリズム、$k$-means (K)Accelerated (A) subgradient (S) Barycentre (B) Average (A)を提案する。 KASBAは、クラスタリングのすべての段階で、Move-Split-Merge (MSM) の弾性距離を使用し、ランダム化下降降下を適用してバリセント・セントロイドを見つけ、クラスタリングの各段階をリンクして収束を加速し、MSM距離の計量特性を利用して距離計算を行う、$k$-meansクラスタリングアルゴリズムである。 汎用的でスケーラブルなクラスタリングである。
  論文  参考訳（メタデータ） (2024-11-26T19:26:17Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• GBMST: An Efficient Minimum Spanning Tree Clustering Based on Granular-Ball Computing [78.92205914422925]
  多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。 粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。 いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
  論文  参考訳（メタデータ） (2023-03-02T09:04:35Z)
• Careful Seeding for k-Medois Clustering with Incremental k-Means++ Initialization [17.4921582710817]
  K-medoidsクラスタリングはk-meansクラスタリングの一般的な変種であり、パターン認識や機械学習で広く使用されている。 INCKMアルゴリズムと呼ばれる改良されたk-medoidsクラスタリングアルゴリズムが最近提案され、この欠点を克服した。 インクリメンタルk-means++ (INCKPP) アルゴリズムと呼ばれる新しいk-medoidsクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-06T02:25:35Z)
• 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)
• 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)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
  最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。 最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。 本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
  論文  参考訳（メタデータ） (2020-06-22T20:02:59Z)

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

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