Coursera機械学習入門コース(8週目 - 教師なし学習(K-MeansとPCA))

[Courseraの機械学習コース](https://www.coursera.org/learn/machine-learning/home/welcome)の8週目です。今回は教師なし学習で、クラスタリングと次元削減についてです。クラスタリングはK-Meansを、次元削減は主成分分析(PCA)を学習します。
記事[「Coursera機械学習入門オンライン講座虎の巻(文系社会人にオススメ)」](https://qiita.com/FukuharaYohei/items/b2143413063376e97948)を最初に読むことをお勧めします。

# サマリ
実績時間：約6時間
目安時間：約5.5時間(正確には5時間21分)
※コースに各章の時間目安が書かれていて、それを足しただけです。

## 一覧
|No.|章|目安時間|内容|
|:-:|:--|:-:|:--|
|1|Unsupervised Learning|57分|教師なし学習|
|1.1|Clustering|37分|クラスタリング(K-Means)|
|1.2|Review|20分|K-Meansのクイズ|
|2|Dimensionality Reduction|264分|次元削減|
|2.1|Motivation|15分|次元削減の動機|
|2.2|Principal Component Analysis|24分|主成分分析(PCA)|
|2.3|Applying PCA|25分|主成分分析使用時のTips|
|2.4|Review|200分|主成分分析のクイズとK-Meansも含んだプログラム演習|

# 1. Unsupervised Learning
## 1.1. Clustering
### 1.1.1. Unsupervised Learning: Introduction
Video:3分
教師なし学習(Unsupervised Learning)について。
教師なし学習(Unsupervised Learning)は今まで学習した教師あり学習(Supervised Learning)と異なり、正解(ラベル)がありません。**データの背後に存在する本質的な構造を抽出する**のが教師なし学習です。
代表的な例としてクラスタリングがあります。クラスタリングはデータのかたまり(クラスタ)を見つけ、かたまりごとに分類します。顧客セグメンテーションやソーシャルネットワークなどで使用します。

### 1.1.2. K-Means Algorithm
Video:12分
K-Meansと呼ぶクラスタリングのアルゴリズムについてです。
以下のステップでクラスタリングを行います。

#### ステップ1 ランダムにクラスタの重心を決定
重心は$\mu$で表し、$n$個のベクトルで表すことができる。クラスタの重心の数$n$は自分で指定します。

```math
\mu_1, \mu_2, \cdots \mu_K \in \mathbb{R}^n
```

#### ステップ2 クラスタ割当
各データ$x^{i}$に対して最も距離が近いクラスタを割り当てます。例えば、2つ目のデータ$x^{2}$に一番近いのが$\mu_3$だった場合、$c^{(2)}=3$と表現します。

```math
c^{(i)} := K
```

#### ステップ3 クラスタ重心の移動
それぞれのクラスタの重心を各データの平均に計算しなおします。

あとはステップ2とステップ3を指定の回数だけ繰り返します。
記事[「K-means 法を D3.js でビジュアライズしてみた」](http://tech.nitoyon.com/ja/blog/2013/11/07/k-means/)を見ると理解が容易です。


### 1.1.3. Optimization Objective
Video:7分
K-Meansのコスト関数です。
教師なし学習でもコスト関数があります。教師なし学習であってもコスト関数を持つ理由は、以下の2点です。

1. K-Meansが正しく動いているかを確認するため
2. 局所最適を避け、より良いクラスタを見つける助けとするため

K-Meansのコスト関数は以下の式で、このコスト関数を最小化します。クラスタからの距離の二乗の和です。

```math
{J(c^{(1)},...,c^{(m)},\mu_1,...,\mu_K) = \frac{1}{m} \sum^m_{i=1} ||x^{(i)} - \mu_{c^{(i)}}||^2}
```

### 1.1.4. Random Initialization
Video:7分
最初の重心をどのようにランダムに選択するかです。
K-Meansは最初のステップである[「ランダムにクラスタの重心を決定」]()にランダム性があるため、局所最適解に陥りやすいです。よりよい解を得るために以下のことをするらしいです。

- ランダムにデータ$x^{(i)}$をピックアップして、$\mu_{i}$に設定
- そして、局所最適解に陥らないようにK-Meansを50回から1000回ほど実施して、コスト関数が最小の結果を選択

### 1.1.5. Choosing the Number of Clusters
Video:8分
クラスタ数の決め方。
どうすれば最適なクラスタ数を決められるかという話です。
エルボー法(Elbow Method)という方法があります。2次元のグラフで横軸にクラスタ数、縦軸にコスト関数の結果をとり、曲線が緩やかになった点に決める方法です(下グラフの左がその例で、クラスタ数を3つに決定)。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/f439610b-4b2d-822e-fcbc-23ce8aa98071.png)
ただ、上グラフの右側のように曲線が緩やかにならないこともあり、必ず使える手法ではありません。

目的に応じてクラスタ数を決める方法もあります。例えば、あらかじめTシャツのサイズ種類数によって決める、などです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/f916c3c4-509a-2e17-3c95-9c202a1225f9.png)


## 1.2. Review
### 1.2.1. Lecture Slides
Reading:10分
K-MeansのスライドPDF。

### 1.2.2. Unsupervised Learning
Quiz:5問, Reading:10分
もともとK-Meansは知っていて、動かしたこともあるので簡単でした。100%で一発合格です。

# 2. Dimensionality Reduction
## 2.1. Motivation
### 2.1.1. Motivation I: Data Compression
Video:10分
次元削減を行うメリットととしてデータ圧縮についてです。
下図のように3次元を2次元にできたらデータが圧縮できていいよという話です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/0f643def-c3f1-bdb8-2564-ecddc64585e3.png)

