技術的概要：単純な KNN ベースの異常値検出による堅牢なクラスタリングの達成

問題定義

本論文は、標準的な k-Means クラスタリング目的関数の変種であるRobust k-Means（堅牢な k-Means）問題を取り扱っており、ここではアルゴリズムが異常値の存在に対処しなければならない。$n$ 個の点からなるデータセット $X$、クラスタ数の目標値 $k$、および異常値の予算 $z$ が与えられたとき、残りの点 ($X \setminus Z$) に対する k-Means コストを最小化するような、サイズ $z$ の部分集合 $Z \subseteq X$（異常値）を特定することが目的である。

標準的な k-Means および k-Median の目的関数はノイズに対して極めて敏感であり、単一の遠方の点であっても解を著しく歪ませる可能性がある。Robust k-Means に対する多項式時間の定数倍近似アルゴリズムは存在するが、多くのアルゴリズムは高次の多項式実行時間を要する複雑な線形計画法緩和や、制約を違反する（例えば、$k$ 個を超える中心を使用する、または $z$ 個を超える異常値を除去する）双基準近似に依存している。最近の効率的なアルゴリズムは、準線形時間複雑性を達成するために、しばしば双基準近似に頼っている。

手法

著者らは、驚くほど単純なアプローチを提案する：標準的な k-Means アルゴリズムを適用する前に、K 近傍法（KNN）ヒューリスティックを前処理ステップとして用いて異常値を特定し、除去することである。

中核アルゴリズム

本論文では、異常値除去のスコア付け方法が異なる 2 つのアルゴリズム、OKMeans と OKMeans2 を導入する。

1. OKMeans（バニラ KNN）:

   • 各点 $x$ について、$K = \frac{c+1}{2}z$ となる $K$ 番目の近傍点までの距離を計算する。
   • ここで、$c$ は最適クラスタが大きいという仮定（具体的には、各最適クラスタのサイズが少なくとも $cz$ であること）に関連する定数である。
   • 最大の $K$-NN 距離を持つ $z$ 個の点を除去する。
   • 残った点に対して、標準的な $\beta$-近似 k-Means アルゴリズムを実行する。

2. OKMeans2（集約 KNN）:

   • 対立的な入力（異常値が互いにクラスタリングする可能性がある場合）に対する堅牢性を向上させるため、ある範囲の近傍点までの距離を集約する変種である。
   • 各点 $x$ について、ランク $z+1$ から $cz$ までの近傍点までの距離の和を計算する。
   • 最大の集約スコアを持つ $z$ 個の点を除去する。
   • 残った点に対して、標準的な k-Means アルゴリズムを実行する。

理論的枠組み

分析は、実用的な仮定に依存している：最適解における各クラスタのサイズは、ある定数 $c > 1$ に対して少なくとも $cz$ である。この仮定は、異常値の数と比較してインライアが実質的なグループを形成する現実世界のシナリオを反映している。この仮定の下で、著者らは KNN ベースの除去ステップが、Robust k-Means 問題から標準的な k-Means 問題への定数倍の削減を提供することを証明している。

具体的には：

• OKMeans は $\Phi(c)$-近似削減を達成する。先行研究で一般的な仮定である $c=3$ の特定のケースにおいて、近似比は 9 である。
• OKMeans2 は $\Psi(c)$-近似削減を達成する。$c=3$ の場合、この比率は約 5.98 に改善される。

重要なのは、これらの手法が問題の厳密な制約を遵守している点である：すなわち、多くの既存の効率的なアルゴリズムが双基準緩和を必要とするのに対し、これらは正確に $k$ 個の中心を使用し、正確に $z$ 個の異常値を除去する。

主要な貢献

1. KNN に対する理論的保証: 本論文は、適切にパラメータ化された（$K$ を $z$ に比例させてスケーリングする）古典的な KNN ヒューリスティックが、Robust k-Means に対して強力な近似保証をもたらすことを示す、最初の厳密な理論的分析を提供する。これは、異常値検出ヒューリスティックと堅牢なクラスタリング理論の間のギャップを埋めるものである。
2. 厳密な制約の満足: $O(k)$ 個の中心を使用するか、$(1+\epsilon)z$ 個の異常値を除去する可能性がある先行する効率的なアルゴリズム（TIKMeans など）とは異なり、提案された手法は、定数倍の近似保証を維持しながら $k$ および $z$ の制約を厳密に遵守する。
3. 改善された近似比: 提案された OKMeans2 変種は、$c=3$ の仮定の下で近似比を 9 から 5.98 に改善し、制約を厳密に遵守する手法における以前の既知の最良の削減を上回る。
4. コアセットによるスケーラビリティ: 大規模データセットにおける正確な KNN 距離の計算に伴う $O(dn^2)$ の複雑性に対処するため、著者らはこの手法をコアセット構築と統合する。これにより、実行時間を準線形時間 $O(dkn \log n)$ に削減し、このアプローチを数百万の点にスケーラブルにする。

実験結果

著者らは、500 万点に及ぶ 4 つの実世界データセット（SKIN, SUSY, SHUTTLE, KDDFULL）上で OKMeans および OKMeans2 を評価し、TIKMeans, IKMeans, RobustKMeans++, NKMeans, および標準的な KMeans++ を含む 6 つのベースラインと比較した。

• クラスタリングの品質: 提案された手法は競争力のあるクラスタリングコストを達成し、しばしば洗練されたベースラインと同等かそれ以上の性能を示した。特に、大規模な SUSY-10 データセットにおいて、OKMeans は以前の最先端（TIKMeans）を上回った。
• 実行時間の効率性: KNN ベースのアプローチは優れたスケーラビリティを実証した。SUSY-10 のような大規模データセットにおいて、OKMeans は TIKMeans（約 89.2 秒）および RobustKMeans++（約 74.1 秒）よりも著しく高速（約 12.9 秒）でありながら、高品質な解を維持した。
• パラメータ感度: 手法はパラメータ $c$ の選択（適度な範囲内）に対して堅牢であることが判明した。しかし、実験は、異常値検出の標準である $K$ に小さな固定定数を選択することが、堅牢なクラスタリング目的に対して最適ではないという理論的洞察を確認した。$K$ は異常値の予算 $z$ に比例してスケーリングする必要がある。

意義と主張

本論文は、単純な KNN ベースのヒューリスティックが堅牢なクラスタリングに対して驚くほど効果的であり得ると主張しており、スケーラブルで高品質な堅牢なクラスタリングのために複雑なサンプリング戦略や双基準近似が必要であるという考えに挑戦している。

著者らは以下の点を強調している：

• 異常値検出と堅牢なクラスタリングの間には、以前は見落とされていた直接的なつながりがある。
• 「大きなクラスタ」という仮定で理論的基盤を与えられた KNN ヒューリスティックは、より複雑なアルゴリズムに対する実用的かつ効率的な代替手段を提供する。
• 結果は、異常値検出とクラスタリングの手法を架橋する新たな方向性を示唆しており、実用上の堅牢なクラスタリングアルゴリズムの設計を単純化する可能性がある。

論文は、現在の分析は厳密ではないが、異常値検出と堅牢なクラスタリングの枠組みを統合する将来の作業の基盤を確立していると結論付けている。