계층적 군집화 (Hierarchical Clustering)

  • HC라고도 이야기 한다.
  • 객체의 유사성을 측정해서 유사성이 높은 대상들을 집단적으로 분류하고 군집간의 어떤 상회성을 분류하는 방법
  • dendrogram으로 나타낼 수 있다.
    • 다이어그램 같은 트리는 병합 또는 나눔의 순서를 기록한다.
  • 거리, 유사도를 계산해서 갖고 있어야 한다.
    • 유사도 - 유클리드거리, 맨하튼 거리,
  A B C D
A   20 7 2
B     10 25
C       3
D        

‘AD’ ex ‘B’, ‘AD’ ex ‘C’

군집화 - 객체

군집- 군집

  AD B D  
AD   22 3  
B     10  
C        
         

계층적 군집화의 두가지 주요 타입

  • Agglomerative(응집하는):
    • 점을 개별 클러스터로 시작한다
    • 각 단계에서 하나의 클러스터 (또는 k 클러스터) 만 남아있을 때까지 클러스터에서 가장 가까운 쌍을 합친다.
  • Divisive(분열을 초래하는):
    • 모든 기능이 포함된 단일 클러스터로 시작한다
    • 각 단계에서 각 클러스터에 점이 포함될 때까지 (또는 k 클러스터가 있을 때까지) 클러스터를 분할한다.

기존의 계층적 알고리즘은 유사성 또는 거리 행렬을 사용한다.

  • 한 번에 하나의 클러스터를 병합 또는 분할

Agglomerative clustering algorithm

  • 클러스터부터 나눠서 단일 클러스터만 남을 때까지 반복적으로 처리한다.
  • 가장 가까운 거리의 값이나 유사성을 가지고 있는 것들을 계속 군집을 병행해서 사용한다.
  • 병행 후 반복적으로 단일 클러스터만 남았을 때 사용한다.

중간 상황(Intermediate Situation)

  • 가장 가까운 클러스터를 병합한다.

클러스터간 유사성을 어떻게 정의하나?

  • MIN : 최단거리 (최단 연결, single link)
  • K-075
  • MAX : 최장거리 (최장 연결)
  • K-076
  • 그룹 평균 : 평균 연결 (군집과 군집간의 거리 평균)
  • K-077
  • 중심점 사이 거리 : 중심 사이사이 거리
  • K-078
  • 목적 함수에 의해 구동되는 다른 방법 :
    • Ward’s Method uses squared error - 군집간의 정보 손실을 최소화하는 방법, ex) 제곱의 합
  1. 유사한 가까운 객체
  2. 한번 속한 부분은 이동이 안된다
  3. dendrogram 군집형성 과정을 파악한다.
  4. 군집간의 거리 차이가 큰 경우

클러스터 유사성 : MIN or 단일링크

  • 두 기반의 각각의 값들을 처리한다.
  • 하나의 점을 이용한다.
  • 근접 그래프는 하나의 값이 있다고 하면 값을 표현할 수 있는 형태로 나타낸다.
MIN
  • K-064

K-065

클러스터 유사성 : MAX or Complete Linkage

  • 두 클러스터의 유사성은 최소 두개의 점을 기반으로 한다. 다른 클러스터 안에서
  • 두 클러스터 안에 있는 모든 점들의 쌍은 결정된다.

MAX

K-067

MAX의 강점

K-068

MAX의 한계

K-070

클러스터 유사성 : Group Average

  • 두 군집의 근접성은 두 군집의 점들 사이의 쌍별 근접성의 평균입니다.
  • 대규모 클러스터에 총 근접성이 유리하므로 확장성을 위해 평균 연결 사용 필요

계층 군집화 : Group Average 그룹 평균

K-072

  • 단일 링크와 전체 링크를 절충해준다.

    강점 : 노이즈 및 특이상치의 영향을 덜 받는다.

    제한사항 : 한쪽이 치우쳐져 있는 경향이 있다.

클러스터 유사성 : Ward’s Method

  • 점 사이의 거리가 제곱인 경우 그룹의 평균값과 유사하게 처리를 한다.
  • 두 군집의 유사성은 군집이 병합될 때 제곱 오차의 증가를 기반으로 합니다.
    • 포인트 간 거리가 거리 제곱인 경우 그룹 평균과 유사
  • 노이즈 및 특이치의 영향을 덜 받습니다. 구상성단에 치우침 K-평균의 계층적 아날로그 - K-평균 초기화 시 사용 가능

계층적 클러스터링 : 비교

K-074

계층적 클러스터링 : 시간과 공간의 요구사항

  • 근접 행렬을 사용하기 때문에 O(N^2)의 공간을 사용한다.
    • N은 점의 숫자
  • 각 단계의 N^2부터 근접 행렬을 업데이트한다. 일부 접근 방식의 경우 복잡성을 N log n의 시간으로 줄일 수 있다.

계층적 클러스터링 : 문제와 제한

  • 두 클러스터를 결합하기로 결정한 후에는 취소할 수 없습니다.

  • 객관적 기능이 직접 최소화되지 않음

  • 서로 다른 체계는 다음 중 하나 이상에 문제가 있습니다.

    • 노이즈 및 특이치에 대한 민감도 다양한 크기의 군집 및 볼록형 처리 어려움 대규모 클러스터 해제

클러스터링 종류

  1. 군집적
  • K-means (객체를 사전 정의해서 개수로 나타내는 것)
  1. 계층적
  • 덴드로그램 ( 가까운 거리(거리, 유사성))

이상치

  • 내가 가지고 있는 점이 내가가지고 있는 범위를 벗어난 값을 이상치라 한다.
  • 다른 데이터보다 가장 작은 값이나 큰 값을 말함
  • 필요한 이유 : 데이터를 분석 했을 때, 이상치에 의해서 의사결정에 영향을 미칠 수가 있다, 그래서 사용한다.
  • 모형을 구축함에 있어서 이상치는 빈도에 비해 영향력이 크다.
  • 정확한 모수(parameter)를 추정하기 어렵다.