계층적 클러스터링 기술은 데이터 개체를 클러스터 트리로 결합하여 작동합니다. 계층적 클러스터링 알고리즘은 하향식 또는 상향식입니다. 진정한 계층적 클러스터링 방법의 품질은 병합 또는 분할 결정이 완료된 후 조정을 구현할 수 없기 때문에 저하됩니다.
클러스터 병합은 클러스터 간의 거리를 기반으로 합니다. 클러스터 사이의 거리에 대해 널리 사용되는 측정값은 다음과 같습니다. 여기서 mi는 클러스터 Ci의 평균, ni는 Ci의 포인트 수, |p – p'| 두 점 p와 p' 사이의 거리입니다.
계층적 클러스터링 방법 유형
다음과 같은 두 가지 유형의 계층적 클러스터링 방법이 있습니다. -
AHC(Agglomerative Hierarchical Clustering) - AHC는 클러스터에 하위 클러스터가 있고 차례로 하위 클러스터 등이 있는 상향식 클러스터링 방법입니다. 클러스터에서 각 객체를 찾는 것으로 시작한 다음 모든 객체가 나타날 때까지 이러한 원자 클러스터를 더 크고 더 큰 클러스터로 결합합니다. 단일 클러스터에 있거나 특정 종료 조건을 충족할 때까지 대부분의 계층적 클러스터링 방법이 이 유형에 적용됩니다. 그들은 클러스터 간 유사성에 대한 정의에서만 구별됩니다.
예를 들어 AGNES(Agglomerative Nesting)로 알려진 방법은 단일 링크 기술을 사용하며 다음과 같이 작동합니다. 직사각형에 있는 개체 집합이 있다고 가정합니다. 원래 각 개체는 자체 클러스터에 배치됩니다. 그런 다음 클러스터는 클러스터에서 가장 가까운 객체 사이에서 최소 유클리드 거리로 클러스터를 병합하는 것을 포함하는 몇 가지 원칙에 따라 단계적으로 결합됩니다.
분할 계층적 클러스터링(DHC) − DHC는 하향식 접근 방식이며 덜 일반적으로 사용됩니다. 응집 클러스터링과 유사한 방법으로 작동하지만 반대 방향입니다. 이 방법은 모든 객체를 포함하는 단일 클러스터에서 시작하여 단일 객체 클러스터만 남을 때까지 또는 원하는 클러스터 수를 포함하여 특정 종료 조건을 만족하거나 가장 가까운 두 클러스터 사이의 거리가 100 이상일 때까지 결과 클러스터를 연속적으로 분할합니다. 특정 임계값 거리.
분할 방법은 일반적으로 접근할 수 없으며 높은 수준에서 올바른 분할 결정을 내리는 것이 어렵기 때문에 거의 사용되지 않았습니다. DIANA(Divisia Analysis)는 분할 계층 클러스터링 방법의 한 예입니다. 반대 순서로 작동합니다. 원래 모든 개체는 하나의 클러스터에 있습니다. 따라서 클러스터는 클러스터에서 가장 가까운 인접 객체 간의 최대 유클리드 거리에 따라 클러스터를 분할하는 것을 포함하여 몇 가지 원칙에 따라 분할됩니다.