Skip to content

Instantly share code, notes, and snippets.

@hfhchan
Last active November 15, 2017 08:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hfhchan/344ce287b51bcd2d0a749e085739e84d to your computer and use it in GitHub Desktop.
Save hfhchan/344ce287b51bcd2d0a749e085739e84d to your computer and use it in GitHub Desktop.
COMP4331 Assignment 2
1. Use Google Chrome 61.0 or above.
2. Navigate to this page.
3. Press F12.
4. Choose the "Console" tab.
5. Paste in the script and press enter.
// Input File
var input_txt = '15\n0| 1.0 1.0\n1| 2.0 1.0\n2| 2.0 4.0\n3| 4.0 5.0\n4| 5.0 4.0\n5| 5.0 5.0\n6| 5.0 6.0\n7| 6.0 5.0\n8| 9.0 9.0\n9| 10.0 9.0\n10| 10.0 10.0\n11| 11.0 9.0\n12| 13.0 13.0\n13| 14.0 10.0\n14| 14.0 12.0';
// Load Data
var rows = input_txt.split("\n");
rows.shift();
var dataset = rows.map((row) => {
let point = row.split('| ');
let data = point[1].split(' ');
return {label: +point[0], x: +data[0], y: +data[1], group:null }
});
var cluster_k_means = (input_dataset, k) => {
// Clone the dataset
let dataset = JSON.parse(JSON.stringify(input_dataset));
// Pick random k points
const shuffled = dataset.sort(() => .5 - Math.random());// shuffle
let selected = shuffled.slice(0, k);
let means = selected.map((point, i) => ({group: i, x: point.x, y: point.y}));
// Repeat
let iter = 0;
while (true) {
if (++iter > 20) {
throw 'Could not Converge';
}
// Assign each point to closest mean
let changed = 0;
dataset.forEach((point) => {
let newgroup = means.map((mean) => {
// Find distances to the mean of each cluster
return (mean.x - point.x) * (mean.x - point.x) * (mean.y - point.y) * (mean.y - point.y);
}).reduce((accumulator, distance, index) => {
// Find the closest mean
if (accumulator[0] > distance) {
return [distance, index];
}
return accumulator;
}, [Number.MAX_VALUE, null])[1];
if (point.group !== newgroup) {
changed = 1;
}
point.group = newgroup;
});
if (!changed) {
break;
}
// Recompute the means
for (let j = 0; j < k; j++) {
// Get points for cluster
let cluster = dataset.filter((point) => point.group == j);
// Sum each attribute then assign new mean
let sum = cluster.reduce((acc, point) => { acc.x += point.x; acc.y += point.y; return acc }, {x: 0, y: 0});
means[j].x = sum.x / cluster.length;
means[j].y = sum.y / cluster.length;
}
}
// Ensure every cluster has at least one point. If not, try again.
if (means.some((mean) => dataset.filter((point) => point.group == mean.group).length === 0)) {
return cluster_k_means(input_dataset, k);
}
dataset.sort((a, b) => a.label - b.label);
const output = means.map((mean) => {
let j = mean.group + 1;
let cluster = dataset.filter((point) => point.group == mean.group);
return 'Cluster ' + j + ': ' + cluster.map((point) => point.label).join(' ');
}).join("\n");
console.log(output);
};
// Cluster by 3
cluster_k_means(dataset, 3);
// Cluster by 4
cluster_k_means(dataset, 4);
> cluster_k_means(dataset, 3);
< Cluster 1: 3 4 5 6 7
< Cluster 2: 8 9 10 11 12 13 14
< Cluster 3: 0 1 2
> cluster_k_means(dataset, 4);
< Cluster 1: 12 13 14
< Cluster 2: 3 4 5 6 7
< Cluster 3: 0 1 2
< Cluster 4: 8 9 10 11
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment