Untitled

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Affinity Propagation clustering</title>
    <script src="./jquery-2.1.3.min.js"></script>
    <script>
      function getRandomInt(min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
      }
      function distance(p, q) {
        return Math.sqrt(Math.pow(p.x - q.x, 2.0) + Math.pow(p.y - q.y, 2.0));
      }
      function median(values) {
        values.sort( function(a,b) {return a - b;} );

        var half = Math.floor(values.length/2);

        if(values.length % 2)
            return values[half];
        else
            return (values[half-1] + values[half]) / 2.0;
      }
      function drawArrow(ctx, fromx, fromy, tox, toy){
        var color = 'rgba(204, 0, 0, 0.5)'
        var headlen = 5;
        var angle = Math.atan2(toy-fromy,tox-fromx);

        //starting path of the arrow from the start square to the end square and drawing the stroke
        ctx.beginPath();
        ctx.moveTo(fromx, fromy);
        ctx.lineTo(tox, toy);
        ctx.strokeStyle = color;
        ctx.lineWidth = 2;
        ctx.stroke();

        //starting a new path from the head of the arrow to one of the sides of the point
        ctx.beginPath();
        ctx.moveTo(tox, toy);
        ctx.lineTo(tox-headlen*Math.cos(angle-Math.PI/7),toy-headlen*Math.sin(angle-Math.PI/7));

        //path from the side point of the arrow, to the other side point
        ctx.lineTo(tox-headlen*Math.cos(angle+Math.PI/7),toy-headlen*Math.sin(angle+Math.PI/7));

        //path from the side point back to the tip of the arrow, and then again to the opposite side point
        ctx.lineTo(tox, toy);
        ctx.lineTo(tox-headlen*Math.cos(angle-Math.PI/7),toy-headlen*Math.sin(angle-Math.PI/7));

        //draws the paths created above
        ctx.strokeStyle = color;
        ctx.lineWidth = 2;
        ctx.stroke();
        ctx.fillStyle = color;
        ctx.fill();
      }

      var canvas, data, N, iter, isAuto = false,
          preference, lambda = 0.9,
          similarities, availabilities, responsibilities;

      function plot(withCentroidMarker) {
        if (arguments.length == 0) {
          withCentroidMarker = true;
        }
        var ctx = canvas.getContext("2d");
        ctx.clearRect(0, 0, canvas.width, canvas.height);
        for (var i = 0; i < N; ++i) {
          var p = data[i];
          ctx.lineWidth = 2;
          ctx.fillStyle = 'black';
          ctx.beginPath();
          ctx.fillRect(p.x - 3, p.y - 3, 6, 6);
          if (p.klass == i) {
            if (withCentroidMarker) {
              ctx.strokeStyle = 'black';
              ctx.beginPath();
              ctx.arc(p.x, p.y, 5, 0, Math.PI * 2, false);
              ctx.stroke();
            }
          } else {
            drawArrow(ctx, p.x, p.y, data[p.klass].x, data[p.klass].y);
          }
        }
      }

      function init(n) {
        var flatsim = new Array();
        iter = 0;
        $('#iter').text(iter);
        N = n;
        similarities = new Array(N);
        responsibilities = new Array(N);
        availabilities = new Array(N);

        /*
        data = [[135,183],[184,94],[24,131],[144,36],[207,106],[202,102],[164,69],[156,173],[230,95],[84,35],[76,181],[230,136],[157,147],[80,115],[119,211],[56,95],[215,101],[226,87],[185,15],[163,31],[186,159],[108,50],[203,88],[34,182],[16,179]].map(function(arr) {
          return {x: arr[0], y: arr[1], klass: -1};
        });
        for (var i = 0; i < N; ++i) {
          data[i].klass = i;
        }
        */
        data = new Array(N);
        for (var i = 0; i < N; ++i) {
          data[i] = {x: getRandomInt(10, canvas.width - 10), y: getRandomInt(10, canvas.height - 10), klass: i};
        }
        for (var i = 0; i < N; ++i) {
          similarities[i] = new Array(N);
          for (var j = 0; j < N; ++j) {
            var s = -distance(data[i], data[j]);
            similarities[i][j] = s;
            if (i != j)
              flatsim.push(s);
          }
        }
        preference = median(flatsim);
        // preference = flatsim.sort(function(a, b) { return a - b; })[0];
        $('#preference').text(preference);
        for (var i = 0; i < N; ++i) {
          similarities[i][i] = preference;
        }

        for (var i = 0; i < N; ++i) {
          responsibilities[i] = new Array(N);
          for (var j = 0; j < N; ++j) {
            responsibilities[i][j] = 0;
          }
        }
        for (var i = 0; i < N; ++i) {
          availabilities[i] = new Array(N);
          for (var j = 0; j < N; ++j) {
            availabilities[i][j] = 0;
          }
        }
      };

      function updateResponsibilities() {
        for (var i = 0; i < N; ++i) {
          var m1 = -Infinity, m2 = -Infinity, idx;
          for (var k = 0; k < N; ++k) {
            var score = availabilities[i][k] + similarities[i][k];
            if (m1 < score) {
              m2 = m1;
              m1 = score;
              idx = k;
            } else if (m2 < score) {
              m2 = score;
            }
          }

          for (var k = 0; k < N; ++k) {
            var rold = responsibilities[i][k],
                rnew = similarities[i][k] - (k == idx ? m2 : m1);
            responsibilities[i][k] = lambda * rold + (1 - lambda) * rnew;
          }
        }
      }

      function updateAvailabilities() {
        for (var i = 0; i < N; ++i) {
          var Rp = new Array(N), sum = 0;
          for (var k = 0; k < N; ++k) {
            Rp[k] = (responsibilities[k][i] < 0 && k != i) ? 0 : responsibilities[k][i];
            sum += Rp[k];
          }

          for (var k = 0; k < N; ++k) {
            var aold = availabilities[k][i],
                anew = sum - Rp[k];
            if (anew > 0 && k != i) {
              anew = 0;
            }
            availabilities[k][i] = (1 - lambda) * anew + lambda * aold;
          }
        }
      }

      function assign() {
        for (var i = 0; i < N; ++i) {
          var maxScore = -Infinity, maxScoreIndex = -Infinity;
          for (var k = 0; k < N; ++k) {
            var score = responsibilities[i][k] + availabilities[i][k];
            if (maxScore < score) {
              maxScore = score;
              maxScoreIndex = k;
            }
          }
          data[i].klass = maxScoreIndex;
        }
      }

      function step() {
        updateResponsibilities();
        updateAvailabilities();
        assign();
        ++iter;
        $('#iter').text(iter);
      }

      $(function() {
        var n = 20;
        canvas = document.getElementById("canvas");
        $('#step').click(function() { step(); plot(); });
        $('#init').click(function() { init(n); plot(false); });
        $('#start').click(function() { isAuto = true; });
        $('#stop').click(function() { isAuto = false; });
        setInterval(function() { if (isAuto) { step(); plot(); } }, 50);
        init(n);
        plot(false);
      });
    </script>
  </head>
  <body>
    <canvas id="canvas" width="240" height="240">
      canvas is not available
    </canvas>
    <br>
    <button id="init">Init</button>
    <button id="step">Step</button>
    <button id="start">Auto</button>
    <button id="stop">Stop</button>
    <p>Iter: <span id="iter"></span></p>
    <p>Preference: <span id="preference"></span></p>
  </body>
</html>