第10回　k-means①：クラスタ内分散最小化¶

本日の到達目標¶

k-meansの目的関数（クラスタ内分散の最小化）を数式で説明できる
k-meansアルゴリズムの各ステップを追うことができる
PCA出力を入力とした場合の利点と手順を説明できる
発展：重心が平方和を最小にする点であることを導き、Lloyd's アルゴリズムの各ステップで WCSS が増えないことを示せる

1. クラスタリングとは¶

1.1 クラスタリングの位置づけ¶

教師なし学習：正解ラベル（目的変数 $y$）なしに、データの構造を発見する

分析	目的変数	手法例
重回帰（第6・7回）	あり（連続値）	OLS
PCA（第8・9回）	なし	分散最大化
k-means（今回）	なし	クラスタ内分散最小化
PLS（第12・13回）	あり（連続値）	共分散最大化

クラスタリングの目的：データを「似た者同士のグループ（クラスタ）」に分割する

1.2 応用例¶

分野	応用
マーケティング	顧客セグメンテーション（優良客・離反リスク客等）
小売	購買パターンによる店舗分類
製造	センサーデータによる設備の稼働パターン分類
医療	患者の症状プロファイルによる類型化

2. k-meansの目的関数¶

2.1 問題設定¶

$n$ 個のデータ点を $k$ 個のクラスタ $C_1, C_2, \ldots, C_k$ に分割する。

目的関数：Within-cluster Sum of Squares（WCSS）

\[WCSS = \sum_{j=1}^{k} \sum_{\mathbf{x}_i \in C_j} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2\]

$\boldsymbol{\mu}_j$：クラスタ $j$ の重心（centroid）= クラスタ内のデータ点の平均
$\|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2$：データ点と重心の距離の二乗

目標：WCSSを最小化するクラスタ割り当てと重心を求める

【カードに記入・3分】：WCSSが小さいとき、クラスタはどのような形状・特性を持つか考えてください。

導出①：なぜ代表点が「平均」なのか

WCSS の定義に $\boldsymbol{\mu}_j$ =「クラスタ内の平均」と最初から書きましたが、なぜ平均なのかは説明していません。実は平均は選んだのではなく、平方和を最小にする点を求めたら平均になったのです。

クラスタ $C$ に属する点を固定し、代表点 $\mathbf{c}$ を自由に動かして平方和を考えます。クラスタ内平均を $\boldsymbol{\mu} = \frac{1}{|C|}\sum_{\mathbf{x}_i \in C}\mathbf{x}_i$ とおき、$\mathbf{x}_i - \mathbf{c} = (\mathbf{x}_i - \boldsymbol{\mu}) + (\boldsymbol{\mu} - \mathbf{c})$ と分けて展開します。

\[\sum_{\mathbf{x}_i \in C}\|\mathbf{x}_i - \mathbf{c}\|^2 = \sum_i \|\mathbf{x}_i - \boldsymbol{\mu}\|^2 + 2(\boldsymbol{\mu}-\mathbf{c})^T\sum_i(\mathbf{x}_i - \boldsymbol{\mu}) + |C|\,\|\boldsymbol{\mu}-\mathbf{c}\|^2\]

真ん中の交差項は $\sum_i (\mathbf{x}_i - \boldsymbol{\mu}) = \mathbf{0}$ なので消えます（平均からの偏差の和はゼロ）。残るのは

\[\sum_i \|\mathbf{x}_i - \mathbf{c}\|^2 = \underbrace{\sum_i \|\mathbf{x}_i - \boldsymbol{\mu}\|^2}_{\mathbf{c} \text{ によらない}} + \underbrace{|C|\,\|\boldsymbol{\mu}-\mathbf{c}\|^2}_{\geq 0}\]

第2項は $\mathbf{c} = \boldsymbol{\mu}$ のときだけゼロです。したがって平方和を最小にする代表点は平均であり、どこにずらしても必ず増えます。

これは統計学Ⅰ第2回の「平均は二乗のズレの合計を最小にする点」とまったく同じ式です。1次元で見た性質が、そのまま多次元のクラスタ重心になっています。

数値で確かめる：7点 $(1,1), (1.5,2), (3,4), (5,7), (3.5,5), (4.5,5), (3.5,4.5)$ の重心は $(3.142857,\ 4.071429)$、そのときの平方和は $37.071429$ です。重心を $x$ 方向に $+0.3$ ずらすと $37.701429$、$-0.3$ ずらしても $37.701429$、$+0.7$ では $40.501429$ と、いずれも増えました。増加分は上の式の第2項 $|C|\|\boldsymbol{\mu}-\mathbf{c}\|^2 = 7 \times 0.09 = 0.63$ と一致します。

使った数学：平方完成、偏差の和がゼロになること。

2.2 重回帰のRSSとの比較¶

手法	目的関数	最小化する対象
重回帰（OLS）	RSS = $\sum(y_i - \hat{y}_i)^2$	実測値と予測値の差
k-means	WCSS = $\sum\sum\\|\mathbf{x}_i - \boldsymbol{\mu}_j\\|^2$	データ点と重心の距離

共通点：どちらも「残差（距離）の二乗和」を最小化する枠組み

3. k-meansアルゴリズム¶

3.1 Lloyd's アルゴリズム（標準的実装）¶

初期化：$k$ 個の重心をランダムに選ぶ

繰り返し（収束まで）： 1. 割り当てステップ（E-step的）：各データ点を最も近い重心のクラスタに割り当てる $$c_i = \arg\min_{j} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2$$

更新ステップ（M-step的）：各クラスタの重心を更新する $$\boldsymbol{\mu}_j = \frac{1}{|C_j|} \sum_{\mathbf{x}_i \in C_j} \mathbf{x}_i$$

収束判定：クラスタ割り当てが変化しなくなったとき（またはWCSSの変化が閾値以下）

導出②：なぜ必ず止まるのか、そしてなぜ最良とは限らないのか

2つのステップを繰り返すだけで止まる保証があるのは、どちらのステップも WCSS を増やさないからです。

割り当てステップ：各点 $\mathbf{x}_i$ を、最も近い重心のクラスタに付け替えます。付け替え後の $\|\mathbf{x}_i - \boldsymbol{\mu}_{c_i}\|^2$ は、定義から今までの値以下です。点ごとに減るか同じなので、合計である WCSS も増えません。

更新ステップ：割り当てを固定して重心を動かします。導出①より、平方和を最小にするのはクラスタ内平均です。今の重心は平均ではないかもしれませんが、平均に置き換えれば必ず以下になります。よって WCSS は増えません。

つまり WCSS は反復のたびに単調非増加で、かつ $0$ 以上で下に有界です。さらに、$n$ 個の点を $k$ 個に分ける分け方は高々 $k^n$ 通りの有限個しかありません。同じ割り当てが再び現れた時点で値は動かなくなるので、有限回で必ず停止します。

数値で確かめる：上の7点を $k=2$、初期重心 $(1,1), (2,2)$ で回しました。

反復	割り当て後 WCSS	重心更新後 WCSS
1	74.250000	20.708333
2	11.284722	8.525000
3	8.525000	8.525000（収束）

一度も増えずに3反復で止まりました。

ただし、止まることと、一番良い答えに止まることは別です。 上の議論が保証するのは「もうどちらのステップでも改善できない状態に達する」ことだけで、それが全分割の中で WCSS 最小である保証はありません。初期重心の置き方次第で別の停止点に落ちます。この問題への対処が次回の k-means++ です。

この授業で扱う範囲外：WCSS を厳密に最小化する分割を求める問題の計算量（この問題が NP 困難であること）の議論。ここでは「大域最適は保証されない」という事実だけを使います。

使った数学：単調非増加で下に有界な列は止まること、分割が有限個であること。

3.2 アルゴリズムの視覚的理解¶

初期化: ×=重心         ステップ1: 割り当て        ステップ2: 重心更新

  ×          ×           ○○  ×  ○            ○○   ×   ○
  ○ ○  ○ ○  ×           ●●  ×  ●●           ●● ×→   ●●
  ○    ×   ○            ●●     ●●            ●●      ●●
        ×                 × ×                 ↓×  ↑×

繰り返すことで重心が真のクラスタ中心に収束する。

3.3 計算量¶

1反復あたり：$O(nkd)$（$n$：データ点数、$k$：クラスタ数、$d$：次元数）

収束まで $T$ 回繰り返すとして：$O(TnkD)$

次元 $d$ が大きい場合：PCAで次元削減してから k-means を適用することで計算を削減

4. PCAとk-meansのパイプライン¶

4.1 なぜ PCA 後に k-means を使うか¶

問題点（高次元直接適用時）： - 次元の呪い：次元が増えると全てのデータ点が互いに「同じ距離」になる傾向 - 時間窓特徴量間の共線性が距離計算を歪める - 可視化が困難（2D/3Dで見られない）

PCA後の利点： - 主成分は互いに直交（共線性なし） - 上位2〜3主成分で2D/3Dプロットができる - 次元を減らすことで k-means の計算が速い

4.2 パイプラインの設計¶

時間窓特徴量行列 X（高次元）
      ↓ 標準化
      ↓ PCA（例：上位 k=10 主成分）
主成分スコア Z（低次元）
      ↓ k-means
クラスタラベル c
      ↓ 解釈・可視化
散布図（PC1 vs PC2、色=クラスタ）

4.3 標準化の重要性¶

k-means は距離ベースの手法 → スケールの違いが距離を歪める

例： - 移動平均7日（単位：万円、値域：0〜500） - 来店頻度（単位：回、値域：0〜30）

標準化なしでは売上の差異が距離を支配し、頻度の違いが無視される。

→ PCA の前に必ず標準化（PCA自体も標準化を前提としていた: 第9回）

5. クラスタの解釈¶

5.1 クラスタの特性把握¶

各クラスタの重心 $\boldsymbol{\mu}_j$ の成分（元の変数空間に戻した場合）を比較する。

クラスタ	移動平均7日	来店頻度	直近値	解釈
C1	高	高	高	常連・高売上客
C2	低	高	低	頻繁だが少額
C3	中	低	高	直近に活性化

5.2 散布図（PC1 vs PC2）での可視化¶

PC2 ↑     ●●
    |   ●●       ▲▲▲
    |  ●●    ▲▲▲▲▲
    |       ▲▲       ■■■
    |            ■■■■■
    ├──────────────────→ PC1
    ●=C1   ▲=C2   ■=C3

クラスタが重なっていない → 分離がよい。重なりが多い → k を増やすか特徴量を見直す。

6. 基盤リンクの整理¶

基盤概念	本回での役割	具体的な使い方
列指向	反復更新に必要な特徴列を高速供給	各反復で必要な特徴行列を低コストで読み直す
整合性	学習データ固定でクラスタ比較を可能に	異なる k の比較で同じデータを使う
DAG	PCA→k-means→評価の流れを固定	パイプラインを変えずにkだけ変えて比較
近似	初期当たりを近似で付けて探索を速く	k-means++ やミニバッチで高速化（第11回）

7. 本日のまとめ¶

k-means の目的関数は WCSS（クラスタ内分散の和）の最小化
アルゴリズムは「割り当て→重心更新」の繰り返しで収束（Lloyd's法）
高次元特徴行列には PCA → 標準化 → k-means のパイプラインが有効
クラスタの解釈は重心の値を元の変数空間で比較することで行う

次回予告¶

第11回では k-means②：初期値依存性の問題とミニバッチ処理によるスケール対応、そしてシルエット分析によるクラスタ数の選択を学ぶ。

事後課題¶

以下の問いに答えること（A4 半枚）：

k-means の WCSS と重回帰の RSS の数式上の共通点・相違点を比較してください。
2次元（$k=2$）の単純な例で、Lloyd's アルゴリズムの最初の2反復を手計算で追ってください（座標は自分で設定してよい）。

手法	目的関数	最小化する対象
重回帰（OLS）	RSS = \(\sum(y_i - \hat{y}_i)^2\)	実測値と予測値の差
k-means	WCSS = \(\sum\sum\\|\mathbf{x}_i - \boldsymbol{\mu}_j\\|^2\)	データ点と重心の距離

第10回 k-means①：クラスタ内分散最小化¶