ラビットチャレンジ - 機械学習 第5章 アルゴリズム

# 0．概要
本記事は日本ディープラーニング協会認定の講座プログラムである「ラビット・チャレンジ」が提供している科目の1つである機械学習のレポートである。
記事タイトルに記載のとおり、第5章のアルゴリズム(k近傍法、k-平均法)について以下にまとめる。

# 1．k近傍法(kNN:k-Nearest Neighbor)
分類問題のための機械学習手法(教師あり学習)。

最近傍のデータを$k$個取り、それらが最も多く属するクラスに識別する。
$k$の数を変えることで結果も変わりうる(変わるかは近傍のデータによる)。
$k$が大きいほど決定境界は滑らかになる。

例）$k=3$の場合、新しく識別するデータの近傍3つのデータがどのクラスに属するか多数決で新しいデータのクラスを決める。

距離の計算にはユークリッド距離(いわゆる直線距離)が使われるとのことだが他の距離(マハラノビス距離とか)でも良い。

# 2．k-平均法(k-means)
クラスタリングのための機械学習手法(教師なし学習)。

与えられたデータを$k$個のクラスタ(特徴が似ているグループ)に分類する。

## 2.1．クラスタリング
特徴が似ているデータをグループ化すること。
教師なし学習の一種なため、各データがどのクラスタに属するのが正しいかは与えられない。

## 2.2．k-平均法の流れ

1. 各クラスタ中心点の初期値を設定。
2. 各データ点と各クラスタ中心点の距離を計算し、各データ点が属するクラスタとして最も近いクラスタを割り当てる。
3. 各クラスタの平均ベクトル(中心)を計算し、中心点を更新。
4. 収束するまで2~3を繰り返す。

初期値とする各クラスタの中心点が近いとうまくクラスタリングできない(近いせいで似ているデータを別々のクラスタにしてしまったりどのクラスタとも遠いデータができうる)。　
　→k-means++法という初期値の決め方が改良された手法がある。
　　最初の1つはランダムな値ではなくデータ点からランダムに選んだ点をクラスタの中心点とし、以降のクラスタ中心点は離れた位置になるように初期化される。
　　これで複数の中心点が近くにならないようになる。
　　k-means++法の方が時間はかかるが精度向上に繋がる。

クラスタがいくつになるかはハイパーパラメータである$k$によるので、k-means++法を使っていても適切ではない$k$となっていると、その分クラスタができてしまい、無理やり分けられてしまうため、適切に設定する必要がある。

https://qiita.com/NoriakiOshita/items/cbd46d907d196efe64a3

# 3．ハンズオン：k近傍法

## 3.1．演習

### 3.1.1．ライブラリのインポート

```Python:
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
```

### 3.1.2．訓練データの生成とプロット

```Python:
# 訓練データ生成
def gen_data():
    # 分類0の説明変数生成
    x0 = np.random.normal(size=50).reshape(-1, 2) - 1
    # 分類1の説明変数生成
    x1 = np.random.normal(size=50).reshape(-1, 2) + 1.
    # 分類0の説明変数と分類1の説明変数を1つの変数に連結。
    x_train = np.concatenate([x0, x1])
    # 分類0と分類1の目的変数をそれぞれ25個ずつ生成して1つに連結
    y_train = np.concatenate([np.zeros(25), np.ones(25)]).astype(np.int)
    return x_train, y_train

X_train, ys_train = gen_data()
plt.scatter(X_train[:, 0], X_train[:, 1], c=ys_train)
```

![knn0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/b93203de-4e91-3c87-0e32-ca0cd97b9e1a.png)

乱数を用いて分類0と分類1の変数を生成する。
trainとついているがこれ自体を与えて学習するのではなく、このデータとの距離を元に学習する。

### 3.1.3．最も近いクラスに分類(Numpy実装)

