계층적 클러스터링이란 무엇인가요?

클러스터링은 데이터 분석에서 유사한 개체를 감지하고 그룹화하는 데 사용되는 비지도 머신 러닝 기법입니다. 계층적 클러스터 분석(HCA) 또는 계층적 클러스터링은 개체 내에서 선형적인 순서를 적용하지 않고 개체를 클러스터 계층으로 그룹화합니다. 생물학, 이미지 분석, 사회 과학 등 많은 분야에서 계층적 클러스터링 방법을 사용해 데이터 세트의 패턴을 탐색하고 인식합니다. 사용 사례로는 임상 연구에서의 인구 분류, 고객 세분화, 네트워크 모델에서 노드 커뮤니티 감지 등이 있습니다.

계층적 클러스터링에는 다음과 같은 두 가지 유형이 있습니다.

- 하나의 클러스터가 나타날 때까지 클러스터를 반복적으로 더 큰 클러스터로 병합하는 응집적 또는 상향식 접근 방식¹을 사용합니다.

- 분할 또는 하향식 접근 방식²은 단일 클러스터의 모든 데이터로 시작하여 모든 클러스터가 싱글톤이 될 때까지 연속적인 클러스터를 계속 분할하는 방식입니다.

계층적 클러스터링 분석에는 계산 비용이 많이 듭니다. 힙(heap)을 사용하면 계산 시간을 줄일 수 있지만 메모리 요구 사항은 증가합니다. 클러스터링의 분할 유형과 집계 유형 모두 "greedy"한데, 즉 알고리즘이 프로세스의 각 단계에서 국소적으로 최적의 클러스터를 선택하여 병합 또는 분할할 클러스터를 결정합니다. 미리 정해진 클러스터 수에 도달하면 알고리즘이 클러스터 집합 또는 클러스터 분할을 중지하는 중지 기준을 적용할 수도 있습니다.

덴드로그램³이라고 하는 나무 모양의 다이어그램은 종종 클러스터의 계층을 시각화하는 데 사용됩니다. 클러스터가 병합되거나 나뉜 순서를 표시하고 데이터 포인트 간의 유사성 또는 거리를 보여줍니다. 덴드로그램은 속성이 있는 ^목록의 중첩된 목록으로 이해할 수도 있습니다.

계층적 클러스터링 알고리즘은 비유사성 행렬의 개념을 사용하여 병합하거나 나눌 클러스터를 결정합니다. 비유사성은 선택한 연결 방법으로 측정된 두 데이터 포인트 간의 거리입니다. 비유사성 행렬의 값은 다음과 같이 표현됩니다.

- 거리⁵(예: 유클리드 거리), 집합 내 단일 점 사이의 거리

- 연결 클러스터링 기준은 유사성을 집합 간 포인트의 쌍별 거리 함수로 지정합니다.

가장 일반적인 유클리드 거리(Euclidean distance) 연결 방법을 살펴보겠습니다. 사용할 수 있는 다른 거리 메트릭의 예로는 민코프스키(Minkowski), 해밍(Hamming), 마할라노비스(Mahalanobis), 하우스도르프(Hausdorf), 맨해튼(Manhattan) 거리가 있습니다. 각 연결 방법은 동일한 데이터 세트에서 다른 클러스터를 생성합니다. 적절한 연결 클러스터링 방법을 선택하는 것은 클러스터링되는 데이터 유형, 데이터 밀도, 클러스터 모양, 데이터 세트에 이상치 또는 노이즈가 있는지 여부와 같은 요인에 따라 달라집니다.

단일 연결 방법은 두 클러스터에 있는 항목 간의 쌍별 거리를 분석한 다음 클러스터 간의 최소 거리를 사용합니다. 최소 방법은 타원형이 아닌 클러스터 모양을 잘 처리하지만 노이즈와 이상값의 영향을 받습니다. 이 방법에는 연쇄 효과⁶라는 한계가 있습니다. 클러스터 쌍 사이에 다리를 만드는 몇 개의 점으로 인해 두 클러스터가 하나로 합쳐질 수 있습니다. 최소 연결 기준은 다음과 같이 표현할 수 있습니다.

 mina∈A,b∈Bd(a,b)

