3 / 10강

가까운 그룹부터 합치기

처음에는 각 데이터를 별도 그룹으로 두고 가장 가까운 두 그룹을 계속 합칩니다. 그러면 작은 묶음이 큰 묶음에 들어가는 계층이 생깁니다. 이를 병합형 계층 군집화라고 합니다.

네 점으로 따라가기

일직선 위에 1, 2, 8, 10이 있습니다. 점 사이 거리는 차이의 절댓값입니다.

1. 1과 2의 거리가 1이므로 먼저 합칩니다.
2. 8과 10의 거리가 2이므로 합칩니다.
3. 두 그룹을 합치면 모든 점이 한 그룹이 됩니다.

합쳐지는 순서와 거리를 나무 그림으로 나타낸 것이 덴드로그램입니다. 어느 높이에서 자르느냐에 따라 그룹 수를 고를 수 있습니다.

그룹끼리의 거리는 무엇일까요?

점끼리의 거리를 정해도 그룹 사이 거리는 또 정해야 합니다.

• 단일 연결: 두 그룹에서 가장 가까운 점 쌍의 거리입니다. 위 두 그룹 사이 거리는 6입니다.
• 완전 연결: 가장 먼 점 쌍의 거리입니다. 위에서는 9입니다.
• 평균 연결: 두 그룹에 걸친 모든 점 쌍의 거리 평균입니다. 위에서는 (7+9+6+8)/4 = 7.5입니다.

단일 연결은 가느다란 연결 고리 때문에 큰 그룹이 이어질 수 있습니다. 완전 연결은 그룹의 최대 퍼짐에 더 민감합니다. 연결 기준이 바뀌면 최종 묶음도 달라질 수 있습니다.

확인 문제

한 번 합친 두 그룹을 기본 병합형 알고리즘이 나중에 다시 나눌까요? 데이터가 아주 많을 때 모든 점 쌍의 거리 표는 부담이 될까요?