군집분석 #3

    지금까지는 군집 분석이란 무엇이고 왜 필요한지, 군집 분석을 할 때 고려해야 할 것들은 무엇인지 등에 대해 알아 보았습니다. 또한 군집 분석을 할 때 꼭 필요한 유사도 (혹은 거리)를 측정하는 방법에 대해서 다양한 방법들을 소개했습니다. 이번 편에서는 이렇게 측정된 유사도를 바탕으로 서로 유사한 개체끼리 그룹을 묶기 위한 군집화 알고리즘에 대해서 소개하려고 합니다.

    군집 분석 방법은 매우 다양하며 저마다의 강점과 한계점이 있습니다. 따라서 군집 분석을 하고자 하는 데이터의 특징이나 형태에 따라 적절한 방법을 사용해야 합니다. 이 글에서는 이 중에서 대표적인 알고리즘 몇 가지를 소개하고 각 알고리즘의 특징 및 장/단점, 어떤 상황에서 사용해야 하는지 등을 설명하겠습니다.

k-평균 알고리즘 (k-means algorithm)

    상당수의 군집 분석 관련 자료에서 가장 먼저 소개되는 대표적인 알고리즘입니다. 이 알고리즘이 가장 널리 사용되는 이유는 알고리즘이 직관적이고 쉬우면서도 평균적으로 괜찮은 결과가 나오기 때문이죠. k 평균 알고리즘은 말 그대로 k 개의 평균값(중심점)을 이용해서 군집을 만드는 방식입니다. 알고리즘의 동작 방식은 다음과 같습니다. 

    1) 최초에 임의의 점 k 개를 중심점으로 지정합니다.

    2) 각 데이터를 k 개의 점과 비교하여 가장 가까운 점이 있는 쪽으로 분류합니다.

    3) 모든 데이터를 k개 그룹으로 분류하고 나면, 각 그룹의 중심점을 계산합니다.

    4) 이전 단계에서 계산한 k 개의 중심점을 이용해서 2), 3) 단계를 반복합니다. 이 때 3)단계에서 갱신한 k개의 중심점이 이전 과정에서 사용한 중심점들과 차이가 없거나 미리 정한 수준 이하로만 변하면 과정을 종료합니다.

k-means 알고리즘을 이용해서 전체 데이터를 3개 그룹으로 군집화하는 예

    참고로 k 평균 알고리즘을 사용할 때 분석가는 전체 데이터를 몇 개의 그룹으로 묶을 것인지를 나타내는 k값을 명시적으로 지정해줘야 합니다. 어떤 자료에서는 이것을 k 평균 알고리즘의 단점으로 꼽는 경우가 있는데 이것은 잘못된 설명입니다. 뒤에서 다른 알고리즘들을 설명할 때 보면 아시겠지만 대부분의 군집화 알고리즘은 군집을 만들기 위한 몇 가지 파라미터들을 분석가가 명시적으로 지정해 줘야 합니다. 이런 파라미터 설정이 없이 모든 것을 자동으로 지정해 주는 알고리즘은 제가 아는 한 없습니다. 

    그럼 이 k 값은 어떻게 정해야 할까요? 이에 대해서는 뒤에서 따로 설명하겠습니다.

k 평균 알고리즘의 주요 특징

    k 평균 알고리즘의 주요 특징은 다음과 같습니다.

    첫째, 좌표 기반의 군집 분석 방법입니다. 위 그림에서 보다시피 개체들을 좌표 상의 점으로 표현한 후 각 점들의 거리를 기반으로 군집을 묶는 방법입니다. 따라서 2편에서 소개했던 좌표 기반의 거리 측정 방식을 사용할 수 있는 데이터에 대해서만 이 방법을 사용할 수 있습니다. 

    둘째, 대용량 데이터 처리에 유리합니다. k 평균 알고리즘은 분산 처리에 매우 유리한 알고리즘입니다. 아주 단순하게 보자면 k개 그룹에 대한 거리 측정이나 중심점 갱신 등의 작업은 k개의 시스템으로 분산하여 계산할 수 있죠. 또한 전체 계산량이 그리 많지 않기 때문에 대용량 데이터에 대한 군집 분석에 좋습니다.

    셋째, 각 유형의 특징을 파악하기 좋습니다. 군집 분석을 하는 주요 목적 중 하나는 전체 데이터를 유형별로 분류하여 특징을 파악하는 탐사 분석이나 고객 세그먼테이션을 통한 서비스 관리입니다. 이런 경우 군집 분석 결과로 나온 각 유형이 어떤 특징을 갖는지 파악하는 것이 중요합니다. k 평균 알고리즘은 각 유형을 나눌 때 사용한 k개의 중심점이 곧 해당 유형의 대표값이기 때문에 각 유형의 특징을 파악하기 쉽습니다.

k 평균 알고리즘의 한계점

    k 평균 알고리즘은 많은 장점을 갖고 있는 반면 다음과 같은 한계점 및 주의할 점도 갖고 있습니다.

    첫째, 아웃라이어에 민감합니다. 아웃라이어가 있는 경우 이런 극단값에 의해 전체 평균이 영향을 받는 평균의 특성 상 k 평균 알고리즘 역시 극단값에 의해 중심점이 왜곡되기 쉽습니다. 따라서 이런 문제를 완화하기 위해 평균 대신 중앙값을 이용하는 k-median 알고리즘이 대안으로 사용되기도 합니다. 

아웃라이어로 인해 평균이 왜곡되는 예

    둘째, 유형별 '데이터의 분산이 비슷하고 구형(공모양)으로 분포되어 있는 경우'가 아니라면 부적절한 결과를 낼 수 있습니다. 아래 세 개의 그림은 각각 다른 특징을 갖는 데이터들에 대해 k 평균 알고리즘을 적용한 결과입니다. 보다시피 가장 왼쪽 그림처럼 각 유형이 비슷한 분포를 갖는 경우에는 직관과 일치하는 결과를 보이지만, 가운데와 오른쪽의 경우 의도와 다른 결과가 나옵니다.  

다양한 분포의 데이터들에 대한 k 평균 알고리즘 결과

    위 그림에서 두번째 예시의 경우를 보면, 크게 네 개의 유형 (웃는 얼굴의 테두리, 양쪽 눈 모양, 입 모양) 으로 분류가 되는 것이 적절해 보이지만 k 평균 알고리즘 결과를 보면 전체를 크게 네 등분으로 나눈 결과가 나옵니다. 그 이유는 앞서 설명했듯이 이 알고리즘은 전체 유형이 동일한 분산과 분포를 갖는다고 가정하기 때문입니다. 그러나 보다시피 이 데이터는 각 유형이 분산도 다르고 분포의 형태도 다릅니다. 따라서 이런 경우 k 평균 알고리즘은 좋은 선택이 아닙니다. 

    세번째 예시의 경우엔 아마도 가운데 가장 큰 구형 데이터, 왼쪽 상단의 작은 구형, 오른쪽 상단의 작은 구형 데이터로 유형이 나뉘는 것이 더 좋겠지만 역시 의도와 다른 결과가 나옵니다. 이 경우엔 비록 각 유형의 데이터들이 모두 구형이긴 하지만 분산이 다르기 때문에 그렇습니다.

    결국 이렇게 각 유형의 분산이 다르거나 분포의 형태가 다른 데이터의 경우 k 평균 알고리즘 대신 다른 방법을 사용하는 것이 좋습니다. 그럼 먼저 두번째 예시부터 대안을 살펴 보죠.

밀도 기반 클러스터링 (DBSCAN)

    두번째로 소개할 기법은 밀도 기반 클러스터링입니다. 이 방법은 말 그대로 개체들의 밀도를 계산하여 촘촘하게 분포되어 있는 개체들끼리 그룹을 묶는 방식을 사용합니다. 이를 위해 이 알고리즘에서는 두 개의 파라미터를 정해주는데, 하나는 밀도를 계산할 범위(epsilon)이고 또 하나는 하나의 그룹으로 묶는데 필요한 최소 개체수(minPts)입니다. 알고리즘의 동작 방식은 다음과 같습니다.

    (a) 먼저 임의의 점 p에서 epsilon 만큼의 범위 (그림에서 원으로 표시된 범위) 내에 포함된 점들의 개수가 minPts 이상이면 점 p를 중심으로한 클러스터를 형성합니다. 

    (b) p와 같은 클러스터에 있는 다른 점 q를 중심으로 하는 epsilon 만큼의 범위를 다시 잡아 해당 범위 내에 minPts 이상의 개체가 포함되어 있으면 이 범위 내 개체들을 (a)와 같은 그룹으로 묶습니다.

    (c) 만약 (b) 과정에서 더 이상 그룹에 포함할 개체가 없으면 해당 클러스터가 아닌 다른 점을 중심으로 (a), (b) 과정을 반복합니다. 

    (c) 만약 점 r를 중심으로 epsilon 범위 내에 minPts 이상의 개체가 존재하지 않으면, r은 아웃라이어로 처리합니다.

밀도 기반 클러스터링의 동작 방식

    밀도 기반 클러스터링 알고리즘은 유사한 개체들을 계속 연결하여 하나의 군집으로 묶는 방식이기 때문에 k 평균 알고리즘처럼 데이터의 분포가 구형이고 분산이 일정해야 한다는 제약이 없습니다. 또한 몇 개의 그룹을 묶을 것인지 미리 지정하지 않고 하나의 군집으로 묶을 최소한의 밀도만 지정해 주면 알아서 군집을 묶어 줍니다. 따라서 아래 그림처럼 다양한 형태의 분포에 대해서도 그룹을 묶을 수 있으며, 다른 개체들과 상대적으로 멀리 떨어져 있는 아웃라이어들을 군집에서 제외할 수 있는 장점이 있습니다.

DBSCAN 알고리즘을 이용해서 군집 분석을 한 예

    반면 각 유형 사이 공간의 데이터 밀도가 충분히 낮지 않다면, 다시 말해 각 유형 간의 경계가 모호하다면 군집 분석이 잘 안되는 한계를 갖고 있습니다. 예를 들어 k 평균 알고리즘의 한계점을 설명할 때 소개한 세번째 그림의 경우 세 개의 유형 사이에 경계가 불분명하기 때문에 DBSCAN을 이용하더라도 유형을 잘 묶지 못합니다.

    따라서 아래 그림과 같이 그냥 하나의 유형으로 묶이거나 혹은 너무 유형이 세밀하게 쪼개지는 문제가 발생할 수 있습니다.

DBSCAN은 각 유형 사이의 밀도 차가 뚜렷하지 않은 경우엔 잘 작동하지 않습니다.

    위와 같이 각 유형 사이의 밀도 차가 뚜렷하지 않은 경우라면 데이터 분포의 차이를 이용한 군집 분석 방법을 시도해 볼 수 있습니다.

확률 분포 기반 클러스터링 (Gaussian Mixture Model)

    가우시안 혼합 모델은 전체 데이터의 확률 분포가 여러 개의 가우시안 분포의 조합으로 이뤄져 있다고 가정하고 각 분포에 속할 확률이 높은 데이터끼리 군집을 묶는 방법입니다. 가령 분석할 데이터의 분포가 아래 그림과 같다면 이 데이터는 두 개의 정규 분포가 결합된 형태라고 생각할 수 있습니다. 그러면 각 데이터가 정규 분포 상으로 볼 때 둘 중 어떤 분포에 속할 확률이 더 높은지를 계산하여 군집을 나누는 것이죠.

가우시안 혼합 모델 - 데이터를 여러 개의 가우시안 확률 분포의 조합으로 표현하여 군집을 나누는 기법

    이 방법을 이용하면 k 평균 알고리즘이나 DBSCAN 알고리즘으로는 그룹을 잘 묶을 수 없었던 아래 데이터도 군집을 잘 묶을 수 있습니다.

    가우시안 혼합 모델은 k평균 알고리즘처럼 각 유형의 중심(평균)을 중심으로 유형을 표현하면서도 DBSCAN처럼 각 유형별 데이터의 분산이 일정하지 않더라도 유형을 잘 묶을 수 있는 장점을 갖고 있어 유용한 방법입니다. 

    물론 가우시안 혼합 모델도 만능은 아닙니다. 이 기법은 데이터가 정규 분포의 조합으로 표현된다는 가정 하에 분석하는 방식이기 때문에 아래 그림과 같이 이 가정에 어긋나는 데이터라면 클러스터링이 부적절하게 될 수 있습니다. 또한 이 기법은 계산량이 많기 때문에 대량의 데이터에 사용하기에는 적절하지 않습니다. 

GMM도 만능은 아닙니다.

