Coursera MachineLearning 8週目 まとめ

MachineLearning

機械学習界隈で評判高いCourseraのMachineLearningを受講したので、講義内容を個人的にまとめてみたいと思います。
8週目は、クラスタリング(clustering)とPCA(Principal Component Analysis)についてです。


 

クラスタリング(clustering)


これまでの教師あり学習では、あるデータ\(x^{(i)}\)のカテゴリーは\(y^{(i)}\)というように、既にラベル付けされたデータを扱ってきました。教師なし学習では、データ\(x^{(i)}\)のとき\(y^{(i)}\)になるというような紐付けがない trainig set を取り扱っていきます。

教師なし学習での training set(データ数\(m\))は\(x^{(1)}\), \(x^{(2)}\), \(x^{(3)}\), …, \(x^{(m)}\)のように与えられるので、アルゴリズム自身が training set の構造を見つけて分類していくことになります。
このようなただの点の集まりをいくつかのクラスター(集団)に分けていくアルゴリズムを、クラスタリング(clustering)と呼びます。
SNSでは、まだフォローしていないユーザーの中から「あなたの友達かも?」と選んで教えてくれる機能がよくありますが、あれもクラスタリングによるものです。

K – Means Algorithm

人気で広く使われているクラスタリングアルゴリズムです。
決まった手順を反復するアルゴリズムで、全体の流れは以下のようになります。

  1. クラスター重心の設定
    クラスター重心(Cluster Centroids)を、分けたいクラスターの数(\(K\))だけ設定します。
    (\(μ_{1}\),\(μ_{2}\)…\(μ_{K}\))

  2. クラスターの割付の段階
    各サンプルが、どのクラスター重心に近いかを見ていき、最も近い重心のクラスに割り振ります。
    \(x^{(i)}\)のラベル\(C^{(i)}\)を新しく設定し、最も近いクラスターのインデックス(\(1…K\))を代入します。(\(x^{(i)}\)とクラスター重心の距離(\(||x^{(i)} – μ_{k}|| ^{2}\))が最小になるようなインデックスを選択し、\(C^{(i)}\)に代入)

  3. クラスター重心の移動の段階
    クラスター重心を、それぞれに割り振られたサンプルの平均値へと移動させます。
    (それぞれのクラスター重心\(μ_{k}\)に、割り当てられたデータの算術平均値を代入)

  4. ②、③のループ
    クラスター重心が徐々に、正しいと思われるクラスターの中心へと移動していきます。


    それぞれのクラスター重心が最適と思われるポイントまで少しづつ移動しています。このアルゴリズムはゴールを定めなければ永遠に繰り返されそうですが、もちろんそれはよくありません。ここでも目的関数を設定し、それが最小になった場合をゴールとします。

K – Means Algorithmの目的関数(CostFunction)

K – Means Algorithmは、より良いクラスターを見つけるために、 2つの変数を交互に使用しながら目的関数を最小値へと近づけていきます。(ディストーション関数とも呼ばれる)
上記の②の工程では、K – Means Algorithmの目的関数が最小となるような\(C^{(i)}\)を選びます。
(このときクラスター重心\(μ_{k}\)は変化しない)
また、③の工程では、K – Means Algorithmの目的関数が最小となるような\(μ_{k}\)を選びます。
(このとき\(C^{(i)}\)は変化しない)
式として表すと以下のようになります。

(\(μ_{c^{(i)}}\)は、\(x^{(i)}\)が割り当てられたクラスター重心を示します)

各サンプルとそれぞれ割り当てられたクラスター重心との距離が最短になる場合を求めていきます。

クラスター重心をランダムに割り振るために、どう初期化すれば良い?

  1. \(K < m\)に設定する。
    分類するためのクラスター数が分類したいサンプル数より多くなるのは不自然なので、以上のように設定します。
  2. \(K\)個のTrainingExampleをランダムに選択する。
  3. ②でピックアップしたTrainingExampleと同じ座標に\(μ\)を割り振る。

局所的極小値(Local Minimum)を避けるためにはどうしたら良い?

クラスター重心をランダムで割り振ることができるようになりましたが、ここで一つ問題が発生します。もしランダムに設定したクラスター重心が偏った範囲にかたまってしまうと、求めたい最小値(Global Minimum)が得られなくなる。ということです。ランダムに設定するので、このような状況はどうしても起こり得ます。
対策としては、クラスター重心の初期化を複数回試みるという方法が挙げられます。K – Meansを一回だけ初期化して成功することを祈るよりかは、複数回試してみた方が良いですよね。
以下の手順で、局所的極小値(Local Minimum)を避け、最小値(Global Minimum)が得られているかどうかを確認します。

  1. K – Means Algorithmを走らせる回数を決める。
    \(i\)=100 など(50 – 1000がよく使われるようです)。決めた回数でforループを回す。
  2. K – Means Algorithmをランダムに初期化する。
    先ほどの①〜③の方法でおこないます。
  3. K – Means Algorithmを実行、\(C^{(1)}\)~\(C^{(m)}\) と \(μ^{(1)}\)~\(μ^{(K)}\) の値を得る。
  4. 目的関数を計算する。
    \(i\)=100とすると、100通りの答えが得られることになります。
  5. 目的関数が最も小さい値を示したクラスタリングのデータを最適解とする。

