[ Part Ⅱ] Chapter 4. 구매 이력 데이터를 이용한 사용자 그룹 만들기

4.1 군집화

데이터 특징을 이용한 그룹핑 문제에서는 특정 패턴을 정의하여 모델을 만드는 방법보다는 비슷한 데이터를 한데 모으는 방법이 더 효율적이다. 이 방법을 군집화라고 한다. 이 방법은 미리 그룹을 정의하지 않기 때문에 비지도학습에 속한다. 크게 중심 기반 군집화, 계층적 군집화, 밀도 기반 군집화로 나눌 수 있다.

 

군집화의 핵심 아이디어는 비슷한 데이터를 한데 묶는다는 것이다. 비슷하다는 것, 즉 유사도가 높다는 것은 데이터를 이루는 피처값이 비슷하다는 것이다. 각 피처의 총합 ∑_(i=1)^m (x_i-y_i) 가 적을수록 비슷한 사용자라고 할 수 있다.

 

하지만 단순히 차이를 모두 합하면 한 피처에 대해 +가 나오고, 다른 ㅏㅎㄴ 피처에 대해 -가 나오면 두 데이터 사이의 피처가 많이 다름에도 불구하고 전체 합이 0이 될 수 있다. 따라서 단순한 차이 대신 그 차이를 제곱한 값을 더하여 얻어진 값에 루트를 사용한다.

 

d(X,Y)=√(∑_(i=1)^m (x_i-y_i)^2 )=|X-Y|

 

4.2 K-중심 군집화

중심 기반 군집화의 대표적인 예이다. 중심 기반 군집화는 클러스터 중심점을 정한 후 클러스터 중심점에 가까운 데이터들을 모아가며 클러스터를 확장하는 방법이므로 군집화 초기에 몇 개의 중심점을 어떻게 배치하는가가 중요하다. K-중심 군집화는 초기에 K개의 중심점을 랜덤으로 선택하여 군집화를 시작한다. 

1. 임의로 뽑은 K개의 데이터를 중심으로 하는 클러스터를 만든다(각 클러스터가 데이터 하나씩만 가지고 있다).
2. 각 데이터와 클러스터 중심 간의 거리를 계산한다.
3. 데이터와 클러스터 중심 간의 거리가 가장 짧은 클러스터에 데이터를 할당하고 이 데이터를 포함하여 클러스터 중심을 업데이트한다.
4. 과정 2와 3을 반복하는데, 과정 3에서 더 이상 중심의 위치가 변하지 않거나, 업데이트 전후 중심점의 차이가 사용자가 지정한 허용 오차 이내거나, 사용자가 지정한 횟수만큼 반복했으면 종료한다.

 

과정 3에서는 가장 가까운 클러스터에 데이터를 할당하고 있다. K-중심 군집화에서 클러스터는 클러스터 중심으로 정의되므로 결국 데이터와 클러스터 중심 사이의 거리가 가장 짧게 되는 클러스터를 찾는 것이다. 

 

과정 4에서 업데이트가 없으면 군집화를 종료한다고 했는데, 이는 각 데이터가 속한 클러스터가 변하지 않는 것, 즉 수렴하는 것을 의미한다. 하지만 수렴되기까지 상당하나 시간이 걸리므로 실제로는 이전 단계의 총제곱합과 새로 얻은 총제곱합의 차이가 허용오차보다 작거나, 클러스터 중심 업데이트 횟수가 사용자가 지정한 반복 횟수 이상이면 군집화를 종료한다.

 

4.3 계층적 군집화

계층적 군집화에서의 계층은 클러스터의 계층을 의미한다. 최상위 계층의 클러스터는 모든 데이터를 포함하는 하나의 클러스터이다. 최하위 계층의 클러스터는 단 하나의 데이터만을 포함하므로 클러스터 수가 데이터 수와 같게 된다.

 