계층 클러스터링

    위에서 소개한 세 가지 알고리즘은 데이터들의 분포나 평균을 측정할 수 있는 경우에만 사용할 수 있습니다. 그러나 실제 데이터 중에서는 이런 것들을 측정할 수 없는 경우도 있습니다. 대표적인 것이 텍스트 데이터입니다. 가령 아래와 같은 세 개의 문장이 있다고 하죠.

    1) 아버지가 방에 들어가신다.

    2) 어머니가 방에 들어가신다.

    3) 나는 바둑이와 산책을 나갔다. 

    앞서 소개한 문자열 매칭 알고리즘을 이용한다면 문장 간의 유사도를 측정하는 것은 가능합니다. 따라서 이를 통해 우리는 1)과 2) 사이의 유사도가 3) 보다 더 가깝다는 것을 알 수 있습니다. 그러나 1)과 2)의 평균 혹은 2)와 3)의 평균을 측정할 수는 없습니다. 또한 위 세 문장의 적절한 확률 분포나 공분산 역시 구할 수 없습니다. 

    이처럼 데이터 각 쌍에 대해서는 유사도를 측정할 수 있지만 집단에 대한 평균이나 분산 등을 구할 수 없는 경우에는 위 세 개의 알고리즘은 이용할 수 없습니다. 반면 계층 클러스터링은 이런 경우에도 사용할 수 있는 기법입니다. 

군집 내 개체들의 중심점을 구할 수 없는 데이터 예시

    계층 클러스터링은 개체 간의 모든 쌍에 대해서 먼저 유사도를 구한 후 유사도가 높은 개체들부터 여러 단계의 계층 구조를 생성해 나가면서 군집을 구성하는 기법입니다. 앞서 예로 든 문장 데이터들이 있는 경우 2편에서 소개한 문자열 매칭 알고리즘을 이용해서 문장 간의 유사도를 측정합니다. 이후 가장 유사도가 높은 개체쌍끼리 먼저 그룹을 묶어서 가장 하위 단계의 계층을 만든 후 각 그룹 간의 유사도를 측정하여 다시 유사도가 높은 군집쌍끼리 상위 그룹을 묶어 나가면서 점차 상위 계층을 형성해 나갑니다. 이렇게 하면 결국 모든 군집이 최상위 계층에서 하나도 묶이게 되는데 이 상태에서 몇번째 단계에서 군집을 나눌지 정하여 최종적으로 그룹을 분류하는 방식입니다. 아래 그림은 방금 설명한 내용을 도식화한 것입니다.

계층 클러스터링 예시

     계층 클러스터링은 중심점을 구할 수 없는 시퀀스 데이터에 대해서도 군집을 묶을 수 있는 장점이 있는 반면, 모든 쌍에 대해서 반복적으로 유사도를 구해야 하기 때문에 계산량이 매우 많은 단점이 있습니다. 

중간 정리 #3

    지금까지 소개한 군집 분석 알고리즘들의 특징 및 장/단점을 간략하게 정리하면 아래 표와 같습니다. 다만 알고리즘의 장/단점은 상대적인 비교를 위한 내용일 뿐 엄밀한 정보는 아닙니다. 

    물론 이 외에도 다양한 군집 알고리즘이 있으며 역시 제각기 다른 특성 및 장/단점을 갖고 있습니다. 그렇다면 어떤 방법을 사용하는 것이 좋은지 어떻게 판단할 수 있을까요? 우선 중요한 것은 군집 분석의 목적과 사용되는 데이터의 특성을 파악하는 것입니다. 만약 데이터가 수백 만개의 대규모 데이터인데 서버 한 대에서 처리해야 하다면 GMM이나 계층 클러스터링은 거의 사용할 수 없습니다. 또한 앞서 예로 든 문장 간의 유사도를 측정하는 경우라면 평균을 구하는 방식인 k 평균이나 GMM은 사용할 수 없죠.

    그렇다면 이렇게 제약 조건이 불명확한 경우에는 어떻게 해야 할까요? 또한 이런 대부분의 군집 알고리즘들은 군집 개수와 같은 하이퍼 파라미터를 분석가가 직접 지정해 줘야 하는데 어떤 값이 좋은지는 어떻게 판단해야 할까요? 다음 편에서는 실제 군집 분석을 할 때 고려해야 할 점들에 대해 소개하겠습니다.