스펙트럴 군집화

통계 수치해석 마지막 수정: 2026-07-31 05:48:09

1. 개요[편집]

스펙트럴 군집화 Spectral Clustering
입력	유사도 행렬 $W$ (그래프)
핵심 도구	그래프 라플라시안의 하위 고유벡터
대표 논문	Shi & Malik(2000), Ng·Jordan·Weiss(2002)
마무리	고유벡터 좌표 위의 k-평균 군집화
강점	동심원·초승달 같은 비볼록 군집
약점	$\sigma$·이웃 수 선택에 극도로 민감

점들을 직접 나누지 말고, 일단 그래프로 바꾼 뒤 고유벡터한테 물어봐라.

스펙트럴 군집화(spectral clustering)는 자료점들을 유사도 그래프로 바꾼 다음 그래프 라플라시안의 작은 고유값에 대응하는 고유벡터로 좌표를 새로 매기고, 그 좌표 위에서 군집을 나누는 방법이다. k-평균 군집화가 “가까이 뭉쳐 있음”을 요구하는 반면 이쪽이 요구하는 것은 “서로 연결되어 있음”이다. 동심원 두 개나 서로 감긴 초승달처럼 볼록하지 않은 군집에서 k-평균이 대각선으로 잘라 버리는 실패가, 여기서는 그냥 풀린다.

거리 기반 알고리즘을 고유값 문제로 바꿔치기했다는 점에서 주성분 분석과 사촌이지만, 다루는 행렬이 공분산이 아니라 그래프 라플라시안이고 쓰는 고유벡터가 큰 쪽이 아니라 작은 쪽이라는 것이 결정적으로 다르다. PCA가 “분산이 큰 방향”을 찾는다면 이쪽은 “진동수가 낮은 모드”, 즉 그래프 위에서 가장 완만하게 변하는 함수를 찾는다. 실제로 균일한 격자 그래프의 라플라시안 고유벡터는 이산 코사인 기저이고, 그래서 이 절차를 그래프 위의 푸리에 변환으로 읽는 관점(그래프 신호처리)이 따로 있을 정도다.

2. 유사도 그래프 만들기[편집]

먼저 점 $n$ 개를 정점으로 하는 가중 그래프를 짓는다. 표준 선택지는 세 가지다.

$\varepsilon$ -이웃 그래프 — 거리가 $\varepsilon$ 이하인 쌍을 잇는다. 보통 가중치 없이 쓴다.
kNN 그래프 — 각 점의 최근접 $k$ 개를 잇는다. 방향성을 없애는 방식에 따라 대칭 kNN과 상호 kNN으로 갈린다. 밀도가 다른 군집이 섞여 있을 때 가장 무난하다.
완전 그래프 + 가우시안 커널 — $w_{ij} = \exp(-\lVert \mathbf{x}_i - \mathbf{x}_j \rVert^2 / 2\sigma^2)$ .

어느 쪽을 쓰든 결과 그래프는 되도록 희소해야 한다. 뒤에 올 고유분해 비용이 간선 수에 직결되기 때문이고, 조밀 유사도 행렬을 그대로 들고 가는 순간 $n$ 이 몇만만 되어도 계산이 서 버린다.

이 단계가 사실상 결과 전부를 결정한다. 특히 $\sigma$ 는 악명이 높아서, 조금 크면 그래프가 통째로 한 덩어리가 되고 조금 작으면 점마다 고립돼 라플라시안의 0 고유값이 수백 개로 늘어난다.¹ 알고리즘 자체는 결정론적인데 결과가 재현이 안 되는 것 같다면 거의 항상 이 단계를 의심해야 한다.

3. 그래프 라플라시안 세 종류[편집]

차수 행렬 $D = \mathrm{diag}(d_i)$ , $d_i = \sum_j w_{ij}$ 에 대해 라플라시안은 세 가지가 표준이다.

L = D - W, \qquad L_{\mathrm{sym}} = I - D^{-1/2} W D^{-1/2}, \qquad L_{\mathrm{rw}} = I - D^{-1} W

셋 다 준정부호이며, 그 근거는 임의의 벡터 $\mathbf{f}$ 에 대해 성립하는 항등식

\mathbf{f}^{\mathsf T} L \mathbf{f} = \frac{1}{2}\sum_{i,j} w_{ij}\,(f_i - f_j)^2 \ \ge\ 0

이다. 이 식이 이 문서 전체의 엔진이다 — 연결이 강한 두 정점에 다른 값을 주면 벌점이 크다. 따라서 $L$ 의 이차형식을 작게 만드는 벡터는 자연히 “그래프를 약한 곳에서 자르는” 벡터가 된다.

여기서 가장 유용한 사실 하나. 고유값 0의 중복도는 그래프의 연결성분 개수와 정확히 같고, 그 고유공간은 각 성분의 지시벡터들이 친다. 성분이 완전히 분리돼 있다면 고유벡터만 읽어도 군집이 그대로 나온다는 뜻이다. 현실의 그래프는 성분끼리 약하게 이어져 있으므로 0이 $\varepsilon$ 만큼 들려 올라가고, 지시벡터도 그만큼 흐려질 뿐이다.

세 라플라시안의 차이는 차수 불균형을 어떻게 다루느냐다. $L_{\mathrm{rw}} = I - D^{-1}W$ 의 이름이 말해 주듯 $D^{-1}W$ 는 그래프 위 무작위 보행의 전이행렬이고, 따라서 이 방법은 “보행자가 좀처럼 빠져나가지 못하는 영역을 찾는 일”로도 정확히 읽힌다. $L_{\mathrm{sym}}$ 과 $L_{\mathrm{rw}}$ 는 고유쌍이 $\mathbf{u} \leftrightarrow D^{-1/2}\mathbf{u}$ 로 일대일 대응하는 사실상 같은 물건이고, 차수가 크게 들쭉날쭉한 그래프에서는 정규화판이 거의 항상 낫다.

4. 절단 문제의 연속 완화[편집]

왜 하필 고유벡터인가. 그래프를 두 조각 $A, \bar{A}$ 로 나눌 때 목적함수로 잘린 간선 가중치 합 $\mathrm{cut}(A,\bar{A})$ 만 쓰면 점 하나를 떼는 자명한 해가 이긴다. 그래서 크기로 나눠 준 정규화 절단을 쓴다.

\mathrm{NCut}(A,\bar{A}) = \mathrm{cut}(A,\bar{A})\left(\frac{1}{\mathrm{vol}(A)} + \frac{1}{\mathrm{vol}(\bar{A})}\right)

이 최소화는 NP-난해다. 그런데 지시벡터가 두 값만 갖는다는 이산 제약을 풀어 실수 벡터를 허용하면(연속 완화), 문제는 정확히 “ $\mathbf{1}$ 에 직교하는 방향에서 라플라시안의 레일리 몫을 최소화하라”가 되고 답은 두 번째로 작은 고유값의 고유벡터 — 곧 피들러 벡터다. 비율 절단(RatioCut)은 $L$ , 정규화 절단은 $L_{\mathrm{rw}}$ 에 대응한다.

완화의 대가는 정직하게 치른다. 연속해와 원래 이산해의 차이에는 일반적으로 어떤 상수배 보장도 없고, 실제로 임의로 나쁠 수 있는 예제가 알려져 있다.² 그럼에도 실전에서 잘 도는 이유는 앞 절의 “0 고유값 = 연결성분” 구조가 웬만큼만 유지되면 고유벡터가 지시벡터의 섭동으로 남기 때문이다.

5. 알고리즘과 실무 요령[편집]

유사도 그래프 $W$ 를 만든다.
라플라시안의 하위 $k$ 개 고유벡터를 구해 $n \times k$ 행렬 $U$ 의 열로 놓는다. ( $L_{\mathrm{sym}}$ 을 쓰면 각 행을 단위 노름으로 정규화한다.)
$U$ 의 각 행을 $\mathbb{R}^k$ 의 한 점으로 보고 k-평균 군집화를 돌린다.

마지막에 굳이 k-평균을 다시 부르는 게 이상해 보이지만, 이상적인 블록 분리 상황에서 같은 군집의 행들은 한 점으로 완전히 붕괴한다. 즉 3단계는 군집화라기보다 연속 완화해를 이산해로 되돌리는 반올림 단계이고, 그 단계에서는 k-평균의 볼록 군집 가정이 처음으로 참이 된다.

$k$ 는 고유값을 작은 것부터 늘어놓고 간극 $\lambda_{k+1} - \lambda_k$ 가 크게 벌어지는 지점에서 끊는 고유간극 휴리스틱으로 고른다. 근거는 앞에서 본 구조 그대로다 — 군집이 $k$ 개면 앞의 $k$ 개가 0 근처에 눌려 있고 $k+1$ 번째부터 확 올라간다. 잘 분리된 자료에서는 이 계단이 눈에 띄게 보이지만, 애초에 구조가 흐릿하면 이것도 아무 말을 해 주지 않는다. k-평균의 팔꿈치 그래프와 같은 처지다.