여기서 A와 B는 두 개의 관측치 집합이고 d는 거리 함수입니다.

군집 거리는 서로 가장 멀리 떨어져 있는 점을 기준으로 계산할 수도 있습니다. 최대 방법은 최소 방법보다 잡음과 이상값에 덜 민감하지만 구형 또는 대형 클러스터가 있는 경우 최대 방법을 사용하면 결과가 왜곡될 수 있습니다. 최대 연결은 대개 최소 연결보다 구형 군집을 더 많이 생성합니다. 최대 연결은 다음 공식으로 나타낼 수 있습니다.

 최대∈A,b∈Bd(a,b)

여기서 A와 B는 두 개의 관측치 집합이고 d는 거리입니다.

Sokal과 Michener⁷에 의해 도입된 이러한 방법은 군집 사이의 거리를 군집의 모든 점 쌍에 걸친 쌍 사이의 평균 거리로 정의합니다. 알고리즘은 UPGMA(산술 평균)를 사용하는 비가중 쌍 그룹 방법 또는 WPGMA(산술 평균을 사용하는 가중 쌍 그룹 방법)이 모두 가능합니다. 여기서 "가중치 없음"의 의미는 모든 거리가 각 평균에 동등하게 기여한다는 것입니다.

UPGMA는 다음 공식으로 표현됩니다.

1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

여기서 *A*와 *B*는 두 개의 관측 세트이고 *d*는 거리입니다.

WPGMA는 다음 공식으로 표시됩니다.

d(i∪j,k)=d(i,k)+d(j,k)2

여기서 i와 j는 각 단계에서 결합되어 i와 j의 합집합의 새 군집을 형성하는 가장 가까운 군집입니다. 그런 다음 k와 i, k와 j의 데이터 포인트 사이의 평균 거리의 산술 평균인 다른 클러스터 k까지의 거리를 계산할 수 있습니다.

여기서는 군집 중심 또는 중심 사이의 거리를 사용합니다. 중심 사이의 거리는 거리 함수를 사용하여 계산됩니다.

∥μA-μB∥2

여기서 _μA는 A의 중심이고 _μB는 B의 중심입니다.

Joe H. Ward는 1960년대에 MISSQ(Minimal Increase of Sum of Squares) 방법⁸을 도입했습니다. 모든 데이터 포인트는 자체 클러스터에서 시작되는데, 이 접근 방식은 데이터 포인트 간의 제곱합이 처음에는 0이고 클러스터를 병합함에 따라 증가한다는 것을 의미합니다. Ward의 방법은 점들이 병합될 때 군집 중심에서 점들의 제곱 거리의 합을 최소화합니다. Ward의 방법은 양적 변수⁹에 대해 좋은 선택이며, 잡음이나 특이치의 영향을 덜 받습니다. 이는 다음과 같이 나타낼 수 있습니다.

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

여기서 A의 평균과 B의 평균은 각각 A와 B의 중심이고 x는 A와 B의 합집합에 속하는 데이터 포인트입니다.

Ward의 최소 분산 방법은 Lance-Williams 알고리즘을 사용하여 개선할 수 있습니다. 이 알고리즘은 재귀 공식을 사용하여 클러스터 거리를 업데이트하고 병합할 최적의 가장 가까운 클러스터 쌍을 찾습니다.

응집적 중첩(AGNES)이라고도 하는 응집적 계층적 클러스터링에서는 각 데이터 포인트가 클러스터로 시작됩니다. 이 알고리즘은 유사도 행렬을 기반으로 선택한 연결 클러스터링 기준을 사용하여 조인할 클러스터 쌍을 결정합니다. 알고리즘은 계층을 위로 이동하고 모든 것이 서로 연결될 때까지 클러스터를 계속 짝을 지어 중첩된 일련의 계층적 클러스터를 만듭니다. 대략적으로 말하면 응집 클러스터링 단계¹⁰는 다음과 같습니다.

1. 특정 메트릭을 사용하여 비유사성 행렬을 계산합니다.

2. 각 데이터 포인트를 클러스터에 할당합니다.

3. 클러스터 간의 유사성에 대한 연결 기준에 따라 클러스터를 병합합니다.

4. 거리 행렬을 업데이트합니다.

5. 하나의 클러스터가 남거나 정지 기준이 충족될 때까지 3단계와 4단계를 반복합니다.

분할 계층적 클러스터링의 원리는 1964년 Macnaughton-Smith를 포함한 다수의 사람들이¹¹ 개발했고, 1990년 Kaufman과 Rousseeuw가 DIANA(분할 분석 클러스터링) 알고리즘¹²을 통해 더 연구되었습니다. 분할 클러스터링은 응집 클러스터링과 반대되는 접근 방식을 사용합니다. 모든 데이터 포인트는 단일 클러스터에서 시작하여 반복적으로 더 많은 클러스터로 분할됩니다. 나머지 모든 클러스터가 싱글톤이 되거나 미리 정의된 클러스터 수와 같은 중지 기준이 충족될 때까지 분할이 발생합니다. 분할 방법은 대규모 클러스터¹³를 식별하는 데 더 뛰어나며 알고리즘이 프로세스 시작부터 전체 데이터 세트 분포를 고려하기 때문에 응집 방법보다 정확할 수 있습니다.

효율성을 높이기 위해 분할 방식은 k-평균과 같은 평면 클러스터링 알고리즘을 사용하여 데이터 세트를 클러스터로 분할합니다. 클러스터의 수는 미리 지정해야 합니다. k-평균 알고리즘은 중심점 사이의 클러스터 내 제곱 합을 최소화하여 클러스터를 분할합니다. 이를 관성 기준¹⁴이라고 합니다. 분할 클러스터링 단계¹⁵는 다음과 같습니다:

1. 데이터 세트 크기 N(d1, d2, d3 ... dN)에 대한 모든 데이터 포인트를 하나의 클러스터로 시작합니다.

2. k-means 알고리즘과 같은 플랫 클러스터링 방법을 사용하여 클러스터를 두 개의 서로 다른 클러스터 또는 이질적인 클러스터로 분할합니다.

3. 2단계를 반복하여 분할하기에 가장 적합한 클러스터를 선택하고 각 반복(Iteration) 후 응집력이 가장 낮은 클러스터에서 이상값을 제거합니다

4. 각 예제가 자체 단일 클러스터에 있을 때 중지하고, 그렇지 않으면 3단계를 반복합니다.

클러스터 결과는 일반적으로 덴드로그램(이진 트리 구조)으로 표시됩니다. 덴드로그램의 x축은 데이터 점을 나타내고 y축 또는 선의 높이는 클러스터가 병합될 때 얼마나 멀리 떨어져 있었는지를 나타냅니다.

덴드로그램을 사용하여 최종 클러스터링 모델에 얼마나 많은 클러스터¹⁶가 포함될지 결정할 수 있습니다. 한 가지 전략은 가지가 줄어들고 길어지는 나무의 자연적인 절단 지점을 식별하는 것입니다. 또는, 군집의 수는 수평선이 덴드로그램을 절단할 때 교차하는 수직선의 수로 주어집니다.

여기에 표시된 예제 이미지에서 수평선 H1은 두 개의 수직선을 자릅니다. 이는 프로세스의 이 시점에 두 군집, 즉 점 5, 8, 2가 있는 군집 하나와 나머지 점이 있는 군집이 있음을 보여줍니다. 덴드로그램의 다른 수평선을 자르지 않고 수평선이 위 또는 아래로 더 멀리 이동할 수 있을수록 클러스터링 모델에 맞게 이 개수의 클러스터를 선택하는 것이 더 좋습니다. 아래 예제에서 수평선 H2는 클러스터 4개를 선택합니다. H2는 다른 수평선을 자르기 전에는 H1까지 위아래로 이동할 수 없습니다. 이 시나리오는 클러스터링 모델에 2개의 클러스터 선택(H1)이 더 적합할 수 있음을 보여줍니다.

