論文の概要: Consistency and Inconsistency in $K$-Means Clustering

• arxiv url: http://arxiv.org/abs/2507.06226v1
• Date: Tue, 08 Jul 2025 17:59:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-09 16:34:38.439787
• Title: Consistency and Inconsistency in $K$-Means Clustering
• Title（参考訳）: $K$-Meansクラスタリングにおける一貫性と一貫性
• Authors: Moïse Blanchard, Adam Quinn Jaffe, Nikita Zhivotovskiy,
• Abstract要約: ポラードの有名な結果は、人口分布が有限分散であるとき、$k$-meansクラスタリングの一貫性を証明する。 人口レベルの$k$-meansクラスタリング問題は、実際には、有限予想のより弱い仮定の下でうまく仮定されていることを示す。
• 参考スコア（独自算出の注目度）: 10.234307333602048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A celebrated result of Pollard proves asymptotic consistency for $k$-means clustering when the population distribution has finite variance. In this work, we point out that the population-level $k$-means clustering problem is, in fact, well-posed under the weaker assumption of a finite expectation, and we investigate whether some form of asymptotic consistency holds in this setting. As we illustrate in a variety of negative results, the complete story is quite subtle; for example, the empirical $k$-means cluster centers may fail to converge even if there exists a unique set of population $k$-means cluster centers. A detailed analysis of our negative results reveals that inconsistency arises because of an extreme form of cluster imbalance, whereby the presence of outlying samples leads to some empirical $k$-means clusters possessing very few points. We then give a collection of positive results which show that some forms of asymptotic consistency, under only the assumption of finite expectation, may be recovered by imposing some a priori degree of balance among the empirical $k$-means clusters.
• Abstract（参考訳）: ポラードの有名な結果は、集団分布が有限分散であるとき、$k$-meansクラスタリングの漸近一貫性を証明している。 本研究では,人口レベルの$k$-meansクラスタリング問題は,実際には有限予想の弱い仮定の下で十分に仮定されていることを指摘し,この設定において漸近的一貫性の何らかの形態が成立するかどうかを考察する。 例えば、実証的な$k$-meansクラスタセンターは、一意の集団である$k$-meansクラスタセンターが存在しても収束しないかもしれない。 以上の結果から, 異常はクラスター不均衡の極端な形によるものであり, 外部サンプルの存在は, ごくわずかな点を持つ経験的な$k$-meansクラスターに繋がることを示した。 次に、いくつかの漸近的整合性は、有限予想の仮定の下では、経験的$k$-meansクラスタ間での事前のバランスを課すことによって回復できることを示す正の結果の集合を与える。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。 有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
  論文  参考訳（メタデータ） (2025-06-01T09:34:52Z)
• One-shot Robust Federated Learning of Independent Component Analysis [16.462282750354408]
  そこで我々は,$k$-meansクラスタリングを利用して局所的クライアント推定における置換あいまいさを解消する幾何的中央値に基づく集約アルゴリズムを提案する。 提案手法は,まず,クライアントが提供する推定器をクラスタに分割し,次に幾何学的中央値を用いて各クラスタ内の推定器を集約するk-meansを実行する。
  論文  参考訳（メタデータ） (2025-05-26T21:37:19Z)
• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation [44.25945344950543]
  境界共分散分布の混合に対するクラスタリング問題について検討する。 このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。 我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
  論文  参考訳（メタデータ） (2023-12-19T01:01:53Z)
• Asymptotics for The $k$-means [0.6091702876917281]
  k$-meansは統計学と計算機科学において最も重要な教師なし学習手法の1つである。 提案したクラスタリング整合性は,クラスタリング手法の以前の基準整合性よりも適切である。 提案した$k$-means法はクラスタリングエラー率を低くし,小さなクラスタやアウトレイアに対してより堅牢であることがわかった。
  論文  参考訳（メタデータ） (2022-11-18T03:36:58Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Distribution free optimality intervals for clustering [1.7513645771137178]
  データ$mathcalD$と、これらのデータのパーティション$mathcalC$を$K$クラスタにすると、得られたクラスタがデータに対して正しい、あるいは有意義なものであると言えますか? 本稿では,K-means歪みなどの損失関数に関して,クラスタリング$mathcalC$が有意義であると考えられるパラダイムを紹介した。
  論文  参考訳（メタデータ） (2021-07-30T06:13:56Z)
• Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
  我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。 我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
  論文  参考訳（メタデータ） (2021-04-28T13:35:17Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Robust $k$-means Clustering for Distributions with Two Moments [4.21934751979057]
  我々は、$N$独立観測に基づいて量子化器を構成する$k$-meansクラスタリング問題に対するロバストアルゴリズムについて考察する。 我々の主な結果は、一般分離ヒルベルト空間における2つの有界モーメント仮定の下で成り立つ平均に基づく非漸近的過剰歪み境界の中央値である。
  論文  参考訳（メタデータ） (2020-02-06T16:36:53Z)

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

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