論文の概要: OneBatchPAM: A Fast and Frugal K-Medoids Algorithm
- arxiv url: http://arxiv.org/abs/2501.19285v1
- Date: Fri, 31 Jan 2025 16:48:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-03 14:01:07.193597
- Title: OneBatchPAM: A Fast and Frugal K-Medoids Algorithm
- Title（参考訳）: OneBatchPAM: K-Medoidsアルゴリズム
- Authors: Antoine de Mathelin, Nicolas Enrique Cecchi, François Deheeger, Mathilde Mougeot, Nicolas Vayatis,
- Abstract要約: 本稿では,大規模データセットを適切な計算時間とメモリの複雑さで処理する新しいk-medoids近似アルゴリズムを提案する。
単一のサイズ m n のバッチは、ほとんどの k-メディドのベースラインと比較して、O(n2) ではなく、必要なメモリサイズとペアの異なる計算数を O(mn) に減少させる。
我々は,m = O(log(n)) のバッチが強い確率で元の局所探索アルゴリズムと同じ性能を保証するのに十分であることを示す理論的結果を得る。
- 参考スコア（独自算出の注目度）: 6.69456225406097
- License:
- Abstract: This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a local-search algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m << n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n^2) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time.
- Abstract（参考訳）: 本稿では,大規模データセットを適切な計算時間とメモリの複雑さで処理する新しいk-medoids近似アルゴリズムを提案する。
そこで我々は,k-メドイドの目的を推定し,メドイド選択を反復的に改善する局所探索アルゴリズムを開発した。
m <<n の単一バッチは、ほとんどの k-メディドのベースラインと比較して、O(n^2) ではなく、必要なメモリサイズとペアの異なる計算数を O(mn) に減少させる。
我々は,m = O(log(n)) のバッチが強い確率で元の局所探索アルゴリズムと同じ性能を保証するのに十分であることを示す理論的結果を得る。
様々なサイズと次元の実際のデータセット上で行われた複数の実験により、我々のアルゴリズムは、FasterPAMやBanditPAM++のような最先端の手法と同様に、実行時間を劇的に短縮した性能を提供することを示した。
関連論文リスト
- Robust Clustering on High-Dimensional Data with Stochastic Quantization [0.0]
本稿では,従来のベクトル量子化アルゴリズムの限界に対処する。
量子化(SQ)を高次元計算の代替として検討する。
論文 参考訳（メタデータ） (2024-09-03T17:13:55Z) - Quantum-Based Feature Selection for Multi-classification Problem in
Complex Systems with Edge Computing [15.894122816099133]
マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。
我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
論文 参考訳（メタデータ） (2023-10-01T03:57:13Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Accelerated Doubly Stochastic Gradient Algorithm for Large-scale
Empirical Risk Minimization [23.271890743506514]
本稿では,学習課題に対する大規模経験的リスク最小化問題を解くために,新たな高速化マルチモーメンタム手法を用いた二重アルゴリズムを提案する。
絶対的に優れた収束率を享受しながら、各イテレーションにおいて、そのようなアルゴリズムはサンプルの小さなバッチにのみアクセスし、変数座標の小さなブロックを更新する。
論文 参考訳（メタデータ） (2023-04-23T14:21:29Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - 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) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。