```Python:
# 距離の計算(ユークリッド距離の2乗)
# https://www.monodukuri.com/gihou/article/2871
def distance(x1, x2):
    return np.sum((x1 - x2)**2, axis=1)

def knc_predict(n_neighbors, x_train, y_train, X_test):
    # 予測した値を保持する空の配列
    y_pred = np.empty(len(X_test), dtype=y_train.dtype)

    for i, x in enumerate(X_test):
        # 各データ点との距離を計算
        distances = distance(x, X_train)
        # 昇順に並び替えてk(n_neighbors)の数だけ頭から該当データのインデックスを取り出す
        nearest_index = distances.argsort()[:n_neighbors]
        # 取り出した近傍のデータから最頻値(モード)のクラスを取得
        mode, _ = stats.mode(y_train[nearest_index])
        # 取得した最頻のクラスを予測クラスとする
        y_pred[i] = mode
    return y_pred

# 可視化
def plt_resut(x_train, y_train, y_pred):
    xx0, xx1 = np.meshgrid(np.linspace(-5, 5, 100), np.linspace(-5, 5, 100))
    xx = np.array([xx0, xx1]).reshape(2, -1).T
    plt.scatter(x_train[:, 0], x_train[:, 1], c=y_train)
    plt.contourf(xx0, xx1, y_pred.reshape(100, 100).astype(dtype=np.float), alpha=0.2, levels=np.linspace(0, 1, 3))

# ハイパーパラメータkを3とする
n_neighbors = 3

xx0, xx1 = np.meshgrid(np.linspace(-5, 5, 100), np.linspace(-5, 5, 100))
# X_test shape:10000, 2
# (2, 100, 100)を2行になるようreshapeして転置しているため
X_test = np.array([xx0, xx1]).reshape(2, -1).T

# k近傍法実行
y_pred = knc_predict(n_neighbors, X_train, ys_train, X_test)
plt_resut(X_train, ys_train, y_pred)
```

![knn1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/1ad25c4a-291e-366b-ad6a-de3e52e43d44.png)

各処理についてはコメント参照(元コードに追記)。
最終的に、予測したy_predを元に等高線(contourf)のグラフを引くことで境界の可視化をしている。

### 3.1.4．最も近いクラスに分類(scikit-learn実装)

```Python:
xx0, xx1 = np.meshgrid(np.linspace(-5, 5, 100), np.linspace(-5, 5, 100))
xx = np.array([xx0, xx1]).reshape(2, -1).T

from sklearn.neighbors import KNeighborsClassifier

knc = KNeighborsClassifier(n_neighbors=n_neighbors).fit(X_train, ys_train)
plt_resut(X_train, ys_train, knc.predict(xx))
```

![knn2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/2131507c-8fc7-c85f-658e-f522668c12fb.png)

Numpyによる実装と同じ結果になっている。
k近傍法の計算自体は複雑なものではないが、Numpyによる実装の後にscikit-learnによる実装に触れるといかにscikit-learnが強力か分かる。

# 4．ハンズオン：k-平均法

## 4.1．演習

### 4.1.1．ライブラリのインポート

```Python:
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
```

### 4.1.2．データ生成

```Python:
def gen_data():
    # グラフ左下
    x1 = np.random.normal(size=(100, 2)) + np.array([-5, -5])
    # グラフ真ん中上
    x2 = np.random.normal(size=(100, 2)) + np.array([5, -5])
    # グラフ右下
    x3 = np.random.normal(size=(100, 2)) + np.array([0, 5])
    return np.vstack((x1, x2, x3))

# データ作成
X_train = gen_data()
# データ描画
plt.scatter(X_train[:, 0], X_train[:, 1])
```

![kmeans0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/6b1150a8-f543-9fbb-9749-ff1b4e24c906.png)

正規分布(平均と標準偏差を指定していないので標準正規分布)に従う乱数+arrayで指定した位置を足すことでarrayの位置周辺で散らばるデータを生成している。

### 4.1.3．クラスタリング(Numpy実装)

