Coursera Machine Learning Week8のメモ

Courseraのマシンラーニング講座を勉強しています。
week8は動画を見ながらメモを取ったので、共有します。
[week6のメモ](http://qiita.com/tackey/items/bf367b534fb235cf4780)より乱雑な点はご了承ください。

# Unsupervised Learning
# Clustering

## Unsupervised Learning :introduction

教師なし学習

ラベルがないデータが与えられる。

それを構造で分ける。

clustering　アルゴリズム

クラスタリングは1つの例

マーケットのセグメンテーション、
ソーシャルネットワーク分析、
コンピュータのデータセンターの組み合わせ
銀河の形成の理解


## K-Means Algorithm

k means 
人気のあるクラスタリング手法


ランダムに2つの点を選ぶ。（クラスタ重心）
2つに分けたいなら2つ。


1）クラスタの割り付けステップ
2）重心の移動ステップ

1）
2つの点のどちらに近いかによってそれぞれの点が2つのどちらに属するかを決める。

2）
重心を色づけされたそれぞれの平均の場所に移動する。
新たな重心が決まる。

そして1に戻る

これを繰り返す。
いつか重心が移動しなくなる。


2つの入力
・クラスタの数
・トレーニングセット（ラベルなし）


1）クラスタ重心をクラスタの数分選ぶ。
2）各サンプルを重心のどれに近いかで分類。最小化する重心に属する。
3）割り振られたサンプルの平均に重心を移動する。
点を割り振られない重心があったらそれは取り除くのが一般的。
クラスタの数は1つ少なくなる。
K個のクラスタが必要な場合はランダムに初期化。


K-meansの応用。

分かれているようには見えないものも分けてくれる。
だからマーケットセグメンテーションにも使える。

## Optimization Objective

K-meansもコスト関数を持っていてそれを最小化しようとする。
・目的関数が何かを知ることはデバッグできること
・局所最適を避ける。


目的関数は
すべてのサンプルに対し、割り振られたクラスタ重心との位置との二乗距離の合計を最小化する。

各店をクラスタの重心に割り振る
重心は変更せず、最小化されるクラスタ重心に割り振る。

サンプルは動かさずに、クラスタ重心を動かし、距離を最小化する。

コスト関数はどんどん最小化されていく。

## Random initialization

k meansの初期化について
クラスタ重心をどのようにランダムに初期化するか
1つのやり方は、
1)サンプルの数よりもKを小さくする。
Kこのトレーニングサンプルをランダムに選ぶ。
そこを重心としてしまう。

もちろん近い2つを選んでしまうことはある。


局所最適に陥ってしまうことがありうる。
その心配がある場合は、複数のランダム初期化を試みると良い。
k-meansをたくさん初期化したくさん実行する。
そうすればグローバルな最適な場所を考えられる。

50-1000回ぐらい。

100この異なるクラスタリング方法が出る。
その中から一番コストが小さいものを選ぶ。ディストーションが小さい。
k~2-10なら繰り返すのはいいこと。
でも大きい場合。100とかのクラスタの場合は複数回やっても大きな違いはない。最初のランダム初期化でかなり良い回が得られている可能性がある。
そんなに回は変わらない。複数やっても。
数が好くなったら複数回やったほうが良い。


## Choosing the number of clusters

クラスタの数の選び方

素晴らしい回答はない。
結果を見てから手動で選ぶとか。
一番一般的なのは手動。

なぜ難しいか。
クラスタは曖昧だからだ。
人によってはデータを見ても2つに捉えたり4つに捉えたりする。
正しい答えなんてない。ラベルが割り振られてないのだし。
これが自動で決めるのが難しい理由。

エルボー法
クラスタの数を変化させていく。
1つの時のディストーション、
2つの時のディストーション、
・・・これを繰り返し、プロットしていく。

エルボー法は、その傾きが大きく変わったところ（下がりづらくなったところ）のクラスタの数を使う。（エルボーぽい））

わかりやすかったら運がいい！そこにしよう

でも実際にはそんなにはっきりとしたエルボーは見つけられない。
その場合はこの手法は使えない。

エルボー法はいつでもいまくいくとは思わないほうがいい。


# Dimensionality Reduction

#Motivation

## Motivation1:Data Compression

別の選び方

マーケットのセグメンテーションの選び方の場合などは
その目的にそったクラスタ数を選ぶ。
例えばTシャツなら、サイズを3つにしたいのか、5つにしたいのか。

例えば、Tシャツビジネスから考えると、顧客に対して多くのサイズがあるほうがいいのか、
サイズを減らしたいのか。
3つと5つどちらかいいかをビジネスの観点から考える。


画像圧縮に使う場合は、どれだけ画質を保ちたいか、圧縮したいのか、など。

手動で選んだり、
エルボー法を使ったり、
ビジネスの観点から考えたりすると良い。


## Motivation 2:Visualization
次元削減

理由は幾つか
データを圧縮、学習スピードアップ


データをたくさん集める。
cmをインチで表現したりと助長なことがある。
そこで次元を削減したい。
1つで十分。
フィーチャーを全て管理するのも大変。

高く相関したフィーチャーがあれば削減したい。

次元を削減することが意味するのは、
2次元であれば、一つのサンプルを示すのに2次元ベクトルが必要だったが、それを一次元の直線で表せるようになったということ。
射影したもの。
1つの実数で1つのサンプルを示すことができる。

メモリ量、データ保存スペースを半減させる。
アルゴリズムを早く走らせる。

これは3次元から2次元への圧縮もあり得る。
1000次元とかのデータでも。

3次元に、大体はある平面に乗っかっているサンプルがあるとする。
そのサンプルを平面に射影したとする。
そうすると、サンプル1つは、その平面上の場所を示すための2つの数字で表せることになる。


次元削減はアルゴリズムを早く走らせる際に用いる。




# Principal Component Analysis

## Principal Component Analysis Problem Formulation


データの可視化

次元削減はデータの可視化の方法を提供してくれる。

膨大なデータセットがあるとする。
データをよりよく理解するには、どう可視化するのがいいか？
フィーチャーが50もあると、50次元だ。
ここで次元削減を考える。

別のフィーチャーベクトルで表せないか。
50次元を要約するような2つの数字とかに。
もちろん自分でその2つはわかるようなものに。

次元削減しプロットしてより理解しやすくする。



次元削減で最も使われているのは
主成分分析、PCA

PCAになにをしてほしいか定義しよう。

データを2次元から1次元に削減したいとする。
それは射影した時に各店と射影された点が近いような直線だ。
つまりPCAは、射影する先として2条和を最小化する。
射影誤差を最小化するものを探す。

平均標準化、フィーチャースケーリングをしておく。
平均0で比較可能なものにしておく。


PCAのゴールは
以下のようなベクトルを探すこと。
自らより次元が低く、射影誤差を低くするようなベクトル。
ベクトルの向きは気にしなくて良い（プラスかマイナスか）

K次元にするなら射影先はK本のベクトルが必要。



PCAと線形回帰の関係。
これらは全く異なるアルゴリズム。
線形回帰はyを予測するために2乗誤差を最小化する直線。
その誤差は直線。y方向の誤差だから。

PCAに於いては、直線と直行した距離を最小化。
PCAにはyは存在せず、すべてのフィーチャーは等しく扱われる。

だからPCAと線形回帰は異なる。



PCAは2乗射影誤差を最小化するような、より低い次元の平面を探す。




## Principal Component Analysis Algorithm


主成分分析のアルゴリズムについて

データの前処理のステップ。
必ずやる。

平均標準化
フィーチャースケーリング
（教師あり学習のと似ている）

各フィーチャーの平均を探し、x-平均する。
平均は0に成る。
スケールが違うのであれば、
比較可能にスケーリングする。
フィーチャーの値の範囲に関する何らかの指標で割る。
最大値ー最小値や、標準偏差。

そのあとにPCA。

射影2乗誤差和が最小になるようなベクトルを探す。
次元を削減するというのは、サンプルを表すデータを射影し、
もとより少ない数の数字で表せるようにすること。

PPCAの任務は
射影する先のベクトルを考え出すこと、
そして射影した先の数字を計算すること。

数学的証明は大変。


共分散行列を計算し、
svd関数をoctaveで使えば良い

この共分散行列はnxn行列。
x*xTの足し合わせだから。

svdの結果、U,S,Vを得る。
U行列もnxn

削減したい場合はu行列の最初のk本を取る。

そして元のデータセットを持ってきて、
U行列の最初のk本（n x k 行列）にかける。
z = UreduceT * X 
k x n  * n x 1 = k x 1

トレーニングセット、CVセット、テストセットでも良い。

まとめると
平均標準化とと、フィーチャースケーリングをして
行分散行列Sigmaを計算して、
svdルーチンでU,S,Dを計算し、
Uの最初のk業を持ってきて、
それにxをかける。

# Applying PCA

## Reconstruction from Compressed Representation

