Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <!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>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement