[논문 리뷰] : Selective review of offline change point detection methods - (1) 변화점 탐지와 비용함수

C. Truong, L. Oudre, N. Vayatis. Selective review of offline change point detection methods. Signal Processing, 167:107299, 2020. [journal] [pdf]

 

  이 논문은 다변량 시계열에서 여러 변경점을 오프라인으로 감지하는 알고리즘에 대한 선별적인 검토를 제공합니다. 변경점을 찾는 방법론은 광범위한데 저자들은 이 광범위한 연구 분야를 세 가지 핵심 요소를 기반으로 설명하고 있습니다. 선별적인 검토인 이유는 해당 구조를 따르지 않는 방법론은 제외되었기 때문이며 이는 한계에도 언급되어 있습니다. 해당 논문은 비용함수 기반의 최적화 문제로 변경점을 찾지만  베이즈(Bayesian) 기반의 접근법의 경우 확률적 추론으로 변경점을 찾기 때문에 제외되었습니다. 

 

  세 가지 핵심 요소는 (1) 비용함수(cost function), (2) 탐색 방법(search method), 그리고 (3) 변경점에 대한 제약(constraint on the number of changes)으로 구성됩니다.  각 요소 별 상세 내용이 자세히 기술되어 있어 하나의 글로 담기에는 내용이 많아 주요 요소 별로 나눠서 리뷰를 진행한 후, 해당 알고리즘이 구현된 파이썬 패키지 Ruptures 로 어떻게 적용되는지 살펴보고자 합니다. 

 

 

문제 정의

변화점 탐지는 다변량 비정상 시그널 $y = \{y_1, \dots, y_T\}$에서 특성의 급격한 변화가 발생하는 알 수 없는 시점을 추정하는 것을 목표로 합니다. 즉, 최적의 분할 $\mathcal{T}$ 를 찾기 위해 정량적 기준이 되는 비용함수 $V(\mathcal{T}, y)$를 최소화하고자 합니다.

$V(T, y) := \sum_{k=0}^{K^*} c(y_{t_k} .. t_{k+1})$

• V(T,y): 특정 분할 T와 시그널 y에 대한 전체 기준(criterion) 값입니다. 이 값을 최소화하는 것이 목표입니다.
• T: 추정된 변화점 인덱스들의 집합입니다. 예를 들어, $\mathcal{T} = \{t_1, t_2, \dots, t_K\}$와 같이 표현될 수 있습니다. 여기서 K는 추정된 변화점의 개수입니다.
• y: 전체 시그널 데이터입니다.
• K: 추정된 변화점의 개수입니다.
• k: 세그먼트를 나타내는 인덱스입니다. k=0부터 K까지 존재하므로 총 K+1개의 세그먼트가 됩니다 (변화점이 3개면 세그먼트는 4개).
• c(⋅): 비용 함수(cost function)로, 주어진 서브 시그널이 얼마나 동질적인지(homogeneous)를 측정합니다. 서브 시그널이 동질적이면 c(⋅) 값은 낮고, 변화점을 포함하여 이질적이면 c(⋅) 값은 높게 나옵니다.
• $y_{t_k .. t_{k+1}}$: 인덱스 $t_k$부터 $t_{k+1}$까지의 서브 시그널을 의미합니다.

 

문제 유형

변화점 탐지 문제는 크게 두 가지 문제로 나뉩니다. 알려진 변화점 개수를 알고 있는가, 알지 못하는가. 

유형에 따라서 사용 가능한 알고리즘이 다르게 나타나기 때문에 내가 마주한 문제에서 변화점이 명확하게 정해져 있는지 알 수 없는지 정의해야 합니다. 하지만 보통 실제 데이터 분석에서는 변화점 개수를 알 수 없는 상황을 더 흔하게 마주하게 됩니다. 정확히 몇 개의 변화점이 있을지, 심지어 변화점이 아예 없을지는 데이터 분석을 수행하기 전에는 알 수 없습니다. 예를 들어, 공정 모니터링에서는 기계 고장이 몇 번 발생할지, 금융 데이터에서는 시장 추세 변화가 몇 번 일어날지 사전에 알기 어렵습니다.