비용은 정직하게 비싸다. 조밀 $W$ 를 만들면 저장만 $O(n^2)$ 이고 고유분해는 $O(n^3)$ 이다. 그래서 실무는 kNN으로 희소화한 뒤 란초스 알고리즘·ARPACK으로 하위 몇 개만 뽑거나, 열 일부만 계산해 나머지를 외삽하는 나이스트룀 근사를 쓴다. 희소행렬 저장이 여기서 그대로 성능이다.

6. 동심원에서는 왜 이기는가[편집]

이 방법의 홍보용 예제는 늘 동심원 두 개다. 안쪽 원과 바깥 고리를 k-평균에 던지면 중심이 두 개 다 원점 근처로 몰려 결국 좌우로 반 갈라 버린다. 목적함수가 중심까지의 제곱거리 합이니 당연한 결과이고, 초기화를 백 번 바꿔도 똑같다.

스펙트럴 쪽에서는 사정이 다르다. kNN 그래프를 만들면 안쪽 원의 점들끼리, 바깥 고리의 점들끼리만 이웃이 되고 두 무리를 잇는 간선은 거의 없다. 그래프가 사실상 두 연결성분이므로 라플라시안의 0 고유값이 (거의) 두 겹이 되고, 피들러 벡터는 두 무리에 서로 다른 상수를 얹은 계단 함수 모양이 된다. 원래 공간의 기하가 아무리 휘어 있어도 알고리즘이 보는 것은 연결 관계뿐이라서 곡률이 문제가 되지 않는 것이다.

	k-평균	스펙트럴
보는 것	중심까지의 거리	이웃 관계(그래프)
잘 되는 군집	볼록·등방·비슷한 크기	연결돼 있으면 모양 무관
주 실패 원인	초기화, 비볼록 형태	유사도 파라미터, 잡음 다리
비용	반복당 $O(nkd)$	고유분해가 지배

물론 공짜는 아니다. 두 무리 사이에 잡음 점 몇 개가 다리를 놓아 주면 그래프가 하나로 이어지고, 그러면 절단은 다리 근처에서 점 하나를 떼는 쪽으로 기울 수 있다. 비볼록 형태에 강한 대신 연결 구조를 망치는 잡음에는 오히려 취약하다 — 강점과 약점이 같은 뿌리에서 나온다.

7. 메시 분할이라는 원조 응용[편집]

이 발상은 기계학습보다 병렬 컴퓨팅에서 먼저 실용화됐다. 유한요소법 메시를 프로세스에 나눠 줄 때 통신량은 절단 간선 수이고, 부하 균형은 조각 크기가 비슷하다는 제약이다. 이 균형 그래프 분할 문제에 피들러 벡터의 부호로 자르는 스펙트럴 이분법이 1990년 전후 표준으로 자리 잡았다. 오늘날 METIS류 다단계 휴리스틱이 속도에서 이겨 실무 1순위를 넘겨받았지만, 다단계 알고리즘의 조대 레벨 초기 분할로 스펙트럴 방법이 아직 들어가 있는 구현이 흔하다. 조합 최적화·네트워크 흐름 문서의 절단 이야기와 정확히 같은 대상을 다른 언어로 보는 셈이다.³

8. 관련 문서[편집]

흔히 쓰는 경험칙은 $\sigma$ 를 각 점의 $k$ 번째 최근접 이웃까지의 거리로 국소 적응시키는 것(Zelnik-Manor & Perona, 2004)이다. 하이퍼파라미터 하나를 없애는 대신 $k$ 라는 하이퍼파라미터를 얻는다. 세상에 공짜는 없다. ↩
폰 룩스부르크(von Luxburg)의 2007년 튜토리얼이 이 분야의 사실상 표준 입문서이고, 완화의 품질 보장이 없다는 점도 거기 명시돼 있다. “잘 되는데 왜 되는지는 경우에 따라 다르다”는 서술을 논문에서 대놓고 보는 흔치 않은 경험을 할 수 있다. ↩
그래서 이 주제는 소속이 애매하다. 데이터 사이언스 수업에서는 k-평균 다음 장에 나오고, 병렬 수치해석 수업에서는 도메인 분할 장에 나온다. 같은 피들러 벡터를 한쪽은 “군집”, 다른 쪽은 “프로세스 랭크”라고 부른다. ↩