[Seoul National Univ: ML/DL] Lecture 11. Unsupervised Learning

본 포스팅은 서울대학교 이준석 교수님의 M3239.005300 Machine Learning & Deep Learning 1을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.
이준석 교수님에게 강의 자료 사용에 대한 허락을 받았음을 알립니다.
https://youtu.be/fBtMz4htSGg?si=qsHn3wPXg3gUjLcJ

 

 

Unsupervised Learning (비지도 학습)

 Unsupervised Learning은 label이 없는 데이터에서 패턴이나 구조를 찾아내는 학습 방법이다. 주어진 데이터만으로 숨겨진 관계나 구조적 특성을 발견하는 것이 목표이다. 주요 기법으로 Clustering, Dimension reduction, Density estmation이 있다.

 

 

1. Clustering

 

Clustering는 Unsupervised Learning의 대표적인 기법으로, 유사한 특성을 가진 데이터를 그룹으로 묶는 과정을 의미한다. 레이블이 없는 데이터에서 패턴을 발견하거나 숨겨진 구조를 찾는 데 활용된다.

 

 Clustering의 주요 algorithm에는 Hierarchical algorithms과 Partitional algorithms으로 나눌 수 있다. 

 

 Hierarchical algorithms은 세부적인 것 부터 집합시키면서 계층적 구성을 만드는 알고리즘이다. Bottom-up 형식이다.

 Partitional algorithms은 다양한 partitions을 만든 후 어떤 기준을 바탕으로 평가하는 Top-down 형식이다.

 

K-Means Clustering

 

 K-Means Clustering은 K개의 중심점을 기준으로 데이터를 K개의 군집으로 나누는 알고리즘이다. 

 

Initialize: K개의 cluser center를 랜덤으로 선택한다.

Alternate:

Step a) 각 data point를 가장 가까운 cluster center로 할당한다.(유클리드 거리 사용)

Step b) 각 cluster의 평균을 구해 cluster center를 변경한다.

-> Step a~b를 cluster center가 변경되지 않을 때까지 반복한다.

 초기 설정이 K = 2인 K-Means Clustering 동작을 그림으로 나타내면 아래와 같다.

 

초기 설정이 K = 3인 K-Means Clustering 동작을 그림으로 나타내면 아래와 같다.

 

K-Means Clustering은 각 data point와 해당 centroid 간의 유클리드 거리를 최소화하는 것이 목표이다. 

 

 K-Means Clustering이 무한 루프에 빠지지 않으려면 algorithm이 계속 반복 되다가 어떠한 datapoint도 바뀌지 않는 상황이 있어야만 한다. 다행히도 모든 경우의 수를 돈다고 가정 해도 O(K^N)이므로 무한루프는 발생하지 않게 된다. 

 

 K-Means Clustering은 초기 랜덤 K가 어떤 값을 가지느냐에 따라 다른 결과를 가지게 된다.

 K-Means Clustering의 시간 복잡도는 1번 실행할 때마다 모든 data point를 대상으로 K개의 cluster center의 유클리드 거리를 계산해야하므로 O(KN)이고, 이를 몇 번 반복하느냐에 따라서 최악의 경우 O(K^N)만큼의 시간 복잡도를 갖는다.

 cluster center 개수인 K를 결정하는 방법은 elbow point가 되는 지점의 K를 고르는것이 적절하다. J 함수는 K를 계속 증가시킬수록 값이 작아지는 함수이다. 이는 K가 계속 증가하면 모든 data point의 개수인 N을 그대로 clustering하기 때문이다. 이를 x를 K로, y를 J에 대한 그래프로 나타내보면 어떤 지점부터 y축 값의 변화가 미미해지는 지점이 있는데, 이를 elbow point라 하고, 이 지점을 K로 결정한다. 하지만 실제로는 elbow point가 관측되지 않는 경우도 있다.  

 

 

 

2. Dimension Reduction

 

 Data Mainifolds는 고차원 공간에서의 데이터가 밀집된 저차원 구조이다. 예를 들어 MNIST의 전체 차원은 28X28차원 공간이지만 실제 유효한 이미지는 전체 784차원 공간의 극히 일부를 차지한다. 이 일부가 바로 저차원 manifolds에 해당하며, 서로 비슷한 숫자들은 이 manifolds 상에서 가깝게 위치한다.

 

Multidimensional Scaling(MDS)

 

Multidimensional Scaling(MDS)는 고차원 데이터를 저차원 공간에 투영해 시각화하거나 분석하는 Dimension Reduction 기법이다. 특히, 데이터 간의 거리(유사도) 정보를 보존하면서 차원을 축소하는 데 사용된다.

 

 일반적으로 MDS는 closed form solution을 갖고 있지 않아, 최적의 저차원 embedding을 찾기 위해서는 Gradient Descent 같은 iterative optimization 방법을 사용해야 한다.

 

Principal Component Analysis(PCA)

 

 Principal Component Analysis(PCA)는 고차원 데이터를 저차원으로 변환하는 Dimension Reduction 기법이다. 데이터의 Variance을 최대한 보존하는 새로운 축(Principal Component)을 찾아 원래의 차원을 축소한다.

 

 

 

 

 

 

PCA) Step 1. Zero-center and normalize the data

 

 먼저 X에 평균을 빼서 평균이 0이 되도록 변환한다. 그리고 scaling을 통해 변수들의 standard를 동일하게 맞춘다.

 

PCA) Step 2. Estimate the covariance matrix

 

 큰 분산을 가지는 값만을 Principle component으로 선택해야하므로 각 변수들간의 관계를 나타내는 covariance matrix를 계산한다. 

PCA) Step 3. Eingenvalue Decomposition

 

고유값 분해(Eigenvalue Decomposition)을 수행해 covariance를 eigenvalue와 eigen vector로 분리한다. 원래 data를 회전 시키는 것이다.

 

PCA) Step 4. Principal Components 

 

 원래 데이터의 정보의 손실을 최소화시키기 위해 eigen value가 가장 큰 순서대로 K개의 principle components를 선택한다. 

 

 PCA를 Linear Regression과 비교하면 아래와 같다. Linear Regression은 hyperplane에 수평으로 데이터를 projection 하지만, PCA는 hyperplane에 수직으로 데이터를 projection한다.

 

 최적의 principal component 수는 앞서 K-Means Clustering에서 배웠던 것 처럼 elbow point로 결정하면 된다.