• 문제 1 (P1): 변화점 개수 K를 알고 있을 때
  
  • 목표: 정해진 K개의 변화점을 갖는 분할 T 중에서 V(T)를 최소화
  • 수식:  $\min_{|T|=K} V(T)$
    • 참고
      • |T| : "변화점 인덱스의 집합 T가 정확히 K개의 원소(즉, K개의 변화점)를 가져야 한다”
      • |집합| : 집합에 쓰이면 그 집합 안에 포함된 원소의 개수를 의미
• 문제 2 (P2): 변화점 개수를 알 수 없을 때
  
  • 목표: V(T)와 분할의 복잡성을 나타내는 페널티(penalty) 항 pen(T)의 합을 최소화. 
  • 수식:  $\min_T V(T) + \text{pen}(T)$
    • 이 페널티는 변화점의 개수가 너무 많아지는 것을 방지하여 과적합(overfitting)을 막는 역할을 합니다.
    • 첫번째 항인 V(T)는 모델이 데이터에 얼마나 잘 맞는지를 측정합니다. 변화점은 세그먼트 길이가 짧을수록 동질성을 갖게 되어 V(T)가 낮아지는데, 모든 포인트 사이 변화점을 넣으면 0에 가까워지기 때문에 이를 방지하고자 패널티항을 추가하여 모델이 복잡해지는 것을 막습니다. 
    • 변화점의 개수가 많아질수록 모델은 더 복잡해지고, 따라서 pen(T) 값은 커지게 되므로 최소를 만들기 위해 모델의 복잡성을 무조건 키울 수 없게 되므로 데이터에 잘 맞으면서도(낮은 V(T)), 불필요하게 복잡하지 않은(낮은 pen(T)) 모델을 찾도록 유도합니다.

 

변화점 탐지 알고리즘의 3가지 핵심 요소

비용함수 (Cost Function)

• 주어진 시그널 구간이 얼마나 '동질적인지'를 측정하는 함수로 구간을 분할하는 기준이 됩니다. 
• 구간 내에 변화점이 없으면(동질적이면) 낮은 값을 반환하고, 변화점이 포함되어 있으면(이질적이면) 높은 값을 반환하도록 설계됩니다.
• 그래서 구간 내 동질적인 값을 가져 각 구간의 합이 최소가 되도록 변화점을 탐지하게 되면 변화가 뚜렷하게 구간이 나뉘게 됩니다.
• 데이터의 어떤 변화(예: 평균의 변화, 분산의 변화, 분포의 변화 등)를 탐지할 것인지에 따라 적절한 비용 함수를 선택해야 합니다.

탐색 방법(Search Method)

• 변화점 탐지 문제를 해결하기 위한 최적화 절차를 의미합니다. 이 문제는 시그널을 여러 세그먼트로 나누는 이산 최적화 문제입니다.
• 이 논문에서 정의한 문제 1 (P1: 변화점의 개수가 알려진 경우) 또는 문제 2 (P2: 변화점의 개수가 알려지지 않은 경우)를 정확하게 풀거나, 근사적으로 풀 수 있는 다양한 방법들이 있습니다.
• 각 탐색 방법은 계산 복잡도와 정확도 사이의 trade-off가 있습니다. 일부 방법은 정확한 해를 찾지만 계산 비용이 높고, 다른 방법은 빠른 대신 근사적인 해를 제공합니다. 상황에 맞춰 적절한 탐색 방법을 선택해야 합니다. 

변화점 개수에 대한 제약 (Constraint on the number of change points)

• 변화점의 개수가 미리 알려져 있지 않은 문제 2 (P2)를 해결할 때, 과도한 변화점을 탐지하거나 너무 적은 변화점을 탐지하는 것을 방지하기 위해 추가되는 제약 조건입니다.
• 주로 '복잡성 페널티' 형태로 주어지며, 모델의 복잡도(즉, 변화점의 개수)에 비례하여 패널티를 부여합니다. 
• 페널티의 크기에 따라 탐지되는 변화점의 수가 달라집니다. 페널티가 너무 작으면 노이즈로 인한 사소한 변화까지 모두 탐지할 수 있고, 페널티가 너무 크면 가장 중요한 변화점조차 놓칠 수 있습니다.

 

비용함수(Cost Function)

비용 함수는 주어진 신호 세그먼트가 특정 모델에 얼마나 잘 맞는지, 즉 얼마나 구간 내 데이터가 균질한지를 측정하는 척도로써 작동하며 두 가지 범주로 나뉩니다. 

• Parametric models: 신호의 통계적 분포가 특정 매개변수(parameter)에 의해 정의된다고 가정하는 모델입니다. 예를 들어, 신호가 가우시안 분포를 따른다고 가정하고 평균이나 분산의 변화를 탐지하는 경우가 이에 해당합니다.
• Non-parametric models: 신호의 통계적 분포에 대한 특정 가정을 하지 않고, 데이터 자체의 특성이나 관계를 통해 변화를 탐지하는 모델입니다. 이는 더 일반적인 유형의 변화를 탐지할 수 있게 합니다.

 

매개변수적 모델 (Parametric Models)

• 정의 
  • 이 모델들은 데이터가 특정 통계적 분포(예: 가우시안, 포아송)를 따른다고 가정하며, 이 분포의 유한한 수의 파라미터(예: 평균, 분산)의 변화를 감지하는 데 중점을 둡니다.
• 장점
  • 가정한 분포를 데이터가 따른다면 적은 데이터로 정확한 결과를 얻을 수 있으며 비용이 적게 들어 빠르게 처리 가능합니다. 
  • 변화가 특정 매개변수(예: 평균이 5에서 10으로 변했다, 분산이 두 배로 커졌다)의 변화로 명확히 설명되므로, 변화의 원인 분석 및 해석이 용이합니다.
• 단점
  • 데이터가 가정한 확률 분포를 따르지 않으면 성능이 크게 저하되어 신뢰성이 떨어지게 됩니다. 
  • 가정된 매개변수로 설명되지 않는 복잡한 형태의 변화는 탐지하기 어렵습니다.
