HELLO CYBERNETICS

深層学習、機械学習、強化学習、信号処理、制御工学、量子計算などをテーマに扱っていきます

クラスタリングの基本

人工知能 人工知能-機械学習

　

　

follow us in feedly

はじめに

クラスタリングとは機械学習手法の1つであり、通常は「教師なし学習」によって実現されます。今回はクラスタリングの使いドコロや、通常の判別などと何が違うのかを理解し、基本的な手法を確認することを目的とします。

 

クラスタリングと教師なし学習

教師なし学習の全てがクラスタリングというわけではありません。あくまで、教師なし学習の中にクラスタリングというものがあるというイメージです。教師なし学習とクラスタリングがいったいそれぞれ何なのかを説明していきます。

 

教師なし学習

データ\bf x_1,x_2,...,x_nがあったとしましょう。機械学習をするという場合には、何らかの評価関数J({\bf w,x})を使って関数f(\bf {w,x})を決定します。

 

仮に「教師あり学習」の場合は、データ\bf x_1,x_2,...,x_nに対してそのラベルt_1,t_2,...,t_nがセットで与えられ、評価関数の中身にラベルが現れます。つまり明示すればJ({\bf w,x},t)という具合になってきます。例えば線形回帰の場合には

 

J({\bf w,x},t)=\left( {\bf w^T x} - t \right)^2

 

という評価関数を設定し、パラメータ\bf wを評価関数が最小になるように決定するという形式が最も単純になります。データをn個与えた場合に上記の二乗誤差の和が最小になるようにするということを明示すると、この問題は

 

arg\min_w \sum_{i=1}^n \left( {\bf w^T x_i} - t_i \right)^2

 

と表すことができます。

 

教師なし学習の場合は、ラベルが明示的に与えられません。そもそも回帰問題なのか判別問題なのかという区別すら問いません。データ（あるいは変換）に対して何らかの仮定を与えることで、その仮定を満たすような形式に変更するのが教師なし学習だと思えばいいでしょう。どんな仮定を与えるのかが評価関数に反映され、それが各種法の主な違いになってきます。

たとえば、自己符号化器の評価関数は以下のようになっています。

 

J({\bf W_1,b_1,W_2,b_2,x})=\left( {\bf W_2} f(\bf{W_1x + b_1}) + \bf {b_2 - x} \right)^2

 

ここにラベルというものは入り込んできません。（見ようによっては、入力自身がラベルであるとも言えますが、いずれにしてもコレを行ったからと行ってデータがすぐに分類できるとかいう類のものではありません）

ここではパラメータ\bf W_1,W_2,b_1,b_2を上記の評価関数を最小化することで求めます。

この手法の仮定は、今から獲得する変換は、自分自身に戻ってこれるような変換であるということです。この変換にどんな意味があるのかというと、このような変換を獲得しておきつつ、実際にはW_1,b_1のみを使えば、何らかの変換を施したのだが戻ろうと思えばいつでも戻ることのできる何らかのデータに加工することができるのです。そんな変換を獲得するために、上記のように変換を二段階に構えた評価関数が準備されているわけです。

 

ほかにも主成分分析とか独立成分分析なども教師なし学習です。

 

クラスタリング

クラスタリングとは、データ\bf x_1,x_2,...,x_nが実は何個かのグループに分類されるであろうと予測できるが、そのラベルを知らないような場合に使います。つまりクラスタリングには大雑把に、「手元のデータはいくつかに分けられるはず」という仮定があるということです。もし既にラベルを手に入れていれば教師あり学習を行ったほうがいいでしょう。しかし、現在はラベルが無いだけでなく、手元のデータがいくつに分けられるのかすらも知りません。

 

従って、クラスタリングを行うことでグループ分けができたとしても、「このグループは○○である」

と断定できるわけではなく、「仮定の下で分けられた何か」としか言えません。ただし手元のデータに何らかの意味があればそこから類推することができるかもしれません。

 

 

例えば、お客様のコンビニでの購買情報があったとしましょう。何をどれだけ買ったかというデータが大量にあり、商品配置などの戦略を立てたいとします。

