| Title: | Segmentation using Optimal Partitioning and Function Pruning |
|---|---|
| Description: | A dynamic programming algorithm for the fast segmentation of univariate signals into piecewise constant profiles. The 'fpop' package is a wrapper to a C++ implementation of the fpop (Functional Pruning Optimal Partioning) algorithm described in Maidstone et al. 2017 <doi:10.1007/s11222-016-9636-3>. The problem of detecting changepoints in an univariate sequence is formulated in terms of minimising the mean squared error over segmentations. The fpop algorithm exactly minimizes the mean squared error for a penalty linear in the number of changepoints. |
| Authors: | Guillem Rigaill [aut, cre], Toby Hocking [aut], Robert Maidstone [aut], Michel Koskas [ctb], Paul Fearnhead [aut] |
| Maintainer: | Guillem Rigaill <[email protected]> |
| License: | LGPL (>= 2.1) |
| Version: | 2019.08.26 |
| Built: | 2025-03-01 04:20:19 UTC |
| Source: | https://github.com/cran/fpop |
A wrapper to a C implementation of optimal partioning with functional pruning
| Package: | fpop |
| Type: | Package |
| Title: | Segmentation using optimal partioning and functional pruning |
| Version: | 2014.7.16 |
| Depends: | methods, cghseg |
| SystemRequirements: | GNU GSL |
| Date: | 2014-02-26 |
| Author: | Guillem Rigaill |
| Maintainer: | Guillem Rigaill <[email protected]> |
| License: | LGPL (>= 2.1) |
Guillem Rigaill
Function calling the fpop algorithm, use functional pruning and optimal partioning to recover the best segmentation with respect to the L2 loss with a per change-point penalty of lambda. More precisely, this function computes the solution to argmin_m sum_i=1^n (x_i-m_i)^2 + lambda * sum_i=1^n-1 I(m_i != m_i+1), where the indicator function I counts the number of changes in the mean vector m.
Fpop(x, lambda, mini = min(x), maxi = max(x))Fpop(x, lambda, mini = min(x), maxi = max(x))
x |
A vector of double : the signal to be segmented |
lambda |
Value of the penalty |
mini |
Min value for the mean parameter of the segment |
maxi |
Max value for the mean parameter of the segment |
Named list with the following elements: input data (signal, n, lambda, min, max), path (best previous segment end up to each data point), cost (optimal penalized cost up to each data point), t.est (vector of overall optimal segment ends), K (optimal number of segments), J.est (total un-penalized cost of optimal model). To see how cost relates to J.est, see definition of J.est in the R source code for this function.
Guillem Rigaill, Toby Dylan Hocking
set.seed(1) N <- 100 data.vec <- c(rnorm(N), rnorm(N, 2), rnorm(N)) fit <- Fpop(data.vec, N) end.vec <- fit$t.est change.vec <- end.vec[-length(end.vec)] start.vec <- c(1, change.vec+1) segs.list <- list() for(seg.i in seq_along(start.vec)){ start <- start.vec[seg.i] end <- end.vec[seg.i] seg.data <- data.vec[start:end] seg.mean <- mean(seg.data) segs.list[[seg.i]] <- data.frame( start, end, mean=seg.mean, seg.cost=sum((seg.data-seg.mean)^2)) } segs <- do.call(rbind, segs.list) plot(data.vec) with(segs, segments(start-0.5, mean, end+0.5, mean, col="green")) with(segs[-1,], abline(v=start-0.5, col="green", lty="dotted"))set.seed(1) N <- 100 data.vec <- c(rnorm(N), rnorm(N, 2), rnorm(N)) fit <- Fpop(data.vec, N) end.vec <- fit$t.est change.vec <- end.vec[-length(end.vec)] start.vec <- c(1, change.vec+1) segs.list <- list() for(seg.i in seq_along(start.vec)){ start <- start.vec[seg.i] end <- end.vec[seg.i] seg.data <- data.vec[start:end] seg.mean <- mean(seg.data) segs.list[[seg.i]] <- data.frame( start, end, mean=seg.mean, seg.cost=sum((seg.data-seg.mean)^2)) } segs <- do.call(rbind, segs.list) plot(data.vec) with(segs, segments(start-0.5, mean, end+0.5, mean, col="green")) with(segs[-1,], abline(v=start-0.5, col="green", lty="dotted"))
A function to count the number of intervals and or candidate segmentation at each step of fpop (under-developpemment)
fpop_analysis(x, lambda, mini = min(x), maxi = max(x))fpop_analysis(x, lambda, mini = min(x), maxi = max(x))
x |
A vector of double : the signal to be segmented |
lambda |
Value of the penalty |
mini |
Min value for the mean parameter of the segment |
maxi |
Max value for the mean parameter of the segment |
return a list with a vector containing the position of the change-points t.est
Guillem Rigaill, Toby Dylan Hocking
Binary segmentation of p profiles using the L2 loss
multiBinSeg(geno, Kmax)multiBinSeg(geno, Kmax)
geno |
A matrix with p columns and n lines, each column is one of the profile |
Kmax |
Maximum number of change-points |
return an object with the successive change-points found by binseg t.est and the L2 cost J.est
Guillem Rigaill, Toby Dylan Hocking
This function is used by the Fpop function to recover the best segment ends from 1:n from the C output.
retour_op(path)retour_op(path)
path |
the path vector of the "colibri_op_R_c C" function |
a vector with the best segment ends.
Guillem Rigaill, Toby Dylan Hocking