Agglomerative Hierarchical clustering은 클러스터에 하위 클러스터가 있고 하위 클러스터가 연속적으로 포함되는 상향식 클러스터링 접근 방식입니다. 클러스터의 모든 객체를 찾는 것으로 시작한 다음 일부 객체가 생성될 때까지 이러한 원자 클러스터를 더 높은 클러스터로 결합합니다. 단일 클러스터에서 또는 명확한 종료 조건이 필요할 때까지. 여러 계층적 클러스터링 접근 방식이 이 유형에 사용됩니다. 클러스터 간 유사성에 대한 설명에서만 구별됩니다.
예를 들어 AGNES(Agglomerative Nesting)라는 방법은 단일 링크 기술이 필요하며 다음과 같이 작동합니다. 직사각형에 배치된 개체 그룹이 있다고 가정합니다. 처음에 각 개체는 자체 클러스터에 있습니다. 따라서 클러스터는 클러스터에서 가장 가까운 객체 사이의 최소 유클리드 거리로 클러스터를 병합하는 것과 관련된 몇 가지 원칙에 따라 단계적으로 결합됩니다.
계층적 클러스터링은 클러스터-하위 클러스터 연관과 클러스터가 결합(집합적 보기) 또는 분할(분할 보기)된 순서를 모두 보여주는 덴드로그램으로 알려진 트리와 같은 다이어그램을 사용하여 그래픽으로 표시됩니다.
기본 집합적 계층적 클러스터링 알고리즘.
-
필요한 경우 근접 행렬을 계산합니다.
-
반복
-
가장 가까운 두 클러스터를 병합합니다.
-
새 클러스터와 초기 클러스터 간의 근접성을 반영하도록 근접성 매트릭스를 새로 고칩니다.
-
클러스터가 하나만 남을 때까지.
클러스터 근접성은 일반적으로 특정 유형의 클러스터로 정의됩니다. 예를 들어, MIN, MAX 및 그룹 평균을 포함한 여러 응집 계층적 클러스터링 기술은 클러스터의 그래프 기반 보기에서 나옵니다.
MIN은 클러스터 근접성을 여러 클러스터에 있는 두 점을 닫는 근접성으로 정의하거나 그래프 방법을 사용하여 여러 노드 하위 집합에 있는 두 노드 중 가장 짧은 가장자리입니다.
또는 MAX는 여러 클러스터에서 가장 먼 두 지점 사이의 근접도를 클러스터 근접도로 간주하거나 그래프 방법을 사용하여 노드의 서로 다른 하위 집합에 있는 두 노드 사이의 가장 높은 가장자리를 사용합니다.
제시된 개념 집합적 계층적 클러스터링 알고리즘은 근접 행렬을 필요로 합니다. 이를 위해서는 $\mathrm{\frac{1}{2}m^2}$ 근접성의 창고가 필요했습니다(근접 행렬이 대칭인 경우). 여기서 m은 다중 데이터 포인트입니다. 클러스터의 추적을 유지하는 데 필요한 공간은 단일 클러스터를 제외하고 m-1인 다중 클러스터에 비례합니다. 따라서 전체 공간 복잡도는 $\mathrm{O(m^2)}$입니다.
기본 응집 계층적 클러스터링 알고리즘의 분석은 계산 복잡성과 관련하여도 쉽습니다. $\mathrm{O(m^2)}$ 근접 행렬을 계산하는 데 시간이 필요합니다. 그 단계 후에 시작에 m개의 클러스터가 있고 모든 반복 중에 두 개의 클러스터가 병합되기 때문에 단계 3과 4를 포함하는 m - 1개의 반복이 있습니다.