Segmenting Piecewise Linear Time Series

Description
<b id="docs-internal-guid-97cfcc2e-2d3b-0c59-2838-a02b6a9f8ae6"></b><p dir="ltr"><span style="color: #000000;background-color: transparent;">Many interesting time series can be represented as a piecewise combination of linear functions, where each segment corresponds to a specific dynamical behavior. For example, the time series of an aircraft’s altitude plotted at regular intervals from takeoff to landing would, roughly speaking, include distinct and distinguishable phases such taxi, takeoff, ascent, cruise, descent, and landing. We need an algorithm that performs this segmentation automatically, in an unsupervised fashion.</span></p><br/><span style="color: rgb(0, 0, 0);background-color: transparent;">As input, the algorithm must take a multidimensional timeseries, and number of segments to classify. The input timeseries consists of an array of length </span><span style="color: rgb(0, 0, 0);background-color: transparent;"><i>T</i></span><span style="color: rgb(0, 0, 0);background-color: transparent;">, where </span><span style="color: rgb(0, 0, 0);background-color: transparent;"><i>T</i></span><span style="color: rgb(0, 0, 0);background-color: transparent;"> is the number of samples. Each sample consists of a </span><span style="color: rgb(0, 0, 0);background-color: transparent;"><i>D</i></span><span style="color: rgb(0, 0, 0);background-color: transparent;"> dimensional vector of real valued numbers. In JSON this is represented by:</span><br/><span style="color: #000000;background-color: transparent;"></span><div><ul><li><font color="#000000"><span id="docs-internal-guid-97cfcc2e-2d3b-6755-755c-c16c11c4b19b"><span style="color: rgb(0, 0, 0);background-color: transparent;">A </span><span style="color: rgb(0, 0, 0);background-color: transparent;"><i>T</i></span><span style="color: rgb(0, 0, 0);background-color: transparent;">x</span><span style="color: rgb(0, 0, 0);background-color: transparent;"><i>D</i></span><span style="color: rgb(0, 0, 0);background-color: transparent;"> array of arrays</span></span><br/></font></li><li><font color="#000000"><span><span style="color: rgb(0, 0, 0);background-color: transparent;"><span id="docs-internal-guid-97cfcc2e-2d3b-b0c8-1f45-3d55a7a12072"><span style="color: rgb(0, 0, 0);background-color: transparent;">An integer </span><span style="color: rgb(0, 0, 0);background-color: transparent;"><i>N</i></span><span style="color: rgb(0, 0, 0);background-color: transparent;"> which is the number of segment to classify</span></span></span></span></font></li></ul><div><b id="docs-internal-guid-97cfcc2e-2d3c-1dd0-0ca0-12a6726acdd1"></b><p dir="ltr"><span style="color: #000000;background-color: transparent;">The output should consist of a length </span><span style="color: #000000;background-color: transparent;"><i>N-1</i></span><span style="color: #000000;background-color: transparent;"> array, where the </span><span style="color: #000000;background-color: transparent;"><i>i</i></span><span style="color: #000000;background-color: transparent;">-th entry in the output array is the index of the start of the next segment in the input array.</span></p><span style="color: #000000;background-color: transparent;">There are a number of ways to tackle this problem, but most established methods for this problem are profiled in this paper: </span><a href="https://www.cs.rutgers.edu/~pazzani/Publications/survey.pdf"><span style="color: #1155cc;background-color: transparent;">https://www.cs.rutgers.edu/~pazzani/Publications/survey.pdf</span></a><span style="color: #000000;background-color: transparent;">. </span></div></div><div><span style="color: #000000;background-color: transparent;"><br/></span></div><div><span style="color: #000000;background-color: transparent;">You can find some example data at <a href="https://algorithmia.com/v1/data/TimeSeries/segment/track.json">https://algorithmia.com/v1/data/TimeSeries/segment/track.json</a> (you will need to be logged in to view).</span></div><div><span style="color: #000000;background-color: transparent;"><br/></span></div><div><span style="color: #000000;background-color: transparent;">This data is visualized below </span><img src="http://i.imgur.com/aVFefAU.png"/></div><div><span style="color: #000000;background-color: transparent;"><br/></span></div><div><span style="color: #000000;background-color: transparent;"><br/></span></div>
Fulfilled By
  • Split a multidimensional timeseries such that a piece linear reconstruction has minimal error.
    • requests
Discussion
  • {{comment.username}}
Status
Fulfilled
Bounty expires in
Bounty expired
Bounty
100
Tags
(no tags)