[Data Mining] 12. Clustering - Hierarchical clustering

Clustering (군집)

군집(clustering)은 쉽게 표현하면 전체 데이터를 sub-classes로 쪼개는 기법인데, 이 sub-classes를 clusters라 부른다. 일종의 유사한 패턴을 가지는 데이터를 grouping하는 기법이다. 분류(classification)문제와 유사하게 보이지만 가장 큰 차이점은 label이 없다는 것이다. 예를 들면 독립변수가 있고 종속변수가 불량/정상, 이렇게 label이 있는 것이 아니라, 독립변수만 보고 비슷한 성질을 가지는 데이터끼리 grouping 하는 것이 바로 군집이다.

사실 군집이 잘 이루어졌는지 평가하는게 쉽지가 않다. 왜냐하면 label이 없기 때문에 잘 grouping이 됐는지를 확인하기가 어렵기 때문이다. 그래도 굳이 정성적으로 정의하자면 각 군집은 similarity가 높아야 잘 grouping 되었다고 표현한다. 추후에 이걸 그나마 정량적으로 평가할 방법을 소개하도록 한다.

군집이 갖춰야 할 요건은 대략 아래와 같다.

• Scalability : 문제가 커져도 풀 수 가 있어야 한다.

• attributes도 다양하게(연속형, 범주형) 적용할 수 있어야 한다.

• domain knowledge을 최소한으로 해서 군집을 만들 수 있어야 한다.

• 데이터의 순서에 민감하지 않아야 한다.

• high dimensionality 문제도 해결을 할 수 있어야 한다.

군집을 적용할 수 있는 분야는 아래와 같이 다양하다.

• Marketing : 특정 패턴을 가지는 고객을 군집하여 맞춤형 서비스 제공 

• Insurance : Marketing과 마찬가지로 보험 고객에게도 많이 쓰인다.

• 그 외 : Land use, City-planning, Document clustering...

본격적으로 군집의 원리에 대해 알아보기 전에 Formulation부터 정의하자.

• S = {O1, ... , On}     Oi : xi = (Xi1, ..., Xip)
  : n개의 object가 있고 각 object는 p개의 attribute(=variables)가 있다.

• C = {C1, ..., Ck}
  : 1개의 군집을 Ci로 표현하며 전체 k개 군집의 합집합은 S와 같다.
    그리고 각 군집의 교집합은 없어야 한다.

상세한 내용은 추후에 다루겠지만, 군집 분석을 하기 위한 큰 Step은 아래와 같다.

• 유사성을 측정한다. (주로 거리를 사용한다.)

• 군집 방법을 결정한다. (hierarchical vs. non-hierarchical)

• 군집의 수를 결정한다.

• 결과를 해석한다.

비유사성의 측정 (Distance or Dissimilarity measure)

유사성(Similarity)을 측정한다는 것은 유사하지 않은 정도(Dissimilarity)를 측정함으로써 알 수 있는데, 가장 일반적인 비유사성은 두 sample간의 거리(distance)라 할 수 있다. 즉 거리가 멀면 멀수록 유사성이 떨어진다는 것이다. 일반적으로 유클리디언 거리를 사용한다.

유클리디언 거리 외에도 다양한 측정 방법이 있지만 잘 쓰진 않는다. 아래 몇 가지 Distance Measure가 있는데 참고하도록 하자.

그런데 한가지 의문이 든다. 수치형 데이터 간의 거리는 분명 위와 같은 방법으로 구할 수 있는데, 범주형 데이터간의 거리는 어떻게 구할 수 있을까? 

Binary / Nominal Variables

순서가 없는 binary나 nominal 범주형 변수는는 보통 simple matching으로 유사성을 판단한다. 거창하게 말했지만 Xik와 Xjk가 같으면 sim(Xik, Xij) = 1, 다르면 0으로 보는 것이다. (Jaccard라는 유사한 방법도 있긴하다.)

Ordinal Variables

ordinal은 순서가 있기 때문에 조금 다르지만 그렇게 어렵진 않다. 수식은 아래와 같이 있긴한데, 간단한 예가 더욱 이해가 잘 될 것 같다.

만약 1~5등급의 ordinal variable이 있다고 하자. 그럼 1과 5등급 사이의 전체 거리가 1이라고 했을 때 1-2등급 사이의 거리는 1/4 = 0.25라 할 수 있다. 

Mixed type

※ Rk = max(Xk) - min(Xk)

위에서 언급한 3가지의 경우 모두 거리가 0~1사이의 거리를 갖는다. 그런데 만약 변수들 사이에 연속형(continuous) 범주가 있다면 어떤일이 발생할까. 이 경우, 범주형 변수는 0~1사이의 스케일을 갖는데 연속형 범주가 예를 들어 0~1000사이의 값을 가지면 연속형 범주의 영향도가 너무 커질 수 있다. 그래서 일종의 scaling처럼 0~1사이의 값을 갖도록 위와 같은 수식을 적용할 수 있다.(min-max scaling과 유사) 

