K-means クラスタリング

in English

はじめに

K-meansクラスタリングの理論とOpenCVを使った実践をまとめます。

理論

D次元ユークリッド空間内の点 を考える。

いま、N個の点 が与えられたとき、これらをK個のクラスタに分割することを考える。
各クラスタの中心座標を としたとき、最小にすべき目的関数Jを次式で定義する。

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

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

手順2を実現することは容易である。ある点 を考えたとき、それに最も近い を検索すればよい。
手順3を実現するため、Jを で偏微分する。

これより次式を得る。

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

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

手順2の最も直接的な実現方法は、各点と全てのクラスタの中心座標との距離を計算し、その最小値を探すというものである。これは大変時間がかかる。木構造などを導入し高速化すべきである。

OpenCVによる実践

K-meansクラスタリングを実行する関数はcv::kmeansである。以下の実装では、3次元色空間内の点を考え、類似色が同一のクラスタに属するような領域分割を行っている。

1. 3行目から11行目まで：入力画像を読み込み表示する。変数imageはチャンネル数3のH x Wの行列である。Hは画像の高さ、Wは画像の幅を表す。
2. 13行目から15行目まで：関数kmeansは、各行に点の座標を持つ行列を要求する。従って、入力画像を保持する行列imageの形状を、reshapeを使って変更する。この変更により、各行にB,G,Rの値の並ぶT x 3の行列になる。ここでT=W * Hである。
3. 18行目から21行目まで：関数kmeansは浮動小数点の行列を要求するので、convertToを使って値の型を変更する。
4. 23行目から27行目まで：関数kmeansを実行する。出力結果を格納する2つの行列labels, centersを用意する。さらに、アルゴリズムを停止させる条件を表現したクラス cv::TermCriteria のインスタンスを作成する。ここでは、最大繰り返し数を100とした。最後の引数の1はここではダミーである。kmeansの第6引数にcv::KMEANS_RANDOM_CENTERSを指定した。これは、クラスタの中心座標値の初期値を乱数で決めることを意味する。
5. 29行目：結果を表示する。その中身は以下の通りである。

1. 3行目から7行目まで：labelsはT x 1の行列である。各行にはラベルの値が収められている。cluster_numberを3とすれば、整数値0,1,2のいずれかとなる。centersはcluster_number x 3の行列である。各行にクラスタの中心座標が収められる。いまの場合、(B,G,R)の値が並ぶことになる。
2. 9行目から12行目まで：最終結果を収める行列rgb_imageを作る。
3. 14行目から16行目まで：centersの要素の型は浮動小数点である。これを0から255までのstd::uint8_tの型に変更する。さらに、チャンネル数を3に変更する。
4. 18行目から23行目まで：ラベルの値を(B,G,R)に置き換え、最終画像rgb_imageを作る。

結果を示す。
cluster_number=2

cluster_number=3

cluster_number=5

cluster_number=10

元画像

開発環境

1. Mac OS X 10.8.2
2. プロセッサ：3.06 GHz Intel Core 2 Duo
3. メモリ：4GB
4. Xcode4.6 with Apple LLVM 4.2（C++ Language Dialect → GNU++11, C++ Standard Library → libc++）
5. boost-1.51.0（Apple LLVM 4.1でコンパイルしたもの。こちら）
6. opencv-2.4.3（Apple LLVM 4.2でコンパイルしたもの。こちら）

参考文献

1. Pattern Recognition and Machine Learning, Christopher M. Bishop, Springer, p424-430
2. OpenCVドキュメント