• 관련 비용 함수
  • Maximum likelihood estimation (최대 우도 추정)
    • Maximum Likelihood Estimation(최대 우도 추정, MLE)은 주어진 데이터가 발생할 확률을 최대화하는 방식으로 통계 모델의 파라미터를 추정하는 방법입니다. 
    • 각 세그먼트 내에서는 데이터가 하나의 통계적 모델을 따른다고 가정합니다. 예를 들어, 한 세그먼트에서는 평균이 5인 정규 분포를 따르다가, 다음 세그먼트에서는 평균이 10인 정규 분포로 변하는 경우가 해당됩니다.
    • MLE의 핵심은 관측된 데이터를 가장 잘 설명하는 모델 파라미터(예: 평균, 분산)를 찾는 것입니다. '가장 잘 설명한다'는 것은 해당 파라미터 하에서 관측된 데이터가 나타날 '확률(우도)'이 가장 높다는 의미입니다. 변화점 탐지에서 만약 어떤 구간이 동질적이라면, 그 구간의 데이터는 하나의 모델(그리고 그 모델의 파라미터)에 아주 잘 맞을 것(fit)이고 MLE를 통해 계산된 우도(likelihood)는 높게 나타날 것입니다. 반대로, 만약 어떤 구간이 변화 시점을 포함하고 있다면, 이 구간의 데이터를 하나의 모델로 설명하려고 하면 적합도가 떨어져 MLE를 통해 계산된 우도가 낮게 나타날 것입니다. 즉, 구간 내 데이터가 동질적이면 우도가 높게 나타나고 이질적이면 우도가 낮게 나타나기 때문에 총 비용 V(T, y)을 최소화하는 문제인 변화점 탐지에서는  '음의 로그 우도(negative log-likelihood)'를 비용 함수로 사용합니다. 
    • \(c_{\text{i.i.d.}}\): 독립 항등 분포(i.i.d.)를 따르는 데이터에 대한 일반적인 최대 우도 비용 함수입니다.
      • 수식 
        • \[c_{i.i.d.}(y_{a..b}) := -\sup_{\theta} \sum_{t=a+1}^{b} \log f(y_t | \theta)\]
      • 이 수식은 "어떤 주어진 확률 분포 f(yt|θ)에 대해, 그 분포의 파라미터 θ를 최적화(supremum, 즉 우도를 최대화)했을 때 얻어지는 로그 우도의 음수 값"을 비용으로 정의하고 있으며, 여기서 f(yt|θ)는 어떤 특정 확률 분포 함수를 가정하느냐에 따라 달라집니다. θ는 그 분포의 파라미터(예: 평균, 분산, 비율 등)를 의미하며, 해당 파라미터가 어떤 것이냐 즉, 어떤 분포를 가정하느냐에 따라 cL2, cΣ, cPoisson 비용함수가 유도됩니다. 
    • \(c_{L_2}\): 제곱 오차 손실 함수로도 불리며 데이터의 평균 변화를 감지하는 데 특화된 비용 함수입니다. 
      • 수식: \(c_{L_2}(y_{a..b}) := \sum_{t=a+1}^{b} \|y_t - \bar{y}_{a..b}\|_2^2\)
      • 각 항의 의미
        •  \(c_{L_2}(y_{a..b})\): \(a\)부터 \(b\)까지의 서브-시그널 \(y_{a..b}\)에 대한 \(L_2\) 비용 함수 값으로, 이 값은 해당 구간이 얼마나 균일한지를 측정
        •  \(y_t\): 서브-시그널 \(y_{a..b}\) 내의 \(t\)번째 데이터 샘플
        •  \(\bar{y}_{a..b}\): 서브-시그널 \(y_{a..b}\)의 경험적 평균으로, 구간 \([a+1, b]\) 내의 모든 \(y_t\) 값들의 평균
        •  \(\| \cdot \|_2^2\): 유클리드 노름(Euclidean norm)의 제곱으로, 두 벡터 사이의 유클리드 거리의 제곱. 여기서는 각 데이터 샘플 \(y_t\)와 해당 서브-시그널의 평균 \(\bar{y}_{a..b}\) 사이의 차이의 제곱을 의미
        •  \(\sum_{t=a+1}^{b}\): \(t=a+1\)부터 \(b\)까지의 모든 데이터 샘플에 대해 뒤따르는 항을 합산하라는 의미
      • 데이터가 다변량 정규 분포를 따를 때 사용하며, \(y_{a..b}\) 내의 각 데이터 포인트가 해당 구간의 평균으로부터 얼마나 떨어져 있는지를 측정하는 방식입니다.
        • 만약 구간 \(y_{a..b}\)가 균일하다면, 모든 데이터 포인트가 구간 평균에 가깝게 분포할 것이므로 \(c_{L_2}\) 값은 작게 나타납니다.
        • 반대로, 만약 구간 \(y_{a..b}\) 안에 변화점이 있다면, 데이터 포인트들이 평균으로부터 멀리 떨어져 있을 것이므로 \(c_{L_2}\) 값은 커지게 됩니다.
      • 장점 : 계산이 매우 빠르고 안정적이며 평균 변화에 매우 민감합니다. 
      • 단점 : 제곱으로 계산하기 때문에 이상치에 약하며 분산이 바뀌는 변화에는 둔감합니다. 
    • \(c_{\Sigma}\): 평균과 분산(혹은 공분산)의 변화를 동시에 감지하는 데 사용되는 비용 함수입니다.
      • 수식 : \[
        c_{\Sigma}(y_{a\dots b}) := (b - a) \log \det \hat{\Sigma}_{a\dots b} + \sum_{t=a+1}^{b} (y_t - \bar{y}_{a\dots b})^{\prime} \hat{\Sigma}_{a\dots b}^{-1} (y_t - \bar{y}_{a\dots b})
        \]
      • 평균뿐 아니라 변동성(variance)이나 상관구조(correlation) 변화가 중요할 때 주로 사용합니다.
    • \(c_{\text{Poisson}}\): 포아송 분포를 따르는 카운트 데이터의 발생률(rate parameter) 변화를 감지하는 비용함수입니다.
      • 수식 :$c \operatorname{Poisson}(y_{a..b}) := -(b-a)\bar{y}{a..b} \log \bar{y}{a..b}$
      • 결함 건수, 클릭수, 콜 수, 이벤트 발생 횟수처럼 정수 카운트의 레벨이 변화했을 때 사용합니다.
  • Multiple linear model (다중 선형 모델)
    • 시계열 데이터 내의 선형 회귀 관계(종속 변수와 독립 변수 간의 관계)가 변하는 경우를 탐지하는 방법입니다. 
    • \(c_{\text{linear}}\): 선형 회귀 모델에서 잔차(residuals)의 제곱합을 최소화하는 비용 함수입니다.
      • 수식 : \[
        c_{\text{linear}}(y_{a..b}) := \min_{u \in \mathbb{R}^p, v \in \mathbb{R}^q} \sum_{t=a+1}^{b} (y_t - x'_t u - z'_t v)^2.
        \]
    • \(c_{\text{linear}, L_1}\): 잔차의 절댓값 합을 최소화하는 비용함수입니다.
      
      • 수식 : \[
        c_{\text{linear},L_1}(y_{a..b}) := \min_{u \in \mathbb{R}^p, v \in \mathbb{R}^q} \sum_{t=a+1}^b |y_t - x'_t u - z'_t v|.
        \]
      • 이상치(outliers)나 헤비 테일(heavy-tailed) 노이즈에 더 강인합니다.
    • \(c_{AR}\): 자기회귀(autoregressive, AR) 모델의 계수 변화를 감지하는 비용함수입니다.
      • 수식 : \[
        c_{AR}(y_{a..b}) := \min_{u \in \mathbb{R}^p} \sum_{t=a+1}^b \|y_t - x'_t u\|^2
        \]
  • Mahalanobis-type metric (마할라노비스 유형 거리)
    • 데이터의 상관 관계를 고려하여 평균 변화를 감지하는 데 사용되는 거리 측정 방식입니다.
    • \(c_M\): 마할라노비스 유사-노름(pseudo-norm)을 사용하여 평균 변화를 측정하는 비용 함수입니다. 
    • 수식 : \[
      c_M (y_{a\dots b}) := \sum_{t=a+1}^{b} \left\|y_t - \bar{y}_{a\dots b}\right\|^2_M
      \]

 