※ 이렇게 연속형 변수가 0~1사이의 값을 가지면 마치 ordinal variable과 같이 변환되기 때문에 similarity를 동일하게 측정할 수 있다.

Hierarchical(계층적) Clustering

1. Linkage Method

Hierarchical(계층적) clustering의 개념은 similarity가 높은 sample 혹은 cluster끼리 먼저 묶으면서 계층적으로 군집을 구성하는 것이다. 예를 들어 위 그림에서는 다른 샘플들간의 거리보다 X1-X6, X3-X7 이 가장 가까이 있었던 경우다. 그리고 다음으로 가까이 있는 sample을 군집에 속하게 하거나, 두 군집사이의 거리가 가까우면 하나의 군집으로 합치면서 계층적으로 군집을 이룬다.

위와 같이 군집을 구성하기 위해 Agglomerative(작은 것부터 군집을 이루는 방법) 혹은 Divisive(전체에서 작은 군집을 때어네는 방법)이 있지만 통상 Agglomerative하게 군집을 형성하는 것이 일반적이다. 그리고 clustering 과정을 시각화하기 위해 위 그림과 같이 dendrogram을 유용한 툴로 사용할 수 있다.

여기서 한가지 개념이 추가되는데, 지금까지는 객체(sample, object)간의 거리를 유클리디언 거리로 계산했었다. 그런데 군집분석에서는 군집-객체, 혹은 군집-군집 간의 유사도를 측정할 수 있어야 한다. 그렇기 때문에 두 군집간의 거리라는 개념(Linkage method)이 추가로 필요하다.

두 군집간의 거리를 평가하는 개념은 위와 같이 다양한 종류가 있는데, "어떤 정의를 사용할 것인지"가 군집의 중요한 하이파파라미터 중 하나가 된다. (만능 Linkage라는 것이 없다. = 해 봐야 안다. = Domain knowledge를 가진 사람만이 평가할 수 있다.)

Single linkage method 를 적용한 계층적 군집 예제를 하나 살펴보자.

• 변수가 2개인 표본 5개가 있는 상황이다.
  각 객체를 군집으로 보고, 각 군집간의 distance를 구해서 표 D(Ci, Cj)로 정리해둔다. 
  아직은 두 점간의 거리기 때문에 유클리디언 거리를 사용하였다.
  ※ 참고 : D(Ci, Cj) = 군집간 유사성 척도

• 가장 가까운 거리에있는 두 군집(4, 5)을 합쳐서 1개 군집으로 인식한다. 

• 다음은 (4, 5)를 1개의 군집로 인식하고 다시 D(Ci, Cj)를 구한다.
  이 때 single linkage method를 적용한다.

• 전체가 1개의 군집이 될 때까지 반복하고, 이를 Dendrogram으로 나타내면 위와 같다. 적당한 거리(점선)에서 cut-off 하면 원하는 갯수의 군집을 얻을 수 있다.

위 과정을 크게 나눠보면 아래 3개 step으로 일반화 된다.

• Step. 0 모든 객체를 군집으로 인식한다 (k=n)

• Step. 1 D(Ci, Cj)를 계산한다.

• Step. 2 가장 가까이 있는 두 군집을 하나의 군집으로 만든다. (k←k-1)

• Step. 3 k=1 이 아니라면 Step 1, 2를 반복한다.

※ 교재에는 Average linkage method를 설명하긴 하는데, 두 군집의 거리를 구하는 식만 다를 뿐 모두 동일하기 때문에 예제 설명은 생략한다.

2. Ward's method

linkage method에서는 두 군집간의 거리를 활용해 계층적(Hierarchical)으로 군집을 형성했는데, 거리가 아닌 다른 기준을 세울 수도 있다. Ward's method가 그 중 하나인데, 알고리즘을 설명하기 전에 몇 가지 Formulation을 정의하고 가자.

• SSC : Error sum of squares for cluster Ci
  → 군집 내 모든 객체가 군집의 중심과 얼마나 떨어져 있는가?

• SSW : Total within sum of squares
  → 전체 군집의 SSC 합

위 두가지 Formulation으로 몇 가지 상황을 예측해보자.

Case 1. 군집을 형성하는 중

- Iteration = 0 : 모든 객체가 군집이다. 그 때 SSC와 SSW는 얼마일까?
  정답은 0이다. 객체 스스로가 군집이기 때문에 모든 군집의 SSC=0이기 때문이다.

- Iteration = 1 : 가장 가까운 거리에 있는 2개 군집이 1개의 군집으로 합쳐졌다.
  다른 모든 군집의 SSC=0 이지만, 새롭게 합쳐진 군집은 SSC > 0 이다.
  마찬가지로 SSW도 늘어났을 것이다.

- Iteration = 2 : 기존의 군집이 커졌거나 새로운 군집이 생겼다.
  마찬가지로 SSW가 늘어났을 것이다.

