機械学習を学ぶのに最も適した教材と言われる、Machine Learning | Coursera を受講しているので、復習も兼ね学んだ内容を簡潔にまとめてみようと思います。
第八弾は、とうとう教師なし学習 (Unsupervised Learning)に入っていきます。K-Means、PCAという、わかりやすく、役に立つアルゴリズムを学びます。
過去の記事
Coursera Machine Learning (1): 機械学習とは？単回帰分析、最急降下法、目的関数
Coursera Machine Learning (2): 重回帰分析、スケーリング、正規方程式
Coursera Machine Learning (3): ロジスティック回帰、正則化
Coursera Machine Learning (4): ニューラルネットワーク入門
Coursera Machine Learning (5): ニューラルネットワークとバックプロパゲーション
Coursera Machine Learning (6): 機械学習のモデル評価（交差検定、Bias & Variance、適合率 & 再現率）
Coursera Machine Learning (7): サポートベクターマシーン、カーネル
K-Means
教師なし学習 (Unsupervised Learning)では、データ$x$がラベル付けされておらず（$x^{(i)}$に対応する$y^{(i)}$がない）、アルゴリズム自らがデータの構造を見つけなければいけません。
その代表例がクラスタリング (Clustering) で、データからパターンを抽出し、複数の似た者同士のグループにまとめます。例えば服を売り出すとき、サイズの種類をどれくらいにすればいいか決めるときに使えますね。S, M, Lだけでいいのか、それとももっと細かくした方がいいのかとか……。
K-Meansは最も単純なクラスタリングアルゴリズムです。手順は以下のようです。
- クラスター中心の候補を決める：データ$x$と同次元にある、$K$個の中心点 (Centroid) $\mu_1, ..., \mu_K$を決める。
- 各データサンプル$x^{(i)}$のラベル$c^{(i)}$を決める：中心点$\mu_1, ... \mu_K$のうち最も距離が近いもののインデックス ($1,...,K$のどれか) に決める。
- 各中心点の座標を更新する：新しい中心点$\mu_k$の座標は、クラスター$k$と分類されたデータ$x$ ($c^{(i)} = x^{(i)}$)の平均をとする。
例として、$K = 3$のとき、アルゴリズムを繰り返し (Iterate)ていくときのクラスタリングの様子を以下に示します。
最初はとんちんかんな所にある中心点でも、K-Meansが繰り返されるごとに各中心点が別々のクラスターの中心へと移動していき、クラスタリングがより正確になされていくのがわかります。
k-Meansは、繰り返して行くごとにクラスタリングが続いていきますが、永遠に繰り返すわけにはいきません。「k-Meansのクラスタリングって、いつ止めていいの？」という疑問に対して、家宅捜索のように「よし、適当なところで切り上げるぞ！」と返してもいいのかもしれませんが、一応数学的な回答があります。機械学習で何度も登場する、目的関数 (Cost Function)です。
K-Means１回のリピートで、各データポイント$x^{(i)}$のラベル$c^{(i)}$は最も近い中心点のインデックス ($k = 1,...,K$のどれか)を取りますよね。このとき、最小値をとるべき目的関数は以下のようになります。
J(c^{(1)},...,c^{(m)},\mu_1,...,\mu_K) = \frac{1}{m} \sum^m_{i=1} ||x^{(i)} - \mu_{c^{(i)}}||^2
計算量は増えますが、とりあえずK-Meansを100回ほど繰り返してみて、この目的関数を最小にするクラスターを選ぶことが推奨されています。
注意点
- 当然ですが、クラスター数$K$はデータサンプル数$m$より小さくなくてはいけません。
- 中心点$\mu_1,...,\mu_K$の初期値は、元のデータ$x$からランダムに$K$個選びます。
PCA (Principal Component Analysis)
PCA (Principal Component Analysis)は主成分分析とも呼ばれ、クラスタリングのみならず、あらゆるデータサイエンス分野で大活躍する統計手法です。PCAを使うことでデータの次元減少 (Dimensionality Reduction)ができるため、データサイズの圧縮 (Compression)や、可視化 (Visualization)に威力を発揮するからです。容量が軽ければ計算も捗るし、3次元以下のデータだったらグラフを作ることができます。便利ですね。
PCAの原理は案外単純で、元データ$x$の次元が$n$でそれを$k$まで減らすとき、PCAは$n$次元空間で投射誤差 (Projection Error)を最小にするベクトルを$k$個見つけます。
PCAがデータを2次元から1次元に変換する様子を、線形回帰 (Linear Regression)と比較するとわかりやすいかもしれません。
- 線形回帰: 各データポイントと回帰直線のx,y方向の距離を最小にするようなベクトルを選ぶ。
- PCA: 各データポイントからあるベクトルに投射した距離を最小にするようなベクトルを選ぶ。
3次元から2次元に変換するときは、PCAは3次元空間上で、各データポイントからの投射誤差が最小となるような2つのベクトル$u^{(1)}, u^{(2)}$を見つけます。そうすることで、元データ$x$は、新たに軸$u^{(1)},u^{(2)}$を持つ平面上に表現できます。
n -> k の次元削減を行うPCAのアルゴリズムは、以下の手順をたどります。
1: データのスケーリング (例えばz-scoring)を行い、説明変数同士の範囲を揃える。
x = \frac{x - mean(x)}{std(x)}
2: 共分散行列 (Covariance Matrix) を計算する。
\sum = \frac{1}{m}\sum^n_{i=1}(x^{(i)})(x^{(i)})^{\mathrm{T}}
Matlab/Octaveでは、
sigma = (X'*X)/m;
で求められます。
3: 共分散行列の固有値 (eigenvector)を計算する。
[U,S,V] = svd(sigma);
Matlab/Octaveの、singular value deconvosition関数に先ほど計算した共分散行列を放り込むと求められます。
4: 新しい次元ベクトル$z$を固有ベクトル (eigenvector)から計算する。
Z = X*U(:,1:k);
次元を$k$まで減少させたいので、$n$ x $n$行列の$U$から最初の$k$個の固有ベクトルを取ってきます。この計算で、$x$ ($m$ x $n$次元) から$z$ ($m$ x $k$次元)に変換できます。
「よくわからないけど、これでデータの次元を減らすことができたぞ！……待てよ、もっと次元削減したらもっと仕事捗るかも！」
と思ってどんどんデータを軽くしていきたいところではありますが、次元減少のデメリットは、ベクトルの投射によって元データ$x$が持っていた情報の一部がなくなってしまうことです。
どれくらいの情報量が失われたのか定量したいとき、variance explainedというものを計算します。この計算には、まず$z$から元の次元にデータを戻したもの$x_{approx}$を求め、それが元データ$x$とどれくらい違っているか見ればいいですね。
元の次元に戻す (Reconstruction)ことで得られる$x_{approx}$は、以下のように計算します。
X_approx = Z*U(:,1:k)';
これにより、$z$ ($m$ x $k$次元)から$x_{approx}$ ($m$ x $n$次元)に復活させることができます。variance explainedは、以下のように計算します。
variance \hspace{3pt} explained = 1 - \frac{\sum^m_{i=1} ||x^{(i)} - x^{(i)}_{approx}||^2}{\sum^m_{i=1}||x^{(i)}||^2}
$x$と$x_{approx}$がどれくらいずれているか、二乗差を取って割合を計算しています。
実は、固有値計算のときに出てきた固有値行列$S$を使っても同じです。
variance \hspace{3pt} explained = \frac{\sum^k_{i=1}S_{i,i}}{\sum^n_{i=1}S_{i,i}}
$S$には固有値が降順になって行列の対角成分にしまわれているおり、対角以外の成分は0のため、例えば$k$次元まで次元削減したときのvariance explainedは、Matlab/Octaveで以下のように計算できます。
eigenvals = sum(S,1);
varianceExplained = sum(eigenvals(1:k))/sum(eigenvals);
このvariance explainedが、$0.99$を下回らない (99%の情報が保たれている)ように$k$を選択するのが望ましいとされています。
まとめのまとめ
- K-Meansはクラスタリングを行うアルゴリズムである。
- K-Meansは中心点 (Centroids)の周辺のデータをそのインデックスでラベリングし、ラベルごとに平均を計算して新しい中心点を求める、ということを繰り返すことで、中心点(Centroids)がクラスター中心に近づいていく。
- PCAは次元削減に役立ち、データ圧縮や可視化に使える。
- PCAは、$n$次元空間で、各データポイントからの投射誤射を最小化する$k$個のベクトルを見つける。
終わりに
今回はK-MeansとPCAについてでした。教師なし学習では最も単純なアルゴリズムであるK-Meansと、クラスタリング以外にも大活躍のPCAを学んだことで、機械学習、というよりデータサイエンスに対する理解がぐっと進んだような気がします。少なくともそんな気になれます。
次回は、異常値検知 (Anomaly Detection)と情報フィルタリング (Recommender System) を扱います。機械学習の実用に、ぐっと近づく内容です。