Three.js Clustering Algorithms (K-means vs DBSCAN in 3D)

Animated unsupervised clustering in Three.js, comparing K-means with k-means++ seeding (assign and update steps converging) against density-based DBSCAN growing clusters and flagging noise on 3D blobs, rings and moons.

Key topics: k-means visualization, dbscan, clustering algorithms, unsupervised learning, three.js data science, k-means++

What this code does

- K-Means: alternates assigning each point to the nearest centroid and moving centroids to their members' mean, until no point changes cluster.
- k-means++: seeds centroids far apart (sampled ∝ squared distance), which avoids bad local minima.
- Limits of K-Means: it assumes convex blobs of similar size, so rings and moons get cut into wedges.
- DBSCAN: core points have at least minPts neighbours within ε; clusters grow by flooding through core points, and points reached by none are noise.
- No k: DBSCAN finds arbitrary shapes and the number of clusters itself, but is sensitive to ε.
- Controls: algorithm, dataset, k, true blob count, ε, minPts, speed and restart.

Continue Learning

JavaScript Implementation

ES6+
// Lloyd's k-means: alternate assignment and centroid update until nothing moves

function kmeansStep (points, centroids, labels) {
  points.forEach((p, i) => {
    labels[i] = centroids.reduce((best, c, k) => (p.distanceToSquared(c) < p.distanceToSquared(centroids[best]) ? k : best), 0)
  })
  centroids.forEach((c, k) => {
    const members = points.filter((_, i) => labels[i] === k)
    if (members.length) c.copy(members.reduce((s, p) => s.add(p), new THREE.Vector3()).divideScalar(members.length))
  })
}
// DBSCAN instead grows clusters from "core" points that have ≥ minPts neighbours within ε.