```Python:
# 距離の計算(ユークリッド距離の2乗)
def distance(x1, x2):
    return np.sum((x1 - x2)**2, axis=1)

# クラスタ数3
n_clusters = 3
# クラスタの割り当て、クラスタ中止点更新の上限回数を100とする
iter_max = 100

# 各クラスタ中心をランダムに初期化
centers = X_train[np.random.choice(len(X_train), n_clusters, replace=False)]

for _ in range(iter_max):
    prev_centers = np.copy(centers)
    # 距離を保持する行列をまず0で生成
    D = np.zeros((len(X_train), n_clusters))
    # 各データ点に対して、各クラスタ中心との距離を計算
    for i, x in enumerate(X_train):
        D[i] = distance(x, centers)
    # 各データ点に、最も距離が近い(argmin:最小値)クラスタを割り当てる
    cluster_index = np.argmin(D, axis=1)
    # 各クラスタの中心を計算
    for k in range(n_clusters):
        # クラスタkに属するデータのインデックス取得
        index_k = cluster_index == k
        # クラスタkに属するデータの平均で中心点を更新
        centers[k] = np.mean(X_train[index_k], axis=0)
    # 収束判定
    if np.allclose(prev_centers, centers):
        print(prev_centers)
        break

# 可視化
def plt_result(X_train, centers, xx):
    # データを可視化
    plt.scatter(X_train[:, 0], X_train[:, 1], c=y_pred, cmap='spring')
    # クラスタ中心点を可視化
    plt.scatter(centers[:, 0], centers[:, 1], s=200, marker='X', lw=2, c='black', edgecolor="white")
    # クラスタ領域の可視化
    pred = np.empty(len(xx), dtype=int)
    for i, x in enumerate(xx):
        d = distance(x, centers)
        pred[i] = np.argmin(d)
    plt.contourf(xx0, xx1, pred.reshape(100, 100), alpha=0.2, cmap='spring')

# 各データがどのクラスタに属するか保持する空の配列
y_pred = np.empty(len(X_train), dtype=int)
for i, x in enumerate(X_train):
    # 距離を計算
    d = distance(x, centers)
    # 最も距離が近い属するクラスタを取得し、設定
    y_pred[i] = np.argmin(d)

# 可視化
xx0, xx1 = np.meshgrid(np.linspace(-10, 10, 100), np.linspace(-10, 10, 100))
xx = np.array([xx0, xx1]).reshape(2, -1).T

plt_result(X_train, centers, xx)
```

![kmeans1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/b72dad24-fcb9-8a29-dcdc-bb861856db2f.png)

各処理についてはコメント参照(元コードに追記)。
元々目視で確認するとはっきり分かれているデータではあるが、クラスタリングによってそれぞれ適切なクラスタが割り当てられていることが確認できる。

### 4.1.4．クラスタリング(scikit-learn実装)

```Python:
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=3, random_state=0).fit(X_train)

print("labels: {}".format(kmeans.labels_))
print("cluster_centers: {}".format(kmeans.cluster_centers_))

plt_result(X_train, kmeans.cluster_centers_, xx)
```

![kmeans2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/59983d0b-6da5-dcf5-bc8c-a727d5f786e6.png)

Numpyによる実装と同じ結果になっている。
k近傍法と同様にk-平均法も複雑な計算ではないが、scikit-learnを使うとかなりシンプルに実装できる。

labels_；どのクラスタに属しているか
cluster_centers_：各クラスタの中心点

### 4.1.5．クラスタ数を増やしてみる

![kmeans9.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/9d8fbfa3-ed65-3cdf-f242-7b7cab3c1bf1.png)

クラスタを倍の6つとしてみた場合。
可視化による目視で分かる通り、適正なクラスタ数は3つなので無理やり6つに分けようとしている(これに意味はないがそれぞれ半分こにしているのである意味それっぽく分けられていると言えるかもしれない)。

# X．ラビットチャレンジとは
ラビットチャレンジとは、日本ディープラーニング協会認定の講座プログラムの1つ。
E資格を受験するためにはこのラビットチャレンジ等、いずれかの講座プログラムを修了しなければならない。

ラビットチャレンジの特徴は「現場で潰しが効くディープラーニング講座」の通学講座録画ビデオを編集した教材を使用した自習スタイルであるという点。
サポートは他の講座より少なく、受け身ではなく自主的に学んでいく姿勢でなければ進められないが、その分、他の講座に比べると安価であり、手が出しやすい。
ある程度知識がある人、自力で頑張るぞというガッツのある人向けではないかと感じる。

![bnr_jdla.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/389699/bce66671-a2f5-a7f9-de6f-3f87e15c253b.png)