계층적 군집화에는 하향식인 분할적 군집화와 상향식인 집괴적 군집화가 있다. 사용자가 클러스터 수 K를 명시적으로 지정하는 K-중심 군집화와는 달리 계층적 군집화는 클러스터 수를 지정할 필요가 없다.

 

계층적 군집화는 각 단계마다 한 쌍의 클러스터를 비교하는데, 하향식인 분할적 군집화는 각 계층의 클러스터들을 둘로 쪼개어 하위 계층으로 진행하고, 상향식인 집괴적 군집화는 각 계층의 클러스터들 중에서 가장 가까운 두 개를 하나로 합쳐 상위 계층의 클러스터를 만들어간다.

 

주의할 점은 늘 한 쌍의 클러스터만 비교한다는 것이다. 군집화 전에 클러스터 수가 2^n개가 아니라는 점을 알고 있다면 계층적 군집화보다는 K-중심 군집화를 하는 것이 좋다.

 

K- 중심 군집화에서는 K 값에 따라 군집화의 성능이 달라지는 것과 마찬가지로, 계층적 군집화에서는 클러스터를 어느 정도로 분할 혹은 병합하는가에 다라 군집화의 성능이 달라진다. 계통 트리를 통한 클러스터 생성 과정, 클러스터 안의 데이터 분석 등을 통해 적절한 클러스터를 찾을 수 있다.

 

4.4 밀도 기반 군집화

데이터 밀도가 높아지는 방향으로 데이터를 군집화하는 방식이다. 대표적인 밀도 기반 군집화 알고리즘에는 평균이동 군집화와 DBSCAN_Density-based spatial clustering of applications with noise(디비스캔, 노이즈를 가지는 애플리케이션의 밀도 기반 공간 군집화)이 있다.

 

데이터셋 안의 모든 데이터를 군집화하는 K-중심 군집화나 계층적 군집화와는 달리 밀도 기반 군집화는 예외 데이터를 정의하고 군집화 과정에서 그것을 제외시킨다. 또한 클러스터 중심과 데이터 사이의 거리를 이용하는 K-중심 군집화와 계층적 군집화의 경우 중심으로부터의 같은 거리 안에 있는 모든 점이 같은 클러스터에 속하게 되므로 클러스터가 원형이 될 수밖에 없다. 이와 달리 밀도 기반 군집화는 클러스터 모양이 제한이 없다.

 

4.5 유사도 계산

유사도가 클수록 거리가 줄어들기 때문에 거리가 가깝다는 것은 유사도가 크다는 것이고 거리가 멀다는 것은 유사도가 작다는 것이다.

 

** 민코스키 거리

d(X,Y)=√(p&∑_(i=1)^m |x_i-y_i|^p)

p가 1일 때는 맨해튼 거리(혹은 L1 거리), 2일 때는 유클리드 거리(혹은 L2 거리)라고 한다.

 

출처:https://m.blog.naver.com/samsjang/220980080522

맨해튼 거리는 거리 계산 시 제약이 있을 때 유용하다. 반면 유클리드 거리는 두 점 사이의 최소 거리를 제약 없이 구할 때 사용한다.

 

** 마할라노비스 거리

두 점 사이의 거리를 계산할 때 데이터의 분포를 고려하는 거리이다. 

 

두 좌표축의 단위가 다른 경우에는 각 축 간의 공분산을 고려하는 게 좋다. 공분산이란 두 변수가 얼마나 연관성이 있는지 나타내는 값이다. 공분산의 값이 1이면 한 변수가 증가할 때 다른 변수도 증가하는 것이고, -1이면 한 변수가 증가할 때 다른 변수가 감소하는 것이다. 0이면 두 변수 간에 아무런 상관관계가 없다. 

 

d(x,y)=√((x_i-y_i )^T S^(-1) (x_i-y_i))

S는 공분산행렬이다.

공분산행렬은 정의로 인해 늘 정방행렬이고 대칭행렬이다.

 

유클리드 거리는 마할라노비스 거리에서 공분산행렬이 단위행렬인 특수한 경우이다.