### 2.1.2. Motivation II: Visualization
Video:5分
次元削減を行うメリットととして可視化についてです。
たくさんある特徴量を2つに削減できたら見た目わかりやすいよ、という話です。下の図は50ある国の特徴を2次元に削減した場合のグラフです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/62a90e5c-21db-1277-ce85-936a87d62c3a.png)

## 2.2. Principal Component Analysis
### 2.2.1. Principal Component Analysis Problem Formulation
Video:9分
主成分分析(PCA)について。
PCA (Principal Component Analysis)は主成分分析とも呼ばれ、次元削減で人気のあるアルゴリズムです。
下図の左側が2次元を1次元にしているイメージです。数式では、$u^{(1)} \in \mathbb{R}^n$と表現します($u$はベクトルです)。右側の図は3次元を２次元に削減しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/08c12a03-7134-cbcf-2c4a-4a2847cde9d0.png)

主成分分析、次元削減時に各データとベクトルとの距離が最小になるようなベクトルを見つけます。
線形回帰とイメージとしては似ていますが、実態は異なります。

- 線形回帰(下図の左)：**正解である$y$との差を最小**にする
- 主成分分析(下図の右)：**ベクトルとの距離を最小**にする

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/7441463c-7412-a48e-11fd-34ec22b324d8.png)

### 2.2.2. Principal Component Analysis Algorithm
Video:15分
主成分分析のアルゴリズム。

#### ステップ1 前処理
主成分分析の前処理として平均標準化(Mean Normalization)を必ず行います。平均標準化は、1. 相加平均を求めて2. その結果との差異を計算します。下記のように相加平均を求め、$x_j^{(i)}$を$x_j^{(i)} - \mu_j$に置き換えます。

```math
\mu_j = \frac{1}{m} \sum_{i=1}^m x_j^{(i)} \\
```