圧縮アルゴリズムとしてのPCAについて話した。

これが圧縮というのなら、元に戻す方法があるはず。
戻すにはどうすれば良いだろうか？

2次元を1次元の直線に表した場合、
近似的な2次元に戻す方法は何か？

z = UreduceT * x　で次元を下げたから
X approx = Ureduce * z

(Rn = n x k * k x 1)

Xapproxは元のxに近い値となる。

これが近似したものに戻す方法
オリジナルデータの再構築、と読んだりする。


次ではkの選び方について扱う。

## Choosing the Number of Principal Components

kは主成分分析のパラメータとなる。
主成分の数とも呼ばれる。

どうやって選ぶことが多いのかについて話そう。

PCAは2乗射影誤差の平均を最小化しようとする。
データ全体の分散は、手本xiの長さの平均。

経験則として、
2乗射影誤差の平均をデータ全体の分散で割って、1％以下になるようなものを選ぶ。

0,01なら、「99%の分散が保持されている」、という。


0.01以外には、0.05を用いて、95%の分散が保持されている、と言ったりする。
0.10ぐらいまではやったりする。
95~99が最も一般的。


どう実装するか。

k = 1から始めて、PCAを実行する。
そして分散が99%保持されているか確認し、
されていなければk=2
それを繰り返し、99%保持される最小値を見つける。
これは方法の1つだが、効率が悪い。

PCAを実行するなら、
svdの際にいいやり方がある。

svdをコールしたら,
Sという行列を返す。
これは正方行列。
対角成分だけ、それ以外は0

この対角成分に着目して計算すると、

1 - (sigma k Sii / sigma n Sii ) <= 0.01
となるようなkをテストすれば良い。

これをやれば、svd関数は1回で済む。
効率的だ。


まとめると

PCAのkを選ぶ際は
svdを一回使い、
Sを求めkを計算する。

手動で選びたいとする。
その場合も、パフォーマンスを表現するのは、分散の何％が保持されているかを説明するのが良い。

1000次元のデータでも、高い相関を持つデータが存在するから、
次元を下げつつ、分散を維持することができるだろう。


## Advice for Applying PCA


スピードアップをどうやるのかについて。
その他アドバイス

教師あり学習のスピードアップにPCAを用いることが多い。

xiが1万次元のベクトルだとする。
コンピュータービジョンなら100x100とか。

そのようなベクトルを食わせると時間がかかる。

PCAで持って次元を減らすことができる。

まず最初に入力のみ引き抜いて
PCAを実行し、1000次元のフィーチャーベクトルを得る。
それを元にあらたなトレーニングセットを作る。
z1とy1のように。
その上で学習アルゴリズムに食わせて、仮説を得る。
これは次元削減されたものを元にした仮説だ。

新しい手本を得たら、
テストのxも対応するzにして、仮説に食わせる。

PCAがやっていることはxからzのマッピングを定義すること。
これはトレーニングセットだけに対してはしらせることで定義すべき。
Ureduceは学習したパラメータのようなもの。
トレーニングセットにPCAして得ること。
そしてそれをCVセットやテストセットにかませてzを得ること。

10倍とか削減するのはよくあること。

PCAの応用例。
圧縮という話。メモリやディスク容量削減、スピードアップ。

kを選ぶために保持される分散のパーセンテージを調べた。
99%の分散を保持するという基準。

他には可視化という視点。
2、3次元にプロットすればわかりやすい。

これらがkの選び方。


こんなことはしないでほしい。
オーバーフィッティングを防ぐためのPCA。

それは悪い使い方。
うまくいくとは思う。
オーバーフィッティングを防ぐなら正規化を使うこと。

PCAはxだけを見て次元を削減する。
yを見てない。
貴重な情報を削減してしまっている可能性。
多くの場合は正規化の方がよく働く。
正規化なら、yの値が何か知っているから貴重な情報を捨て去る可能性が低い。


他の間違った使い方。
PCAを用いたプランを作る際に、
・PCAなしでこれをやったらどうだろう？
と考えてみよう。
できるだけオリジナルのデータでやってみて、
それでうまくいかなければPCAを検討しよう。
オリジナルのデータに対して、単純に学習アルゴリズムを訓練してみよう。
それでうまくいかない、実行速度が遅い、メモリやディスク容量がきつい、となって初めて生のデータでは難しいという強い理由があって、PCAを検討しよう。
PCAなしでもうまくいくことはある。

学習アルゴリズムの実行時間を減らすのに一番よく使う。