orizuru

つながる.見える.わかる IoTソリュ-ション

K-meansクラスタリング

約 6 分
K-meansクラスタリング

はじめに

 機械学習は大きく2つに分けることができる。

  • 教師あり学習:訓練データとして入力値と出力値がともに提供される場合
  • 教師なし学習:訓練データとして入力値のみが与えられる場合

教師なし学習の1つであるK-meansクラスタリングは、データ解析業務において割と出番の多い手法である。今回は、K-meansクラスタリングの理論的説明を行い、画像処理に適用した実装例を示す。

理論

 K-meansクラスタリングとは、あるデータの分布とクラスタ数Kが与えられたとき、データ間の距離を基準にしてデータをK個のクラスタに分割する処理である(下図はK=3のときの例)。

いま、D次元ユークリッド空間内の点\vec{x}_{n}を考える。

(1)    \begin{equation*} \vec{x}_{n}=(x_{n}^{(1)},\cdots,x_{n}^{(D)}) \end{equation*}

N個の点(\vec{x}_{1},\cdots,\vec{x}_{N})が与えられたとき、これらをK個のクラスタに分割することを考える。各クラスタの中心座標を\vec{\mu}_kとしたとき、最小にすべき目的関数Jを次式で定義する。

(2)    \begin{equation*} J=\sum_{n=1}^{N}\sum_{k=1}^{K}r_{n,k}\|\vec{x}_{n}-\vec{\mu}_k\|^2 \end{equation*}

ここで、r_{n,k}は、点\vec{x}_nがクラスタkに属するなら1を、そうでなければ0をとる変数である。Jを最小にする手順は以下の通りである。

  1. \vec{\mu}_kに適当な初期値を与える。
  2. \vec{\mu}_kを固定し、r_{n,k}についてJを最小にする。
  3. r_{n,k}を固定し、\vec{\mu}_kについてJを最小にする。
  4. r_{n,k}\vec{\mu}_kが収束するまで、2と3の手順を繰り返す。

手順2を実現することは容易である。ある点\vec{x}_nを考えたとき、それに最も近い\vec{\mu}_kを検索すれば良い。一方、手順3を実現するには、J\vec{\mu}_kで偏微分する(\vec{\mu}_{k}の成分を\mu_{k}^{(i)}とした)。

(3)    \begin{eqnarray*} \frac{\partial J}{\partial \mu_k^{(j)}}&=&-\sum_{n=1}^{N}\sum_{k'=1}^{K}r_{n,k'}\sum_{i}2(x_n^{(i)}-\mu_{k'}^{(i)})\delta_{k,k'}\delta_{i,j} \\ &=&-\sum_{n=1}^{N}r_{n,k}2(x_n^{(j)}-\mu_{k}^{(j)}) \end{eqnarray*}

故に、

(4)    \begin{equation*} \frac{\partial J}{\partial \vec{\mu}_k}=-\sum_{n=1}^{N}r_{n,k}2(\vec{x}_n-\vec{\mu}_k)=0 \end{equation*}

を得る。これより

(5)    \begin{equation*} \vec{\mu}_k = \frac{\sum_{n=1}^{N} r_{n,k}\;\vec{x}_n}{\sum_{n=1}^{N} r_{n,k}} \end{equation*}

を得る。上式の分母はクラスタkに属する点の総数である。すなわち、\vec{\mu}_kは、クラスタkに属する点の重心となる。ここまでの議論を踏まえて、Jを最小にする手順を書き直すと以下のようになる。

  1. クラスタの中心に適当な初期値を与える。
  2. 各点を一番近いクラスタに割り振る。
  3. 割り振られた点の重心を計算し、それを新たなクラスタの中心座標とする。
  4. クラスタの中心座標が変化しなくなるまで、2と3の手順を繰り返す。

実装

 ここでは、K-meansクラスリングを画像処理に適用した例を示す。

 最初に一枚のRGB画像を考える。各画素にはRGB値が割り当てられている。これを3次元ベクトルとみなすと一枚のRGB画像はRGB空間内の点の集合とみることできる。この空間内では、類似色同士が塊を作って分布しているはずである。この分布の偏りをK-meansクラスリングにより明確に分割してみる。使用するライブラリはOpenCV、言語はC++である。動作確認した環境は以下の通り。

  • macOS Sierra
  • Xcode(C++ Language Dialect: C++14)
  • OpenCV-3.2.0
  • boost-1.59.0

OpenCVのcv::kmeansを呼び出すだけである。

実行コマンドは以下の通り。

最初の引数は画像へのパス、2番目の引数はクラスタ数を表す。さまざまなクラスタ数の時の結果を以下に示す。各クラスタの色はそのクラスタの重心座標の色である。

k=2

k=3

k=5

k=10

k=20

k=100

元画像

いわゆる減色処理が行われていることになる。

まとめ

 今回はデータ解析においてしばしば用いられるK-meansクラスタリングを説明し、画像処理に適用した例を示した。画像は、見方を変えれば、グリッド上に並ぶ3次元ベクトルの集合である。K-meansクラスタリングにより、少ない数の色(カラーパレット)で画像を表現することができる。
 ところで、上記のboost::copyの中身は理解できたでしょうか?

About The Author

IoT/AIソリューション事業部(深層/機械学習・画像処理エンジニア)KumadaSeiya
深層/機械学習と画像処理などを担当。物性理論で博士号を取得。
http://seiya-kumada.blogspot.jp/
https://twitter.com/seiya_kumada

Leave A Reply

*
*
* (公開されません)