K-means clustering is a method to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster centers or cluster centroid).

Given a set of observations, where each observation is a d-dimensional real vector, k-means clustering aims to partition the n observations into k(≤ n) sets so as to minimize the within-cluster sum of squares (i.e. variance).

Complexity

  • Time: $O(n^{2k+1})$ for 2-dimensional real vector

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

    // define helper functions {
const shuffle = a => {
  const array = a.slice(0)
  const copy = []
  let n = array.length

  while (n) {
    let i = Math.floor(Math.random() * n--)
    copy.push(array.splice(i, 1)[0])
  }

  return copy
}

const sum = (x, y) => x + y
const chooseRandomCenters = (data, k) => shuffle(data).slice(0, k)
const pointify = ([x, y]) => `(${x}, ${y})`
const arrayify = a => a.map(pointify)
const stringify = a => arrayify(a).join(', ')
const distance = ([x1, y1], [x2, y2]) => sum(Math.pow(x1 - x2, 2),
    Math.pow(y1 - y2, 2))
const col = (a, i) => a.map(p => p[i])
const mean = a => a.reduce(sum, 0) / a.length
const centerOfCluster = cluster => [
  mean(col(cluster, 0)),
  mean(col(cluster, 1)),
]
const reCalculateCenters = clusters => clusters.map(centerOfCluster)
const areCentersEqual = (c1, c2) => !!c1 && !!c2 && !(c1 < c2 || c2 < c1)

function cluster(data, centers) {
  const clusters = centers.map(() => [])

  for (let i = 0; i < data.length; i++) {
    const point = data[i]
    let minDistance = Infinity
    let minDistanceIndex = -1

    for (let j = 0; j < centers.length; j++) {
      const d = distance(point, centers[j])

      if (d < minDistance) {
        minDistance = d
        minDistanceIndex = j
      }
    }

    if (!clusters[minDistanceIndex] instanceof Array) {
      clusters[minDistanceIndex] = []
    }

    clusters[minDistanceIndex].push(point)
  }

  return clusters
}

// define input variables
const unClusteredData = Randomize.Array2D(
    { N: Randomize.Integer({ min: 10, max: 25 }) })
const k = Randomize.Integer(
    { min: 2, max: Math.floor(unClusteredData.length / 5) })

const recenterAndCluster = (originalClusters) => {
  const centers = reCalculateCenters(originalClusters)
  const clusters = cluster(unClusteredData, centers)
  return { centers, clusters }
}

const improve = (loops, clusters, centers) => {
  const allowImprove = () => loops < 1000

  if (!allowImprove()) {
    return { clusters, centers }
  }

  loops++

  const ret = recenterAndCluster(clusters)

  // trace {
  array2dTracer.set(clusters.map(c => c.map(pointify)))
  scatterTracer.set([unClusteredData, ...ret.clusters, ret.centers])

  logTracer.println('')
  logTracer.println(`Iteration #${loops} Result: `)
  logTracer.println(`\tClusters:`)
  logTracer.println(
      `\t\t${ret.clusters.map(c => stringify(c)).join(`\n\t\t`)}`)
  logTracer.println(`\tCenters:`)
  logTracer.println(`\t\t${stringify(ret.centers)}`)
  logTracer.println('')

  Tracer.delay()

  if (!allowImprove() || areCentersEqual(centers, ret.centers)) {
    return ret
  }

  return improve(loops, ret.clusters, ret.centers)
}

(function main() {

  // Start with random centers
  const centers = chooseRandomCenters(unClusteredData, k)

  // trace {
  logTracer.println(
      `Initial random selected centers = ${stringify(centers)}`)
  scatterTracer.set([unClusteredData, ...[[], []], centers])

  Tracer.delay()

  // Cluster to the random centers
  const clusters = cluster(unClusteredData, centers)

  // trace {
  logTracer.println(
      `Initial clusters = \n\t${clusters.map(stringify).join('\n\t')}`)
  array2dTracer.set(clusters.map(c => c.map(pointify)))
  scatterTracer.set([unClusteredData, ...clusters, centers])

  Tracer.delay()

  // start iterations here
  const ret = improve(0, clusters, centers)

  // trace {
  Tracer.delay()

  logTracer.println(
      `Final clustered data = \n\t${ret.clusters.map(stringify)
          .join('\n\t')}`)
  logTracer.println(`Best centers = ${stringify(ret.centers)}`)
  array2dTracer.set(ret.clusters.map(c => c.map(pointify)))
  scatterTracer.set([unClusteredData, ...ret.clusters, ret.centers])
  Tracer.delay()
  
})()