All examples By author By category About

Kcnarf

Full window Github gist

timeline - approximation thanks to FFT/iFFT

This block is a continuation of a previous one, and an experimentation of how to rebuilt an approximation of a timeline thanks to an inverse Fast Fourier Transform (iFFT) algorithm.

Usages :

in the top graph, Drag & Drop points to update the timeline, or use the shortcuts below the graph; this will update the corresponding FFT components (in the bottom graph)
in the bottom graph, move the treshold up and down; this will rebuild another timeline (in the top graph) based on the retained FFT components

Notes:

I've done other bl.ocks dealing with timeline analyses:

another block highlights how important detrending is when trying to detect seasonality
another block experiments seasonality detection
another block experiments autocorrelation
another block experiments time series correlation
another block deals with the impact of seasonality when computing the trend of a timeline

Acknowledgments:

<!DOCTYPE html>
<title>timeline - approximation thanks to FFT/iFFT</title>
<meta content="Illustrating timeline approximation thanks to FFT/iFFT with d3.js" name="description">
<meta charset="utf-8">
<style>
  
  body {
    position: relative;
    background-color: #ddd;
    margin: auto;
  }
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 300px;
    font-size: 40px;
  }
  
  .controls {
    position: absolute;
    font: 11px arial;
  }
  #controls1 {
    top: 300px;
    left: 10px;
  }
  #controls2 {
    top: 300px;
    left: 450px;
  }
  #controls3 {
    top: 300px;
    right: 10px;
    text-align: right;
  }
  
  .viz {
    position: absolute;
    background-color: white;
    border-radius: 10px;
    left: 5px;
  }
  .viz#timelines {
    top: 5px;
  }
  .viz#fft {
    top: 355px;
  }
  
  .flow {
    position: absolute;
    font-size: 30px;
    color: darkgrey;
    top: 320px;
  }
  
  .flow span {
    font-size: initial;
  }
  
  #flow-1 {
    left: 400px;
  }
  
  #flow-2 {
    right: 120px;
  }
  
  .axis path,
  .axis line {
    fill: none;
    stroke: black;
    shape-rendering: crispEdges;
  }
  .axis text {
    font-family: sans-serif;
    font-size: 11px;
    fill: black;
  }
  .grid>line, .grid>.intersect {
    fill: none;
    stroke: #ddd;
    shape-rendering: crispEdges;
    vector-effect: non-scaling-stroke;
  }
  .legend {
    font-size: 12px;
  }
  
  .dot {
    fill: steelblue;
    stroke: white;
    stroke-width: 3px;
  }
  .dot.draggable:hover, .dot.dragging {
    fill: pink;
    cursor: ns-resize;
  }
	
  .timeline {
    fill: none;
    stroke: lightsteelblue;
    stroke-width: 2px;
  }
  
  .timeline.rebuilt {
    stroke: pink;
    stroke-dasharray: 3 3;
  }
  
  .fft-bar {
    fill: grey;
  }
  
  #fft-treshold>line{
    stroke: pink;
    stroke-width: 2px;
  }
  #fft-treshold.draggable:hover, #fft-treshold.dragging {
    cursor: ns-resize;
  }
  #fft-treshold>text {
	  font-size: 12px;
  }

</style>
<body>
  <div id="timelines" class="viz">
    <div id="controls1" class="controls">
      update time serie with a seasonality's length of <a href="#" onclick="updateSeasonalityPeriod(2);">2</a> /<a href="#" onclick="updateSeasonalityPeriod(3);">3</a> / <a href="#" onclick="updateSeasonalityPeriod(4);">4</a> / <a href="#" onclick="updateSeasonalityPeriod(5);">5</a> / <a href="#" onclick="updateSeasonalityPeriod(6);">6</a> / <a href="#" onclick="updateSeasonalityPeriod(7);">7</a> / <a href="#" onclick="updateSeasonalityPeriod(8);">8</a> / <a href="#" onclick="updateSeasonalityPeriod(9);">9</a> / <a href="#" onclick="updateSeasonalityPeriod(10);">10</a> periods
    </div>
    <div id="controls2" class="controls">
      <a href="#" onclick="increaseSeasonOrderOfMagnitude();">increase</a> / <a href="#"  onclick="decreaseSeasonOrderOfMagnitude();">decrease</a> seasonality's order of magnitude
    </div>
    <div id="controls3" class="controls">
      <a href="#" onclick="increaseTrend();">increase</a> / <a href="#"  onclick="decreaseTrend();">decrease</a> timeline's trend
    </div>
  </div>
  <div id="fft" class="viz"></div>
  <div id="flow-1" class="flow"><span>FFT</span>&#8615;</div>
  <div id="flow-2" class="flow">&#8613;<span>iFFT of retained components (above treshold)</span></div>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
	<script src="https://d3js.org/d3.v4.min.js"></script>
  <script src="fft.js"></script>
  <script>
    var timeserie = [];
    var fftComponents = [];
    function fftComponentCoef (d) {
      // Amplitude-Units-Peak (Apk), from sooeet.com/math/online-fft-calculator.php
      return Math.sqrt(Math.pow(d.re,2)+Math.pow(d.im,2));
      // dBV, from sooeet.com/math/online-fft-calculator.php
      return 20*Math.log(Math.sqrt(Math.pow(d.re,2)+Math.pow(d.im,2)));
    }
    var fftTreshold = 0;
    var rebuiltTimeserie = [];
    var randomness = [];
    var currentSeasonLength = 4;
    var currentSeasonOrderOfMagnitude = 8;
    var currentTrend = 1.4;
    var shouldDetrend = false;
    var radix = 5;	//6 max., see below
    var pointNumber = Math.pow(2,radix);	//max = Math.pow(2,6) = 64 samples
    var maxAmount = {3: 40, 4: 50, 5: 70, 6: 120}[radix];

//begin: const.
    var WITH_TRANSITION = true;
    var WITHOUT_TRANSITION = false;
    var duration = 500;
    var NEW_RANDOMNESS = true;
    var PRESERVE_RANDOMNESS = false;
    //end: const.

//begin: layout conf.
    var timelineVizDimension = {width: 960, height:340},
        fftVizDimension = {width: 960, height:160},
        vizMargin = 5,
        flowWidth = 20
    legendHeight = 20,
      xAxisLabelHeight = 10,
      yAxisLabelWidth = 10,
      margin = {top: 20, right: 20, bottom: 20, left: 20},
      timelineSvgWidth = timelineVizDimension.width - 2*vizMargin,
      timelineSvgHeight = timelineVizDimension.height - 2*vizMargin - flowWidth/2,
      fftSvgWidth = fftVizDimension.width - 2*vizMargin,
      fftSvgHeight = fftVizDimension.height - 2*vizMargin - flowWidth/2,
      timelineWidth = timelineSvgWidth - margin.left - margin.right - yAxisLabelWidth,
      timelineHeight = timelineSvgHeight - margin.top - margin.bottom - xAxisLabelHeight - 1.5*legendHeight,
      fftWidth = fftSvgWidth - margin.left - margin.right - yAxisLabelWidth,
      fftHeight = fftSvgHeight - margin.top - margin.bottom;
    //end: layout conf.

var drag = d3.drag()
    .subject(function(d) { return d; })
    .on("start", dragStarted)
    .on("drag", dragged1)
    .on("end", dragEnded);

var tresholdDrag = d3.drag()
    //.subject(function(d) { return d; })
    .on("start", dragStarted)
    .on("drag", tresholdDragged)
    .on("end", dragEnded);

var x = d3.scaleLinear()
    .domain([0, pointNumber])
    .range([0, timelineWidth]);
    var y = d3.scaleLinear()
    .domain([0, maxAmount])
    .range([0, -timelineHeight]);

var xFft = d3.scaleLinear()
    .domain([0, pointNumber])
    .range([0, fftWidth]);
    var yFft = d3.scaleLinear()
    .domain([0, 1])
    .range([0, -fftHeight]);

var xAxisDef = d3.axisBottom()
    .scale(x)
    .ticks(pointNumber);
    var yAxisDef = d3.axisLeft()
    .scale(y);

var xAxisFftDef = d3.axisBottom()
    .scale(xFft)
    .tickValues(d3.range(0,pointNumber));
    var yAxisFftDef = d3.axisLeft()
    .scale(yFft)
    .ticks(3)
    .tickFormat("");