その中の雑多なデータをクラスタリングしてみたら、どうも大きく2つのグループに分けられそうで、一方のグループの方が大きな集団となっている場合があれば、その集団をメインターゲットにすると影響の大きい戦略が取れそうです。そのグループは化粧品やスイーツを買う傾向にあることが購買情報から分かれば、「この集団は女性」だと言え、そもそも女性客の方が多そうだなどと言えるわけです。

 

f:id:s0sem0y:20170107072143p:plain

 

 

 

もちろん今勝手に2つのグループと言いましたが、もう少し見てみると、大きな集団もいくつかのグループに固まっているように見えるかもしれません。それがもしかしたら「年齢」による違いかもしれませんし、それはデータを見ながら類推するということになります。

 

f:id:s0sem0y:20170107072214p:plain

 

ともかく大量にあるデータを何らかの基準で仕分けするのがクラスタリングというわけです。

ラベルが無いので教師なし学習ですが、主にグループ分けを行うのがクラスタリングの目的であるということになります。

 

クラスタリングの手法

具体的な例題を使ってクラスタリングの手法を見ていきます。 

凝集型クラスタリング

凝集型クラスタリングは、もともとデータ点が全てバラバラの初期状態から始めて、似た傾向のあるデータ点を統合していく方法です。

「似た傾向」というものを如何にして測るのかが決まれば、基本的には単純な操作でクラスタリングを行うことができます。クラスタリングでは元々いくつのグループに分けられるのかということを明示的に知っているケースは少ないため、凝集型クラスタリングでは最終的には全てのデータ点が1つのクラスタに収まるという状態になりますが、それを適当な段階で途中終了することでクラスタリングを行います。

 

今回は簡単のため、スカラー値をクラスタリングしていきましょう。

重心法

データ点は(-4,-2,1,3,4,7)の6点とします。手続きは単純で、最も似ているクラスター同士を統合していくという方法になります。

まずデータ点全てがバラバラの状態で始めます。従って、最初はデータ点1つ1つがクラスターに対応します。クラスターの堺を縦棒「｜」で表すとして初期状態は

 

1.(-4|-2|1|3|4|7)

 

という形になります。この似た傾向を測るために類似度として値の差の絶対値の逆数\frac{1}{|x_i-x_j|}というものを導入します（もちろんこれは他のものでもいいですが、最も分かりやすいのがコレでしょう）。すると、最も近いクラスターは3と4になります。従ってこれを統合して1つのクラスターとしてしまいます。

 

2.(-4|-2|1|3,4|7)

 

これで1回分の手続きが終了しました。先程は類似度を測るために、値の絶対値の差の絶対値の逆数を用いました。しかし、今、3,4というクラスターと7というクラスターの類似度を測るためにはどうすればいいでしょうか。ここもクラスターの類似度を測る値として何か基準を作らなければなりません。ここではクラスターの含まれる値の平均値を、そのクラスターの値として用いることにします。つまり、3,4のクラスターの値を3.5とするということです。

そうして以下同様に、最も近いクラスターを統合していきます。一番近いクラスターは-4と-2です。

 

3.(-4,-2|1|3,4|7)

 

同様に、出来上がった-4,-2の値を-3として考え、再び最も近いクラスターを統合していきます。次は1と3,4のクラスターが近いですから、

 

4.(-4,-2|1,3,4|7)

 

すると1,3,4の値を4に変更できます。またクラスターを統合し

 

5.(-4,-2|1,3,4,7)

 

とし、もう2つしかクラスターがありませんから最後は

 

6.(-4,-2,1,3,4,7)

 

というクラスターに最後は凝集されます。統合されていったクラスターの順番を考えて樹形図を構成すると以下のようになります。

f:id:s0sem0y:20170107100637p:plain

このクラスタリングは下から始まって、次第に上へ進んでいきます。基本的にはひと通り1つのクラスターに凝集してしまうまでこの手続きを繰り返し、その過程で出てきたクラスターを記憶させるようプログラムしておけば、後でいろんなクラスターの分け方を検討できます。

 

アルゴリズムとしてまとめておきましょう。

データ点をD=\{x_1,x_2,...,x_n\}

クラスターをC=\{c_1,c_2,...,c_n \}

と表しておきます。初期状態においては、c_i=\{x_i\}と各クラスターに1つの値が入ってる状態となります。

 

while　|C|\geq2  (クラスターの数が2以上の間以下を繰り返す)

　　(c_m,c_n)=\arg\max_{c_i,c_j} \left(sim(c_i,c_j) \right)　(最も近いクラスタc_i,c_jを見つける)

　　（クラスターの類似度としてsim(c_i,c_j)= \frac{1}{|c_i-c_j|}を用いる）

　　（|c_i-c_j|の計算では、各クラスターにあるデータ点の平均値を用いる）

　　merge(c_m,c_n)　（最も近かったクラスターを統合する）

end while

 

いま、類似度を測る指標として、\frac{1}{|c_i-c_j|}を用いましたが、そうでなくてもいいです。他にもっと良い方法があればそれでもいいでしょう。2つのクラスターに属するデータ点から1つずつ値を取り、すべての組み合わせにおいて差を計算しておき、一番小さな値を使うとか、一番大きな値を使うとか、他にも考えられる方法はいくらでもあります。

 

今回紹介したのは重心法と呼ばれる方法です。

他にも単連結法とか完全連結法などがあり、2つのクラスターに属するデータ点から1つずつデータ点を選出し、すべての組み合わせについてデータ点の類似度を計算し、最も大きな値をクラスターの類似度にしてしまうのが単連結法で、最も小さな値を使うのが完全連結法です。

 

単連結法

データ点を使って、例題を見るのが一番理解が早いでしょう。以下のようなデータ点でやってみましょう。

 

1.(-4|-2|1|3|4|8)

 

最初はどの方法を使っても、最も近い点が統合されます。

 

2.(-4|-2|1|3,4|8)

 

ここで単連結法では、クラスター3,4と1の類似度は\frac{1}{|3-1|}で測られることになり、クラスター3,4と7の類似度は\frac{1}{|4-7|}で測られることになります。重心ではなく、最も都合の良い類似度を使うという形です。

 

今回の場合クラスター3,4と1の類似度と同じ値が、-4と-2でも得られます。このような場合には、どちらを統合するかは予め決めてかなければなりません。

例えば、なるべく均等なサイズのクラスターにしようとすれば、統合されたときにクラスターに属するデータ点がなるべく小さくなるように設定しておけばいいです。そうすると次の統合では

 

3.(-4,-2|1|3,4|8)

 

となります。同じように類似度を計算すれば、

 

4.(-4,-2|1,3,4|8)

 

となり、左2つのクラスターの方が類似しているので

 

5.(-4,-2,1,3,4|8)

 

6.(-4,-2,1,3,4,8)

 

となって完結します。

 

f:id:s0sem0y:20170107110143p:plain

 

完全連結法

先ほどと同じデータ点で試していきましょう。

 

1.(-4|-2|1|3|4|8)

 

2.(-4|-2|1|3,4|8)

 

ここで完全連結法では、クラスター3,4と1の類似度は\frac{1}{|4-1|}で測られることになり、クラスター3,4と7の類似度は\frac{1}{|3-7|}で測られることになります。最も都合の悪い類似度を使うという形です。

 

3.(-4,-2|1|3,4|8)

 

