# 군집화 고르기: Leiden·Louvain·k-means·계층적 군집화

> 라벨 없는 세포에 그룹 번호를 붙이는 네 군집화 알고리즘이 각각 무엇을 입력받아 무엇을 출력하고, 데이터 특성에 따라 어느 것을 골라야 하는지 비교한다.

군집화는 **정답 라벨 없이 비슷한 관측치끼리 묶어 각 관측치에 그룹 번호를 붙이는 비지도 학습 방법**입니다. 싱글셀 RNA-seq에서는 세포마다 `0`, `1`, `2` 같은 cluster 번호를 붙이고, 그 번호가 뒤에 오는 [세포 종류 이름 붙이기](/lessons/single-cell-annotation/)와 조건 비교의 단위가 됩니다.

이 문서는 싱글셀에서 실제로 마주치는 네 알고리즘을 같은 틀로 비교합니다.

| 방법 | 종류 | 입력 | 군집 수 지정 | 출력 |
| --- | --- | --- | --- | --- |
| Leiden | 그래프 커뮤니티 탐지 | [kNN 그래프](/reference/knn-graph/) | 안 함 (`resolution`으로 조절) | 세포별 cluster 번호 |
| Louvain | 그래프 커뮤니티 탐지 | kNN 그래프 | 안 함 (`resolution`) | 세포별 cluster 번호 |
| k-means | 좌표 기반 분할 | 세포×PC 좌표 | 함 (`k`) | 세포별 cluster 번호 + 중심점 |
| 계층적 군집화 | 거리 행렬 기반 병합 | 거리 행렬 (보통 군집 수준) | 나중에 자름 | dendrogram (트리) |

싱글셀의 기본 선택은 **Leiden**입니다. 나머지 셋은 Leiden이 맞지 않는 상황이나 보조 작업에 씁니다.

## 네 방법이 공통으로 푸는 문제

세포 30,000개가 PCA 공간에 흩어져 있을 때 "이 세포들은 몇 종류이고 각 세포는 어디에 속하는가"를 자동으로 결정하는 것이 목표입니다. 어느 방법이든 출력은 세포 수만큼의 정수 열 하나이고, 그 번호는 알고리즘이 임의로 붙인 것이라 `cluster 3`에 생물학적 의미는 없습니다.

방법들은 세 가지에서 갈립니다.

- **무엇을 입력받는가**: 좌표인가, 그래프인가, 거리 행렬인가.
- **군집 수를 누가 정하는가**: 사람이 미리 주는가, 알고리즘이 데이터에서 정하는가.
- **어떤 모양의 군집을 가정하는가**: 둥근 덩어리인가, 어떤 모양이든 촘촘히 연결된 영역인가.

## Leiden·Louvain: 그래프에서 촘촘한 구역을 찾는다

**Louvain**과 **Leiden**은 그래프에서 **내부 edge는 많고 외부 edge는 적은 node 집합(커뮤니티)을 찾는 알고리즘**입니다. 소셜 네트워크에서 친구 그룹을 찾는 데 쓰이는 것과 같은 알고리즘이고, 싱글셀에서는 세포가 node, 발현이 비슷한 세포 사이의 연결이 edge입니다.

### 어떤 문제를 풀 때 쓰는가

세포 종류가 몇 개인지 미리 모르고, 집단마다 크기와 모양이 제각각일 때 씁니다. 큰 T세포 집단 옆에 작은 수지상세포 집단이 가늘게 붙어 있어도, 두 집단 사이에 edge가 적으면 갈라냅니다.

### 입력

가까운 이웃일수록 큰 연결 강도를 가진 가중 [kNN 그래프](/reference/knn-graph/)입니다. 좌표가 아니라 그래프를 받으므로, 그래프를 만든 좌표(PCA든 VAE든)와 k가 군집 결과를 좌우합니다.

### 어떻게 동작하는가

