非階層型クラスタリング k-means

非階層型クラスタリング k-means
===

それでは、機械学習やその他色々について得た知識を
復習and記事作成の練習and個人の備忘録としてまとめていきます！

前回、"階層型クラスタリング"について書いたので、
今回はそれと対になる、"非階層型クラスタリング"について書いていこうと思います！

⚠︎※※注意※※⚠︎  

・出来るだけ専門知識のあまりない人に対して、分かりやすく書くことを目標にしています。
　そのため、厳密に言うと間違っている部分があると思いますがご容赦ください。

・また、ネットで調べたレベルの知識がほとんどなので、
　"厳密に言うと"レベルではなく間違っている箇所があるかもしれません。。
　その場合は非常に申し訳ないです。指摘していただけると幸いです！

##### 前回までの記事

・[機械学習について](http://qiita.com/AwaJ/items/950953a9c20f391e72cf)
・[教師あり学習　〜回帰〜](http://qiita.com/AwaJ/items/78de8b4738e87a57addd)
・[教師あり学習　〜分類〜](http://qiita.com/AwaJ/items/b769a5461e33ea8437a5)
・[Random Forest](http://qiita.com/AwaJ/items/3c02ff64b6a89e1a96f1)
・[階層型クラスタリング](http://qiita.com/AwaJ/items/ab43ce47817b3b864b9e)

クラスタリング
---
教師なし学習の、クラスタリングということについて少しだけおさらいをしたいと思います。
(前回のコピペです、すみません。。)

クラスタリングとは

<img width="300" alt="スクリーンショット 2017-06-25 6.21.11.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/b84e1987-c163-7fe1-2740-b83cc476e9a8.png">

空間にバラバラな点として存在するデータを

<img width="300" alt="スクリーンショット 2017-06-25 6.23.09.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/5dca492e-bb6d-96cb-44b6-52843a109911.png">

図のように、何らかの基準で「似たもの」を集めるという技術です。

クラスタリングの手法には、大きく分けて二種類あり、
"階層型クラスタリング"と"非階層型クラスタリング"が存在します。

今回は"非階層型クラスタリング"の代表的な手法である、k-meansについて書いていきます。

k-means
---
非階層型クラスタリングでは、階層型クラスタリングと違って、
先に、データをいくつのクラスターに分けるかを指定しなければなりません。

今回のk-meansでは、2つのクラスターに分けていきたいと思います。

まず初めに、基準となる２つの点をランダムに選択します。
今回はDとEが選択されたとします。

<img width="300" alt="スクリーンショット 2017-06-25 13.56.15.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/e01e02d4-903d-ad78-f2f7-8d5c882992a2.png">

そして、残りの点を"基準点のどちらに近いか"で分けます。

<img width="300" alt="スクリーンショット 2017-06-25 13.58.53.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/c590ec6a-7a59-2446-417a-19db1db84da7.png">

次に、分けられたクラスター内の重心を計算します。

<img width="300" alt="スクリーンショット 2017-06-25 14.03.58.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/29eb4f74-0f0a-0f55-91a2-2cc5b2e751fa.png">
(大体の雰囲気で重心を決めたのでズレていますが、そこはツッコんではいけません。笑)

今度はこの重心を基準として、同様に残りの点を"基準点のどちらに近いか"で分けます。

<img width="300" alt="スクリーンショット 2017-06-25 14.07.26.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/6276dcbd-917a-7e7b-6fa3-1d823b441b80.png">

そしてまた、クラスター内の重心を計算します。

<img width="300" alt="スクリーンショット 2017-06-25 14.09.15.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/31ea239f-7f72-581a-264c-ce8b297ed8a5.png">

もう一度この重心を基準として、同様に残りの点を"基準点のどちらに近いか"で分けます。
今回はこの段階でクラスターの変動がなくなり、安定した状態となりました。

このように、

1. 全ての点において、基準点との距離を計算し、近い方の基準点と同じクラスターとする。
2. クラスター内の重心を取り、次の基準点とする。

というのを重心が変動しなくなるまで繰り返すことによってクラスタリングを行うのが、"k-means"です。

階層型クラスタリングに比べて、計算量が非常に少ないのが特徴となっています。

初期値依存性
---
k-meansは、非常に初期値（最初に選択される基準点）に依存します。

下の図を二つのクラスターにクラスタリングしてみましょう。

<img width="300" alt="スクリーンショット 2017-06-25 14.40.37.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/3ebbb506-4a79-4c95-1d0e-06f4c8350eab.png">

「こんなもの右上と左下に簡単に分類できるやろ！」
と思いきや、、

例えば一番右上の二点が初期基準点となってしまうと・・

<img width="300" alt="スクリーンショット 2017-06-25 14.42.51.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/2ef96979-6b51-63d4-581f-a87e42c3ebe1.png">
<img width="300" alt="スクリーンショット 2017-06-25 14.43.44.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/97bea54c-3408-f8d5-2a56-de884cd7c78e.png">
<img width="300" alt="スクリーンショット 2017-06-25 14.49.55.png" src="https://qiita-image-store.s3.amazonaws.com/0/185346/db7527d2-16db-7efa-5423-22487399532f.png">

のようになり、この状態で安定してしまいます。

こうならないために、k-meansを行うときは、
"複数回行なった上で、クラスター内平均距離が最小となる初期値を選択する。"
などの工程が必要となります。


まとめ
---
・非階層型クラスタリングには、代表的な手法として"k-means"が存在する。

・k-meansでは、
　①基準点を元にクラスターに分ける
　②クラスターの重心を新たな基準点とする
　を繰り返すことでクラスタリングを行う。

・クラスタリングの結果は、初期値に非常に依存してしまう。そのため、複数回行なってクラスター内平均距離が最小となる初期値を選択する、などを行う必要がある。

・メリットとしては階層型クラスタリングに比べて計算量が非常に少ない。

・デメリットとしては、上記の初期値依存性の他、クラスタリングを行う段階で分割数を決めなけばならない、などがある。

あとがき
---
k-meansの初期値依存性は、初めて図で見た時「なるほどー！おもしろいなぁ」と思った記憶があります。

やっぱり可視化することは、理解する上でかなり重要ですね。
情報の共有にも使えますし！

ここまで読んでいただき、ありがとうございました！