[Paper Review] GRAPH-BASED CHANGE-POINT DETECTION
이 포스팅은 H.Chen et el. (2014)의 논문 Graph-Based Change-Point Detection을 읽고 정리한 글입니다.
Introduction
변화점 탐지(Change-point Detection, CPD)는 데이터 과학에서 오래된 주제입니다. 주가가 갑자기 추세를 바꾸는 시점, 환자 생체 신호에서 리듬이 달라지는 시점, 혹은 SNS에서 팔로잉/팔로워 구조가 갑자기 재편되는 시점 등의 모든 것이 변화점 탐지 문제로 귀결됩니다.
전통적인 방법들은 평균이나 분산 같은 저차원 통계량의 변화를 봅니다(CUSUM, LRT 등). 하지만 데이터가 점점 고차원, 비정형, 복잡한 구조를 갖게 되면서 한계가 뚜렷해졌습니다. 평균/분산만으로는 “관계나 구조의 변화”를 포착하기 어렵기 때문입니다.
바로 이런 문제의식에서 Chen & Zhang (2012)은 데이터를 그래프로 표현하고, 그래프 위에서 변화점을 스캔하는 비모수적 접근을 제안합니다. 핵심은 간단하지만 효과적입니다: 비슷한 것끼리 연결해 보고, 시점을 나눴을 때 두 그룹을 잇는 간선이 얼마나 남는지 세어보자.
Motivation
이 논문의 기본 아이디어는 직관적입니다.
- 각 데이터 포인트를 그래프의 노드로 두고,
- 서로 비슷한 포인트를 엣지로 연결합니다(유사성 그래프).
- 어떤 시점 $t$을 기준으로 데이터를 과거(≤t) 와 미래(>t) 로 나눴을 때,
두 그룹을 가로지르는 엣지(경계 엣지) 가 얼마나 있는지 봅니다.
- 변화가 없다면 두 그룹은 여전히 비슷하게 섞여 있어 경계 엣지가 많습니다.
- 변화가 있다면 두 그룹의 성격이 달라져 경계 엣지가 줄어듭니다.
이 단순한 관찰을 수학적으로 정제하여, 논문은 검정 통계량과 그 근사 분포를 제시합니다.
덕분에 무거운 순열검정(permutation test) 없이도 p-value를 빠르게 계산할 수 있습니다.
※ “비모수”란 정규/포아송 등 분포 모양에 대한 파라메트릭 가정이 없다는 뜻입니다.
다만 교환가능성(exchangeability), 즉 귀무가설에서 데이터 순서가 무작위로 섞여도 분포가 같은 순열 불변성은 가정합니다.
Methodology
1) 유사성 그래프 생성
각 관측치를 노드로 두고, “가깝다/비슷하다”를 잇는 유사성 그래프 $G$를 만듭니다.
- MST(최소 신장 트리): 전체 거리 합이 최소가 되도록 $n-1$개의 엣지만 선택 (파라미터 없음, 가벼움)
- kNN 그래프: 각 점에서 가장 가까운 $k$개 이웃과 연결 (민감도/견고성 조절 가능)
- NNG(최근접 이웃): 각 점을 가장 가까운 한 점과만 연결 (간단하나 다소 취약)
- MDP(최소거리 페어링): 겹치지 않는 짝을 만들어 총 거리 최소화 (해석력은 좋지만 구현 비용이 큼)
2) 스캔 통계량 $R_G(t)$
시점 $t$에서 데이터를 과거 그룹($i \le t$)과 미래 그룹($i > t$)으로 나눕니다.
그래프에서 두 그룹을 잇는 엣지 수를 세어 다음과 같이 정의합니다.
- $R_G(t)$ 작음 → 두 그룹이 각자 더 잘 뭉침 → 변화점 후보
- $R_G(t)$ 큼 → 두 그룹이 뒤섞임 → 변화 없음에 가깝다
3) 표준화 통계량 $Z_G(t)$
시점에 따라 $R_G(t)$의 스케일이 달라지므로, 기대값/분산으로 표준화합니다.
\[Z_G(t) = -\frac{R_G(t) - \mathbb{E}[R_G(t)]}{\sqrt{\mathrm{Var}[R_G(t)]}}\]부호를 음수로 붙여 값이 클수록 변화에 대한 증거가 강해지도록 했습니다.
Key Lemmas (직관 중심 요약)
논문은 순열 귀무가설에서 $R_G(t)$의 기댓값과 분산을 닫힌형태로 제공합니다.
Lemma 2.1 (단일 변화점)
\[E[R_G(t)] = p_1(t)|G|,\quad p_1(t)=\frac{2t(n-t)}{n(n-1)}\] \[\mathrm{Var}[R_G(t)] = p_2(t)|G| + \Big(\tfrac{1}{2}p_1(t)-p_2(t)\Big)\sum_i |G_i|^2 + \big(p_2(t)-p_1^2(t)\big)|G|^2\] \[p_2(t)=\frac{4t(t-1)(n-t)(n-t-1)}{n(n-1)(n-2)(n-3)}\]- $p_1(t)$: 임의의 엣지가 서로 다른 그룹에 걸칠 확률
- $p_2(t)$: 엣지 두 개가 동시에 그룹 간에 걸칠 확률
- $|G|$: 엣지 개수, $|G_i|$: 노드 $i$의 차수(연결 수)
요지: 그래프 구조($|G|, \sum |G_i|^2$)와 시점 $t$만 알면
$R_G(t)$의 분포(평균·분산)를 계산할 수 있어, 표준화 $Z_G(t)$가 가능해집니다.
Lemma 2.3 (변화 “구간”)
변화가 한 시점이 아닌 구간 $(t_1,t_2]$ 에서 발생한다고 볼 때도 같은 아이디어로
$R_G(t_1,t_2)$, $Z_G(t_1,t_2)$를 정의하여 윈도우 길이 제약 하에 최대값을 탐색합니다.
Gaussian Process Approximation (왜 근사가 가능한가)
관심사는 결국 다음입니다.
\[P\Big(\max_t Z_G(t) > b \;\big|\; H_0\Big)\]즉, 변화가 없다고 가정할 때도 우연히 큰 $Z_G(t)$가 나올 확률(= p-value 꼬리)을 알고 싶습니다.
문제는 $Z_G(t)$들이 서로 상관되어 있어 직접 계산이 어렵다는 점입니다.
논문의 아이디어는 다음과 같습니다.
- 표본 크기 $n$이 충분히 크면 ${Z_G(t)}$는 가우시안 랜덤필드(GRF)처럼 행동합니다.
- 최대치 근처에서는 선형 기울기 + 브라운 운동 노이즈로 국소 근사할 수 있습니다.
- 그러면 문제는 확률 과정의 경계 통과(boundary crossing) 확률로 환원됩니다.
Local Slope $h^*(x)$
\[h^*(x) = \frac{1}{2x(1-x)} + \frac{2}{4x(1-x) + (1-2x)^2(r_1-4r_0)}\]여기서
$r_0 = \lim |G|/n$, $\; r_1 = \lim \frac{\sum_i |G_i|^2}{|G|}$ 는 그래프의 조밀도/허브 정도를 반영합니다.
- $h^*(x)$는 “국소적으로 값이 얼마나 빨리 흔들리는지”를 나타내는 기울기입니다.
- 허브 노드가 많고 차수 제곱합이 크면 $h^*$가 커져 작은 이동에도 $Z_G$가 크게 변동 → 탐지 민감도↑
Approximation Result (실제 p-value 근사식)
Proposition 3.4는 다음 근사를 제시합니다.
\[P\Big(\max_{n_0\le t \le n_1} Z_G(t) > b\Big) \;\approx\; b\,\phi(b)\,\int_{x_0}^{x_1} h^*(x)\,\nu\!\left(\frac{b_0}{\sqrt{2h^*(x)}}\right)\,dx\]- $\phi(b)$: 표준정규 밀도
- $\nu(\cdot)$: 경계 통과에 등장하는 보조함수(일반적으로 Siegmund–Yakir 근사 사용)
- 적분 구간 $[x_0,x_1]$은 보통 극단부(초반/후반 소수 구간)를 제외하여 안정화합니다.
Point: 그래프의 간단한 요약 통계($r_0, r_1$)와 $h^*(x)$만 알면
순열검정 없이도 유의확률을 빠르게 근사할 수 있습니다.
Practical Guide (실무 적용 가이드)
1) 전처리
- 피처 스케일이 다르면 표준화 후 거리 계산을 권장합니다.
- 고차원에서는 코사인 거리가 종종 더 안정적입니다.
- 이상치가 많다면 로버스트 거리(예: Huber, rank-based) 고려가 유리합니다.
2) 그래프 선택 가이드
-
MST: 파라미터 없고 빠름($ G =n-1$), 전체 구조를 잘 요약. 시작점으로 강추. - kNN: $k$로 민감도/견고성 조절. 대략 5~15에서 시작, 교차검증으로 조정.
- NNG: 가장 간단하나 끊김이 생길 수 있음. 데이터가 매우 조밀할 때만 권장.
- MDP: 해석은 직관적이지만 구현/비용 부담이 큼.
3) 검색 구간/윈도우
- $\max_t Z_G(t)$ 탐색 시, 극단부(예: 앞뒤 5%)를 제외하면 안정적입니다.
- 구간 변화 탐지 시에는 $[L_{\min}, L_{\max}]$ 윈도우 길이 제한을 둡니다.
4) 자기상관 대처
- 시계열 자기상관이 강하면 교환가능성 가정이 깨질 수 있습니다.
- 블록 순열(block permutation) 혹은 블록 부트스트랩으로 근사 분포를 보정합니다.
- 블록 길이는 데이터 특성(ACF, PACF, 도메인 지식)으로 정합니다.
5) 다중 변화점
- $\max_t Z_G(t)$로 하나를 검정/추정 → 구간을 분할 → 반복하는 바이너리 세그멘테이션이 실무에서 널리 쓰입니다.
- 유의수준은 Bonferroni/FDR 등으로 다중 비교 보정을 고려합니다.
Intuition Recap
- 시점 $t$마다 두 그룹을 나누고, 경계 엣지 수 $R_G(t)$를 센다.
- 그래프 구조만으로 $E, \mathrm{Var}$를 계산해 표준화 $Z_G(t)$를 만든다.
- 관심사는 $\max_t Z_G(t)$가 임계값을 넘는지(= p-value).
- 큰 $n$에서 ${Z_G(t)}$는 가우시안 랜덤필드로 근사된다.
- 국소 기울기 $h^*$ 로 경계 통과 확률을 근사한다(허브 많을수록 민감).
- 결과적으로 순열 없이도 빠른 p-value 근사가 가능하다.
Discussion
강점
- 고차원/비유클리드 데이터에도 적용 가능합니다.
- 교환가능성(Exchangeability) 만 가정하고, 분포 모양에 대한 추가 가정은 없는 비모수적 방법입니다.
- permutation test 없이도 점근적 근사 로 p-value를 계산할 수 있습니다.
한계
- 독립성/교환가능성 가정 때문에, 자기상관이 강하면 Type I error 제어가 완벽하지 않을 수 있습니다.
- 유한 표본에서는 근사 정확도가 떨어질 수 있어 보정(왜도 보정, 유한표본 보정)이 필요합니다.
- 그래프를 만들 때 유사도 정의(거리/커널, 연결 방식, $k$) 에 따라 결과가 크게 달라집니다.
→ 도메인 지식·탐색적 분석으로 합리적인 그래프를 구성하는 것이 핵심입니다.
References
- Chen, H., & Zhang, N. (2012). Graph-based change-point detection. (arXiv:1209.1625)
댓글남기기