教師なし学習(Unsupervised Learning)

クラスタリング(Clustering)

教師なし学習: イントロダクション(Unsupervised Learning: Introduction)

ラベルなしのデータセットから学習することを、教師なし学習(Unsupervised Learning)という。

教師なし学習のトレーニングセットには、ラベルがない。なので教師なし学習では、データセットからデータ構造を探す。

データセットからデータ構造を探すためにクラスタリングというアルゴリズムがある。

データセットからデータ構造を探すためのアルゴリズムは、他にも幾つかあるが、まずはクラスタリングを学ぶ。

K-Meansアルゴリズム(K-Means Algorithm)

クラスタリングアルゴリズムであるK-Meansアルゴリズムを学ぶ。

K-Meansアルゴリズムを文章で書くと下記のとおり。

1. 各クラスタの中心点(Centroid)を決める: データ$x$と同次元にあるK個のクラスタの中心点 $u_1, u_2,…, u_{K} \in \mathbb{R}^{n}$ を求める
2. データセットの要素をクラスタの割り付ける: 中心点$u_1, u_2,…, u_{K}$と$x$との距離を求めて、最も距離が近いクラスタを割り付ける
3. クラスタの中心点を更新する: クラスタへ割り付けられた要素$x$の平均を算出して、新たなクラスタの中心点(Centroid)を更新する
4. クラスタの割り付けによる移動がなくなるまで2-3を繰り返す

目的関数の最適化(Optimization Objective)

K-Meansアルゴリズムの目的関数は、$x$とクラスタの中心点$u$を使って下記のように定義される。

$$ \displaystyle J(c^{(1)},…,c^{(m)},u_{1},…,u_{K}) = \frac{1}{m} \sum_{i=1}^{m} |x^{(i)} - u_{c^{(i)}}| $$

K-Meansアルゴリズムでは、この目的関数を最小化するクラスタを選択することが推奨される。

