COMP4331 Assignment 2

README

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.

question1.js

// 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);

Sample Output

> 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