좋은 분할의 기준은 **modularity**입니다. 군집 안에 edge가 많다는 것만으로는 좋은 군집인지 알 수 없습니다. 군집이 크면 안쪽 edge는 저절로 많아지고, 모든 세포를 한 군집으로 묶으면 모든 edge가 안쪽에 들어가기 때문입니다. 그래서 modularity는 군집 안의 실제 edge 수를 **우연만으로 기대되는 수**와 비교합니다.

우연의 기준은 이렇게 만듭니다. 모든 edge를 가운데서 잘라 각 세포에 끝만 남긴 뒤, 그 끝들을 무작위로 둘씩 다시 잇습니다. 각 세포의 이웃 수는 그대로이지만 누가 누구와 가까운지는 사라집니다. 이 상태에서 군집 안에 들어오는 edge 수가 우연으로 기대되는 수입니다.



③을 누를 때마다 끝들이 새로 이어지고, 군집 안에 들어오는 edge 수가 달라집니다. 여러 번 반복한 평균은 일정한 값으로 모입니다. 군집이 전체 끝의 절반을 가지고 있으면, edge의 양 끝이 모두 군집 안에 놓일 확률은 1/2 × 1/2 = 1/4이므로 전체 edge의 1/4이 기대값입니다. 실제 수가 이 기대값을 넘는 만큼이 군집이 정말로 뭉쳐 있다는 증거이고, 이 초과분을 전체 edge 수로 나눈 값이 그 군집의 몫입니다.

modularity는 이 몫을 모든 군집에 대해 더한 값입니다. 두 알고리즘은 이 합이 커지는 분할을 탐욕적으로 찾습니다.

Louvain은 두 단계를 반복합니다.

1. **node 이동**: node 하나를 이웃 군집으로 옮겨 보고 modularity가 오르면 옮긴다. 더 오르지 않을 때까지 반복한다.
2. **축약**: 각 군집을 node 하나로 뭉쳐 작은 그래프를 만들고 1로 돌아간다.



modularity는 분할이 정해져 있어야 계산할 수 있는 점수입니다. 그래서 세포마다 각자 군집인 임시 분할에서 출발해, 한 번에 node 하나씩 옮겨 보며 점수를 올려 갑니다. "한 걸음"을 누를 때마다 아래의 modularity가 오르거나 그대로이고, 내려가는 일은 없습니다. 축약 뒤에는 뭉친 node를 통째로 옮기므로 작은 군집들이 한꺼번에 합쳐집니다.

Leiden은 1과 2 사이에 **세분화** 단계를 넣어, 한 군집 안에서 서로 연결되지 않은 조각이 생기면 떼어 냅니다. Louvain은 이 보장이 없어 "하나의 군집이지만 그래프에서는 두 섬"인 결과를 낼 수 있습니다. 같은 입력이면 Leiden이 더 빠르고 결과도 더 안정적이라 Scanpy와 Seurat 모두 Leiden을 권장합니다.

**resolution**은 유일하게 중요한 손잡이입니다. 값이 클수록 modularity 계산에서 작은 군집을 더 선호해 군집 수가 늘어납니다. 정답 값은 없으며 데이터와 질문에 따라 여러 값을 시도합니다.



resolution을 낮추면 가는 다리로 이어진 무리까지 한 군집으로 묶이고, 올리면 큰 무리가 안쪽의 덩이 단위로 갈라집니다. 어느 값에서든 군집 사이를 건너는 흰 점선은 군집 안의 선보다 적고, resolution을 올릴수록 그 수가 늘어납니다. 이것이 "내부 edge는 많고 외부 edge는 적은" 분할입니다. 위젯은 Louvain의 node 이동과 축약을 그대로 계산합니다.

| resolution | 보통 생기는 군집 수 (세포 수만 개 기준) | 용도 |
| ---: | --- | --- |
| 0.1~0.3 | 5~10개 | 큰 계통(면역·상피·간질) 구분 |
| 0.5~1.0 | 10~25개 | 일반적인 세포 종류 수준 |
| 1.5 이상 | 30개 이상 | 세부 상태, 한 계통 안에서 재군집화 |

### 출력

세포마다 cluster 번호가 하나씩 붙은 열입니다. 번호는 보통 세포 수가 많은 순서이고, resolution이나 seed를 바꾸면 번호가 전부 바뀝니다. 여러 resolution의 결과를 비교하려면 열을 따로 저장해 둡니다.

## k-means: 중심점 k개 주변으로 나눈다

**k-means**는 **좌표 공간에서 중심점 k개를 두고, 각 점을 가장 가까운 중심에 배정하고, 중심을 배정된 점들의 평균으로 옮기는 과정을 반복하는 알고리즘**입니다.

### 어떤 문제를 풀 때 쓰는가

세포 종류를 찾는 주 군집화로는 잘 쓰지 않습니다. 군집 수 k를 미리 줘야 하고, 모든 군집이 비슷한 크기의 둥근 덩어리라고 가정하기 때문입니다. 가늘고 긴 분화 궤적은 여러 조각으로 잘리고, 작은 희귀 집단은 큰 집단에 흡수됩니다.



"한 단계"를 누르면 배정과 이동이 번갈아 진행되고, 배정이 더 바뀌지 않으면 멈춥니다. 눈으로 보면 무리는 셋이지만, k = 3으로 두어도 길쭉한 띠가 둘로 잘리고 둥근 무리 둘이 하나로 묶이는 결과가 자주 나옵니다. 중심에서의 거리만 보기 때문입니다. "중심 다시 놓기"를 누르면 출발 위치에 따라 결과가 달라지는 것도 볼 수 있습니다.

대신 **보조 작업**에 유용합니다.

- 세포 수백만 개를 수천 개의 작은 묶음(metacell, pseudo-bulk 단위)으로 미리 뭉칠 때
- 군집 하나의 세포들을 발현 패턴에 따라 몇 조각으로 빠르게 나눠 볼 때
- 유전자를 발현 패턴별로 묶을 때 (세포가 아니라 유전자가 관측치)

### 입력과 출력

입력은 세포×PC 좌표 행렬과 k입니다. 그래프가 필요 없어 계산이 매우 빠릅니다. 출력은 세포별 cluster 번호와 k개의 중심점 좌표입니다. 처음 중심점을 무작위로 놓으므로, 여러 번 돌려 가장 좋은 결과를 고르는 것이 보통입니다.

## 계층적 군집화: 가까운 것부터 합쳐 트리를 만든다

**계층적 군집화**(hierarchical clustering)는 **모든 관측치를 각자 하나의 군집으로 시작해, 가장 가까운 두 군집을 합치는 일을 하나가 남을 때까지 반복하는 알고리즘**입니다. 합친 순서를 기록한 트리가 **dendrogram**입니다.

### 어떤 문제를 풀 때 쓰는가

관측치 쌍마다 거리를 계산해 저장하므로 세포 수가 수만 개면 메모리와 시간이 감당되지 않습니다. 그래서 세포가 아니라 **군집 20개 사이의 관계**처럼 관측치가 수십~수백 개인 수준에서 씁니다.

- Leiden 군집들의 평균 발현을 비교해 어떤 군집끼리 가까운지 트리로 보여 줄 때
- heatmap에서 행과 열의 순서를 비슷한 것끼리 모을 때
- bulk RNA-seq처럼 샘플이 수십 개인 데이터에서 [샘플 유사도](/lessons/rna-sample-similarity/)를 볼 때

### 입력과 출력

입력은 관측치 사이의 거리 행렬과 두 군집 사이 거리를 정의하는 **linkage** 규칙(average, complete, ward 등)입니다. 출력은 dendrogram이고, 원하는 높이에서 트리를 잘라 군집 수를 나중에 정합니다.



트리는 한 번만 만들고, 자르는 높이만 바꿔서 군집 수를 정합니다. 높이를 내리면 군집이 잘게 나뉘고 올리면 합쳐집니다. 위젯은 두 묶음 사이의 거리를 모든 점 쌍 거리의 평균으로 정하는 average linkage를 씁니다.

## 데이터 특성에 따라 고르기