設定したクラスターの数Kが少なければ少ないほど位置が偏る可能性が高くなるので、クラスター数を少なく設定した場合には以上の工程を行うようにしましょう。もちろんKを大きく設定した場合でも効果はあります。

クラスターの数Kはどうやって決める?

残念ながら明確な答えはないそうです。
分類する目的にもよるので、得られた結果を見ながら調整する必要があるみたいです。

PCA(Principal Component Analysis)

特徴量が多数あるdata setを集めた際に、以下のような課題が挙げられたとします。

  • データ圧縮(Data Compression)を行いたい。
    (メモリやディスクの節約になりますし、学習アルゴリズムの計算速度の向上にも寄与します)
  • データの可視化(visualization)を行いたい。
    (3次元や2次元のデータであればグラフ化することで、より直感的にデータを理解することができます)

これらを行うためには、 次元削減(Dimensionality Reduction)を行う必要があります。
今回学習する主成分分析(Principal Component Analysis)は、次元削減のために用いられる最もポピュラーなアルゴリズムです。

PCAのアルゴリズムは、投射誤差(Projection Error)を最小化するような射影先の平面を探します。\(n\)次元のデータを\(k\)次元へと減らしたい。そういったときに投射誤差が最小になる\(k\)本(\(k\)方向)のベクトルを探します。
\(k\)は主成分の数のことで、保持する主成分の総数を示します。

例えば、3次元から2次元に変換したい場合は、投射誤差が最小になるような2つのベクトル\(z_{1}\) \(z_{2}\)を探し、2次元から1次元に変換したい場合は、投射誤差が最小になるような1つのベクトル\(z_{1}\)を探します。

(出典:Andrew Ng, Coursera Machine Learning Week 8)

2本のベクトルなので2次元、1本のベクトルなので1次元、とそれぞれ変換されていますね。

PCAと線形回帰は似ていますが、全く別物のアルゴリズムです。

  • 線形回帰:点(x,y)と仮説が予測した値との垂直な距離の内、最小の距離になるものを取得している。
  • PCA:各データからベクトルへと投射した長さのうち、最小の距離になるものを取得している。

PCAでは、この投射誤差が大きければ大きいほど、元データの情報が多く失われることになります。

データを投射する先のベクトルはどうやって見つけるのか?

実際にPCAのアルゴリズムが行うことを確認しましょう。次元削減を以下のような手順で行っていきます。

1. 平均標準化(mean normalization)を行う。
PCAを実装する前には必ず、データの前処理をしなければなりません。 ここでは平均標準化(mean normalization) を行います。

  1. training setに含まれるデータ数を\(m\)(\(x^{(1)}\), \(x^{(2)}\), \(x^{(3)}\), …, \(x^{(m)}\))、特徴量を(\(x_{1}\), \(x_{2}\), \(x_{3}\), …, \(x_{j}\))として、以下の式で平均値(mean)を計算します。
  2. 各特徴量\(x_{j}^{(i)}\)を、\(x_{j}-μ_{j}\)で置き換えます。
    ⇨ \(j\)個ある特徴量(\(x_{1}\), \(x_{2}\), \(x_{3}\), …, \(x_{j}\))それぞれを(\(x^{(1)}\), \(x^{(2)}\), \(x^{(3)}\), …, \(x^{(m)}\))の平均値を用いて更新します。(\(x_{1}\)であれば、\(x_{1}^{(1)}\),\(x_{1}^{(2)}\), …, \(x_{1}^{(m)}\)の平均値を用いて更新)
  3. スケーリング(feature scaling) (過去の章を参照)も必要に応じて行います。

2. 共分散行列(covariance matrix)を計算する。

