kNN 그래프: 가까운 이웃 찾기
This content is not available in your language yet.
kNN 그래프(k-nearest-neighbour graph, k-최근접 이웃 그래프)는 숫자 벡터로 표현된 관측치마다 가장 가까운 이웃 k개를 찾아 선으로 연결한 그래프입니다. 입력은 관측치×특징 행렬이고, 출력은 관측치를 node, 가까운 관계를 edge로 가진 희소 인접 행렬입니다.
싱글셀 RNA-seq 분석에서는 세포×PCA 좌표 행렬에서 kNN 그래프를 만듭니다. 이 그래프 하나가 Leiden 군집화, UMAP, Diffusion Map, PAGA의 공통 입력이 되므로, 뒤 단계 결과가 이상하면 먼저 이 그래프가 어떻게 만들어졌는지 확인합니다.
어떤 문제를 풀 때 쓰는가
섹션 제목: “어떤 문제를 풀 때 쓰는가”세포 30,000개가 각각 유전자 2,000개의 발현값을 가진 행렬이 있다고 해봅시다. 이 행렬에서 “어떤 세포들이 서로 비슷한가”를 알고 싶지만, 30,000 × 30,000개의 모든 세포 쌍 거리를 저장하면 9억 칸이 됩니다. 대부분의 쌍은 전혀 비슷하지 않으므로 그 거리를 들고 있을 이유가 없습니다.
kNN 그래프는 각 세포에서 가장 가까운 k개(보통 10~30개)만 남깁니다. 세포 30,000개 × 이웃 15개면 edge가 45만 개뿐이라 메모리에 가볍게 올라가고, “비슷한 세포끼리 연결된 네트워크”라는 형태로 바뀌어 그래프 알고리즘을 바로 적용할 수 있습니다.
아래는 같은 과정을 점 10개로 줄인 것입니다. k를 늘리면 점마다 가까운 순서대로 edge가 추가됩니다.
| 뒤 단계 | kNN 그래프를 어떻게 쓰는가 |
|---|---|
| Leiden·Louvain 군집화 | edge가 촘촘한 node 묶음을 찾는다 |
| UMAP | edge로 연결된 점은 가깝게, 아닌 점은 멀게 2차원에 배치한다 |
| Diffusion Map·pseudotime | edge를 따라 걷는 random walk로 세포 사이 거리를 다시 정의한다 |
| PAGA | 군집 사이에 edge가 얼마나 많은지 세어 군집 연결 지도를 만든다 |
입력: 관측치×특징 행렬과 k
섹션 제목: “입력: 관측치×특징 행렬과 k”입력은 행이 관측치, 열이 숫자 특징인 행렬입니다. 설명을 위한 가상 데이터로 2차원 점 5개를 생각해 봅시다.
| point | x | y |
|---|---|---|
A | 0 | 0 |
B | 1 | 0 |
C | 0 | 1 |
D | 5 | 5 |
E | 6 | 5 |
여기에 결정할 것이 세 가지 있습니다.
- k: 각 점이 몇 개의 이웃과 연결될지. 작으면 그래프가 잘게 끊기고, 크면 작은 집단이 큰 집단에 묻힙니다.
- 거리 척도: 보통 Euclidean distance입니다. 방향만 중요하면 cosine distance를 쓰기도 합니다.
- 어떤 좌표에서 거리를 재는가: 원래 특징 공간인지, PCA로 줄인 공간인지.
싱글셀에서는 원래 유전자 공간이 아니라 PCA로 줄인 30~50차원 좌표를 입력으로 씁니다. 수천 개 유전자 각각의 측정 잡음이 거리를 지배하는 것을 막고 계산도 빨라집니다.
어떻게 계산하는가
섹션 제목: “어떻게 계산하는가”점마다 다른 모든 점과의 거리를 구한 뒤 가장 작은 k개를 고릅니다. 위 표에서 k = 2이면 결과는 다음 인접 리스트입니다.
A -> B, CB -> A, CC -> A, BD -> E, A # D에서 두 번째로 가까운 점은 멀리 있는 AE -> D, A여기서 두 가지를 볼 수 있습니다.
- 방향이 있다. D는 A를 이웃으로 골랐지만 A는 D를 고르지 않았습니다. 대부분의 도구는
A -> D와D -> A중 하나라도 있으면 edge를 두는 식으로 대칭화해 무방향 그래프를 만듭니다. - k는 항상 채워진다. D와 E처럼 외딴 점도 k개의 이웃을 억지로 갖습니다. 그래서 떨어진 두 집단 사이에도 가느다란 edge가 생길 수 있고, 뒤 단계에서 이 edge를 끊는 기준이 필요해집니다.
관측치가 수십만 개가 되면 모든 쌍의 거리를 계산하는 brute force는 느립니다. 그래서 실제 도구는 근사 최근접 이웃(approximate nearest neighbour, ANN) 알고리즘을 씁니다. Scanpy는 기본적으로 pynndescent를, Seurat는 annoy를 사용하며, 정확한 k개 중 일부가 빠질 수 있지만 큰 구조에는 영향이 거의 없습니다.
출력: 희소 인접 행렬 두 개
섹션 제목: “출력: 희소 인접 행렬 두 개”출력은 관측치 × 관측치 크기의 희소 행렬입니다. 각 행에 0이 아닌 값이 k개 정도만 있습니다. Scanpy는 두 가지를 저장합니다.
| 저장 위치 | 값 | 쓰임 |
|---|---|---|
adata.obsp['distances'] | 이웃까지의 실제 거리 | 거리가 필요한 분석 |
adata.obsp['connectivities'] | 0~1 사이 연결 강도(가까울수록 큼) | Leiden, UMAP, PAGA 입력 |
앞에서 본 점 10개로 distances 행렬을 만들면 다음과 같습니다. k를 바꾸면 그래프와 행렬이 함께 바뀝니다.
connectivities는 거리를 그대로 뒤집은 값이 아닙니다. UMAP 논문의 방식으로 각 점 주변의 밀도에 맞춰 거리를 다시 스케일한 뒤, 양쪽 방향의 값을 합쳐 대칭으로 만든 가중치입니다. 밀집한 영역과 성긴 영역 모두에서 “가장 가까운 이웃은 1에 가까운 값”을 받도록 보정된 결과라고 이해하면 됩니다.
adata.uns['neighbors']에는 k, 거리 척도, 사용한 좌표 같은 파라미터가 기록됩니다.
사례: 싱글셀 분석에 적용하면
섹션 제목: “사례: 싱글셀 분석에 적용하면”정규화와 PCA를 마친 AnnData 객체에서 그래프를 만드는 호출은 한 줄입니다.
import scanpy as sc
sc.pp.neighbors( adata, n_neighbors=15, # k n_pcs=30, # PCA 상위 30개 축에서 거리를 잰다 use_rep='X_pca', # adata.obsm['X_pca']를 입력으로 metric='euclidean',)
adata.obsp['connectivities'].shape # (n_cells, n_cells), 희소adata.obsp['connectivities'].nnz # 0이 아닌 칸 수 ≈ n_cells × k × 2 이하이후 sc.tl.leiden, sc.tl.umap, sc.tl.diffmap, sc.tl.paga는 모두 이 호출이 만든 connectivities를 읽습니다. 그래프를 다시 만들지 않고 파라미터만 바꾸면 뒤 단계 결과도 모두 바뀌므로, k와 n_pcs는 분석 기록에 남깁니다.
k를 고르는 감각
섹션 제목: “k를 고르는 감각”| k | 그래프 성격 | 영향 |
|---|---|---|
| 5~10 | 국소적, 잘게 끊김 | 작은 집단이 살아남지만 잡음 edge도 많음 |
| 15~30 | 일반적인 기본값 | 대부분 분석의 출발점 |
| 50 이상 | 전역적, 매끄러움 | 희귀 세포 집단이 이웃 집단에 흡수될 수 있음 |
세포 수가 수십만 개로 늘면 같은 밀도를 유지하기 위해 k를 조금 키우는 것이 일반적입니다.
흔한 함정
섹션 제목: “흔한 함정”- batch가 다른 세포끼리 연결되지 않는다. 실험 날짜나 장비가 다르면 같은 종류의 세포가 PCA 공간에서 떨어져 있어 batch별로 그래프가 갈립니다. 이 경우 Harmony 같은 보정 좌표를
use_rep에 넣거나, batch를 고려해 이웃을 고르는 BBKNN을 씁니다. - 외딴 세포도 k개 이웃을 갖는다. doublet이나 손상된 세포가 두 집단 사이를 잇는 다리가 되어 군집이 합쳐지거나 UMAP에서 가짜 연결이 보일 수 있습니다. QC를 먼저 끝냅니다.
- 그래프는 거리 척도와 전처리의 함수다.
log1p정규화 여부, HVG 선택, PC 개수가 바뀌면 “이웃”의 의미가 바뀝니다. 다른 설정으로 만든 두 그래프의 군집 번호를 직접 비교하지 않습니다. - 근사 알고리즘은 실행마다 조금 다를 수 있다. 재현하려면
random_state를 고정하고 라이브러리 버전을 기록합니다.