[기계학습심화] 8. K-Means

K-Means

지금까지는 지도학습의 예시로 대표적인 회귀와 분류 모델의 학습 알고리즘을 정리하였다.

이번 글에서는 비지도학습의 예시로 K-Means 를 정리해본다.

 

K-means는 라벨링이 되어있지 않은 데이터들을 비슷한 특징을 가진 데이터들끼리 묶어서 라벨링하는 '클러스터링' 에 사용하는 알고리즘이다. 이때 k는 클러스터의 개수를 가리키는 하이퍼파라미터이다.

K-means는 클러스터링 알고리즘으로 굉장히 간단하고 유명하면서 또 강력하다.

 

 

 

K-Means 는 라벨이 없는 비지도학습 알고리즘이므로, K-Means 알고리즘을 적용하면 그제서야 데이터들이 어떤 클러스터에 속해있는지 라벨이 생기게 된다.

 

클러스터링은 이미지에 적용해서 비슷한 rgb 값을 갖고 있는 픽셀들끼리 분류할 수도 있고,

의류회사의 경우 사람들의 체형 데이터를 내가 원하는 사이즈의 종류만큼 분류해서 각 사이즈 종류마다 가로/세로/너비 길이를 각 클러스터의 평균으로 활용하는 등의 방법으로 사용할 수 있다.

 

 

알고리즘

k-means 알고리즘은 간단하다.

 

1. 랜덤하게 k개의 점을 찍는다. 이 점은 각 클러스터의 중심점으로서 centroid 라고 부른다.

2. 모든 데이터에 대해 각 centroid 와 거리를 재서 더 가까운 centroid 쪽으로 분류하여 k개의 클러스터를 구성한다.

3. 각 클러스터마다 해당 클러스터에 속한 데이터들의 좌표값을 평균내서 새로운 centroid 를 구한다.

4. centroid 가 변하지 않을 때까지 2~3번 과정을 계속 반복한다.

 

(1번 에서 랜덤하게 점을 찍을 때 한쪽 점이 전체 데이터와 너무 멀리 떨어져있으면 2번 단계에서 모든 데이터가 1개의 클러스터로 몰리면서 멈추는 경우도 생긴다. 이를 방지하기 위해 1번에서 랜덤으로 점을 찍을 때 데이터 중에서 k개를 고르도록 할 수도 있다.)

 

 

 

이 알고리즘을 수식으로 나타내면 위와 같다.

xi 는 i번째 데이터를 말하고, bj 는 j번째 centroid 를 말한다.

wij 는 가중치로서 이 가중치 값을 곱해서 다 더하는데, 이때 그 합을 최소로 만드는 w를 찾는 것이 목표이다.

그리고 모든 j에 대해 특정 j값을 갖는 wij 의 합은 1이 되어야 한다.

 

예를 들어 k = 2 일 때, w11 ||x1 - b1|| + w12 || x1 - b2 || 식에서 w11 + w12 = 1 이 되어야 한다.

x1 - b1 의 거리가 3이고, x1 - b2 의 거리가 5일 때, w11, w12 조합은 어떻게 해야 최소가 될까?

w11 = 1, w12 = 0 이어야 위 수식값이 3이 되면서 최소가 된다.

즉, 사실상 제일 거리가 가까운 점 1개에만 wij 가 1이 되고 나머지 wij 에는 0이 들어가게 된다.

그리고 그때의 j 값이 이 데이터가 속할 클러스터의 번호가 된다.

 

그런데 k-means 에서는 w 값과 b 값이 계속 바뀐다. (센트로이드도 바뀌니까)

이렇게 2개의 값이 동시에 변할 때 어떻게 최적의 w, b 값을 찾을 수 있을까?

이 경우에도 gradient decent 를 사용할 수 있고, 간단하게는 기존 알고리즘과 비슷하게 w 를 고정하고 b 에 대해서 최적화를 하고, 그 다음에는 b 를 고정하고 w 를 최적화하고, .. 를 반복해서 (w, b) 조합의 최적값을 찾을 수 있다.

 

 

그리고 k-means 에서 centroid 와 거리를 계산할 때 L2 norm 을 사용했는데, L2 norm 은 평균과 관련이 있다.

(x-3)^2 + (x-5)^2 의 최소값이 되는 x의 값은 직관적으로 4 라는 것을 알 수 있고, 4는 3과 5의 평균이기 때문이다.

(이 식을 x로 미분한 뒤에, 0과 같다고 방정식을 놓고 풀면 평균이 나온다.)

이 x에 벡터를 적용해도 동일하게 나오며, b1, b2, ... 의 평균값을 넣으면 제일 작은 값이 나온다.

 

참고로 L1-norm 은 그 의미가 median 값과 관련이 있다.

예를 들어 |x-1| + |x-3| + |x-7| 의 값을 최소로 만들고 싶다고 해보자. 이때는 1 3 7 의 중간값인 3을 넣으면 최소가 나온다.

7 대신에 100을 넣어도 중간값인 3을 넣는 것이 최소가 된다.

(|x-1| + |x-3| + |x-100| 에서 100의 중간인 50을 넣으면 49 + 47 + 50 = 146, 3을 넣으면 2 + 0 + 97 = 99 가 나온다.)

마찬가지로 x 대신에 벡터를 넣으면 b1, b2, ... 의 중간값을 갖는 벡터를 넣을 때 최소가 나온다.

 

k-means 에서 다음 centroid 를 결정할 때 거리를 구해서 평균을 내는데, 이때 l2 norm 대신 l1 norm 을 사용해도 된다.

