Growing neural gas in javascript using D3.js for visualization

README.md

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.js

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;
}

index.html

<!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>

sliders.js

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) });
}