[Week 8] Clustering

K-Means Algorithm

 

 이번 시간부터 비지도학습의 클러스터링을 설명합니다. 지도 학습과는 다르게 비지도 학습은 주어진 데이터셋에 레이블이 붙어있지 않고 알고리즘이 스스로 구조를 찾아야 합니다.

 위 그래프처럼 레이블없이 데이터가 주어졌을 때 두가지 그룹으로 묶는 것을 클러스터링이라고 합니다. 가장 많이 사용하는 클러스터링 알고리즘인 K-평균 알고리즘에 대해 알아봅니다.

 

 위와 같이 데이터들이 주어졌을 때 K-평균 알고리즘을 적용해봅시다. 우선 임의로 클러스터의 중심으로 사용될 두 개의 점을 지정합니다. K-평균 알고리즘은 두 가지 단계로 이루어집니다. 첫째, 클러스터 할당. 둘째, 클러스터 중심 이동입니다.

 

 클러스터 할당 단계에서는 각 데이터들이 어떤 클러스터 중심에 더 가까운 지를 계산합니다. 빨간색으로 칠해진 데이터들은 위쪽 중심에 더 가깝고, 파란색으로 칠해진 데이터들은 아래쪽 중심에 더 가깝습니다.

 

 

 그 다음으로 클러스터 중심 이동 단계입니다. 클러스터 중심을 데이터들의 평균값으로 이동합니다. 즉 모든 빨간색 점의 평균을 계산하고 중심을 그 평균으로 이동시킵니다. 파란색도 마찬가지입니다. 

 

 

 이 과정을 반복하다 보면 더 이상 클러스터의 중심이 변하지 않고 데이터 셋의 색상도 변하지 않는 단계에 다다릅니다. 이로써 K-평균은 수렴하고 알고리즘이 완료됩니다.

 

 

 K-평균 알고리즘에 필요한 두가지 입력은 파라미터 K (클러스터의 수) 와 레이블이 없는 데이터 셋입니다. x 벡터는 n차원 벡터로 x0은 관습적으로 1로 둡니다.

 

 

 μ는 각 클러스터의 중심을 나타냅니다. 즉 μ는 K개 존재합니다. 첫번째 for 루프는 클러스터 할당을 담당합니다. 모든 데이터셋에 대해 가장 가까운 클러스터 중심을 할당합니다. 이 때 c^(i) 는 i번째 x 벡터 원소의 가장 가까운 클러스터 중심을 나타냅니다. c^(i) = min k ||x^(i) - μk|| 로 표현할 수 있습니다. 즉 여러 클러스터 중심 중 데이터와의 거리가 가장 짧은 클러스터를 선택하고 할당합니다.

 두번째 for 루프는 클러스터 중심 이동입니다. 클러스터에 할당된 모든 데이터의 평균 값을 구하고 그 위치로 중심을 이동시킵니다.

 

Optimization Objective

  선형 회귀나 로지스틱 회귀처럼 K-평균 알고리즘도 최적화 목표와 비용 함수가 있습니다.

 

 

 새로운 변수가 있습니다. μc^(i)는 학습 예제가 할당된 클러스터의 중심을 나타냅니다. 예를 들어 x^(i) 에 클러스터 5를 할당했다면 C^(i) = 5 입니다. 따라서 μc^(i) = 5 가 됩니다. 결국 x^(i) 에 클러스터 5를 할당한다는 뜻입니다.

 

 

 K-평균을 최소화하는 알고리즘은 결국 클러스터와 데이터들 사이의 거리를 최소화하는 것입니다. 따라서 거리를 비용 함수라고 둘 수 있고 그 거리를 최소화하는 c와 μ 값을 찾는 것이 목표입니다. K-평균 알고리즘에서 비용 함수는 왜곡(Distortion)이라고도 불립니다.

 

 

 이미 우리가 보았던 두가지 for 루프를 통해 비용 함수를 최소화할 수 있습니다. 첫번째 루프에서는 거리를 줄이면서 적절한 c값을 찾을 수 있고 두번째 루프에서는 평균 위치로 중심을 옮기면서 적절한 μ값을 찾습니다.

 

Random Initialization

 

 K-평균 알고리즘에서 초기에 어떤 위치에 클러스터 중심을 위치하냐가 중요한 문제입니다. 초기 위치값에 따라 다른 결과가 나오기 때문입니다. 따라서 우리는 랜덤 초기화를 진행하고 가장 오차가 작은 케이스를 선택합니다. 

 

 

 위 그림처럼 초기값에 따라서 다양한 결과가 나오고 로컬 최적값에 빠지는 경우가 있습니다. 따라서 여러 번의 랜덤 초기화를 진행하고 가장 좋은 결과를 가진 케이스를 고릅니다.

 

 

 실행 방법입니다. 만약 100번 반복하기로 결정했다면 for 루프를 백번 반복합니다.  무작위로 초기화를 100번하고 클러스터 할당과 중심 이동 또한 반복합니다. 결과적으로 가장 낮은 왜곡 값을 가진 케이스를 고르고 초기화 값을 설정합니다.

 

Choosing the Number of Clusters

 또 하나 지정해야 할 파라미터는 클러스터의 수인 K 입니다. 

 

 위 데이터 셋에서 클러스터는 몇개여야 할까요? 2개라고 하는 사람도 있을테고 , 4개라고 답하는 사람도 있고, 다른 숫자를 말하는 사람도 있을 것 입니다. 실제로는 정확한 정답은 없습니다. 비지도 학습의 특성 상 항상 명확한 답이 있는 것은 아닙니다.

 

 클러스터의 수를 사용할 수 있는 방법 중에 하나로 elbow method가 있습니다. K의 숫자를 바꾸면서 알고리즘을 반복하여 비용 함수의 값도 확인합니다. K=3 부분에서 그래프가 급격하게 꺾입니다. 이런 부분을 팔꿈치라고 하고 K=3를 선택합니다.

 다만 이 방법은 자주 쓰이는 방법은 아닙니다. 왜냐하면 왼쪽처럼 적합하게 그래프가 나오지 않고 오른쪽처럼 애매하게 나올 수도 있기 때문입니다. 따라서 특정 그래프에서 제대로 동작하지 않을 수 있습니다.

 결론으로, K를 결정하는 정확한 방법은 없습니다. 주로 알고리즘을 적용한 문제의 종류에 따라 분석하여 몇가지 분류가 필요한지 정하게 됩니다.

---

혼자서 강의를 듣고 정리한 것이니 틀린 점이 있다면 언제든지 지적 부탁드립니다 :)