Skip to content

Instantly share code, notes, and snippets.

@saifuddin778

saifuddin778/README.md

Last active April 22, 2017 20:12
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 saifuddin778/b71aae06c7feb57a9118c9daba34063b to your computer and use it in GitHub Desktop.
Save saifuddin778/b71aae06c7feb57a9118c9daba34063b to your computer and use it in GitHub Desktop.
Download ZIP
DTW
Raw
README.md

DTW (Dynamic Time Warping) is a widely used algorithm for finding similarity metric between two time-series (T1 and T2). The idea of this algorithm is to utilize dynamic programming to figure out the most optimal alignment path (i.e. a path that minimizes the overall distance cost if we have to travel from beginning to the end of both time-series(s) while comparing them), which is constructed under some constraints.

This demonstration gives a basic idea of how this path is constructed. The original distance value is usually interpreted as the cumulative cost present at i=N, J=M, where N is the size of T1 and M is the size of T2. A very intuitive visible observation is: As the path is constructed, it avoids the traps with higher cost (red-ish).

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
text-align: center;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.js"></script>
<script>
var width = 900;
var height = 500;
var n = 50;
function argmin(items, t) {
var minindex = 0;
var min = items[minindex];
for (var i = 0; i < items.length; i++) {
if (items[i] < min) {
minindex = i;
min = items[i];
}
}
return t[minindex];
}
function dtw(a, b) {
var la = a.length;
var lb = b.length;
var map = {};
for (var i = 0; i < la; i++) {
map[[i, -1]] = Number.POSITIVE_INFINITY;
}
for (var i = 0; i < lb; i++) {
map[[-1, i]] = Number.POSITIVE_INFINITY;
}
map[[-1, -1]] = 0;
for (var i = 0; i < la; i++) {
for (var j = 0; j < lb; j++) {
map[[i, j]] = Math.abs(a[i] - b[j]);
}
}
for (var i = 0; i < la; i++) {
for (var j = 0; j < lb; j++) {
var current_cost = map[[i, j]];
var add_cost = Math.min(map[[i - 1, j]], map[[i, j - 1]], map[[i - 1, j - 1]]);
map[[i, j]] = current_cost + add_cost;
}
}
var optimalpath = [];
var n = la - 1;
var m = lb - 1
var location = [n, m];
optimalpath.push(location);
while (true) {
var t = [
[n - 1, m],
[n, m - 1],
[n - 1, m - 1]
];
if (n == 0) {
location = [0, m - 1];
} else if (m == 0) {
location = [n - 1, 0];
} else {
location = argmin(t.map(function(d) {
return map[d];
}), t);
}
n = location[0];
m = location[1];
optimalpath.push(location);
if ((location[0] == 0) & (location[1] == 0)) {
break;
}
}
return {
optimalpath: optimalpath,
map: map
};
}
function draw_lines() {
var xscale = d3.scale.linear().domain([0, n]).range([width * 0.1, width * 0.5]);
var yscale = d3.scale.linear().domain([0, 500]).range([height * 0.5, height * 0.1]);
var yscale2 = d3.scale.linear().domain([0, 500]).range([height * 0.9, height * 0.5]);
var line_A = d3.svg.line()
.x(function(d) {
return xscale(d.x)
})
.y(function(d) {
return yscale(d.y)
})
.interpolate("cardinal");
var line_B = d3.svg.line()
.x(function(d) {
return xscale(d.x)
})
.y(function(d) {
return yscale2(d.y)
})
.interpolate("cardinal");
var line_C = d3.svg.line()
.x(function(d) {
return d.x
})
.y(function(d) {
return d.y
})
.interpolate("linear");
space.append("path")
.style("fill", "none")
.style("stroke", "rgba(231, 76, 60, 1.0)")
.style("stroke-width", 2)
.style("opacity", 0.6)
.attr("d", line_A(data_A));
space.append("path")
.style("fill", "none")
.style("stroke", "rgba(231, 76, 60, 1.0)")
.style("stroke-width", 2)
.style("opacity", 0.6)
.attr("d", line_B(data_B));
var l1 = data_A.map(function(d, i) {
space.append("circle")
.attr("class", "l1")
.attr("id", i)
.attr("cx", xscale(d.x))
.attr("cy", yscale(d.y))
.attr("r", 3);
return d.y;
});
var l2 = data_B.map(function(d, i) {
space.append("circle")
.attr("class", "l2")
.attr("id", i)
.attr("cx", xscale(d.x))
.attr("cy", yscale2(d.y))
.attr("r", 3);
return d.y;
});
return {
l1: l1,
l2: l2
};
}
function grid(optimalpath, map) {
var maxw = 300;
var maxh = 300;
var nboxes = n * n;
var pad_x = maxw / n;
var pad_y = maxh / n;
var x = 0;
var y = 0 - pad_y;
var x_ = 0;
var y_ = 0;
var maxcost = Math.max.apply(Math, Object.keys(map)
.map(function(d) {
return map[d]
})
.filter(function(d) {
return (d < Number.POSITIVE_INFINITY) & (d);
}));
var mincost = Math.min.apply(Math, Object.keys(map)
.map(function(d) {
return map[d]
})
.filter(function(d) {
return (d < Number.POSITIVE_INFINITY) & (d);
}));
var colors_ = d3.scale.linear().domain([mincost, maxcost]).interpolate(d3.interpolateHsl).range(['lightyellow', 'red']);
var points = d3.range(nboxes).map(function(d) {
x = pad_x * (d % n);
if (d % n == 0) {
y += pad_y;
}
if (d == 0) {
x_ = x_;
y_ = y_;
} else {
x_ = (d % n);
y_ = y / pad_y;
}
return {
x: x,
y: y,
x_: x_,
y_: y_,
fill: colors_(map[[x_, y_]])
}
});
var gspace = space.append("g")
.attr("id", "grid")
.attr("transform", "translate(" + width * 0.55 + "," + height * 0.2 + ")")
.selectAll()
.data(points)
.enter()
.append("rect")
.attr("x", function(d) {
return d.x
})
.attr("y", function(d) {
return d.y
})
.attr("x_", function(d) {
return d.x_
})
.attr("y_", function(d) {
return d.y_
})
.attr("width", pad_x)
.attr("height", pad_y)
.style("fill", function(d) {
return d.fill
})
.style("stroke", "black")
.style("stroke-width", 0.5);
return points;
}
function play(optimalpath, grids) {
var l1s = d3.selectAll(".l1")[0];
var l2s = d3.selectAll(".l2")[0];
var b = 0;
var interval = setInterval(function() {
if (b == optimalpath.length - 1) {
clearInterval(interval);
}
var ap = optimalpath[b][0];
var bp = optimalpath[b][1];
d3.select("#grid").selectAll("rect").filter(function(d) {
return (d.x_ == ap) & (d.y_ == bp);
}).style("fill", "green");
var apx = d3.select(l1s[ap]).attr("cx");
var apy = d3.select(l1s[ap]).attr("cy");
var bpx = d3.select(l2s[bp]).attr("cx");
var bpy = d3.select(l2s[bp]).attr("cy");
space.append("line")
.attr("x1", apx)
.attr("y1", apy)
.attr("x2", bpx)
.attr("y2", bpy)
.attr("fill", "none")
.attr("stroke", "rgba(38, 166, 91, 1)")
.attr("stroke-width", 0.7);
b += 1;
}, 300);
}
var space = d3.select("body").append("svg").attr("width", width).attr("height", height).append("g");
var data_A = d3.range(n).map(function(d) {
return {
x: d,
y: 100 + (200 * Math.random())
}
});
var data_B = d3.range(n).map(function(d) {
return {
x: d,
y: 100 + (200 * Math.random())
}
});
var lines = draw_lines();
var l1 = lines.l1;
var l2 = lines.l2;
var dtwobj = dtw(l1, l2);
var grids = grid(dtwobj.optimalpath, dtwobj.map);
play(dtwobj.optimalpath, grids);
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment