# R hclust

## 1. 개요
`hclust()`는 R 언어의 기본 패키지(`stats`)에서 제공하는 함수로, **계층적 군집 분석(Hierarchical Clustering)**을 수행하는 도구입니다. 계층적 군집 분석이란 데이터 포인트 간의 유사성을 측정하여 유사한 데이터끼리 순차적으로 묶어 나가는 분석 방법으로, 최종적으로 모든 데이터가 하나의 군집으로 합쳐질 때까지의 과정을 나무 모양의 계층 구조인 **덴드로그램(Dendrogram)**으로 시각화하는 것을 목적으로 합니다.

## 2. 작동 원리 및 알고리즘
`hclust()`는 기본적으로 **응집형(Agglomerative)** 방식을 사용합니다. 이는 모든 개별 데이터를 각각의 군집으로 간주하고 시작하여, 가장 가까운 군집들을 반복적으로 병합하는 'Bottom-up' 방식입니다.

### 2.1 거리 행렬 (Distance Matrix)
분석의 시작은 데이터 간의 거리를 계산하는 것입니다. R에서는 `dist()` 함수를 통해 거리 행렬을 생성합니다. 일반적으로 유클리드 거리(Euclidean distance)가 가장 많이 사용되지만, 데이터의 특성에 따라 다음과 같은 다양한 거리 측정법을 선택할 수 있습니다.
- **유클리드 거리 (`method = "euclidean"`)**: n차원 공간에서 두 점 사이의 직선 거리
- **맨해튼 거리 (`method = "manhattan"`)**: 각 좌표축의 차이의 절대값의 합
- **캔버라 거리 (`method = "canberra"`)**: 두 점 사이의 거리의 합으로 정규화한 거리 (주로 0에 가까운 값이 많은 데이터에 사용)

### 2.2 연결법 (Linkage Methods)
군집과 군집 사이의 거리를 어떻게 정의하느냐에 따라 결과가 달라집니다. 이를 연결법(Linkage method)이라고 합니다.

| 메서드 (`method`) | 명칭 | 특징 | 결과 경향 |
| :--- | :--- | :--- | :--- |
| `complete` | 최장 연결법 | 두 군집의 가장 먼 요소 간의 거리를 측정 | 군집의 지름을 최소화하며, 콤팩트한 군집 형성 |
| `average` | 평균 연결법 | 두 군집의 모든 요소 쌍 간 거리의 평균을 측정 | `complete`와 `single`의 중간적 성격, 안정적임 |
| `single` | 최단 연결법 | 두 군집의 가장 가까운 요소 간의 거리를 측정 | 사슬 모양의 군집(Chaining effect)이 나타나기 쉬움 |
| `ward.D2` | 와드 방법 | 병합 후 군집 내 분산(SSE)의 증가량을 최소화 | 군집 크기가 비슷하고 구형인 군집을 형성하는 경향. (R의 `ward`는 제곱 거리를 사용하지 않으므로, 현대적 분석 표준인 `ward.D2` 사용을 권장) |

## 3. 함수 사용법 및 파라미터

### 3.1 함수 구문
```R
hclust(d, method = "complete", ...)
```
- **`d`**: `dist()` 함수 등으로 생성된 거리 행렬(dissimilarity matrix)입니다.
- **`method`**: 위 표에서 설명한 연결법 중 하나를 선택합니다.
- **반환 값**: `hclust` 클래스 객체를 반환하며, 다음과 같은 주요 속성을 포함합니다.
    - `merge`: 군집이 병합되는 순서와 대상 정보
    - `height`: 병합 시의 거리(높이)
    - `order`: 덴드로그램의 리프 노드(데이터 포인트)가 배치되는 순서
    - `labels`: 데이터의 레이블

### 3.2 기본 워크플로우 예제
계층적 군집 분석은 일반적으로 **[데이터 전처리 $\rightarrow$ 거리 계산 $\rightarrow$ 군집 분석]**의 순서로 진행됩니다.

```R
# 1. 데이터 준비 (iris 데이터셋 사용, 수치형 변수만 추출)
df <- iris[, 1:4]

# 2. 데이터 스케일링 (단위가 다를 경우 필수)
df_scaled <- scale(df)

# 3. 거리 행렬 생성 (유클리드 거리)
dist_matrix <- dist(df_scaled, method = "euclidean")

# 4. 계층적 군집 분석 수행 (Ward.D2 방법 적용)
hc_result <- hclust(dist_matrix, method = "ward.D2")
```

