[기계 학습] Mean Shift 클러스터링

클러스터링(clustering)은 사람의 간섭 없이 컴퓨터가 스스로 유사한 값들을 묶어서 덩어리를 찾아내는 작업을 뜻합니다. 사람이 분류 체계를 미리 만들어주어야 하는 분류(classification)과는 유사하지만 지도(supervise) 여부에서 차이가 나지요. D차원의 유클리드 공간 상의 점들 N개를 클러스러팅하는 데에 가장 사용되는 대표적인 알고리즘에는 K-means Clustering이 있습니다. 이 알고리즘은 전체 N개의 데이터를 K개의 클러스터로 빠르게 묶어낸다는 장점이 있습니다만, 클러스터의 개수 K가 사전에 결정되어야 하고, 초기 중심점(Centroid) 설정에 따라 수렴 여부가 크게 좌우된다는 한계가 있습니다. 반면, 시간이 좀 더 걸리더라도 데이터에 따라 적절한 클러스터 개수를 발견하여 클러스터링해야할 경우에는 비모수 기법을 사용해야 합니다. 대표적인 비모수 클러스터링 기법에는 평균점 이동(Mean-shift) 클러스터링이 있는데요, 이번 포스팅에서는 Mean Shift 클러스터링 알고리즘에 대해서 알아보도록 하겠습니다.

연속 분포를 클러스터링하기

데이터의 밀도가 다음과 같은 경우를 생각해봅시다.

-2 부근과 +2 부근에서 밀도가 매우 높은 걸 볼수가 있죠. 이 데이터를 자연스럽게 나눠야한다면 어떻게 나누실건가요? 저라면 두 꼭대기 사이에 있는 최하점(0.5 주변쯤이 되려나요)을 기준으로 왼쪽과 오른쪽 둘로 나눌 것 같네요. 이렇게 나누는 데에는 이견이 별로 없을 겁니다. 왜냐하면 주어진 데이터 내에는 2종류의 흔한 데이터(-2 부근의 점들과 +2부근의 점들)가 존재하는데, 이걸 둘로 잘 나누었기 때문이죠. 좀더 수학적으로는 이 분포에는 두 종류의 최빈값(mode)이 있는데, 이 mode를 기준으로 전체 데이터를 분할했기 때문이라고 말할 수 있습니다. 여기서 최빈값(mode)이라 하면, 분포에서 꼭대기를 이루는 점이라 생각하면 되겠습니다. 연속분포에서는 꼭대기를 알기가 쉽습니다. 곡선을 따라올라가다가 상승이 멈추는 지점을 찾으면 되니깐요. 그런데 이산 분포를 이루는 데이터에서 mode를 찾기는 생각보다 어렵습니다.

이산 데이터의 밀도는?

그런데 이산 데이터에서는 밀도를 구해서 그 mode를 찾는게 어렵습니다. 한국 성인의 키 분포를 알아서 그 밀도를 추정하여 클러스터링하려고 한다고 생각해봅시다. 길을 다니면서 사람들을 만나서 키를 재어서 다음과 같은 데이터를 얻었다고 생각해봅시다.

170.1, 165.6, 169.9, 171.3, 164.5, 150.5, 151.6, 158.2, 149.5, 152.2

총 10개의 점이 있는 셈인데, 겹치는 점은 단 하나도 없습니다. 따라서 이 데이터를 바탕으로하면 mode는 총 10개 됩니다. (혹은 mode가 없다고 볼수도 있습니다.) 그런데 일의 자리에서 반올림해서 데이터를 다듬어 보면

170, 170, 170, 170, 160, 150, 150, 160, 150, 150

이 되고, 170이 4개, 160이 2개, 150이 4개이므로 이 경우 mode는 170과 150이 됩니다. 그리고 이를 바탕으로 한국 성인의 키가 145~155일 확률이 40%, 155~165일 확률이 20%, 165~175일 확률이 40%라고 추정도 가능하지요. 이렇게 이산 데이터들을 적당히 구간을 나누어 그 갯수를 세어 전체 분포를 보는 방식을 히스토그램(Histogram)이라고 합니다.

 

 

히스토그램은 이산 데이터의 분포를 추정하는 가장 손쉬운 방법입니다. 그런데 그만큼 한계도 명확합니다. 일단 폭(bandwidth)을 어떻게 정할지에 따라 전체 분포의 모양이 크게 달라집니다. 위의 그래프는 폭이 10인 경우의 모양이며, 폭을 2로 설정하고 같은 데이터의 히스토그램을 그리면 아래와 같습니다.

또한 히스토그램의 경우 경계가 불연속이며 고차원의 데이터에 대해 희소한 결과(데이터가 없는 빈공간을 너무 많이 만들어냄)를 보여줍니다. 희소성을 해소하기 위해 폭을 크게 잡으면 전체 분포를 제대로 볼수 없으며, 반대로 폭을 작게 잡으면 분포를 좀더 명확하게 볼수 있지만, 빈 칸이 너무 많아집니다. 

그래서 등장하는 방법이 커널 밀도 추정(Kernel Density Estimation)입니다. 이 기법의 기본 아이디어를 풀어 설명하자면, 관찰된 데이터들을 경계가 명확한 점으로 보는 것이 아니라 경계가 흐리멍텅한 안개로 보자는 것입니다. 즉, 170.1이라는 점이 관찰되었을 경우, 우리 실제 데이터 내에는 딱 170.1이 1개만 있고, 170.0이나 170.05은 0개가 있는게 맞습니다. 하지만, 그렇게 빡빡하게 굴지말고 조금 관대하게 봐줘서, 정답을 완벽하게 맞추지 못했더라도 부분점수를 주는것마냥, 170.0은 0.1개쯤, 170.05는 0.2개쯤, 170.1은 0.5개쯤 있다고 봐주자는 것이지요. 즉, 이렇게 관대하게 봐줄 경우 어떤 수치를 들이밀어도 그 값이 우리 데이터 내에 몇개가 있는지를 계산해줄 수 있습니다. 이 계산방법을 수학에서는 커널(Kernel)이라고 합니다.

대표적인 커널 함수로 가우시안 함수(Gaussian)가 있습니다. 이 함수는 다음과 같은 모양(정규 분포에서 흔히 보던 그것)을 띕니다.

가우시안 커널의 경우 위와 같은 수식을 따라서 계산이 되는데, 여기서 u는 원 데이터로부터의 거리가 됩니다. 즉, 원데이터인 170.1로부터 거리가 0인경우 그 데이터는 K(0) ≒ 0.39개 정도 있다고 봐주게 되는 것이고, 169.1인 경우 떨어진 거리가 1이므로 K(1) ≒ 0.24개 정도 있다고 부분점수를 준다는 것이죠. 커널을 적용하여 데이터의 분포를 그리려면 다음처럼 계산합니다.

여기서 x_i는 각각의 데이터가 되며 h는 얼마나 관대하게 봐줄지를 설정하는 폭(bandwidth, 대역폭) 파라미터입니다.

위의 데이터에 가우시안 커널을 적용하여 h=1로 그리면 다음과 같이 됩니다.

 

그리고 h를 바꾸면 관대함을 조절할 수 있습니다. 원 데이터와의 거리가 u인 경우 K(u)만큼의 데이터가 있다고 쳐주기로 했었는데, 이 비율을 조절해볼수 있겠죠. h=2로 둘 경우 원 데이터와의 거리가 u만큼 떨어져 있으면 K(u/2)만큼 부분점수를 주게 됩니다. h가 커질수록 더 완만한 분포를 보이게 되고, 반대로 h가 작을수록 더 뾰족뾰족한 분포를 보이게 됩니다. 예를 들어 h=2.3으로 할 경우 아래와 같은 모양이 됩니다.

Mean Shift로 클러스터링을 해보자

이제서야 본론입니다. 지금까지는 커널에 대해 제대로 이해하지 못한 제 자신을 위한 복습시간이었습니다. 서두에 언급한 Mean Shift에 대한 설명은 여기서부터 시작됩니다. Mean Shift는 한국어로는 평균점 이동이라고 번역하는데, 기본적인 아이디어는 각 점들에 대해 데이터의 분포에서 mode를 찾아 이동하다보면 점들이 적당하게 모일것이라는 것입니다.

가우시안 커널로 밀도를 추정한 그래프에 실제 데이터들 10개를 점으로 찍어보았습니다. 이 점들 각각에 대해서 주변의 밀도를 계산해서 밀도가 높은쪽으로 조금씩 이동시킨다고 해봅시다.

각 점들의 이동을 화살표로 표현하면 위와 같이 될겁니다. 조금씩 조금씩 움직이다 보면 처음 10개의 점들은 몇 개의 점으로 모이게 될겁니다. 위 예시의 경우 왼쪽의 4개는 왼쪽 정상으로 모이게 될 것이고, 오른쪽 5개의 경우 오른쪽 정상에, 가운데 158지점에 있는 점은 혼자 남아 총 3개의 클러스터가 생성될 겁니다. 이것이 Mean Shift 클러스터링 알고리즘의 기본적인 아이디어입니다. 그림으로는 간단하지만, 실제로는 위와 같이 연속적인 분포가 주어지지는 않고 점들만 주어지기 때문에 이를 계산하려면 조금 노력을 해야합니다. Mean Shift에서는 각 지점을 중심으로하는 커널을 적용하여 새로운 평균을 구하는 식으로 mode를 향해 올라가는 방향을 찾고자 합니다.

정확히는 위와 같은 식을 통해서 mode를 향하는 방향을 찾습니다. 여기서 x_i는 위와 마찬가지로 각각의 데이터가 되며 , h는 bandwidth의 크기, c는 현재 점의 지점, c^~는 새로운 점의 지점입니다. 일례로 149.5라는 점을 시작 지점이라고 생각해봅시다. 이 위치에서 위 식을 따라 h=2.3으로 가우시안 커널 함수를 계산해서 가중 평균을 구해봅시다.

최초의 c는 149.5입니다. 계산하면 다음과 같이 되지요.

$x_i$	$K\left(\frac{x_i - c}{h}\right)$	$K\left(\frac{x_i - c}{h}\right) \cdot x_i$
149.5	0.3989	59.6419
150.5	0.2583	38.8708
151.6	0.0586	8.8899
152.2	0.0168	2.5515
158.2	0.0000	0.0000
164.5	0.0000	0.0000
165.6	0.0000	0.0000
169.9	0.0000	0.0000
170.1	0.0000	0.0000
171.3	0.0000	0.0000
SUM	0.7326	109.9540

따라서 새로운 c는 109.9540 / 0.7326 = 150.1가 됩니다. 이제 이 c를 기준으로 다시 똑같은 계산을 반복해볼까요?

$x_i$	$K\left(\frac{x_i - c}{h}\right)$	$K\left(\frac{x_i - c}{h}\right) \cdot x_i$
149.5	0.3411	51.0005
150.5	0.3721	56.0060
151.6	0.1500	22.7382
152.2	0.0586	8.9251
158.2	0.0000	0.0000
164.5	0.0000	0.0000
165.6	0.0000	0.0000
169.9	0.0000	0.0000
170.1	0.0000	0.0000
171.3	0.0000	0.0000
SUM	0.9219	138.6698

이제 새로운 c는 138.6698 / 0.9219 = 150.4 입니다. 여기서 또 계산을 반복해볼까요?

$x_i$	$K\left(\frac{x_i - c}{h}\right)$	$K\left(\frac{x_i - c}{h}\right) \cdot x_i$
149.5	0.2805	41.9376
150.5	0.3972	59.7803
151.6	0.2133	32.3373
152.2	0.0975	14.8435
158.2	0.0000	0.0000
164.5	0.0000	0.0000
165.6	0.0000	0.0000
169.9	0.0000	0.0000
170.1	0.0000	0.0000
171.3	0.0000	0.0000
SUM	0.9886	148.8987