//being: build layout
    var svg = d3.select("#timelines").append("svg")
    .attr("width", timelineSvgWidth)
    .attr("height", timelineSvgHeight)
    .append("g")
    .attr("transform", "translate(" + [margin.left, margin.top] + ")");

var container = svg.append("g")
    .attr("class", "graph")
    .attr("transform", "translate(" + [yAxisLabelWidth, timelineHeight] + ")");

container.append("text")
      .attr("transform", "translate(" + [timelineWidth/2, -timelineHeight] + ")")
      .attr("text-anchor", "middle")
      .text("Timeline");

container.append("g")
      .attr("class", "axis x")
      .call(xAxisDef)
      .append("text")
      .attr("x", timelineWidth)
      .attr("y", -6)
      .style("text-anchor", "end")
      .text("Time");

container.append("g")
      .attr("class", "axis y")
      .call(yAxisDef)
      .append("text")
      .attr("transform", "rotate(-90)")
      .attr("x", timelineHeight)
      .attr("y", 16)
      .style("text-anchor", "end")
      .text("Amount");

var rebuiltTimeline = container.append("path")
    .classed("timeline rebuilt", true)
    .attr("d", line)

var timeline = container.append("path")
    .classed("timeline", true)
    .attr("d", line)

var dotContainer = container.append("g")
    .classed("dots", true);

svg = d3.select("#fft").append("svg")
      .attr("width", fftSvgWidth)
      .attr("height", fftSvgHeight)
      .append("g")
      .attr("transform", "translate(" + [margin.left, margin.top] + ")");

container = svg.append("g")
      .attr("class", "graph")
      .attr("id", "fft")
      .attr("transform", "translate(" + [yAxisLabelWidth, fftHeight] + ")");

var fftTitle = container.append("text")
    .attr("transform", "translate(" + [fftWidth/2, -fftHeight] + ")")
    .attr("text-anchor", "middle")
    .text("Power spectrum");

grid = container.append("g")
      .attr("class", "grid");
    intersects = [];
    d3.range(1, xFft.invert(fftWidth), 1).forEach(function(a) { d3.range(-1, yFft.invert(-fftHeight)+0.5,0.5).forEach(function(b) { intersects.push([a,b])})});
    grid.selectAll(".intersect")
      .data(intersects)
      .enter().append("path")
      .classed("intersect", true)
      .attr("d", function(d) { return "M"+[xFft(d[0])-1,yFft(d[1])]+"h3M"+[xFft(d[0]),yFft(d[1])-1]+"v3"});

container.append("g")
      .attr("class", "axis x")
      .call(xAxisFftDef)
      .append("text")
      .attr("x", fftWidth)
      .attr("y", -6)
      .style("text-anchor", "end")
      .text("Freqency");

container.append("g")
      .attr("class", "axis y")
      .call(yAxisFftDef)
      .append("text")
      .attr("transform", "rotate(-90)")
      .attr("x", fftHeight)
      .attr("y", -10)
      .style("text-anchor", "end")
      .text("Apk");

var barContainer = container.append("g")
    .attr("id", "bar-container");

var drawnTreshold = container.append("g")
    .attr("id", "fft-treshold")
    .classed("draggable", true)
    .attr("transform", "translate("+[0,yFft(0)]+")")
    .call(tresholdDrag);
    drawnTreshold.append("line")
      .attr("id", "fft-treshold")
      .attr("x1", xFft(0))
      .attr("x2", xFft(pointNumber))
      .attr("y1", 0)
      .attr("y2", 0)
    drawnTreshold.append("text")
      .attr("x", fftWidth+margin.right)
      .attr("y", 10)
      .style("text-anchor", "end")
      .text("Treshold");
    //end: build layout

d3.csv("timeserie.csv", dottype, function(error, dots) {
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITHOUT_TRANSITION);
    });

function dottype(d) {
      d.x = +d.x;
      d.y = +d.y+(+d.random);
      if (timeserie.length<pointNumber) { //FFT only on data of length 2-radix
        timeserie.push(d);
        randomness.push(+d.random);
      }
      return d;
    }

var line = d3.line()
    .x(function(d) { return x(d.x); })
    .y(function(d) { return y(d.y); });

function computeAll(withRandom) {
      computeTimeserie(withRandom);
      computeFftComponents();
      computeRebuiltTimeserie();
    }