## 4. 결과 시각화 및 해석

### 4.1 덴드로그램 출력
`plot()` 함수를 사용하여 분석 결과를 시각화합니다. Y축의 높이는 병합될 때의 거리(유사도)를 나타내며, 높이가 낮을수록 더 유사한 데이터임을 의미합니다.

```R
# 기본 덴드로그램 출력
plot(hc_result, main = "Iris Clustering Dendrogram", sub = "", xlab = "")

# 특정 군집 영역 강조 (군집 수 3개)
rect.hclust(hc_result, k = 3, border = "red")
```

### 4.2 군집 강조 및 고급 시각화
`dendextend` 패키지를 사용하면 덴드로그램의 색상을 변경하거나 가지의 모양을 조정하는 등 더 전문적인 시각화가 가능합니다.

```R
# install.packages("dendextend")
library(dendextend)

# 덴드로그램 객체로 변환
dend <- as.dendrogram(hc_result)

# 군집 수 3개로 설정하여 색상 지정
dend <- color_branches(dend, k = 3)

plot(dend, main = "Enhanced Dendrogram with dendextend")
```

## 5. 군집 수 결정 및 데이터 분할

### 5.1 `cutree()`를 이용한 군집 할당
덴드로그램은 구조만 보여줄 뿐, 실제 데이터가 어느 군집에 속하는지는 `cutree()` 함수를 통해 결정해야 합니다. 이 함수는 덴드로그램의 특정 높이(`h`) 또는 원하는 군집 수(`k`)에서 가지를 잘라 군집 번호를 부여합니다.

```R
# 군집 수를 3개로 지정하여 분할
cluster_assignment <- cutree(hc_result, k = 3)

# 결과 확인 (각 관측치별 군집 번호)
head(cluster_assignment)
```

### 5.2 데이터프레임 결합 및 시각화
분석 결과인 군집 번호를 원본 데이터와 결합하여 각 데이터가 어떤 군집으로 분류되었는지 확인하고 시각화합니다.

```R
# 원본 데이터와 군집 결과 결합
final_df <- cbind(df, cluster = cluster_assignment)

# 군집 결과 시각화 (산점도)
library(ggplot2)
ggplot(final_df, aes(x = Sepal.Length, y = Sepal.Width, color = as.factor(cluster))) +
  geom_point() +
  labs(color = "Cluster", title = "Clustering Result Visualization")
```

### 5.3 최적의 군집 수 결정
최적의 $k$를 결정하기 위해 덴드로그램에서 수직 거리(가지의 길이)가 가장 길게 나타나는 구간을 찾는 방법을 사용합니다. 이는 군집 간 거리가 급격히 멀어지는 지점을 찾는 것으로, $K$-means의 $Elbow$ $method$와 유사한 논리입니다.

## 6. 추가 팁 및 주의사항

### 6.1 hclust 객체 속성 접근법
`hclust` 결과 객체는 리스트 형태이므로 `$` 기호를 통해 내부 데이터에 직접 접근할 수 있습니다.
```R
# 병합 순서 확인
hc_result$merge

# 병합 높이 확인
hc_result$height

# 덴드로그램 리프 노드 순서 확인
hc_result$order
```

### 6.2 데이터 스케일링의 중요성
`hclust()`는 거리 기반 알고리즘이므로 변수의 단위(Scale)에 매우 민감합니다. 예를 들어, 한 변수는 단위가 'm'이고 다른 변수는 'km'라면, 수치 범위가 큰 변수가 거리 계산에 지배적인 영향을 미치게 됩니다. 따라서 반드시 `scale()` 함수를 통해 표준화 과정을 거쳐야 합니다.

### 6.3 시간 및 공간 복잡도
계층적 군집 분석은 다음과 같은 성능 한계를 가집니다.
- **시간 복잡도**: 일반적으로 $O(n^2 \log n)$ 또는 $O(n^3)$의 복잡도를 가집니다. 데이터 개수($n$)가 증가함에 따라 연산 시간이 기하급수적으로 증가합니다.
- **메모리 사용량**: $n \times n$ 크기의 거리 행렬을 메모리에 적재해야 하므로, 수만 건 이상의 대용량 데이터셋에 적용할 경우 메모리 부족(Out of Memory) 오류가 발생할 가능성이 높습니다. 대규모 데이터의 경우 $K$-means나 DBSCAN과 같은 다른 알고리즘을 고려해야 합니다.