$$ \displaystyle min_{c^{(1)},…,c^{(m)},u_{1},…,u_{K}} J(c^{(1)},…,c^{(m)},u_{1},…,u_{K}b $$

ランダム初期化(Random Initialization)

最初にランダムにクラスタをトレーニングセットにピックする。

K-Meansアルゴリズムは局所最適解に収束しうるが、最適解を得るために、K-Meansアルゴリズム100回実行して、その中でコスト関数が最も小さくなるものを選べば良い。

クラスタ数の選択(Choosing the Number of Clusters)

クラスタの数はどうやって選ぶのか？

多くの場合は、人が決める。

自動的に決める方法とし、エルボー法というアルゴリズムがある。

エルボー法はクラスタ数$K$を徐々に増やしていき、コスト関数の変化量が一番大きいクラスタ数$K$を選ぶ方法。

ただし、クラスタ数$K$を増やしても、コスト関数の変化量があまりかわらない場合は、クラスタ数を決めることができない。

その場合は、そもそもどういった目的でクラスタを分けたいのか、ということからクラスタ数を決める。

次元数の削減(Dimensionality Reduction)

動機(Motivation)

動機Ⅰ: データ圧縮(Motivation I: Data Compression)

データ圧縮は、より少ないメモリやディスク容量にデータを圧縮するだけでなく、学習アルゴリズムのスピードアップにもなる。

2次元から1次元に削減する場合、2次元の要素${x^{1},x^{2},…,x^{n}} \in \mathbb{R}^{2}$を1次元に射影するという近似を行い、1次元の要素${z^{1},z^{2},…,z^{n}} \in \mathbb{R}^{1}$を求める。

次元数が増えても、n次元からk次元に削減する場合、n次元の要素${x^{1},x^{2},…,x^{n}} \in \mathbb{R}^{n}$をk次元に射影するという近似を行い、k次元の要素${z^{1},z^{2},…,z^{n}} \in \mathbb{R}^{k}$を求める。

動機Ⅱ: データ可視化(Motivation II: Visualization)

次元数を削減することで、データを可視化できるようになる。

データを可視化できれば、よりデータを理解できるようになる。

主成分分析(Principal Component Analysis)

主成分分析問題の定式化(Principal Component Analysis Problem Formulation)

次元数を削減するアルゴリズムのうち、最もポピュラーなのは主成分分析(Principal Component Analysis)、PCAとも呼ばれるアルゴリズムである。

PCAの原理は、n次元のデータ$x$をk次元まで減らすとき、PCAはn次元空間でのk次元のベクトルへの投射した時の距離(投射誤差(Projection Error))を最小にするベクトルを見つけることである。

2次元から1次元に削減する場合は、2次元の各点からの直線へ射影した距離を最小化するベクトルを選択する。

3次元から2次元に削減する場合は、3次元の各点から平面へ射影した距離を最小化するベクトルを選択する。

PCAは線形回帰と一緒ではない。

主成分分析問題のアルゴリズム(Principal Component Analysis Algorithm)

まず、必ず説明変数のスケーリングを行い、説明変数を比較可能な範囲にする。

平均値$u_{j}$を計算する。

$$ u_j = \frac{1}{m} \sum_{i=1}^{m} x_{j}^{(i)} $$

$x_{j}^{(i)}$を$x_{j} - u_{j}$を$\sigma$で割った値で置き換える($\sigma$は標準偏差)。

$$ x_{j}^{(i)} = \frac{x_{j} - u_{j}}{\sigma} $$

次に共分散行列(Covariance Matrix)を計算する。

$$ \sum = \frac{1}{m}\sum^n_{i=1}(x^{(i)})(x^{(i)})^{\mathrm{T}} $$

Octaveでは、下記のように計算する。

sigma = (X'*X)/m;

共分散行列の固有値(eigenvector)$U$を計算する。

$$ AU = \lambda U $$

Octaveでは下記のように計算する。

[U,S,V] = svd(sigma);

新しい次元ベクトルzzを固有ベクトル (eigenvector)から計算する。

$$ Z = U^{T}X $$

Octaveでは下記のように計算する。

Ureduce = U(:,1:k);
Z = Ureduce'*X;

上記の式では、$k$まで次元を減少させたいので$n \times n$の行列$U$の最初の$k$個の固有ベクトルを使って計算している。

Applying PCA

圧縮状態からの復元(Reconstruction from Compressed Representation)

固有値$U$の左からかけることで、元の行列$X$が求まる。

$$ Z = U^{T}X \\
UZ = X_{approx} $$

主成分の数の選択(Choosing the Number of Principal Components)

圧縮する次元数$k$を選ぶためのガイドラインを与える。

$X$と$X_{approx}$の差の2乗をとって割合を計算して、$0.01$以下であれば良い。

$$ \frac{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)} - x_{approx}^{(i)}||}{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2} \leq 0.01 $$

$0.01$以外に$0.01〜0.15$くらいまでなら一般的に有効な値となる。

この式を使って、下記のように$k$を$1,2,3…,n$と加算していって、$0.01$以下となる値を見つける。

1. kを1に初期化する
2. $U_{reduce}$, $z^{(1)},z^{(2)},…,z^{(m)}$, $x_{approx}^{(1)},…,x_{approx}^{(m)}$を計算する
3. $\frac{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)} - x_{approx}^{(i)}||}{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2}$を計算する
4. 3で計算した値が$0.01$を超える場合は$k=k+1$として2に戻る

下記の式はより効率的な式に置き換えることが可能。

$$ \frac{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)} - x_{approx}^{(i)}||}{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2} \leq 0.01 $$

共分散行列の固有値(eigenvector)$U$の計算において算出される固有値行列$S$を使って、下記のように書ける

$$ 1 - \frac{\sum_{i=1}^{k} S_{i,i}}{\sum_{i=1}^{n} S_{i,i}} \leq 0.01 \\
\frac{\sum_{i=1}^{k} S_{i,i}}{\sum_{i=1}^{n} S_{i,i}} \geq 0.99 $$

Advice for Applying PCA

PCAはトレーニングセットにだけ実行して、トレーニングセットへPCAを使って得られた$U_{reduce}$を、クロス検証セットやテストセットに適用する。クロス検証セットやテストセットに対してPCAを適用してはいけない。

PCAはオーバーフィッティグを防ぐ方法として使ってはいけない。おそくらうまくいくが、使ってはいけない。

オーバーフェッティングを防ぐなら、正規化を使うべきで、正規化の方が単純にうまく機能する。

PCAは次元数を削減するため、重要な何かを捨てしまってしまう可能性もあるため、おすすめしない。