Fugu-MT 論文翻訳(概要): An effective variant of the Hartigan $k$-means algorithm

論文の概要: An effective variant of the Hartigan $k$-means algorithm

arxiv url: http://arxiv.org/abs/2604.21798v1
Date: Thu, 23 Apr 2026 15:57:05 GMT
ステータス: 翻訳完了
システム内更新日: 2026-04-24 14:40:06.702265
Title: An effective variant of the Hartigan $k$-means algorithm
Title（参考訳）: ハルディガン$k$-meansアルゴリズムの有効変種
Authors: François Clément, Stefan Steinerberger,
Abstract要約: k-平均問題はおそらく古典的なクラスタリング問題であり、ロイドのアルゴリズム(1957年)と同義である。ハーディガンのアルゴリズム(1975年)がほぼ全てのケースでより良い結果を与えることが明らかになっている。
参考スコア（独自算出の注目度）: 0.013714053458441644
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The k-means problem is perhaps the classical clustering problem and often synonymous with Lloyd's algorithm (1957). It has become clear that Hartigan's algorithm (1975) gives better results in almost all cases, Telgarsky-Vattani note a typical improvement of $5\%$ -- $10\%$. We point out that a very minor variation of Hartigan's method leads to another $2\%$ -- $5\%$ improvement; the improvement tends to become larger when either dimension or $k$ increase.
Abstract（参考訳）: k-平均問題はおそらく古典的なクラスタリング問題であり、ロイドのアルゴリズム(1957年)と同義である。 Telgarsky-Vattani は典型的な 5\%$ --10\%$ の改善を指摘している。我々は、Hartigan の手法の非常に小さなバリエーションが、さらに 2\%$ --5\%$ 改善をもたらすことを指摘している。

関連論文リスト

The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It [4.34403357988936]
ロイドのk平均アルゴリズムは高次元高雑音環境において破滅的な故障を示すことを示す。我々は、ハーディガンのk-平均アルゴリズムがこの病理を示さないことを証明した。
論文参考訳（メタデータ） (2026-02-10T16:10:59Z)
Dynamic Consistent $k$-Center Clustering with Optimal Recourse [0.6077284832583713]
我々は、$k$-centerクラスタリング問題において、決定論的定数係数近似を開発することにより、最適リコース境界を許容することを証明する。当社のインクリメンタルアルゴリズムは,Charikar,Chekuri,Feder,Motwaniによる8ドルの近似アルゴリズムよりも改善されている。
論文参考訳（メタデータ） (2024-12-04T11:39:03Z)
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)
Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文参考訳（メタデータ） (2023-10-28T13:01:10Z)
Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文参考訳（メタデータ） (2022-02-12T21:55:44Z)
Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。最適なデータ依存上界を導出する。また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文参考訳（メタデータ） (2020-08-12T15:40:21Z)

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