Tunny Icon
TunnyDocs

The next-gen Grasshopper optimization tool.

k-means

概要

k-means は、データを kk 個のクラスタに分割する最も基本的なクラスタリング手法です。 各クラスタは「重心（centroid）」で代表され、各点は最も近い重心のクラスタに割り当てられます。 Tunny Dashboard では、目的関数空間、変数空間、その複合空間を対象として実行できます。

アルゴリズム

目的関数（最小化）

クラスタ内二乗和（WCSS: Within-Cluster Sum of Squares）を最小化します：

WCSS=∑k=1K∑xi∈Ck∥xi−μk∥2\text{WCSS} = \sum_{k=1}^{K} \sum_{x_i \in C_k} | x_i - \mu_k |^2

ここで μk\mu_k はクラスタ CkC_k の重心です。

アプリの wcss フィールドについて補足します。 アプリが wcss として報告する値は、上記の WCSS の総和ではなく、最近傍重心への二乗距離の標本平均（WCSS / N）です。 エルボー法への影響はありません。 kk ごとに NN は共通なので、総和の代わりに平均を使っても各 WkW_k が共通の定数 1/N1/N 倍されるだけであり、二次差分の最大位置（推奨 kk）はずれません（elbow.md 参照）。

処理フロー

  1. 初期化：選択した戦略（k-means++ または Deterministic）で初期重心を選びます
  2. 割り当て（Assignment）：各点を最近傍の重心クラスタに割り当てます
  3. 更新（Update）：m_k-means 型の更新式で新しい重心を計算します（単純平均ではありません。詳細は後述します）
  4. 収束判定：新旧の重心配列間のユークリッド距離が許容誤差（1e-5）以下になれば終了します（最大 300 イテレーション）

初期化：2 種類の戦略

Lloyd's アルゴリズム本体（割り当て、更新、収束）は共通であり、初期重心の選び方だけが異なります。 どちらも固定シードで再現できます。

k-means++（デフォルト）

Arthur & Vassilvitskii（2007）が提案した初期化手法です。 ランダム初期化と比べて局所最適解に陥りにくく、収束後の WCSS が平均的に低くなります。

理論的背景

ランダムに初期重心を選ぶと、複数の重心が同じクラスタ内に集中してしまう「偏り」が生じます。 k-means++ はこれを防ぐため、既存の重心から遠い点ほど次の重心に選ばれやすくなるよう確率を設計します。

p(xi)=D(xi)2∑jD(xj)2p(x_i) = \frac{D(x_i)^2}{\sum_j D(x_j)^2} D(xi)D(x_i) は点 xix_i から最近傍の既存重心までのユークリッド距離です。 距離の二乗に比例させることで、近い点の確率を強く抑制し、遠い点を優先的に選びます。

近似保証

初期化のランダム性による最悪ケースを排除でき、期待 WCSS が最適解の O(log⁡k)O(\log k) 倍以内に収まることが証明されています。

E[WCSS]≤8(ln⁡k+2)⋅WCSSopt\mathbb{E}[\text{WCSS}] \leq 8(\ln k + 2) \cdot \text{WCSS}_{\text{opt}}

Tunny Dashboard での挙動

初期重心はシード付き乱数生成器で選ばれます。 シードを nn と kk の組み合わせから導出することで、同じデータ、同じ設定では常に同一の結果が得られます。

Deterministic（決定論的スプレッド）

k-means++ と同じ D² 比例確率のアルゴリズムを使いますが、固定シード（42）を用いるため、常に同一の結果が得られます。

エルボー法による自動 k 推定（Elbow Auto モード）では、この Deterministic 戦略が内部的に使用されます。

k-means++ との違い

k-means++ が n・k から導出したシードを使うのに対し、こちらは常にシード 42 を使用します。 選択アルゴリズム自体は同じですが、シードが定数のため完全な決定論的再現性が得られます。

複数回実行（best-of-10）

