Skip to content

Instantly share code, notes, and snippets.

@eweitnauer
Last active June 18, 2016 15:46
Show Gist options
  • Save eweitnauer/7da9ff0972ebf5ef2b6c to your computer and use it in GitHub Desktop.
Save eweitnauer/7da9ff0972ebf5ef2b6c to your computer and use it in GitHub Desktop.
Growing neural gas in javascript using D3.js for visualization

A javascript implementation of the classis Growing Neural Gas (GNG) algorithm from the paper A growing neural gas network learns topologies.

You can click or drag on the input space to add input data. At each step one input data instance is randomly selected and is used to update the GNG. Use the sliders to adjust the parameter values, hover over a value to see a description.

If you are looking at this on bl.ocks.org/eweitnauer, make sure to click the Open in a new window link to see the parameter input elements.

GNG = function() {
this.init();
this.α = 0.5; // error factor on split
this.β = 0.9995; // error factor each step
this.λ = 300; // add neuron every λ steps
this.max_n = 100; // maximum neuron count
this.ε_b = 0.05; // best learning rate
this.ε_n = 0.001; // neighbor learning rate
this.max_age = 10; // max link age
this.params = [
{ name: 'α', desc: 'error factor on split', min: 0, max: 1, step: 0.001 }
, { name: 'β', desc: 'error factor each step', min: 0.5, max: 1, step: 0.0005 }
, { name: 'λ', desc: 'add neuron every λ steps', min: 1, max: 1000, step: 1 }
, { name: 'max_n', desc: 'maximum neuron count', min: 2, max: 1000, step: 1 }
, { name: 'ε_b', desc: 'learning rate best neuron', min: 0, max: 1, step: 0.001 }
, { name: 'ε_n', desc: 'learning rate best neuron neighbors', min: 0, max: 1, step: 0.001 }
, { name: 'max_age', desc: 'maximum link age', min: 0, max: 1000, step: 1 }
];
}
GNG.prototype.init = function() {
this.neurons = [];
this.links = [];
this.createNeuron();
this.createNeuron();
this.createLink(this.neurons[0], this.neurons[1]);
this.step = 0;
}
GNG.prototype.input = function(x, y) {
this.step++;
var b1 = this.getClosestNeuronExcept(x, y, null);
var b2 = this.getClosestNeuronExcept(x, y, b1);
b1.error += b1.dist2(x, y);
b1.move_towards(x, y, this.ε_b);
var connected = false;
b1.links.reduceRight((prev_l, l) => {
var b1n = l.get_other(b1);
b1n.move_towards(x, y, this.ε_n);
if (b1n === b2) {
connected = true;
l.age = 0;
} else {
l.age++;
if (l.age > this.max_age) this.removeLink(l);
}
}, null);
if (!connected) this.createLink(b1, b2);
this.neurons = this.neurons.filter(n => n.links.length > 0);
if (this.step % this.λ === 0) this.addNeuron();
this.neurons.forEach(n => n.error *= this.β);
}
GNG.prototype.addNeuron = function() {
if (this.neurons.length >= this.max_n) return;
var w1 = this.getWorstNeuron(this.neurons);
var w2 = this.getWorstNeuron(w1.links.map(l => l.get_other(w1)));
var w3 = this.createNeuron((w1.x+w2.x)/2, (w1.y+w2.y)/2);
this.createLink(w1, w3);
this.createLink(w2, w3);
this.removeLink(this.getLink(w1, w2));
w1.error *= this.α;
w2.error *= this.α;
w3.error = (w1.error + w2.error) / 2;
}
GNG.prototype.getClosestNeuronExcept = function (x, y, except) {
return _.minBy(this.neurons, n => n===except ? Infinity : n.dist2(x, y));
};
GNG.prototype.getWorstNeuron = function (ns) {
return _.maxBy(ns, n => n.error);
};
GNG.prototype.createNeuron = function(x, y) {
if (arguments.length < 2) { x = Math.random(); y = Math.random() }
var n = new Neuron(x, y);
this.neurons.push(n);
return n;
}
GNG.prototype.createLink = function(n1, n2) {
var l = new Link(n1, n2);
this.links.push(l);
n2.links.push(l);
n1.links.push(l);
}
GNG.prototype.removeLink = function(l) {
this.links.splice(this.links.indexOf(l), 1);
l.n1.links.splice(l.n1.links.indexOf(l), 1);
l.n2.links.splice(l.n2.links.indexOf(l), 1);
}
GNG.prototype.getLink = function(n1, n2) {
return _.find(n1.links, l => (l.n1 === n1 && l.n2 === n2) || (l.n1 === n2 && l.n2 === n1));
}
Neuron = function(x, y) {
this.error = 0;
this.x = x;
this.y = y;
this.links = [];
}
Neuron.prototype.dist2 = function(x, y) {
var dx = this.x-x, dy = this.y-y;
return dx*dx + dy*dy;
}
Neuron.prototype.move_towards = function(x, y, s) {
this.x += s*(x-this.x);
this.y += s*(y-this.y);
}
Link = function(n1, n2) {
this.age = 0;
this.n1 = n1;
this.n2 = n2;
}
Link.prototype.get_other = function(n) {
return this.n1 === n ? this.n2 : this.n1;
}
<!DOCTYPE html>
<meta charset="utf-8">
<title>GNG + D3</title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.2.0/lodash.js"></script>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src='gng.js'></script>
<script src='sliders.js'></script>
<style>
svg {
border: 1px solid silver;
}
.node {
stroke: #fff;
stroke-width: 1.5px;
fill: steelblue;
opacity: 0.5;
}
.inode {
stroke: #fff;
stroke-width: 1.5px;
fill: #000;
}
.link {
stroke: #999;
stroke-opacity: .6;
}
div.param {
display: inline-block;
width: 120px;
}
input {
width: 830px;
}
</style>
<body>
<div id='gas'></div>
<div id='controls'></div>
<script>
var width = 960
, height = 470
, r = 10;
var input = _.times(100, i => { return {x: Math.random(), y: Math.random()}});
var x = d3.scale.linear()
.range([r,width-r])
.domain([0,1]);
var y = d3.scale.linear()
.range([r,height-r])
.domain([0,1]);
var svg = d3.select("#gas").append("svg")
.attr("width", width)
.attr("height", height);
svg.append('rect')
.attr({width: '100%', height: '100%'})
.style('opacity', 0)
.style('pointer-events', 'all')
.on('click', function() {
var pos = d3.mouse(this);
input.push({x: x.invert(pos[0]), y: y.invert(pos[1]) });
update_inputs();
})
.call(d3.behavior.drag().on('drag', function() {
input.push({x: x.invert(d3.event.x), y: y.invert(d3.event.y) });
update_inputs();
}));
var input_els = svg.selectAll(".input");
var node_els = svg.selectAll(".node");
var link_els = svg.selectAll(".links");
function update_inputs() {
input_els = input_els.data(input);
input_els.enter().append('circle')
.attr("class", "input")
.attr("r", r/2);
input_els.exit().remove();
input_els
.attr("cx", d => x(d.x))
.attr("cy", d => y(d.y));
}
function update(gas) {
// links
link_els = link_els.data(gas.links);
link_els.enter().append("line")
.attr("class", "link");
link_els.exit().remove();
link_els
.attr("x1", d => x(d.n1.x))
.attr("y1", d => y(d.n1.y))
.attr("x2", d => x(d.n2.x))
.attr("y2", d => y(d.n2.y));
// nodes
node_els = node_els.data(gas.neurons);
node_els.enter().append("circle")
.attr("class", "node")
.attr("r", r);
node_els.exit().remove();
node_els
.attr("cx", d => x(d.x))
.attr("cy", d => y(d.y));
}
var gas;
var cdiv = d3.select('#controls');
var speed = 100;
function initGas() {
if (!gas) gas = new GNG();
else gas.init();
update(gas);
}
function initParams() {
cdiv.selectAll('*').remove();
initSlider(cdiv, { type:"range", name: 'speed', min: 1, max: 1000
, step: 1, value: speed, title: 'GNG updates per animation frame' }
, value => speed = value);
gas.params.forEach(p => {
initSlider(cdiv, { type:"range", name: p.name, min: p.min, max: p.max
, step: p.step, value: gas[p.name], title: p.desc }
, value => gas[p.name] = value);
});
}
function resetParams() {
cdiv.selectAll('*').remove();
speed = 100;
initSlider(cdiv, { type:"range", name: 'speed', min: 1, max: 1000
, step: 1, value: speed, title: 'GNG updates per animation frame' }
, value => speed = value);
var g2 = new GNG();
g2.params.forEach(p => {
initSlider(cdiv, { type:"range", name: p.name, min: p.min, max: p.max
, step: p.step, value: g2[p.name], title: p.desc }
, value => gas[p.name] = value);
gas[p.name] = g2[p.name];
});
}
var running = false;
var should_pause = false;
function run() {
running = true;
should_pause = false;
d3.timer(function() {
if (should_pause) { running = false; return true; } // stop the timer
_.times(speed, function() {
var d = _.sample(input);
gas.input(d.x, d.y);
});
update(gas);
});
}
d3.select('#gas').append('div');
var btn = d3.select('#gas').append('button').text('start').on('click', function() {
if (running) {
d3.select(this).text('start');
should_pause = true;
} else {
if (input.length < 1) {
alert('create inputs first by clicking or dragging on the rectangle');
return;
}
d3.select(this).text('stop');
run();
}
});
d3.select('#gas').append('button').text('reset gas').on('click', initGas);
d3.select('#gas').append('button').text('reset params').on('click', resetParams);
d3.select('#gas').append('button').text('clear inputs').on('click', function() {
input = [];
should_pause = true;
btn.text('start');
update_inputs();
});
initGas();
initParams();
update_inputs();
</script>
function initSlider(container, options, callback) {
var p = container.append('p');
var div = p.append('div').attr('title', options.title).classed('param',true);
div.append('span').text(options.name+': ');
var val_el = div.append('span').classed('value', true).text(options.value);
p.append('input')
.attr(options)
.on('input', function() { val_el.text(this.value); callback(this.value) });
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment