mayth/ap.html

## ap.html
<!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>

## kmeans.html
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>k-means 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 drawArrow(ctx, fromx, fromy, tox, toy, color){
        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, centroids, N, K, iter, ready = false,
          colors = ['#CC3300', '#3300CC', '#33CC00'];

      function plot() {
        var ctx = canvas.getContext("2d");
        ctx.clearRect(0, 0, canvas.width, canvas.height);
        for (var i = 0; i < K; ++i) {
          var p = centroids[i];
          ctx.beginPath();
          ctx.arc(p.x, p.y, 3, 0, Math.PI * 2, false);
          ctx.fillStyle = p.klass >= 0 ? colors[p.klass] : 'black';
          ctx.fill();
        }
        for (var i = 0; i < N; ++i) {
          var p = data[i];
          ctx.beginPath();
          ctx.fillStyle = p.klass >= 0 ? colors[p.klass] : 'black';
          ctx.fillRect(p.x - 3, p.y - 3, 6, 6);
          if (p.klass >= 0)
            drawArrow(ctx, p.x, p.y, centroids[p.klass].x, centroids[p.klass].y, colors[p.klass]);
        }
      }

      function init(n, k) {
        N = n;
        K = k;
        iter = 0;
        updateIter();
        $('#k').text(K);
        ready = false;
        /*
        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};
        });
        */
        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: -1};
        }
        var indices = new Array(k);
        for (var i = 0; i < K; ++i) {
          while (true) {
            var x = getRandomInt(0, N - 1);
            if (indices.indexOf(x) == -1) {
              indices[i] = x;
              break;
            }
          }
        }
        centroids = indices.map(function(i) { return {x: data[i].x, y: data[i].y}; });
        for (var i = 0; i < K; ++i) {
          centroids[i].klass = i;
        }
      };

      function assign() {
        for (var i = 0; i < N; ++i) {
          var p = data[i], nearestDistance = 9999, nearestPoint;
          for (var j = 0; j < K; ++j) {
            var q = centroids[j], d = distance(p, q);
            if (d < nearestDistance) {
              nearestDistance = d;
              nearestPoint = q;
            }
          }
          p.klass = nearestPoint.klass;
        }
      };

      function updateCentroid() {
        centroids.forEach(function(c) {
          var sx = 0, sy = 0, points = data.filter(function(p) { return p.klass == c.klass; });
          points.forEach(function(p) { sx += p.x; sy += p.y; });
          c.x = sx / points.length;
          c.y = sy / points.length;
        });
      }

      function step() {
        assign();
        updateCentroid();
        ++iter;
        updateIter();
      }

      function updateIter() { $('#iter').text(iter); }

      $(function() {
        var n = 20, k = 3;
        canvas = document.getElementById("canvas");
        $('#step').click(function() {
          if (!ready) {
            // just assign
            assign();
            ready = true;
          } else {
            step();
          }
          plot();
        });
        $('#init').click(function() { init(n, k); plot(); });
        init(n, k);
        // assign();
        plot();
      });
    </script>
  </head>
  <body>
    <canvas id="canvas" width="240" height="240">
      canvas is not available
    </canvas>
    <br>
    <button id="step">Step</button>
    <button id="init">Init</button>
    <p>Iter: <span id="iter"></span></p>
    <p>k = <span id="k"></span></p>
  </body>
</html>
	<!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-headlenMath.cos(angle-Math.PI/7),toy-headlenMath.sin(angle-Math.PI/7));

	//path from the side point of the arrow, to the other side point
	ctx.lineTo(tox-headlenMath.cos(angle+Math.PI/7),toy-headlenMath.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-headlenMath.cos(angle-Math.PI/7),toy-headlenMath.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>