Octave/Matlab
Sigma = (X'*X)/m;

記号は\(Σ\)を用います。(総和記号の\(Σ\)ではないので注意)
ここでは\(n×n\)行列の\(Σ\)が求まります。(特徴量が2個の場合は、\(2×2\)行列になります)

3. 行列Σの固有値ベクトルを計算する。
特異値分解(singular value decomposition)の関数で、先ほどの\(Σ\)の固有値ベクトルの計算を行います。

Octave/Matlab
[U,S,V] = svd(Sigma);

ここで、主成分を持つ\(U\)行列(\(n×n\))が得られます。(U will contain the principal components)

4. 特異値分解で得られた \(U\)行列 の、\(1\)〜\(k\)列までを取り出す。
次元を\(k\)まで減らしたい場合、以下のコードを実行して\(n×k\) 行列(U_reduce)を得ます。

Octave/Matlab
U_reduce = U(:,1:k)

5. 求めたい次元ベクトルzを、U_reduce を用いて計算する。

Octave/Matlab
z= U_reduce’ * X


これで、(\(m×n\))から(\(m×k\))へと次元を減らすことができました。
また、低次元にしたベクトルから元の次元のデータに戻したいときは、以下の計算を行い\(x_{approx}\)を求めます。

Octave/Matlab
Xapprox = U_reduce * z

approximatelyの意の\(approx\)を添字につけています。
元の次元に戻す、と言っても次元だけを戻しているだけなので元データと値は完璧には一致しません。
元データにどれだけ近似しているか?(元データとどれだけ違うのか?)を確認したいときに使用します。

kはどうやって決めるか?

次元削減を行えるようになりましたが、次元削減の目標値である\(k\)はどのようにして決めれば良いのでしょうか?
何かしら基準が必要なので、次元削減を行なった際に失われた情報量を定量化するために以下の計算を行います。

分子は、\(x^{(i)}\)と\(x_{approx}^{(i)}\)がどれだけ異なっているのかを表します。(数値が大きければ元データの情報も多く失われていることになるので、できる限り小さくしたい)
分母は、データの変動(total variation in the data)、原点を基点とした時にデータがどれだけばらついているかを示します。

この場合では0.01以下なので、99%の分散が保持されています(99% of variance is retained) 。 つまり、99%の分散が保持されるようにkを選びました、ということが言えます。元データの情報を多く含んでいるということですね。
その他でよく使われる数字としては、0.05(5%)、0.10(10%)などだそうです。

これでkを決める基準が得られたので、\(K\) = 1 から基準値(0.01)以下になるまで繰り返し計算していきましょう!…と言いたいところなのですが、U_reduce を計算して、\(z\)を求めて、\(x_{approx}\)を得るために元データに戻して…と毎回行わなければいけないのでかなり効率が悪そうです。

そこで効率的に行うために、特異値分解の関数を使用したときに得られるS行列を使用します。(先ほどはU行列のみ使用していました)S行列は、(\(n×n\))の正方行列で、対角成分から外れた全ての成分は0になっています。

この方法だと特異値分解(singular value decomposition)の関数を1回呼び出すだけで良いので。一回呼び出して、\(k\)=1から試していき、効率的に99%の分散が保持されるような最小の\(k\)を求めることができます。

《注意点》
PCAが行なっていることは、\(x\)からベクトル\(z\)へのマッピングを定義するということであり、このマッピングは training set のみに対して適用し定義するべき、とのこと(cross validation set や test set は使用しない)。training set のみで定義されたマッピングを、cross validation set や test set に適用していきます。
つまり、固有値ベクトルU_reduceのフィッティングは、training set だけに対して行うべきということです。

《PCAの誤用》
PCAの誤用として「オーバーフィッティングを防ぐために使用する」ということがあるそうです。

   オーバーフィッティングを防ぐには?(過去の章を参照)

  • 特徴量(feature)を減らす。
  • サンプル数\(m\)を増やす。
  • 正則化パラメーター\(λ\)を大きくする。      など

フィーチャー数\(n\)から\(k\)に減らせるので、オーバーフィッティング防止にも使えるのでは?という発想です。
しかしこれは誤用で、オーバーフィッティングに悩んでいるのであれば、最適な正則化パラメーター\(λ\)を探す方に注力した方が良いとのこと。

PCAのアルゴリズムでは、\(y\)ラベルを使用しません。\(x\)ラベルのみを使用して、低次元で射影誤差が最小になるようなベクトルを探していきます。つまり、(\(x^{(1)}\), \(y^{(1)}\)), (\(x^{(2)}\), \(y^{(2)}\)), … , (\(x^{(m)}\), \(y^{(m)}\)) という training set があったとしても、\(y\)ラベルの値を考慮せずに、\(x\)ラベルの値のみを抽出することになります。

99%の分散が保持されるように主成分の数\(k\)を選んだのだから、問題ないのでは?と言われるとそれも正しいのですが、可能性として貴重な情報を捨て去っているかもしれません。(正則化は、線形回帰やロジスティック回帰、ニューラルネットワークなどと共に用いられ、\(y\)ラベルの値を参考にしているので、重要な値を捨て去る可能性が低い)

PCAは、学習アルゴリズムのスピードアップ、メモリやディスクの節約、データを直感的に理解するための可視化(2次元や3次元に圧縮してグラフ化)などの使用用途で使用するべきで、オーバーフィッティングを防ぐためにわざわざPCAを適用するよりかは、正則化を使用した方が効率的かつ効果的ですよ、とのことです。


 

9週目は、異常検知(Anomaly Detection)とリコメンダーシステム(Recommender System)について学習していきます。

コメント

タイトルとURLをコピーしました