ADsP 3과목 5-5 군집분석 | 정리📝

데이터 간 유사도/비유사도를 평가하여 데이터를 특정 개수의 군집으로 분할하는 기법
군집의 개수나 구조에 대한 가정 없이 다변량 데이터로부터 거리 기준에 의한 자발적 군집화를 유도함

• 비지도 학습으로 사전 정보 없이 자료를 유사한 대상끼리 묶음
• 다변량 분석(상관분석, 회귀분석, 주성분 분석 등)을 활용하여 각 군집에 대한 특징을 파악함
  군집분석에 이용되는 다변량 자료는 별도의 반응변수가 필요 없음
  • 상관분석: 경향과 관계의 정도를 알아보는 분석 (인과관계, 분산을 알 수 없음)
• 개체를 분류하기 위한 명확한 기준이 존재하지 않거나 기준이 밝혀지지 않은 상태에서 유용함
• 군집분석은 하위군집 내 동질성 / 하위군집 간 이질성을 만족
• 군집화의 방법에는 분리 군집, 밀도 기반 군집 등이 있음
• 실루엣 계수(silhouette coefficient): 군집분석 품질 평가의 기준으로 군집의 밀집 정도를 계산함
  군집 내의 거리, 군집 간의 거리를 기준으로 분할 성과 평가
  응집도, 분리도가 커지며 완변학 분리일 경우 1의 값을 가짐
  • 데이터 응집도(cohesion)
  • 군집간 분리도(separation)
• 군집 분리 안정성 검토: 교차타당성 이용
  교차타당성: 두 집단으로 나눠 각각 군집분석 후 합쳐서 원래 군집분석과 비슷한지 비교하는 방법
• 군집 분리 논리성 검토: 군집 간 변동의 크기 차이 검토
  군집 분리에 대해 안정성도 중요하지만 해당 군집에 대한 분리가 논리적으로 설명되는 부분이 더 중요함

  

 

군집분석 거리 계산
데이터 간 거리를 계산하여 유사성을 측정하고 이를 근거로 군집 판단

• 수치형(연속형) 변수
  • 유클리디안(Euclidean) (통계적 특성 고려 X)
    두 점을 잇는 가장 짧은 직선 거리
    공통으로 점수를 매긴 항목의 거리를 통해 판단함
    $\sqrt{ \displaystyle\sum_{j=1}(x_j-y_j)^2\ }$
  • 표준화 거리(Statistical Distance)
  • 마할라노비스(Mahalanobis) (통계적 특성 고려 O)
    변수의 표준오차, 산포, 변수 간 상관성까지 고려하여 표준화한 거리
    • 표준화 거리 + 상관성 고려
    • 표본공분산으로 나눠주어야
    • 각 변수를 표준편차로 바꾸고 유클리드 거리를 계산하는 표준화를 통해 왜곡 줄어듦
      $\sqrt{(x-y)^T\ S^{-1}(x-y)}$
  • 체비셰프(Chebychev)
  • 맨하탄(Manhattan)
    각 방향의 직각 이동 거리의 합
    $\displaystyle\sum_{j}|x_j-y_j|$
  • 캔버라(Canberra)
  • 민코우스키(Minkowski) (유클리디안 + 맨하탄)
    $(\ \displaystyle\sum_{j}|x_j-y_j|^m\ )^{1/m}$
• 범주형 변수
  • 자카드
    boolean 속성으로 이루어진 두 객체 간 유사도 측정
    $1-J(A,B)=\frac{(|A \cup B|-|A\cap B|)}{|A \cup B|}$
  • 코사인 (문서 간 유사도 계산할 때 많이 사용)
    $1-\frac{A\cdotp B}{\lVert A\rVert_2 \cdotp \lVert B\rVert_2 }$

 

계층적 군집분석

데이터 간 계층적 구조 및 관계를 트리 형태로 표현

n개의 군집으로 시작해 점차 군집의 개수를 줄여가는 방법

군집의 개수를 미리 정하지 않아도 되어 탐색적 분석에 사용함

동일한 거리 계산법을 적용하면 몇 번을 시행해도 결과가 동일함

 

형성방법은 병합적 방법과 분할적 방법이 있음

• 합병형 방식(bottom up)
  데이터를 각각 군집으로 보고 유사한 데이터끼리 군집화해 나가는 방식
  군집 N개 → $\cdot\cdot\cdot$ → 군집 1개
• 분리형 방식(top down)
  합병형 방식과 반대
  모든 데이터를 단일 군집에 속한다고 정의하고 시작하는 방법으로 상위 군집에서 잘못된 결정을 하면 하위 군집에 파급되는 정도가 크다는 단점이 있음
• 최단 연결법(single linkage method) → 군집 나누는 문제는 평면에 점 찍어서 풀기
  다른 군집에 속한 가장 가까운 관측값 간의 거리를 군집 간의 거리로 측정하는 방식
  • 사슬 모양 군집이 생길 수 있음
  • 고립된 군집을 찾는데 중점을 둔 방법
• 최장 연결법(complete linkage)
  다른 군집에 속한 가장 먼 관측값 간의 거리를 군집 간의 거리로 측정하는 방식
• 평균 연결법(average linkage)
  다른 군집에 속한 관측값 쌍들의 모든 거리를 계산하고 이의 평균값을 군집 간 거리로 측정하는 방식
