Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active December 3, 2018 08:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kcnarf/288224c523cd73757bf946c52aed0a37 to your computer and use it in GitHub Desktop.
Save Kcnarf/288224c523cd73757bf946c52aed0a37 to your computer and use it in GitHub Desktop.
Download ZIP
timeline - approximation thanks to FFT/iFFT
Raw
.block
license: mit
Raw
README.md

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:

Raw
fft.js
/******************************************************************/
/* complex fast fourier transform and inverse from */
/* https://rosettacode.org/wiki/Fast_Fourier_transform#JavaScript */
/******************************************************************/
function icfft(amplitudes)
{
var N = amplitudes.length;
var iN = 1 / N;
//conjugate if imaginary part is not 0
for(var i = 0 ; i < N; ++i)
if(amplitudes[i] instanceof Complex)
amplitudes[i].im = -amplitudes[i].im;
//apply fourier transform
amplitudes = cfft(amplitudes)
for(var i = 0 ; i < N; ++i)
{
//conjugate again
amplitudes[i].im = -amplitudes[i].im;
//scale
amplitudes[i].re *= iN;
amplitudes[i].im *= iN;
}
return amplitudes;
}
function cfft(amplitudes)
{
var N = amplitudes.length;
if( N <= 1 )
return amplitudes;
var hN = N / 2;
var even = [];
var odd = [];
even.length = hN;
odd.length = hN;
for(var i = 0; i < hN; ++i)
{
even[i] = amplitudes[i*2];
odd[i] = amplitudes[i*2+1];
}
even = cfft(even);
odd = cfft(odd);
var a = -2*Math.PI;
for(var k = 0; k < hN; ++k)
{
if(!(even[k] instanceof Complex))
even[k] = new Complex(even[k], 0);
if(!(odd[k] instanceof Complex))
odd[k] = new Complex(odd[k], 0);
var p = k/N;
var t = new Complex(0, a * p);
t.cexp(t).mul(odd[k], t);
amplitudes[k] = even[k].add(t, odd[k]);
amplitudes[k + hN] = even[k].sub(t, even[k]);
}
return amplitudes;
}
/*
basic complex number arithmetic from
http://rosettacode.org/wiki/Fast_Fourier_transform#Scala
*/
function Complex(re, im)
{
this.re = re;
this.im = im || 0.0;
}
Complex.prototype.add = function(other, dst)
{
dst.re = this.re + other.re;
dst.im = this.im + other.im;
return dst;
}
Complex.prototype.sub = function(other, dst)
{
dst.re = this.re - other.re;
dst.im = this.im - other.im;
return dst;
}
Complex.prototype.mul = function(other, dst)
{
//cache re in case dst === this
var r = this.re * other.re - this.im * other.im;
dst.im = this.re * other.im + this.im * other.re;
dst.re = r;
return dst;
}
Complex.prototype.cexp = function(dst)
{
var er = Math.exp(this.re);
dst.re = er * Math.cos(this.im);
dst.im = er * Math.sin(this.im);
return dst;
}
Complex.prototype.log = function()
{
/*
although 'It's just a matter of separating out the real and imaginary parts of jw.' is not a helpful quote
the actual formula I found here and the rest was just fiddling / testing and comparing with correct results.
http://cboard.cprogramming.com/c-programming/89116-how-implement-complex-exponential-functions-c.html#post637921
*/
if( !this.re )
console.log(this.im.toString()+'j');
else if( this.im < 0 )
console.log(this.re.toString()+this.im.toString()+'j');
else
console.log(this.re.toString()+'+'+this.im.toString()+'j');
}
Raw
index.html
<!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] + ")");
var grid = container.append("g")
.attr("class", "grid");
var intersects = [];
d3.range(1, x.invert(timelineWidth)+1, 1).forEach(function(a) { d3.range(5, y.invert(-timelineHeight)+5,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"+[x(d[0])-1,y(d[1])]+"h3M"+[x(d[0]),y(d[1])-1]+"v3"});
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 computeRebuiltTimeserie() {
var fftComponentCopy = fftComponents.map(function(d, i){
if (fftComponentCoef(d) >= fftTreshold) {
return new Complex(d.re, d.im);
} else {
return new Complex(0, 0);
}
});
var complexRebuiltTimeserie = icfft(fftComponentCopy);
rebuiltTimeserie = [];
complexRebuiltTimeserie.forEach( function(d, i) {
rebuiltTimeserie.push({
x: i+1,
y: d.im});
})
}
function redrawAll(withTransition) {
redrawDots(withTransition);
redrawTimeline(withTransition);
redrawTreshold();
redrawFftComponents(withTransition);
redrawRebuiltTimeline(withTransition);
}
function redrawDots(withTransition) {
var dots = dotContainer.selectAll(".dot")
.data(timeserie);
dots = dots.enter()
.append("circle")
.classed("dot draggable", true)
.attr("r", 5)
.attr("cx", function(d) { return x(d.x); })
.call(drag)
.merge(dots);
dots.transition()
.duration(withTransition? duration : 0)
.attr("cy", function(d) { return y(d.y); })
}
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>
Raw
timeserie.csv
x y random
1 3 -1
2 10 -1
3 10 1
4 17 0
5 3 1
6 10 2
7 10 0
8 17 -1
9 3 0
10 10 0
11 10 -1
12 17 1
13 3 0
14 10 -1
15 10 1
16 17 0
17 3 2
18 10 1
19 10 -1
20 17 1
21 3 -2
22 10 2
23 10 1
24 17 -1
25 3 0
26 10 0
27 10 1
28 17 -1
29 3 -1
30 10 1
31 10 1
32 17 -1
33 3 -1
34 10 -1
35 10 1
36 17 0
37 3 1
38 10 2
39 10 0
40 17 -1
41 3 0
42 10 0
43 10 -1
44 17 1
45 3 0
46 10 -1
47 10 1
48 17 0
49 3 2
50 10 1
51 10 -1
52 17 1
53 3 -2
54 10 2
55 10 1
56 17 -1
57 3 0
58 10 0
59 10 1
60 17 -1
61 3 -1
62 10 1
63 10 1
64 17 -1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment