군집화(Clustering)

부천대 IOT 응용소프트웨어를 수강하는 학생들을 위해 강의내용을 정리했습니다. 강의내용은 모두 파이썬 머신러닝 완벽 가이드를 참고하였습니다.

군집화의 개념

학생시절 사물함을 사용했던 경험을 회상해보자. 사물함에 물건을 둘 때 책들은 가장 뒷편에, 자주사용하는 필기구는 맨 앞으로, 잘 사용하지 않은 문구류는 뒷편에 배치했을 것이다. 이처럼 군집화도 비슷하다. 아래 군집화 개념에 대해 알아보자.

데이터 포인트들을 별개의 군집으로 그룹화하는 것을 말한다.
유사성이 높은 데이터들을 동일한 그룹으로 분류하고, 서로 다른 군집들이 상이성을 가지도록 그룹화한다.

군집화 활용분야

군집화는 특히 세분화(Segmentation)에서 활용된다.

E-commerce에서 500만명의 이상 확보한 온라인 쇼핑몰이 고객을 특정유형으로 분류하여 맞춤서비스를 제공하고, 마케터들이 알지 못했던 새로운 고객유형을 군집화로 발견하여 마켓팅 전략에 활용될 수 있다.

예를들면 판교지역에서 감성시집을 많이 구매하는 것처럼 특정지역에서의 특정제품을 구매하는 고객을 발견하여 이를 콘텐츠 전략에 사용하면 마케팅 효과를 얻을 수 있다.

이외에 이미지, 영상 분야에서 트랙킹(tracking)에서 활용이 가능하고, 제조분야, 물류등에서 이상검출(Abnomaly detection)에 활용된다.

그렇다면 데이터들간 어떻게 유사성을 정의할 수 있을까?

군집화는 알고리즘 사용유무에 따라 유사성이 다르다.

군집화 알고리즘

K-Means (Centroid)
K-Medoids
Mean Shift (Centroid)
Gaussian Mixture Model (정규분포)
DBSCAN (밀도)

위에 소개된 알고리즘에 대해 알아보겠다.

K-Means Clustering

군집 중심점(Centroid) 기반의클러스터링 중 하나인 K-Means는 일반적으로 가장 쉽고 많이 사용되는 알고리즘이다. K-Means Clustering의 동작방식에 대해 알아보겠다.

A,B,C,D,E,F 와 같이 5개의 데이터 세트가 주어지고 2개의 군집을 형성시키고 싶다.

이때 아래 왼쪽 그림과 같이 먼저 임의의 2개 검은점 Centroid를 만든다.

각 A,B,C,D,E 데이터는 2개의 Centroid와의 거리를 확인한 다음, 가까운 Centroid에 소속이 된다.

소속이 결정되면 각 데이터의 중심 공간으로 Centrod들이 이동한다.

다시 A,B,C,D,E 데이터들은 각 Centroid와 거리를 계산하여 가까운 Centroid에 소속이 된다.(3번째그림)

그랬더니 C데이터는 전과 다르게 다른 Centroid에 소속이 된것을 확인할 수 있다.(4번째 그림)

각 Centroid는 다시 자신의 속한 데이터들의 중심으로 이동하게 되고, 더이상 각 데이터들이 Centroid 소속이 변경되지 않는다면 종료된다.

K-Means Clustering 장/단점

장점

일반적으로 가장 많이 활용되는 알고리즘으로 가장 쉽고 간결하다.

대용량 데이터에서도 활용이 가능하다.

단점

거리기반 알고리즘으로 속성 갯수가 많으면 군집화 정확도가 떨어져, PCA로 차원축소를 진행할 수 있다.

반복횟수가 많아질 경우 수행시간이 느려지고, 이상치(outlier)에 민감하다.

군집평가 - 실루엣 분석

대부분 클러스터링을 사용하는 데이터셋은 label 값이 없는 경우가 많다.

그렇다면 군집평가는 어떻게 해야될까?

군집화의 대표적인 평가방법인 실루엣 분석에 대해 소개하겠다.

실루엣 분석은 각 군집 간의 거리가 얼마나 효율적으로 분리 돼있는지를 나타내는 방법으로, 개별 데이터가 가지는 군집화 지표인 실루엣 계수(Silhouette Coefficient)를 기반으로 한다.

'효율적으로 잘 분리 됐다'는 말은 다른 군집과의 거리는 멀어져 있고 동일 군집끼리의 데이터는 서로 가깝게 있다는 의미다. 군집화가 잘 될 수록 개별 군집은 비슷한 정도의 여유공간을 가지고 떨어져 있을 것이다.

그림을 활용해 실루엣 계수를 구하는 방법에 대해 설명하겠다.

특정 데이터 포인트의 실루엣 계수 값은 해당 데이터 포인트와 같은 군집 내에 있는 다른 데이터 포인트와의 거리를 평균한 값 a(i), 해당 데이터 포인트가 속하지 않은 군집 중 가장 가까운 군집과의 평균 거리 b(i)를 기반으로 계산된다. 두 군집 간의 거리 값은 b(i) - a(i) 이며 이 값을 정규화 하기 위해 Max(a(i),b(i)) 값으로 나눈다. 따라서 i 번째 데이터 포인트의 실루엣 계수 값 s(i) 는 위의 식으로 정의할 수 다.

정규화를 통해 알게된 실루엣 계수는 -1 에서 1사이의 값을 가지며, 1로 가까워 질수록 근처의 군집과 더 멀리 떨어져 있다는 것이고, 0에 가까울 수록 근처의 군집과 가까워졌음을 알 수 있다.

좋은 군집화가 되려면 다음조건을 충족되어야 한다.

전체 실루엣 계수의 평균값, 즉 사이킷런읜 silhouette_score() 값은 0~1 사이의 값을 가지며, 1에 가까울 수록 좋다.
전체 실루엣 계수의 평균값과 더불어 개별 군집의 평균값의 편차가 작아야한다. 즉 개별 군집의 실루엣 계수 평균값이 전체 실루엣 계수의 평균값에서 크게 벗어나지 않는 것이 중요하다. 만약 전체 실루엣 계수의 평균값은 높지만, 특정 군집의 실루엣 계수 평균값만 유난히 높고 다른 군집들의 실루엣 계수 평균값은 낮으면 좋은 군집화가 아니다.

주의할 점으로 실루엣 분석은 대용량 데이터에서 실행시간이 오래걸리는 문제가 있다.

Mean Shift

평균점 이동이라 부르는 Mean Shift는 확률 밀도 함수를 추정하는 대표적인 방법인 KDE(Kernel Density Estimation)을 이용하여 데이터 포인트들이 데이터 분포가 높은곳으로 이동하면서 군집화를 수행하는 기법이다. 확률밀도 함수 PDF(Probability Density Function)는 확률 변수의 분포를 나타내는 함수로, 정규분포 함수를 포함해 감마분포, t-분포 등이 있다.

K-Means와 달리 별도로 군집화 갯수를 지정하지 않고, 데이터 분포도에 기반하여 군집화 개수를 정한다. 그래서 대역폭 크기를 어떤 값으로 설정하는가에 따라 군집화의 품질이 결정된다.

Means Shift 수행절차

개별 데이터의 특정 반경 내에 주변 데이터를 포함해 데이터 분포를 계산한다. 이때 데이터 분포도가 높은 (데이터들 간의 거리값을 Kernel 함수값으로 입력하면 확률밀도가 높은 쪽)방향으로 중심점을 이동한다. 다시 이동된 데이터를 기반으로 특정반경 내의 데이터 분포도가 높은곳으로 이동하면서, 특정 데이터 포인트가 더이상 이동하지 않을 때까지 수행한다.

확률밀도 추정방법

