クラスタリングで最適なクラスタ数を決める方法～エルボー法とシルエットスコア～

この記事で学べること

みなさん、こんにちは。りゅう9です。この記事ではクラスタリングにおいて最適なクラスタ数を決める方法としてエルボー法やシルエットスコアを使った方法を解説します。

なぜクラスタ数を決める必要があるのか

クラスタリングでは、どうやってクラスタ数を決定するか？が大きな課題となります。k-means法やk-medoids法では初めにクラスタ数を指定してからクラスタリングを始めます。しかし、未知のデータでは、このデータがいくつのクラスタに分類できるかは予想できません。そこで、客観的な指標を用意することが必要となります。

準備 (SSEとシルエットスコアの計算方法)

まず、準備としてSSEとシルエットスコアの計算方法について解説します。

SSE (Sum of Squared Errors, クラスタ内誤差平方和)

SSEはクラスタリングの性能評価に使われる指標で、エルボー法に使用されます。これは、各データ点とその点が所属するクラスタの重心（セントロイドやメドイド）との距離の2乗の総和のことです。式で表すと以下のようになります。クラスタ数を$k$, 各クラスタを$C_j$とすると、

$$\text{SSE} = \sum_{j=1}^{k} \sum_{x_i \in C_j} \| x_i - \mu_j \|^2$$

となります。ここで、$x_i$はデータ点、$\mu_j$はクラスタ$C_j$の重心です。

例えば、Fig. 1のようなデータがあった時のSSEは以下のようになります。

• $クラスタ0: 16+9+25 = 50$
• $クラスタ1: 9+9+4+1=23$
• $SSE = クラスタ0+クラスタ1= 73$
  
  Fig. 1 SSE

SSEは計算式からわかる通り、クラスタ内の点がどれだけ重心から近いかを測る指標です。
SSEが大きいと、バラバラに散らばっているクラスタ、SSEが小さいと固まったクラスタといったイメージです。

シルエットスコア (Silhouette Score)

シルエットスコアもクラスタリングの性能評価のための指標です。シルエットスコアによって、クラスタ内の凝集度とクラスタ間の分離度をバランスよく評価することが出来ます。シルエットスコアは-1から1までの値をとり、1に近いほど良いクラスタリングができていると解釈します。式で表すと以下のようになります。

$$s_i = \frac{b_i-a_i}{max(a_i, b_i)}$$

ここで、$a_i$は同じクラスタ内の平均距離 (凝集度)、$b_i$は最も近い別のクラスタとの平均距離 (乖離度) です。すべての点についてシルエットスコアを計算して、その平均をデータ全体のシルエットスコアとして最終の指標とします。

Fig. 2で具体的な例を見てみます。3つのクラスタがあるとき、クラスタ0内の1つの点のシルエットスコアを求めます。今回はクラスタ0内の点についてシルエットスコアを求めるので、クラスタ0内のほかの点との距離の平均を求めてそれを$a_i$とします (Fig. 2では青線)。また、ほかのクラスタ (クラスタ1, 2) 内の点のうち最も近い点との距離をそれぞれ求めて、その平均をとったものを$b_i$とします (Fig. 2では赤線)。

Fig. 2 シルエットスコア

計算式やイメージ図からわかるように、シルエットスコアは、1に近いほどクラスタ内にしっかりと属していて、0付近であるときは2つのクラスタの境界にいて、-1に近いほど違うクラスタに入れた方が良いと解釈できます。

エルボー法

エルボー法は、クラスタ数を増やしながらSSEを計算し、それをプロットして最適なクラスタ数を見つける手法です。SSEの計算式などからわかる通り、クラスタ数を増やすと、クラスタが細かく分かれるためSSEは必ず減少します。クラスタ数を増やせば増やすほど、際限なく減っていくため、最小値を選ぶのは適切とは言えません。そこで、SSEをプロットしてみて、減少が鈍化する点を選びます。
具体例をFig. 3に示します。

Fig. 3 エルボー法

エルボー法では横軸にクラスタ数、縦軸にSSEをとって描画します。今回の例を見ると、クラスタ数 (k) が4を超えたあたりから、SSEの減少が鈍化しているように見えます。つまり、今回の例では4をクラスタ数として選ぶのが最適と判断します。ちなみに、このグラフの形が曲げた肘にみえることからエルボー法と呼ばれます。

シルエットスコアの図示

シルエットスコアもエルボー法と同じようにクラスタ数を増やしたときの値を図示することで最適なクラスタ数を見つけることが出来ます。Fig. 4に疑似的に描画した様子を載せます。(実際にクラスタリングして評価した結果ではないことに注意してください)

Fig. 4 シルエットスコア

Fig. 3とFig. 4を合わせてみることで、最適なクラスタ数を見つけることが出来ます。エルボー法のグラフでSSEの減少が鈍化し、シルエットスコアのグラフでスコアが最大なクラスタ数が最適です。

Fig. 3, 4のようなグラフが理想的な形です。しかし、実際のデータではこのようにきれいにならないことが多いです。

注意点

各クラスタ数でクラスタリングをすることになるので、実行には時間がかかります。また、各クラスタ数においても複数回クラスタリングして、最も良いSSEやシルエットスコアとなった時を採用するようにすると良いです。k-means法やk-medoids法ではランダムに初期値を選ぶため、この選び方によってはクラスタリングがうまくいかないことも多いからです。
各クラスタ数で100回クラスタリングして、クラスタ数2~11で試したとすると、合計1000回のクラスタリングをすることになります。

まとめ

クラスタリングの手法の、k-means法やk-medoids法で最適なクラスタ数を決める方法としてエルボー法やシルエットスコアを参照する方法を見てきました。最適なクラスタ数を見つけることはクラスタリングを成功させるためにはとても重要です。
この記事に誤りがありましたらご指摘ください。
最後までお読みいただきありがとうございました。