K-평균 알고리즘(K-Means)
1. 데이터는 생각보다 많은 것을 보여준다
데이터는 생각보다 많은 이야기를 담고 있습니다. 아래는 두 메신저의 주 접속시간대와 사용자가 머무르는 시간을 나타내는 그래프입니다. 두 메신저의 사용자를 각각 분류해볼까요? 어떻게 나눌 수 있을까요?
어때요? 생각이랑 비슷한가요?
그럼 이렇게 생각해봅시다. 위의 것들을 그룹1이라고 하고 아래를 그룹2라고 해 봅시다.
두 메신저의 사용 용도는 어떤 것일까요? 추측해봅시다.
추측컨대 그룹1은 주로 업무시간대에 사용이 몰려 있는 것으로 보아 업무용 메신저일 것입니다. 밤에는 사용자가 낮보다 현저히 적네요. 이제부터 그룹1은 [타라그래] 메신저로 명명하죠. 그룹2는 아침부터 저녁까지 꾸준히 사용되고, 저녁시간대에 조금 더 쓰는 모습입니다. 일반사용자가 친목이나 대화를 위해 사용하는 메신저로 보입니다. 이제부터 이건 코코아톡이라고 하죠. 어때요, 추측이 그럴싸 한가요? 이렇게 가까운 데이터들을 분류해보는 일을 군집화(Clustering)이라고 합니다. 아래처럼 바꿔볼 수 있습니다.
군집화란?
군집화는 데이터에 대한 정보가 없을 때 비슷한 집단으로 묶는 방법입니다. 즉 Label(이름표)이 없는 데이터를 군집(cluster) 단위로 나누는 것으로 비지도 학습(Unsupervised learning)의 일종입니다. 각 데이터의 이름표(label)이 있는 데이터를 분류하는 지도학습(Supervised learning)과는 반대의 개념입니다.
2. 군집화를(Clustering) 하는 이유는?
그렇다면 K-Means와 같은 방법을 이용하여 군집화를 하는 이유는 무엇일까요?
그 이유는 바로 데이터에서 의미를 찾아내기 위함입니다. 그리고 의미를 찾으면 이 의미는 다양하게 사용할 수 있습니다.
가장 많이 사용되는 곳은 마케팅(홍보) 부분입니다. 사용자들의 특성을 파악해서 더욱 더 좋은 서비스를 제공하고 이윤을 창출할 수 있습니다.
만약 마트에서 식빵을 산 사람이 다음에 갈 곳은 어디일 확률이 높을까요?
정답은 알 수 없음입니다. 한 명의 고객이 어디로 갈지는 아무도 모르는 일이죠.
하지만 여러 사용자가 모이면 달라집니다. 이 마트에서 옷 코너에서 대부분이 운동복을 사는 사람이라면 어떨까요? 그렇다면 대부분이 달걀을 사러 가지 않을까요? 그럼 마트의 담당자는 아마 바나나와 달걀을 가까이에 배치해서 사람들에게 편리함을 줄 수 있겠죠. 아니면 반대로 멀리 배치해서 그 사이에 몸에 좋은 상품들을 잔뜩 진열해 구미가 당기게 할 수 도 있을 겁니다.
최종 선택은 인간이 하겠지만, 이에 도움을 줄 수 있는 방법이 군집화 인 것이죠.
K-Means는 이러한 군집화 방법 중의 일종입니다. 앞의 타라그래와 코코아톡은 비교적 간단한 데이터들이 있었지만, 만약 수만개, 수십만개의 데이터가 있다면 저렇게 단순히 나눌 수 없겠죠?
그리고 명확하게 데이터가 눈에 보일 정도로 나눠지지도 않겠죠.
클러스터링을 하는 비지도학습의 종류에는 K-Means, 선형 회귀, SVM, 결정 트리 등 전혀 추측할 수 없는 것들이 가득합니다. 그러나 모두 군집화를 한다는 점에서 같은 비지도학습입니다. K-Means는 그중에서 가장 기본이 되는 내용입니다. 알고리즘을 알아볼까요?
비슷한 이미지를 추출하는데 사용할 수 있다. (O/X)
학생에 따라 어려워하는 부분을 분석할 수 있다. (O/X)
마케팅 회사의 고객층을 분석할 수 있다. (O/X)
3. K-Means 알고리즘
이제 K-Means 알고리즘을 알아보도록 합시다. 먼저 K-Means에서 K와 Means의 뜻은 무엇일까요?
K는 중심점의 개수입니다. 즉 몇 개로 나눌 것인지 알아보는 것이죠.
Means는 평균, 중심이라는 뜻입니다.
즉 이를 합쳐보면 K를 중심(means)으로 모이는 것을 의미합니다.
어떻게 이뤄지는 지 하나씩 살펴볼까요? 다시 한번 데이터를 시각화(visualization)을 통해 2차원 그래프로 나타내봅시다.
앞의 타라그래와 코코아톡의 사용자를 조금 줄여보았습니다. 이제 여기서 K가 2인 K-Means를 실행해보겠습니다.
1단계에서 K는 기본적으로 무작위로 위치를 정합니다.
그리고 각 데이터를 가까운 K점에 연결합니다. 이를 Expectation 이라고 합니다.
각 거리의 합을 구해봅니다(제곱의 합). 그리고 합이 나오면 계산을 수행하여 거리들의 합이 가장 작은 방향으로 K 값을 이동합니다. 이 과정을 Maximazation이라고 합니다.
이를 계속 반복합니다. 그럼 더 이상 값이 작아지지 않아 K이 움직이지 않을때까지 반복하다가 멈추면 K의 최종 위치가 결정됩니다.
최종적으로 K의 위치와 이와 연결된 각 데이터들이 군집을 형성합니다.
점이 세개일때도 마찬가지입니다. K-Means는 이렇게 쉬운 알고리즘과 간단한 계산으로 대규모 데이터에도 적용할 수 있는 장점이 있습니다. 또한 주어진 자료에 대한 정보가 많이 없더라도 군집화가 가능합니다.
4. K-Means 알고리즘의 단점
K-Means도 단점이 있습니다. 그래서 현재는 이를 보완하는 더 복잡한 방법들이 있습니다. 무엇이 있을까요?
첫번째로는 K의 초기 위치 선정입니다. 다음과 같은 경우를 보죠. K가 운좋게 잘 맞은 경우와 운이 좋지 않은 경우입니다. 첫번째의 경우 몇 단계 안에 계산이 끝나고 군집도 비교적 정확할 확률이 높습니다. 하지만 두번째 케이스의 경우에는 계산도 오래 걸릴 뿐더러 잘못 군집될 가능성이 있습니다.
이 경우에는 초기 K값을 무작위로 정하는 것이 아니라 K 위치를 정할 때 한번 무작위로 데이터를 선택하여 그 중심에 위치한 상태로 시작하기도 합니다.
또 데이터가 아주 많을 때, K의 개수를 직접 정해주어야 합니다. 컴퓨터가 알아서 K 값을 정해주지는 않는거죠.
어차피 어떤 데이터인지 모르는 상태에서 몇 개로 나눌 것인지 사람도 쉽게 정하지 못합니다.
마찬가지로 실제 군집이 4개인데 사용자가 3개로 인식하고 k를 3으로 설정하면 의미있는 데이터를 얻기 어렵습니다.
따라서 사람이 여러 번 실험을 하고, 이에 따라 결과값을 직접 해석하여 통찰력(insight)를 직접 알아내야 합니다.
이 외에도 값들의 거리가 한쪽으로 쏠려있고 이상값(outlier)들이 멀리 떨어져있을 때 거리를 기준으로 계산하다 보니 실제 점이 오른쪽에 있기보다 왼쪽에 치우칠 가능성이 있습니다.
