機械学習を世界一分かりやすく理解する(クラスタリング編)

## はじめに

「世界一わかりやすく」とか言っとけばいいねもらえると思っている安易なネーミングをお許しください。
みなさん今日も機械学習お疲れ様です。桜も散りそうですがいかがお過ごしでしょうか。


さて、桜といえば、目黒川の夜桜がめちゃくちゃキレイでした。実は今回は全く桜の話ではないですけどね。



# クラスタリング

さて、機械学習している人なら誰でも一度は嗜んだであろう「クラスタリング」ですが、みなさんはまず<b>「教師なし学習」</b>と聞いて

> 「なにか強大な力が働いていそう」

なんて思ったんじゃないでしょうか？
それで勉強していったら`scikit-learn`なんていう便利なライブラリに早々に出会い、「便利じゃん」とかいって中身を何も理解せずに機械学習している。違いますか？

まだ間に合います。今ここで「教師なし学習」の中身を完全に理解しましょう。
大丈夫。強大な力なんてどこにもありません。数学くらいは知っておいてほしいですけど。


## 概要

そもそもクラスタリングというのは、データにラベルを与えることを言います。
正解も何もない生のデータを分類していくから「教師なし学習」なんて呼ばれています。




## アルゴリズム

さて、具体的にデータをクラスタリングしていきましょう。
僕は親切なので、ここに来るみんなが書籍などでクラスタリングのアルゴリズムを理論的に勉強するのが億劫なことくらい知っています。
文字がバーーーってなってても何がなんだかわからないと思うので実際に2次元の生データをプロットしてクラスタリングの推移を見ていきたいと思います。

さて、下のようなデータがあります。

<img width="885" alt="Screen Shot 2019-04-10 at 20.00.12.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/8ac3abd8-398f-36e4-e23f-a2c3598d857a.png">

人間なら、これを3種類に分類することはたやすいでしょう。
しかし、機械がこれをどう分類するか想像することはたやすくないことでしょう。<br>

さあ、まず機械は、分類の<b>重心となる点</b>を適当に生成します。これを<b>セントロイド</b>なんて呼んだりもします。

<img width="883" alt="Screen Shot 2019-04-10 at 20.02.34.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/588a729f-3cc1-fa94-ad45-fae045706b33.png">

次にそれぞれのデータとの距離を計算します。
ここでいう「距離」ですが、一般的には<b>ユークリッド距離</b>を指します。
なんか難しいなあって思った人、大丈夫、ただの距離だから。三平方の定理だから。

イメージにすると本当にこんな感じで、純粋な距離を指していることがわかりますね。

<img width="682" alt="Screen Shot 2019-04-10 at 20.07.03.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/fcba9d5c-b3fd-0d9a-cc00-60a6ccb6cfb2.png">

対して、<b>マンハッタン距離</b>なんてのもあります。今回は使いませんがこの際なので覚えておきましょう。

<img width="918" alt="Screen Shot 2019-04-10 at 20.08.50.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/04549d66-aacc-e477-2605-46ccef323348.png">

この2つの距離の概念は教師あり学習の回帰なんかでうるさくやります。実はけっこう大事だったりもします。


さて、早速分類していきますが、このユークリッド距離を計算し、<b>一番近いものを自身のラベルと判定</b>します。


<img width="708" alt="Screen Shot 2019-04-10 at 20.13.16.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/1d3a4e5f-b43f-c7d3-782a-58379181fa1c.png">

ね？？簡単でしょ？？普通でしょ？？
さすがにこれで終わったらポンコツすぎるのですごいのはここから。

ラベル付けされたデータの<b>重心</b>に中心となる点を移動させます。ベクトルを勉強した人なら簡単だと思いますが重心はこんな感じでチョチョイのチョイで求められます。

$$
\vec{G}=\frac{\sum_{k=1}^{n}{\vec{a_k}}}{n}
$$

ベクトルがよくわからない人はこれを座標に置き換えればオッケーです


さて、そうしてセントロイドを移動させました。

<img width="1005" alt="Screen Shot 2019-04-10 at 20.26.17.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/1f5bfa42-2007-3416-97d2-df27825ad5ee.png">

ここでもう一度ユークリッド距離を計算し直して再度ラベル付けを行います。

<img width="1018" alt="Screen Shot 2019-04-10 at 20.27.50.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/c9882390-7642-6881-5bc4-af5d661d5078.png">

あら不思議、もう立派に分類がされています。

最後に重心も計算し直してセントロイドを正確な位置に移動させれば...

<img width="1032" alt="Screen Shot 2019-04-10 at 20.29.35.png" src="https://qiita-image-store.s3.amazonaws.com/0/243995/a6f7a7bc-667c-908e-7047-5e6b40a7fe2b.png">

完成です！！

お察しの通り、セントロイドをランダムに配置することが肝心で、このセントロイドを上手い具合に動かしていくことによって分類を実現させています。


アルゴリズムをまとめます。

<hr>クラスタリングのアルゴリズム

1. k(≥1)を決めます
2. k個のランダムな配列(セントロイド)を生成します
3. セントロイドからの距離を近いものにラベル付けしていきます
4. 各ラベルの重心にセントロイドを移動させます
5. セントロイドが収束するまで3, 4を繰り返します

<hr>

次回、実装。


## 実装

では、やっていきます。
決して難しくありませんがゴチャゴチャしてくると嫌なので計算の中身は`numpy`に任せました。

まず、セントロイドの生成から。

```Python
import numpy as np

# kはクラスターの数、arrは生データを指しています
centroids = np.random.randint(np.max(arr), size=(k, arr.ndim))
```

データセットが2次元とは限らないことも考慮しています。


次にラベル付け。

ユークリッド距離を計算して一番ユークリッド距離の短いラベルにクラスタリングします。

```Python
labels = []

# データの1つ1つを精査
for index, data in enumerate(arr):

    min_distance = 10000000  # なるべく大きい数
    min_label = 0

    # セントロイド一つ一つと精査
    for cluster, centroid in enumerate(centroids):
        eucrid_distance = np.linalg.norm(data - centroid, ord=2)
        if min_distance > eucrid_distance:
            min_distance = eucrid_distance
            min_label = cluster

    labels.append(min_label)
```

そして重心の計算と移動。

```Python
# 更新後のセントロイド(初期化のためにそのまま代入)
centroids_new = centroids

for cluster in range(k):
    
    # 重心(原点で初期化。後の計算のためにfloat型に)
    gravity_center = np.array([0, 0], dtype=np.float)

    # クラスターごとに重心を再計算
    for index, label in enumerate(labels):
        # 重心の計算
        if label == cluster:
            gravity_center+= arr[index] / len(arr)

    # セントロイドを更新
    centroids_new[cluster] = gravity_center
```

さて、ここで、なぜ`centroids`と`centroids_new`を分けたのかと気になる方が出てくるでしょう。
それは、アルゴリズムの

>セントロイドが収束するまで

の「収束」を機械的にハッキリさせるために移動距離を比較したいからです。
具体的な比較方法は様々ですが3歳のパイソニアでもわかるよう以下のようにしましょう。

```Python
er = []
for cluster in range(k):
    # 移動距離を計算(これもユークリッド距離)
    centroid_error = np.linalg.norm(centroids_new[cluster] - centroids[cluster], ord=2)
    er.append(centroid_error)

# 距離が収束していないと判断した場合セントロイドを更新してもう一回前の作業を行います
if np.mean(er) < error:
    centroids = centroids_new
    continue

break
```

最後に、クラスタリング終了後の返り値を定義します

```Python
return labels, centroids_new
```

本当にたったこれだけ。簡単でしょ？

実は`scikit-learn`はこれを上手いことやっています。機会があればその仕組みを見ていきましょう。
とりあえず今回はここまで。コードは<a href="https://github.com/masatsch/k-means_algorithm">GitHub</a>にあげてます。