이번은 앤드류 응 선생님의 머신러닝 코세라 강의의 8주차 내용이다. 이번에는 비지도학습 (Unsupervised Learning)을 배운다.
Clustering
Unsupervised Learning: Introduction
Unsupervised learning 에서는 레이블(outcome 같은 것)이 존재하지 않는다. Unsupervised learning 은 데이터에서 구조를 파악하는 것이다. 예를 들어, 서로 다른 cluster 를 찾는 것이다. Clustering 의 응용으로는 고객군을 분류하거나, 소셜 네트워크 분석에서 사용하거나, 컴퓨팅 클러스터를 구조화하는 것이다.
K-Means Algorithm
K-Means 알고리즘은 clustering 문제를 푸는 대표적인 알고리즘이다. 예를 들어, 두 개의 클러스터로 묶고 싶다고 하자. 랜덤으로 두 개의 클러스터 중심 (cluster centroids) 를 잡는다. 두 개의 중심에 가까운지 여부를 바탕으로 그룹을 나눈다. 그 다음 스텝은 중심을 옮기는 것이다. 각각의 클러스터에 대해서 평균적인 지점으로 중심을 옮긴다. 그리고 옮긴 중심을 바탕으로 다시 클러스터 여부를 지정한다. 이러한 과정을 중심이 거의 움직이지 않을 때까지 반복한다.
Optimization Objective
K-Means 알고리즘이 최적화하려는 목적함수는 각각의 값들이 해당 클러스터 중심부와의 차이의 합의 제곱이 최소화되는 것이다. K-Means 알고리즘이 최적화하는 이유는 첫번째 스텝에서 클러스터 중심부를 고정시킨 상태에서 각각의 값들의 클러스터 여부를 선택하는 것과 두번째 스텝에서 각각의 값들의 클러스터 여부를 고정시킨 상태에서 클러스터 중심부를 선택하는 것과 같다.
Random Initialization
랜덤하게 $K$ 개의 트레이닝 값을 선택한다. 운이 없으면 local optima 가 잘못된 결과를 보여줄 수 있다. 이를 해소하기 위해서는 random initialization 을 여러 번 (예를 들어, 100번) 하는데 각 경우에 대해서 cost function 을 구한다. 그리고, cost 를 최소화하는 경우를 선택한다.
Choosing the Number of Clusters
Cluster 개수를 구하는 방법 중 하나는 "Elbow" 방법이다. 각각의 cluster 개수에 대해서 cost 값을 구한다. Cluster 개수가 증가함에 따라서 cost 가 감소하는데, 그 중에 감소율이 급격히 변하는 cluster 값이 있다. 이 값을 선택할 수 있다. 하지만, 명확하게 "elbow" 처럼 보이지 않는 경우가 있다.
고객 분류 등의 목적을 위해서 K-means 알고리즘을 사용할 때, 클러스터 개수가 적절한 지 판단할 수 있다. 예를 들어, 티셔츠 사이즈를 구분한다고 할 때, S, M, L 의 $K=3$ (세 가지)을 할 지, 아니면 XS, S, M, L, XL 의 $K=5$ (다섯 가지) 를 할 지를 판단할 수 있다.
Motivation
Motivation I: Data Compression
러닝 알고리즘을 빠르게 하기 위해서 차원을 줄인다. 예를 들어서, 2차원을 1차원의 선으로 줄이거나, 3차원을 2차원의 평면으로 줄이는 것이다.
Motivation II: Visualization
시각화는 데이터를 쉽게 이해하도록 해주는데, 시각화 전에 차원을 줄이는 것이 도움이 된다. 예를 들어, 50차원의 특징을 가진 변수를 2차원으로 줄인 후에 시각화가 가능하다.
Principal Component Analysis
Principal Component Analysis Problem Formulation
PCA 를 통해서 차원을 줄일 수 있다. 예를 들어, 2차원을 1차원으로 줄인다면, (x,y) 의 평면에 있는 점들을 하나의 선에 투사 (project) 할 수 있다. 이 때, 프로젝션 에러를 최소화하는 방법으로 선을 추정할 수 있다. PCA 는 선형회귀식이 아니다. 선형회귀식에서는 $x_1, ... , x_n$ 에서 $y$ 를 예측한다면, PCA 에서는 특별히 예측하는 $y$ 와 같은 값이 없다.
Principal Component Analysis Algorithm
PCA 를 시행하기 전에 데이터를 사전에 처리한다. 각각의 변수들을 평균으로 뺀 후 최소값/최대값/표준편차 중에 나누어 normalize 하는 과정을 거친다. PCA 에서 하는 것은 1차원으로 줄이는 예로 들면, 에러를 최소화하는 선 $u^{(1)}$ 의 벡터 하나를 찾는 것이고, 2차원으로 줄이는 경우에는 평면을 이루는 $u^{(1)}$과 $u^{(2)}$를 구하는 것이다. 이를 구하는 과정은 첫번째로 공분산 행렬을 구하는 것이다. 그런 후에 공분산 행렬의 고유벡터(eigenvector) 를 구한다. Single-Value-Decomposition 코드를 실행하여, 행렬 $U$ 를 구한다. 이 중에서 첫 $k$ 개의 컬럼을 쌓은 행렬의 transpose 에 행렬 $X$ 를 곱하여 $z$ 행렬을 구한다. [ ] 수식적으로의 증명을 이해하면 알고리즘을 이해하는데 도움이 될 것 같다.
Applying PCA
Reconstruction from Compressed Representation
차원을 축소한 데이터를 바탕으로 예측한 후 축소한 데이터를 다시 원래 차원으로 복원하는 방법에 대해 다룬다. $X_{approx} = U_{reduce} \cdot z$ 를 이용한다. 이러한 과정을 "reconstruction from compressed representation" 이라 부른다.
Choosing the Number of Principal Components
이번 섹션에서는 $k$ 를 선택하는 방법에 대해서 다룬다. Average squared projection error 를 total variation in the data 로 나눈 값이 가장 작은 $k$ 값을 선택한다. 이 값이 0.01 보다 작으면, 99 퍼센트의 분산이 유지(reatin)되었다고 말한다. 또 다른 값으로는 0.05, 0.10 이다 (95 퍼센트, 90퍼센트의 분산 유지). 이를 구하는 알고리즘은 $k=1$ 부터 PCA 를 시작하여, 값이 0.01 보다 작은지를 확인해볼 수 있다. 이보다 더 효율적인 방법은 svd (single-value-decomposition) 를 할 때, 행렬 S 의 대각선에 있는 값들을 이용하여 쉽게 구할 수 있다. $1-\frac{ \sum_{i=1}^k S_{ii} }{ \sum_{i=1}^n S_{ii} }$ 값이 0.01 보다 작은지 확인한다.
Advice for Applying PCA
이번 섹션에서는 PCA 를 통해서 러닝 알고리즘의 속도를 빠르게 하는지 적용하는 방법에 대해 다룹니다. 강화 학습(supervised learning) 에서, 예를 들어서 100 x 100 = 10,000 개의 feature 가 있다고 하자 ($x, y$). 이는 매우 느릴 것이다. 먼저, input 데이터만 가져온 후 PCA 를 이용해서 예를 들어서 1,000 개의 feature 로 줄인다. 그러면, 새로운 트레이닝 셋이 생긴다 ($z, y$). 로지스틱 회귀식이나 뉴럴 네트워크 등을 이용해서 예측을 한다. 한편, PCA 는 트레이닝 데이터에서만 하며, $x$ 에서 $z$ 로의 대응 (mapping) 을 cross validation 데이터나 test 데이터에 적용할 수 있다. Compression 의 경우에는 $k$ 를 유지되는 분산에 기반하여 선택하는데 비해, 시각화 (vizualization) 의 경우에는 $k=2, 3$을 선택한다.
참고로, PCA 는 overfitting 을 방지하는 방법이 아니다. 이보다는 regularization 을 대신 하는 것이 좋다. 왜냐하면, PCA 에서는 $y$ 값에 대한 정보를 반영하지 않기 때문이다.
시작 단계에서부터 PCA 를 적용하는 것이 좋지 않다. 이보다는 PCA 없이 해본 후에, 메모리 등의 문제로 작동하지 않을 때 PCA 를 적용하는 것이 바람직하다.