論文の概要: BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed
Bandits
- arxiv url: http://arxiv.org/abs/2006.06856v2
- Date: Sun, 6 Dec 2020 22:40:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 09:17:02.989628
- Title: BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed
Bandits
- Title（参考訳）: BanditPAM: ほぼ線形時間$k$-Medoidsクラスタリング
- Authors: Mo Tiwari, Martin Jinye Zhang, James Mayclin, Sebastian Thrun, Chris
Piech, Ilan Shomorony
- Abstract要約: 現在の$k$-medoidsクラスタリングアルゴリズム、例えば、PAM(Partitioning Around Medoids)は反復的であり、各イテレーションで$n$のデータセットサイズであり、大規模なデータセットでは極めて高価である。
マルチアームバンディットの技法にインスパイアされたランダム化アルゴリズムであるBanditPAMを提案する。これは、PAMの繰り返しの複雑さを$O(n2)$から$O(n log n)$に減らし、実際に保持されるデータに対する仮定の下で、高い確率で同じ結果を返す。
我々は、コーディングを含むいくつかの大規模な実世界のデータセットで実験的に結果を検証する。
- 参考スコア（独自算出の注目度）: 16.1767275655842
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a ubiquitous task in data science. Compared to the commonly
used $k$-means clustering, $k$-medoids clustering requires the cluster centers
to be actual data points and support arbitrary distance metrics, which permits
greater interpretability and the clustering of structured objects. Current
state-of-the-art $k$-medoids clustering algorithms, such as Partitioning Around
Medoids (PAM), are iterative and are quadratic in the dataset size $n$ for each
iteration, being prohibitively expensive for large datasets. We propose
BanditPAM, a randomized algorithm inspired by techniques from multi-armed
bandits, that reduces the complexity of each PAM iteration from $O(n^2)$ to
$O(n \log n)$ and returns the same results with high probability, under
assumptions on the data that often hold in practice. As such, BanditPAM matches
state-of-the-art clustering loss while reaching solutions much faster. We
empirically validate our results on several large real-world datasets,
including a coding exercise submissions dataset, the 10x Genomics 68k PBMC
single-cell RNA sequencing dataset, and the MNIST handwritten digits dataset.
In these experiments, we observe that BanditPAM returns the same results as
state-of-the-art PAM-like algorithms up to 4x faster while performing up to
200x fewer distance computations. The improvements demonstrated by BanditPAM
enable $k$-medoids clustering on a wide range of applications, including
identifying cell types in large-scale single-cell data and providing scalable
feedback for students learning computer science online. We also release highly
optimized Python and C++ implementations of our algorithm.
- Abstract（参考訳）: クラスタリングはデータサイエンスにおけるユビキタスなタスクです。
一般的に使用される$k$-meansクラスタリングと比較すると、$k$-medoidsクラスタリングは、クラスタセンタを実際のデータポイントとして、任意の距離メトリックをサポートする必要がある。
現在の最先端の$k$-medoidsクラスタリングアルゴリズム(PAM(Partitioning Around Medoids)など)は反復的であり、各イテレーションのデータセットサイズが$n$である。
本研究では,多腕バンディットの手法に触発されたランダム化アルゴリズムであるbanditpamを提案し,pamの各イテレーションの複雑さをo(n^2)$ から$o(n \log n)$ に低減し,同じ結果を高い確率で返す。
そのため、BanditPAMは最先端のクラスタリング損失と一致し、ソリューションをはるかに高速にする。
我々は、コーディングエクササイズ提案データセット、10xGenomics 68k PBMCシングルセルRNAシークエンシングデータセット、MNIST手書き桁データセットなど、いくつかの大規模な実世界のデータセットに対して、我々の結果を実証的に検証した。
これらの実験では、BanditPAMは最先端のPAMライクなアルゴリズムと同じ結果を最大4倍高速に出力し、最大200倍の距離計算を行う。
BanditPAMが示した改善により、大規模なシングルセルデータのセルタイプ識別や、学生がオンラインでコンピュータサイエンスを学ぶためのスケーラブルなフィードバックなど、幅広いアプリケーションで$k$-medoidsクラスタリングが可能になる。
また、アルゴリズムの高度に最適化されたPythonとC++の実装もリリースしました。
関連論文リスト
- A Scalable k-Medoids Clustering via Whale Optimization Algorithm [0.0]
We introduced WOA-kMedoids, a novel unsupervised clustering method which with the Whale Optimization Algorithm (WOA)。
セントロイド選択を最適化することにより、WOA-kMedoidsは観測数に関してk-メドロイドアルゴリズムの計算複雑性を2次からほぼ直線に減らす。
UCRアーカイブから25種類の時系列データセットを用いたWOA-kMedoidsの性能評価を行った。
論文 参考訳（メタデータ） (2024-08-30T03:43:37Z) - Distributed Collapsed Gibbs Sampler for Dirichlet Process Mixture Models
in Federated Learning [0.22499166814992444]
本稿では,DPMM (DisCGS) のための分散マルコフ連鎖モンテカルロ (MCMC) 推論手法を提案する。
我々のアプローチでは、崩壊したGibbsサンプルラーを使用し、独立マシンと異種マシンの分散データを扱うように設計されています。
例えば、100Kのデータポイントのデータセットでは、中央集権的なアルゴリズムは100回のイテレーションを完了するのに約12時間かかります。
論文 参考訳（メタデータ） (2023-12-18T13:16:18Z) - BanditPAM++: Faster $k$-medoids Clustering [16.42816643809205]
k$-medoidsクラスタリングでは、クラスタセンターは実際のデータポイントでなければならない。
最近の研究では、最先端の複雑さとクラスタリング精度を備えたランダム化$k$-medoidsアルゴリズムであるBanditPAMが提案されている。
本稿では,BanditPAMを2つのアルゴリズム改良により高速化するBanditPAM++について述べる。
論文 参考訳（メタデータ） (2023-10-28T23:11:16Z) - 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) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Faster DBSCAN via subsampled similarity queries [42.93847281082316]
DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。
本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
論文 参考訳（メタデータ） (2020-06-11T18:57:54Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Efficient Algorithms for Generating Provably Near-Optimal Cluster
Descriptors for Explainability [36.11663695534294]
本稿では,クラスタに対する簡潔な表現を構築するための最近のアプローチを拡張して,クラスタをより解釈しやすくする問題について検討する。
我々は,その問題に対する性能保証を証明可能な近似アルゴリズムを開発した。
また、異なる脅威レベルを表すゲノム配列のクラスタを含むデータセットからのクラスタを説明するアプリケーションを示す。
論文 参考訳（メタデータ） (2020-02-06T19:49:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。