Crowds and Loners
At a party, people bunch up into crowds. A crowd can be any shape: a long queue, a circle round the cake. And some people stand all alone. Robo finds crowds by asking one question: how many friends are close to me?
Each dot is a person. Every dot draws a friend circle around itself. If enough friends fit inside, it is part of a crowd! My circles are too small right now, so these two curvy crowds are broken into bits. Make the friend circle bigger!
Look: hover or tap anywhere to see a friend circle and count the dots inside it.
crowd member (lots of friends)edge of a crowdloner
Crowd finder vs pizza magnets
The same dots, grouped two ways. Pizza magnets (k-means, from the Pizza Shop lesson) pull dots to the nearest middle, so they cut curvy shapes in half.
Challenges
Try this: slide the friend circle up slowly on Moons and watch the little bits join together.
What just happened?
- Nobody told Robo how many crowds there were. It worked that out by itself.
- A dot with enough friends inside its circle is a crowd member. Crowd members pass the crowd along to their friends, so a crowd can snake around any shape.
- A dot near a crowd, without enough friends of its own, joins at the edge. A dot near nobody is a loner.
- Too small a circle breaks crowds into bits and makes lots of loners. Too big a circle glues separate crowds together. The right size depends on how packed your dots are.
- Pizza magnets always make round-ish groups and give every dot a group. The crowd finder follows shapes and is allowed to say "this one belongs to nobody".
How it works
Count friends
Every dot counts how many dots are inside its friend circle.
Start a crowd
Pick a dot with enough friends. It starts a new crowd with a new colour.
Spread it
Its friends join. Any friend who also has enough friends passes the crowd on to their friends too.
Leftovers are loners
When nobody is left to visit, any dot that never joined a crowd is a loner.
For grown-ups: what's really going on
This is DBSCAN (Density-Based Spatial Clustering of Applications with Noise; Ester, Kriegel, Sander and Xu, 1996). Two parameters: the radius ε ("friend circle size", in pixels here) and minPts ("friends needed", counting the point itself, as scikit-learn's min_samples does).
- A core point has at least
minPtspoints in its ε-neighbourhood. A border point is not core but lies within ε of a core point. Everything else is noise. - Clusters are the connected components of core points under "within ε", plus their border points (density-reachability). Border points touching two clusters go to whichever reaches them first, which is the only order-dependent part.
- The step-by-step replay is the standard queue-based expansion. Neighbourhoods are found by brute force (O(n²)); real libraries use a k-d tree or grid to get close to O(n log n).
- Unlike k-means, DBSCAN needs no
k, finds non-convex shapes and labels outliers. It struggles when clusters have very different densities (one ε cannot suit both); HDBSCAN and OPTICS address that. A common way to choose ε is the elbow of the sorted k-distance plot. - The "% match" scores use the adjusted Rand index against the generating groups (each noise point treated as its own group), clipped at 0. k-means uses k-means++ seeding with k set to the true number of groups.
Every preset comes from a seeded random generator (mulberry32), so a seed always gives the same dots.