다시 새로운 c는 148.8987 / 0.9886 = 150.6 입니다. 이렇게 계속 c를 계산하는 것을 반복하면 그 값은 151.1에서 151.2사이를 벗어나지 않고 c값이 수렴하게 됩니다. 즉 이 지점이 149.5에서 출발했을때 오르게 되는 최종적인 정상지점이 됩니다. 지금은 149.5의 경우만 계산했지만, 나머지 점들에 대해서도 똑같이 계산을 수행하면 그 점들이 오르게 되는 정상지점도 결정됩니다. 정상지점이 동일한 점들의 경우는 동일한 클러스터로 묶을 수 있겠죠. 각 점들에 대해서 그 점들의 최종 도착지를 정리해보면 다음과 같습니다.

최초의 c	최종 c	클러스터 번호
149.5	151.16	0번
150.5	151.16	0번
151.6	151.16	0번
152.2	151.16	0번
158.2	158.2	1번
164.5	165.05	2번
165.6	165.05	2번
169.9	170.34	3번
170.1	170.34	3번
171.3	170.34	3번

이렇게 10개의 점은 총 4개의 클러스터로 묶이게 되었습니다. 물론 이 결과는 bandwidth의 크기인 h값에 따라서 크게 달라질 수 있습니다. 사실 이 값을 잘 정하는게 k-means clustering에서 k값을 잘 정하는 것만큼 중요하고 어려운 문제이긴 합니다. 그러나 k-means의 k값에 비해 h값은 폭이라는 물리적인 의미를 가지고 있으며, 주어진 데이터에 대해 적절한 h값을 자동으로 구하는 방법이 제안되어 있기도 합니다. 

이렇게 보면 굉장히 좋은 방법인데 생각보다 널리 쓰이지는 못합니다. 그 이유는 데이터가 늘어날 수록 연산량이 제곱에 비례해서 급증하기 때문입니다. 즉, 각각의 점에 대해 새로운 c를 계산하기 위해서는 모든 점에 대한 커널 함수의 가중 평균을 구해야하기 때문에 시간복잡도가 O(N^2)가 됩니다. 클러스터링의 개수를 K로 설정했을 경우 K-means clustering은 O(N*K)의 시간복잡도를 가지는데, 일반적으로 K는 N보다 크게 작기 때문에 k-means clustering이 훨씬 빠르게 수행될 수 있습니다. 따라서 Mean Shift 클러스터링을 사용하기에 적합한 상황은 1. 데이터가 과도하게 많지 않으며, 2. 그 분포를 예측할 수 없어 얼만큼의 클러스터가 나올지 알수 없을 때 라고 정리할 수 있습니다.

생각해보기

데이터의 개수 N이 매우 큰 경우 Mean Shift 클러스터링을 사용하려면 어떻게 해야할까요? 만약 데이터가 오밀조밀하게 모여 있다면 미리 k-means 클러스터링을 적용해 볼 수 있겠습니다. K를 적당히 잡고 먼저 k-means 클러스터링을 몇 번 돌리면 전체 데이터에서 K개의 중심점이 발견될 것입니다. 그리고 이 k개의 중심점에 대해서만 Mean Shift를 적용하면 어떨까요? 그러면 최종적으로 N개의 데이터에 대해 가중 평균을 계산하는게 아니라 K개의 중심점에 대해서만 가중평균을 계산하면 되므로 O(N*K)번의 연산으로 Mean Shift를 수행할 수 있을 겁니다. 단 이 경우 발견되는 클러스터링의 개수는 K개 이하로 한정될 수 밖에 없죠. 그러나 클러스터링은 수많은 데이터에서 큼지막한 군집을 발견하는게 목표이므로 N이 백만, 천만개를 넘는다고 해도 K값은 수백이면 충분할 수 있습니다. 따라서 널널하게 K를 천으로 잡아도 큰 속도 향상이 있을 겁니다.

그리고 사실 커널 함수를 꼭 가우시안으로 안 잡아도 됩니다. 실제로 Mean Shift를 사용할때 데이터가 충분하다면 가우시안 커널 대신에, 거리가 h보다 작은 경우 1을, 그 외의 점들에 대해서는 0을 돌려주는 단순한 binary 분류 함수를 사용하기도 합니다. 이 경우 가우시안 커널보다 훨씬 빠르게 연산이 가능합니다.

관련 링크

https://en.wikipedia.org/wiki/Mean_shift

https://spin.atomicobject.com/2015/05/26/mean-shift-clustering/

https://darkpgmr.tistory.com/147