【教師なし学習・クラスタリング】K-means

f:id:s0sem0y:20170701051832p:plain

はじめに
K-means

はじめに

近年の機械学習は専ら教師あり学習に話題が集中しています。

しかし、実際のデータは必ずしもラベルを正確に付与できるとは限りません。多くのデータはなんだかよくわからないが手元にある状態で、そのデータはいくつかの塊に分けられると（あるいはいくつかのデータの源がある）考えられます。

そのようなときに使える機械学習の手法が、教師なし学習であり、その一種であるクラスタリングは、ラベルの付与無しに、データをいくつかの塊（クラスター）に分けます。

今回はクラスタリングで最も基本的な手法であるK-meansを紹介します。

K-meansは混合ガウスモデルの特殊なケースと考えることもできます。

K-means

K-meansの働き

K-meansはクラスタリングの手法の一種です。

データが「K」個の塊（以後クラスター）に分けられると仮定し、あとはある所定の手続きに従って、各データ点をいずれかのクラスターに振り分けていきます。

具体的な手続きに関しては、手計算でできるレベルのものを下記で紹介しています。

s0sem0y.hatenablog.com

K-meansはシンプルながら強力なアルゴリズムであり、ちょっとしたデータセットなら割と正確にクラスターを見つけ出してくれます。またアルゴリズムがシンプルであるがゆえに、何をしているか、どういう仮定のもとでクラスターが得られたのかを解釈しやすいです。

K-meansの概要

データ集合 $X = \{ {\bf x_1,x_2,...,x_N} \}$ が手元にあるとします。各データ点は $\bf x \in \mathcal R ^{D}$ (D次元のベクトル)であると考えます。すなわち、データはD次元のユークリッド空間に点在することになります。

この際、このデータはK個のクラスターに分かれていると仮定します。クラスターとはデータの塊のようなもので、そのクラスターに属するデータ同士は、互いに近くに集まっているだろうと考えます。

例えば下の図のように2次元のデータが点在していた場合、なんとなく2つのクラスターがあるように考えられます（実際にはそのようなラベルは無い状況なのだが）。

f:id:s0sem0y:20170701051717p:plain

仮にクラスターが2個あるものだと仮定した場合には、それぞれのクラスターに対して重心 $\bf μ _k$ を考えることができます。クラスターの重心とは、そのクラスターに属するデータ点の位置の平均で表されます。

しかし本来、データがどのクラスターに属するのかなど正確には知り得ないという状況です。従って、クラスターの重心は、最初は適当に与えてしまいます（下の図では菱型で2つのクラスターの重心を表現した）。

f:id:s0sem0y:20170701051832p:plain

すると、この重心が一旦正しいものだと考え、どちらの重心に近いかによって、各データ点をクラスターに割り当てることができるようになります（もちろん実際は仮のクラスターである）。

f:id:s0sem0y:20170701052135p:plain

このようにして2つのクラスターにどのデータが属するかが分かれば、そのクラスターの重心が計算できるようになります。最初においた重心は仮の姿であったため、今、この2つのクラスターの重心を更新します。

f:id:s0sem0y:20170701052356p:plain

重心の位置が移動したら、次はこの重心の位置を正しいものと考え、再び、データ点を各クラスターに割り当て直します。

f:id:s0sem0y:20170701052514p:plain

これによって、データ点がどのクラスターに属するか、一部変更が入りました。従って、新たなデータ点を用いて、それぞれのクラスターの重心を再度求め直します。

f:id:s0sem0y:20170701052629p:plain

新たな重心を用いて、データ点を近い方のクラスターに割り当てます。

f:id:s0sem0y:20170701052716p:plain

しかしどうやら割り当ての変更はなさそうです。これによりK-meansのアルゴリズムは収束します。しかも、収束した時にはどうもそれらしい分け方を上手くできているように見えます。

K-meansの詳細

上記の動きを定式化します。

データ集合: $X = \{ {\bf x_1,x_2,...,x_N} \}$

各データ点: $\bf x \in \mathcal R ^{D}$

クラスタKの重心: $\bf μ _k$ 　 $(k = 1,...,K)$

としたとき、これは以下の損失関数の最小化問題となります。

$\displaystyle L = \sum_{n=1}^N \sum_{k=1}^K r_{nk}({\bf x_n - μ _k})^2$

$r_{nk}$ は $x_n$ がクラスター $k$ に割り当てられている場合に $1$ となり、そうでなければ $0$ となる値です。要するに上記の損失関数は、各クラスターの重心とそのクラスターに属するデータの二乗距離の総和を表しています。

