論文の概要: An interpretable Good--Turing restart criterion for k-means++

• arxiv url: http://arxiv.org/abs/2607.08243v1
• Date: Thu, 09 Jul 2026 08:43:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-10 14:45:27.472441
• Title: An interpretable Good--Turing restart criterion for k-means++
• Title（参考訳）: k-means++の解釈可能なGood-Turing再起動基準
• Abstract要約: k-means++アルゴリズムは、ローカル最適化の貧弱さを避けるために、通常、何度も再起動される。 本稿では,GTRC,Good-Turing推定値,証明された無条件境界値,信頼に基づく境界値を組み合わせた再起動基準を紹介する。 36データセットにわたって、GTRCはクラスタリング品質に到達し、良好に固定された再起動回数と競合した。
• 参考スコア（独自算出の注目度）: 0.9137554315375919
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The k-means++ algorithm is commonly restarted multiple times to avoid poor local optima, yet the number of restarts is almost always chosen arbitrarily and applied uniformly regardless of data set difficulty. This undermines any comparison relying on such a choice and wastes computation on easy data sets while potentially under-serving hard ones. We introduce GTRC, a restart criterion combining a Good-Turing estimate, a proven unconditional bound, and a confidence-based bound on the probability that a further restart would improve on the current result, stopping once this probability falls below a user-specified tolerance $\varepsilon$. Across 36 data sets, GTRC reached clustering quality competitive with well-chosen fixed restart counts, while the number of restarts used varied considerably and appropriately with data set difficulty, governed by an interpretable, data-dependent signal rather than a fixed rule. GTRC offers a principled and reportable alternative to fixing the number of $k$-means++ restarts in advance. Software:https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion.
• Abstract（参考訳）: k-means++アルゴリズムは、ローカルの最適化が貧弱になるのを避けるために、通常、複数回再起動されるが、再起動の回数は、データセットの難易度に関わらず、ほぼ任意に選択され、一様に適用される。 これは、そのような選択に依存するあらゆる比較を弱め、簡単なデータセットでの計算を無駄にしながら、潜在的にハードなものを不足させる。 我々は、GTRC、Good-Turingの推定値、証明された非条件境界、そして、現在の結果に対して更なる再起動が改善する確率に基づく信頼ベースのバウンダリを組み合わせた再起動基準を導入し、この確率がユーザ指定のトレランス$\varepsilon$以下になると停止する。 36個のデータセットでGTRCはクラスタリング品質に到達し、使用する再起動回数は、固定ルールではなく解釈可能なデータ依存信号によって制御されるデータセットの難易度によって大きく、適切に変化した。 GTRCは、$k$-means++の再起動数を事前に修正する、原則的でレポート可能な代替手段を提供する。 ソフトウェア:https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion

関連論文リスト

• Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond [11.884593048693507]
  我々は,$doperator次元の自己選択バイアスを持つ線形回帰器を$k$で推定する問題を再検討する。 我々の主な結果は、この問題に対する$namepoly(d,k,1/varepsilon) + kO(k)$ time algorithmである。
  論文  参考訳（メタデータ） (2025-04-06T20:59:12Z)
• Geometric Median Matching for Robust k-Subset Selection from Noisy Data [75.86423267723728]
  最適分解点1/2のロバストな推定器であるGeometric Medianを利用する新しいk-subset選択法を提案する。 提案手法は, k-subset を反復的に選択し,部分集合の平均が(潜在的に)ノイズデータセットの GM に近似し,任意の汚損の下でもロバスト性を確保する。
  論文  参考訳（メタデータ） (2025-04-01T09:22:05Z)
• Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing [2.542838926315103]
  ランダム化ブロックKaczmarz法(RBK)のデータの一様サンプリング時の収束を解析し,その繰り返しがモンテカルロの感覚で$textit$ least-squaresの解に収束することを示す。 RBKイテレーションに正規化を組み込むことでこれらの問題を制御し、正規化アルゴリズムReBlocKを得る。
  論文  参考訳（メタデータ） (2025-02-02T19:23:46Z)
• Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery [33.26163081551751]
  本稿では,$k$サポート標準正規化器に基づく新しい反復正規化アルゴリズムIRKSNを提案する。 IRKSNを用いてスパースリカバリ条件を提供し、従来のリカバリ条件と$ell_1$標準正規化器を比較した。 また、IRKSNのモデル誤差を定数で早期に停止し、スパースリカバリの標準線形レートを達成する。
  論文  参考訳（メタデータ） (2023-12-19T09:21:08Z)
• Sequential Kernelized Independence Testing [77.237958592189]
  我々は、カーネル化依存度にインスパイアされたシーケンシャルなカーネル化独立試験を設計する。 シミュレーションデータと実データの両方にアプローチのパワーを実証する。
  論文  参考訳（メタデータ） (2022-12-14T18:08:42Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。 本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。 政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
  論文  参考訳（メタデータ） (2021-06-03T09:50:13Z)
• On the Comparison between Cyclic Sampling and Random Reshuffling [27.27774034428748]
  周期的なサンプリングは、サンプルを周期的に再シャッフルするよりも頑丈でない、固定された循環的な順序でサンプルを引き出す。 既存の研究は、循環サンプリングにおける最悪のケース収束率を確立しており、一般にランダムリシャフリングよりも悪い。 本論文では,リシャッフルよりも一定の周期順序の方がはるかに早く,低コストで発見できることを発見した。
  論文  参考訳（メタデータ） (2021-04-25T09:29:43Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Entropy Regularized Power k-Means Clustering [21.013169939337583]
  本稿では、クローズドフォーム更新と収束保証を享受できるスケーラブルな大規模化最小化アルゴリズムを提案する。 我々の手法は、$k$-meansと$k$-meansと同じ計算量を維持しているが、どちらも大幅に改善されている。
  論文  参考訳（メタデータ） (2020-01-10T14:05:44Z)

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

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