비매개변수적 모델 (Non-parametric Models)

• 정의 
  • 데이터의 특정 확률 분포를 가정하지 않는 대신, 경험적 누적 분포 함수(empirical cumulative distribution function), 순위 통계량(rank statistics) 또는 커널(kernel) 추정 등을 활용하여 변화를 탐지합니다.
  • 여기서 변화는 데이터의 전체적인 분포 특성이 변하는 것을 의미합니다.
• 장점
  • 데이터의 실제 분포에 대한 가정을 하지 않으므로, 다양한 종류의 데이터와 예상치 못한 복잡한 변화에도 잘 작동합니다. 평균, 분산뿐만 아니라 왜도(skewness), 첨도(kurtosis) 또는 분포의 형태(예: 단봉 분포에서 이봉 분포로의 변화) 의 분포 변화도 탐지 가능합니다. 
• 단점
  • 경험적 분포 함수나 커널 계산 등은 일반적으로 매개변수 모델보다 복잡하기 때문에 계산 비용이 높을 수 있습니다. 
  • 변화가 발생했다는 것은 알지만, 그 변화가 데이터의 어떤 통계적 특성(예: 평균, 분산)에 기인한 것인지 직관적으로 이해하고 이를 설명하기가 어렵습니다.
• 관련 비용 함수 
  • Non-parametric maximum likelihood
    
    • $c_{\hat{F}}$ : 데이터의 특정 확률 분포(예: 가우시안 분포, 푸아송 분포)를 가정하지 않고, 데이터의 경험적 분포(empirical cumulative distribution function, ecdf)에 기반한 비모수 비용함수입니다.
    • 수식 : $c_{\hat{F}}(y_{a..b}) := -(b-a) \sum_{u=1}^{T} \frac{\hat{F}{a..b}(u) \log \hat{F}{a..b}(u) + (1 - \hat{F}{a..b}(u)) \log(1 - \hat{F}{a..b}(u))}{(u - 0.5)(T - u + 0.5)}$
    • cF 비용 함수는 데이터의 경험적 분포 즉, 관측된 데이터로부터 직접 계산하여 얻은 분포를 사용하기 때문에 데이터 자체의 특성을 반영합니다. 그렇기에 다양한 종류의 데이터와 분포에 유연하게 적용될 수 있다는 장점이 있습니다.
    • 하지만 그만큼 높은 계산 비용을 요구하여 이 방법의 계산 효율성을 높이거나, 커널(kernel) 기반 방법 등 다른 비모수적 접근 방식을 사용하여 보다 효율적으로 분포 변화를 감지하는 방향으로 발전했습니다. 
  • Rank-based detection
    • $c_{\operatorname{rank}}$ : 데이터 샘플을 rank로 대체하여 구간 내 동질성을 평가하는 비모수 비용함수입니다. 
    • 원본 데이터 값 대신 순위(rank)를 사용하여 통계량을 도출합니다. 데이터 샘플을 상대적인 순위로 대체하기 때문에 데이터가 정규분포와 같은 특정 분포를 따르지 않거나 이상치에 강인한 변화점 탐지가 필요할 때 유용합니다.
    • 수식 : \[
      c_{\operatorname{rank}}(y_{a..b}) := -(b-a) \bar{\vec{r}}'_{a..b} \hat{\Sigma}^{-1} \bar{r}_{a..b}
      \]
  • Kernel-based detection 
    
    • $c_{\text{kernel}}$ : 원본 신호를 reproducing kernel Hilbert space (rkhs)로 매핑하여 비모수 변화 감지를 수행합니다.
    • 수식 : \[
      c_{\text{kernel}}(y_{a..b}) := \sum_{t=a+1}^{b} \left\| \phi(y_t) - \bar{\mu}_{a..b} \right\|_{\mathcal{H}}^2
      \]

 

