naginterfaces.library.tsa.cp_​binary_​user

naginterfaces.library.tsa.cp_binary_user(n, beta, chgpfn, minss=2, mdepth=0, data=None)

cp_binary_user detects change points in a univariate time series, that is, the time points at which some feature of the data, for example the mean, changes. Change points are detected using binary segmentation for a user-supplied cost function.

For full information please refer to the NAG Library document for g13ne

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/g13/g13nef.html

Parameters

nint

$n$, the length of the time series.

betafloat

$\beta$, the penalty term.

There are a number of standard ways of setting $\beta$, including:

SIC or BIC

$\beta =p\times \log \left(n\right)$.

AIC

$\beta =2p$.

Hannan-Quinn

$\beta =2p\times \log \left(\log \left(n\right)\right)$.

where $p$ is the number of parameters being treated as estimated in each segment.

The value of $p$ will depend on the cost function being used.

If no penalty is required then set $\beta =0$.

Generally, the smaller the value of $\beta$ the larger the number of suggested change points.

chgpfncallable (v, cost, info) = chgpfn(side, u, w, minss, info, data=None)

$chgpfn$ must calculate a proposed change point, and the associated costs, within a specified segment.

Parameters

sideint

Flag indicating what $chgpfn$ must calculate and at which point of the Binary Segmentation it has been called.

$side=-1$

only $C\left(y_{u:w}\right)$ need be calculated and returned in $cost\left[0\right]$, neither $v$ nor the other elements of $cost$ need be set. In this case, $u=1$ and $w=n$.

$side=0$

all elements of $cost$ and $v$ must be set. In this case, $u=1$ and $w=n$.

$side=1$

the segment, $y_{u:w}$, is a left-hand side subsegment from a previous iteration of the Binary Segmentation algorithm. All elements of $cost$ and $v$ must be set.

$side=2$

the segment, $y_{u:w}$, is a right-hand side subsegment from a previous iteration of the Binary Segmentation algorithm. All elements of $cost$ and $v$ must be set.

The distinction between $side=1$ or $2$ may allow for $chgpfn$ to be implemented in a more efficient manner.

The first call to $chgpfn$ will always have $side=-1$ and the second call will always have $side=0$.

All subsequent calls will be made with $side=1$ or $2$.

uint

$u$, the start of the segment of interest.

wint

$w$, the end of the segment of interest.

minssint

The minimum distance between two change points, as passed to cp_binary_user.

infoint

$info=0$.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

vint

If $side=-1$ then $v$ need not be set.

if $side\ne -1$ then $v$, the proposed change point.

That is, the value which minimizes

$${\text{minimize}}_{v}C\left(y_{u:v}\right)+C\left(y_{v+1:w}\right)$$

for $v=u+minss-1$ to $w-minss$.

costfloat, array-like, shape $\left(3\right)$

Costs associated with the proposed change point, $v$.

If $side=-1$ then $cost\left[0\right]=C\left(y_{u:w}\right)$ and the remaining two elements of $cost$ need not be set.

If $side\ne -1$ then

$cost\left[0\right]=C\left(y_{u:v}\right)+C\left(y_{v+1:w}\right)$.

$cost\left[1\right]=C\left(y_{u:v}\right)$.

$cost\left[2\right]=C\left(y_{v+1:w}\right)$.

infoint

In most circumstances $info$ should remain unchanged.

If $info$ is set to a strictly positive value then cp_binary_user terminates with $errno$ = 51.

If $info$ is set to a strictly negative value the current segment is skipped (i.e., no change points are considered in this segment) and cp_binary_user continues as normal.

If $info$ was set to a strictly negative value at any point and no other errors occur then cp_binary_user will terminate with $errno$ = 52.

minssint, optional

The minimum distance between two change points, that is ${\tau }_i-{\tau }_{i-1}\ge minss$.

mdepthint, optional

$K$, the maximum depth for the iterative process, which in turn puts an upper limit on the number of change points with $m\le 2^K$.

If $K\le 0$ then no limit is put on the depth of the iterative process and no upper limit is put on the number of change points, other than that inherent in the length of the series and the value of $minss$.

dataarbitrary, optional

User-communication data for callback functions.

Returns

ntauint

$m$, the number of change points detected.

tauint, ndarray, shape $\left(ntau\right)$

The first $m$ elements of $tau$ hold the location of the change points. The $i$th segment is defined by $y_{({\tau }_{i-1}+1)}$ to $y_{{\tau }_i}$, where ${\tau }_0=0$ and ${\tau }_i=tau[i-1],1\le i\le m$.

Raises

NagValueError

(errno $11$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 2$.

(errno $31$)

On entry, $minss=⟨value⟩$.

Constraint: $minss\ge 2$.

(errno $51$)

User requested termination by setting $info=⟨value⟩$.

Warns

NagAlgorithmicWarning

(errno $52$)

User requested a segment to be skipped by setting $info=⟨value⟩$.

Notes

Let $y_{1:n}=\{y_j:j=1,2,\dots ,n\}$ denote a series of data and $\tau =\{{\tau }_i:i=1,2,\dots ,m\}$ denote a set of $m$ ordered (strictly monotonic increasing) indices known as change points with $1\le {\tau }_i\le n$ and ${\tau }_m=n$. For ease of notation we also define ${\tau }_0=0$. The $m$ change points, $\tau$, split the data into $m$ segments, with the $i$th segment being of length $n_i$ and containing $y_{{\tau }_{i-1}+1:{\tau }_i}$.

Given a cost function, $C\left(y_{{\tau }_{i-1}+1:{\tau }_i}\right)$, cp_binary_user gives an approximate solution to

$${\text{minimize}}_{m,\tau }\sum _{i=1}^m(C\left(y_{{\tau }_{i-1}+1:{\tau }_i}\right)+\beta )$$

where $\beta$ is a penalty term used to control the number of change points. The solution is obtained in an iterative manner as follows:

1. Set $u=1$, $w=n$ and $k=0$

2. Set $k=k+1$. If $k>K$, where $K$ is a user-supplied control parameter, then terminate the process for this segment.

3. Find $v$ that minimizes

   $$C\left(y_{u:v}\right)+C\left(y_{v+1:w}\right)$$

4. Test

   $$C\left(y_{u:v}\right)+C\left(y_{v+1:w}\right)+\beta <C\left(y_{u:w}\right)$$

5. If inequality [equation] is false then the process is terminated for this segment.

6. If inequality [equation] is true, then $v$ is added to the set of change points, and the segment is split into two subsegments, $y_{u:v}$ and $y_{v+1:w}$. The whole process is repeated from step 2 independently on each subsegment, with the relevant changes to the definition of $u$ and $w$ (i.e., $w$ is set to $v$ when processing the left-hand subsegment and $u$ is set to $v+1$ when processing the right-hand subsegment.

The change points are ordered to give $\tau$.

References

Chen, J and Gupta, A K, 2010, Parametric Statistical Change Point Analysis With Applications to Genetics, Medicine and Finance (Second Edition), Birkhäuser