|
<html> |
|
<head> |
|
<script src="http://d3js.org/d3.v3.min.js"></script> |
|
<style> |
|
body { font-family: "Open Sans", Calibri, Verdana; } |
|
</style> |
|
</head> |
|
<body> |
|
<div id="header"><div>An iterative algorithm: k-means</div> |
|
<!-- Some interactive controls --> |
|
<button id="addClusters">Random Clusters</button> |
|
<button id="clusterPoints">Cluster Points</button> |
|
<button id="moveMeans">Move Clusters</button> |
|
</div> |
|
|
|
<div id="chart"></div> |
|
|
|
<script> |
|
var height = 500; |
|
var width = 600; |
|
|
|
var svg = d3.select("#chart").append("svg").attr("height", height).attr("width", width).append("g"); |
|
|
|
var xScale = d3.scale.linear().domain([0, 50]).range([0, width]); |
|
var yScale = d3.scale.linear().domain([0, 50]).range([height, 0]); |
|
|
|
// A voronizer function |
|
var voronoi = d3.geom.voronoi() |
|
.x(function (cluster) { return xScale(cluster.x); }) |
|
.y(function (cluster) { return yScale(cluster.y); }) |
|
.clipExtent([[0,0], [width, height]]); |
|
|
|
// A helper function for plotting Voronoi polygons |
|
function polygonPath(d) { |
|
return "M" + d.join("L") + "Z"; |
|
} |
|
|
|
// The data array for cluster centers. |
|
// We'll make six clusters, in random locations away from the edges of the plot. |
|
var clusters = []; |
|
var numClusters = 6; |
|
|
|
// Each cluster is represented by a <text> and a <path> element. |
|
var clusterTexts; |
|
var clusterBorders; |
|
|
|
// The data array for points to be clustered. |
|
var points = []; |
|
var pointTexts; |
|
var randomNormal = d3.random.normal(0, 2); |
|
|
|
for (var cluster = 0; cluster < 6; cluster++) { |
|
var clusterCenter = { x: 40 * Math.random() + 5, y: 40 * Math.random() + 5 }; |
|
|
|
for (point = 0; point < 10; point++) { |
|
points.push({ id: points.length, x: clusterCenter.x + randomNormal(), y: clusterCenter.y + randomNormal(), cluster: "" }); |
|
} |
|
} |
|
|
|
// Add circles for each point |
|
svg.selectAll("circle").data(points).enter().append("circle") |
|
.style("fill", "#ccc").style("opacity", 0.7) |
|
.attr("cx", function (p) { return xScale(p.x); }) |
|
.attr("cy", function (p) { return yScale(p.y); }) |
|
.attr("r", 4); |
|
|
|
// Create <text> elements for each point, showing |
|
// their current assignment. |
|
pointTexts = svg.selectAll(".point").data(points); |
|
|
|
pointTexts.enter().append("text").attr("class", "point"); |
|
|
|
pointTexts |
|
.attr("id", function (point) { return "p" + point.id; }) |
|
.attr("x", function (point) { return xScale(point.x); } ) |
|
.attr("y", function (point) { return yScale(point.y); } ) |
|
.style("font-size", "small") |
|
.text(function (point) { return point.cluster; }); |
|
|
|
|
|
// Now we define three functions, which correspond |
|
// to initialization and the two steps of the iterative algorithm: |
|
|
|
// Initialization: place clusters randomly |
|
d3.select("#addClusters").on("click", function() { |
|
clusters = []; |
|
|
|
for (var i = 0; i < numClusters; i++) { |
|
clusters.push( { x: 50 * Math.random(), y: 50 * Math.random(), n: 0 } ); |
|
} |
|
|
|
// Create <text> elements for each cluster. |
|
var texts = svg.selectAll(".cluster").data(clusters); |
|
|
|
texts.enter().append("text").attr("class", "cluster"); |
|
|
|
texts |
|
.attr("x", function (cluster) { return xScale(cluster.x); } ) |
|
.attr("y", function (cluster) { return yScale(cluster.y); } ) |
|
.text(function (cluster, i) { return i; } ) |
|
.style("fill", "red") |
|
.style("font-size", "xx-large"); |
|
|
|
clusterBorders = svg.selectAll(".clusterborder").data(voronoi(clusters)); |
|
clusterBorders.enter().append("path").attr("class", "clusterborder") |
|
.style("fill", "none").style("stroke", "#cccccc"); |
|
clusterBorders.attr("d", polygonPath); |
|
|
|
clusterTexts = texts; |
|
}); |
|
|
|
// Iterative step 1: Move the cluster centers based on the current |
|
// assignment of points to clusters. |
|
d3.select("#moveMeans").on("click", function() { |
|
// Reset the clusters |
|
clusters.forEach( function (cluster) { |
|
cluster.x = 0; cluster.y = 0; cluster.n = 0; |
|
} ); |
|
|
|
// Sum up x and y coordinates |
|
points.forEach( function (point) { |
|
clusters[ point.cluster ].x += point.x; |
|
clusters[ point.cluster ].y += point.y; |
|
clusters[ point.cluster ].n ++; |
|
}); |
|
|
|
// Divide to get the average |
|
clusters.forEach( function (cluster) { |
|
// Move empty clusters to random locations |
|
if (cluster.n === 0) { |
|
cluster.x = 40 * Math.random() + 5; |
|
cluster.y = 40 * Math.random() + 5; |
|
} |
|
else { |
|
cluster.x /= cluster.n; |
|
cluster.y /= cluster.n; |
|
} |
|
}); |
|
|
|
// Now change the underlying data and move the |
|
// <text> elements. |
|
clusterTexts.data(clusters); |
|
clusterTexts.transition() |
|
.attr("x", function (cluster) { return xScale(cluster.x); } ) |
|
.attr("y", function (cluster) { return yScale(cluster.y); } ); |
|
|
|
clusterBorders.data(voronoi(clusters)); |
|
clusterBorders.transition() |
|
.attr("d", polygonPath); |
|
}); |
|
|
|
// Iterative step 2: Reassign points to their nearest cluster center. |
|
d3.select("#clusterPoints").on("click", function () { |
|
// Consider every point... |
|
points.forEach( function (point, i) { |
|
var shortestDistance = Number.POSITIVE_INFINITY; |
|
// Find the nearest cluster... |
|
var newCluster = -1; |
|
clusters.forEach( function (cluster, id) { |
|
var distance = Math.sqrt(Math.pow(point.x - cluster.x, 2) + Math.pow(point.y - cluster.y, 2)); |
|
if (distance < shortestDistance) { |
|
shortestDistance = distance; |
|
newCluster = id; |
|
} |
|
} ); |
|
if (point.cluster != newCluster) { |
|
d3.select("#p" + point.id).transition().duration(1000) |
|
.style("font-size", "x-large"); |
|
} |
|
point.cluster = newCluster; |
|
} ); |
|
|
|
// Update the text of the points to reflect the |
|
// new cluster assignments. |
|
pointTexts.data(points); |
|
pointTexts.transition().delay(1000).duration(1000) |
|
.text(function (point) { return point.cluster; }); |
|
|
|
pointTexts.transition().delay(2000).duration(1000) |
|
.style("font-size", "small"); |
|
|
|
}); |
|
|
|
</script> |
|
</body> |
|
</html> |