[Incarnate the Algorithm] PCA & K-means Clustering

unsupervised learning은 입력값인 x만 존재하고 output이 존재하지 않는다.

PCA(Principal Component Analysis)와 K-means Clustering(이하 K.C)은 대표적인 unsupervised learning이다. 

---

 

PCA는 대표적인 dimension reduction기법 중에 하나다.

PCA를 알기 위해서는 encoding과 decoding이 필요하다.

 

먼저, 공차한계(tolerance)혹은 분산팽창요인(VIF)가 현저하게 높아지거나 낮아지는 것을 방지하기 위해 mean centering을 사용한다.

각 data를 데이터의 평균(mean)으로 빼주는 것을 말한다.

 

이제 encoding과 decoding을 알아보자.

N-dim data x_p에 대해 모든 vector는 그 N-dim vector space의 basis로 나타낼 수 있다.

basis는 서로에 대해 모두 일차독립이다.

이를 이용하여 각 데이터를 다음과 같이 나타낼 수 있다.

c_n : basis vector

w_n : 어떤 data point x_p를 c_n으로 표현하기 위한 weight vector

이를 행렬의 형태로 나타내면 다음과 같다.

이와 같이 나타내는 것을 encoding이라 한다.

encoding; 첫번째 식은 식1이라 하자.

C는 basis column vector로 이루어진 행렬이다.

 

이를 이용하여 우리가 나타내는 C*w_p와 기존의 data x_p와의 cost를 Least Square로 나타낼 수 있다.

데이터와 같은 차원의 basis로 나타냈기 때문에 cost를 계산해도 0이다.

 

기존의 data를 basis vector로 표현한 것(encoding)을 다시 기존의 data형태로 되돌리는 것을 decoding이라 하며 다음의 과정을 거친다.

decoding

 

이때, 일반적인 basis가 아니라 orthonormal basis(or spanning set)으로 표현하면 위 식을 간단하게 바꿀 수 있다.

-  orthonormal basis : 크기가 1이고 서로 수직인 basis vectors의 집합

 

orthonormal basis c

간단해진 식

식1에 간단해진 식을 대입하면 다음의 결과를 얻을 수 있다.

이를 Autoencoder라 하며 이는 encoding후에 decoding이 이뤄진 결과이다.

basis vector의 차원인 K와 data의 차원 N이 같은 경우, Autoencoder의 결과는 여전히 기존의 x_p와 같다.

 

만약 K < N인 경우 다음과 같은 결과를 얻어야 한다.

Autoencoder로 원하는 결과

 

지금까지 구한 cost function은 오직 weight parameter에 대한 함수였고, spanning set C는 고정되었다. 하지만 더 나은 C가 존재할 수 있으며 그것까지 찾아야 정말 좋은 결과를 얻을 수 있다.

이 점을 보완한 것이 PCA이다. 

PCA에서는 C 또한 학습한다. 그에 따른 cost function은 다음과 같다.

PCA에서 cost function

앞서 orthonormal basis를 적용하여 간단해진 식을 위 cost function에 대입하면 다음과 같다.

이를 Linear Autoencoder라 한다.

이를 최소화하는 것이 우리의 목표다.

 

 

linear Autoencoder를 통해 기존의 data를 다음과 같이 표현이 가능하다.

이때, 주목할 점은 linear autoencoder가 공분산 행렬(covariance matrix)의 고유벡터들(eigenvectors)로 표현이 가능하다는 것이다.

N X P의 mean-centered data matrix X가 존재한다고 하자.

N X N 공분산 행렬은 고유벡터행렬과 고윳값행렬로 나타낼 수 있다. 식으로 표현하면 다음과 같다.

PCA의 autoencoder

 

이제 이를 통해 encoding한 data는 다음과 같이 나타난다.

PCA의 autoencoder

 

 

드디어 간단한 코드를 통해 encoding을 진행해보자.

먼저 아래의 코드로 data를 mean-centering한다.

def center(X):
    '''
    A function for normalizing each feaure dimension of an input array, mean-centering
    and division by its standard deviation
    
    '''
    X_means = np.mean(X,axis=1)[:,np.newaxis] # 각 행의 평균을 구한다
    X_normalized = X - X_means # 각 행의 데이터를 위에서 구한 평균으로 뺴준다

    return X_normalized

 

 

mean-centered data

 

numpy의 method를 이용하여 eigenvector와 eigenvalue matrices를 구할 수 있다.

def compute_pcs(X,lam):
    '''
    A function for computing the principal components of an input data matrix.  Both
    principal components and variance parameters (eigenvectors and eigenvalues of XX^T)
    are returned
    '''
    # create the correlation matrix
    P = float(X.shape[1])
    Cov = 1/P*np.dot(X,X.T) + lam*np.eye(X.shape[0]) # np.eye : 2를 넣어주면 2X2 단위 행렬을 만들어준다

    # use numpy function to compute eigenvalues / vectors of correlation matrix
    D,V = np.linalg.eigh(Cov)
    return D,V # D ; eigenvector matrix, V : eigenvalue matrix(principal component)

lam = 10**(-7)
D, V = compute_pcs(X, lam)

 

그리고 이를 PCA의 Autoencoder에 대입하여 다음의 결과를 얻을 수 있다.

w_p = np.dot(V.T, X) # autoencoded x_p
w_x = w_p[0]
w_y = w_p[1]

plt.figure(figsize=(2,8))
plt.ylim(-10, 10)
plt.xlim(-3,3)
plt.scatter(w_x, w_y)

Autoencoded data

 

---

 

 

K-means clustering에 대해 알아보자.

생각보다 간단하다.

 

이 기법의 동작순서는 다음과 같다.

1) k개의 initial centroids를 랜덤으로 설정한다.

2) 각 centroid로부터 x_p까지의 거리를 재고 그 중에서 가장 작은 kth cluster에 그 data를 포함시킨다.

3) 각 cluster에 포함된 data들의 평균좌표를 새로운 centroid로 지정한다.

4) 2 ~ 3을 반복한다.

 

Notations

- k : # of clusters in a dataset(= 분류하고자 하는 clusters의 수)

- centroid of the clusters : c_1, c_2, ... , c_k

- S_k = { p | if x_p belongs to the kth cluster} (= kth cluster에 속하는 data(= x_p)의 index(= p)의 집합)

 

이때, 적절한 cluster의 개수 k를 설정해야 한다.

k를 점진적으로 늘리면서 각 cluster의 centroid와 data 사이의 평균 거리가 더이상 크게 감소하지 않는 시점의 k를 가장 효율적인 k로 선택한다.

 

 

 

이제 이를 코드로 짜보자.

여기서는 k를 설정하는 과정은 생략하고 k를 3으로 고정한다.

 

다음과 같은 data를 가정하자.

 

먼저 initial centroids를 설정한다.

import random

C = np.zeros((3, 2)) # 초기 3개의 클러스터의 x,y좌표를 -1.5~1.5 범위에서 지정
for i in range(3):
        for j in range(2):
            k = random.uniform(-1.5, 1.5)
            C[i, j] = k

 

이후, 2 ~ 3의 과정을 반복하는데 10번의 반복으로도 충분하기 때문에 10번만 반복하였다.

for iteration in range(10):
    dist_c = np.zeros((3,36)) # 36개 data의 각 점과 3개의 클러스터간의 distance를 저장한 array
    for i in range(3):
        x = np.repeat(C[i,0], 36) # ith cluster의 x좌표를 data수만큼 복사한 array
        y = np.repeat(C[i,1], 36) # ith cluster의 y좌표를 data수만큼 복사한 array

        dist_x = np.abs(X[0,:] - x) # data와 cluster의 x좌표 차이 array
        dist_y = np.abs(X[1,:] - y) # data와 cluster의 y좌표 차이 array

        d = np.sqrt(dist_x**2 + dist_y**2) # data와 cluster간의 거리 array
        dist_c[i,:] = d # dist_c array의 ith행에 ith cluster와 data간의 거리를 저장

    c = np.argmin(dist_c, axis=0) # 3개의 cluster 중에서 가장 거리가 가까운 index 반환
    c_k = np.zeros((3,2)) # index를 기반으로 정할 새로운 cluster array
    for i in range(3):
        c_k[i,0] = np.mean(X[0][c==i])
        c_k[i,1] = np.mean(X[1][c==i])
    C = c_k

plt.scatter(X[0],X[1])
for i in range(3):
    plt.scatter(c_k[i,0], c_k[i,1], label="{index}th cluster".format(index=i))

plt.title("K-means Clustering")
plt.legend(loc='best', fontsize=8)
plt.show()

그리 어렵지 않은 과정을 통해 성공적인 결과를 얻을 수 있었다.

가끔 initial centroid의 위치에 따라 이상한 결과가 나오기도 하지만 그럴 확률은 매우 희박하다.

 

 

 

지금까지 PCA와 K-means clustering에 대해 간단하게 알아보고 코드로 구현해보았다.

매우 간단한 코딩이지만 이론을 이해하는데 큰 도움이 되었다.