[Machine Learning] Exam 7 (Week 8)

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

8주차 과제는 다음과 같습니다.

 

- pca.m : PCA 알고리즘 구현 코드

- projectData.m : PCA 알고리즘으로 구한 \(U\) 행렬을 통해서 새로운 feature \(z\)를 구하는 함수

- recoverData.m : 새로운 feature \(z\)에서 다시 n차원의 \(x_{approx}\)를 구하는 함수

- findClosestCentroids.m : 각 training example \(x^{(i)}\)의 가장 가까운 centroid의 index를 반환하는 함수

- computeCentroids.m : 각 centroid에 속하는 example을 평균을 구해서 centroid \(\mu_k\)를 갱신하는 함수

- kMeansInitCentroids.m : 초기 Centroid를 설정해주는 함수

 

전체 코드는 아래 경로를 참조하면 됩니다.

https://github.com/junstar92/Coursera/tree/master/MachineLearning/ex7

 

우선 7주차에 배웠던 K-means algorithm부터 시작하겠습니다. 자세한 내용은 아래 7주차 강의내용을 참조.

2020/08/25 - [ML and DL/Machine Learning] - [Machine Learning] Unsupervised Learning 비지도 학습

[findClosestCentroid.m]

input X에 대해서 가장 가까운 Centroid의 index를 반환하는 함수를 작성합니다.

모든 training set에 대해서 가장 가까운 centroid의 index를 반환하게 됩니다.

즉,  training set \(x^{(i)}\)에 대해서 \(\mu_1, ... \mu_K\)의 거리의 제곱을 구해서 가장 작은 centroid의 index를 \(c^{(i)}\)에 저장하면 됩니다.

여기서 [a b] = min(Matrix)를 사용했는데, 이때 a는 Matrix의 가장 작은 값이고, b는 가장 작은 값의 index입니다.

 

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.
%
m = size(X, 1);

for i = 1:m
  length = (X(i,:) - centroids).^2;
  [a idx(i)] = min(sum(length, 2));
endfor

% =============================================================

end

참고로 26 line의 X(i, :) - centroids는 1 x n 차원 - K x n 차원이며, X(1,:)이 centroid의 각각의 행에 연산이 되어서 결과는 K x n 차원입니다.

 

[computeCentroids.m]

위의 과정을 진행합니다. 각 centroid에 속하는 example \(x^{(i)}\)의 값들의 평균을 구해서 \(\mu_k\)의 값을 갱신한다.

우선 전체 코드는 아래와 같습니다.

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
  X_i = X(find(idx == i), :);
  n = size(X_i, 1);
  centroids(i,:) = sum(X_i) ./ n;
endfor


% =============================================================


end

line29에서 i번째 centroid에 속하는 training example만을 추출한 다음, line31에서 각 feature별로 다 더해서 평균을 구해줍니다.

 

[kMeansInitCentroids.m]

K-mean 알고리즘에서 처음 K개의 centroid를 선택하는 방법 중 하나는 m개의 training example에서 랜덤으로 K개를 뽑아서 centroid로 사용하는 것입니다. 랜덤한 training example을 선택할 때는 randperm함수를 사용합니다.

코드는 다음과 같습니다.

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
%

randidx = randperm(size(X, 1));
centroids = X(randidx(1:K), :);

% =============================================================

end

 

다음은 8주차의 PCA에 관련된 과제입니다.

PCA 강의내용는 이전 글을 참조.

2020/08/27 - [ML and DL/Machine Learning] - [Machine Learning] Dimensionality Reduction(PCA)

 

[pca.m]

ex7_pca.m 코드를 살펴보면 이미 featrue scaling이 되어있기 때문에, 우리는 아래 PCA 알고리즘만 구현하면 됩니다.

단순히 Sigma를 구해서 svd함수를 적용하면 쉽게 구현할 수 있습니다.

코드는 다음과 같습니다.

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).
%

Sigma = (1/m)*(X'*X);
[U, S, V] = svd(Sigma);

% =========================================================================

end

 

[projectData.m]

위에서 구한 \(U\) Matrix에서 우리가 축소하려고 하는 K차원의 값만큼의 열을 추출해서 \(U_{reduce}\)를 구합니다.

그리고 \(U_{reduce}^T \times x\)를 계산해서 \(z\)를 구하면 됩니다.

\(U_{reduce}\)는 \(n \times k\)차원이고, \(x\)는 \(m \times n\)차원이기 때문에 \(x * U_{reduce}\)를 계산하면 됩니다.

코드는 아래와 같습니다.

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

 

 

[recoverData.m]

우리가 K차원으로 축소해서 새롭게 구한 feature \(z\)를 다시 n차원의 \(x\)로 복구하는 함수입니다. 완전히 복구가 되지는 않으며 여기서 구해진 x는 기존의 x값의 근사값입니다.

\[x_{approx} = U_{reduce} \times z\]

여기서 \(z\)는 \(m \times k\)차원이고, \(U_{reduce}\)는 \(n \times k\)차원이기 때문에 \(z * U_{reduce}^T\)로 한번에 계산해줍니다.

코드는 아래와 같습니다.

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.
%               
X_rec = Z * U(:,1:K)';

% =============================================================

end