• 중심 연결법(centroid linkage)
  각 군집의 중심위치 간의 거리를 군집 간 거리로 측정하는 방식
• 와드 연결법(Ward Linkage)
  • 각 군집의 분산을 고려하여 거리를 계산
  • 군집을 합치면서 군집 내 변동이 최소화되도록 설계
    병합 후 오차제곱합의 증가 정도가 작아짐
  • 계산량이 많음
    군집 내 편차들의 제곱합을 고려해 군집 간 정보 손실을 최소화 하는 방향으로 군집 형성
• 군집화
  덴드로그램을 통해 적절한 군집 수 선정

  

  가로선을 그어 군집을 자르고 그 위를 군집 수로 함

 

 

비계층적 군집분석
계층적으로 군집을 형성하지 않고 원하는 군집의 개수를 사전에 설정

• 퍼지 군집화(Fuzzy clustering)
  관측값이 여러 클러스터에 동시에 속할 수 있는 군집화 방법론
  관측값마다 여러 클러스터에 속할 확률을 계산
• 밀도 기반 군집화
  데이터의 밀도(=밀집도)를 기준으로 군집 형성
  임의적인(Arbitrarity) 모양의 군집 탐색
  • DBCAN, OPTICS, DENCLUE

 

K-평균 군집분석(K-Means Clustering)

데이터를 K개의 군집으로 그룹화하는 알고리즘

군집 내 변동(오차제곱합)을 최소화하는 방향으로 군집화 하므로 군집 수를 정할 때 집단 내 제곱합 그래프가 필요함

• 사회 연결망 분석에서 연결망을 표현하는 분석 방법임

장점

• 대용량 데이터셋에서도 빠르게 실행 가능
• 분석 방법의 적용이 용이함
• 상대적으로 단순한 알고리즘
• 다양한 형태에 적용 가능
• 사전정보 없이도 의미있는 결과 창출 가능

단점

• 이상치, 잡음(noise)에 영향을 많이 받음 군집 경계 설정이 어려움
• 초깃값에 영향을 많이 받음
• 군집 개수를 지정해 줘야 함
• 군집이 원형으로 나눠지지 않은 경우 적절치 않음
  볼록(convex)한 형태가 아닌 오목한 형태의 군집이 존재하면 성능이 떨어짐
• 사전에 주어진 목적이 없어 결과 해석이 어려움

 

K-평균 군집분석 - 프로세스

1. K값 설정
2. 중심 초기화
   K개의 seed 중심을 임의로 선택
   • 임의로 선택하므로 군집이 형성되어도 군집 내 객체들은 다른 군집으로 이동 가능함
3. 군집 할당
   각 관측값을 가장 가까운 중심에 할당
4. 업데이트
   군집화된 데이터를 바탕으로 각 군집의 중심을 다시 계산
5. 모든 개체가 군집으로 할당될 때까지 3, 4번 반복
   중심의 위치를 업데이트하고 새로운 군집에 할당

 

PAM (Partitioning Around Medoids)
군집화(클러스터링) 알고리즘

• K-means와 유사하지만, 군집의 중심(centroid)을 평균 대신 데이터셋의 샘플을 사용해 보완한 방법
• 중앙값(Medoids) 사용: 군집의 중심점으로 데이터의 샘플을 사용하기 때문에 이상치에 강건하지만 계산량이 많다는 단점이 있음

 

혼합 분포 군집 (Gaussian Mixture Model)

확룰분포를 도입하여 군집을 수행하는 모형 기반 군집 방법

• 가정: 각 군집의 데이터 샘플을 확률분포에서 샘플링
• 통상 확률분포는 정규분포를 사용
• K-means나 PAM과 달리 확률분포 기반
• 군집의 크기가 너무 작으면 추정의 정도가 떨어지거나 어려울 수 있음
• 군집을 몇 개의 모수로 표현할 수 있음
• 모수 추정에서 데이터가 커지면 수행하는 데 시간이 걸릴 수 있음

 

확률분포 (모수) 추정 방법

EM 알고리즘 최대 가능도 추정량(Maximum Likelihood Estimation)을 위해 사용되는 알고리즘

• E-step: 잠재변수 $Z$의 기댓값 계산
  관측값이 특정 군집에 속할 확률 계산
• M-step: $Z$의 기댓값을 통한 파라미터 추정 (likelihood maximization)
• E단계, M단계를 반복하여 파라미터를 수정

 

Self-Organizing Maps (SOM; 자기조직화지도): 고차원의 데이터를 이해하기 쉬운 저차원의 뉴런으로 정렬해 지도형태로 형상화 하는 클러스터링 방법

입력층(Input Layer): 입력 벡터를 받는 층. 입력 변수의 개수와 동일하게 뉴런 수가 존재함

경쟁층(Competitive Layer): 2차원 격차로 구성된 층. 입력 벡터의 특성에 따라 벡터가 한 점으로 클러스터링 되는 층

• 역전파 알고리즘을 사용하는 인공신경망과 달리, 단 하나의 전방 패스를 사용함
• 경쟁학습으로 뉴런과 입력백터의 거리를 계산해 연결강도를 반복적으로 재조정함
  입력패턴과 유사한 뉴런일수록 연결강도가 셈
• 입력층의 뉴런은 경쟁층에 있는 뉴런들과 완전연결(Fully Connected)되어 있음
• 속도가 빠르고, 실시간 학습처리가 가능함
• 입력변수의 위치관계를 그대로 보존함