論文の概要: A Geometric Approach to $k$-means

• arxiv url: http://arxiv.org/abs/2201.04822v2
• Date: Mon, 22 Sep 2025 21:01:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-24 20:41:27.332047
• Title: A Geometric Approach to $k$-means
• Title（参考訳）: $k$-meansに対する幾何学的アプローチ
• Authors: Jiazhen Hong, Wei Qian, Yudong Chen, Yuqian Zhang,
• Abstract要約: kmeansクラスタリングは多くのエンジニアリング領域において基本的な問題である。 本稿では,望ましくない2つの解を回避し,解や接地クラスタリングを回復するための一般的な枠組みを提案する。
• 参考スコア（独自算出の注目度）: 12.972775894401943
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: \kmeans clustering is a fundamental problem in many scientific and engineering domains. The optimization problem associated with \kmeans clustering is nonconvex, for which standard algorithms are only guaranteed to find a local optimum. Leveraging the hidden structure of local solutions, we propose a general algorithmic framework for escaping undesirable local solutions and recovering the global solution or the ground truth clustering. This framework consists of iteratively alternating between two steps: (i) detect mis-specified clusters in a local solution, and (ii) improve the local solution by non-local operations. We discuss specific implementation of these steps, and elucidate how the proposed framework unifies many existing variants of \kmeans algorithms through a geometric perspective. We also present two natural variants of the proposed framework, where the initial number of clusters may be over- or under-specified. We provide theoretical justifications and extensive experiments to demonstrate the efficacy of the proposed approach.
• Abstract（参考訳）: クメールスクラスタリングは多くの科学的・工学的な領域において根本的な問題である。 kmeansクラスタリングに関連する最適化問題は非凸であり、標準的なアルゴリズムは局所的な最適化を見つけることしか保証されない。 局所解の隠れ構造を利用して、望ましくない局所解を逃れ、大域的解や真理クラスタリングを回復するための一般的なアルゴリズム的枠組みを提案する。 この枠組みは、2つのステップを反復的に交互に交互に構成する。 (i)局所溶液中の誤特定クラスタを検出して (ii)非局所的操作による局所的解法の改善。 本稿では,これらのステップの具体的実装について論じ,幾何学的視点から,提案するフレームワークが既存の多くの \kmeans アルゴリズムを統一する方法について述べる。 また、提案するフレームワークの2つの自然な変種を示す。 提案手法の有効性を実証するために,理論的正当化と広範な実験を行った。

関連論文リスト

• Modified K-means Algorithm with Local Optimality Guarantees [10.936166435599574]
  K-meansアルゴリズムは機械学習において最も広く研究されているクラスタリングアルゴリズムの1つである。 本稿では,K-meansアルゴリズムが局所最適解に収束する条件を提案する。 連続性と離散性の両方において局所的最適性を保証するK-meansアルゴリズムの簡単な修正を提案する。
  論文  参考訳（メタデータ） (2025-06-08T04:37:28Z)
• SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization [35.92829763686735]
  本稿では,複数のエージェントが協調して,近傍通信によるネスト最適化構造に関わる問題を解く分散二段階最適化について検討する。 SPARKLE(Single-loop Primal-dual AlgoRithm frameworK)を提案する。 本稿では,SPARKLEの統一収束解析を行い,既存の分散二段階アルゴリズムと比較して,最先端の収束率を持つ全変種に適用する。
  論文  参考訳（メタデータ） (2024-11-21T14:23:06Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  異種環境における分散学習のためのコミュニケーション効率化手法のファミリーを提案する。 ユーザによるローカル計算に基づくワンショットアプローチと、サーバにおけるクラスタリングベースのアグリゲーションステップは、強力な学習保証を提供する。 厳密な凸問題に対しては,ユーザ毎のデータ点数がしきい値を超える限り,提案手法はサンプルサイズの観点から順序最適平均二乗誤差率を達成する。
  論文  参考訳（メタデータ） (2022-09-22T09:04:10Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  本稿では、2つの革新的な手法を取り入れたMIS問題に対する効率的なアルゴリズムを提案する。 提案アルゴリズムは、解の質、計算効率、安定性の点で最先端のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Distributed and Stochastic Optimization Methods with Gradient Compression and Local Steps [0.0]
  本稿では,誤差補償と局所的な更新を伴う解析および分散手法に関する理論的枠組みを提案する。 線形収束型Error-pensated法と分散型Local-SGD法を含む20以上の新しい最適化手法を開発した。
  論文  参考訳（メタデータ） (2021-12-20T16:12:54Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• From Local SGD to Local Fixed-Point Methods for Federated Learning [17.04886864943171]
  分散環境で,演算子の平均点の固定点,あるいは近似を求めるという一般的な問題を考える。 このようなコンセンサスを達成するための2つの戦略について検討する。一方は局所的なステップの固定数に基づくもので、もう一方はランダム化された計算に基づくものである。
  論文  参考訳（メタデータ） (2020-04-03T09:24:10Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Structures of Spurious Local Minima in $k$-means [20.155509538529568]
  我々は、$k$-means問題に対する急激な局所解の構造について検討する。 分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
  論文  参考訳（メタデータ） (2020-02-16T22:15:03Z)

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

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