분류	구분	비용 함수	주요 탐지 대상	아이디어	적합한 상황
모수적 (Parametric)	최대 우도 (MLE)	cL2​​	평균 (Mean)	세그먼트 평균 대비 제곱오차 합	가우시안 + 평균 변화
		cΣ​	평균 및 분산	공분산 구조까지 포함한 likelihood	변동성 변화 포함 시
		cPoisson​	발생률 (Rate)	포아송 우도 기반	이벤트·카운트 데이터
	선형 모델	clinear​	회귀 계수	잔차 제곱합(RSS)	선형 관계 변화
		clinear, l1	회귀 계수	잔차 절댓값 합	이상치 존재
		cAR​	자기상관 계수	자기회귀 구조 변화	시계열 상관 강함
	거리 기반	cM​	평균 (상관성 고려)	Mahalanobis 거리	변수 간 상관 존재
비모수적 (Non-parametric)	분포/순위	cF	전체 분포 (CDF)	경험적 CDF 차이	분포 형태 미상. 분포의 모양 자체가 변하는 지점 탐지
		crank​	순위 데이터	값 대신 순위 사용	이상치 존재. 스케일 불변
	커널 기반	ckernel​	고차원 특징 변화	특징 공간 평균 차이	복잡하고 비선형적인 분포 변화 감지
		crbf​	고차원 특징 (RBF)	가우시안 커널	가우시안 커널을 통한 유연한 탐지

결론적으로, 매개변수적 모델은 데이터의 분포에 대한 사전 가정이 있고, 평균이 변화하는 것과 같이 탐지하고자 하는 변화의 유형이 명확하며, 계산 효율성이 중요할 때 적합합니다. 반면, 비매개변수적 모델은 데이터 분포에 대한 사전 지식이 없거나, 복잡한 유형의 변화를 탐지해야 할 때, 계산 비용보다 유연성과 강건성이 더 중요할 때 적합합니다. 그렇기에 실제 적용 시에는 데이터의 특성, 분석 목표, 그리고 계산 자원  등을 고려하여 적절한 모델을 적용하는 것이 중요합니다.

 

데이터로 변화점 탐지 과정 이해하기 

사실 수식만으로는 변화점 탐지 과정이 직관적으로 이해가 되지 않을 수 있습니다. 그래서 데이터 기반으로 어떻게 변화점이 탐지되는지 살펴보겠습니다. 쉬운 이해를 위해 평균 변화(mean shift)를 예시로 해서 구간을 다르게 나눴을 때 비용값이 어떻게 달라지는지, 왜 변화점이 특정 위치로 잡히는지 알아보겠습니다. 

 