単純に、クラスター $k$ に属しているデータ点 $\bf x_n$ は、 $\bf \mu_k$ に近いはずである、ということを表現しているわけです。この損失関数の最小化の手続きは以下のとおりです。（既に具体的にどんな動きをするのかを概要で見たので、すぐに分かるはずです）

１．初期化

$\bf μ_k$

を適当に決定します。

２．クラスターへの割り当て

$r_{nk}= 1 　if　 k = arg\min_j ({\bf x_n - μ_j})^2 　else　 0$

によりデータをクラスターへ割り当てます。これは単純に、一番近い重心にデータ点を割り当てることになります。

３．重心の更新

$\displaystyle {\bf μ_k} = \frac{\sum_n r_{nk}{\bf x_n}}{\sum_n r_{nk}}$

により重心を更新します。これは要するに「２．」で割り当てられたデータ（ベクトル）の平均に相当します。この計算は損失関数

$\displaystyle L = \sum_{n=1}^N \sum_{k=1}^K r_{nk}({\bf x_n - μ _k})^2$

に関して、 $\bf μ_k$ に関する偏微分をとり、

$\displaystyle \frac{\partial L}{\partial {\bf μ_k}} = 2\sum_{n} r_{nk}({\bf x_n-μ_k})$

と置いて $0$ と置いたものを、 $\bf μ_k$ について解いたものです。

４．「２．」と「３．」を繰り返す

重心が変更されたため、データの割り当ても変更を受けます。

いずれ変更を受けなくなるまで、上記の処理を繰り返します。

K-meansの欠点

K-meansの欠点はいくつか考えられますが、まず、クラスターの個数を指定しなければならないことが挙げられます。本来いくつのクラスターがあるのか分かりません。データが２次元であれば当たりを付けるのは簡単かもしれませんが、これが可視化できない次元になれば難しくなります。実際、当たりを上手く付けられなかった場合、クラスターは想定外の割り当てを行ってしまいます。

また、損失関数を見れば分かる通り、重心との二乗距離を評価しています。従って、仮にデータに外れ値が混ざりこんでいた場合、そのデータの損失を低くするために重心がやたらと引っ張られてしまう可能性が出てきます。

また、データを評価する上で二乗距離というものが本当に妥当であるかは分かりません。

K-meansの改良

そこで、K-meansの改良をするという試みがいくつかあります。

K-meansのアルゴリズムを、単に動きとしてだけでなく数式ベースで見てきたため、以下のような変更が有効に活用できそうなのは容易に想像できるかと思われます。

$\displaystyle L = \sum_{n=1}^N \sum_{k=1}^K r_{nk} d({\bf x_n , μ _k})$

単に二乗誤差の部分を、 $d$ で置き換えたということになります。この場合でも、まずは重心を適当に置きます。しかし、その後割り当ての仕方が異なってきます。単にユークリッド距離が小さいクラスターに割り当てるのではなく、非類似度 $d$ が小さいクラスターに割り当てます。

そして重心の計算も異なってきます。重心は損失関数が小さくなるように決定されるべきであり、単にベクトルの平均を取るという方法ではなくなります。

しかしそれも、損失関数を重心で微分して $0$ と置くことで求まるでしょう（簡単に求まるかは $d$ の形状次第ではあるが）。

混合ガウスモデル

確率的なクラスタリングの手法として混合ガウスモデルがあります。

真面目に数式を追いかけるとそれなりにゴツい式になってしまうので（確率的な手法は総じて）、今回はK-meansから派生した軽い説明をします。

今回は $r_{nk}$ による振り分けを行っていますが、この部分が確率で表現されるようになります。すなわち、80％はあっちで、20％はこっちのクラスタかもしれない、位のソフトな振り分けを行うのです。また、 $d$ がK-meansでは二乗距離になっていましたが、ここが指数関数の形になります。これはガウス分布を仮定したことに由来します。

また、今回のK-meansの解法を一般化したものはEMアルゴリズムとして知られ、隠れマルコフモデルなど隠れ変数を持つモデルに広く持ち入られています。

EMアルゴリズムはK-meansの解法と同じように、一方を求めて一旦固定し、その固定した条件の元で他方を求めるという最適化を交互に行うことで達成されます。

また確率的なモデルはベイズ理論で拡張が可能で、その場合には他の解法が用いられる場合もあります。