데이터는 어떤 변수가 가질 수 있는 다양한 가능성 중 하나인 현실 세계에서 구체화된 값이다. 그리고 우리는 이렇게 관측된 데이터들을 통해 그 변수(random variable)가 가지고 있는 본질적인 특성을 파악하고자 노력한다. 그러나 하나의 데이터는 변수의 일면에 불과하기 때문에 변수의 진면목을 파악하기 위해서는 많은 수의 데이터가 필요하다[5].

(관측된)데이터들의 분포로부터 원래 변수의 (확률)분포 특성을 추정하고자 하는것이 밀도 추정(Density estimation)이다. 확률밀도 추정방법으로 크게 모수적 추정방법(parametric)방법과 비모수 추정방법(non-parametric)방법으로 구분 가능하다.

첫 번째 모수적 추정방법은 특정 데이터분포를 따른다는 가정하에 데이터 분포를 찾는방법이다. 대표적으로 Gaussian Mixture가 있다. 하지만 현실에서는 이렇게 모델이 미리 주어지는 경우가 많지 않고 분포의 모델을 미리 안다는 것이 너무 어려운 가정이 될 수 있다.

두번째 비모수 추정방법은 데이터가 특정분포를 따르지 않는다는 가정하에 밀도를 추정한다.오직 관측된 데이터만으로 확률 밀도를 추정하는 방법으로서 히스토그램(histogram), KDE가 있다.

밀도추정의 가장 간단한 형태인 히스토그램 binary의 경계에서 불연속성이 나타나고 binary의 크기 및 시작위치에 따라 히스토그램이 달라지며, 고차원(high-dim) 데이터에는 메모리 문제등으로 인해 사용하기 힘들다. 밀도추정 방법 중 하나인 커널밀도추정(KDE)은 커널함수(kernel function)를 이용해 히스토그램 문제점을 개선했다.

KDE는 개별 관측 데이터에 커널 함수를 적용한 뒤, 커널함 적용한 값을 모두 더한 후, 개별 관측 데이터 개수로 나눠 확률 밀도함수를 추정한다. KDE는 아래식과 같이 커널함수 식으로 표현이 된다.

h는 커널(kernel) 함수의 bandwidth 파라미터로서 커널이 뽀족한 형태(h가 작은 값)인지 완만한 형태(h가 큰 값)인지를 조절하는 파라미터이다. 수식적으로 보면 어렵지만 이를 직관적으로 이해하면 다음과 같다.

커널함수의 대표적으로 가우시안이 있는데 가우시안을 적용한 커널함수 KDE는 아래식으로 변하게 된다.

이때 Xi는 관측값들로부터의 평균을 말하고, bandwidth h는 표준편차와 동일하다.

표준편차가 작으면 뾰족한 종모양의 데이터분포를 이뤄져 있을 것이고, 표준편차가 크면 완만한 종모양의 분포를 이룰 것이다. 가우시안 커널함수를 적용할 경우 최적의 bandwidth는 다음과 같다.

(n은 샘플 데이터의 개수, σ는 샘플 데이터의 표준편차를 말한다.)

그래서 bandwidth에 따른 KDE 곡선의 모양은 아래 그림과 같이 바뀔 수 있다.

왼쪽그림부터 설명을 하면 bandwidth가 1인 경우, 좁고 뾰족한 KDE를 가지게 되는데, 개별데이터 특성을 잘 받아들여 과적합(over-fitting)이 일어나기 쉽다. 하지만 bandwidth를 너무 키우면 평활화된(smoothing) KDE로 인해 단순화가 되어 과소적합(under-fitting) 문제가 생길 수 있다. 따라서 적절한 KDE 대역폭인 bandwith를 계산하는것이 중요하다.

따라서 정리하면 일반적으로 Mean shift는 대역폭이 클수록 평활화된 KDE로 적은 수의 군집 중심점을 가지게 되고, 대역폭이 적을수록 많은 수의 군집 중심점을 가진다. Mean Shift는 군집 갯수가 정해져 있지 않으며, 오직 대역폭 크기에 따라 군집화를 수행한다.