- [결론] 군집을 생성하면 생성할 수록 SSW는 커진다.

Case 2. 군집을 거의 완성해 가는 중

- C1 군집이 C2군집과 합쳐져서 C3군집이 됐다. 즉, 군집의 중심이 변경됐다.
  전체적으로 SSW는 늘어났겠지만 군집의 중심이 어디냐에 따라서 SSW 증가량은 다르다.

- C1 군집이 C2군집보다 더 가까운 C4군집과 합쳐졌다.
  C2군집과 합쳐졌을 때 보다 SSW가 조금 늘어났을 것이다.

- [결론] 군집이 완료 됐을 때 SSW가 작을수록 군집이 잘 된 것이다.

위 케이스를 이해했다면 Ward's method 가 어떤 목적으로 군집을 할 지 예상했을 것이다.

Ward's method는 각 군집간의 거리(Linkage)가 아니라 SSW가 최소가 되도록 군집을 형성하는 방법이다. 아래는 Ward's method 절차를 기술하였는데, Linkage 대신 SSW를 사용하는 것 외에는 모든 절차가 동일하다.

• Step. 0 모든 객체를 군집으로 인식한다 (k=n, SSW = 0)

• Step. 1 2개 군집을 묶어보고 SSW를 확인한다. SSW를 가장 작게하는 조합을 찾아 군집을 형성한다. (k=n-1)

• Step. 3 k=1이 아니라면 위 과정을 반복한다.

Ward's method 예제를 통해 살펴보자.

• 첫 Iteration 때 거리를 계산하는 것이 아니라 SSW를 계산한 후 가장 작은 조합인 (C2+C7)를 첫 군집으로 삼는다.
  ex.SSW({C1, C2}) = (4 - 12)² + (20-12)² + (15-14)² + (13-14)² = 130

• 이 과정을 반복하면서 군집의 수를 하나씩 줄여나간다. (k = 1이 될 때까지)

• k=1 이 될때까지 반복하면 위와 같은 Dendrogram을 그릴 수 있다.
  참고로 위 Dendrogram의 y축은 SSW가 아니라 SSW의 증가분으로 표현되어 있다.

3. Dendrogram을 이용한 군집의 수 k 설정하기

보통 군집분석은 군집의 수 k가 중요한 파라미터지만, 최적의 k를 사전에 예측하는 것은 매우 어렵다. 하지만 계층적(Hierarchical) 군집 모형은 k가 하이퍼파라미터가 아니다. 앞서 원리를 보았듯, 계측정 군집은 모든 샘플이 군집이 될 때까지 작은 군집을 점차적으로 합쳐나간다. 그렇기 때문에 Dendrogram이 도출되며, Dendrogram은 계측적 군집의 특권이다.

다음 챕터에서 다루겠지만 Non-Hierarchical 군집은 사전에 k를 하이퍼파라미터로 지정해줘야 k개의 군집을 만들기 위해 군집을 형성할 수 있다.

반면 계측적 군집에서는 Dendrogram을 이용한다면, 사전에 k를 정할 수는 없지만 군집분석 사후의 분석결과를 보고 적절한 군집의 수를 도출할 수 있다. 예를 들어 위 Dendrogram의 세로축은 군집간의 유클리디언 거리이다. 만약 거리가 약 9인 점선지점에서 군집을 그만두면 3개의 군집을 얻을 수 있다.

방금은 거리(CD : Cluster Distance)를 이용해서 내가 원하는 군집의 갯수를 맞췄다. 하지만 거리 외에도 군집 갯수를 결정하기 위한 척도가 여럿 있다. 아래 그래프를 살펴보자.

위 그래프를 보면 군집의 수가 늘어날수록 증가하는 수치도 있고(RMSSTD, CD(cluster distance), RS(R-square)), 줄어드는 수치(SPR(semipartial R-square))도 있다. 위 수치들을 기준으로 적정 수준에서 군집화를 멈추면 적절한 군집의 수라 할 수 있다. 아래는 각 수치를 계산하는 방법인데 참고 정도만 하자.

[정리]

• 계층적(Hierarchical) 군집은 작은 군집에서 시작해서 단계적으로 큰 군집을 형성하는 방법이다.

• 작은 군집이 큰 군집을 이루기 위해서는 주변 군집과의 거리를 사용할 수 있는데 이런 방법을 Linkage method clustering이라 한다.

• 반면 거리가 아니라 객체가 군집의 중심(centroid)과 최대한 가깝도록, 즉 SSW가 가장 작은 객체와 군집을 이루는 방법을 Ward's method clustering이라 한다.

• 이렇게 작은 군집에서 큰 군집을 향해 단계적으로 진행되기 때문에 dendrogram이라는 툴로 시각화 할 수 있는 특권이 있다.

• dendrogram을 이용하면 내가 원하는 군집의 수를 결정할 수 있는데, dendrogram의 y축에 해당하는 값은 다양하게 있다.