K-mediansクラスタリング入門：L1ノルムと中央値で外れ値に強い手法の基礎とK-means・K-medoidsとの比較
エバープレイ編集部K-medians とは — 概要と基本概念
K-medians（ケイ・メディアンズ）はクラスタリング手法の一つで、クラスタ中心（センター）を各クラスタ内の「中央値（median）」で定め、データ点と中心との距離和（L1ノルム：マンハッタン距離）を最小化することを目的とします。k-means が二乗誤差（L2ノルムの二乗和）を最小化するのに対して、k-medians は絶対誤差（L1ノルム）に基づくため、外れ値に対してよりロバスト（頑健）という特徴があります。
目的関数と数学的定義
n 個のデータ点 x_i ∈ R^d を k 個のクラスタに分割し、各クラスタ C_j に中心 m_j を割り当てるとき、k-medians の目的は次を最小化することです：
sum_{j=1..k} sum_{x in C_j} ||x - m_j||_1
ここで ||·||_1 は L1 ノルム（全次元の絶対差の和）。各クラスタの最適な m_j は、L1 ノルム下では各次元ごとの中央値（coordinate-wise median）が最小化解となります。そのため、更新ステップで各次元ごとにデータの中央値を計算すれば良い、という簡便さがあります（ただし重み付きデータの場合は重み付き中央値を使います）。
k-medians と k-means / k-medoids の違い
- k-means：目的は平方和誤差（sum of squared Euclidean distances）。最適センターは各クラスタの平均（mean）。L2 に敏感で外れ値に弱い。
- k-medians：目的は L1 距離の和。最適センターは各次元ごとの中央値。外れ値に対して比較的ロバスト。
- k-medoids：各クラスタの代表点（medoid）としてクラスタ内の実データ点をセンターにする手法。任意の距離行列が使え、センターは実在データ点に限定される点で k-medians と異なる。
アルゴリズム（Lloyd 型の反復法）
k-medians の基本的な反復アルゴリズムは k-means の Lloyd アルゴリズムに似ています。
- 初期化：k 個の初期中心を選ぶ（ランダム選択、k-means++ に類似した確率的手法など）。
- 割り当てステップ：各データ点を最も近い中心（L1 距離）に割り当てる。
- 更新ステップ：各クラスタの中心をそのクラスタ内の各次元ごとの中央値に更新する。
- 収束判定：割り当てが変化しなくなるか、目的関数の変化が閾値以下になるまで繰り返す。
この手順は必ず目的関数を単調に減少させるため、有限回のステップで局所最適解に収束しますが、全体最適（グローバル最小）は保証されません。
計算量と実装上の注意
- 1 回のイテレーションの計算量は割り当てステップが O(n k d)、更新ステップで中央値を求めるのがクラスタごとにソートなどを用いると O(n d log n) になることがあり得ます。一般的には O(n k d) が支配的。
- 高次元データでは「各次元ごとの中央値」を取ることで計算は比較的単純になるが、次元ごとに独立に最小化することが適切でない場合（次元間の依存が強い場合）には注意が必要。
- 初期化に依存するため、複数回ランダム再初期化して最良解を選ぶのが実務的。
ロバスト性と適用領域
- 外れ値に対して k-means（平均を使う）より頑健。特に L1 は外れ値の影響を抑えられる。
- 特徴がスパースまたは重み付けが重要な場合、L1 は有効。例えばテキストの Bag-of-Words（頻度データ）や異常値が混在する計測データなど。
- カテゴリカルデータや任意距離を使いたい場合は k-medoids や専用の手法が適しており、k-medians が最適とは限らない。
離散 k-median（施設配置問題）との関係
注意点として、機械学習での k-medians（連続空間での中央値更新）と離散最適化問題としての「k-median 問題」は用語が混在しやすいです。離散 k-median 問題は限られた候補位置から k 個を選んで距離和を最小化する組合せ最適化問題で、こちらは NP-hard であり多くの近似アルゴリズム（局所探索、LP 緩和、ラウンディング手法など）が研究されています。機械学習で実装する k-medians（連続型の反復法）も一般には NP-hard な最適化問題の近似解を求める手法になります。
実務での注意点と前処理
- スケーリング：L1 距離でもスケールの異なる特徴があると距離計算に偏りが生じる。標準化や正規化が有効。
- 欠損値処理：中央値は欠損に対して扱いやすい（中央値で補完する等）だが、欠損が多い場合は注意が必要。
- 次元削減：高次元では距離の集中現象（curse of dimensionality）が起こるので、必要に応じて PCA や特徴選択を行う。
- 初期化方法：k-means++ の考え方を L1 距離に合わせて応用することで初期中心の選び方を改善できる。
利点・欠点の整理
- 利点
- 外れ値に対して比較的ロバスト
- 更新が中央値で明確、特に 1 次元ごとの解が効率的に求められる
- L1 に基づく評価指標が自然なデータで有効
- 欠点
- 局所最適に陥りやすく、初期化依存性がある
- 高次元や次元間依存が強い場合は中央値が適切でない可能性
- 離散版の k-median 問題は計算量的に困難（NP-hard）
関連アルゴリズムと実装ライブラリ
- k-medoids（PAM, CLARA, CLARANS 等）：任意距離行列に対して堅牢に動作し、代表点が実データ点となる。
- 近似アルゴリズム（離散 k-median）：局所探索法や LP 緩和を用いた定数近似アルゴリズムが理論的に研究されている。
- 実装例：Python では pyclustering が k-medians を実装、scikit-learn には直接の k-medians はないが、scikit-learn-extra に KMedoids がある。R でも複数のクラスタリングパッケージで類似手法が使える。
実践例・ユースケース
- 物流や配達拠点の配置（マンハッタン距離が適切な都市格子上の距離モデル等）
- センサーデータや異常値を含む計測データのクラスタリング
- テキストや頻度データのクラスタリング（スパースで L1 性質が有効）
まとめ
k-medians は L1 ノルムに基づくクラスタリング手法で、中央値を中心に用いることで外れ値に強く、特定のデータ特性（スパース性や重み付け）に対して有効です。k-means と似た反復アルゴリズムで実装できますが、初期化や高次元データへの適用、離散版の NP-hard 性など実務上の注意点もあります。目的に応じて k-means、k-medians、k-medoids、あるいはより高度な近似アルゴリズムを使い分けることが重要です。
参考文献
- K-medians clustering — Wikipedia
- K-medoids — Wikipedia
- K-means clustering — Wikipedia
- Geometric median — Wikipedia
- k-median problem (Facility location) — Wikipedia
- Arthur, D. and Vassilvitskii, S., "k-means++: The Advantages of Careful Seeding" (k-means++ 論文)
- pyclustering — Python library (k-medians 実装あり)
- scikit-learn — 機械学習ライブラリ（関連アルゴリズム・参照用）
投稿者プロフィール
