機械学習
この演習では、K-meansクラスタリング・アルゴリズムを実装し、それを適用して画像を圧縮します。 2番目のパートでは、主成分分析を使用して、顔の画像の低次元の表現を検索します。 プログラミング演習を始める前に、ビデオ講義を見て、関連トピックのレビュー質問を完了することを強くお勧めします。
演習を開始するには、スターター・コードをダウンロードし、演習を行うディレクトリーにその内容を解凍する必要があります。
必要に応じて、この演習を開始する前にOctave/MATLABのcdコマンドを使用して、このディレクトリーに移動してください。
また、コースウェブサイトの「環境設定手順」にOctave/MATLABをインストールするための手順も記載されています。
ex7.m- K-meansの最初の演習のためのOctave/MATLABスクリプトex7_pca.m- PCAでの2番目の演習のためのOctave/MATLABスクリプトex7data1.mat- PCAのサンプル・データセットex7data2.mat- K-meansのサンプル・データセットex7faces.mat- 顔データセットbird_small.png- サンプル画像displayData.m- 行列に格納された2Dデータを表示するdrawLine.m- 元の図形に線を描画するplotDataPoints.m- K-means重心を初期化するplotProgresskMeans.m- 進行中のK-meansの各ステップをプロットするrunkMeans.m- K-meansアルゴリズムを実行するsubmit.m- 解答をサーバーに送信するスクリプト- [*]
pca.m- 主成分分析を実行する - [*]
projectData.m- データセットをより低い次元の空間に射影する - [*]
recoverData.m- 元のデータを射影から復元する - [*]
findClosestCentroids.m- 最も近い重心を見つける（K-meansで使用） - [*]
computeCentroids.m- 重心の平均の計算する（K-meansで使用） - [*]
kMeansInitCentroids.m- K-meansの重心を初期化する
* はあなたが完了する必要があるものを示しています。
演習では、スクリプトex7.mを使用します。
演習の最初のパートではスクリプトex7.mを使用し、2番目のパートではex7_pca.mを使用します。
これらのスクリプトは、問題に対するデータセットをセットアップし、あなたが実装する関数を呼び出します。
こららのスクリプトを変更する必要はありません。
この課題の指示に従って、他のファイルの関数を変更することだけが求められています。
このコースの演習では、数値計算に適した高度なプログラミング言語であるOctave（※1）またはMATLABを使用します。 OctaveまたはMATLABがインストールされていない場合は、コースWebサイトのEnvironment Setup Instructionsのインストール手順を参照してください。
Octave/MATLABコマンドラインでは、helpの後に関数名を入力すると、組み込み関数のドキュメントが表示されます。
たとえば、help plotはプロットのヘルプ情報を表示します。
Octave関数の詳細なドキュメントは、Octaveのドキュメントページにあります。
MATLABのドキュメントは、MATLABのドキュメントページにあります。
また、オンライン・ディスカッションを使用して、他の学生との演習について話し合うことを強く推奨します。 しかし、他人が書いたソースコードを見たり、他の人とソースコードを共有したりしないでください。
※1：Octaveは、MATLABの無料の代替ソフトウェアです。 プログラミング演習は、OctaveとMATLABのどちらでも使用できます。
この演習では、K-meansアルゴリズムを実装し、画像圧縮に使用します。
最初に、K-meansアルゴリズムの仕組みを直感的に理解するために、2Dデータセットのサンプルを表示することから始めます。
その後、画像に現れる色の数をその画像で最も一般的な色の数に減らすため、画像圧縮にK-meansアルゴリズムを使用します。
演習のこのパートでは、ex7.mを使用します。
K-meansアルゴリズムは、類似のデータのサンプルを自動的にクラスタリングする手順です。
具体的には、与えられたトレーニング・セット （ここで、
）に対して、データをいくつかのまとまった「クラスター」にグループ化したいということです。
K-meansの背景にある直感は、最初の重心を推測することから始まり、次に最も近い重心にサンプルを繰り返し割り当て、それに基づいて重心を再計算することによって、この推測を洗練する反復手順であると言えます。
K-meansアルゴリズムは以下の通りです。
% 重心を初期化する
centroids = kMeansInitCentroids(X, K);
for iter = 1:iterations
% クラスタ割り当てステップ:
% 各データ点を最も近い重心に割り当てます。idx(i)は、
% c^(i)（サンプルiに割り当てられた重心のインデックス）に対応します。
idx = findClosestCentroids(X, centroids);
% 重心移動ステップ：
% 重心の割り当てに基づいて平均を計算します。
centroids = computeMeans(X, idx, K);
end
アルゴリズムの内部ループは、次の2つのステップを繰り返し実行します。
- (i) 各トレーニング・サンプル
をその最も近い重心に割り当てる
- (ii) 割り当てられたポイントを使用して各重心の平均を再計算する
K-meansアルゴリズムは、いくつかの重心の平均の最終的な集合に常に収束します。 収束した解は必ずしも理想的ではなく、重心の初期設定に依存することに注意してください。 したがって、実際にK-meansアルゴリズムは、通常、異なるランダム初期化を用いて数回実行されます。 異なるランダム初期化からこれらの異なる解を選択する方法の1つは、コスト関数値（歪み）が最も低いものを選択することです。 次のセクションでは、K-meansアルゴリズムの2つのフェーズを個別に実装します。
K-meansアルゴリズムの「クラスター割り当て」の段階では、アルゴリズムは、現在の重心の位置を考慮して、すべてのトレーニング・サンプルをその最も近い重心に割り当てます。
具体的には、設定したすべてのサンプル
に対して、以下をセットします。
ここで、は
に最も近い重心のインデックスであり、
は
番目の重心の位置（値）です。
は、スターター・コードの
idx(i)に対応することに注意してください。
あなたがすべきことは、findClosestCentroids.mでコードを完成させることです。
この関数は、データ行列Xと重心の中のすべての重心の位置を取り、最も近い重心のインデックスを各トレーニング・サンプルに保持する1次元配列idx（の値、ここで
は重心の総数です）を出力する必要があります。
すべてのトレーニング・サンプルと各重心のループを使用して、これを実装できます。
findClosestCentroids.mでコードを完成し、スクリプトex7.mがコードを実行すると、最初の3つのサンプルの重心の割り当てに対応する出力[1 3 2]が表示されます。
ここで解答を提出する必要があります。
与えられたすべての点の重心の割り当てについて、アルゴリズムの第2段階は、各重心に対して、それに割り当てられた点の平均を再計算します。
具体的には、すべての重心に対して、
ここでは重心
に割り当てられたサンプルの集合です。
具体的には、
と
が重心
に割り当てられているとする2つのサンプルがある場合、
を更新する必要があります。
これでcomputeCentroids.mのコードを完成させられるはずです。
この関数は、重心のループを使用して実装できます。
サンプルにループを使用することもできます。
そのようなループを使用しないベクトル化された実装を使用することができれば、コードはより速く実行される可能性があります。
computeCentroids.mでコードを完成すると、ex7.mスクリプトはコードを実行し、K-meansの最初のステップの後に重心を出力します。
ここで解答を提出する必要があります。
図1: 期待される出力
2つの関数（findClosestCentroidsとcomputeCentroids）を完了すると、ex7.mの次のステップでK-meansアルゴリズムがトイ2Dデータセットで実行され、K-meansの仕組みを理解できます。
関数は、runkMeans.mスクリプトの中から呼び出されます。
どのように機能するかを理解するために関数を見てみることをお勧めします。
このコードは、ループで実装した2つの関数を呼び出しています。
次のステップを実行すると、K-meansコードは、各繰り返しでアルゴリズムの進捗状況を可視化します。
Enterキーを何度か押して、K-meansアルゴリズムの各ステップが重心とクラスター割り当てをどのように変更するかを確認してください。
最後に、図は図1のように表示されます。
ex7.mのサンプル・データセットの重心の最初の割り当ては、図1と同じ図が表示されるように設計されています。
実際には、重心を初期化するための良い方法は、トレーニング・セットからランダムなサンプルを選択することです。
この演習では、次のコードを使用してkMeansInitCentroids.m関数を完成させる必要があります。
% ランダムに選択したサンプルで重心を初期化する
% サンプルのインデックスをランダムに並べ替える
randidx = randperm(size(X, 1));
% 最初のK個のサンプルを選択し、重心とする
centroids = X(randidx(1:K), :);
上記のコードは、最初に（randpermを使用して）サンプルのインデックスをランダムに置き換えます。
次に、インデックスをランダム置換した結果から最初の個のサンプルを選択します。
これにより、同じサンプルを2回選択するリスクを伴わずに、サンプルをランダムに選択することができます。
図2: オリジナルの128x128イメージ
この演習では、画像圧縮にK-meansを適用します。 画像（※2）の簡単な24ビットカラー表現では、各ピクセルは、赤、緑、青の輝度値を指定する3つの8ビット符号なし整数（0～255の範囲）で表現されます。 このエンコーディングは、RGBエンコーディングと呼ばれます。 画像には何千もの色が含まれていますが、この演習では色の数を16色に減らします。
この削減を行うことで、写真を効率的に表現（圧縮）することができます。 具体的には、選択した16色のRGB値を保存するだけで済みます。 画像の各ピクセルについて、その位置に色のインデックスを格納する必要があります（16の可能性を表すのであれば、4ビットしか必要ありません）。
この演習では、K-meansアルゴリズムを使用して、圧縮画像を表すために使用される16色を選択します。 具体的には、原画像のすべてのピクセルをデータサンプルとして扱い、K-meansアルゴリズムを使用して、3次元RGB空間内のピクセルを最適にグループ化（クラスタリング）する16色を検索します。 画像のクラスター重心を計算したら、16色を使用して元の画像のピクセルを置き換えます。
※2: この演習で使用している写真は、Frank Wouters氏のものであり、彼の許可を得て使用しています。
Octave/MATLABでは、次のように画像をロードすることができます。
% 128x128カラー画像（bird_small.png）をロードする
A = imread('bird small.png');
% imreadを使用するには、画像パッケージをインストールする必要があります。
% 画像パッケージをインストールしていない場合は、代わりに次の行を変更する
% 必要があります。
%
% load('bird small.mat'); % 画像を変数Aにロードする
これにより、三次元行列Aの最初の2つのインデックスがピクセルの位置を識別し、最後のインデックスが赤、緑、青のいずれかを表します。
たとえば、A(50, 33, 3)は50行33列のピクセルの青の輝度を示します。
ex7.m内のコードは、最初に画像をロードし、次にそれを再整形してのピクセルのカラー行列（
）を作成し、K-means関数を呼び出します。
画像を表すために上位色を見つけた後、
findClosestCentroids関数を使用して、各ピクセルの位置を最も近い重心に割り当てることができます。
これにより、各ピクセルの重心の割り当てを使用して、元の画像を表現することができます。
画像を記述するために必要なビット数が、大幅に削減されていることに注目してください。
元の画像は、ピクセル位置のそれぞれに対して、24ビットを必要とし、合計サイズは
ビットとなります。
新しい表現は、24ビットを必要とする16色の辞書の形式でオーバーヘッド記憶装置を必要としますが、画像そのものはピクセル位置当たり4ビットしか必要としません。
したがって、使用される最終ビット数は、
ビットであり、原画像を約6倍に圧縮することになります。
図3： 元の画像と再構築の画像（K-meansを使用して画像を圧縮する場合）
最後に、重心の割り当てのみに基づいて画像を再構築することで、圧縮の効果を表示できます。 具体的には、各ピクセルの位置を、それに割り当てられた重心の平均で置き換えることができます。 図3に、得られた再構築の画像を示します。 結果として得られる画像にはオリジナルの特性のほとんどが残っていますが、いくつかの圧縮のアーティファクト（画像の乱れ）もあります。
このオプションの（非評価）演習は、解答を提出する必要はありません。
この演習では、あなたが持っている画像の1つで実行するために提供したコードを変更します。
画像が非常に大きい場合、K-meansは実行に時間がかかることに注意してください。
したがって、コードを実行する前にイメージを管理可能なサイズにリサイズすることをお勧めします。
圧縮に及ぼす影響を見るためにを変化させることもできます。
この演習では、主成分分析（PCA）を使用して次元削減を行います。
最初に、2Dデータセットのサンプルを試して、PCAの仕組みを直感的に理解し、それを5000個の顔画像のより大きなデータセットに使用します。
提供されたスクリプト、ex7_pca.mは、演習の後半を実行するのに役立ちます。
PCAの仕組みの理解に役立つように、まずは大きな変化の方向と小さな変化の方向を有する2つのデータセットから始めます。
スクリプトex7_pca.mはトレーニング・データをプロットします（図4）。
演習のこのパートでは、PCAを使用して2Dから1Dにデータを削減するときに起こることを可視化します。
実際には、データを256次元から50次元に削減したいと考えるかもしれません。
このサンプルでは、低次元のデータを使用することで、アルゴリズムをよりよく可視化することができます。
図4： サンプル・データセット1
演習のこのパートでは、PCAを実装します。
PCAは2つの計算ステップで構成されています。
まず、データの共分散行列を計算します。
次に、Octave/MATLABのSVD関数を使用して、固有ベクトルを計算します。
これらは、データの変化の主成分に対応します。
PCAを使用する前に、まず各フィーチャーの平均値をデータセットから差し引いてデータを正規化し、各次元が同じ範囲になるように各次元をスケーリングすることが重要です。
提供したスクリプトex7_pca.mでは、featureNormalize関数を使用してこの正規化が実行されています。
データを正規化したら、PCAを実行して主成分を計算することができます。
あなたがすべきことは、pca.mのコードを完成させて、データセットの主成分を計算することです。
まず、データの共分散行列を以下により、計算する必要があります。
ここで、は行にサンプルを持つデータ行列で、
は列の数です。
は
の行列であり、総和の演算子ではないことに注意してください。
共分散行列を計算した後、SVDを実行して主成分を計算することができます。
Octave/MATLABでは、次のコマンドでSVDを実行することができます。
[U, S, V] = svd(Sigma)。ここで、Uは主成分を含み、Sは対角行列を含みます。
図5： 計算されたデータセットの固有ベクトル
pca.mが完成すると、ex7_pca.mスクリプトはサンプル・データセットでPCAを実行し、見つかった対応する主成分をプロットします（図5）。
スクリプトはまた、見つかった中で最も高い主成分（固有ベクトル）を出力し、期待する出力は約[-0.707 -0.707]になります
（と
が最初の主成分に対して等しく有効な選択肢なので、Octave/MATLABは代わりにこの負数を出力する可能性があります）。
ここで解答を提出する必要があります。
主成分を計算した後、各サンプルをより低い次元の空間（たとえば、2Dから1Dに）に射影することにより、データセットのフィーチャーの次元を削減できます。
この演習では、PCAから返された固有ベクトルを使用して、サンプルのデータセットを1次元空間に射影します。
実際には、線形回帰やニューラル・ネットワークなどの学習アルゴリズムを使用していた場合、元のデータの代わりに射影データを使用できるようになります。 射影されたデータを使用することで、入力の次元が少なくなるため、モデルをより早くトレーニングすることができます。
これでprojectData.mのコードを完成させられるはずです。
具体的には、データセットX、主成分U、および削減したい次元数Kが与えられます。
Xの各サンプルをUの上位K個の成分に射影する必要があります。
Uの上位K個の成分は、Uの最初のK個の列、すなわちU_reduce = U(:, 1:K)によって与えられることに注意してください。
projectData.mのコードを完成すると、ex7_pca.mは最初の次元に最初のサンプルを射影し、約1.481の値を表示します（の代わりに
を指定した場合は
-1.481）。
ここで解答を提出する必要があります。
下位次元空間にデータを射影した後、元の高次元空間に射影してデータを近似的に復元することができます。
あなたがすべきことは、recoverData.mを完了して、Zの各サンプルを元の空間に射影し、復元した近似をX_recに返すことです。
recoverData.mでコードを完成すると、ex7_pca.mは最初のサンプルの近似値を復元し、約[-1.047 -1.047]の値が表示されます。
ここで解答を提出する必要があります。
図6：PCA後に正規化と射影を行ったデータ
projectDataとrecoverDataの両方を完成すると、ex7_pca.mは射影と近似の再構築の両方を実行し、射影がどのようにデータに影響するかを示します。
図6では、元のデータ点は青色の円で示され、射影されたデータ点は赤色の円で示されます。
射影は事実上、によって与えられた方向の情報のみを保持します。
演習のこのパートでは、顔画像でPCAを実行して、実際に次元削減のためにそれをどのように使用できるかを確認します。
データセットex7faces.matには、32×32のグレースケールの顔画像のデータセットX（※3）が含まれています。
Xの各行は、1つの顔画像（長さ1024の行ベクトル）に対応します。
ex7_pca.mの次のステップは、これらの顔画像の最初の100個をロードして可視化します（図7）。
※3：このデータセットは、「Labeled Faces in the Wild」のデータセットのcropped versionをベースにしています。
図7：顔のデータセット
顔のデータセットでPCAを実行するには、最初にデータ行列Xから各フィーチャーの平均を引いてデータセットを正規化します。
スクリプトex7_pca.mがこれを行い、PCAコードを実行します。
PCAを実行すると、データセットの主成分が取得されます。
Uの各主成分（各行）は、長さのベクトルです（顔のデータセットの場合、
）。
これらの主成分を、元のデータセットのピクセルに対応する32×32の行列に再構築することによって、これらの主成分を可視化することができます。
スクリプト
ex7_pca.mは、最大の変動を描写する最初の36個の主成分を表示します（図8）。
必要に応じて、コードを変更してより多くの主成分を表示し、より詳細なキャプチャーの方法を確認することもできます。
これで、顔のデータセットの主成分を計算したので、これを使用して顔データセットの次元を減らすことができます。 これにより、元の1024次元ではなく、より小さな入力サイズ（たとえば100次元）で学習アルゴリズムを使用することができます。 これは学習アルゴリズムのスピードアップに役立ちます。
図8：顔のデータセットの主成分
図9：顔の元画像と上位100個の主成分のみから再構築された画像
ex7_pca.mの次のパートは、顔のデータセットを最初の100の主成分に射影します。
具体的には、各顔画像をベクトルで記述します。
次元削減で失われたデータを理解するために、射影されたデータセットのみを使用してデータを復元できます。
ex7_pca.mにより、データのおおよその復元が実行され、元の画像と射影された顔画像が並べて表示されます（図9）。
再構築から、細部が失われている一方、顔の一般的な構造と外観が維持されていることが分かります。
これは、学習アルゴリズムを大幅にスピードアップするのに役立つ、データセットサイズの大幅な（10倍以上の）削減です。
たとえば、人の認識（顔の画像を与えて、人物の識別を予測する）を行うためにニューラル・ネットワークをトレーニングしていた場合、元のピクセルの代わりに100次元のピクセルの削減された入力を使用できます。
図10：3Dのオリジナルデータ
以前のK-means画像圧縮の演習では、3次元RGB空間でK-meansアルゴリズムを使用しました。
ex7_pca.mスクリプトの最後のパートでは、scatter3関数を使用して、この3D空間内の最終的なピクセル割り当てを可視化するためのコードを提供しました。
各データ点は、割り当てられたクラスターに従って色付けられます。
図の上でマウスをドラッグすると、このデータを3次元で回転して調べることができます。
3次元以上のデータセットを可視化することは面倒であることが分かっています。
したがって、いくつかの情報を失うことを犠牲にしても、2Dでデータを表示することが望ましいことがよくあります。
実際に、PCAは可視化の目的でデータの次元を減らすためによく使用されます。
ex7_pca.mの次のパートで、スクリプトはPCAの実装を3次元データに適用して2次元に削減し、2D散布図で結果を可視化します。
PCAの射影は、データの広がりを最大化するビューを選択する回転と考えることができます。
これはしばしば「ベスト」な見方に相当します。
図11：PCAを使用して生成された2Dの可視化
この課題が完了したら、送信機能を使用して解答を我々のサーバーに送信してください。 以下は、この演習の各パートの得点の内訳です。
| パート | 提出するファイル | 点数 |
|---|---|---|
| 最も近い重心の検出 | findClosestCentroids.m |
30 点 |
| 重心の平均の計算 | computeCentroids.m |
30 点 |
| PCA | pca.m |
20 点 |
| データのプロジェクト | projectData.m |
10 点 |
| データのリカバリー | recoverData.m |
10 点 |
| 合計点 | 100 点 |
解答を複数回提出することは許可されており、最高のスコアのみを考慮に入れます。