論文の概要: The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It

• arxiv url: http://arxiv.org/abs/2602.09936v1
• Date: Tue, 10 Feb 2026 16:10:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-11 20:17:43.675279
• Title: The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It
• Title（参考訳）: 高次元におけるk平均アルゴリズムの破滅的破壊とハーディガンのアルゴリズムの回避方法
• Authors: Roy R. Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory,
• Abstract要約: ロイドのk平均アルゴリズムは高次元高雑音環境において破滅的な故障を示すことを示す。 我々は、ハーディガンのk-平均アルゴリズムがこの病理を示さないことを証明した。
• 参考スコア（独自算出の注目度）: 4.34403357988936
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lloyd's k-means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd's algorithm simply returns its initial partition - even when the underlying clusters are trivially recoverable by other methods. In contrast, we prove that Hartigan's k-means algorithm does not exhibit this pathology. Our results show the stark difference between these algorithms and offer a theoretical explanation for the empirical difficulties often observed with k-means in high dimensions.
• Abstract（参考訳）: ロイドのk平均アルゴリズムは最も広く使われているクラスタリング法の一つである。 高次元で高ノイズな設定では、アルゴリズムは破滅的な失敗を示す。 その結果、ロイドのアルゴリズムは、基礎となるクラスタが他のメソッドによって自明に回復可能である場合でも、その初期パーティションを単に返す。 対照的に、Hartiganのk-meansアルゴリズムは、この病理を示さないことを証明している。 以上の結果から,これらのアルゴリズムの違いが示され,高次元のk-meansでしばしば観察される経験的困難について理論的に説明できる。

関連論文リスト

• An Observation on Lloyd's k-Means Algorithm in High Dimensions [2.186901738997927]
  クラスタリングと推定クラスタは、統計学と機械学習における中核的な問題である。 我々は,高雑音と限られたサンプルサイズを有する高次元設定におけるk平均値の故障に関する理論的説明を提供する。
  論文  参考訳（メタデータ） (2025-06-17T20:06:41Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Adversarially robust clustering with optimality guarantees [6.194839632717497]
  我々はガウス以下の混合系から得られるデータポイントをクラスタリングする問題を考察する。 ロイドアルゴリズムのような最適ラベル誤りを確実に達成する既存の手法は、通常、外れ値に対して脆弱である。 本稿では, 対数外乱が存在する場合でも, 座標中央値に基づく単純なロバストアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-16T17:17:07Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• 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)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)

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

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