[수학] 최단 연결법 계산을 통한 덴드로그램 그리기

0. 목표

 - 최단 연결법 계산을 통한 덴드로그램 그리기

1. 준비

 1) 예제 데이터

data2 = [[1, 1], [2, 2], [5, 5], [10, 10], [12, 12]]

 2) 유클리드 거리 계산

  - 파이썬 코드

  - 결과

2. 실습

 1) 최단 거리 검색

  - 0과 1 사이의 거리가 가장 짦음(1.414214)

 2) 0과 1을 하나로 묶고 각 집단 마다의 최소거리 계산

  (1) d((2), (0, 1)) = min|d(2, 0), d(2, 1) = d(2, 1) = 4.242641

  (2) d((3), (0, 1)) = min|d(3, 0), d(3, 1) = d(3, 1) = 11.313708

  (3) d((4), (0, 1)) = min|d(4, 0), d(4, 1) = d(4, 1) = 14.142136

 3) 정리

 - 그림으로 나타내면

 4) 3)에서 최단거리 검색

  - 3과 4 사이의 거리가 가장 짧음(2.828427)

 5) 3과 4를 하나로 묶고 각 집단 마다의 최소거리 계산

  (1) d((0, 1), (3, 4)) = min|d((0, 1), 3), d((0, 1), 4) = d((0, 1), 3) = 11.313708

  (2) d((2), (3, 4)) = min|d(2, 3), d(2, 4) = d(2, 3) = 7.071068

 6) 정리

  - 그림으로 나타내면

 7) 6)에서 최단거리 검색

  - 2와 (0, 1) 사이의 거리가 가장 짧음(4.242641)

 8) 2와 (0, 1)을 하나로 묶고 각 집단 마다의 최소거리 계산

  - d((3, 4), (0, 1, 2)) = min|d((3, 4), (0, 1)), d((3, 4), 2) = d((3, 4), 2) = 7.071068

 9) 정리

  - 그림으로 나타내면

 8) 최종

  - d(0, 1, 2, 3, 4) = 7.071068

3. scipy 모듈과 비교

   1) 그림

from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt

X = np.array([[1, 1], [2, 2], [5, 5], [10, 10], [12, 12]])

Z = linkage(X, 'single')

fig = plt.figure(figsize=(25, 10))
dn = dendrogram(Z)
plt.show()

 2) 수치확인

Z

4. 참고

 - 군집분석 최단 연결법 single linkage

 - 군집분석

 - scipy.cluster.hierarchy.linkage