강력한 클러스터링 모델¹⁷은 클래스 내 유사성은 높고 클래스 간 유사성은 낮은 클러스터를 생성합니다. 그러나 클러스터 품질을 정의하는 것은 어려울 수 있으며, 연결 기준과 클러스터 수를 선택하는 것이 결과에 큰 영향을 미칠 수 있습니다. 따라서 클러스터링 모델을 구축할 때는 다양한 옵션을 시도해 보고 나중에 고려할 데이터 세트의 패턴을 탐색하고 드러내는 데 가장 도움이 되는 옵션을 선택해야 합니다. 고려해야 할 요소¹⁸는 다음과 같습니다.

- 데이터 세트에 대해 실용적이거나 논리적인 클러스터 수(데이터 세트 크기, 클러스터 모양, 노이즈 등)

- 각 클러스터의 평균, 최대값, 최소값 등의 통계 정보

- 적용할 최상의 비유사성 메트릭 또는 연결 기준

- 이상값 또는 결과 변수의 영향

- 특정 도메인 또는 데이터 세트 지식

최적의 클러스터 수¹⁹를 결정하는 데 도움이 되는 다른 방법은 다음과 같습니다.

- 엘보 방법은 클러스터 수에 대한 클러스터 내 제곱의 합을 플롯하고 "엘보"(플롯이 수평을 이루는 지점)를 결정하는 방법입니다.

- 갭 통계: 실제 클러스터 내 제곱합과 null 레퍼런스 분포에 대한 예상 클러스터 내 제곱합을 비교하여 가장 큰 격차를 식별하는 통계입니다.

계층적 클러스터링은 데이터 과학자에게 데이터 세트 내의 구조와 관계에 대한 인사이트를 제공하며 다양한 사용 사례에 적용될 수 있습니다.

계층적 클러스터링은 제품 선택, 인구 통계, 구매 행동, 위험 프로필 또는 소셜 미디어와의 상호 작용을 기준으로 그룹화하는 등 트렌드를 분석하고 고객 데이터를 세분화하는 데 도움이 될 수 있습니다.

임상 연구를 위한 환자 코호트는 수천 개에 달할 수 있습니다. 계층적 군집화(Hierarchical clustering)는 예를 들어, 진단 기준, 생리적 반응 또는 DNA 돌연변이를 사용하여 혼합된 집단을 보다 동질적인 그룹²⁰으로 분류하는 데 도움이 됩니다. 또한 진화 발달을 이해하기 위해 생물학적 특징에 따라 종을 그룹화하는 데 적용 할 수 있습니다.

계층적 클러스터링은 이미지 기반 텍스트 인식 응용 프로그램에서 손으로 쓴 문자를 모양별로 그룹화하는 데 사용됩니다. 또한 특정 기준을 사용하여 정보를 저장 및 검색하거나 검색 결과를 분류하는 데 사용됩니다.

Python과 R 프로그래밍 언어는 모두 데이터 과학에서 널리 사용됩니다. Python은 유연하며 광범위한 작업을 처리할 수 있고, R은 통계 컴퓨팅을 위해 특별히 설계되었으며 계층적 클러스터링 분석을 시각화할 수 있는 다양한 옵션을 제공합니다.

Python은 AgglomerativeCluster 함수²¹ (sklearn의 병합 군집(agglomerative clustering) 예제²² 참조)를 제공하며, SciPy는 덴드로그램(dendrogram)²³을 플로팅하는 함수를 제공합니다. ddextend²⁴와 같은 패키지는 R의 덴드로그램 기능을 향상시켜 민감도 분석을 개선하고 다양한 덴드로그램을 비교하고 조작할 수 있도록 합니다. 실습 경험이 필요하면 Python에서 계층적 클러스터링을 구현하는 방법 및 R에서 계층적 클러스터링을 구현하는 방법과 같은 단계별 튜토리얼을 확인하세요.