Coursera Machine Learning の受講記録（Week8）

[Machine Learning by Stanford University](https://www.coursera.org/learn/machine-learning/home/welcome) WEEK8 のまとめ
# 教師なし学習
## Introduction
教師なし学習はラベル付けされていないトレーニングセットからある法則やカテゴライズを見つける手法。
例）

- マーケットセグメンテーション
- SNSの解析

## K-Means Algorithm (k-means クラスタリング）
## k-meansの概要
k-means クラスタリングは、データをあるグループに分類する方法として最もポピュラーな方法。以下の順番で解析する
- 1. ランダムに初期のk個のポイントを選ぶ。（このk個のポイントを cluster centroidsと呼ぶ）
- 2. 全てのデータをk個のcluster centroidsのうち近い方に分類する
- 3. 各々のグループの中心点を計算し、新たなcluster centroidsとする。
- 4. 2,3を繰り返す


## 使用する変数
![Kobito.I73ewF.png](https://qiita-image-store.s3.amazonaws.com/0/102387/c0f92037-4ebf-951f-84e7-60959e2dd87e.png "Kobito.I73ewF.png")

##アルゴリズム

```octave:
Randomly initialize K cluster centroids mu(1), mu(2), ..., mu(K)
Repeat:
   for i = 1 to m:
      c(i):= index (from 1 to K) of cluster centroid closest to x(i)
   for k = 1 to K:
      mu(k):= average (mean) of points assigned to cluster k
```

- 最初のループはcluster centroidの決定 c(i)はトレーニングデータk(i)に対応するcluster centroid。数式で示すと以下。
![Kobito.mUamn5.png](https://qiita-image-store.s3.amazonaws.com/0/102387/ec14aa75-2946-4079-f420-7d450e858398.png "Kobito.mUamn5.png")

- 2つめのループは新たなcluster controidを決定するステップ。数式で示すと以下。
![Kobito.Xhiniz.png](https://qiita-image-store.s3.amazonaws.com/0/102387/54006ee0-297d-01b6-41aa-620a806a5745.png "Kobito.Xhiniz.png")
もし、cluster centroidが動かない場合は再度ランダム初期化をしてやり直すか、該当のクラスタグループを省いてしまうかの対応をする。

- 繰り返しにより、アルゴリズムは収束する。

## コスト関数
![Kobito.Jofxd6.png](https://qiita-image-store.s3.amazonaws.com/0/102387/03615c9d-eeb0-111a-de84-436deca0786c.png "Kobito.Jofxd6.png")

これは、トレーニングセットのそれぞれとcluster centroidの距離の平均。

## ランダム初期化
cluster centroidsのランダム初期化について
k-meansはしばしば局所的な最小値に陥ることがあるので、ランダム初期化を複数回行い、最小のコスト関数を取る値を解とする。
具体的なコード例は以下の通り

```octave:
for i = 1 to 100:
   randomly initialize k-means
   run k-means to get 'c' and 'm'
   compute the cost function (distortion) J(c,m)
pick the clustering that gave us the lowest cost
```

## クラスタ数の選択方法
k-meansのクラスタ数の取り方の手法として「エルボウ法」がある。
![Kobito.FRZFDY.png](https://qiita-image-store.s3.amazonaws.com/0/102387/fffeec61-d6f1-1be2-65b3-eb3d2cb0eae4.png "Kobito.FRZFDY.png")
クラスタ数を変化させて、「肘」にあたるクラスタ数を取るというもの。
ただ、実際には肘にあたる部分がなだらかではっきりと判断できない事も多々ある。

# 次元圧縮
## 次元圧縮の動機
- 動機1: データの圧縮
	- 相関関係のある変数等余計なデータを削減したい場合がある
- 動機2: データの可視化
	- データの可視化をしたい場合変数が多すぎると難しい為、次元を削減したい場合がある

## PCA(主成分分析)
次元圧縮の最もポピュラーな手法がPCA(主成分分析)

### 次元削減のイメージ
2次元から1次元に、3次元から2次元に次元圧縮するイメージは以下の図の通り
![Kobito.nsOSQc.png](https://qiita-image-store.s3.amazonaws.com/0/102387/f9621241-2b23-8e01-31d8-7bfcecf83822.png "Kobito.nsOSQc.png")

### PCA 〜データの前処理〜
PCAを行う前に必ず行わなければいけない前処理が以下
(フィーチャースケーリング、平均標準化）
![Kobito.cUF92v.png](https://qiita-image-store.s3.amazonaws.com/0/102387/58706aa7-e724-9807-a132-6503f4994177.png "Kobito.cUF92v.png"

### PCA 〜n次元からk次元への削減の手順〜
- 1. Σ（共分散行列）の計算
![Kobito.YPsUA8.png](https://qiita-image-store.s3.amazonaws.com/0/102387/fe0afcb2-d988-e4ce-f693-82dd2748323e.png "Kobito.YPsUA8.png")
★Xはn×1行列、X'は1×n行列なので、Σはn×n行列
- 2. 共分散行列Σの固有ベクトルを計算する
	- octaveでは以下のコードになる

```octave:
[U,S,V] = svd(Sigma);
```

U,S,Vはそれぞれ行列が返ってくるが、Σの固有ベクトルはUとなる。(Uのみ使う）UはΣ同様 n×n行列。

- 3.Uの最初のk列を取得し、n次元からk次元にもとの行列Xの次元を削減したベクトルZを計算する。octaveでの実装は以下の通り。
![Kobito.XxxE80.png](https://qiita-image-store.s3.amazonaws.com/0/102387/e96624c3-d297-16d7-681c-62a4cb69929c.png "Kobito.XxxE80.png")


### PCA 〜削減したk次元から元のn次元への戻し方〜
![Kobito.nGkXPN.png](https://qiita-image-store.s3.amazonaws.com/0/102387/2425f2f5-e41c-9199-25d3-cf3be6807051.png "Kobito.nGkXPN.png")
なので、
![Kobito.ALFuhG.png](https://qiita-image-store.s3.amazonaws.com/0/102387/f2139e91-0a70-8bef-2d46-774d20fbd4df.png "Kobito.ALFuhG.png")

### PCA 〜次元数の選び方〜
n次元からk次元に圧縮する際、そのkの求め方（=どれだけ次元を圧縮できるか）でよく使う手法は以下

二乗射影誤差と全体の分散の比率を取って、1%未満とする。
(= 99%の主成分が保持されている状態）
![Kobito.8rqKWD.png](https://qiita-image-store.s3.amazonaws.com/0/102387/15c2e877-8b48-b3a6-7298-4717193bda6e.png "Kobito.8rqKWD.png")


具体的なoctaveでの実装方法は以下
![Kobito.AgQNoF.png](https://qiita-image-store.s3.amazonaws.com/0/102387/d1537246-2d22-7a1e-faac-d4069f3ec351.png "Kobito.AgQNoF.png")


### PCA適用時のアドバイス
- PCAの適用はトレーニングセットにのみ行い、n次元の元のベクトルXから圧縮したk次元のベクトルZへのマッピング情報を得て初めて、クロスバリデーションセットやテストセットに適用すること
- PCAをアルゴリズムのスピードアップ、メモリやディスク等の削減、データの可視化の為に利用するのは良い使い方。変数の数を減らしてオーバーフィッティングを防ぐために利用するのは悪い使い方。オーバーフィッティングを防ぐには、正規化を用いる事。
- PCAを使わずに元の次元のデータそのままでまずは機械学習を行ってみる事を推奨する。