論文の概要: BanditPAM++: Faster $k$-medoids Clustering
- arxiv url: http://arxiv.org/abs/2310.18844v1
- Date: Sat, 28 Oct 2023 23:11:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 16:04:01.721068
- Title: BanditPAM++: Faster $k$-medoids Clustering
- Title（参考訳）: BanditPAM++: $k$-medoidsクラスタリングの高速化
- Authors: Mo Tiwari, Ryan Kang, Donghyun Lee, Sebastian Thrun, Chris Piech, Ilan
Shomorony, Martin Jinye Zhang
- Abstract要約: k$-medoidsクラスタリングでは、クラスタセンターは実際のデータポイントでなければならない。
最近の研究では、最先端の複雑さとクラスタリング精度を備えたランダム化$k$-medoidsアルゴリズムであるBanditPAMが提案されている。
本稿では,BanditPAMを2つのアルゴリズム改良により高速化するBanditPAM++について述べる。
- 参考スコア（独自算出の注目度）: 16.42816643809205
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Clustering is a fundamental task in data science with wide-ranging
applications. In $k$-medoids clustering, cluster centers must be actual
datapoints and arbitrary distance metrics may be used; these features allow for
greater interpretability of the cluster centers and the clustering of exotic
objects in $k$-medoids clustering, respectively. $k$-medoids clustering has
recently grown in popularity due to the discovery of more efficient $k$-medoids
algorithms. In particular, recent research has proposed BanditPAM, a randomized
$k$-medoids algorithm with state-of-the-art complexity and clustering accuracy.
In this paper, we present BanditPAM++, which accelerates BanditPAM via two
algorithmic improvements, and is $O(k)$ faster than BanditPAM in complexity and
substantially faster than BanditPAM in wall-clock runtime. First, we
demonstrate that BanditPAM has a special structure that allows the reuse of
clustering information $\textit{within}$ each iteration. Second, we demonstrate
that BanditPAM has additional structure that permits the reuse of information
$\textit{across}$ different iterations. These observations inspire our proposed
algorithm, BanditPAM++, which returns the same clustering solutions as
BanditPAM but often several times faster. For example, on the CIFAR10 dataset,
BanditPAM++ returns the same results as BanditPAM but runs over 10$\times$
faster. Finally, we provide a high-performance C++ implementation of
BanditPAM++, callable from Python and R, that may be of interest to
practitioners at https://github.com/motiwari/BanditPAM. Auxiliary code to
reproduce all of our experiments via a one-line script is available at
https://github.com/ThrunGroup/BanditPAM_plusplus_experiments.
- Abstract（参考訳）: クラスタリングは幅広いアプリケーションを扱うデータサイエンスにおける基本的なタスクである。
k$-medoidsクラスタリングでは、クラスタセンタは実際のデータポイントでなければならず、任意の距離メトリクスが使用できる。
$k$-medoidsクラスタリングは、より効率的な$k$-medoidsアルゴリズムの発見により、最近人気が高まっている。
特に最近の研究では、最先端の複雑さとクラスタリング精度を備えたランダム化$k$-medoidsアルゴリズムであるBanditPAMが提案されている。
本稿では,BanditPAMを2つのアルゴリズム改良により高速化するBanditPAM++を提案する。
まず、BanditPAMはクラスタリング情報の再利用を可能にする特別な構造を持っていることを実証します。
次に、banditpamには、$\textit{across}$の異なるイテレーションを再利用する追加の構造があることを実証する。
これらの観測から提案したアルゴリズムであるBanditPAM++は、BanditPAMと同じクラスタリングソリューションを返すが、多くの場合は数倍高速である。
例えば、CIFAR10データセットでは、BanditPAM++はBanditPAMと同じ結果を返すが、10$\times$高速に実行される。
最後に、我々は、PythonとRから呼び出し可能なBanditPAM++の高性能なC++実装を提供しています。
実験を1行のスクリプトで再現するための補助的なコードはhttps://github.com/ThrunGroup/BanditPAM_plus_experiments.comにある。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - GBMST: An Efficient Minimum Spanning Tree Clustering Based on
Granular-Ball Computing [78.92205914422925]
多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。
粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。
いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
論文 参考訳（メタデータ） (2023-03-02T09:04:35Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。
本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文 参考訳（メタデータ） (2023-01-17T17:49:04Z) - Faster Maximum Inner Product Search in High Dimensions [17.040520467777295]
最大内部製品探索(MIPS)は、リコメンデーションシステムなどの機械学習アプリケーションにおいて、ユビキタスなタスクである。
複雑度が$d$に依存しない新しいランダム化MIPSアルゴリズムであるBanditMIPSを提案する。
我々は、BanditMIPSが正しい答えを高い確率で返し、$d$を$O(sqrtd)$から$O(1)$に改善する理論的な保証を提供する。
論文 参考訳（メタデータ） (2022-12-14T23:46:23Z) - 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) - 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) - Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the
PAM, CLARA, and CLARANS Algorithms [0.0]
Partitioning Around Medoids (PAM) は非ユークリッドデータをクラスタリングするためのアルゴリズムである。
本稿では,アルゴリズムの第2フェーズ(SWAP)でO(k)倍の高速化を実現するPAMの修正を提案する。
k=100,200の実データを用いた実験では,元のPAM SWAPアルゴリズムと比較して,それぞれ458倍のスピードアップを観測した。
論文 参考訳（メタデータ） (2020-08-12T08:37:50Z) - BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed
Bandits [16.1767275655842]
現在の$k$-medoidsクラスタリングアルゴリズム、例えば、PAM(Partitioning Around Medoids)は反復的であり、各イテレーションで$n$のデータセットサイズであり、大規模なデータセットでは極めて高価である。
マルチアームバンディットの技法にインスパイアされたランダム化アルゴリズムであるBanditPAMを提案する。これは、PAMの繰り返しの複雑さを$O(n2)$から$O(n log n)$に減らし、実際に保持されるデータに対する仮定の下で、高い確率で同じ結果を返す。
我々は、コーディングを含むいくつかの大規模な実世界のデータセットで実験的に結果を検証する。
論文 参考訳（メタデータ） (2020-06-11T22:17:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。