다음과 같은 1차원 시계열을 가정해 봅시다.

y = [5, 4, 6, 5, 5, 9, 11, 10, 10, 9]

구간 평균으로부터 얼마나 퍼져 있는가를 중심으로 변화점 탐지하기 위해 비용함수로 $c_{L_2}$ 사용합니다.

$c_{L_2}(y_{a..b}) = \sum_{t=a+1}^{b} (y_t - \bar{y}_{a..b})^2$

언뜻 봐서 가운데 부분에서 극명하게 데이터가 변화했는데요. 

후보로 t=4, 5, 6을 뽑아 해당 변화점으로 구간을 나눴을 때 비용함수로 계산된 비용이 어떻게 변화되었는지 살펴보겠습니다.

 

✅ 후보 1) τ = 4

(1) 구간1 : [5, 4, 6, 5]

• 평균 $\bar{y_1}=5$
• $c_1=(0^2+(-1)^2+1^2+0^2)=2$

(2) 구간2 : [5,9,11,10,10,9]

• 평균 $\bar{y_2}=9$
• $c_2=(-4)^2+0^2+2^2+1^2+1^2+0^2=16+0+4+1+1+0=22$

총 비용 $V(4)=2+22=24$

✅ 후보 2) τ = 5

(1) 구간1: [5,4,6,5,5]

• 평균 $\bar{y_1}=5$
• $c_1=0^2+(-1)^2+1^2+0^2+0^2=2$

(2) 구간2: [9,11,10,10,9]

• 평균 $\bar{y_2}=9.8$
• $c_2=(-0.8)^2+(1.2)^2+(0.2)^2+(0.2)^2+(-0.8)^2
  =0.64+1.44+0.04+0.04+0.64=2.8$

총비용 $V(5)=2+2.8=4.8$

✅ 후보 3) τ=6

(1) 구간1: [5,4,6,5,5,9]

• 평균 $\bar{y_1}=\frac{34}{6}\approx 5.667$
• $c_1=\frac{46}{3}\approx 15.33$

(2) 구간2: [11,10,10,9]

• 평균 $\bar{y_2}=10$
• $c_2=1^2+0^2+0^2+(-1)^2=2$

총비용 $V(6)\approx 15.33+2=17.33$

결론: 최적 변화점은 “총비용이 최소인 τ”

 

• V(4)=24
• V(5)=4.8 <--최소
• V(6)≈17.33

실제 데이터를 통해 알 수 있듯이, 구간을 나눌 때 이질적인 데이터가 섞이면 비용함수​가 커지고 진짜 변화점에서는 각 구간이 동질적이라 비용이 최소가 됩니다. 다시 한번 정리하자면, 구간의 성질이 같을 때 비용이 최소가 되도록 함으로써 변화점을 탐지하는 기법이 바로 변화점 탐지입니다. 

 

 

비용 함수 선택이 중요한 이유

비용 함수의 선택은 데이터에서 어떤 유형의 변화(예: 평균의 변화, 분산의 변화, 선형 회귀 관계의 변화, 전체 분포의 변화 등)를 찾을 것인지를 결정하는 역할을 합니다. 평균 변화에 적합한 비용함수, 분산 변화에 적합한 비용함수가 다르기 때문에 어떤 종류의 변화를 찾을 것인지에 따라 알맞은 비용 함수를 선택해야 효과적으로 변화점을 탐지할 수 있습니다. 잘못된 비용 함수는 노이즈를 변경점으로 오인하거나, 실제 중요한 변경점을 놓치게 만들 수 있습니다. 또한, 비용 함수의 형태에 따라 필요한 계산량과 복잡성이 달라집니다. 간단한 대수 연산으로도 계산되는 비용함수도 있지만 복잡한 통계적 계산을 요구하는 비용함수도 있습니다. 결론적으로 비용 함수는 변화점 탐지 알고리즘이 '무엇'을 목표로 탐색할 것인지를 규정하는 나침반과 같은 역할을 하기 때문에 어떤 비용함수를 선택할 것인지가 변화점 탐지 기법에서 중요한 요소로 작용됩니다.