function computeTimeserie(withRandom) {
      var trend = shouldDetrend ? 0 : currentTrend;
      var intercept = 10;

var expected;
      timeserie.forEach(function(d,i) {
        expected = trend*d.x+intercept;
        switch (i%currentSeasonLength) {
          case 0: expected -= currentSeasonOrderOfMagnitude; break;
          case (currentSeasonLength-1): expected += currentSeasonOrderOfMagnitude; break;
        }

if (withRandom) {
          randomness[i] = 3*(Math.random()-0.5);
        }
        d.y = expected + randomness[i];
      })
    }

function computeFftComponents() {
      var complexTimeserie = timeserie.map(function(d) {
        return new Complex(d.x, d.y);
      })
      fftComponents = cfft(complexTimeserie);
    }

function redrawAll(withTransition) {
      redrawDots(withTransition);
      redrawTimeline(withTransition);
      redrawTreshold();
      redrawFftComponents(withTransition);
      redrawRebuiltTimeline(withTransition);
    }

function redrawTimeline(withTransition) {
      timeline.transition()
        .duration(withTransition? duration : 0)
        .attr("d", line(timeserie));
    }

function redrawRebuiltTimeline(withTransition) {
      rebuiltTimeline.transition()
        .duration(withTransition? duration : 0)
        .attr("d", line(rebuiltTimeserie));
    }

function redrawFftComponents(withTransition) {
      var barData = [],
          maxCoef= -Infinity,
          coef;

fftComponents.forEach( function(d, i) {
        coef = fftComponentCoef(d);
        maxCoef = Math.max(maxCoef, coef);
        barData.push({
          index: i,
          coef: coef
        })
      })

yFft.domain([0, maxCoef]);

bars = barContainer.selectAll(".fft-bar")
        .data(barData);

bars.enter().append("path")
        .classed("fft-bar", true)
        .attr("d", function(d) { return "M"+[xFft(d.index)-2,yFft(0)]+"h5V"+yFft(d.coef)+"h-5z" })
        .attr("fill-opacity", function(d){
        return (d.coef >= fftTreshold)? 1 : 0.5;});
      bars.transition()
        .duration(withTransition? duration : 0)
        .attr("d", function(d) { return "M"+[xFft(d.index)-2,yFft(0)]+"h5V"+yFft(d.coef)+"h-5z" })
        .attr("fill-opacity", function(d){
        return (d.coef >= fftTreshold)? 1 : 0.5;});
    }

function redrawTreshold() {
      drawnTreshold.attr("transform", "translate("+[0,yFft(fftTreshold)+2]+")");
    }

//begin: handle UI interactions (drag, available controls)
    function dragStarted(d) {
      d3.select(this).classed("dragging", true);
    }

function dragged1(d) {
      d.y += y.invert(d3.event.dy);

computeFftComponents();
      computeRebuiltTimeserie();

redrawAll(WITHOUT_TRANSITION);
    }

function tresholdDragged() {
      fftTreshold = yFft.invert(d3.event.y);
      computeRebuiltTimeserie();

redrawTreshold();
      redrawFftComponents(WITHOUT_TRANSITION);
      redrawRebuiltTimeline(WITHOUT_TRANSITION);
    }

function dragEnded(d) {
      d3.select(this).classed("dragging", false);
    }

function updateSeasonalityPeriod(newSeasonLength) {
      currentSeasonLength = newSeasonLength;
      computeAll(NEW_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function increaseTrend() {
      currentTrend *= 1.6;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function decreaseTrend() {
      currentTrend *= 0.625;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function increaseSeasonOrderOfMagnitude() {
      currentSeasonOrderOfMagnitude *= 1.6;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function decreaseSeasonOrderOfMagnitude() {
      currentSeasonOrderOfMagnitude *= 0.625;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function trend() {
      shouldDetrend = false;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function detrend() {
      shouldDetrend = true;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }

function handleDetrend(cb) {
      shouldDetrend = cb.checked;
      computeAll(PRESERVE_RANDOMNESS);
      redrawAll(WITH_TRANSITION);
    }
    //end: handle UI interactions (drag, available controls)
  </script>
</body>

https://d3js.org/d3.v4.min.js