機械学習

機械学習プログラミングの割り当て（exe7）の概要



Machine Learning Programming Assignment Summary



演習7-K-meansとPCA

ここからダウンロード Coursera-WuEnda-機械学習-すべてのプログラミング実践の回答

この演習では、K-meansクラスタリングアルゴリズムを実装し、それを圧縮画像に適用します。第2部では、主成分分析を使用して、顔画像の低次元表現を見つけます。



1K-means

2次元の点から始めて、分類にK-meansを使用します。 A
画像
K-meansのステップは上記のとおりです。各ループで、最初にすべてのポイントを分類してから、各クラスの中心座標を更新します。

例はex7.mにあり、Kは手動で初期化されています。



%% Machine Learning Online Class % Exercise 7 | Principle Component Analysis and K-Means Clustering % % Instructions % ------------ % % This file contains code that helps you get started on the % exercise. You will need to complete the following functions: % % pca.m % projectData.m % recoverData.m % computeCentroids.m % findClosestCentroids.m % kMeansInitCentroids.m % % For this exercise, you will not need to change any code in this file, % or any other files other than those mentioned above. % %% Initialization clear close all clc %% ================= Part 1: Find Closest Centroids ==================== % To help you implement K-Means, we have divided the learning algorithm % into two functions -- findClosestCentroids and computeCentroids. In this % part, you should complete the code in the findClosestCentroids function. % fprintf('Finding closest centroids. ') % Load an example dataset that we will be using load('ex7data2.mat') % Select an initial set of centroids K = 3 % 3 Centroids initial_centroids = [3 3 6 2 8 5] % Find the closest centroids for the examples using the % initial_centroids idx = findClosestCentroids(X, initial_centroids) fprintf('Closest centroids for the first 3 examples: ') fprintf(' %d', idx(1:3)) fprintf(' (the closest centroids should be 1, 3, 2 respectively) ') fprintf('Program paused. Press enter to continue. ') pause function idx = findClosestCentroids(X, centroids) %FINDCLOSESTCENTROIDS computes the centroid memberships for every example % idx = FINDCLOSESTCENTROIDS (X, centroids) returns the closest centroids % in idx for a dataset X where each row is a single example. idx = m x 1 % vector of centroid assignments (i.e. each entry in range [1..K]) % % Set K K = size(centroids, 1) % You need to return the following variables correctly. idx = zeros(size(X,1), 1) % ====================== YOUR CODE HERE ====================== % Instructions: Go over every example, find its closest centroid, and store % the index inside idx at the appropriate location. % Concretely, idx(i) should contain the index of the centroid % closest to example i. Hence, it should be a value in the % range 1..K % % Note: You can use a for-loop over the examples to compute this. % for i=1:size(X,1) adj=sqrt((X(i,:)-centroids(1,:))*(X(i,:)-centroids(1,:))') idx(i)=1 for j=2:K temp=sqrt((X(i,:)-centroids(j,:))*(X(i,:)-centroids(j,:))') if(temp %% ===================== Part 2: Compute Means ========================= % After implementing the closest centroids function, you should now % complete the computeCentroids function. % fprintf(' Computing centroids means. ') % Compute means based on the closest centroids found in the previous part. centroids = computeCentroids(X, idx, K) fprintf('Centroids computed after initial finding of closest centroids: ') fprintf(' %f %f ' , centroids') fprintf(' (the centroids should be ') fprintf(' [ 2.428301 3.157924 ] ') fprintf(' [ 5.813503 2.633656 ] ') fprintf(' [ 7.119387 3.616684 ] ') fprintf('Program paused. Press enter to continue. ') pause function centroids = computeCentroids(X, idx, K) %COMPUTECENTROIDS returns the new centroids by computing the means of the %data points assigned to each centroid. % centroids = COMPUTECENTROIDS(X, idx, K) returns the new centroids by % computing the means of the data points assigned to each centroid. It is % given a dataset X where each row is a single data point, a vector % idx of centroid assignments (i.e. each entry in range [1..K]) for each % example, and K, the number of centroids. You should return a matrix % centroids, where each row of centroids is the mean of the data points % assigned to it. % % Useful variables [m n] = size(X) % You need to return the following variables correctly. centroids = zeros(K, n) % ====================== YOUR CODE HERE ====================== % Instructions: Go over every centroid and compute mean of all points that % belong to it. Concretely, the row vector centroids(i, :) % should contain the mean of the data points assigned to % centroid i. % % Note: You can use a for-loop over the centroids to compute this. % for i=1:K if(size(find(idx==i),2)~=0) centroids(i,:)=mean(X(find(idx==i),:)) else centroids(i,:)=zeros(1,n) end end % ============================================================= end %% =================== Part 3: K-Means Clustering ====================== % After you have completed the two functions computeCentroids and % findClosestCentroids, you have all the necessary pieces to run the % kMeans algorithm. In this part, you will run the K-Means algorithm on % the example dataset we have provided. % fprintf(' Running K-Means clustering on example dataset. ') % Load an example dataset load('ex7data2.mat') % Settings for running K-Means K = 3 max_iters = 10 % For consistency, here we set centroids to specific values % but in practice you want to generate them automatically, such as by % settings them to be random examples (as can be seen in % kMeansInitCentroids). initial_centroids = [3 3 6 2 8 5] % Run K-Means algorithm. The 'true' at the end tells our function to plot % the progress of K-Means [centroids, idx] = runkMeans(X, initial_centroids, max_iters, true) fprintf(' K-Means Done. ') fprintf('Program paused. Press enter to continue. ') pause

ポイントを10回の反復で3つのカテゴリに分割します。 3つのカテゴリの中心点は、（3、3）、（6、2）、（8、5）に初期化されます。
次の画像を取得します。 （真ん中の画像は省略され、最初と最後の画像のみが表示されます）
これは最初の画像です：

10回の反復後の画像：画像
ポイントの3つの山が3つのカテゴリにうまく分類されていることがわかります。写真は中心点の移動軌跡も示しています。 A

%% ============= Part 4: K-Means Clustering on Pixels =============== % In this exercise, you will use K-Means to compress an image. To do this, % you will first run K-Means on the colors of the pixels in the image and % then you will map each pixel onto its closest centroid. % % You should now complete the code in kMeansInitCentroids.m % fprintf(' Running K-Means clustering on pixels from an image. ') % Load an image of a bird A = double(imread('bird_small.png')) % If imread does not work for you, you can try instead % load ('bird_small.mat') A = A / 255 % Divide by 255 so that all values are in the range 0 - 1 % Size of the image img_size = size(A) % Reshape the image into an Nx3 matrix where N = number of pixels. % Each row will contain the Red, Green and Blue pixel values % This gives us our dataset matrix X that we will use K-Means on. X = reshape(A, img_size(1) * img_size(2), 3) % Run your K-Means algorithm on this data % You should try different values of K and max_iters here K = 16 max_iters = 10 % When using K-Means, it is important the initialize the centroids % randomly. % You should complete the code in kMeansInitCentroids.m before proceeding initial_centroids = kMeansInitCentroids(X, K) % Run K-Means [centroids, idx] = runkMeans(X, initial_centroids, max_iters) fprintf('Program paused. Press enter to continue. ') pause function centroids = kMeansInitCentroids(X, K) %KMEANSINITCENTROIDS This function initializes K centroids that are to be %used in K-Means on the dataset X % centroids = KMEANSINITCENTROIDS(X, K) returns K initial centroids to be % used with the K-Means on the dataset X % % You should return this values correctly centroids = zeros(K, size(X, 2)) % ====================== YOUR CODE HERE ====================== % Instructions: You should set centroids to randomly chosen examples from % the dataset X % Reorder the index of the data set randomly randidx = randperm(size(X, 1)) % Take the first K examples as the data center centroids = X(randidx(1:K), :) % ============================================================= end %% ================= Part 5: Image Compression ====================== % In this part of the exercise, you will use the clusters of K-Means to % compress an image. To do this, we first find the closest clusters for % each example. After that, we fprintf(' Applying K-Means to compress an image. ') % Find closest cluster members idx = findClosestCentroids(X, centroids) % Essentially, now we have represented the image X as in terms of the % indices in idx. % We can now recover the image from the indices (idx) by mapping each pixel % (specified by its index in idx) to the centroid value X_recovered = centroids(idx,:) % Reshape the recovered image into proper dimensions X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3) % Display the original image subplot(1, 2, 1) imagesc(A) title('Original') % Display compressed image side by side subplot(1, 2, 2) imagesc(X_recovered) title(sprintf('Compressed, with %d colors.', K)) fprintf('Program paused. Press enter to continue. ') pause

画像圧縮にはK-meansを使用します。 A
例として128 times 128の画像を取り上げると、RGBを使用すると、合計128 times 128 times 24 = 393216ビットが必要になります。 A
ここでは、彼を圧縮し、すべての色を16のカテゴリに分割し、カテゴリ全体の色を重心に対応する色に置き換えます。これにより、スペースを16 times 24 + 128 x 128 times 4 = 65920ビットに圧縮できます。 A
タイトルで提供されている例を使用すると、効果はおおよそ次のようになります。

2 PCA

この演習では、主成分分析（PCA）を使用して次元削減を実行します。最初にサンプルの2Dデータセットを使用して、PCAがどのように機能するかを直感的に理解し、次にそれを5000の顔画像データセットのより大きなデータセットに使用します。

提供されているスクリプトex7pca.mは、演習の前半を段階的に完了するのに役立ちます。

まず、例の2次元ベクトルを1次元に縮小します。

%% Initialization clear close all clc %% ================== Part 1: Load Example Dataset =================== % We start this exercise by using a small dataset that is easily to % visualize % fprintf('Visualizing example dataset for PCA. ') % The following command loads the dataset. You should now have the % variable X in your environment load ('ex7data1.mat') % Visualize the example dataset plot(X(:, 1), X(:, 2), 'bo') axis([0.5 6.5 2 8]) axis square fprintf('Program paused. Press enter to continue. ') pause %% =============== Part 2: Principal Component Analysis =============== % You should now implement PCA, a dimension reduction technique. You % should complete the code in pca.m % fprintf(' Running PCA on example dataset. ') % Before running PCA, it is important to first normalize X [X_norm, mu, sigma] = featureNormalize(X) % Run PCA [U, S] = pca(X_norm) % Compute mu, the mean of the each feature % Draw feature vectors centered on the data. These lines show the direction of the largest change in the data set. % Draw the eigenvectors centered at mean of data. These lines show the % directions of maximum variations in the dataset. hold on drawLine(mu, mu + 1.5 * S(1,1) * U(:,1)', '-k', 'LineWidth', 2) drawLine(mu, mu + 1.5 * S(2,2) * U(:,2)', '-k', 'LineWidth', 2) hold off fprintf('Top eigenvector: ') fprintf(' U(:,1) = %f %f ', U(1,1), U(2,1)) fprintf(' (you should expect to see -0.707107 -0.707107) ') fprintf('Program paused. Press enter to continue. ') pause function [U, S] = pca(X) %PCA Run principal component analysis on the dataset X % [U, S, X] = pca(X) computes eigenvectors of the covariance matrix of X % Returns the eigenvectors U, the eigenvalues (on diagonal) in S % % Useful values [m, n] = size(X) % You need to return the following variables correctly. U = zeros(n) S = zeros(n) % ====================== YOUR CODE HERE ====================== % Instructions: You should first compute the covariance matrix. Then, you % should use the 'svd' function to compute the eigenvectors % and eigenvalues of the covariance matrix. % % Note: When computing the covariance matrix, remember to divide by m (the % number of examples). [U,S,V] = svd(1/m*X'*X) % ========================================================================= end

%% =================== Part 3: Dimension Reduction =================== % You should now implement the projection step to map the data onto the % first k eigenvectors. The code will then plot the data in this reduced % dimensional space. This will show you what the data looks like when % using only the corresponding eigenvectors to reconstruct it. % % You should complete the code in projectData.m % fprintf(' Dimension reduction on example dataset. ') % Plot the normalized dataset (returned from pca) plot(X_norm(:, 1), X_norm(:, 2), 'bo') axis([-4 3 -4 3]) axis square % Project the data onto K = 1 dimension K = 1 Z = projectData(X_norm, U, K) fprintf('Projection of the first example: %f ', Z(1)) fprintf(' (this value should be about 1.481274) ') X_rec = recoverData(Z, U, K) fprintf('Approximation of the first example: %f %f ', X_rec(1, 1), X_rec(1, 2)) fprintf(' (this value should be about -1.047419 -1.047419) ') % Draw lines connecting the projected points to the original points hold on plot(X_rec(:, 1), X_rec(:, 2), 'ro') for i = 1:size(X_norm, 1) drawLine(X_norm(i,:), X_rec(i,:), '--k', 'LineWidth', 1) end hold off fprintf('Program paused. Press enter to continue. ') pause function Z = projectData(X, U, K) %PROJECTDATA Computes the reduced data representation when projecting only %on to the top k eigenvectors % Z = projectData(X, U, K) computes the projection of % the normalized inputs X into the reduced dimensional space spanned by % the first K columns of U. It returns the projected examples in Z. % % You need to return the following variables correctly. Z = zeros(size(X, 1), K) % ====================== YOUR CODE HERE ====================== % Instructions: Compute the projection of the data using only the top K % eigenvectors in U (first K columns). % For the i-th example X(i,:), the projection on to the k-th % eigenvector is given as follows: % x = X(i, :)' % projection_k = x' * U(:, k) % Ureduce = U(:,1:K) Z = X * Ureduce % ============================================================= end function X_rec = recoverData(Z, U, K) %RECOVERDATA Recovers an approximation of the original data when using the %projected data % X_rec = RECOVERDATA(Z, U, K) recovers an approximation the % original data that has been reduced to K dimensions. It returns the % approximate reconstruction in X_rec. % % You need to return the following variables correctly. X_rec = zeros(size(Z, 1), size(U, 1)) % ====================== YOUR CODE HERE ====================== % Instructions: Compute the approximation of the data by projecting back % onto the original space using the top K eigenvectors in U. % % For the i-th example Z(i,:), the (approximate) % recovered data for dimension j is given as follows: % v = Z(i, :)' % recovered_j = v' * U(j, 1:K)' % % Notice that U(j, 1:K) is a row vector. % Ureduce = U(:, 1:K) X_rec = Z * Ureduce' % ============================================================= end

上の画像から、復元された画像は特徴ベクトルの1つに関する情報のみを保持し、垂直方向の情報が失われていることがわかります。

顔画像データセット

顔画像の次元削減を行います。 Ex7faces.matには、顔のグレースケール画像が多数含まれているため（32 times 32）、各ベクトルの次元は32 times 32 = 1024です。A
以下は最初の100枚の顔画像です。

%% =============== Part 4: Loading and Visualizing Face Data ============= % We start the exercise by first loading and visualizing the dataset. % The following code will load the dataset into your environment % fprintf(' Loading face dataset. ') % Load Face dataset load ('ex7faces.mat') % Display the first 100 faces in the dataset displayData(X(1:100, :)) fprintf('Program paused. Press enter to continue. ') pause

PCAを使用して主成分を取得し、それを32 times 32行列に変換し、次のように視覚化します。（最初の36のみを表示）

%% =========== Part 5: PCA on Face Data: Eigenfaces =================== % Run PCA and visualize the eigenvectors which are in this case eigenfaces % We display the first 36 eigenfaces. % fprintf([' Running PCA on face dataset. ' ... '(this might take a minute or two ...) ']) % Before running PCA, it is important to first normalize X by subtracting % the mean value from each feature [X_norm, mu, sigma] = featureNormalize(X) % Run PCA [U, S] = pca(X_norm) % Visualize the top 36 eigenvectors found displayData(U(:, 1:36)') fprintf('Program paused. Press enter to continue. ') pause

射影のために最初の100個の特徴ベクトルを取ります。

寸法を縮小した後でも、人間の顔の一般的なフレームは保持されていますが、一部の詳細が失われていることがわかります。私たちのインスピレーションは、ニューラルネットワークを使用して顔認識をトレーニングしているときに、この方法を使用して速度を上げることができる場合があることです。 A

%% ============= Part 6: Dimension Reduction for Faces ================= % Project images to the eigen space using the top k eigenvectors % If you are applying a machine learning algorithm fprintf(' Dimension reduction for face dataset. ') K = 100 Z = projectData(X_norm, U, K) fprintf('The projected data Z has a size of: ') fprintf('%d ', size(Z)) fprintf(' Program paused. Press enter to continue. ') pause %% ==== Part 7: Visualization of Faces after PCA Dimension Reduction ==== % Project images to the eigen space using the top K eigen vectors and % visualize only using those K dimensions % Compare to the original input, which is also displayed fprintf(' Visualizing the projected (reduced dimension) faces. ') K = 100 X_rec = recoverData(Z, U, K) % Display normalized data subplot(1, 2, 1) displayData(X_norm(1:100,:)) title('Original faces') axis square % Display reconstructed data from only k eigenfaces subplot(1, 2, 2) displayData(X_rec(1:100,:)) title('Recovered faces') axis square fprintf('Program paused. Press enter to continue. ') pause

前のk-means画像圧縮の演習では、3次元RGB空間でK-meansアルゴリズムを使用しました。 ex7_pca.mの最後の部分では、散布関数を使用してこの3D空間での最終的なピクセル割り当てを視覚化できるコードを提供しました。各データポイントは、割り当てられたクラスターに応じて色分けされます。マウスをグラフにドラッグして回転させ、3次元空間のデータを調べることができます。データセットを3次元以上で視覚化することは非常に難しいことがわかりました。したがって、一部の情報が失われるという犠牲を払っても、通常はデータを2Dで表示するだけで済みます。実際には、PCAは通常、視覚化を実現するためにデータ次元の数を減らすために使用されます。 ex7-pcaの次の部分。このスクリプトは、PCA実装を3Dデータに適用し、それを2D空間に縮小し、結果を2D散布図として視覚化します。 PCA投影は、データを最大化するビューを選択する回転と考えることができます。これは通常、「最良の」ビューに対応します。

%% === Part 8(a): Optional (ungraded) Exercise: PCA for Visualization === % One useful application of PCA is to use it to visualize high-dimensional % data. In the last K-Means exercise you ran K-Means on 3-dimensional % pixel colors of an image. We first visualize this output in 3D, and then % apply PCA to obtain a visualization in 2D. close all close all clc % Reload the image from the previous exercise and run K-Means on it % For this to work, you need to complete the K-Means assignment first A = double(imread('bird_small.png')) % If imread does not work for you, you can try instead % load ('bird_small.mat') A = A / 255 img_size = size(A) X = reshape(A, img_size(1) * img_size(2), 3) K = 16 max_iters = 10 initial_centroids = kMeansInitCentroids(X, K) [centroids, idx] = runkMeans(X, initial_centroids, max_iters) % Sample 1000 random indexes (since working with all the data is % too expensive. If you have a fast computer, you may increase this. sel = floor(rand(1000, 1) * size(X, 1)) + 1 % Setup Color Palette palette = hsv(K) colors = palette(idx(sel), :) % Visualize the data and centroid memberships in 3D figure scatter3(X(sel, 1), X(sel, 2), X(sel, 3), 10, colors) title('Pixel dataset plotted in 3D. Color shows centroid memberships') fprintf('Program paused. Press enter to continue. ') pause %% === Part 8(b): Optional (ungraded) Exercise: PCA for Visualization === % Use PCA to project this cloud to 2D for visualization % Subtract the mean to use PCA [X_norm, mu, sigma] = featureNormalize(X) % PCA and project the data to 2D [U, S] = pca(X_norm) Z = projectData(X_norm, U, 2) % Plot in 2D figure plotDataPoints(Z(sel, :), idx(sel), K) title('Pixel dataset plotted in 2D, using PCA for dimensionality reduction') fprintf('Program paused. Press enter to continue. ') pause