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++
Game Over
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.
Related Demos
Continue Learning
JavaScript Implementation
// 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 ε.