また、前処理として必要に応じて[Feature Scaling](https://qiita.com/FukuharaYohei/items/bcd676691f61dac8d0c8#23-gradient-descent-in-practice-i---feature-scalingvideo8%E5%88%86-reading3%E5%88%86)を行う場合もあるようです。
※どんな「必要」かの言及がなかったですが、「常にやった方がよさそう」と考えています。

#### ステップ2 主処理
主成分分析で$n$次元を$k$次元に減らします。
主成分分析は数学的に難しくコースの範囲外とのことでした。Matlab/Octaveを使ってどう計算してくかを説明しています。
※Matlab/Octaveに依存した内容に見えたので詳細省略(他言語・パッケージでも同様なのかもしれないですが・・・)

## 2.3. Applying PCA
### 2.3.1. Reconstruction from Compressed Representation
Video:3分
PCAで削減された次元を元に戻す方法です。
次元削減をしたときに一部の情報が欠落しているので、完全に元に戻すことができません。元の値を比較して主成分分析の誤差を求めるために復元します。
※Matlab/Octaveに依存した内容に見えたので詳細省略(他言語・パッケージでも同様なのかもしれないですが・・・)

### 2.3.2. Choosing the Number of Principal Components
Video:10分
次元をいくつまで削減すべきかを説明。
次元を削減した時に、どれだけ分散が保持できるか(Variance is retained)を評価基準とします。
下記の平均射影自乗誤差(Average squared projection error)を分散の総和(Total Variance in the data)を使って計算します。

- 平均射影自乗誤差 : $\frac{1}{m} ||x^{(i)} - x^{(i)}_{approx}||^2$
- 分散の総和 : $\frac{1}{m} ||x^{(i)}||^2$

※$x^{(i)}_{approx}$は次元削減後に$x^{(i)}$を復元したときの値
※分散の総和(Total Variance in the data)は、既に前処理で平均標準化をしているのでこの式で分散となります

1から$\frac{平均射影自乗誤差}{分散の総和}$を引いた値が「どれだけ分散が保持できるか(Variance is retained)」で、99%を超えることが望ましいです。ただ、95%や90%をしきい値とすることもあるようです。

```math
{variance \hspace{3pt} explained = 1 - \frac{\sum^m_{i=1} ||x^{(i)} - x^{(i)}_{approx}||^2}{\sum^m_{i=1}||x^{(i)}||^2}
}
```

### 2.3.3. Advice for Applying PCA
Video:12分
主成分分析を使う際のアドバイス。

#### アドバイス1 PCAの計算は訓練データだけで行う
評価・テストデータセットに対しては訓練データを使ってできた計算式を使う

#### アドバイス2 過学習対策を目的として使わない
[ハイバリアンス(過学習)の対処法として「特徴量を減らす」](https://qiita.com/FukuharaYohei/items/25a76132b420cea901f2#124-deciding-what-to-do-next-revisited)とありましたが、そのための方法として主成分分析は使うべきでありません。過学習対策としては正則化(Regularization)を使うべきです。
主成分分析は正解ラベル$y$と関係なく情報を捨てます。たとえ99%の情報を保持していたとしても、捨てた1%が重要な情報である可能性もあります。重要性を考慮せずに捨てるというデメリットを負った主成分分析をするよりは、正則化(Regularization)の方が過学習対策としては理にかなっています。

#### アドバイス3 主成分分析を最初のシステム設計に組み込まない
主成分分析を(可視化ではなく)データ圧縮の目的として最初のシステム設計に組み込むのではなく、まずは素のデータで機械学習を実施すべきです。主成分分析は正解ラベル$y$と関係なく情報を捨てているので、捨てたデータが重要な可能性もあります。メモリエラー等で処理不可能のような状態で無い限り、最初は素のデータで実施すべきで、機械学習のアルゴリズムは機能することを確認した後、スピード改善などの対策として主成分分析をシステム設計に組み込みます。

## 2.4. Review
### 2.4.1. Lecture Slides
Reading:10分
主成分分析のスライドPDF。

### 2.4.2. Principal Component Analysis
Quiz:5問, Reading:10分
簡単でした。100%の一発クリア。
主成分分析のMatlab/Octave依存の問題があるとわからないな、と思っていましたが、そんな問題なかったので楽にクリアできました。

### 2.4.3. K-Means Clustering and PCA
Programming Assignment:180分
K-Meansと主成分分析のプログラム演習。
[GitHub](https://github.com/atinesh-s/Coursera-Machine-Learning-Stanford/tree/master/Week%208)を見たので1時間弱で終了。
K-Meansは画像圧縮について含んでいて、わかりにくかったので、記事[「機械学習を使って画像の圧縮をしてみた」](https://qiita.com/Hironsan/items/fb6ee6b8e0291a7e5a1d)を参考にしました。
主成分分析は顔画像の主成分分析について含んでいます。

# 感想
K-Meansは以前使ったこともあるので、ある程度知っていて楽でした。主成分分析はきちんと学んだのが始めてだったので非常に勉強になりました。この辺まで来ると、機械学習のエキスパートになった気がしてきます(気のせい)。Kaggleに挑戦したくなってきます。

# 関連記事
私より詳しくまとめてくれています。

- [Coursera Machine Learning (8): 教師なし学習 (K-Means)、主成分分析 (PCA)](https://qiita.com/katsu1110/items/10ae4a62cfd37e37cd0b)
- [カンニング用GitHub](https://github.com/atinesh-s/Coursera-Machine-Learning-Stanford/tree/master/Week%208)
- [Coursera MachineLearning 8週目　まとめ](https://makuramarks.com/coursera-machinelearning-8-week)
 
他の週のリンクです。

- [Coursera機械学習入門コース(1週目 - 線形回帰と線形代数)](https://qiita.com/FukuharaYohei/items/44d97f411f0b1baaa42c)
- [Coursera機械学習入門コース(2週目 - 重回帰、多項式回帰、正規方程式)](https://qiita.com/FukuharaYohei/items/bcd676691f61dac8d0c8)
- [Coursera機械学習入門コース(3週目 - ロジスティック回帰、正則化)](https://qiita.com/FukuharaYohei/items/270c629fd74a7da4b9da)
- [Coursera機械学習入門コース(4週目 - ニューラルネットワーク)](https://qiita.com/FukuharaYohei/items/6337dd992ebde6a744fa)
- [Coursera機械学習入門コース(5週目 - ニューラルネットワークと誤差逆伝播法)](https://qiita.com/FukuharaYohei/items/e7d60e371c076a0c215a)
- [Coursera機械学習入門コース(6週目 - 様々なアドバイス)](https://qiita.com/FukuharaYohei/items/25a76132b420cea901f2)
- [Coursera機械学習入門コース(7週目 - SVM)](https://qiita.com/FukuharaYohei/items/a67a8ae381b54e4ee0ea)
- Coursera機械学習入門コース(8週目 - 教師なし学習(K-MeansとPCA)) <- 本記事
- [Coursera機械学習入門コース(9週目 - 異常検知、レコメンデーション)](https://qiita.com/FukuharaYohei/items/32caeaca6f77bf6f92dd)
- [Coursera機械学習入門コース(10週目 - ビッグデータ対応)](https://qiita.com/FukuharaYohei/items/1e33cb05a5833d22fe4b)
- [Coursera機械学習入門コース(11週目 - 写真OCR)](https://qiita.com/FukuharaYohei/items/46c60cf591223915e6b4)