ChangePointDetection.jl
A fast Julia implementation of the least square density difference (LSDD) method. It is used to detect changepoints in time-series or to infer wether or not two time-series come from the same underlying probability distribution. The LSDD method was developped in the article Density-difference estimation from M. Sugiyama, T. Suzuki, T. Kanamori, M. C. du Plessis, S. Liu, and I. Takeuchi. in 2013.
Given two time-series and
produced by underlying probability densities
and
, the LSDD method directly modelizes the difference
to compute its L2 norm. This approach has good convergence properties and is more accurate than computing the KL-divergence of
and
after estimating them from scratch.
In practice, the closer the LSDD value is to 0, the more similar and
are. To estimate changepoints in a time-series, two sliding windows are used. The LSDD value of these two sliding windows is computed along the whole time-series. Spikes in the obtained LSDD "profile" indicate potential changepoints. The procedure is best understood graphically :
One ends up with a time-dependant LSDD "profile", and threshold can be set to detect changepoints when exceeded.
Usage :
To infer if two time-series come from the same underlying probability density, use the lsdd(ts1, ts2) function :
lsdd(x::Array{Float64,1}, y::Array{Float64,1}; folds = 5, sigma_list = nothing, lambda_list = nothing)
Input :
'x', 'y' : the time-series of data upon which to perform the lsdd computation.
folds : the number of cross-validation tests. higher is more precise but more expensive.
sigma_list, lambda_list : points defining the grid search during the optimization of gaussian kernels.
Returns :
L2 : lsdd value.
To compute the LSDD profile of a time-series, use the lsdd_profile(ts; window = 70) function :
lsdd_profile(ts; window = 70)
Input :
`ts` : the time-series to analyze
window : the size of the sliding windows used for the lsdd computation. Bigger windows will be more accurate but can rapidly become very cumputationally expensive.
Returns : lsdd profile of the input time-series. Note that since we are using 2 sliding windows, only time steps [1:end-2*window] are actually taken in account.
Finally, to run an automatized changepoint detection, you can use the changepoints(ts; threshold = 0.5, window = 150) function.
Input
ts : time-series to analyse
threshold : when exceeded, a changepoint is detected
window : size of the sliding windows;
Returns : a 1-D array of all detected change points.
Example :
The following code
using Plots
ts1 = rand(500)
ts2 = 1.5 * rand(500) .+ 1
ts = vcat(ts1, ts2)
profile = lsdd_profile(ts; window = 50)
points = getpoints(profile)
a = plot(ts,xlabel = "Time steps",ylabel = "Value",label = "",title = "Random time-series with change point",color = "black")
b = plot(profile,xlabel = "Time steps",ylabel = "LSDD value",label = "lsdd",title = "Corresponding LSDD profile",color = "black")
vline!(b,points,label = "detected changepoint \n (threshold exceeded)",color = "red",lw = 3,linestyle = :dash)
p = plot(a, b, layout = (2, 1), legend = true)
display(p)
Produced the following output :
