DBSCAN

Part of the Unsupervised Learning section of Coddy's Machine Learning journey. Lesson 20 of 51.

This chapter finds crowds of any shape, and the points that belong to none. By its end, you map a valley's lights:

A night map of a valley: a long curved town, a round town and a small village, each in its own color and marker, and 10 lone lights as gray x marks between them

First, the seals' sandbars that broke k-means in When K-Means Fails. DBSCAN follows the crowds instead:

Two charts of the same 200 seals on two curved sandbars. Left, k-means cuts them into a left and a right half. Right, DBSCAN finds each sandbar whole, with a small circle labelled eps around one seal

A point with min_samples points (itself included) within eps, the circle's radius, sits in a crowd. Crowds spread through such points. No k to choose:

from sklearn.cluster import DBSCAN
labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
print(labels.max() + 1)

This prints 2: crowds are numbered from 0, so the largest plus one counts them.

Challenge

Medium

On a frozen lake, skaters race along a track that winds between two islands, and a crowd watches a hockey game. k-means would cut the track into pieces. The program reads eps in meters.

Fit DBSCAN with that eps and min_samples=5; keep the crowds in labels.
Print how many crowds it found.
Draw them with draw_crowds(ax, X, labels) and show.

For another lake and eps 3.5:

Crowds found: 3

A chart titled Skaters on the Lake: a winding S-shaped track of 150 skaters in blue, a round crowd of 30 in orange above its left bend and a group of 22 in green below its right bend, with a legend of sizes

Coddy describes your chart. Then run it with eps 8: where did the crowds go?

Try it yourself

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN

# Where 170 skaters stood on the frozen lake, in meters
skaters = pd.read_csv("skaters.csv")
X = np.column_stack([skaters["x_m"], skaters["y_m"]])
eps = float(input())


# Draws each crowd in its own color, labelled with its size
def draw_crowds(ax, X, labels):
    for crowd in range(labels.max() + 1):
        rows = labels == crowd
        ax.scatter(X[rows, 0], X[rows, 1], s=14, label=f"{rows.sum()} skaters")
    ax.legend()


fig, ax = plt.subplots()
ax.set_title("Skaters on the Lake")
ax.set_xlabel("East (m)")
ax.set_ylabel("North (m)")

# Write your code below