| 데이터·질문의 특성 | 맞는 방법 | 이유 |
| --- | --- | --- |
| 세포 종류 수를 모르고 크기가 제각각 | Leiden | 군집 수를 데이터에서 정하고 모양을 가정하지 않음 |
| 희귀 집단(전체의 1% 미만)을 놓치면 안 됨 | Leiden (resolution 높임) | 그래프에서 분리돼 있으면 작아도 갈라냄 |
| 가늘고 긴 연속 궤적이 있음 | Leiden, 이후 [궤적 분석](/reference/trajectory-methods/) | k-means는 궤적을 토막 냄 |
| 세포 수백만 개를 빠르게 뭉쳐야 함 | k-means (사전 뭉치기), 이후 Leiden | 그래프 없이 선형 시간 |
| 군집끼리의 유사 관계를 트리로 보고 싶음 | 계층적 군집화 (군집 평균 위에서) | dendrogram이 관계를 직접 보여 줌 |
| 관측치가 수십 개 (bulk 샘플, 군집 평균) | 계층적 군집화 | 거리 행렬이 작아 전체 구조를 한눈에 봄 |
| Louvain 결과에 끊어진 군집이 보임 | Leiden으로 교체 | 연결성 보장 |

## 결과를 검증하는 법

군집은 알고리즘이 낸 가설이지 정답이 아닙니다. 다음 세 가지로 점검합니다.

1. **여러 resolution을 비교한다.** 0.3, 0.5, 1.0으로 돌려 어느 군집이 어느 resolution에서 갈라지는지 봅니다. 모든 설정에서 유지되는 군집이 안정적인 군집입니다.
2. **marker 유전자를 본다.** 군집마다 상대적으로 높은 유전자가 있고 그 조합이 알려진 세포 종류와 맞는지 확인합니다. marker 없이 갈라진 군집은 QC 지표(총 UMI, 미토콘드리아 비율)나 batch로 색칠해 기술적 원인인지 확인합니다.
3. **sample 구성을 본다.** 한 군집이 특정 donor나 날짜의 세포로만 이루어져 있으면 batch 효과일 가능성이 큽니다.

silhouette score 같은 수치 지표는 둥근 군집을 가정하므로 Leiden 결과의 좋고 나쁨을 재는 기준으로 쓰기 어렵습니다.

## 흔한 함정

- **UMAP 그림에서 섬을 세어 군집 수를 정한다.** UMAP은 뭉친 것을 더 뭉치게 그립니다. 군집은 그래프에서, 그림은 확인용으로 씁니다.
- **cluster 번호를 실행 간에 비교한다.** `cluster 3`은 같은 데이터라도 seed나 resolution이 바뀌면 다른 세포 집단을 가리킵니다. 비교하려면 marker나 세포 종류 이름을 기준으로 맞춥니다.
- **모든 세포가 군집을 받는다는 점을 잊는다.** doublet과 손상 세포도 어딘가에 배정됩니다. 작은 군집이 두 세포 종류의 marker를 동시에 보이면 doublet 군집을 의심합니다.
- **한 번의 resolution으로 끝낸다.** 큰 계통은 낮은 resolution에서, 세부 상태는 관심 계통만 떼어 내 다시 그래프를 만들고 군집화하는 두 단계가 보통 더 정확합니다.
- **k-means에 UMAP 좌표를 넣는다.** UMAP 좌표의 거리는 의미가 없으므로 PC 좌표를 씁니다.

### 공식 자료

- [Scanpy `sc.tl.leiden` API](https://scanpy.readthedocs.io/en/stable/api/generated/scanpy.tl.leiden.html)
- [Leiden 논문: Traag, Waltman & van Eck, *Scientific Reports* (2019)](https://www.nature.com/articles/s41598-019-41695-z)
- [Louvain 논문: Blondel et al., *J. Stat. Mech.* (2008)](https://doi.org/10.1088/1742-5468/2008/10/P10008)
- [scikit-learn 군집화 개요 (k-means, hierarchical)](https://scikit-learn.org/stable/modules/clustering.html)
- [단일세포 분석 모범 사례: Heumos et al., *Nature Reviews Genetics* (2023)](https://www.nature.com/articles/s41576-023-00586-w)