Tunny Icon
TunnyDocs

The next-gen Grasshopper optimization tool.

k-means

概要

k-means は、データを kk 個のクラスタに分割する最も基本的なクラスタリング手法です。

各クラスタは「重心（centroid）」と呼ばれる 1 点で代表され、各点は最も近い重心のクラスタに割り当てられます。

クラスタをこの 1 点だけで表すことで、アルゴリズムは重心を求める処理と各点を割り当て直す処理の繰り返しに帰着します。

Tunny Dashboard では、目的関数空間、変数空間、その複合空間を対象として実行できます。

本ページでは、この k-means が最小化している量と処理フロー、そして 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 の総和ではなく、最近傍重心への二乗距離の標本平均（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 アルゴリズム本体（割り当て、更新、収束）は共通であり、初期重心の選び方だけが異なります。

後述するように Lloyd's アルゴリズムは局所最適解に収束することがあるため、どこから始めるかによって行き着く解が変わります。

そのため Tunny Dashboard では、初期重心の選び方を 2 つの戦略から選べるようになっています。

どちらも固定シードで再現できます。

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）を用いるため、常に同一の結果が得られます。

エルボー法は kk を変えながら k-means を繰り返し実行し、その WCSS を比べて肘を探します。

実行のたびに結果が揺れると WCSS の比較そのものが成り立たなくなるため、自動 kk 推定（Elbow Auto モード）ではこの Deterministic 戦略が内部的に使用されます。

k-means++ との違い

k-means++ が n・k から導出したシードを使うのに対し、こちらは常にシード 42 を使用します。

選択アルゴリズム自体は同じですが、シードが定数のため完全な決定論的再現性が得られます。

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

同じシードから初期化 → 割り当て → 更新 → 収束という一連の手順を独立に 10 回実行し、その中で inertia（WCSS）が最小の結果を採用します（best-of-10）。

10 回のうち最も WCSS の小さい解を選ぶことで、たまたま悪い初期値から始まった実行の影響を受けずに済みます。

これは 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}

前ステップの重心を 1 点として含めることで、新しい重心は各クラスタ内点の平均と前ステップの重心のあいだに置かれます。

空クラスタ（ ∣Ck∣=0|C_k| = 0）では、この式がそのまま μknew=μkold\mu_k^{\text{new}} = \mu_k^{\text{old}} に帰着します。

前ステップの重心がそのまま維持されるのは、特別扱いの分岐ではなく、この更新式から自然に導かれる結果です。

収束保証と終了条件

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

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

どの局所最適に落ち着くかは初期重心の選択で決まるため、前述の初期化戦略と best-of-10 が効いてきます。

Tunny Dashboard での設定値

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

特性と限界

強み

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

弱み

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

球形を前提とする点と外れ値に弱い点は、どちらもクラスタを重心という 1 点で代表することから来ています。

たとえば三日月形に並んだ 2 つのまとまりは、重心からの距離だけを見ても分けられません。

こうした構造が疑われる場合は、Dendrogram や SOM Map のように別の原理に基づく手法と見比べてみると、判断がつくこともあります。

入力空間の選択

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

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

k-means は距離だけを見るため、どの列を入力に渡すかで結果は大きく変わります。

そのため、性能が似た設計を探したいのか、設計変数のパターンを見たいのかを決めてから入力空間を選んでください。

参考文献

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