同じシードから初期化 → 割り当て → 更新 → 収束という一連の手順を独立に 10 回実行し、その中で inertia（WCSS）が最小の結果を採用します（best-of-10）。 これは k-means++、Deterministic のどちらの戦略にも同様に適用され、局所最適解に陥るリスクを軽減します。

比較まとめ

k-means++ Deterministic
選択方法 D² 比例確率サンプリング D² 比例確率サンプリング（シード固定）
乱数 n・k から導出したシード シード固定 42
再現性 同データ、同 k で同一結果 常に同一結果（シード 42）
理論保証 O(log⁡k)O(\log k) 近似 同じ（アルゴリズムはシード以外同一）
局所最適リスク best-of-10 により低減 best-of-10 により低減。シード固定のため常に同一結果
推奨場面 通常の用途（デフォルト） 完全な決定論が必要な場合

両戦略は選択アルゴリズムも best-of-10 による再実行も共通であり、シードの決め方だけが異なります。 したがって「理論保証」「局所最適リスク」の違いは、どちらを選ぶかの本質的な根拠にはなりません。 データ由来のシードで毎回微妙に異なる結果を許容できるなら k-means++ を、常に同一の結果が必要なら Deterministic を選ぶ、という使い分けになります。

割り当てステップの計算

各点 xix_i を最小二乗距離のクラスタに割り当てます：

label(xi)=arg⁡min⁡k∥xi−μk∥2\text{label}(x_i) = \arg\min_{k} | x_i - \mu_k |^2

二乗距離（平方根を取らない）で比較するため、比較コストが低いです。

更新ステップの計算

Tunny Dashboard は各クラスタ内点の単純平均ではなく、m_k-means 型の更新式を用います。 前ステップの重心を「追加の 1 点」として加算します。

μknew=μkold+∑xi∈Ckxi∣Ck∣+1\mu_k^{\text{new}} = \frac{\mu_k^{\text{old}} + \sum_{x_i \in C_k} x_i}{|C_k| + 1}

空クラスタ（ ∣Ck∣=0|C_k| = 0）では、この式がそのまま μknew=μkold\mu_k^{\text{new}} = \mu_k^{\text{old}} に帰着します。 前ステップの重心がそのまま維持されるのは、特別扱いの分岐ではなく、この更新式から自然に導かれる結果です。

収束保証と終了条件

条件 説明
重心の許容誤差 新旧の重心配列間のユークリッド距離が 1e-5 以下になれば収束とみなす
最大イテレーション 収束しない場合は 300 回で強制終了
WCSS の計算 収束時または強制終了時に算出する（実体は WCSS の総和ではなく標本平均。上記参照）

Lloyd's アルゴリズムは WCSS が単調減少することは保証されていますが、大域的最適解への収束は保証されません（局所最適に陥る可能性があります）。 初期重心の選択がこの結果を左右します。

Tunny Dashboard での設定値

パラメータ 値 意味
最大イテレーション 300 最大イテレーション数
独立実行回数 10 独立実行回数（best-of-10、inertia 最小を採用）
距離指標 ∑(aj−bj)2\sum (a_j - b_j)^2 距離指標（二乗ユークリッド）
空クラスタ 前重心を維持 m_k-means 更新式の帰結（上記参照）

特性と限界

強み

  • シンプルで計算が高速
  • 解釈が直感的（各点が最近傍の重心クラスタに属します）
  • WCSS で解の品質を定量評価できます

弱み

  • クラスタ数 kk を事前に指定する必要があります（エルボー法で自動推定可能）
  • 凸状・球形のクラスタ形状を前提とします（三日月形などは苦手）
  • 外れ値に感受性が高いです（重心が外れ値に引っ張られます）
  • 局所最適解に収束する可能性があります

入力空間の選択

Tunny Dashboard では 3 種類の入力空間を選択できます：

設定 使用するフィーチャー 適した用途
Objective Space 目的関数値のみ 性能空間でのクラスタ分析
Variable Space パラメータ値のみ 設計変数空間でのクラスタ分析
Combined 目的関数 + パラメータ 両空間を統合した分析

参考文献

← 前へクラスタリング: 概要次へ →クラスタリング: エルボー法