병합 군집(agglomerative clustering)

#!/usr/bin/env python3

---

병합 군집(agglomerative clustering)

---

0. 살펴보기

병합 군집^{agglomerative clustering} 알고리즘은 

시작할 때 각 포인트를 하나의 클러스터로 지정하고, 그다음 종료 조건을 만족할 때까지 가장 비슷한 두 클러스터를 합침

종료조건 : 클러스터 갯수, 지정된 갯수의 클러스터가 남을 때까지 비슷한 클러스터를 합침

linkage: 옵션에서 가장 비슷한 클러스터를 측정하는 방법 지정, 이 측정은 항상 두 클러스터 사이에서 이뤄짐

ward : 기본값, 모든 클러스터 내의 분산을 가장 작게 증가시키는 두 클러스터를 합침, 크기가 비교적 비슷한 클러스터가 만들어짐

average : 클러스터 포인트 사이의 평균 거리가 가장 짤븐 두 클러스터를 합침

complete : complete연결(최대 연결)은 클러스터 포인트 사이의 최대 거리가 가장 짧은 두 클러스터를 합침

클러스터에 속한 포인트 수가 많이 다를 때(하나의 클러스터가 다른 것보다 매우 클 때 ) average나 complete가 더 나음

# library import

import mglearn

import matplotlib

import matplotlib.pyplot as plt

# matplotlib 설정

matplotlib.rc('font', family='AppleGothic')

plt.rcParams['axes.unicode_minus'] = False

# 알고리즘 설명 시각화

mglearn.plots.plot_agglomerative_algorithm()

plt.show()

두 인접 클러스터를 반복적으로 합쳐나가는 병합 군집

1. 초기에 각 포인트가 하나의 클러스터

2. 가장 가까운 두 클러스터가 합쳐짐

3. step4까지 이 방식으로 진행

4. step5에서 두 개의 포인트를 가진 클러스중 하나가 3개로 확장

5. step9까지 이 방식으로 진행

6. 3개의 클러스터를 찾는다고 지정하면 알고리즘은 종료

---

1. make blobs(인위적 데이터)로 병합 군집 분석

알고리즘의 작동 특성상 병합 군집은 새로운 데이터 포인트에 대해서는 예측을 할 수 없기 때문에

predict메소드가 없음(매니폴드 학습과 동일)

# library import

from sklearn.cluster import AgglomerativeClustering

from sklearn.datasets import make_blobs

import numpy as np

# dataset

x, y = make_blobs(random_state=1)

# 모델 생성 및 학습

agg = AgglomerativeClustering(n_clusters=3)

assign = agg.fit_predict(x)

# 배열 x 오른쪽에 열 한개 추가

a = assign.reshape(-1, 1)

x1 = np.hstack([x, a])

# 각 클래스별로 데이터 추출

x_0 = x1[x1[:, 2]==0, :]

x_1 = x1[x1[:, 2]==1, :]

x_2 = x1[x1[:, 2]==2, :]

# 시각화

plt.scatter(x_0[:, 0], x_0[:, 1], cmap=mglearn.cm3)

plt.scatter(x_1[:, 0], x_1[:, 1], cmap=mglearn.cm3)

plt.scatter(x_2[:, 0], x_2[:, 1], cmap=mglearn.cm3)

plt.legend(['cluster 0', 'cluster 1', 'cluster 2'], loc=2)

plt.show()

병합 군집을 사용한 세 개의 클러스터 할당

---

2. 계층적 군집과 덴드로그램

병합군집은 계층적 군집hierarchical clustering을 만듬. 군집이 반복하여 진행되면 모든 포인트는 하나의 포인트를 가진 클러스터에서 시작하여 마지막 클러스터까지 이동

각 중간단계는 데이터에 대한 (다른 갯수)의 클러스터를 생성

mglearn.plots.plot_agglomerative()

plt.show()

병합 군집으로 생성한 계층적 군집

이 그래프는 계층 군집의 모습을 자세히 나타내지만, 2차원 데이터일 뿐이며 특성이 셋 이상인 데이터셋에는 적용불가

dendrogram은 다차원 데이터셋을 처리가능

---

3. dendrogram으로 3차원 이상의 데이터 시각화

# library import

from scipy.cluster.hierarchy import dendrogram, ward^[각주:1]

# dataset

x, y = make_blobs(random_state=0, n_samples=12)

### 데이터 배열 x에 ward 함수를 적용

### scipy의 ward 함수는 병합 군집을 수행할 때 생성된 거리 정보가 담긴 배열을 반환

linkage_array = ward(x)

dendrogram(linkage_array)

ax = plt.gca() # get current axes

bounds = ax.get_xbound() # x축 데이터(처음과 끝), 즉 최소/최대값을 가진 (1,2)리스트

ax.plot(bounds, [7.25, 7.25], linestyle='--', c='k') # 임의로 라인 생성

ax.plot(bounds, [4, 4], linestyle='--', c='k')

ax.text(bounds[1], 7.25, ' 두 개의 클러스터', va='center', fontdict={'size':15}) # bounds: x축 끝

ax.text(bounds[1], 4, ' 세 개의 클러스터', va='center', fontdict={'size':15})

plt.xlabel('샘플 번호')

plt.ylabel('클러스터 거리')

plt.show()

클러스터의 덴드로그램과 클러스터를 구분하는 점선

덴드로그램에서 데이터 포인트(0 ~ 11)까지는 맨 아래 나타남

이 포인트들을 잎leaf으로 하는 트리가 만들어지며 부모 노드는 두 클러스터가 합쳐질때 추가됨

가지의 길이는 합쳐진 클러스터가 얼마나 멀리 떨어져 있는지를 보여줌

빨강 그룹과 바다색 그룹이 합쳐질때 가지의 길이는 짧아짐 ==> 비교적 짧은 거리의 데이터를 병합

1. ward : 기본값, 모든 클러스터 내의 분산을 가장 작게 증가시키는 두 클러스터를 합침, 크기가 비교적 비슷한 클러스터가 만들어짐 [본문으로]