머신러닝 옥타브 실습(7-1): K-평균 클러스터링
온라인 강의 플랫폼 코세라의 창립자인 앤드류 응 (Andrew Ng) 교수는 인공지능 업계의 거장입니다. 그가 스탠퍼드 대학에서 머신 러닝 입문자에게 한 강의를 그대로 코세라 온라인 강의 (Coursera.org)에서 무료로 배울 수 있습니다. 이 강의는 머신러닝 입문자들의 필수코스입니다. 인공지능과 머신러닝을 혼자 공부하면서 자연스럽게 만나게 되는 강의입니다.
Programming Exercise 7:
K-means Clustering and Principal Component Analysis (K-평균 클러스터링과 주성분 분석)
1. K-means Clustering (K-평균 클러스터링)
In this this exercise, you will implement the K-means algorithm and use it for image compression. You will first start on an example 2D dataset that will help you gain an intuition of how the K-means algorithm works. After that, you wil use the K-means algorithm for image compression by reducing the number of colors that occur in an image to only those that are most common in that image. You will be using ex7.m for this part of the exercise.
이번 실습에서 K-평균 알고리즘을 구현하고 이미지를 압축에 사용합니다. 먼저 K-평균 알고리의 동작 방식에 대한 감각을 익힐 수 있는 2D 데이터 셋에서 시작합니다. 그리고, 이미지에서 발생하는 색상 수를 해당 이미지에서 가장 일반적인 색상으로 줄여 이미지 압축에 K-평균 알고리즘을 사용합니다. 연습은 ex7.m 파일을 사용합니다.
1.1 Implementing K-means (K-평균 구현하기)
The K-means algorithm is a method to automatically cluster similar data examples together. Concretely, you are given a training set {x(1),...,x(m)} (where x(i) ∈ Rn), and want to group the data into a few cohesive “clusters”. The intuition behind K-means is an iterative procedure that starts by guess- ing the initial centroids, and then refines this guess by repeatedly assigning examples to their closest centroids and then recomputing the centroids based on the assignments.
The K-means algorithm is as follows:
The inner-loop of the algorithm repeatedly carries out two steps: (i) As- signing each training example x(i) to its closest centroid, and (ii) Recomput- ing the mean of each centroid using the points assigned to it. The K-means algorithm will always converge to some final set of means for the centroids. Note that the converged solution may not always be ideal and depends on the initial setting of the centroids. Therefore, in practice the K-means algorithm is usually run a few times with different random initializations. One way to choose between these different solutions from different random initializations is to choose the one with the lowest cost function value (distortion).
You will implement the two phases of the K-means algorithm separately in the next sections.
K-평균 알고리즘은 자동으로 데이터 셋을 클러스터링을 하는 알고리즘입니다. 예를 들면, 학습 셋 {x^(1), x^(2),..., x^(m)}이고, x^(i)는 R^(n) 차원 벡터입니다. K 개의 클러스터로 그룹화할 것입니다. K-평균은 초기 클러스터 중심을 초기화하고 반복적으로 학습 예제를 할당하고 다시 중심을 계산하는 과정을 반복합니다.
K- 평균 알고리즘은 다음과 같습니다.
% 클러스터 중심(Cluster Centroids) 초기화
centroids = kMeansInitCentroids(X, K);
for iter = 1:iterations
% 클러스터 할당 단계(Cluster assignment step) :
% 가장 가까운 클러스터 중심에 데이터를 할당
% 예제 i에 할당한 클러스터 중심의 인덱스 c^(i)에 대응하는 idx^(i)
idx = findClosestCentroids(X, centroids);
% 클러스터 이동 단계(Move centroid step):
% 평균을 계산
centroids = computeMeans(X, idx, K);
end
알고리즘의 내부 루프는 두 단계를 반복합니다.
(i) 학습 예제를 가장 가까운 클러스터 중심(Cluster Centroid)에 할당
(ii) 클러스터 별로 할당된 학습 예제들의 평균을 계산하여 새로운 클러스터 중심(Cluster Centroid)을 설정
K-평균 알고리즘은 항상 중심에 대한 최종 평균으로 수렴합니다. 수렴된 평균이 항상 이상적인 것은 아니고 중심의 초기 설정에 따라 달라집니다. 실제로 K-평균 알고리즘은 초기화를 여러 번 실행합니다. 여러 번에 걸쳐 진행한 후 가장 낮은 비용 함숫값(왜곡)을 가진 것을 선택합니다.
다음 섹션에서 K-평균 알고리즘의 두 간계를 개별적으로 구현합니다.
1.1.1 Finding closest centroids (가장 가까운 클러스터 중심 찾기)
In the “cluster assignment” phase of the K-means algorithm, the algorithm assigns every training example x(i) to its closest centroid, given the current positions of centroids. Specifically, for every example i we set
c(i) := j that minimizes ||x(i) − μj||^2
where c(i) is the index of the centroid that is closest to x(i), and μj is the position (value) of the j’th centroid. Note that c(i) corresponds to idx(i) in the starter code.
Your task is to complete the code in findClosestCentroids.m. This function takes the data matrix X and the locations of all centroids inside centroids and should output a one-dimensional array idx that holds the index (a value in {1,...,K}, where K is total number of centroids) of the closest centroid to every training example.
You can implement this using a loop over every training example and every centroid.
Once you have completed the code in findClosestCentroids.m, the script ex7.m will run your code and you should see the output [1 3 2] corresponding to the centroid assignments for the first 3 examples.
You should now submit your solutions.
K-평균 알고리즘의 클러스터 할당 단계에서 알고리즘은 학습 예제 x^(i)를 가장 가까운 클러스터 중심에 할당합니다. 예를 들어, 모든 예제에 대해 최소화합니다.
여기서, c^(i)는 x^(i)에 가장 가까운 중심의 인덱스이고, μj는 j 번째 중심의 위치 값입니다. c^(i)는 시작 코드의 idx(i)에 해당합니다.
findClosestCentroids.m 파일의 코드를 완성합니다. findClosestCentroids.m 파일은
데이터 행렬 X와 클러스터 중심 내부의 모든 중심 위치 인덱스 {1,2,..., K}를 입력받아 모든 학습 예제에 가장 가까운 중심의 1차원 배열의 idx를 출력합니다.
findClosestCentroids.m 파일에서 코드를 완성하면, ex7.m 파일 코드를 실행하고 처음 3개 예제의 중심 할당에 해당하는 출력 [1 3 2]를 볼 수 있습니다.
완성되면 답안을 제출합니다.
<Part 1 : 가장 가까운 클러스터 중심 찾기>
(1) 데이터 업로드
clear ; % 옥타브 프로그램에 모든 변수를 제거
close all; % 터미널 이외의 창을 닫음
clc % 터미널을 깨끗이 정리
load('ex7data2.mat');
>> load('ex7data2.mat');
>> whos
Variables in the current scope:
Attr Name Size Bytes Class
==== ==== ==== ===== =====
X 300x2 4800 double
Total is 600 elements using 4800 bytes
(2) 클러스터 중심 개수와 위치 초기화
클러스터의 총 개수 K를 정의하고, 각 위치를 지정합니다.
K = 3;
initial_centroids = [3 3; 6 2; 8 5];
(3) findClosestCentroid.m 파일 분석
function idx = findClosestCentroids(X, centroids)
%FINDCLOSESTCENTROIDS 모든 학습 예제에 대한 클러스터 중심을 할당
% idx = FINDCLOSESTCENTROIDS (X, centroids) returns the closest centroids
% 데이터 셋 행렬 X를 위한 가자 가까운 클러스터 중심 idx를 반환
% idx는 m X 1 벡터이고 성분의 값은 [1,2,...,K] 값 중 하나
% K 설정 (클러스터 중심의 성분의 개수로 K를 확인)
K = size(centroids, 1);
% idx 변수 초기화
idx = zeros(size(X,1), 1);
% ====================== YOUR CODE HERE ======================
% Instructions: 모든 학습 예제 별로 가장 가까운 클러스터 중심을 할당하고 idx에 저장
% idx(i)는 i 번째 학습 예제에 가장 가까운 클러스터 중심의 인덱스
% idx는 m X 1 벡터이고 성분의 값은 [1,2,...,K] 값 중 하나
%
% Note: For 루프를 사용하여 계산
%
% =============================================================
end
(4) 클러스터 중심과 학습 예제 간의 거리를 계산
각 클러스터 중심과 학습 예제 i 사이의 유클리드 길이를 구하고 distance에 저장합니다. 유클리드 길이를 구할 때 norm() 함수를 사용합니다.
for i = 1:length(X)
for j = 1: K
distance (j) = norm(X(i,:) - centroids(j,:));
end
end
각 학습 예제마다 K개의 유클리드 길이가 있고, 그중에 가장 작은 값을 구합니다.
[s index] = sort(distance);
idx(i) = index(1);
두 가지 값을 합친 값은 다음과 같습니다.
centroids = initial_centroids
for i = 1:length(X)
for j = 1: K
distance (j) = norm(X(i,:) - centroids(j,:));
end
[s index] = sort(distance);
idx(i) = index(1);
end
이렇게 계산을 완료하면, idx 벡터는 다음과 같습니다.
>> idx
idx =
Columns 1 through 16:
1 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1
....
Columns 289 through 300:
2 2 2 2 2 2 2 3 2 2 2 1
(5) 정답
function idx = findClosestCentroids(X, centroids)
%FINDCLOSESTCENTROIDS 모든 학습 예제에 대한 클러스터 중심을 할당
% idx = FINDCLOSESTCENTROIDS (X, centroids) returns the closest centroids
% 데이터 셋 행렬 X를 위한 가자 가까운 클러스터 중심 idx를 반환
% idx는 m X 1 벡터이고 성분의 값은 [1,2,...,K] 값 중 하나
% K 설정 (클러스터 중심의 성분의 개수로 K를 확인)
K = size(centroids, 1);
% idx 변수 초기화
idx = zeros(size(X,1), 1);
% ====================== YOUR CODE HERE ======================
% Instructions: 모든 학습 예제 별로 가장 가까운 클러스터 중심을 할당하고 idx에 저장
% idx(i)는 i 번째 학습 예제에 가장 가까운 클러스터 중심의 인덱스
% idx는 m X 1 벡터이고 성분의 값은 [1,2,...,K] 값 중 하나
%
% Note: For 루프를 사용하여 계산
%
for i = 1:length(X)
for j = 1: K
distance (j) = norm(X(i,:) - centroids(j,:));
end
[s index] = sort(distance);
idx(i) = index(1);
end
% =============================================================
end
1.1.2 Computing centroid means
Given assignments of every point to a centroid, the second phase of the algorithm recomputes, for each centroid, the mean of the points that were assigned to it. Specifically, for every centroid k we set
where Ck is the set of examples that are assigned to centroid k. Concretely, if two examples say x(3) and x(5) are assigned to centroid k = 2, then you should update μ2 = 1/2* (x^(3) + x^(5)).
You should now complete the code in computeCentroids.m. You can implement this function using a loop over the centroids. You can also use a loop over the examples; but if you can use a vectorized implementation that does not use such a loop, your code may run faster.
Once you have completed the code in computeCentroids.m, the script ex7.m will run your code and output the centroids after the first step of K- means.
You should now submit your solutions.
알고리즘의 첫 번째 단계가 모든 데이터 포인트에 클러스터 중심을 할당하는 단계입니다. 두 번째 단계는 클러스터 중심 k별로 데이터 셋의 평균을 다시 계산하는 단계입니다. 클러스터 중심 k의 값은 다음과 같이 구합니다.
여기서 Ck는 중심 k에 할당된 예제의 집합입니다. 예를 들면, 두 예제 x^(3)와 x^(5)가 클러스터 중심 k = 2에 할당되었습니다. 따라서, k=2 인 클러스터 중심 μ2는 다음과 같이 계산합니다.
μ2 = 1 / 2 * (x ^ (3) + x ^ (5))
computeCentroids.m 파일의 코드를 작성합니다. 클러스터 중심에 대한 루프를 사용하여 함수를 구현할 수 있습니다. 그러나 루프가 아닌 벡터화된 구현을 사용한다면 코드를 더 빨리 실행할 수 있습니다.
computeCentroids.m 파일을 완료하면, ex7.m 파일은 K-평균의 첫 단계를 완료한 후에 클러스터 중심을 출력합니다.
완성되면 submit을 합니다.
<Part 2 : 평균 계산하기>
(1) 데이터 로드
clear; close all; clc
load('ex7data2.mat');
(2) 학습 예제 별로 클러스터 할당
K = 3;
initial_centroids = [3 3; 6 2; 8 5];
idx = findClosestCentroids(X, initial_centroids);
(3) computeCentroids.m 파일 분석
function centroids = computeCentroids(X, idx, K)
%COMPUTECENTROIDS returns 클러스터의 평균을 계산하고 새로운 클러스터 중심을 반환
%
% centroids = COMPUTECENTROIDS(X, idx, K)
% 데이터 행렬 X의 열은 데이터 포인트
% 벡터 idx는 각 데이터 포인터에 할당된 클러스터 중심의 인덱스 [1,2,...,K]
% K는 클러스터 중심의 수
% 데이터 행렬 X의 크기를 정의
[m n] = size(X);
% 반환할 새로운 클러스터 중심을 초기화
centroids = zeros(K, n);
% ====================== YOUR CODE HERE ======================
% Instructions: 각 클러스터별로 평균을 계산
% 열 벡터 centroids(i, :)는 각 클러스터의 평균을 가짐
%
% Note: For 루프를 사용할 수 있음
%
% =============================================================
end
(4) 평균 계산하기
기본 변수를 선언합니다.
[m n] = size(X);
centroids = zeros(K, n);
새로운 클러스터 중심의 위치는 클러스터가 할당된 데이터들의 평균값입니다. 데이터 행렬 X를 클러스터 k 별로 구분해야 합니다. idx의 값이 k과 같으면 1 다르면 0인 '==' 연산자를 이용합니다.
index = (idx == i);
데이터 행렬 X의 피처 개수는 n개입니다. idx는 m X 1 벡터이므로 각 열 단위로 평균을 계산합니다.
centroids(i,:) = index'*X/sum(index);
다음과 같이 계산할 수 있습니다.
[m n] = size(X);
centroids = zeros(K, n);
for i = 1 : K
index = (idx == i);
centroids(i,:) = index'*X/sum(index);
end
새로운 클러스터 중심의 결과는 다음과 같습니다.
>> centroids
centroids =
2.4283 3.1579
5.8135 2.6337
7.1194 3.6167
(5) 정답
function centroids = computeCentroids(X, idx, K)
%COMPUTECENTROIDS returns 클러스터의 평균을 계산하고 새로운 클러스터 중심을 반환
%
% centroids = COMPUTECENTROIDS(X, idx, K)
% 데이터 행렬 X의 열은 데이터 포인트
% 벡터 idx는 각 데이터 포인터에 할당된 클러스터 중심의 인덱스 [1,2,...,K]
% K는 클러스터 중심의 수
% 데이터 행렬 X의 크기를 정의
[m n] = size(X);
% 반환할 새로운 클러스터 중심을 초기화
centroids = zeros(K, n);
% ====================== YOUR CODE HERE ======================
% Instructions: 각 클러스터별로 평균을 계산
% 열 벡터 centroids(i, :)는 각 클러스터의 평균을 가짐
%
% Note: For 루프를 사용할 수 있음
%
for i = 1 : K
index = (idx == i);
centroids(i,:) = index'*X/sum(index);
end
% =============================================================
end
