클러스터링 (k-means 알고리즘)

1. 비지도학습 unsupervised learning

왼: 지도학습    오: 비지도학습

분류로 대표되는 정답이 함께 주어지는 학습을 지도학습이라고 했다. 비지도학습이란 트레이닝 데이터의 클래스 레이블이 주어지지 않은unknown 경우를 말한다. 측정치, 관측치 등등의 집합을 주고, 데이터 안의 클러스터의 존재를 증명하는 것을 목표로 한다. 우리는 데이터를 탐색하여 내재된 구조intrinsic structures를 찾고자 한다.

 

2. 클러스터링

2-1. 개념

(1) 클러스터링은 '군집cluster'이라고 불리는 데이터 안의 유사한 그룹들similarity groups을 찾아내는 기술이다.

(2) 지도학습에서 사전에 이미 그룹화가 완료되어 데이터 인스턴스가 속한 그룹이 무엇인지 알려주는 클래스 값은 주어지지 않는다.

 

2-2. 응용

(1) 시장 세분화 Market Segmentation

(2) 소셜 네트워크 분석 Social Network Analysis

(3) 천문 데이터 분석 Astronomical Data Analysis

 

3. k-means 알고리즘

3-1. 과정

k=2

(1) 만들고자 하는 클러스터 개수 k가 주어진다.

(2) 주어진 데이터 분포 안에서 랜덤하게 k 개의 중심점centroid을 찍는다.

(3) 각 중심점과의 유사도를 측정(어느 중심점과 더 가깝냐)하고, 해당 중심점으로 클러스터링한다.

(4) 나눠진 군집 내의 평균을 다시 중심점으로 삼는다.

(5) 각 데이터 포인트의 변화가 더 이상 없을 때까지 (3), (4)를 반복한다. 클러스터의 중심점이 더 이상 바뀌지 않게 되면 k-means가 수렴하였다고 판단한다.

 

3-2. 알고리즘

인풋: 클러스터 개수 k, 트레이닝 세트

알고리즘:

크게 두 부분으로 나눌 수 있다. "클러스터 배당 단계"와 "중심점 이동 단계"다. 클러스터 배당 단계에서는 클러스터 인덱스 c^(i)에 m개의 데이터 샘플 각각에 대해 클러스터 중심점 k개 중 가장 자신과 가까운 쪽으로 할당된다. 중심점 이동 단계에서는 각 클러스터의 평균(뮤)을 구하고 중심점을 재할당한다.

정해진 답이 없기 때문에 클러스터링 결과가 다소 이상하게 나올 수 있다. 결과의 왜곡 정도를 막아주기 위한 방법에는 최적화와 랜덤 초기화가 있다. 전자는 왜곡을 보정하는 것이고, 후자는 초기에 어떤 점을 잡는가에 따라 성능이 크게 달라지는 성질을 이용한 것이다.

 

3-3. 최적화

optimize function의 다른 말은 왜곡 함수distortion function이다. 무언가가 왜곡되어 이상한 결과가 나오는 것이니까 왜곡을 줄이는 중심점을 찾는 것이다.

 

3-4. 랜덤 초기화 Random Initialization

(1) 군집의 개수 k는 m보다 (일반적으로 아주) 작다.

(2) 일반적으로 randomly initialize한다. 초기에 이 과정을 어떻게 하느냐에 따라 결과가 아주 달라질 수 있다. 만약 우연히 아주 가까운 두 점을 잡아버린다면 결과가 영 꼬여 버릴 수 있는 것이다.

(3) Local Optima: 가장 좋은 것은 데이터셋 전역에 대해 올바른 global optima일 것이다. 그러나 초기값에 따라 각기 다른 로컬에 stuck되어버릴 경우가 있을 수 있다. 해결 방법은 간단하다. 많이(약 1000회) 반복하는 것이다.

Run K-means 부분이 위의 K-means 알고리즘 부분이다. 루프 중첩.

중첩 루프를 수행하며 비용 함수 J (cost, distortion func)가 가장 낮은 클러스터링을 선택한다. 이 알고리즘은 클러스터의 개수가 적을 때 더 효과가 좋다. 랜덤으로 100개의 중심점을 찍어 1000번을 돌려본들 사실 그게 그거인데, k가 많이 작을 때에는 많이 돌리면 효과적인 결과가 나온다.

 

3-5. K를 정하는 방법

(1) 자동으로 찾는 가장 좋은 방법은 없기 때문에 보통은 시각화해서 분포 확인해보고 사람이 수동으로manually 정한다.

(2) Elbow Method

그 외에 쓸만한 방법. 어떤 데이터 xi가 클러스터 안 중심점에서 얼마나 떨어져 있는가를 최소화하게끔 하는 Distortion(Optimize, Cost, ex.SSE) 함수를 플라팅해서 elbow를 찾는 것이다. 위 그래프의 경우에는 k=3이 적당하다.