Fugu-MT 論文翻訳(概要): Randomizing the Number of Centers in k-means++

論文の概要: Randomizing the Number of Centers in k-means++

arxiv url: http://arxiv.org/abs/2607.26202v1
Date: Tue, 28 Jul 2026 19:06:53 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-30 21:06:25.455181
Title: Randomizing the Number of Centers in k-means++
Title（参考訳）: k-means++におけるセンター数のランダム化
Abstract要約: k$-means++アルゴリズムは、$k$-meansクラスタリングのための標準的で広く使われているシード手法である。敵がデータセットと約$K$を最初に修正すると、同じアルゴリズムが検討され、センターの$k$の数は、$K,ldots,2K-1$から一様に選択される。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The $k$-means++ algorithm is a standard and widely used seeding method for $k$-means clustering, but for a fixed number $k$ of centers its worst-case expected approximation ratio is $Θ(\log k)$. We consider the same algorithm when an adversary first fixes the dataset and some $K$; the number of centers $k$ is then chosen uniformly from $\{K,\ldots,2K-1\}$. We prove that $k$-means++ is an $O(1)$-approximation with constant probability in this budget-smoothed setup.
Abstract（参考訳）: $k$-means++アルゴリズムは、$k$-meansクラスタリングのための標準で広く使われているシード手法であるが、固定数$k$のセンターでは、最悪のケースで予想される近似比が$(\log k)$である。敵がデータセットと約$K$を最初に修正したときと同じアルゴリズムを考慮し、センターの$k$の数は$\{K,\ldots,2K-1\}$から一様に選択される。 k$-means++ が$O(1)$-approximation であることを示す。

関連論文リスト

Computational Hardness of Private Coreset [84.99100741615423]
与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。 no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。 $k$-means in the
論文参考訳（メタデータ） (2026-02-19T15:58:49Z)
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)
Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文参考訳（メタデータ） (2023-10-25T16:37:45Z)
Multi-Swap $k$-Means++ [30.967186562175893]
Arthur and Vassilvitskii (SODA 2007)の$k$-means++アルゴリズムは、人気のある$k$-meansクラスタリングの目的を最適化するための実践者の選択アルゴリズムであることが多い。 Lattanzi氏とSohler氏(ICML)は、$k$-means++を$O(k log log k)$で拡張して、$k$-meansクラスタリング問題に$c$-approximationをもたらすよう提案した。
論文参考訳（メタデータ） (2023-09-28T12:31:35Z)
Improved Outlier Robust Seeding for k-means [3.9973713691377646]
逆ノイズや外れ値では、D2$サンプリングは、より遠方の外れ値から中心を選別する傾向にある。サンプル分布として$D2$の単純な変種を提案する。我々のアルゴリズムは、$O(k)$クラスタの代わりに正確に$k$クラスタを出力するように修正することもできる。
論文参考訳（メタデータ） (2023-09-06T04:46:01Z)
Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Differentially Private Clustering in Data Streams [56.26040303056582]
私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
論文参考訳（メタデータ） (2023-07-14T16:11:22Z)
Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文参考訳（メタデータ） (2023-02-20T23:29:43Z)
Global $k$-means$++$: an effective relaxation of the global $k$-means clustering algorithm [0.20305676256390928]
k$-meansアルゴリズムは、その単純さ、有効性、スピードから、一般的なクラスタリング手法である。本稿では,高品質クラスタリングソリューションを効果的に取得する手段として,emphglobal $k$-meanstexttt++クラスタリングアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-11-22T13:42:53Z)
Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文参考訳（メタデータ） (2022-10-31T03:00:11Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)

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