Fugu-MT 論文翻訳(概要): A Faster $k$-means++ Algorithm

論文の概要: A Faster $k$-means++ Algorithm

arxiv url: http://arxiv.org/abs/2211.15118v2
Date: Tue, 13 Feb 2024 19:39:48 GMT
ステータス: 処理完了
システム内更新日: 2024-02-15 20:22:53.118556
Title: A Faster $k$-means++ Algorithm
Title（参考訳）: より高速な$k$-means++アルゴリズム
Authors: Jiehao Liang, Somdeb Sarkhel, Zhao Song, Chenbo Yin, Junze Yin, Danyang Zhuo
Abstract要約: ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
参考スコア（独自算出の注目度）: 11.428775569173638
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: $k$-means++ is an important algorithm for choosing initial cluster centers for the $k$-means clustering algorithm. In this work, we present a new algorithm that can solve the $k$-means++ problem with nearly optimal running time. Given $n$ data points in $\mathbb{R}^d$, the current state-of-the-art algorithm runs in $\widetilde{O}(k )$ iterations, and each iteration takes $\widetilde{O}(nd k)$ time. The overall running time is thus $\widetilde{O}(n d k^2)$. We propose a new algorithm \textsc{FastKmeans++} that only takes in $\widetilde{O}(nd + nk^2)$ time, in total.
Abstract（参考訳）: $k$-means++は、$k$-meansクラスタリングアルゴリズムの初期クラスタセンターを選択するための重要なアルゴリズムである。そこで本研究では,k$-means++問題をほぼ最適実行時間で解く新しいアルゴリズムを提案する。 n$のデータポイントが$\mathbb{r}^d$で与えられると、現在の最先端のアルゴリズムは$\widetilde{o}(k)$の反復で動作し、各イテレーションは$\widetilde{o}(nd k)$の時間を要する。従って、全体の実行時間は$\widetilde{O}(n d k^2)$である。我々は,$\widetilde{o}(nd + nk^2)$ の時間しかかからない新しいアルゴリズム \textsc{fastkmeans++} を提案する。

関連論文リスト

Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文参考訳（メタデータ） (2024-10-08T10:59:14Z)
Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文参考訳（メタデータ） (2024-07-15T20:04:06Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文参考訳（メタデータ） (2023-10-29T16:46:26Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
論文参考訳（メタデータ） (2022-07-16T13:49:07Z)
Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文参考訳（メタデータ） (2021-12-21T01:54:17Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)

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

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