論文の概要: Structures of Spurious Local Minima in $k$-means
- arxiv url: http://arxiv.org/abs/2002.06694v2
- Date: Fri, 21 Feb 2020 21:19:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 18:08:10.091134
- Title: Structures of Spurious Local Minima in $k$-means
- Title（参考訳）: $k$-meansにおけるすっぱい局所最小値の構造
- Authors: Wei Qian, Yuqian Zhang, Yudong Chen
- Abstract要約: 我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
- 参考スコア（独自算出の注目度）: 20.155509538529568
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: $k$-means clustering is a fundamental problem in unsupervised learning. The
problem concerns finding a partition of the data points into $k$ clusters such
that the within-cluster variation is minimized. Despite its importance and wide
applicability, a theoretical understanding of the $k$-means problem has not
been completely satisfactory. Existing algorithms with theoretical performance
guarantees often rely on sophisticated (sometimes artificial) algorithmic
techniques and restricted assumptions on the data. The main challenge lies in
the non-convex nature of the problem; in particular, there exist additional
local solutions other than the global optimum. Moreover, the simplest and most
popular algorithm for $k$-means, namely Lloyd's algorithm, generally converges
to such spurious local solutions both in theory and in practice.
In this paper, we approach the $k$-means problem from a new perspective, by
investigating the structures of these spurious local solutions under a
probabilistic generative model with $k$ ground truth clusters. As soon as
$k=3$, spurious local minima provably exist, even for well-separated and
balanced clusters. One such local minimum puts two centers at one true cluster,
and the third center in the middle of the other two true clusters. For general
$k$, one local minimum puts multiple centers at a true cluster, and one center
in the middle of multiple true clusters. Perhaps surprisingly, we prove that
this is essentially the only type of spurious local minima under a separation
condition. Our results pertain to the $k$-means formulation for mixtures of
Gaussians or bounded distributions. Our theoretical results corroborate
existing empirical observations and provide justification for several improved
algorithms for $k$-means clustering.
- Abstract（参考訳）: k$-meansクラスタリングは教師なし学習における根本的な問題である。
問題は、クラスタ内の変動を最小限に抑えるために、データポイントを$k$クラスタに分割することにある。
その重要性と幅広い適用性にもかかわらず、k$-means問題の理論的な理解は完全に満足できるものではなかった。
理論的な性能保証を持つ既存のアルゴリズムは、しばしば高度な(時には人工的な)アルゴリズム技術と、データに対する仮定を制限している。
主な課題は、問題の凸でない性質にある。特に、大域的最適化以外の局所解が存在する。
さらに、$k$-meansの最も単純で一般的なアルゴリズム、すなわちロイドのアルゴリズムは、理論と実際の両方においてそのような急激な局所解に収束する。
本稿では,これらの局所解の構造を,k$基底真理クラスタを用いた確率的生成モデルの下で検討することにより,新たな視点から,k$-means問題にアプローチする。
k=3$になると、うまく分離されバランスの取れたクラスタでさえも、スプリアスなローカルミニマが確実に存在する。
そのような局所的最小は、2つの中心を1つの真のクラスターに置き、3つ目の中心を残りの2つの真のクラスターの中央に置く。
一般的な$k$の場合、1つのローカル最小は、複数のセンターを真のクラスタに、もう1つは、複数の真のクラスタの中央に配置する。
おそらく驚くべきことに、これは本質的に分離条件下でのスプリアス局所ミニマの唯一のタイプであることを証明している。
この結果はガウス分布や有界分布の混合に対するk$-meansの定式化に関係している。
我々の理論結果は既存の経験的観測結果と一致し、k$-meansクラスタリングのためのいくつかの改良されたアルゴリズムの正当化を提供する。
関連論文リスト
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。
我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。
PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
論文 参考訳（メタデータ） (2024-11-02T02:50:12Z) - Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Are Easy Data Easy (for K-Means) [0.0]
本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。
シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
論文 参考訳（メタデータ） (2023-08-02T09:40:19Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。
分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。
十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文 参考訳（メタデータ） (2022-02-05T01:59:09Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-29T08:13:56Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。