그러면 그 의미는 그 클러스터들을 쭉 정렬했을 때 중간값을 사용하는 것과 같은 효과를 가진다.

 

 

또한 K-Means 는 각 클러스터에 대한 경계선을 그었을 때 그 경계선이 직선으로 나온다.

거리를 기준으로 클러스터를 구분짓기 때문에 직선과 점 사이의 거리를 기준으로 나누는 것과 같기 때문이다.

 

활용

 

K-Means 는 이렇게 이미지를 세그멘테이션 하는데 사용할 수도 있다. (위 경우엔 rgb 픽셀 값을 기준으로 클러스터링)

그리고 세그멘테이션을 나눈 뒤, 배경을 지우고 싶다고 하면 1번 클러스터만 지우면 배경을 지울 수 있다.

 

 

또는 원본 이미지를 k개 종류의 색을 가지고 표현하고 싶을 때 클러스터링을 통해 표현할 수 있다.

k = 2 일 때는 흑/백 2가지 색으로 표현한 것이고, k = 20 일때는 20 종류의 색상으로만 원본 이미지를 표현한 것이다.

k 값이 늘어나면 점점 원본과 비슷한 퀄리티로 그려질 것이다.

 

 

또는 MRI 이미지에 대해 세그멘테이션을 나눠서 특정 크기 이상의 병변이 존재하는지도 볼 수 있다.

이렇게 K-Means 는 꽤 강력하고 자주 사용되는 알고리즘이다. (최근에도 관련 논문들이 나온다고 한다.)

 

하이퍼파라미터 튜닝

k-means 에서도 knn과 마찬가지로 k값이 하이퍼파라미터이다.

그렇다면 어떤 k값이 가장 좋은지 어떻게 찾아낼 수 있을까?

 

k-means 에서 하이퍼파라미터를 튜닝할 때는 knn과 달리 validation / test 셋을 나눌 수가 없다.

k-means 는 정답이 없는 비지도학습이기 때문이다.

 

그래서 비지도학습에서는 휴리스틱한 방법을 사용해서 최적의 하이퍼파라미터를 찾는다.

대표적인 방법으로 elbow 기법이 있다.

elbow 기법은 클러스터링이 끝나면 각각의 점들을 최종적으로 자신이 속한 클러스터의 centroid 와 모든 거리를 다 재서 더한다.

이 거리를 (에러는 아니지만 제곱 오차와 비슷하게) loss 구하듯 다 더한 값을 sum of squared error (SSE) 라고 부르는데, 이 값을 k = 1 일때부터 k 값을 늘려나가면서 구해본다.

 

 

 

그러면 위와 같이 그래프가 그려지는데,

이 그래프에서 제일 급격하게 꺾이는 구간을 최적의 k값으로 본다.

(이유는 없다.. 굳이 따지면 k 값이 증가할 수록 점점 에러가 감소하는데, 뒤로 갈수록 k값을 늘리는 것에 비해 에러가 별로 안 줄어들게 되어서 k를 늘리는 의미가 줄어든다. 그렇게 가다가 k 가 데이터의 숫자만큼 늘어나면 sse = 0 이 되니 그때의 k값은 의미가 없다. 그래서 그 중간 어딘가를 찾다가 제일 감소폭이 큰 쪽을 고른 것이다.)

따라서 위 경우에서는 k = 3 일 때가 최적이다.

 

 

장점과 단점

장점

- 알고리즘이 간단하고 계산이 빠르다.

- 성능도 간단한 것에 비해 꽤 괜찮다.

 

단점

- k값을 찾는 것이 힘들다.

 

- 초기값에 민감하다.

 

처음에 랜덤으로 막 찍었는데, 어떻게 찍느냐에 따라 성능이 다르게 나온다.

(= local minimum 이 많아서 초기값에 따라 다른 local minimum을 가리키게 된다.)

이건 실용적인 관점에서 꽤 치명적인 단점이다.

예를 들면 의료 분야에서는 정확도가 매우 중요한데 초기값에 따라서 모델 성능이 왔다갔다 하니 신뢰하기 힘들 것이다.

 

- outlier에 민감하다.

 

결국 모든 점과 평균을 내기 때문에 모든 점이 모델의 성능에 영향을 주므로, outlier가 저 멀리 뚝 떨어져 찍혀있으면 그만큼 제곱 거리가 크게 잡혀서 centroid 가 outlier 쪽으로 이동하게 되어 전체 성능이 크게 영향을 받는다.

또한 l2 norm 도 모두 평균과 관련이 있다보니 평균 자체가 outlier 에 영향을 잘 받는 편이다.

 

위 그림에서 k-means를 사용한 왼쪽은 outlier들을 하나의 클러스터로 분류해서 나머지 그룹을 전혀 클러스터링 하지 못한다.

그래서 l2 대신 중앙값과 관련이 있는 l1 norm 을 사용하여 메디안 값을 활용한 오른쪽 그림과 같은 모델을 활용할 수도 있다.

(이 방법을 가리켜 k-medoids 라고 하며, l1 norm 은 outlier에 강한 모습을 보여준다.)

 

 

 

 

또한 k-means 는 거리를 구하는 특성상 경계선이 linear 하게 나올 수 밖에 없다.

만약 non-linear 하게 경계선을 나눠 클러스터링 하고 싶다면 kernel method 를 사용해주면 된다.

(데이터를 한 차원 끌어올려서 k-means 적용)