gfpop Vignette

Vincent Runge

LaMME, Evry University

Quick Start

we present a basic use of the main functions of the gfpop package. More details about optional arguments are given in later sections.

We install the package from Github:

#devtools::install_github("vrunge/gfpop")
library(gfpop)

We simulate some univariate gaussian data (n = 1000 points) with relative change-point positions 0.1, 0.3, 0.5, 0.8, 1 and means 1, 2, 1, 3, 1 with a variance equal to 1.

n <- 1000
myData <- dataGenerator(n, c(0.1,0.3,0.5,0.8,1), c(1,2,1,3,1), sigma = 1)

We define the graph of constraints to use for the dynamic programming algorithm. A simple case is the up-down constraint with a penalty here equal to a classic 2 log(n).

myGraph <- graph(penalty = 2*log(n), type = "updown")

The gfpop function gives the result of the segmentation using myData and myGraph as parameters. We choose a gaussian cost.

gfpop(data = myData, mygraph = myGraph, type = "mean")
## $changepoints 
## [1]  101  289  500  796 1000
## $states 
## [1] "Dw" "Up" "Dw" "Up" "Dw"
## $forced 
## [1] FALSE FALSE FALSE FALSE
## $parameters 
## [1] 1.0060138 2.0375075 1.0043767 3.0031951 0.9710685
## $globalCost 
## [1] 961.4759

The vector changepoints gives the last index of each segment. It always ends with the length of the vector vectData.

The vector states contains the states in which lies each mean. The length of this vector is the same as the length of changepoint.

The vector forced is a boolean vector. A forced element means that two consecutive means have been forced to satisfy the constraint. For example, the “up” edge with parameter c is forced if m(i+1) - m(i) = c.

The vector parameters contains the inferred means/parameters of the successive segments.

The number globalCost is equal to the non-penalized cost, that is the value of the fit to the data ignoring the penalties for adding changes.

Some examples

Isotonic regression

The isotonic regression infers a sequence of nondecreasing means.

n <- 1000
mydata <- dataGenerator(n, c(0.1, 0.2, 0.3, 0.4, 0.6, 0.8, 1), c(0, 0.5, 1, 1.5, 2, 2.5, 3), sigma = 1)
myGraphIso <- graph(penalty = 2*log(n), type = "isotonic")
gfpop(data =  mydata, mygraph = myGraphIso, type = "mean")
## $changepoints 
## [1]  197  304  613 1000
## $states 
## [1] "Iso" "Iso" "Iso" "Iso"
## $forced 
## [1] FALSE FALSE FALSE
## $parameters 
## [1] 0.2061122 0.8932943 1.8823408 2.8072058
## $globalCost 
## [1] 990.6153

In this example, we use in gfpop function a robust biweight gaussian cost with K = 1 and the min parameter in order to infer means greater than 0.5.

Fixed number of change-points

This algorithm is called segment neighborhood in the change-point litterature. In this example, we fixed the number of segments at 3 with an isotonic constraint. The graph contains two “up” edges with no cycling.

n <- 1000
mydata <- dataGenerator(n, c(0.1, 0.2, 0.3, 0.4, 0.6, 0.8, 1), c(0, 0.5, 1, 1.5, 2, 2.5, 3), sigma = 1)
beta <- 0
myGraph <- graph(
  Edge(0, 1,"up", beta),
  Edge(1, 2, "up", beta),
  Edge(0, 0, "null"),
  Edge(1, 1, "null"),
  Edge(2, 2, "null"),
  StartEnd(start = 0, end = 2))

gfpop(data =  mydata, mygraph = myGraph, type = "mean")
## $changepoints 
## [1]  302  676 1000
## $states 
## [1] "0" "1" "2"
## $forced 
## [1] FALSE FALSE
## $parameters 
## [1] 0.4652494 1.9471578 2.8599185
## $globalCost 
## [1] 1102.467

Robust up-down with constrained starting and ending states

In presence of outliers we need a robust loss (biweight). We can also force the starting and ending state and a minimal gap between the means (here equal to 1)

n <- 1000
chgtpt <- c(0.1, 0.3, 0.5, 0.8, 1)
myData <- dataGenerator(n, chgtpt, c(0, 1, 0, 1, 0), sigma = 1)
myData <- myData + 5 * rbinom(n, 1, 0.05) - 5 * rbinom(n, 1, 0.05)
beta <- 2 * log(n)
myGraph <- graph(
         Edge("Dw", "Up", type = "up", penalty = beta, gap = 1, K = 3),
         Edge("Up", "Dw", type = "down", penalty = beta, gap = 1, K = 3),
         Edge("Dw", "Dw", type = "null", K = 3),
         Edge("Up", "Up", type = "null", K = 3),
         StartEnd(start = "Dw", end = "Dw"))
gfpop(data =  myData, mygraph = myGraph, type = "mean")
## $changepoints 
## [1]   92  300  502  800 1000
## $states 
## [1] "Dw" "Up" "Dw" "Up" "Dw"
## $forced 
## [1] FALSE  TRUE FALSE  TRUE
## $parameters 
## [1] -0.077107824  0.975014248 -0.024985752  0.994317268 -0.005682732
## $globalCost 
## [1] 1015.152

If we skip all these constraints and use a standard fpop algorithm, the result is the following

myGraphStd <- graph(penalty = 2*log(n), type = "std")
gfpop(data =  myData, mygraph = myGraphStd, type = "mean")
## $changepoints 
##  [1]   11   12   24   25   41   42   68   69   89   90   99  100  105  106  131
## [16]  132  139  140  169  174  175  184  185  186  193  194  213  214  227  238
## [31]  297  299  325  326  330  331  361  362  402  403  437  438  466  467  491
## [46]  492  581  582  583  595  597  651  652  670  673  696  697  706  709  720
## [61]  722  735  736  793  794  823  824  834  835  838  847  848  850  878  879
## [76]  910  911  951  952  963  966  985  986  993  994 1000
## $states 
##  [1] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [13] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [25] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [37] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [49] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [61] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [73] "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std" "Std"
## [85] "Std" "Std"
## $forced 
##  [1] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [25] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [37] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [49] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [61] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [73] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [85] FALSE
## $parameters 
##  [1] -0.150681111  5.891660994 -0.733449233 -5.966990428  0.287363569
##  [6] -5.183607595 -0.363942088 -5.642931862 -0.096061158  6.923131196
## [11]  0.362766787 -4.673143081  2.074130072  6.681532005  0.717550320
## [16]  7.117639212  2.024083100  6.274187113  0.679538395  3.041824908
## [21]  7.883126802  1.503497247 -4.987087608  6.086515116  1.089198913
## [26]  8.257645119  0.401047012 -4.977699011  0.725885704  2.479407365
## [31]  0.765686852  4.654889598 -0.114794135 -8.045914109  0.448551046
## [36] -5.835978305  0.150396570 -5.427916693  0.056081643  5.474625990
## [41] -0.488236041  4.345648222  0.304511493  6.105987403  0.027867884
## [46] -5.533721922  0.873428313 -4.443032425  5.026406503  0.481401781
## [51] -4.571422567  1.039477594 -4.220749769  1.150513616  4.467676563
## [56]  0.667687743 -4.534364281  1.479450359 -2.664124143  0.908319236
## [61] -4.040940779  0.580777115 -4.694629437  1.032924998  6.184086100
## [66] -0.069515106 -6.459202819 -0.002135581 -6.007793552  1.329712818
## [71] -1.237414406 -6.981677024  5.476208099 -0.001811333 -5.635442970
## [76]  0.386596796 -5.699321200  0.321029592 -5.578719601 -0.207707496
## [81]  3.642494474  0.210988182 -5.458105795  0.505108213 -5.866987729
## [86]  0.200548101
## $globalCost 
## [1] 1528.703

abs edge

With a unique "abs" edge, we impose a difference between the means of size at least 1.

n <- 10000
myData <- dataGenerator(n, c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1), c(0, 1, 0, 2, 1, 2, 0, 1, 0, 1), sigma = 0.5)
beta <- 2*log(n)
myGraph <- graph(
  Edge(0, 0,"abs", penalty = beta, gap = 1),
  Edge(0, 0,"null"))
gfpop(data =  myData, mygraph = myGraph, type = "mean")
## $changepoints 
##  [1]  1000  2000  3000  4000  5001  6000  7000  7999  9000 10000
## $states 
##  [1] "0" "0" "0" "0" "0" "0" "0" "0" "0" "0"
## $forced 
## [1] FALSE FALSE FALSE  TRUE  TRUE FALSE FALSE FALSE  TRUE
## $parameters 
##  [1] -0.013968256  1.008516013  0.001439531  2.007256663  1.007256663
##  [6]  2.007256663 -0.008589221  1.012021843 -0.015200784  0.984799216
## $globalCost 
## [1] 2480.378

Notice that some of the edges are forced, the vector forced contains non-zero values.

Exponential decay

The null edge corresponds to an exponential decay state if its parameter is not equal to 1.

n <- 1000
mydata <- dataGenerator(n, c(0.2, 0.5, 0.8, 1), c(5, 10, 15, 20), sigma = 1, gamma = 0.966)
beta <- 2*log(n)
myGraphDecay <- graph(
  Edge(0, 0, "up", penalty = beta),
  Edge(0, 0, "null", 0, decay = 0.966)
  )
g <- gfpop(data =  mydata, mygraph = myGraphDecay, type = "mean")
g
## $changepoints 
## [1]  200  500  800 1000
## $states 
## [1] "0" "0" "0" "0"
## $forced 
## [1] FALSE FALSE FALSE
## $parameters 
## [1] 0.0047770995 0.0003192705 0.0004543741 0.0196688634
## $globalCost 
## [1] 999.0326

and we plot the result

gamma <- 0.966
len <- diff(c(0, g$changepoints))
signal <- NULL
for(i in length(len):1)
  {signal <- c(signal, g$parameters[i]*c(1, cumprod(rep(1/gamma,len[i]-1))))}
signal <- rev(signal)

ylimits <- c(min(mydata), max(mydata))
plot(mydata, type ='p', pch ='+', ylim = ylimits)
par(new = TRUE)
plot(signal, type ='l', col = 4, ylim = ylimits, lwd = 3)

Graph construction

In the gfpop package, graphs are represented by a dataframe with 9 features and build with the R functions Edge, Node, StartEnd and graph.

emptyGraph <- graph()
emptyGraph
## [1] state1    state2    type      parameter penalty   K         a        
## [8] min       max      
## <0 rows> (or 0-length row.names)

state1 is the starting node of an edge, state2 its ending node. type is one of the available edge type ("null", "std", "up", "down", "abs"). penalty is a nonnegative parameter: the additional cost \(\beta_i\) to consider when we move within the graph using a edge (or stay on the same node). parameter is annother nonnegative parameter, a characteristics of the edge, depending of its type (it is a decay if type is “null” and a gap otherwise). K and a are robust parameters. min and max are used to constrain the rang of value for the node parameter.

We add edges into a graph as follows

myGraph <- graph(
  Edge("E1", "E1", "null"),
  Edge("E1", "E2", "down", 3.1415, gap = 1.5)
)
myGraph
##   state1 state2 type parameter penalty   K a min max
## 1     E1     E1 null       1.0       0 Inf 0  NA  NA
## 2     E1     E2 down       1.5       0 Inf 0  NA  NA

we can only add edges to this dataframe using the object Edge.

The graph can contain information on the starting and/or ending edge to use with the StartEnd function.

beta <- 2 * log(1000)
myGraph <- graph(
  Edge("Dw", "Dw", "null"),
  Edge("Up", "Up", "null"),
  Edge("Dw", "Up", "up", penalty = beta, gap = 1),
  Edge("Dw", "Dw", "down", penalty = beta),
  Edge("Up", "Dw", "down", penalty = beta),
  StartEnd(start = "Dw", end = "Dw"))
myGraph
##   state1 state2  type parameter  penalty   K  a min max
## 1     Dw     Dw  null         1  0.00000 Inf  0  NA  NA
## 2     Up     Up  null         1  0.00000 Inf  0  NA  NA
## 3     Dw     Up    up         1 13.81551 Inf  0  NA  NA
## 4     Dw     Dw  down         0 13.81551 Inf  0  NA  NA
## 5     Up     Dw  down         0 13.81551 Inf  0  NA  NA
## 6     Dw   <NA> start        NA       NA  NA NA  NA  NA
## 7     Dw   <NA>   end        NA       NA  NA NA  NA  NA

Some graphs are often used: they are defined by default in the graph function. To use these graphs, we specify a string type equal to "std", "isotonic", "updown" or "relevant". For example,

myGraphIso <- graph(penalty = 12, type = "isotonic")
myGraphIso
##   state1 state2 type parameter penalty   K a min max
## 1    Iso    Iso null         1       0 Inf 0  NA  NA
## 2    Iso    Iso   up         0      12 Inf 0  NA  NA

The function Node can be used to restrict the range of value for parameter associated to a node (called also a vertex). For example the following graph is an isotonic graph with inferred parameters between 0 et 1 only.

myGraph <- graph(
  Edge("Up", "Up", "up", penalty = 3.1415),
  Edge("Up", "Up"),
  Node("Up", min = 0, max = 1)
  )
myGraph
##   state1 state2 type parameter penalty   K  a min max
## 1     Up     Up   up         0  3.1415 Inf  0  NA  NA
## 2     Up     Up null         1  0.0000 Inf  0  NA  NA
## 3     Up     Up node        NA      NA  NA NA   0   1

Supplementary R functions

Data generator function

the dataGenerator function is used to simulate n data-points from a distribution of type equal to "mean", "poisson", "exp", "variance" or "negbin". Standard deviation parameter sigma and decay gamma are specific to the Gaussian mean model. size is linked to the R rnbinom function from R stats package.

Standard deviation estimation

We often need to estimate the standard deviation from the observed data to normalize the data or choose the edge penalties. The sdDiff returns such an estimation with the default HALL method [Hall et al., 1990] well suited for time series with change-points.

Back to Top