概要: K-meansクラスタリングは教師なし学習の定番ですが、外れ値、分布のシフト、限られたサンプルサイズに対して非常に脆いことで知られています。k-meansを経験分布のLloyd--Max量子化として捉えることで、そのような病理を防ぐ分布的に頑健な変種を開発します。我々は、未知の母集団分布が経験分布の周りのWasserstein-2ボールの中に含まれると仮定します。この設定では、不確かさ集合にわたって最悪の場合の期待二乗距離を最小化するクラスタ中心を求めることになり、minimax（ミニマックス）定式化が導かれます。扱いやすい双対問題により、ハードな割当てを滑らかに重み付けされたものに置き換えるソフトクラスタリング手法が得られます。証明可能な単調減少と局所的な線形収束を伴う、効率的なブロック座標降下アルゴリズムを提案します。標準的なベンチマークおよび大規模な合成データに対する実験により、外れ値検出およびノイズへの頑健性において顕著な改善が示されます。
分布的にロバストなK-meansクラスタリング
arXiv stat.ML / 2026/4/14
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、K-meansの外れ値への脆弱性、分布シフト、小標本に対する弱さに対処するため、経験分布のLloyd–Max量子化として再定式化する。
- 真の母集団分布は経験分布の周りにあるWasserstein-2ボールの内部に存在すると仮定し、最悪の場合の期待二乗距離を最小化する最小-最大（minimax）問題として、分布的にロバストなK-meansの目的関数を導入する。
- 著者らは、扱いやすい（tractable）双対問題を導出し、それにより、ハードな割当ではなく滑らかに重み付けされた割当を行うソフト・クラスタリング手法を得る。
- 目的関数の単調な減少が証明された、効率的なブロック座標降下アルゴリズムを提示し、局所線形収束の保証も与える。
- ベンチマークおよび大規模な合成データセットでの実験により、ノイズや分布的摂動下での外れ値検出の改善と、ロバスト性の向上が示される。
