論文の概要: Modified K-means Algorithm with Local Optimality Guarantees

• arxiv url: http://arxiv.org/abs/2506.06990v2
• Date: Wed, 11 Jun 2025 06:52:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 02:07:43.333507
• Title: Modified K-means Algorithm with Local Optimality Guarantees
• Title（参考訳）: 局所最適保証を用いた改良K平均アルゴリズム
• Authors: Mingyi Li, Michael R. Metel, Akiko Takeda,
• Abstract要約: K-meansアルゴリズムは機械学習において最も広く研究されているクラスタリングアルゴリズムの1つである。 本稿では,K-meansアルゴリズムが局所最適解に収束する条件を提案する。 連続性と離散性の両方において局所的最適性を保証するK-meansアルゴリズムの簡単な修正を提案する。
• 参考スコア（独自算出の注目度）: 10.936166435599574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The K-means algorithm is one of the most widely studied clustering algorithms in machine learning. While extensive research has focused on its ability to achieve a globally optimal solution, there still lacks a rigorous analysis of its local optimality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K-means algorithm which ensure local optimality in both the continuous and discrete sense, with the same computational complexity as the original K-means algorithm. As the dissimilarity measure, we consider a general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find a locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at https://github.com/lmingyi/LO-K-means.
• Abstract（参考訳）: K-meansアルゴリズムは機械学習において最も広く研究されているクラスタリングアルゴリズムの1つである。 大規模な研究は、グローバルな最適解を達成する能力に焦点を合わせてきたが、その局所最適性保証に関する厳密な分析はいまだに欠けている。 本稿では,K-meansアルゴリズムが局所最適解に収束する条件を最初に提示する。 そこで本研究では,K-meansアルゴリズムの計算量と同じ計算量で,K-meansアルゴリズムの局所最適性を連続的かつ離散的に保証する手法を提案する。 相似性測度として、K-平均アルゴリズムでよく用いられる2乗ユークリッド距離の拡張である一般ブレグマン発散を考える。 数値実験により,K-meansアルゴリズムは必ずしも局所最適解が見つからないが,提案手法はクラスタリング損失を低減した局所最適解を提供する。 私たちのコードはhttps://github.com/lmingyi/LO-K-means.comで利用可能です。

関連論文リスト

• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• An enhanced method of initial cluster center selection for K-means algorithm [0.0]
  K-meansアルゴリズムの初期クラスタ選択を改善するための新しい手法を提案する。 Convex Hullアルゴリズムは、最初の2つのセントロイドの計算を容易にし、残りの2つは、以前選択された中心からの距離に応じて選択される。 We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data。
  論文  参考訳（メタデータ） (2022-10-18T00:58:50Z)
• How to Use K-means for Big Data Clustering? [2.1165011830664677]
  K-meansはEuclidean Minimum Sum-of-Squares Clustering (MSSC)モデルの下で最もシンプルで広く使われているアルゴリズムである。 ビッグデータクラスタリングにK-means++アルゴリズムとK-means++アルゴリズムを用いる並列方式を提案する。
  論文  参考訳（メタデータ） (2022-04-14T08:18:01Z)
• A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
  この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。 分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
  論文  参考訳（メタデータ） (2022-03-02T09:29:40Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。 それぞれのソリューションのコストを評価するのに 費用がかかります 上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
  論文  参考訳（メタデータ） (2021-08-18T08:41:58Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Locally Private k-Means in One Round [44.00192304748844]
  差分プライバシー(DP)の1ラウンド(別名非相互作用)局所モデルにおけるk平均クラスタリングの近似アルゴリズムを提供する。 このアルゴリズムは、最適な非プライベート近似アルゴリズムに近い近似比を任意に達成する。
  論文  参考訳（メタデータ） (2021-04-20T03:07:31Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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