군집화 고르기: Leiden·Louvain·k-means·계층적 군집화
군집화는 정답 라벨 없이 비슷한 관측치끼리 묶어 각 관측치에 그룹 번호를 붙이는 비지도 학습 방법입니다. 싱글셀 RNA-seq에서는 세포마다 0, 1, 2 같은 cluster 번호를 붙이고, 그 번호가 뒤에 오는 세포 종류 이름 붙이기와 조건 비교의 단위가 됩니다.
이 문서는 싱글셀에서 실제로 마주치는 네 알고리즘을 같은 틀로 비교합니다.
| 방법 | 종류 | 입력 | 군집 수 지정 | 출력 |
|---|---|---|---|---|
| Leiden | 그래프 커뮤니티 탐지 | kNN 그래프 | 안 함 (resolution으로 조절) | 세포별 cluster 번호 |
| Louvain | 그래프 커뮤니티 탐지 | kNN 그래프 | 안 함 (resolution) | 세포별 cluster 번호 |
| k-means | 좌표 기반 분할 | 세포×PC 좌표 | 함 (k) | 세포별 cluster 번호 + 중심점 |
| 계층적 군집화 | 거리 행렬 기반 병합 | 거리 행렬 (보통 군집 수준) | 나중에 자름 | dendrogram (트리) |
싱글셀의 기본 선택은 Leiden입니다. 나머지 셋은 Leiden이 맞지 않는 상황이나 보조 작업에 씁니다.
네 방법이 공통으로 푸는 문제
섹션 제목: “네 방법이 공통으로 푸는 문제”세포 30,000개가 PCA 공간에 흩어져 있을 때 “이 세포들은 몇 종류이고 각 세포는 어디에 속하는가”를 자동으로 결정하는 것이 목표입니다. 어느 방법이든 출력은 세포 수만큼의 정수 열 하나이고, 그 번호는 알고리즘이 임의로 붙인 것이라 cluster 3에 생물학적 의미는 없습니다.
방법들은 세 가지에서 갈립니다.
- 무엇을 입력받는가: 좌표인가, 그래프인가, 거리 행렬인가.
- 군집 수를 누가 정하는가: 사람이 미리 주는가, 알고리즘이 데이터에서 정하는가.
- 어떤 모양의 군집을 가정하는가: 둥근 덩어리인가, 어떤 모양이든 촘촘히 연결된 영역인가.
Leiden·Louvain: 그래프에서 촘촘한 구역을 찾는다
섹션 제목: “Leiden·Louvain: 그래프에서 촘촘한 구역을 찾는다”Louvain과 Leiden은 그래프에서 내부 edge는 많고 외부 edge는 적은 node 집합(커뮤니티)을 찾는 알고리즘입니다. 소셜 네트워크에서 친구 그룹을 찾는 데 쓰이는 것과 같은 알고리즘이고, 싱글셀에서는 세포가 node, 발현이 비슷한 세포 사이의 연결이 edge입니다.
어떤 문제를 풀 때 쓰는가
섹션 제목: “어떤 문제를 풀 때 쓰는가”세포 종류가 몇 개인지 미리 모르고, 집단마다 크기와 모양이 제각각일 때 씁니다. 큰 T세포 집단 옆에 작은 수지상세포 집단이 가늘게 붙어 있어도, 두 집단 사이에 edge가 적으면 갈라냅니다.
가까운 이웃일수록 큰 연결 강도를 가진 가중 kNN 그래프입니다. 좌표가 아니라 그래프를 받으므로, 그래프를 만든 좌표(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은 두 단계를 반복합니다.
- node 이동: node 하나를 이웃 군집으로 옮겨 보고 modularity가 오르면 옮긴다. 더 오르지 않을 때까지 반복한다.
- 축약: 각 군집을 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-means는 좌표 공간에서 중심점 k개를 두고, 각 점을 가장 가까운 중심에 배정하고, 중심을 배정된 점들의 평균으로 옮기는 과정을 반복하는 알고리즘입니다.
어떤 문제를 풀 때 쓰는가
섹션 제목: “어떤 문제를 풀 때 쓰는가”세포 종류를 찾는 주 군집화로는 잘 쓰지 않습니다. 군집 수 k를 미리 줘야 하고, 모든 군집이 비슷한 크기의 둥근 덩어리라고 가정하기 때문입니다. 가늘고 긴 분화 궤적은 여러 조각으로 잘리고, 작은 희귀 집단은 큰 집단에 흡수됩니다.
“한 단계”를 누르면 배정과 이동이 번갈아 진행되고, 배정이 더 바뀌지 않으면 멈춥니다. 눈으로 보면 무리는 셋이지만, k = 3으로 두어도 길쭉한 띠가 둘로 잘리고 둥근 무리 둘이 하나로 묶이는 결과가 자주 나옵니다. 중심에서의 거리만 보기 때문입니다. “중심 다시 놓기”를 누르면 출발 위치에 따라 결과가 달라지는 것도 볼 수 있습니다.
대신 보조 작업에 유용합니다.
- 세포 수백만 개를 수천 개의 작은 묶음(metacell, pseudo-bulk 단위)으로 미리 뭉칠 때
- 군집 하나의 세포들을 발현 패턴에 따라 몇 조각으로 빠르게 나눠 볼 때
- 유전자를 발현 패턴별로 묶을 때 (세포가 아니라 유전자가 관측치)
입력과 출력
섹션 제목: “입력과 출력”입력은 세포×PC 좌표 행렬과 k입니다. 그래프가 필요 없어 계산이 매우 빠릅니다. 출력은 세포별 cluster 번호와 k개의 중심점 좌표입니다. 처음 중심점을 무작위로 놓으므로, 여러 번 돌려 가장 좋은 결과를 고르는 것이 보통입니다.
계층적 군집화: 가까운 것부터 합쳐 트리를 만든다
섹션 제목: “계층적 군집화: 가까운 것부터 합쳐 트리를 만든다”계층적 군집화(hierarchical clustering)는 모든 관측치를 각자 하나의 군집으로 시작해, 가장 가까운 두 군집을 합치는 일을 하나가 남을 때까지 반복하는 알고리즘입니다. 합친 순서를 기록한 트리가 dendrogram입니다.
어떤 문제를 풀 때 쓰는가
섹션 제목: “어떤 문제를 풀 때 쓰는가”관측치 쌍마다 거리를 계산해 저장하므로 세포 수가 수만 개면 메모리와 시간이 감당되지 않습니다. 그래서 세포가 아니라 군집 20개 사이의 관계처럼 관측치가 수십~수백 개인 수준에서 씁니다.
- Leiden 군집들의 평균 발현을 비교해 어떤 군집끼리 가까운지 트리로 보여 줄 때
- heatmap에서 행과 열의 순서를 비슷한 것끼리 모을 때
- bulk RNA-seq처럼 샘플이 수십 개인 데이터에서 샘플 유사도를 볼 때
입력과 출력
섹션 제목: “입력과 출력”입력은 관측치 사이의 거리 행렬과 두 군집 사이 거리를 정의하는 linkage 규칙(average, complete, ward 등)입니다. 출력은 dendrogram이고, 원하는 높이에서 트리를 잘라 군집 수를 나중에 정합니다.
트리는 한 번만 만들고, 자르는 높이만 바꿔서 군집 수를 정합니다. 높이를 내리면 군집이 잘게 나뉘고 올리면 합쳐집니다. 위젯은 두 묶음 사이의 거리를 모든 점 쌍 거리의 평균으로 정하는 average linkage를 씁니다.
데이터 특성에 따라 고르기
섹션 제목: “데이터 특성에 따라 고르기”| 데이터·질문의 특성 | 맞는 방법 | 이유 |
|---|---|---|
| 세포 종류 수를 모르고 크기가 제각각 | Leiden | 군집 수를 데이터에서 정하고 모양을 가정하지 않음 |
| 희귀 집단(전체의 1% 미만)을 놓치면 안 됨 | Leiden (resolution 높임) | 그래프에서 분리돼 있으면 작아도 갈라냄 |
| 가늘고 긴 연속 궤적이 있음 | Leiden, 이후 궤적 분석 | k-means는 궤적을 토막 냄 |
| 세포 수백만 개를 빠르게 뭉쳐야 함 | k-means (사전 뭉치기), 이후 Leiden | 그래프 없이 선형 시간 |
| 군집끼리의 유사 관계를 트리로 보고 싶음 | 계층적 군집화 (군집 평균 위에서) | dendrogram이 관계를 직접 보여 줌 |
| 관측치가 수십 개 (bulk 샘플, 군집 평균) | 계층적 군집화 | 거리 행렬이 작아 전체 구조를 한눈에 봄 |
| Louvain 결과에 끊어진 군집이 보임 | Leiden으로 교체 | 연결성 보장 |
결과를 검증하는 법
섹션 제목: “결과를 검증하는 법”군집은 알고리즘이 낸 가설이지 정답이 아닙니다. 다음 세 가지로 점검합니다.
- 여러 resolution을 비교한다. 0.3, 0.5, 1.0으로 돌려 어느 군집이 어느 resolution에서 갈라지는지 봅니다. 모든 설정에서 유지되는 군집이 안정적인 군집입니다.
- marker 유전자를 본다. 군집마다 상대적으로 높은 유전자가 있고 그 조합이 알려진 세포 종류와 맞는지 확인합니다. marker 없이 갈라진 군집은 QC 지표(총 UMI, 미토콘드리아 비율)나 batch로 색칠해 기술적 원인인지 확인합니다.
- sample 구성을 본다. 한 군집이 특정 donor나 날짜의 세포로만 이루어져 있으면 batch 효과일 가능성이 큽니다.
silhouette score 같은 수치 지표는 둥근 군집을 가정하므로 Leiden 결과의 좋고 나쁨을 재는 기준으로 쓰기 어렵습니다.
흔한 함정
섹션 제목: “흔한 함정”- UMAP 그림에서 섬을 세어 군집 수를 정한다. UMAP은 뭉친 것을 더 뭉치게 그립니다. 군집은 그래프에서, 그림은 확인용으로 씁니다.
- cluster 번호를 실행 간에 비교한다.
cluster 3은 같은 데이터라도 seed나 resolution이 바뀌면 다른 세포 집단을 가리킵니다. 비교하려면 marker나 세포 종류 이름을 기준으로 맞춥니다. - 모든 세포가 군집을 받는다는 점을 잊는다. doublet과 손상 세포도 어딘가에 배정됩니다. 작은 군집이 두 세포 종류의 marker를 동시에 보이면 doublet 군집을 의심합니다.
- 한 번의 resolution으로 끝낸다. 큰 계통은 낮은 resolution에서, 세부 상태는 관심 계통만 떼어 내 다시 그래프를 만들고 군집화하는 두 단계가 보통 더 정확합니다.
- k-means에 UMAP 좌표를 넣는다. UMAP 좌표의 거리는 의미가 없으므로 PC 좌표를 씁니다.