[데이터 분석] 계층적 군집 분석(hierarchical clustering)

계층적 군집 분석(hierarchical clustering)

참고글 : [R 분석] 계층 군집 분석(hierarchical clustering)

            [데이터 분석] K-NN 알고리즘

 군집 분석은 기존 관측치의 Y값(Class)이 없는 데이터의 Clustering 알고리즘입니다.

KNN 알고리즘과 동일한 거리 기반 모델로, 거리가 가까운 관측치들은 비슷한 특징을 가질 것이라는 전체하에 클러스터링을 수행하는 기법입니다. 

차이점이라면, 설명변수를 통한 예측 목적이 아닌 데이터 축소 목적을 가지고 있습니다.

군집 분석에는 계층적인 방법(hierarchical clustering)과 비계층적인 방법(k-means)이 있는데, 순차적으로 그룹을 할당하는지의 여부에 따라 나뉩니다.

계층적인 방법은 가까운 대상끼리 순차적으로 군집을 묶어간다면, 비계층적인 방법은 랜덤하게 군집을 묶어가죠.

계층적 군집 분석의 특징

  1. 거리 계산 

   - 관측치들의 거리 계산은 유클리드 거리 계산식을 이용

   - 거리 기반으로 데이터를 축소(군집)

   - 기존 관측치들간의 모든 거리를 계산 

   - 군집 구성법

      * 최단거리법(single) : 생성된 군집에서 중심과 거리가 가까운 데이터끼리 비교하여 가까운 데이터끼리 군집화 

      * 최장거리법(complete) : 생성된 군집에서 중심과 거리가 먼 데이터끼리 비교하여 가장 가까운 데이터끼리 군집화

      * 평균기준법(average) : 한 군집 안에 속한 모든 데이터와 다른 군집에 속한 모든 데이터의 두 집단에 대한 거리 평균을 계산하여 가까운 데이터끼리 군집화

      * 중앙중심법(median)

2. 데이터의 축소

   - 예측 목적이아닌 데이터 축소 목적의 분석 기법 -> 전체적인 데이터의 구조 파악

   - 전체 집단을 파악하기 어려우므로, 군집으로 나누어 집단을 파악 (A : ~를 좋아한느 집단, B : ~를 싫어하는 집단)

 3. 기타

   - 분석 결과에 대한 가설 검정이 필요 없음(타당한 방법이 없으므로..)

4. 계층적 군집의 생성 과정

    1) 기존 관측치들끼리의 거리 측정

            

    2) 가장 가까운 관측치들을 1번 클러스터로 묶음 -> 클러스터 c1 생성

             

    3) 클러스터 c1과 나머지 관측치들끼리도 거리를 측정 (군집 구성법에 따라 다름)

             

거리기반 모델의 특징 :  KNN 알고리즘과 동일한 특성

 1. 표준화의 필요

  - 표준편차 : 분산에 루트(제곱근, √x)을 씌운 것으로, 분산이 작으면 밀집, 분산이 크면 흩어지는 현상을 보임. Class(그룹)에 따라 그 값의 범위가 각기 다름

      * 같은 범위상에 있더라도 분포에 따라 범위가 달라지므로, 크기의 의미가 달라질 수 있음(거리는 각 설명변수의 범위에 민감) -> 동일 범위더라도 표준화 작업이 필요

         ex) 변수 A의 점수 범위는 1~1000점, 변수 B의 점수 범위는 1~10점일 경우, 1점 차이의 크기가 변수마다 다름, 분포가 다르면 각 변수의 차이를 해석하기 어려움

  - 표준화(Standatd scale) 방법

      * X - Xbar / SE : X에서 평균을 뺀 후, 표준편차로 나누는 방법 (scale 함수 사용, 평균은 0 기준으로 -1 ~ +1 범위)

      ** min-max scale : 최대값은 1, 최소값은 0으로 

 2. 이상치(outlier)에 민감한 반응

  - 이상치(기존 범주에 벗어나 유독 값이 작거나 큰 데이터) 데이터의 제어가 필요

      * 제거 또는 수정(평균, 최소, 최대 값으로)

  - Tree 알고리즘 같은 경우는 설명변수의 중요도 기반으로 동작하기때문에 민감하지 않음

3. 설명변수 민감한 반응

  - 설명변수에 매우 민감 (모델 내 변수 선택 기준이 없기 때문)

  - Tree 알고리즘은 중요도 기반이므로 불필요한 설명변수를 모델에서 사용하지 않지만, KNN 알고리즘은 거리 기반이므로 모든 설명변수를 고려

      * 중요하지 않은 변수가 모델에 추가될 수록 정확도가 낮아짐

  - 중요도가 높은 의미있는 설명변수만 추출하여, 정확성을 높이는 과정이 필요 

   

계층적 군집 분석 과정 예시(평균기준법)

v1 <- c(1,3,6,10,18)

# step 0) 개별 관측치(Object)끼리의 거리 측정

         1   3   6   10

  3     2         

  6     5    3      

10     9    7    4   

18    17  15  12    8

# step 1) 가장 가까운 두 관측치를 묶어 클러스터 생성 => C1(obj1,obj3)

# step 2) 새로 생긴 클러스터 C1과 개별 관측치와의 거리 계산 => C1의 obj1과 obj6 의 거리와 C1의 obj3과 obj6 의 거리의 평균

      -  d(C1, obj6) = d(obj1, obj6)과 d(obj3, obj6)의 평균 -> avg(5,3) = 4

      -  d(C1, obj10) = d(obj1, obj10)과 d(obj3, obj10)의 평균 -> avg(9,7) = 8 

      -  d(C1, obj18) = d(obj1, obj18)과 d(obj3, obj18)의 평균 -> avg(17,15) = 16

     C1   6  10

 6    4      

10   8    4   

18  16  12  8  

# step 3) 클러스터와 관측치의 거리를 모두 고려, 가장 거리가 짧은 관측치를 C1에 포함시키거나 새로운 클러스터 생성

위 결과와 같이 거리가 같을 경우 클러스터로의 포함이 우순순위 => 3번째 관측치(obj6)가 C1에 포함 => C1(obj1,obj3,obj6) 

# step 4) 새로 생기거나 갱신된 클러스터와 개별 관측치와의 거리 계산 

      -  d(C1, obj18) = d(obj1, obj10), d(obj3, obj10), d(obj6, obj10)의 평균 -> avg(9,7,4) = 6.67

      -  d(C1, obj18) = d(obj1, obj18), d(obj3, obj18), d(obj6, obj18)의 평균 -> avg(17,15,12) = 14.67

      C1   10

10  6.7

18  14.7  8  

      => C1 에 obj10이 포함. 만일 obj10, obj18의 거리가 더 가까웠다면 새로운 클러스터 C2가 생성되었을 것임

 

# step 5) 반복적으로 각 거리 계산, 가장 짧은 거리 포함 혹은 새 클러스터 생성 => C1(obj1,obj3,obj6,obj10)