さてここでは、クラスター-4,2と1の類似度は\frac{1}{|-4-1|}で測られることになり、クラスター3,4と1の類似度は[tex:\frac{1}{|4-1|}となります。

 

4.(-4,-2|1,3,4|8)

 

ここで単連結法ならば左2つがくっつくところですが、完全連結法では右2つがくっつきます。

 

5.(-4,-2|1,3,4,8)

 

6.(-4,-2,1,3,4,8)

 

単連結法では、クラスター同士を眺めたときに、1つでも似てるデータ点が見つかれば繋げてしまいますが、完全連結法ではクラスター間の類似度は最も似ていないデータ点が基準になるため、基本的にクラスターが大きくになるに連れて、統合がされにくくなってきます。

 

f:id:s0sem0y:20170107110305p:plain

 

 

まとめ

単連結法は大きなクラスターができやすく、完全連結法は大きなクラスターを作りにくくなります。重心法はその間くらいの性質であるというのを覚えておくといいでしょう。

樹形図を見比べてみます。

 

左が単連結法、右が完全連結法

f:id:s0sem0y:20170107110143p:plainf:id:s0sem0y:20170107110305p:plain 

 

単連結法は、クラスター数が2の時点で、サイズが「５」と「１」に分けられています。一方で完全連結法は「２」と「４」です。このように連結法によって異なった結果が得られます。

 

当然プログラムによって、クラスターの数が少なくなったら連結の方式を変えるということもできるので、問題に応じて適宜使い分けると良いです。

 

今回はスカラーデータを使いましたが、当然これがベクトル型のデータでも一切構いません。ベクトルとベクトルの類似度をどのように測るかは、単純な拡張で言えばユークリッド距離の逆数になりますし、他の方法を取ってもいいでしょう。多次元のデータの方が工夫する面も多く、連結法に応じた性質の違いが顕著に出ます。例えば2次元のベクトルデータを扱う場合においては、単連結法は細長いクラスターを構成しがちになることは想像に難くないでしょう。

 

k-means

凝集型クラスタリングでは、すべてのデータ点を個々のクラスターであるという状態から始めて、次第に近いクラスター同士を統合していくという方法を取りました。一方で今から紹介するk-meansという方法は、最初からクラスターの個数を仮定しておき、適当なクラスターに分けておくことで、より良い分け方を見つけていくという方法を取ります。

 

例題を見ましょう。

データ点を(-4,-2,-1,0,2,3,4,5,8)として、これらが３つのクラスターに分かれているはずだという仮定で始めます。クラスターが３つであるという場合には、まず基準点を３つ初期値として準備します。今回ならば例えば、

 

c_1の基準点m_1=-3

c_2の基準点m_2=0

c_3の基準点m_1=9

 

として始めてみましょう。まずは各データ点と各クラスタ−の基準点の近さを計算し、最も近かったクラスターにデータ点を割り振るということをします。近さの測り方は妥当なものならば何でもいいですが、今回も値の差の絶対値の逆数を使います（結局は差が小さいところに割り振るということ）。

 

(-4,-2,-1,0,2,3,4,5,8)

 

において、

 

c_1=\{-4,-2\}

c_2=\{-1,2,3,4\}

c_3=\{5,8\}

 

と割り振られることとなります。次に基準点を更新します。基準点は各クラスターに属するデータ点の平均値を用います。

 

c_1の基準点m_1=-3

c_2の基準点m_2=2

c_3の基準点m_1=6.5

 

再び、基準点と各データ点との近さを測り、最も近いところへデータを割り当てます。

 

c_1=\{-4,-2,-1\}

c_2=\{2,3,4\}

c_3=\{5,8\}

 

 

基準点の移動によってデータ点の割り振りに変更が起こりました。再び基準点の計算を行います。

 

c_1の基準点m_1=-\frac{7}{3}

c_2の基準点m_2=3

c_3の基準点m_1=6.5

 

 

そして再び割り振ります。

 

c_1=\{-4,-2,-1\}

c_2=\{2,3,4\}

c_3=\{5,8\}

 

 

クラスターの中身に変化が起こりません。これによってクラスタリングを終了とします。

 

初期状態の基準点は適当に決めますが、場合によっては初期値によって収束の様子が変わる場合もあります。また、クラスターの数をいくつに設定すべきかも自明ではありません。

凝集型と違い、次第にクラスターの数が少なくなっていくわけではないので樹形図を書くこともできませんが、非常にシンプルかつ平等な大きさのクラスターが構成できるため頻繁に用いられます。

 

発展的話題

k-meansではデータ点をハッキリと分けてしまいましたが、ある基準点を中心にガウス分布を構成し、データ点がそのガウス分布から生起した確率を計算することもできます。つまりクラスターの数が、ガウス分布の数に相当し、基準点はガウス分布の平均として扱うという対応になります。この場合、きわどい位置にあるデータ点が、どちらのクラスターに属するかを決定的にしてしまうのではなく、きわどいものはきわどいまま、どちらのクラスターに属しているかの確率を知ることができます。

 

これはデータ点に混合ガウス分布を当てはめて、各点の生起確率を計算することに相当します。

 

データ点の生起を確率分布でフィッティングするのは機械学習の有用な手法の１つです。

また混合ガウス分布の解法はより一般的なEMアルゴリズムの一種として捉えることができます。

s0sem0y

スポンサーリンク

コメントを書く