TechFULの中の人

triple-four’s blog

機械学習の基礎②(k-means法)

こんにちは!TechFULでアルバイトしているあたかです. 今回はk-means法について解説します!


k-means法とは?

 いままで紹介した機械学習の方法では,回帰や分類をおこなうときに教師信号としてデータにラベル付けされていました.ラベル付けされていれば教師あり学習することができます.
 しかし,いつも都合よくラベル付けされているデータばかりであるとは限りません.
 このようにラベル付けされていない場合の学習を,「教師なし学習」といいます. たとえば,顧客情報を年齢や購入金額などの特徴量によってグループ分けすることによって,どの顧客層をターゲットにするかなどの販売戦略に活用することができます.
 k-means法とは,与えられたデータのなかから決まった数のグループに分ける方法の一つです.k-meansは「ケーミーンズ」と読みます.k個の平均という意味です.
 k-means法はラベルのないデータから複数のグループに分ける方法ですが,この分けられたグループのことをクラスタといいます.クラスタとはカタマリという意味です.
 k-means法をおこなうときはあらかじめいくつに分けるかを決めておきます.3個のクラスタに分けるなら,クラスタの重心の初期値としてランダムに3つの点を定めます.このそれぞれの点に一番近いデータを同じクラスタに含めます.
 以下の手順を繰り返すことでグループ分けが完了します.

1. 各データそれぞれについて,一番近い重心のクラスタに分ける.      
2. 新しく分けられたクラスタの重心を求める.

f:id:sanbaiefforts:20190326114523g:plain

k-means法の定式化

 先ほど述べたアルゴリズムを数式を交えて説明します.  N個のデータの集合を $$\boldsymbol{x_1}, \boldsymbol{x_2}, \cdots \boldsymbol{x_N}$$  とします.
ただし,$$\boldsymbol{x_i} \in \mathbf{R^{2}},\;(1 \leqq i \leqq N)$$ とします.
 K個のクラスタに分けるとして,それぞれのクラスタの重心を$$\boldsymbol{\mu_{k}} (1 \leqq k \leqq K)$$  とおきます.ギリシャ文字\muはアルファベットのmに相当します.
それぞれのクラスタの重心の初期値は,ランダムに決めます.
 次のような記号\deltaを考えます.

{} $$ \displaystyle \delta_{ik} = \left\{ \begin{array}{} 1 & if\;k = argmin_{j}(\boldsymbol{x_{i}} - \boldsymbol{\mu_{j}})^2 \\ 0 & else \end{array} \right. $$

  argmin_{j}は後ろに続く値(この場合,データと重心のユークリッド距離)が 最小となるときの添字jをあらわします.手順1として,\delta_{ik}=1のとき\boldsymbol{x_{i}}\boldsymbol{\mu_{k}}を重心とするクラスタに割り当てます.

 手順2として,クラスタ重心は以下の更新式にしたがって更新します.
$$\displaystyle \boldsymbol{\mu_{k}} = \frac{\sum_{i=1}^{N}\delta_{ik}\boldsymbol{x_{i}}}{\sum_{i=1}^{N}\delta_{ik}}$$  この更新式は,以下のクラスタの重心とデータとの距離の総和を最小にするような重心として求められます. $$D = \sum_{i=1}^{N}{\sum_{k=1}^{K}{\delta_{ik} (\boldsymbol{x_{i}} - \boldsymbol{\mu_{k}})^2}}$$

k-meansの弱点

 k-means法では,あらかじめ何個のクラスタに分けるか指定しなければなりません. 初期値が異なる場合は結果も異なります. しかし,いくつのクラスタに分けるのが最適かは事前にわかりません.そのためいくつのクラスタに分けるのが最適か,実際に何通りか試してみる必要があります.

まとめ

 k-means法は,上述したような弱点があるもののシンプルなアルゴリズムで比較的実装しやすいため,教師なし学習を体感するには適したテーマだと思います. ぜひ実際に実装してみてください!

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp