Skip to content

Instantly share code, notes, and snippets.

@jbeuckm
Last active May 27, 2019 05:36
Show Gist options
  • Save jbeuckm/5731501 to your computer and use it in GitHub Desktop.
Save jbeuckm/5731501 to your computer and use it in GitHub Desktop.
K-Means in 2D
<html lang="en" xmlns:m="http://www.w3.org/1998/Math/MathML">
<head>
<meta charset="utf-8">
<link rel="stylesheet" href="https://rawgithub.com/yannickulrich/presenter/master/lib/jqMath/UnifrakturMaguntia.css">
<link rel="stylesheet" href="https://rawgithub.com/yannickulrich/presenter/master/lib/jqMath/jqmath-0.4.0.css">
<script src="http://code.jquery.com/jquery-1.4.3.min.js"></script>
<script src="https://rawgithub.com/yannickulrich/presenter/master/lib/jqMath/jqmath-etc-0.4.0.min.js"></script>
<style>
div {
position: absolute;
}
line {
stroke-width: .4px;
}
#stats-table {
width: 460px;
border: none;
left: 0px;
}
</style>
</head>
<body>
<div id="graph"></div>
<div id="controls">
<button onclick="step();">Step</button>
<button onclick="changeK(1);">Increase K</button>
<button onclick="changeK(-1);">Decrease K</button>
<table id="stats-table">
<tr>
<td>
$∣ \{ x_i : {{x_i}^{t-1}∈c_k , {x_i}^{t}∉c_k } \} ∣$
</td>
<td>
$∑↙{k=1}↖K ∑↙{x_i∈c_k} {‖ x_i - μ_k ‖^2}$
</td>
<!--
<td>
$\ov{(m_i-x)}∣x∈S_i$
</td>
<td>
$\ov{(m_i-m_j)}$
</td>
-->
</tr>
</table>
</div>
<script src="unpkg.com/@jbeuckm/k-means-js"></script>
<script type="text/javascript" src="http://mbostock.github.com/d3/d3.js"></script>
<script>
var ranges = [ [0,10], [0,10] ];
var points = kmeans.generateRandomPoints(ranges, 1000);
var means = [];
var assignments = kmeans.assignPointsToMeans(points, means);
var svg = d3.select('#graph').append('svg').attr('width',960).attr('height',500);
var graph = svg.append('g').attr('transform', 'translate(460,0)');
var meanLayer = graph.append('g');
var xScale = d3.scale.linear().domain([0,10]).range([0,500]);
var yScale = d3.scale.linear().domain([0,10]).range([0,500]);
var color = d3.scale.category10();
function redraw() {
var pointDots = graph.selectAll('.pointDots').data(points);
pointDots.enter().append('circle').attr('class','pointDots')
.attr('r', 2)
.attr('cx',function(d){ return xScale(d[0]); })
.attr('cy',function(d){ return yScale(d[1]); });
var assignmentLines = meanLayer.selectAll('.assignmentLines').data(assignments);
assignmentLines.enter().append('line').attr('class','assignmentLines')
.attr('x1',function(d, i){ return xScale(points[i][0]); })
.attr('y1',function(d, i){ return yScale(points[i][1]); })
.attr('x2',function(d, i){ return xScale(means[d][0]); })
.attr('y2',function(d, i){ return yScale(means[d][1]); })
.attr('stroke', function(d) { return color(d); });
assignmentLines.transition().duration(500)
.attr('x2',function(d, i){ return xScale(means[d][0]); })
.attr('y2',function(d, i){ return yScale(means[d][1]); })
.attr('stroke', function(d) { return color(d); });
var meanDots = meanLayer.selectAll('.meanDots').data(means);
meanDots.enter().append('circle').attr('class','meanDots')
.attr('r', 5)
.attr('stroke', function(d, i) { return color(i); })
.attr('stroke-width', 3)
.attr('fill', 'white')
.attr('cx',function(d){ return xScale(d[0]); })
.attr('cy',function(d){ return yScale(d[1]); });
meanDots.transition().duration(500)
.attr('cx',function(d){ return xScale(d[0]); })
.attr('cy',function(d){ return yScale(d[1]); });
meanDots.exit().remove();
}
changeK(5);
redraw();
function step() {
oldAssignments = assignments;
kmeans.moveMeansToCenters(points, assignments, means);
assignments = kmeans.assignPointsToMeans(points, means);
var changeCount = kmeans.countChangedAssignments(assignments, oldAssignments);
var aveDistance = kmeans.findAverageDistancePointToMean(points, means, assignments);
var aveMeanSeparation = kmeans.findAverageMeanSeparation(means);
var sse = kmeans.sumSquaredError(points, means, assignments);
var row = d3.select('#stats-table').append('tr');
row.append('td').html(changeCount);
row.append('td').html(sse);
redraw();
}
function changeK(amt) {
if (amt > 0) {
while (amt--) {
var i = Math.floor(Math.random() * points.length);
var p = points[i];
var newPoint = p.slice(0);
console.log("adding new point "+newPoint);
means.push(newPoint);
}
}
else while (amt < 0) {
means.pop();
amt++;
}
assignments = kmeans.assignPointsToMeans(points, means);
redraw();
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment