Tunny Icon
TunnyDocs

The next-gen Grasshopper optimization tool.

エルボー法

概要

エルボー法は、k-means クラスタリングの最適なクラスタ数 kk を自動推定する手法です。 kk を変化させたときの WCSS（クラスタ内二乗和）の変化率が急激に鈍化する「肘（elbow）」の点を最適 kk とみなします。

Tunny Dashboard では「Elbow (Auto)」モードで自動推定を行い、ユーザーが手動指定しなくても適切な kk を選択できます。

本ページでは、この推定を WCSS の収集、二次差分の計算、推奨 kk の決定という 3 ステップに分けて説明します。

理論背景

WCSS の挙動

クラスタを増やすほど各点は近い重心を持てるため、$k$ を増やすにつれて WCSS は必ず単調減少します。 k=Nk = N（点と同数）にすれば各点が自分自身の重心になるので WCSS は 0 になりますが、それは 1 点ずつに分けただけで、まとまりを見つけたことにはなりません。

k=1⇒WCSS 最大→k↑k=N⇒WCSS=0k = 1 \Rightarrow \text{WCSS 最大} \quad \xrightarrow{k\uparrow} \quad k = N \Rightarrow \text{WCSS} = 0

つまり WCSS の小ささだけを基準にすると、$k$ はいくらでも大きくできてしまいます。

そのため、値そのものではなく減り方の変化を見ます。

「十分な分割効果」が得られる点を超えると、WCSS の減少量は急速に小さくなります。

この屈曲点がエルボーであり、過剰分割（過学習的クラスタリング）を避けた適切な kk とみなされます。

アルゴリズム

ステップ 1：WCSS の収集

k=2,3,…,kmax⁡k = 2, 3, \ldots, k_{\max} のそれぞれで k-means を実行し、WCSS を記録します：

Wk=WCSS(k)(k=2,…,kmax⁡)W_k = \text{WCSS}(k) \quad (k = 2, \ldots, k_{\max})

このとき各 kk の k-means を Deterministic 戦略で初期化することで、同じデータであれば何度実行しても同じ WCSS 列が得られます（kmeans.md 参照）。 kmax⁡=min⁡(N,  Max k 設定値)k_{\max} = \min(N,; \text{Max k 設定値}) です。

上限のデフォルトは 10 で、k 選択が Elbow (Auto) のとき、クラスタウィジェットの「Max k」（範囲 2〜50）で変更できます（$N$ はトライアル数）。

Max k を引き上げると k-means の実行回数もそのぶん増えるので、トライアル数が多い場合は実行時間に注意してください。 WkW_k の実体について補足します。

ここで収集される各 WkW_k の実体は、最近傍重心への二乗距離の標本平均（WCSS / N）であって、WCSS の総和ではありません（kmeans.md の該当注記を参照）。

ですが、$N$ はどの kk を試しても共通なので、これは各 WkW_k を共通の定数 1/N1/N 倍するだけであり、後述する二次差分の最大位置には影響しません。

ステップ 2：二次差分の計算

WCSS 列の二次有限差分を計算します：

Δ2Wi=Wi−2Wi+1+Wi+2(i=0,1,…)\Delta^2 W_i = W_i - 2W_{i+1} + W_{i+2} \quad (i = 0, 1, \ldots)

インデックス ii の Δ2Wi\Delta^2 W_i は、位置 k=i+3k = i + 3 における曲線の「曲がり具合（凹性）」を表します。

二次差分は一次の変化（傾き）を打ち消すため、WCSS が一定の割合で減り続けているあいだは 0 に近いままです。

直線では Δ2W=0\Delta^2 W = 0 となり、エルボー点では Δ2W\Delta^2 W が最大となります。

ステップ 3：推奨 kk の決定

k^=arg max⁡i  Δ2Wi  +  3\hat{k} = \operatorname*{arg,max}_{i}; \Delta^2 W_i ;+; 3 +3+3 のオフセットは、$k = 2$ から始まる WCSS インデックスと二次差分インデックスのずれによります。

変数 kk との対応
W0W_0 k=2k = 2
Δ2W0\Delta^2 W_0 k=2,3,4k = 2, 3, 4 の 3 点を使用 → 肘は k=3k = 3（ =0+3= 0 + 3）
Δ2Wi\Delta^2 W_i 肘は k=i+3k = i + 3

推定 kk は [2,  kmax⁡][2,; k_{\max}] の範囲にクランプされます。

具体例

たとえば k=2,3,4,5k = 2, 3, 4, 5 での WCSS が以下のようになったとします。

kk WCSS
2 1000
3 400
4 350
5 340

二次差分：

Δ2W0=1000−2×400+350=150(肘候補: k=3)\Delta^2 W_0 = 1000 - 2 \times 400 + 350 = 150 \quad \text{(肘候補: } k=3\text{)}

Δ2W1=400−2×350+340=40\Delta^2 W_1 = 400 - 2 \times 350 + 340 = 40 Δ2W0\Delta^2 W_0 が最大のため、推奨 k=0+3=3k = 0 + 3 = 3 です。

WCSS は k=2k = 2 から 3 にかけて 1000 から 400 へ大きく下がり、そこから先はほとんど下がっていません。

表の値を見ても折れ曲がりは k=3k = 3 にあり、二次差分による推定もそこを指しています。

特殊ケース

トライアル数が少ない場合や点が退化している場合は、上記の手順をそのまま適用できません。

これらのケースでは、次のようにフォールバックします。

ケース 動作
kmax⁡<2k_{\max} < 2 WCSS を計算せず、 k^=2\hat{k} = 2 を返す
試行数が 2 以下（差分列が短い） 二次差分を計算せず、 k^=試行数+1\hat{k} = \text{試行数} + 1 を返す
全点が 1 点に重なる（距離 ≈0\approx 0） 重複回避フォールバックで後続の点を重心として使用

強みと限界

強み

  • ユーザーが kk を指定しなくてよい
  • 計算コストが低い（ kmax⁡k_{\max} 回の k-means 実行で完了）
  • 二次差分は線形トレンドをキャンセルし、曲率だけを評価するため頑健

限界

  • WCSS が滑らかに減少しエルボーが不明瞭なデータでは、推定精度が下がる
  • クラスタが自然に存在しないデータ（一様分布など）では、過剰な kk を推奨する場合がある
  • kmax⁡k_{\max} のデフォルトは 10。より多くのクラスタ数が必要なデータでは、「Max k」設定（最大 50）を引き上げることで真のエルボーを探索範囲に含められる（k-means の実行回数は増える）

エルボー法が返すのは、あくまで WCSS 曲線の曲がりが最大になる位置です。

データに明確なまとまりがない場合でも、曲線のどこかが最も曲がっている以上、何らかの kk が返ってきます。

推定結果が不自然なとき

エルボー法の推定が直感と合わない場合は、「Manual」モードに切り替えて kk を直接指定します。

その際は、WCSS が急激に下がる kk の直後を選び、解釈性を重視する場合は小さい kk を優先するとよいです。

クラスタ数に唯一の正解があるわけではありません。

いくつかの kk を試して、解釈しやすい分割を選ぶという進め方でも構いません。

参考文献

← 前へクラスタリング: k-means次へ →統計