Visual Data Analysis — Lecture 5 Practical: Smart Clustering of Cherry Blossom Photos¶

Objective¶

Lecture 5 made one point again and again: a single run of a clustering algorithm is never sufficient. The result depends on the parameters, on the distance function and on the preprocessing, and no formula tells you the "right" settings. In this practical you do what the lecture recommends: you run the clustering several times, compare the runs, assess what you get, revise your plan, and finally ask what you have learned about the data, not only about the algorithm.

Framing with the Six Analytical Questions¶

  1. What are the entities? Part 1: photo-taking events (geolocated photos that mention cherry blossoms). Part 2: weeks.
  2. How are they characterised? Part 1: location and time. Part 2: the number of photos taken in each of five regions of North America.
  3. In what context? Geographic space and the yearly cycle (day of the year, year).
  4. What patterns do we seek? Concentrations of photo-taking in space and time, places where they recur, and typical weekly activity profiles.
  5. How do we assess? Do the groups survive when the parameters change? Do they correspond to real places and seasons? Does the result depend on a choice that has nothing to do with the data?
  6. What knowledge do we generate? Where and when people photograph cherry blossoms, and how the timing differs between places and years.

How this notebook is organised¶

  • Part 1 (in class, about 60 minutes): density-based clustering of the photos (Stages 1–7). Stage 5 is optional.
  • Part 2 (rest of the session or homework, about 40 minutes): partition-based clustering (k-means) of the weekly counts (Stages 8–14). Stages 13 and 14 are optional.
  • Part 3 (homework, about 15 minutes): audit two confident summaries of single runs.

Most stages are look-and-notice: you predict what a result will look like before running the cell, then read a short note on what it actually shows. Some stages are marked (interactive). It is fine if you do not finish everything in class; the notes after each stage explain what you would have found.

The data¶

  • Photos. 9,703 geolocated photos taken in North America between 2007 and 2016 (mostly in the United States, with some in Canada) whose titles or tags mention cherry blossoms. The records are public Flickr metadata. Only the location and the time are used here; no user information. Positions were converted to kilometres (an equal-area projection, columns x_km, y_km), and time to days since 1 January 2007 (t_days), so that radii can be given in km and days.
  • Weekly counts. The number of such photos per week in five regions: NW, SW, NE, SE and GL (Great Lakes), 521 weeks.
  • The base map is made from Natural Earth data (public domain).

Companion: the web demonstrator¶

The same two data sets, with precomputed parameter sweeps, are in the SmartIterator demonstrator: https://geoanalytics.net/and/SmartIterator/demo (open Cherry blossom photos and Cherry blossom photos per week). You can compare your results with it, and try the same ideas there with the Explore dialog.

In [1]:
# =============================================================================
# CONFIGURATION
# All data-set specific details (file names, default parameters, place names)
# live here. Nothing below this cell should contain a hardcoded path or a
# magic parameter value.
# =============================================================================
import math
import warnings

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import ipywidgets as widgets
from IPython.display import clear_output, display
from sklearn.cluster import DBSCAN, KMeans
from sklearn.manifold import MDS
from sklearn.metrics import adjusted_rand_score, silhouette_samples, silhouette_score
from sklearn.preprocessing import MinMaxScaler, StandardScaler

warnings.filterwarnings("ignore")
sns.set_theme(style="whitegrid")
plt.rcParams["figure.figsize"] = (10, 6)

# --- Files (keep them in the same folder as this notebook) ---
PHOTOS_CSV = "cherry_photos.csv"
WEEKS_CSV = "weekly_counts_by_regions.csv"
BASEMAP_IMG = "north_america_basemap.jpg"
MAP_BOUNDS = (-132.0, -52.0, 16.5, 54.5)       # lon_min, lon_max, lat_min, lat_max covered by the base map

# --- Part 1: density-based clustering of the photos ---
RS_DEFAULT, RT_DEFAULT, N_DEFAULT = 25, 7, 7     # spatial radius (km), temporal radius (days), min. neighbours
RS_SWEEP = list(range(10, 51, 5))                # the three parameter sweeps of Stage 4
RT_SWEEP = list(range(1, 15))
N_SWEEP = list(range(3, 13))
SIL_SAMPLE = 3000                                # silhouette is computed on a random sample of this size
EARTH_RADIUS_KM = 6371.0088                      # mean radius of the Earth, used for great-circle distances
RS_REF, RT_REF = RS_DEFAULT, RT_DEFAULT          # the FIXED ruler (km, days) with which all quality indicators are measured
MIN_PHOTOS_PER_PLACE = 100                       # smaller places are not analysed in Stage 7
MIN_PHOTOS_PER_CELL = 15                         # a (place, year) cell needs at least this many photos

# --- Part 2: k-means on weekly counts ---
REGIONS = ["NW", "SW", "NE", "SE", "GL"]
REGION_NAMES = {"NW": "north-west", "SW": "south-west", "NE": "north-east", "SE": "south-east", "GL": "Great Lakes"}
K_SWEEP = list(range(2, 16))
K_DEFAULT, SEED_DEFAULT = 7, 10

# --- A short list of cities, used only to give names to the places you find ---
KNOWN_PLACES = {
    "Washington DC": (38.9, -77.0), "New York": (40.7, -74.0), "Philadelphia": (40.0, -75.2), "Boston": (42.4, -71.1),
    "Toronto": (43.7, -79.4), "Montreal": (45.5, -73.6), "Ottawa": (45.4, -75.7), "Chicago": (41.9, -87.6), "Toledo OH": (41.65, -83.55),
    "Detroit": (42.3, -83.0), "Pittsburgh": (40.4, -80.0), "Cincinnati": (39.1, -84.5), "Raleigh": (35.8, -78.6), "Atlanta": (33.75, -84.4),
    "Macon GA": (32.8, -83.6), "Miami": (25.8, -80.2), "Houston": (29.8, -95.4), "Dallas": (32.8, -96.8), "Denver": (39.7, -105.0),
    "Seattle": (47.6, -122.3), "Portland OR": (45.5, -122.7), "Salem OR": (44.9, -123.0), "Vancouver": (49.3, -123.1), "Victoria BC": (48.4, -123.4),
    "San Francisco": (37.8, -122.4), "Sacramento": (38.6, -121.5), "Los Angeles": (34.1, -118.2), "Huntington Beach CA": (33.66, -118.0),
    "San Diego": (32.7, -117.2),
}
In [2]:
# =============================================================================
# REUSABLE FUNCTIONS (Part 1)
# You do not need to read these to do the practical. Stage 2 explains the idea
# behind st_cluster(); the other functions load, summarise and draw.
# =============================================================================
def load_photos(path=PHOTOS_CSV):
    """Read the photo table: lon, lat, date_taken, year, day_of_year, x_km, y_km, t_days."""
    return pd.read_csv(path, parse_dates=["date_taken"])


# --- distances in space -------------------------------------------------------
def great_circle_km(lon1, lat1, lon2, lat2):
    """REAL spatial distance: the shortest way over the globe (haversine formula), in km. Works on single values and on arrays."""
    p1, p2 = np.radians(lat1), np.radians(lat2)
    a = np.sin((p2 - p1) / 2) ** 2 + np.cos(p1) * np.cos(p2) * np.sin(np.radians(lon2 - lon1) / 2) ** 2
    return 2 * EARTH_RADIUS_KM * np.arcsin(np.sqrt(np.minimum(1.0, a)))


def flat_earth_km(lon1, lat1, lon2, lat2):
    """'FLAT EARTH': longitude and latitude treated as plane coordinates (Pythagoras on the degrees), 111.195 km per degree.
    Shown only to demonstrate the error: one degree of longitude is shorter than one degree of latitude."""
    return np.hypot(np.asarray(lon2) - lon1, np.asarray(lat2) - lat1) * (np.pi / 180 * EARTH_RADIUS_KM)


def compare_space_distances(df, max_km=60, n_pairs=100000, seed=1):
    """For many pairs of photos that are closer than max_km: real (great-circle) distance, flat-earth distance, and the distance in the
    projected coordinates x_km, y_km. Returns the three arrays."""
    from sklearn.neighbors import NearestNeighbors
    g = NearestNeighbors(radius=max_km).fit(df[["x_km", "y_km"]].values).radius_neighbors_graph(mode="connectivity").tocoo()
    keep = g.row < g.col
    i, j = g.row[keep], g.col[keep]
    pick = np.random.default_rng(seed).choice(len(i), size=min(n_pairs, len(i)), replace=False)
    i, j = i[pick], j[pick]
    lon, lat, x, y = df.lon.values, df.lat.values, df.x_km.values, df.y_km.values
    real = great_circle_km(lon[i], lat[i], lon[j], lat[j])
    ok = real > 1                                  # leave out (almost) identical positions: ratios are meaningless there
    return real[ok], flat_earth_km(lon[i], lat[i], lon[j], lat[j])[ok], np.hypot(x[i] - x[j], y[i] - y[j])[ok]


def combine_relative(rel_space, rel_time, combine="max"):
    """Combine the two relative distances: 'max', 'euclid' or 'manhattan'."""
    if combine == "max":
        return np.maximum(rel_space, rel_time)
    if combine == "euclid":
        return np.hypot(rel_space, rel_time)
    return rel_space + rel_time


def st_cluster(df, Rs, Rt, N, combine="max", use_time=True, subset=None, margin=1.08):
    """DBSCAN with a distance function for space AND time (the recipe of the lecture, slides 44-45).

    elementary distances:  space = great-circle distance in km, time = difference in days
    relative distances:    divided by the radii Rs (km) and Rt (days)
    combined by:           'max', 'euclid' or 'manhattan';  two photos are neighbours if the result is at most 1
    N                      minimum number of neighbours (the photo itself counts)
    use_time=False         clusters by space only (the time term is left out);  subset: indices of the photos to cluster
    Returns one label per photo: 0, 1, 2, ... for clusters, -1 for noise (or not clustered).

    How it is done fast: the fast map-projection coordinates (x_km, y_km) only FIND CANDIDATE neighbours (a box of Rs * margin and Rt around
    every photo); for the candidate pairs the exact great-circle distance and the combination rule decide; DBSCAN gets the resulting
    neighbour graph as a sparse 'precomputed' distance matrix and eps = 1.
    """
    idx = np.arange(len(df)) if subset is None else np.asarray(subset)
    lon, lat, t = df.lon.values[idx], df.lat.values[idx], df.t_days.values[idx]
    if not use_time:                               # space only: DBSCAN with the haversine (great-circle) metric, eps in radians
        found = DBSCAN(eps=Rs / EARTH_RADIUS_KM, min_samples=N, metric="haversine", algorithm="ball_tree").fit(np.radians(np.c_[lat, lon])).labels_
    else:
        from scipy.sparse import coo_matrix
        from sklearn.neighbors import NearestNeighbors
        box = np.c_[df.x_km.values[idx] / (Rs * margin), df.y_km.values[idx] / (Rs * margin), t / Rt]
        g = NearestNeighbors(radius=1.0, metric="chebyshev").fit(box).radius_neighbors_graph(mode="connectivity").tocoo()
        i, j = g.row, g.col
        d = combine_relative(great_circle_km(lon[i], lat[i], lon[j], lat[j]) / Rs, np.abs(t[i] - t[j]) / Rt, combine)
        near = d <= 1.0
        n = len(idx)
        graph = coo_matrix((np.r_[np.maximum(d[near], 1e-9), np.full(n, 1e-9)], (np.r_[i[near], np.arange(n)], np.r_[j[near], np.arange(n)])), shape=(n, n)).tocsr()
        found = DBSCAN(eps=1.0, min_samples=N, metric="precomputed").fit(graph).labels_
    labels = np.full(len(df), -1)
    labels[idx] = found
    return labels


def run_overview(labels):
    """(number of clusters, percentage of noise)"""
    return int(labels.max() + 1), 100.0 * float((labels < 0).mean())


def relative_space(df, Rs=RS_REF, Rt=RT_REF):
    """Coordinates measured with ONE FIXED ruler: x / Rs, y / Rs (km) and t / Rt (days). Used for the quality indicators, so that runs with
    different radii are measured in the same way."""
    return np.c_[df.x_km.values / Rs, df.y_km.values / Rs, df.t_days.values / Rt]


def quality_indicators(df, labels, sample=SIL_SAMPLE):
    """K, noise %, and for the CLUSTERED photos only (noise left out), measured in the fixed relative space:
    silhouette (on a random sample), SSE (sum of squared distances to the cluster centre) and explained variance (%)."""
    K, noise = run_overview(labels)
    out = {"K": K, "noise_pct": noise, "silhouette": np.nan, "SSE": np.nan, "explained_pct": np.nan}
    member = labels >= 0
    if K >= 2 and member.sum() > K:
        Z, lab = relative_space(df)[member], labels[member]
        out["silhouette"] = silhouette_score(Z, lab, sample_size=min(sample, len(lab)), random_state=1)
        centres = pd.DataFrame(Z).groupby(lab).transform("mean").values       # the centre of the photo's own cluster
        sse = float(((Z - centres) ** 2).sum())
        total = float(((Z - Z.mean(axis=0)) ** 2).sum())
        out["SSE"], out["explained_pct"] = sse, 100.0 * (1 - sse / total)
    return out


def sweep_st(df, param, values, Rs=RS_DEFAULT, Rt=RT_DEFAULT, N=N_DEFAULT, combine="max"):
    """Repeat the clustering for several values of ONE parameter ('Rs', 'Rt' or 'N') and collect the quality indicators."""
    rows = []
    for v in values:
        p = {"Rs": Rs, "Rt": Rt, "N": N}
        p[param] = v
        rows.append({param: v, **quality_indicators(df, st_cluster(df, p["Rs"], p["Rt"], p["N"], combine))})
    return pd.DataFrame(rows)


def best_jaccard(lab_a, lab_b):
    """For every cluster of lab_a: the best Jaccard overlap (intersection / union) with any cluster of lab_b."""
    ka, kb = lab_a.max() + 1, lab_b.max() + 1
    if ka <= 0 or kb <= 0:
        return np.zeros(max(ka, 0))
    both = (lab_a >= 0) & (lab_b >= 0)
    inter = np.zeros((ka, kb))
    np.add.at(inter, (lab_a[both], lab_b[both]), 1)
    size_a = np.bincount(lab_a[lab_a >= 0], minlength=ka)
    size_b = np.bincount(lab_b[lab_b >= 0], minlength=kb)
    return (inter / (size_a[:, None] + size_b[None, :] - inter)).max(axis=1)


def four_corner_color(x, y, min_x, max_x, min_y, max_y):
    """Colour from a position in a 2D projection (four-corner interpolation, as in the lecture)."""
    wx, wy = max_x - min_x, max_y - min_y
    rr, cc = y - min_y, x - min_x
    if wy < wx:
        rr *= wx / wy
    else:
        cc *= wy / wx
    d = max(wx, wy)
    rr1, cc1 = d - rr, d - cc
    dist = [math.hypot(rr, cc), math.hypot(rr, cc1), math.hypot(rr1, cc), math.hypot(rr1, cc1)]
    w = [max(0.0, (d - v) / d) for v in dist]
    reds, greens, blues = [228, 25, 255, 37], [220, 228, 18, 13], [0, 218, 6, 252]
    rgb = [min(255, max(0, sum(wi * ci for wi, ci in zip(w, ch)))) for ch in (reds, greens, blues)]
    return "#{:02x}{:02x}{:02x}".format(*[int(v) for v in rgb])


def similarity_colors(profiles):
    """profiles: one row per cluster (numeric characteristics). Clusters that are similar get similar colours:
    scale the characteristics, place the clusters in 2D with MDS, colour by position."""
    if len(profiles) < 3:
        return {i: c for i, c in zip(profiles.index, ["#1f77b4", "#d62728"])}
    xy = MDS(n_components=2, random_state=9).fit_transform(MinMaxScaler().fit_transform(profiles.values))
    lo, hi = xy.min(axis=0), xy.max(axis=0)
    return {c: four_corner_color(x, y, lo[0], hi[0], lo[1], hi[1]) for c, (x, y) in zip(profiles.index, xy)}


def cluster_summary(df, labels):
    """One row per cluster: size, centre, and its place in space, time and the yearly cycle."""
    d = df.assign(cluster=labels)
    d = d[d.cluster >= 0]
    g = d.groupby("cluster")
    out = pd.DataFrame({"photos": g.size(), "lon": g.lon.mean(), "lat": g.lat.mean(), "x_km": g.x_km.mean(), "y_km": g.y_km.mean(),
                        "t_mean": g.t_days.mean(), "day_of_year": g.day_of_year.mean(),
                        "first": g.date_taken.min().dt.strftime("%Y-%m-%d"), "last": g.date_taken.max().dt.strftime("%Y-%m-%d")})
    return out


def cluster_colors(df, labels):
    """Similarity-aware colours of the clusters: similar in position (x, y), in time and in the season -> similar colour."""
    s = cluster_summary(df, labels)
    return similarity_colors(s[["x_km", "y_km", "t_mean", "day_of_year"]]) if len(s) else {}


def name_place(lat, lon):
    """Nearest city of KNOWN_PLACES (a naming aid only: check the coordinates)."""
    return min(KNOWN_PLACES, key=lambda k: (KNOWN_PLACES[k][0] - lat) ** 2 + ((KNOWN_PLACES[k][1] - lon) * 0.78) ** 2)


def plot_map(df, labels, colors=None, ax=None, extent=None, title="", s_cluster=8, s_noise=3, show_noise=True, highlight=None):
    """Photos on the base map. Noise in grey, clusters in their colours. `highlight` (a set of clusters) draws the others in light grey."""
    ax = ax or plt.subplots(figsize=(11, 6.4))[1]
    lon0, lon1, lat0, lat1 = extent or MAP_BOUNDS
    if lon1 - lon0 > 20:                         # the base map image is too coarse to zoom into: plain background for zoomed maps
        ax.imshow(plt.imread(BASEMAP_IMG), extent=MAP_BOUNDS, cmap="gray", vmin=0, vmax=255, alpha=0.9, zorder=0)
        ax.grid(False)
    else:
        ax.set_facecolor("#f1f1f1")
        ax.grid(True, color="white", lw=1)
    inside = (df.lon >= lon0) & (df.lon <= lon1) & (df.lat >= lat0) & (df.lat <= lat1)
    noise = (labels < 0) & inside
    if show_noise:
        ax.scatter(df.lon[noise], df.lat[noise], s=s_noise, c="#7a7a7a", alpha=0.45, linewidths=0, zorder=1)
    member = (labels >= 0) & inside
    cols = [colors.get(c, "#1f77b4") if colors else plt.cm.tab20(c % 20) for c in labels[member]]
    if highlight is not None:
        cols = [c if lab in highlight else "#c9c9c9" for c, lab in zip(cols, labels[member])]
    ax.scatter(df.lon[member], df.lat[member], s=s_cluster, c=cols, alpha=0.85, linewidths=0, zorder=2)
    ax.set_xlim(lon0, lon1)
    ax.set_ylim(lat0, lat1)
    ax.set_aspect(1 / np.cos(np.radians((lat0 + lat1) / 2)))
    ax.set_xlabel("longitude")
    ax.set_ylabel("latitude")
    ax.set_title(title)
    return ax


def plot_cube(df, labels=None, colors=None, ax=None, title="", show_noise=True, s_cluster=6, s_noise=3, extent=None, highlight=None, point_colors=None):
    """A static SPACE-TIME CUBE: two axes of space (km, in the equal-area map projection) and time upwards (years). One fixed view, as in the
    earlier practicals. labels=None: all photos in one colour (or point_colors). Otherwise: noise in grey (if show_noise) and clusters in
    their colours; `highlight` (a set of clusters) draws all other clusters in light grey; `extent` limits the cube to a map window."""
    if ax is None:
        ax = plt.figure(figsize=(7, 6)).add_subplot(projection="3d")
    sel = np.ones(len(df), bool) if extent is None else (df.lon.between(extent[0], extent[1]) & df.lat.between(extent[2], extent[3])).values
    x, y, t = df.x_km.values, df.y_km.values, df.t_days.values
    if labels is None:
        ax.scatter(x[sel], y[sel], t[sel], s=s_cluster, c=point_colors[sel] if point_colors is not None else "#1f77b4", alpha=0.35, linewidths=0, depthshade=False)
    else:
        noise, member = (labels < 0) & sel, (labels >= 0) & sel
        if show_noise:
            ax.scatter(x[noise], y[noise], t[noise], s=s_noise, c="#7a7a7a", alpha=0.25, linewidths=0, depthshade=False)
        cols = [colors.get(c, "#1f77b4") if colors else plt.cm.tab20(c % 20) for c in labels[member]]
        if highlight is not None:
            cols = [c if lab in highlight else "#c9c9c9" for c, lab in zip(cols, labels[member])]
        ax.scatter(x[member], y[member], t[member], s=s_cluster, c=cols, alpha=0.85, linewidths=0, depthshade=False)
    ax.view_init(elev=25, azim=-115)                               # change the angles to look from another perspective
    dx, dy = max(np.ptp(x[sel]), 1.0), max(np.ptp(y[sel]), 1.0)
    ax.set_box_aspect((dx, dy, 0.55 * max(dx, dy)))                 # the same scale on both spatial axes
    ax.set_xlim(x[sel].min(), x[sel].max()); ax.set_ylim(y[sel].min(), y[sel].max()); ax.set_zlim(0, t.max())
    years = list(range(int(df.year.min()), int(df.year.max()) + 1, 2))
    ax.set_zticks([(pd.Timestamp(f"{yr}-01-01") - pd.Timestamp("2007-01-01")).days for yr in years])
    ax.set_zticklabels(years)
    ax.tick_params(labelsize=7)
    ax.set_xlabel("x (km)", fontsize=8, labelpad=2); ax.set_ylabel("y (km)", fontsize=8, labelpad=2); ax.set_zlabel("time", fontsize=8, labelpad=0)
    ax.set_title(title, fontsize=10)
    return ax


def plot_map_and_cubes(df, labels, colors, title, s_cluster=6, extent=None, highlight=None):
    """The map, and next to it two space-time cubes: with the noise (grey) and without it."""
    fig = plt.figure(figsize=(20, 6.2))
    gs = fig.add_gridspec(1, 3, width_ratios=[1.35, 1, 1])
    plot_map(df, labels, colors, ax=fig.add_subplot(gs[0]), title=title, s_cluster=s_cluster, extent=extent, highlight=highlight)
    plot_cube(df, labels, colors, ax=fig.add_subplot(gs[1], projection="3d"), title="Space-time cube, with noise (grey)", s_cluster=s_cluster, extent=extent, highlight=highlight)
    plot_cube(df, labels, colors, ax=fig.add_subplot(gs[2], projection="3d"), title="Space-time cube, without noise", show_noise=False, s_cluster=s_cluster, extent=extent, highlight=highlight)
    plt.tight_layout()
    return fig


def doy_label(d):
    """Day of the year -> 'Apr 03' (non-leap calendar)."""
    return (pd.Timestamp("2001-01-01") + pd.Timedelta(days=int(round(d)) - 1)).strftime("%b %d")


def place_table(df, place_labels):
    """The places (clusters of the spatial round) with at least MIN_PHOTOS_PER_PLACE photos: name, size, season window."""
    d = df.assign(place=place_labels)
    d = d[d.place >= 0]
    g = d.groupby("place")
    t = pd.DataFrame({"photos": g.size(), "lat": g.lat.mean(), "lon": g.lon.mean(), "median_day": g.day_of_year.median(),
                      "p10_day": g.day_of_year.quantile(0.10), "p90_day": g.day_of_year.quantile(0.90)})
    t["name"] = [name_place(a, b) for a, b in zip(t.lat, t.lon)]
    return t[t.photos >= MIN_PHOTOS_PER_PLACE].sort_values("photos", ascending=False)


def make_notice_checkpoint(question, options, reveal_html):
    """A low-stakes 'notice' checkpoint: pick an answer, then immediately see what the data shows. Not graded.
    It starts on a neutral placeholder so that the first real option also triggers the reveal."""
    placeholder = "? \u2014 choose one"
    radio = widgets.RadioButtons(options=[placeholder] + list(options), value=placeholder, description="", layout=widgets.Layout(width="760px"))
    out = widgets.Output()

    def on_change(change):
        if change["name"] != "value":
            return
        with out:
            clear_output(wait=True)
            if change["new"] not in (None, placeholder):
                display(widgets.HTML(reveal_html))

    radio.observe(on_change, names="value")
    return widgets.VBox([widgets.HTML(f"<b>{question}</b>"), radio, out])

Part 1 — Density-based clustering of the photos (in class, about 60 minutes)¶

Stage 1: Look at the data (about 5 min)¶

Every analysis starts with a look at the data in its context. Here the context is a map and the yearly cycle.

Before running the next cell, predict: (1) will the photos form a few clear concentrations or be spread evenly over the continent? (2) In which months were most photos taken, and does every year look alike?

In [3]:
df = load_photos()
print(f"{len(df):,} photos, taken between {df.date_taken.min():%Y-%m-%d} and {df.date_taken.max():%Y-%m-%d}")
display(df.head(3))

fig = plt.figure(figsize=(21, 6.4))
gs = fig.add_gridspec(1, 3, width_ratios=[1.35, 1, 1])
plot_map(df, np.full(len(df), -1), ax=fig.add_subplot(gs[0]), title="All photos (each dot is one photo)", s_noise=4)
year_colors = plt.cm.viridis((df.year - df.year.min()) / (df.year.max() - df.year.min()))
plot_cube(df, ax=fig.add_subplot(gs[1], projection="3d"), title="Space-time cube: time goes upwards (colour = year)", point_colors=year_colors, s_cluster=4)
ax2 = fig.add_subplot(gs[2])
sns.histplot(data=df, x="day_of_year", hue="year", bins=range(0, 367, 7), multiple="stack", palette="viridis", ax=ax2)
ax2.set_title("Photos per week of the year, stacked by year")
ax2.set_xlabel("day of the year")
plt.tight_layout()
plt.show()

print("Photos per year:", df.year.value_counts().sort_index().to_dict())
print("Day of the year, 5th / 50th / 95th percentile:", [doy_label(v) for v in np.percentile(df.day_of_year, [5, 50, 95])])
9,703 photos, taken between 2007-01-06 and 2016-12-24
lon lat date_taken year day_of_year x_km y_km t_days
0 -79.466309 43.654026 2015-05-11 00:51:54 2015 131 1317.717 2416.427 3052.0360
1 -79.466309 43.654026 2015-05-15 10:57:13 2015 135 1317.717 2416.427 3056.4564
2 -77.027031 38.888126 2011-04-01 09:54:38 2011 91 1615.602 1929.294 1551.4129
No description has been provided for this image
Photos per year: {2007: 647, 2008: 881, 2009: 1045, 2010: 1134, 2011: 1438, 2012: 1239, 2013: 1325, 2014: 773, 2015: 744, 2016: 477}
Day of the year, 5th / 50th / 95th percentile: ['Feb 26', 'Apr 06', 'Jun 19']

What this shows: the photos are not spread evenly. They pile up in a handful of places (the east coast, the Pacific Northwest, California), and many dots overlap, so you cannot count the places by eye. In the space-time cube (middle: x and y are kilometres on an equal-area map projection, time goes upwards) the photos form vertical columns: each place is a column, and each spring is a burst along it. In time, the photos are concentrated in a season: half of them were taken between the end of February and the end of April, and 90% between 26 February and 19 June (median: 6 April). The number of photos per year varies a lot (from 477 in 2016 to 1,438 in 2011), which already warns us that "more photos" does not simply mean "more blossoms".

To turn what you see into units you can count and compare, you need an explicit grouping. We use density-based clustering, because it finds concentrations and leaves the rest as noise.

Stage 2: A distance function for space and time (about 10 min)¶

DBSCAN needs to know when two photos are "close". For these photos, closeness has two parts: the distance in space (km) and the distance in time (days). You cannot add kilometres and days, so the lecture's recipe (slides 44–45) treats them as two elementary distances and works in three steps:

  1. choose a radius for each elementary distance: Rs for space (km) and Rt for time (days). You define these radii;
  2. turn each elementary distance into a relative distance by dividing it by its radius (1 means "exactly as far as a neighbour may be");
  3. combine the two relative distances (maximum, Euclidean or Manhattan). Two photos are neighbours if the result is at most 1.

A photo is a core photo if it has at least N neighbours (itself included).

Step 1: the elementary distance in space¶

The photos come with geographic coordinates: longitude and latitude, in degrees. Degrees are angles, not lengths. One degree of latitude is about 111 km everywhere, but one degree of longitude is only 111 km × cos(latitude), because the meridians converge towards the poles: about 85 km at 40°N and 71 km at 50°N. So there are two ways to turn the coordinates of two photos into a distance in km:

  • Flat earth: pretend that longitude and latitude are coordinates on a flat sheet (Pythagoras on the degrees) and convert degrees to km with 111 km per degree. Simple, but it makes east–west distances too long.
  • Real spatial distance: the great-circle distance, the shortest way over the globe (haversine formula, Earth radius 6371 km). This is the distance used in this practical.

(The table also contains x_km and y_km: coordinates in an equal-area map projection, in km. They are used only to find candidate neighbours quickly, see "Naming what you just saw" below. The distance that decides is always the great-circle distance.)

Two real photos, taken near New York in April 2008, and three ways of measuring the distance between them:

In [4]:
i, j = 1220, 9003                                  # two photos chosen for this example: one in Newark, one in Manhattan
a, b = df.loc[i], df.loc[j]
real = great_circle_km(a.lon, a.lat, b.lon, b.lat)
flat = flat_earth_km(a.lon, a.lat, b.lon, b.lat)
proj = np.hypot(a.x_km - b.x_km, a.y_km - b.y_km)
print(f"photo {i}: longitude {a.lon:.3f}, latitude {a.lat:.3f}, taken {a.date_taken:%Y-%m-%d}")
print(f"photo {j}: longitude {b.lon:.3f}, latitude {b.lat:.3f}, taken {b.date_taken:%Y-%m-%d}")
print(f"one degree of longitude is {111.195 * np.cos(np.radians(a.lat)):.0f} km here, one degree of latitude 111 km")
print()
print(f"distance, flat earth (degrees x 111 km)  : {flat:5.1f} km")
print(f"distance, real (great circle)             : {real:5.1f} km   <- used in this practical")
print(f"distance in the projected x_km, y_km      : {proj:5.1f} km")
print(f"time difference                           : {abs(a.t_days - b.t_days):5.2f} days")

# Is this pair special? The same comparison for random pairs of photos that are between 1 and 60 km apart:
real_d, flat_d, proj_d = compare_space_distances(df)
over = 100 * (flat_d / real_d - 1)
off = 100 * (proj_d / real_d - 1)
print()
print(f"{len(real_d):,} random pairs of photos, 1 to 60 km apart:")
print(f"flat earth compared with the real distance: {np.median(over):+.0f}% (median); for 90% of the pairs between {np.percentile(over, 5):+.0f}% and {np.percentile(over, 95):+.0f}%")
print(f"projected x_km, y_km, compared with it    : {np.median(off):+.1f}% (median); for 98% of the pairs between {np.percentile(off, 1):+.1f}% and {np.percentile(off, 99):+.1f}%")
photo 1220: longitude -74.181, latitude 40.757, taken 2008-04-13
photo 9003: longitude -73.949, latitude 40.718, taken 2008-04-18
one degree of longitude is 84 km here, one degree of latitude 111 km

distance, flat earth (degrees x 111 km)  :  26.1 km
distance, real (great circle)             :  20.0 km   <- used in this practical
distance in the projected x_km, y_km      :  19.9 km
time difference                           :  4.99 days
67,391 random pairs of photos, 1 to 60 km apart:
flat earth compared with the real distance: +17% (median); for 90% of the pairs between +0% and +34%
projected x_km, y_km, compared with it    : -0.0% (median); for 98% of the pairs between -1.2% and +1.3%

What this shows: the flat-earth distance of this pair is 26.1 km, the real distance only 20.0 km: the flat sheet stretches east–west distances (here by 31%, because one degree of longitude is 84 km, not 111 km). The comparison with many pairs shows that this is typical: flat earth is too long by 17% at the median, and by up to a third. The projected coordinates are within about 1% of the real distance, which is accurate enough to find candidate neighbours, but we let the great-circle distance decide.

It matters for the clustering, not only for the maps. With a spatial radius of 25 km, the flat-earth calculation says that these two photos are not neighbours (26.1 km is more than 25 km), while the real distance says that they are (20.0 km is less than 25 km).

Step 2: the user-defined radii and the relative distances¶

Now the radii that you define come in. Take the real spatial distance of the pair, 20.0 km, and its time difference, 5.0 days. With Rs = 25 km and Rt = 7 days the relative distances are 20.0 / 25 = 0.80 and 5.0 / 7 = 0.71: the pair is at 80% of the allowed distance in space and at 71% of the allowed distance in time. The rule for combining the two numbers then decides whether the photos are neighbours:

In [5]:
space_km, days = real, abs(a.t_days - b.t_days)    # the two elementary distances of this pair (from the cell above)
rel = np.array([space_km / RS_DEFAULT, days / RT_DEFAULT])
print(f"relative distance in space: {space_km:.1f} km / Rs = {RS_DEFAULT} km  ->  {rel[0]:.2f}")
print(f"relative distance in time : {days:.1f} days / Rt = {RT_DEFAULT} days  ->  {rel[1]:.2f}")
print(f"combined by the maximum : {rel.max():.2f}")
print(f"combined by Euclid      : {np.hypot(*rel):.2f}")
print(f"combined by Manhattan   : {rel.sum():.2f}")
print("neighbours if the combined distance is at most 1")

# The three rules draw different neighbourhoods in the plane of the relative distances. The red dot is the pair above.
t = np.linspace(0, 2 * np.pi, 200)
shapes = {"maximum": ([1, 1, -1, -1, 1], [1, -1, -1, 1, 1]), "Euclidean": (np.cos(t), np.sin(t)), "Manhattan": ([1, 0, -1, 0, 1], [0, 1, 0, -1, 0])}
fig, axes = plt.subplots(1, 3, figsize=(11, 3.8))
for ax, (name, (sx, sy)) in zip(axes, shapes.items()):
    ax.fill(sx, sy, alpha=0.25)
    ax.plot(sx, sy)
    ax.scatter([rel[0]], [rel[1]], c="crimson", zorder=3)
    ax.set_xlim(-1.6, 1.6); ax.set_ylim(-1.6, 1.6); ax.set_aspect("equal")
    ax.set_title(name); ax.set_xlabel("relative distance in space"); ax.set_ylabel("relative distance in time")
plt.tight_layout()
plt.show()
relative distance in space: 20.0 km / Rs = 25 km  ->  0.80
relative distance in time : 5.0 days / Rt = 7 days  ->  0.71
combined by the maximum : 0.80
combined by Euclid      : 1.07
combined by Manhattan   : 1.51
neighbours if the combined distance is at most 1
No description has been provided for this image
In [6]:
display(make_notice_checkpoint(
    "Which combination rules call these two photos neighbours (Rs = 25 km, Rt = 7 days)?",
    ["All three rules", "Only the maximum", "Maximum and Euclid", "None of them"],
    "<b>Only the maximum.</b> The relative distances are 0.80 (space) and 0.71 (time). The maximum is 0.80, which is at most 1. "
    "The Euclidean combination is 1.07 and the Manhattan combination is 1.51, both above 1. "
    "The rule defines the <i>shape</i> of the neighbourhood: in the plane of the relative distances a square (maximum), a circle (Euclid) or a diamond (Manhattan); in the space-time cube a cylinder, an ellipsoid or a double cone. "
    "The maximum is the most generous rule and keeps the radii easy to explain: \u201cwithin 25 km <i>and</i> within 7 days\u201d."))

Naming what you just saw: from your radii to clusters. DBSCAN itself knows only one distance function and one radius (eps). So st_cluster() prepares both: (1) for every photo it finds the photos that could be neighbours, using the fast projected coordinates (a box of Rs and Rt around the photo); (2) for these candidate pairs it computes the great-circle distance and the time difference, divides them by Rs and Rt, and combines the two relative distances with the rule you chose; (3) it keeps the pairs whose combined relative distance is at most 1 and hands this neighbour graph to DBSCAN with eps = 1. DBSCAN then does what the lecture describes: a photo with at least N neighbours (itself included) is a core photo, and clusters grow from core photos. A clustering of all 9,703 photos takes a fraction of a second, which makes it practical to run it many times, as the lecture demands. (A distance function written in Python and called for every pair of photos, as in earlier versions of this practical, is much slower.)

Stage 3: A first run (about 5 min)¶

Use the settings of the lecture's example: Rs = 25 km, Rt = 7 days, N = 7.

Before running the next cell, predict: how many clusters, and what share of the photos will be noise?

In [7]:
labels_base = st_cluster(df, RS_DEFAULT, RT_DEFAULT, N_DEFAULT)
q = quality_indicators(df, labels_base)
K, noise = q["K"], q["noise_pct"]
print(f"Rs = {RS_DEFAULT} km, Rt = {RT_DEFAULT} days, N = {N_DEFAULT}:  {K} clusters;  {noise:.1f} % of the photos are noise")
print(f"quality of the clusters (clustered photos only): silhouette {q['silhouette']:.2f},  SSE {q['SSE']:,.0f},  explained variance {q['explained_pct']:.3f} %")

colors_base = cluster_colors(df, labels_base)
plot_map_and_cubes(df, labels_base, colors_base, f"First run: {K} space-time clusters (grey = noise)")
plt.show()

summary = cluster_summary(df, labels_base).sort_values("photos", ascending=False)
summary["place (nearest listed city)"] = [name_place(a, b) for a, b in zip(summary.lat, summary.lon)]
display(summary.head(8)[["photos", "lat", "lon", "first", "last", "place (nearest listed city)"]].round(2))
print(f"Cluster sizes: from {summary.photos.min()} to {summary.photos.max()} photos")
Rs = 25 km, Rt = 7 days, N = 7:  106 clusters;  30.2 % of the photos are noise
quality of the clusters (clustered photos only): silhouette 0.83,  SSE 9,277,  explained variance 99.994 %
No description has been provided for this image
photos lat lon first last place (nearest listed city)
cluster
1 496 38.89 -77.04 2011-03-08 2011-05-03 Washington DC
11 420 38.89 -77.04 2012-02-27 2012-04-16 Washington DC
8 398 38.89 -77.04 2013-03-19 2013-04-26 Washington DC
7 393 38.89 -77.04 2010-03-16 2010-04-16 Washington DC
10 354 38.89 -77.04 2009-03-14 2009-05-02 Washington DC
48 290 38.91 -77.04 2008-03-10 2008-04-27 Washington DC
6 253 38.89 -77.04 2014-03-17 2014-04-29 Washington DC
14 214 38.89 -77.04 2007-03-25 2007-04-28 Washington DC
Cluster sizes: from 6 to 496 photos

What this shows: 106 clusters and 30.2% noise. The clusters sit in the cities. Look at the table: the eight largest clusters (214 to 496 photos each) are all in Washington DC, and each lasts only a few weeks, in a different year from 2007 to 2014 (see first and last). A cluster here is a concentration of photos in space and time: in the space-time cubes, one burst on the column of a place, that is, one place in one spring. The cube in the middle also shows the noise (grey): the loose photos that belong to no concentration; the cube on the right shows only the clusters. That is what we asked for, but it is probably not yet what we want to know. Keep this in mind for Stage 6.

Quality indicators. Besides the number of clusters K and the noise share, the cell printed three indicators for the clustered photos (the noise is left out). All three are measured with one fixed ruler (25 km and 7 days), so that runs with different radii are measured in the same way. The silhouette (0.83) says that the photos are much closer to their own cluster than to the nearest other one. The SSE (9,277) is the sum of the squared distances of the photos to the centre of their cluster: the smaller, the more compact the clusters. The explained variance (99.994%) is the share of the total spread of the clustered photos that the grouping explains, 100% × (1 − SSE / total sum of squares). These are the guides that the lecture used for k-means (slides 55–57). Notice that the explained variance is almost 100%: the clusters are tiny compared with a continent and ten years, so this indicator will hardly tell runs apart here.

What do the colours show? A colour identifies one cluster: the same cluster has the same colour in the map and in the cubes; grey dots are noise. The colours are not arbitrary. Each cluster is described by its average position (x, y), its average time and its average position in the yearly cycle (day of the year). The clusters are placed on a 2D plane so that similar clusters are close to each other (multidimensional scaling, MDS), and the plane is coloured with four corner colours (slides 69–72). So clusters that are alike in place, date and season get similar colours, and clusters that differ a lot get different colours. (The colours are computed anew for every run, so do not compare colours between runs here. Part 2 shows how to keep colours stable across runs.)

Stage 4: One run is never sufficient: parameter sensitivity (about 12 min) (interactive)¶

The lecture asked "Which clustering is the best?" and answered: there may be no best one. The tool below lets you try for yourself. Spend about 4 minutes: change one parameter at a time, press Cluster, and watch how the number of clusters, the noise and the map change. Also try the three combination rules.

In [8]:
def explore_once(Rs, Rt, N, combine):
    lab = st_cluster(df, Rs, Rt, N, combine)
    q = quality_indicators(df, lab)
    print(f"Rs = {Rs:g} km, Rt = {Rt:g} days, N = {N}, combine = {combine}:  {q['K']} clusters;  {q['noise_pct']:.1f} % noise;  "
          f"silhouette {q['silhouette']:.2f},  SSE {q['SSE']:,.0f},  explained variance {q['explained_pct']:.3f} %")
    plot_map_and_cubes(df, lab, cluster_colors(df, lab), f"{q['K']} clusters, {q['noise_pct']:.0f} % noise", s_cluster=6)
    plt.show()


layout = widgets.Layout(width="560px")
w_rs = widgets.FloatSlider(value=RS_DEFAULT, min=5, max=60, step=1, description="Rs (km)", continuous_update=False, layout=layout)
w_rt = widgets.FloatSlider(value=RT_DEFAULT, min=1, max=30, step=1, description="Rt (days)", continuous_update=False, layout=layout)
w_n = widgets.IntSlider(value=N_DEFAULT, min=2, max=20, step=1, description="N", continuous_update=False, layout=layout)
w_comb = widgets.RadioButtons(options=[("maximum", "max"), ("Euclidean", "euclid"), ("Manhattan", "manhattan")], value="max", description="combine")
btn_cluster = widgets.Button(description="Cluster", button_style="primary")
out_cluster = widgets.Output()


def on_cluster(b):
    with out_cluster:
        clear_output(wait=True)
        explore_once(w_rs.value, w_rt.value, w_n.value, w_comb.value)


btn_cluster.on_click(on_cluster)
display(widgets.VBox([w_rs, w_rt, w_n, w_comb, btn_cluster, out_cluster]))

Playing with a tool gives an impression. To get a systematic picture, repeat the clustering for a whole range of values of each parameter in turn, keeping the other two at their defaults. That is a sweep.

Before running the next cell, make a prediction.

In [9]:
display(make_notice_checkpoint(
    "Which parameter changes the result most when you vary it over the ranges below (Rs 10\u201350 km, Rt 1\u201314 days, N 3\u201312)?",
    ["Rs, the spatial radius", "Rt, the temporal radius", "N, the minimum number of neighbours", "All three about equally"],
    "<b>It depends on what you measure, and the sweep below shows it.</b> "
    "The <b>number of clusters</b> changes most with <b>N</b> (from 265 clusters at N = 3 to 85 at N = 12). "
    "<b>Rt</b> changes the <b>noise share</b> most (52% at 1 day, 25% at 14 days). "
    "<b>Rs</b> hardly changes the number of clusters (between 105 and 113 over a fivefold range of the radius)."))
In [10]:
sweeps = {"Rs": sweep_st(df, "Rs", RS_SWEEP), "Rt": sweep_st(df, "Rt", RT_SWEEP), "N": sweep_st(df, "N", N_SWEEP)}
defaults = {"Rs": RS_DEFAULT, "Rt": RT_DEFAULT, "N": N_DEFAULT}
xlabel = {"Rs": "Rs: spatial radius (km)", "Rt": "Rt: temporal radius (days)", "N": "N: minimum number of neighbours"}

fig, axes = plt.subplots(3, 3, figsize=(16, 11), sharex="col")
for j, (p, s) in enumerate(sweeps.items()):
    ax = axes[0, j]
    ax.plot(s[p], s.K, "o-", color="#1f77b4")
    ax.set_ylabel("clusters K", color="#1f77b4")
    ax_noise = ax.twinx()
    ax_noise.plot(s[p], s.noise_pct, "s--", color="#ff7f0e")
    ax_noise.set_ylabel("noise (%)", color="#ff7f0e")
    ax_noise.grid(False)
    axes[1, j].plot(s[p], s.silhouette, "o-", color="#2ca02c")
    axes[1, j].set_ylabel("silhouette")
    axes[2, j].plot(s[p], s.SSE, "o-", color="#9467bd")
    axes[2, j].set_ylabel("SSE", color="#9467bd")
    ax_var = axes[2, j].twinx()
    ax_var.plot(s[p], s.explained_pct, "s--", color="#8c564b")
    ax_var.set_ylabel("explained variance (%)", color="#8c564b")
    ax_var.ticklabel_format(useOffset=False, style="plain")
    ax_var.grid(False)
    axes[2, j].set_xlabel(xlabel[p])
    for a in (ax, axes[1, j], axes[2, j]):
        a.axvline(defaults[p], color="grey", ls=":")
plt.suptitle("Sweeps: vary one parameter, keep the others at their defaults (dotted line = the first run)", y=1.0)
plt.tight_layout()
plt.show()

print("Does the combination rule matter? (Rs = 25 km, Rt = 7 days, N = 7)")
rows = []
for rule in ("max", "euclid", "manhattan"):
    k_, n_ = run_overview(st_cluster(df, RS_DEFAULT, RT_DEFAULT, N_DEFAULT, rule))
    rows.append({"combine": rule, "clusters": k_, "noise %": round(n_, 1)})
display(pd.DataFrame(rows))
No description has been provided for this image
Does the combination rule matter? (Rs = 25 km, Rt = 7 days, N = 7)
combine clusters noise %
0 max 106 30.2
1 euclid 105 31.2
2 manhattan 102 33.1

What this shows:

  • Rs (10 to 50 km): the number of clusters stays between 105 and 113 (look at the vertical axis: the line looks lively, but its range is tiny), while the noise share falls from 35% to 26%. The clusters are separated by distances much larger than 50 km, so a larger radius only attaches a few more border photos.
  • Rt (1 to 14 days): the noise share falls from 52% to 25%. With a short Rt a concentration is cut into pieces (the number of clusters peaks at 140 for Rt = 2 days), with a longer Rt the pieces join again.
  • N (3 to 12): the number of clusters falls from 265 to 85, and the noise share rises from 22% to 34%. Requiring more neighbours removes small clusters.
  • The combination rule changes the result a little (106, 105 and 102 clusters; 30.2%, 31.2% and 33.1% noise): the more restrictive the neighbourhood, the more photos become noise.
  • Be careful with the silhouette. It rises with N, from 0.67 to 0.85, while the noise share rises too. That does not mean the clustering gets better: it is computed only for the clustered photos, so calling loose photos noise improves it (slide 51: metrics of cluster "quality" can be questionable). With Rt it is lowest (0.70) when the concentrations are cut into pieces, highest (0.84) at 6 days and then declines slowly to 0.80; with Rs it hardly moves (between 0.78 and 0.84).
  • SSE and explained variance (third row) are mirror images of each other. The SSE grows with Rs and Rt, because looser neighbourhoods make bigger clusters and attach more photos, and it falls with N. It is lowest when most photos are noise (Rt = 1 day), so here a low SSE is not "better": it reflects how many photos remain in the clusters. The explained variance stays between 99.989% and 99.999% in every run (look at the right-hand axis: the whole range is 0.01 percentage points). This indicator, designed for partition-based methods such as k-means, cannot guide the choice of the radii here.

There is no "ideal" setting here, only a range of reasonable settings and a feeling for what each parameter does. The lecture asked for exactly that: understand the effects of the parameters, and find a suitable range rather than an ideal value.

Stage 5 (optional): Same number of clusters, same groups? (about 8 min)¶

The number of clusters stayed almost constant when Rs changed. Does that mean the same clusters were found each time? To check, compare the groups themselves. For every cluster of the first run we look for the cluster of another run that overlaps it most, measured by the Jaccard index (shared photos divided by all photos in either cluster). A cluster recurs in a run if its best Jaccard index is at least 0.5.

Before running the next cell, predict: out of the 106 clusters, how many will recur in all nine runs of the Rs sweep?

In [11]:
runs_rs = [st_cluster(df, rs, RT_DEFAULT, N_DEFAULT) for rs in RS_SWEEP]
recurrence = np.sum([best_jaccard(labels_base, r) >= 0.5 for r in runs_rs], axis=0)      # in how many of the 9 runs does each cluster recur?
everywhere = int((recurrence == len(RS_SWEEP)).sum())
print(f"{everywhere} of {len(recurrence)} clusters recur in all {len(RS_SWEEP)} runs of the Rs sweep")

fig = plt.figure(figsize=(20, 11.5))
gs = fig.add_gridspec(2, 2, width_ratios=[1, 1.4])
ax1, ax2 = fig.add_subplot(gs[0, 0]), fig.add_subplot(gs[0, 1])
vals, counts = np.unique(recurrence, return_counts=True)
ax1.bar(vals, counts, color="#4c78a8")
ax1.set_xlabel("number of runs (of 9) in which the cluster recurs")
ax1.set_ylabel("number of clusters")
ax1.set_title("Recurrence of the clusters of the first run")
fragile = {c for c, r in enumerate(recurrence) if r < len(RS_SWEEP)}
plot_map(df, labels_base, colors_base, ax=ax2, highlight=fragile, title="Clusters that do not recur in every run (coloured); all others grey")
plot_cube(df, labels_base, colors_base, ax=fig.add_subplot(gs[1, 0], projection="3d"), highlight=fragile, title="Space-time cube, with noise (grey)", s_cluster=6)
plot_cube(df, labels_base, colors_base, ax=fig.add_subplot(gs[1, 1], projection="3d"), highlight=fragile, show_noise=False, title="Space-time cube, without noise", s_cluster=6)
plt.tight_layout()
plt.show()

sizes = np.bincount(labels_base[labels_base >= 0])
print(f"median size of the clusters that recur everywhere: {np.median([sizes[c] for c in range(len(sizes)) if c not in fragile]):.0f} photos; of the others: {np.median([sizes[c] for c in fragile]):.0f} photos")
for n_ in (3, 12):
    kept = int((best_jaccard(labels_base, st_cluster(df, RS_DEFAULT, RT_DEFAULT, n_)) >= 0.5).sum())
    print(f"with N = {n_}: {kept} of the {len(sizes)} clusters of the first run still have a counterpart")
94 of 106 clusters recur in all 9 runs of the Rs sweep
No description has been provided for this image
median size of the clusters that recur everywhere: 39 photos; of the others: 8 photos
with N = 3: 100 of the 106 clusters of the first run still have a counterpart
with N = 12: 82 of the 106 clusters of the first run still have a counterpart

What this shows: 94 of the 106 clusters recur in all nine runs, so most of the structure is stable with respect to Rs, and 12 clusters do not: those are candidates for artefacts of a particular setting. The clusters that do not recur are small (median size 8 photos, against 39 for the others). Changing N is more drastic: with N = 12 only 82 of the first run's clusters keep a counterpart, with N = 3 it is 100. The number of clusters alone hides what happens to the groups. A group that survives many parameter settings is much better evidence of real structure than any single run (this is the idea of persistent groups in the SmartIterator approach).

Stage 6: Assess, then revise the plan (about 12 min)¶

A clustering workflow is planned before running anything, but it may change after the first results (slides 12–17). So: assess before moving on. Look at the first run around Washington DC, where the photos are densest. The cell shows four views of the same photos: the map, a timeline of the clusters, and two space-time cubes of the window (with the noise, and without it).

In [12]:
dc_extent = (-78.6, -75.4, 37.9, 40.1)       # lon_min, lon_max, lat_min, lat_max
in_window = df.lon.between(dc_extent[0], dc_extent[1]) & df.lat.between(dc_extent[2], dc_extent[3])
n_here = len(set(labels_base[in_window.values]) - {-1})
print(f"{n_here} different clusters have photos in this window around Washington DC")

fig = plt.figure(figsize=(18, 12.5))
gs = fig.add_gridspec(2, 2)
ax1, ax2 = fig.add_subplot(gs[0, 0]), fig.add_subplot(gs[0, 1])
plot_map(df, labels_base, colors_base, ax=ax1, extent=dc_extent, s_cluster=16, s_noise=6, title="Round 1: clusters around Washington DC")
local = cluster_summary(df, labels_base)
local = local[local.lon.between(dc_extent[0], dc_extent[1]) & local.lat.between(dc_extent[2], dc_extent[3])].sort_values("first")
for k, (c, row) in enumerate(local.iterrows()):
    ax2.plot([pd.to_datetime(row["first"]), pd.to_datetime(row["last"])], [k, k], lw=7, color=colors_base[c], solid_capstyle="round", alpha=0.9)
ax2.set_yticks(range(len(local)))
ax2.set_yticklabels([f"{row['first'][:4]}: {row.photos} photos" for _, row in local.iterrows()], fontsize=8)
ax2.invert_yaxis()
ax2.set_title("The same clusters in time: from the first to the last photo of each cluster")
plot_cube(df, labels_base, colors_base, ax=fig.add_subplot(gs[1, 0], projection="3d"), extent=dc_extent, s_cluster=14, s_noise=6, title="Space-time cube of the window, with noise (grey)")
plot_cube(df, labels_base, colors_base, ax=fig.add_subplot(gs[1, 1], projection="3d"), extent=dc_extent, s_cluster=14, show_noise=False, title="Space-time cube of the window, without noise")
plt.tight_layout()
plt.show()
13 different clusters have photos in this window around Washington DC
No description has been provided for this image

Assess: 13 clusters have photos in this window, and ten of them are large: one for each spring from 2007 to 2016, all at the same place (the small ones have only a few photos in the window). The timeline (top right) shows the 12 clusters whose centre lies in the window (the ten large ones and two tiny ones), each from its first to its last photo: they follow each other and never overlap. In the cubes the same clusters are ten bursts stacked on a single column. They are the same place at different times. For the question "where do people photograph cherry blossoms?", we want these united into one place.

What do the colours show? A colour identifies one cluster, and it is the same in all four views (map, timeline, both cubes); grey is noise. The colours come from the average position, the average time and the average position in the yearly cycle of the clusters (see the note after Stage 3), so similar clusters get similar colours. The ten large clusters are in the same place and in the same season and differ mainly in the year, so their colours change gradually with the year: here from violet (2007) through blue to light blue (2016).

Plan update (as in the lecture's congestion example): add a second round. Take the photos that belong to the clusters of round 1 (the noise of round 1 is left out), and cluster them again by space only, ignoring the time (distance function without the time term), with the same Rs and N. This unites the clusters that overlap in space.

Before running the next cell, predict: into how many places will the 106 clusters merge?

In [13]:
members = np.where(labels_base >= 0)[0]                      # the photos of round-1 clusters (noise left out)
labels_place = st_cluster(df, RS_DEFAULT, RT_DEFAULT, N_DEFAULT, use_time=False, subset=members)
K2, _ = run_overview(labels_place)
print(f"Round 2 (space only) on the {len(members):,} photos of round 1: {K2} places; {int((labels_place[members] >= 0).sum()):,} of these photos belong to a place")

places = cluster_summary(df, labels_place)
places["place (nearest listed city)"] = [name_place(a, b) for a, b in zip(places.lat, places.lon)]
display(places.sort_values("photos", ascending=False)[["photos", "lat", "lon", "place (nearest listed city)"]].round(2))

colors_place = cluster_colors(df, labels_place)
rows = [{"Rs (km)": rs, "places": run_overview(st_cluster(df, rs, RT_DEFAULT, N_DEFAULT, use_time=False, subset=members))[0]} for rs in RS_SWEEP]
fig = plt.figure(figsize=(20, 12))
gs = fig.add_gridspec(2, 2, width_ratios=[1.6, 1])
plot_map(df, labels_place, colors_place, ax=fig.add_subplot(gs[0, 0]), title=f"Round 2: {K2} places (grey = photos that are not part of any place)", s_cluster=10)
ax = fig.add_subplot(gs[0, 1])
ax.plot([r["Rs (km)"] for r in rows], [r["places"] for r in rows], "o-")
ax.set_xlabel("Rs (km)")
ax.set_ylabel("number of places")
ax.set_title("Round 2 is also a parameter choice")
plot_cube(df, labels_place, colors_place, ax=fig.add_subplot(gs[1, 0], projection="3d"), title="Space-time cube, with noise (grey): each place is a vertical column", s_cluster=8)
plot_cube(df, labels_place, colors_place, ax=fig.add_subplot(gs[1, 1], projection="3d"), show_noise=False, title="Space-time cube, without noise", s_cluster=8)
plt.tight_layout()
plt.show()
Round 2 (space only) on the 6,770 photos of round 1: 14 places; 6,770 of these photos belong to a place
photos lat lon place (nearest listed city)
cluster
1 3201 38.89 -77.04 Washington DC
4 878 40.74 -73.98 New York
2 743 49.26 -123.11 Vancouver
5 541 37.78 -122.42 San Francisco
3 461 47.65 -122.30 Seattle
0 348 43.65 -79.46 Toronto
6 296 45.52 -122.68 Portland OR
7 172 39.97 -75.20 Philadelphia
9 46 42.34 -71.10 Boston
8 38 34.12 -118.32 Los Angeles
12 24 32.85 -83.65 Macon GA
13 8 41.92 -83.44 Toledo OH
11 7 33.71 -118.03 Huntington Beach CA
10 7 44.94 -123.03 Salem OR
No description has been provided for this image

What this shows: the 106 space-time clusters unite into 14 places, and all 6,770 photos of round 1 belong to a place (this is expected: they were dense enough in space and time, so they are dense enough in space alone). In the cubes each place is now a column with one burst per spring. Washington DC alone has 3,201 photos, followed by New York (878), Vancouver (743), San Francisco (541), Seattle (461), Toronto (348), Portland (296) and Philadelphia (172). The remaining six places are small (7 to 46 photos).

Round 2 is itself a parameter choice: between 15 and 30 km the result is 14 places, at 10 km it is 16 (a place splits), and with larger radii neighbouring places merge (13 at 35 km, 12 from 40 km on). The two rounds have different purposes, as in the lecture: round 1 detects candidates, round 2 unites the repeats of the same place. The workflow changed because of the assessment.

Stage 7: When is the season, in each place and each year? (about 8 min)¶

Now that the places are explicit units, we can ask the question the lecture's example ended with: when did the photo-taking happen in each place, and how does this differ between the years? For each place and year we take the median day of the year of its photos (cells with fewer than 15 photos are left empty).

In [14]:
places_big = place_table(df, labels_place)
d = df.assign(place=labels_place)
d = d[d.place.isin(places_big.index)]
cell = d.groupby(["place", "year"]).day_of_year.agg(["median", "size"]).reset_index()
cell = cell[cell["size"] >= MIN_PHOTOS_PER_CELL]
med = cell.pivot(index="place", columns="year", values="median").reindex(places_big.index)
med.index = [f"{places_big.name[p]} ({places_big.photos[p]:,})" for p in med.index]
annot = med.apply(lambda col: col.map(lambda v: "" if pd.isna(v) else doy_label(v)))

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(17, 5.4), gridspec_kw={"width_ratios": [1.6, 1]})
sns.heatmap(med, annot=annot, fmt="", cmap="coolwarm", linewidths=0.5, cbar_kws={"label": "median day of the year"}, ax=ax1)
ax1.set_title("Median date of photo-taking per place and year (empty: fewer than 15 photos)")
ax1.set_xlabel("")
order = list(places_big.sort_values("median_day").index)
for k, p in enumerate(order):
    ax2.plot([places_big.p10_day[p], places_big.p90_day[p]], [k, k], lw=7, alpha=0.55, solid_capstyle="round")
    ax2.plot(places_big.median_day[p], k, "k|", ms=15, mew=2)
ax2.set_yticks(range(len(order)))
ax2.set_yticklabels([places_big.name[p] for p in order])
ax2.set_xticks([32, 60, 91, 121, 152])
ax2.set_xticklabels(["Feb 1", "Mar 1", "Apr 1", "May 1", "Jun 1"])
ax2.set_title("Season of each place: 10th to 90th percentile, median tick")
plt.tight_layout()
plt.show()

summary_places = places_big.assign(median=[doy_label(v) for v in places_big.median_day], window=[f"{doy_label(a)} \u2013 {doy_label(b)}" for a, b in zip(places_big.p10_day, places_big.p90_day)])
display(summary_places[["name", "photos", "median", "window"]].sort_values("median", key=lambda s: pd.to_datetime(s, format="%b %d")))
No description has been provided for this image
name photos median window
place
6 Portland OR 296 Mar 23 Mar 07 – Apr 05
3 Seattle 461 Mar 30 Mar 12 – Apr 14
1 Washington DC 3201 Apr 03 Mar 23 – Apr 12
2 Vancouver 743 Apr 07 Mar 11 – Apr 26
7 Philadelphia 172 Apr 13 Mar 27 – Apr 19
5 San Francisco 541 Apr 14 Feb 15 – Apr 22
4 New York 878 Apr 21 Apr 01 – May 04
0 Toronto 348 May 05 Apr 14 – May 13
In [15]:
display(make_notice_checkpoint(
    "Was there a year that was early in ALL places?",
    ["Yes: one year was early everywhere", "No: the early years differ between the East and the Pacific Northwest", "The figure does not allow a conclusion"],
    "<b>No.</b> In Washington DC, New York, Philadelphia and Toronto the earliest year is <b>2012</b> (for example Washington DC: median day 83, about 24 March; the next earliest year there is 2016 with day 85, and in 2007\u20132015 the other years range from 91 to 101). "
    "In Seattle, Portland and Vancouver the earliest year is <b>2010</b> (Vancouver 70.5, Seattle 70, Portland 66), while in San Francisco it is 2007. A single \u201cearly year\u201d for the whole continent does not exist: the weather that "
    "advances the blossoms differs between the regions. This is knowledge about the <i>data</i> that no single clustering run gives you."))

What this shows: the places are ordered by their median date. Portland is earliest (23 March), then Seattle (30 March), Washington DC (3 April), Vancouver (7 April), Philadelphia (13 April), San Francisco (14 April), New York (21 April) and Toronto (5 May): a rough west-to-east and south-to-north progression, but not a clean one. The windows also differ: Washington DC has the narrowest (about 20 days) and San Francisco the widest (from mid-February to late April), which suggests several flowering periods (a hypothesis to check, not a result).

A caution (lecture 3 again): these are dates when people took photos, not when the trees bloomed, and the number of photos reflects where people live, travel and use the photo service. Photos are a proxy.

Stage 8: Wrap-up of Part 1 (about 3 min)¶

This stage followed the workflow of the lecture: plan, run, assess, revise. You ran a clustering several times, compared the runs (Stage 4), checked whether the groups persist (Stage 5), noticed from the result that the plan needed a second round (Stage 6), and ended with knowledge about where and when (Stage 7).

In a new markdown cell, write 3–4 sentences: which values of Rs, Rt and N would you use for round 1, and why? Base your answer on evidence from the stages above, not only on a single number. What would you check next?

Try the same in the demonstrator. Open Cherry blossom photos at https://geoanalytics.net/and/SmartIterator/demo . The sweeps of Stage 4 are the first three precomputed sweeps; the round-2 sweep is the fourth. (The demonstrator's sweeps treat x and y as two separate features, so with the maximum and Manhattan rules its neighbourhoods are boxes in space, not circles, and its numbers differ slightly from this notebook, for example 108 instead of 106 clusters in the first run. With the Euclidean rule the results are identical.) Open Explore… and try: (a) another combination rule; (b) Items: members of the clusters of the active iteration with time switched off, which is round 2 of this notebook; (c) the comparison of two places in the transition view.


Part 2 — K-means on weekly counts (rest of the session or homework, about 40 minutes)¶

Part 2 uses partition-based clustering (k-means) on a very different kind of entity: weeks, described by the number of cherry-blossom photos taken in five regions (slides 26, 47–60). The questions are the same: which settings, and how do we know?

In [16]:
# =============================================================================
# REUSABLE FUNCTIONS (Part 2 and Part 3)
# =============================================================================
from matplotlib.colors import to_rgb


def relabel_by_size(labels, tie=None):
    """Renumber the groups so that 0 is the largest, 1 the next, ... (ties: larger mean of `tie` first). Makes group numbers comparable between runs."""
    labels = np.asarray(labels)
    sizes = np.bincount(labels)
    mean_tie = [float(np.mean(tie[labels == g])) if tie is not None else 0.0 for g in range(len(sizes))]
    order = sorted(range(len(sizes)), key=lambda g: (-sizes[g], -mean_tie[g]))
    rank = {g: i for i, g in enumerate(order)}
    return np.array([rank[g] for g in labels])


def kmeans_labels(X, k, seed=SEED_DEFAULT, n_init=10, tie=None):
    """k-means; returns (labels renumbered by size, SSE)."""
    km = KMeans(k, random_state=seed, n_init=n_init).fit(X)
    return relabel_by_size(km.labels_, tie), km.inertia_


def kmeans_sweep(X, ks=K_SWEEP, seed=SEED_DEFAULT, n_init=10):
    """Run k-means for every K and collect SSE, the percentage of variance explained and the silhouette."""
    total = ((X - X.mean(axis=0)) ** 2).sum()
    rows = []
    for k in ks:
        km = KMeans(k, random_state=seed, n_init=n_init).fit(X)
        rows.append({"K": k, "SSE": km.inertia_, "variance explained (%)": 100 * (1 - km.inertia_ / total), "silhouette": silhouette_score(X, km.labels_)})
    return pd.DataFrame(rows)


def shared_group_colors(weeks, runs):
    """Colours that stay the same across runs (the idea of the SmartIterator display).
    The mean profiles (photos per week in the five regions) of the groups of ALL runs are placed together in ONE 2D map (MDS) and coloured by
    position. A group that persists from K to K + 1 has almost the same profile, so it lands at almost the same place and keeps its colour.
    runs: {K: labels}.  Returns {(K, group): '#rrggbb'}."""
    keys, rows = [], []
    for K, lab in runs.items():
        profile = weeks[REGIONS].groupby(lab).mean()
        for g in profile.index:
            keys.append((K, g))
            rows.append(profile.loc[g].values)
    xy = MDS(n_components=2, random_state=9).fit_transform(MinMaxScaler().fit_transform(np.array(rows)))
    lo, hi = xy.min(axis=0), xy.max(axis=0)
    return {k: four_corner_color(x, y, lo[0], hi[0], lo[1], hi[1]) for k, (x, y) in zip(keys, xy)}


def tint_labels(tick_labels, colour_list):
    """Give tick labels the colour of their group (white or black text, whichever is readable)."""
    for t, c in zip(tick_labels, colour_list):
        r, g, b = to_rgb(c)
        t.set_bbox(dict(facecolor=c, edgecolor="none", boxstyle="round,pad=0.25"))
        t.set_color("white" if 0.299 * r + 0.587 * g + 0.114 * b < 0.5 else "black")


def plot_busy_weeks_by_run(runs, colors, ax=None):
    """One bar per K; one coloured segment per group (group 0, the large quiet group, is left out). Same colour = same group."""
    ax = ax or plt.subplots(figsize=(12, 4.4))[1]
    for K, lab in runs.items():
        sizes = np.bincount(lab)
        bottom = 0
        for g in range(1, K):
            ax.bar(K, sizes[g], bottom=bottom, color=colors[(K, g)], edgecolor="white", linewidth=0.5, width=0.82)
            bottom += sizes[g]
    ax.set_xticks(list(runs))
    ax.set_xlabel("K")
    ax.set_ylabel("weeks in the groups other than group 0")
    ax.set_title("All runs: each bar is one K, each coloured segment one group (same colour = similar group)")
    return ax


def plot_calendar(weeks, labels, colors, ax=None, title=""):
    """One square per week: week of the year across, years down, painted in the colour of the week's group."""
    ax = ax or plt.subplots(figsize=(14, 3.8))[1]
    years = sorted(weeks.year.unique())
    grid = np.ones((len(years), 53, 3))
    for yr, wk, lab in zip(weeks.year, weeks.week, labels):
        grid[years.index(yr), int(wk) - 1] = to_rgb(colors[lab])
    ax.imshow(grid, aspect="auto", interpolation="nearest")
    ax.set_yticks(range(len(years)))
    ax.set_yticklabels(years)
    ax.set_xticks(range(0, 53, 4))
    ax.set_xticklabels(range(1, 54, 4))
    ax.set_xlabel("week of the year")
    ax.grid(False)
    ax.set_title(title)
    return ax


def plot_region_boxes(weeks, labels, colors):
    """For every region: the distribution of the weekly counts in every group (box = quartiles, whiskers as usual)."""
    k = int(labels.max()) + 1
    fig, axes = plt.subplots(1, len(REGIONS), figsize=(18, 4.2))
    for ax, region in zip(axes, REGIONS):
        sns.boxplot(x=labels, y=weeks[region], order=list(range(k)), palette=[colors[g] for g in range(k)], fliersize=2, linewidth=1, ax=ax)
        ax.set_title(f"{region} ({REGION_NAMES[region]})")
        ax.set_xlabel("group")
        ax.set_ylabel("photos per week" if region == REGIONS[0] else "")
    plt.tight_layout()
    return fig


def make_audit_tool(categories, title="Which patterns from the manual do you think are present in the passage above?"):
    """Checkboxes for the audit categories, a button that reveals which ones are present and why."""
    boxes = {name: widgets.Checkbox(value=False, description=name, indent=False, layout=widgets.Layout(width="560px")) for name in categories}
    button = widgets.Button(description="Reveal analysis", button_style="primary")
    out = widgets.Output()

    def reveal(b):
        with out:
            clear_output(wait=True)
            for name, (present, why) in categories.items():
                mark = "\u2705 present" if present else "\u2796 not the main issue here"
                diff = "" if boxes[name].value == present else "   \u2190 you picked differently"
                print(f"{mark}  {name}{diff}\n      {why}\n")

    button.on_click(reveal)
    return widgets.VBox([widgets.HTML(f"<b>{title}</b>"), widgets.VBox(list(boxes.values())), button, out])

Stage 8: Look at the data (about 4 min)¶

Each row is one week. The five columns are the numbers of photos taken in the five regions of North America: NW north-west, SW south-west, NE north-east, SE south-east and GL the Great Lakes region.

Before running the next cell, predict: which region has the most photos? Are the counts evenly distributed over the weeks, or are there many quiet weeks and a few busy ones?

In [17]:
weeks = pd.read_csv(WEEKS_CSV, parse_dates=["date"], dayfirst=True).rename(columns={"week of year": "week"})
print(f"{len(weeks)} weeks, {weeks.date.min():%Y-%m-%d} to {weeks.date.max():%Y-%m-%d}")
display(weeks.head(3))
print("regions: " + ", ".join(f"{r} = {REGION_NAMES[r]}" for r in REGIONS))
print("mean photos per week:", weeks[REGIONS].mean().round(1).to_dict())
print("maximum in one week :", weeks[REGIONS].max().to_dict())
print(f"weeks without any photo: {int((weeks[REGIONS].sum(axis=1) == 0).sum())} of {len(weeks)}")

fig, axes = plt.subplots(len(REGIONS), 1, figsize=(15, 8), sharex=True)
for ax, r in zip(axes, REGIONS):
    ax.fill_between(weeks.date, weeks[r], color="#4c78a8", step="mid")
    ax.set_ylabel(f"{r}\n({REGION_NAMES[r]})", fontsize=9)
plt.suptitle("Photos per week in each region", y=0.995)
plt.tight_layout()
plt.show()
521 weeks, 2007-01-01 to 2016-12-19
date year week NW SW NE SE GL
0 2007-01-01 2007 1 0 0 1 1 0
1 2007-01-08 2007 2 0 0 1 1 0
2 2007-01-15 2007 3 0 0 0 0 0
regions: NW = north-west, SW = south-west, NE = north-east, SE = south-east, GL = Great Lakes
mean photos per week: {'NW': 3.8, 'SW': 2.2, 'NE': 9.9, 'SE': 0.5, 'GL': 1.4}
maximum in one week : {'NW': 87, 'SW': 39, 'NE': 298, 'SE': 18, 'GL': 51}
weeks without any photo: 92 of 521
No description has been provided for this image

What this shows: NE dominates: on average 9.9 photos per week against 0.5 in SE, and a maximum of 298 photos in one week (the maximum in SW is 39). 92 of the 521 weeks have no photo at all. The counts are mostly small, with one burst every year in spring. Remember this when you choose how to scale the counts: with raw counts, NE would decide everything (lecture slide 41).

Stage 9: A first run (about 4 min)¶

K-means needs the number of groups K. Take the value from the lecture's example, K = 7, and scale every region to the range [0, 1] (min–max scaling) so that all regions count equally.

Before running the next cell, predict how the 521 weeks will be distributed over the seven groups.

In [18]:
X_weeks = MinMaxScaler().fit_transform(weeks[REGIONS])
total_activity = weeks[REGIONS].sum(axis=1).values
runs = {K: kmeans_labels(X_weeks, K, tie=total_activity)[0] for K in K_SWEEP}      # every run of Stage 10, computed once (numbered by size)
group_colors = shared_group_colors(weeks, runs)                                  # one colour per group of every run; stays the same across K
labels7 = runs[K_DEFAULT]
sizes7 = np.bincount(labels7)
print("group sizes (weeks):", sizes7.tolist())
print("mean photos per week in each group.  Regions: " + ", ".join(f"{r} = {REGION_NAMES[r]}" for r in REGIONS))
profile = weeks[REGIONS].groupby(labels7).mean().round(1)
profile["weeks"] = sizes7
display(profile)
group sizes (weeks): [416, 49, 27, 10, 7, 7, 5]
mean photos per week in each group.  Regions: NW = north-west, SW = south-west, NE = north-east, SE = south-east, GL = Great Lakes
NW SW NE SE GL weeks
0 0.7 0.4 1.6 0.1 0.8 416
1 5.2 8.5 9.5 0.8 0.5 49
2 31.3 6.6 44.3 1.4 1.6 27
3 17.8 9.3 74.9 10.1 1.7 10
4 32.4 12.6 235.3 5.4 2.6 7
5 9.9 4.9 25.7 0.1 39.1 7
6 23.4 36.4 47.8 1.2 9.4 5
In [19]:
display(make_notice_checkpoint(
    "How did you expect the weeks to be distributed over the seven groups?",
    ["Roughly equal groups (about 75 weeks each)", "One huge group and several small ones", "Two big groups and five small ones"],
    "<b>One huge group and several small ones.</b> 416 of the 521 weeks (80%) fall into group 0, whose mean counts are low in every region: the <i>quiet</i> weeks. "
    "The other six groups have 49, 27, 10, 7, 7 and 5 weeks. They are the busy weeks, split by which regions were busy. "
    "k-means does not produce groups of similar size; it follows the structure of the data, and here the structure is a large quiet bulk and a few bursts."))

Stage 10: Which K? (about 6 min)¶

The lecture presented three standard guides for choosing K (slides 55–57): the sum of squared errors (SSE), the percentage of variance explained (both look for an "elbow") and the average silhouette. Compute all three for K = 2 to 15.

Before running the next cell, predict: will there be a clear elbow? At which K do you expect the silhouette to be highest?

In [20]:
sweep_k = kmeans_sweep(X_weeks)
display(sweep_k.round(3))

fig, axes = plt.subplots(1, 3, figsize=(16, 4.2))
axes[0].plot(sweep_k.K, sweep_k.SSE, "o-")
axes[0].set_title("Sum of squared errors (SSE)")
axes[1].plot(sweep_k.K, sweep_k["variance explained (%)"], "o-", color="#ff7f0e")
axes[1].set_title("Variance explained (%)")
axes[2].plot(sweep_k.K, sweep_k.silhouette, "o-", color="#2ca02c")
axes[2].set_title("Average silhouette")
for ax in axes:
    ax.set_xlabel("K")
    ax.axvline(K_DEFAULT, color="grey", ls=":")
plt.tight_layout()
plt.show()
K SSE variance explained (%) silhouette
0 2 19.130 40.290 0.781
1 3 15.354 52.076 0.791
2 4 12.800 60.048 0.663
3 5 10.411 67.503 0.670
4 6 8.776 72.606 0.674
5 7 7.377 76.974 0.663
6 8 6.470 79.805 0.679
7 9 5.783 81.949 0.683
8 10 5.413 83.104 0.684
9 11 5.053 84.229 0.667
10 12 4.624 85.567 0.671
11 13 4.284 86.628 0.672
12 14 4.187 86.932 0.670
13 15 3.902 87.819 0.541
No description has been provided for this image

What this shows: SSE decreases smoothly and the variance explained rises smoothly from 40% (K = 2) to 88% (K = 15), without a clear elbow. The silhouette is highest for K = 3 (0.79) and K = 2 (0.78), then it stays between 0.66 and 0.68 up to K = 14 and drops at K = 15 (0.54).

Why K = 3? Look at what the three groups are: one group has 477 weeks (92% of all), one 37 weeks and one only 7. The silhouette likes a solution that sets the big quiet bulk apart from the busy weeks; it says very little about whether the busy weeks are split in a meaningful way. This is what the lecture meant: the numbers may help to select candidates, but they do not tell the "true" number of groups, and we must look at the groups and compare the runs. That is what the next stages do.

Stage 11: What are the groups? (about 8 min)¶

Interpret the groups of the first run (K = 7) in context, as in the lecture's London example (slides 52–54): when do they occur (calendar view), and what characterises them (the distributions of the counts in every region)?

A word on colours. The colours of the groups are not arbitrary, and in this part they stay the same across runs. The mean profiles of the groups of all runs (K = 2 to 15) were placed together in one 2D map (multidimensional scaling), and each group is coloured by its position in that map (four-corner colour interpolation, slides 69\u201372). Groups with similar profiles get similar colours, and a group that persists from K to K + 1 keeps its colour. (In Part 1 the colours were computed anew for every run, so do not compare colours between runs there.)

In [21]:
colors7 = {g: group_colors[(K_DEFAULT, g)] for g in range(K_DEFAULT)}
plot_calendar(weeks, labels7, colors7, title="Calendar of the weeks: week of the year across, years down, colour = group (K = 7)")
plt.show()
plot_region_boxes(weeks, labels7, colors7)
plt.show()

peak = pd.DataFrame({r: weeks.loc[weeks.groupby("year")[r].idxmax()].set_index("year").week for r in REGIONS})
print("Week of the year with the highest count in each region, per year:")
display(peak.T)
No description has been provided for this image
No description has been provided for this image
Week of the year with the highest count in each region, per year:
year 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016
NW 13 13 15 10 15 14 13 12 11 12
SW 16 16 16 16 16 16 16 16 16 16
NE 13 13 14 14 14 12 15 15 15 13
SE 12 14 12 13 13 12 14 14 2 2
GL 18 19 18 17 19 15 18 20 19 20

Your turn (write in a new markdown cell): (1) Describe two or three of the busy groups in terms of the regions that are active. (2) Compare the times of the highest activity in the different regions across the years: which region peaks first, which last, and which is the most regular?

What this shows: the quiet group (0) is present in every year and every season. Groups 0 and 1 have almost the same green because their profiles are similar (low counts everywhere; group 1 has a few more photos in NW, SW and NE and forms the shoulders of the season, weeks 5 to 17): similar colour means similar group, so use the group numbers in the box plots to tell them apart. the busy weeks form six small groups: for example a group of 7 weeks with very high NE counts (about 235 photos per week), a group of 7 weeks in which the Great Lakes region is active (about 39 photos per week) and a group of 5 weeks in which SW is unusually active (about 36 photos per week). The calendar shows that the busy weeks cluster in a season: 80% of them fall into weeks 7 to 17 (mid-February to the end of April), and every year has between 5 and 15 of them.

The peak table adds a lot. NE peaks in weeks 12–15 and NW in weeks 10–15. GL peaks latest (weeks 15–20). SW peaks in week 16 in all ten years, which is suspiciously regular for a natural process, and a recurring event in a fixed week would be a plausible explanation (a hypothesis to check, not a result). SE has too few photos to be reliable: in 2015 and 2016 its highest week is week 2, where the counts are tiny.

Stage 12: Compare runs: what changes from K to K + 1? (about 6 min) (interactive)¶

The lecture's London example built knowledge by comparing neighbouring runs (slide 54): knowledge gain: a new profile, knowledge refinement, and a small cluster as a signal to stop. The tool below shows, for any K, how the weeks of the K groups are distributed over the K + 1 groups of the next run (rows: groups at K, columns: groups at K + 1; groups are numbered by size).

Move the slider, and look for: groups that persist (one big number in the row), groups that split, and groups that are new. The group labels carry the colours of the groups, so you can also follow a group by its colour.

First an overview of all runs: one bar per K, one coloured segment per group (the large quiet group 0 is left out). Segments of the same colour in neighbouring bars are the same group.

In [22]:
plot_busy_weeks_by_run(runs, group_colors)
plt.show()
No description has been provided for this image
In [23]:
def show_transition(K):
    la, lb = runs[K], runs[K + 1]
    ct = pd.crosstab(la, lb)
    fig, ax = plt.subplots(figsize=(9, 5.2))
    sns.heatmap(ct, annot=True, fmt="d", cmap="Blues", cbar=False, ax=ax)
    ax.set_xticklabels([f"{g}\n({n})" for g, n in zip(ct.columns, np.bincount(lb))])
    ax.set_yticklabels([f"{g} ({n})" for g, n in zip(ct.index, np.bincount(la))], rotation=0)
    tint_labels(ax.get_xticklabels(), [group_colors[(K + 1, g)] for g in ct.columns])
    tint_labels(ax.get_yticklabels(), [group_colors[(K, g)] for g in ct.index])
    ax.set_xlabel(f"group at K = {K + 1} (size in weeks)")
    ax.set_ylabel(f"group at K = {K} (size in weeks)")
    ax.set_title(f"Where do the weeks of the K = {K} groups go at K = {K + 1}?")
    plt.show()


w_k = widgets.IntSlider(value=K_DEFAULT, min=2, max=14, step=1, description="K", continuous_update=False, layout=widgets.Layout(width="480px"))
out_tr = widgets.Output()


def on_k(change):
    with out_tr:
        clear_output(wait=True)
        show_transition(change["new"])


w_k.observe(on_k, names="value")
display(widgets.VBox([w_k, out_tr]))
with out_tr:
    show_transition(K_DEFAULT)

What this shows (K = 7 to K = 8): colours first: a group that persists has the same colour on both axes, and the large quiet group keeps practically the same green from K = 2 to K = 15, whereas groups that split or merge change colour. Now the numbers: the quiet group keeps 98% of its weeks in one group (it is stable), three small groups (10, 7 and 5 weeks) carry over unchanged, and the changes are small and local: the group of 27 weeks and one of the 7-week groups split. At K = 8 the sizes are 412, 41, 29, 12, 11, 7, 5 and 4 weeks. Compare other values of K. When the busy weeks keep splitting into groups of a few weeks, as at the top of the range, you gain little new knowledge from each step. That is the lecture's signal to stop.

Stage 13 (optional): How confident is each assignment? (about 5 min)¶

The silhouette of a single week measures how clearly it belongs to its group: close to 1, it is far from the other groups; around 0 or below, it lies between two groups. In SmartIterator this value (rescaled to 0–1) is the assignment confidence.

In [24]:
sil7 = silhouette_samples(X_weeks, labels7)
low = [(g, int((labels7 == g).sum()), float((sil7[labels7 == g] < 0.25).mean())) for g in range(K_DEFAULT)]
print("share of weeks with a silhouette below 0.25, by group (number of weeks):")
print("  " + ",  ".join(f"group {g} ({n}): {s:.0%}" for g, n, s in low))

fig, ax = plt.subplots(figsize=(11, 4.2))
sns.stripplot(x=labels7, y=sil7, order=list(range(K_DEFAULT)), palette=[colors7[g] for g in range(K_DEFAULT)], size=4, jitter=0.25, ax=ax)
ax.axhline(0.25, color="grey", ls=":")
ax.set_xlabel("group (numbered by size)")
ax.set_ylabel("silhouette of the week")
plt.show()
share of weeks with a silhouette below 0.25, by group (number of weeks):
  group 0 (416): 2%,  group 1 (49): 41%,  group 2 (27): 81%,  group 3 (10): 60%,  group 4 (7): 43%,  group 5 (7): 0%,  group 6 (5): 0%
No description has been provided for this image

What this shows: the large quiet group is clear (only 2% of its weeks are below 0.25), whereas the small busy groups are not: 81% of the weeks of the 27-week group, 60% of the 10-week group and 41% of the 49-week group are low-confidence. These groups blend into each other: the busy weeks form a continuum (the shoulders of the season) more than separate types. A grouping can be useful and still have blurred borders; the violins in the SmartIterator display make this visible.

Stage 14 (optional): Does the preprocessing decide the result? (about 6 min)¶

Slide 41 warns that distances depend on how the attributes are scaled. Compare no scaling, z-score and min–max for K = 7, and check how much the result depends on the random start of k-means.

In [25]:
raw = weeks[REGIONS].values.astype(float)
variants = {"no scaling": raw, "z-score": StandardScaler().fit_transform(raw), "min-max": X_weeks}
ref_labels, _ = kmeans_labels(X_weeks, K_DEFAULT, tie=total_activity)
rows = []
for name, data in variants.items():
    km = KMeans(K_DEFAULT, random_state=SEED_DEFAULT, n_init=10).fit(data)
    spread = ((km.cluster_centers_ - data.mean(axis=0)) ** 2).sum(axis=0)
    rows.append({"scaling": name, "variance explained (%)": round(100 * (1 - km.inertia_ / ((data - data.mean(axis=0)) ** 2).sum()), 1),
                 "share of the between-group spread due to NE": round(float(spread[REGIONS.index("NE")] / spread.sum()), 2),
                 "agreement with min-max (ARI)": round(adjusted_rand_score(ref_labels, km.labels_), 2)})
display(pd.DataFrame(rows))

print("Random start: 30 seeds, one start each; agreement (ARI) between all pairs of seeds, and the silhouette of the 30 runs")
for K in (7, 15, 25):
    labs = [KMeans(K, random_state=s, n_init=1).fit_predict(X_weeks) for s in range(1, 31)]
    ari = [adjusted_rand_score(labs[i], labs[j]) for i in range(30) for j in range(i + 1, 30)]
    sil = [silhouette_score(X_weeks, lab) for lab in labs]
    print(f"  K = {K:>2}: median ARI {np.median(ari):.2f}, lowest {min(ari):.2f};  silhouette from {min(sil):.2f} to {max(sil):.2f}")
scaling variance explained (%) share of the between-group spread due to NE agreement with min-max (ARI)
0 no scaling 93.0 0.97 0.65
1 z-score 76.3 0.21 0.97
2 min-max 77.0 0.23 1.00
Random start: 30 seeds, one start each; agreement (ARI) between all pairs of seeds, and the silhouette of the 30 runs
  K =  7: median ARI 0.94, lowest 0.81;  silhouette from 0.65 to 0.68
  K = 15: median ARI 0.85, lowest 0.61;  silhouette from 0.50 to 0.69
  K = 25: median ARI 0.78, lowest 0.47;  silhouette from 0.42 to 0.61

What this shows: without scaling, K = 7 "explains" 93% of the variance, more than with scaling (77%), but 97% of the difference between the groups comes from NE alone: the high number is an artefact of the scale of one column, and scores cannot be compared across preprocessing choices. The groups also differ (agreement with the min-max result: ARI 0.65), whereas z-score and min–max give almost the same groups (ARI 0.97). The random start matters little at K = 7 (median ARI 0.94 between seeds) and more and more as K grows (0.85 at K = 15, 0.78 at K = 25, with a lowest value of 0.47): the higher K, the less you can trust a single run. The silhouette tells the same story here: its spread over the seeds grows from 0.03 (K = 7) to 0.19 (K = 15).

Stage 15: Wrap-up of Part 2¶

Compare the two parts. In Part 1 the question was where the concentrations are; in Part 2 it was which weeks look alike. In both, the metrics narrowed the choices but did not decide them, the comparison of runs told us what changes, and the interpretation in context (the calendar, the places, the seasons) turned groups into knowledge. Write in a new markdown cell: which K would you use for the weekly counts, and what makes you confident or not confident?

Recommendations: how to supervise an unsupervised grouping¶

The SmartIterator page (https://geoanalytics.net/and/SmartIterator/, section Practical Recommendations) condenses the experience of applying this approach to three method families into eight recommendations. Here they are, each with the place in this practical where you already did it:

  1. Start coarse, refine progressively. Begin with a wide sweep at a coarse step to find the region of interest (elbows, peaks, plateaus), then narrow the range and reduce the step. Two to three rounds usually suffice, each informed by the previous one. (Stage 4: coarse sweeps; Stage 6: a second round.)
  2. Let the stability of the groups, not the metrics alone, define stability. A metric peak only narrows the candidates. The evidence comes from how the groups behave when the parameter changes: a group that persists with little change at the neighbouring settings is stable; a group that splits in two may hide sub-structure; several thin flows converging into one new group may be a "wastebasket" of unrelated members; a group that thins out progressively is dissolving. A group that splits already at the very next step may be an artefact of the granularity. (Stage 5: which clusters recur; Stage 12: what happens from K to K + 1.)
  3. Use domain views to break metric ties. When settings score alike, look at them in the domain views: are the clusters contiguous on the map, coherent in time, with distinct profiles? Domain coherence often discriminates between statistically equivalent alternatives. (Stages 6, 7 and 11: the maps, the cubes, the calendar.)
  4. Inspect what changes, not only what persists. Look at the members that leave a group at the next setting, and where they go. Losses at the edge of a spatial cluster mean that the finer setting trims boundary members; losses scattered at random suggest over-fitting to noise; losses that form a coherent sub-group suggest genuine sub-structure. (Stage 5: the clusters that do not recur; Stage 12: the groups that split or merge.)
  5. Treat completeness as necessary, not sufficient. In SmartIterator an iteration is complete if it contains all recurrent group patterns (archetypes). That makes it a strong candidate, but it does not guarantee interpretability: check the other points as well. (You can try this in the demonstrator.)
  6. Verify seed robustness for partition-based methods. Run 20–30 seeds at the chosen K, and look at the score and at the groups. In Stage 14 the silhouette spread and the disagreement between the groups grow together with K. A stable score does not prove stable groups: in the EU population example of the SmartIterator paper the silhouette varied by only 0.012 over 30 seeds, although the groups of different seeds agreed only moderately (median adjusted Rand index 0.53).
  7. Document rejections explicitly. When you reject a setting, record which evidence discriminated (metrics? transitions? domain views?), what you saw, and what the rejection tells you about the data. Documented rejections strengthen confidence in the final choice and show what the data does not support. (Example: K = 3 has the highest silhouette, but it merely separates the quiet weeks from the busy weeks, see Stage 10.)
  8. When in doubt, keep multiple candidates. You need not converge to a single winner: a coarse typology (for example K = 7) and a fine one (K = 15) can be complementary lenses, and understanding how the coarse groups differentiate into the fine ones is valuable in itself. (Stage 12.)

Write in a new markdown cell a note that documents one rejection of your own (recommendation 7): a setting that you did not choose, the stage that gave the evidence, what you saw there, and what it tells you about the data.

Try the same in the demonstrator. Open Cherry blossom photos per week at https://geoanalytics.net/and/SmartIterator/demo : the metrics chart, the calendar and the box plots show these results, the transition view shows Stage 12 for all K at once, and Order runs (for the sweep over seeds) shows Stage 14.


Part 3 — Audit a confident summary (homework, about 15 minutes)¶

A single run is easy to over-interpret, and so are the summaries of it, including those written by an AI assistant. Below are two confident summaries, one for each part. As in the earlier follow-up practical, read each passage, decide which problems it has, and only then reveal the analysis.

Passage 1 (about the weekly counts)¶

Great question! The silhouette score peaks at K = 3 (0.79), which proves that cherry-blossom photo activity has exactly three regimes. This confirms that K = 3 is the true structure of the data. The result held up consistently across every setting we tried, so you can safely use three regimes as the basis for planning photo-tourism capacity.

In [26]:
CATEGORY_CAUSAL = "Causal / prescriptive claim (see the manual's DON'T list)"
AUDIT_WEEKS = {
    "Sycophancy": (True, "\u2018Great question!\u2019 praises the question, not any evidence."),
    "Confirmation bias": (False, "The passage does not select evidence to fit an expectation; the problem is how it interprets one number."),
    "Overstated certainty": (True, "\u2018Proves\u2019, \u2018confirms\u2019 and \u2018the true structure\u2019 for a peak of a heuristic score. In Stage 10, K = 2 scored almost as high (0.78), and no score proves a number of groups."),
    "False precision": (False, "0.79 is the correct silhouette for K = 3; the numbers themselves are fine."),
    "Unacknowledged confounds": (True, "The silhouette at K = 3 rewards setting the quiet bulk apart (92% of the weeks fall into one group), and the result depends on the scaling: without it the groups change (Stage 14). Neither is mentioned."),
    "Erased uncertainty": (True, "\u2018Held up consistently\u2019 erases what Stages 10\u201314 showed: the other K give a different picture, and the scaling, the random start and the low-confidence groups all matter."),
    "Fabricated or unseen detail": (True, "\u2018Every setting we tried\u2019: only one setting (min\u2013max scaling, one seed) was ever shown. No other tests are on record."),
    "Style masking substance": (False, "The issue is the specific overreaching claims, not formatting or tone standing in for evidence."),
    CATEGORY_CAUSAL: (True, "\u2018Safely use three regimes \u2026 for planning photo-tourism capacity\u2019 turns a grouping of photo counts into an action. Photo counts are a proxy for photographers, not visitors, and a grouping says nothing about causes."),
}
display(make_audit_tool(AUDIT_WEEKS))

Passage 2 (about the photos)¶

Excellent analysis! DBSCAN identified 106 cherry-blossom hotspots, which confirms that Washington DC is the top destination. The result is robust: changing the parameters does not change it. City planners should therefore concentrate festival resources on the busiest clusters.

In [27]:
AUDIT_PHOTOS = {
    "Sycophancy": (True, "\u2018Excellent analysis!\u2019 praises the work, not any evidence."),
    "Confirmation bias": (False, "No evidence is selected to fit an expectation here."),
    "Overstated certainty": (True, "\u2018Confirms\u2019 and \u2018robust\u2019: Stages 4 and 5 showed how much the result depends on the parameters."),
    "False precision": (True, "\u2018106\u2019 is presented as a fact, but it is the result of one parameter setting (from 85 to 265 clusters for N = 3 to 12), and these are space-time concentrations, not hotspots: Stage 6 united them into 14 places."),
    "Unacknowledged confounds": (True, "Photos show where people take and upload photos (population, tourism, who uses the service), not where the blossoms are best or where visitors go."),
    "Erased uncertainty": (True, "\u2018Changing the parameters does not change the result\u2019 is wrong for N and Rt (Stage 4) and only roughly true for Rs; 12 of the 106 clusters did not recur across the Rs sweep (Stage 5)."),
    "Fabricated or unseen detail": (False, "Washington DC does have the most photos (3,201 of the 6,770 photos in round-1 clusters), so this part is supported by the analysis; the problem is the wording."),
    "Style masking substance": (False, "The issue is the specific claims, not formatting or tone."),
    CATEGORY_CAUSAL: (True, "\u2018Concentrate festival resources\u2019 is an action recommendation derived from a clustering of photo locations."),
}
display(make_audit_tool(AUDIT_PHOTOS))

Rewrite and synthesise¶

  1. In a new markdown cell, rewrite each passage in two or three sentences that you could defend: every claim must be supported by something you saw in this notebook, and the uncertainty that you found must be visible.
  2. Synthesis (5–6 sentences). A colleague is about to cluster a new data set and plans to run the algorithm once with default settings. What do you tell them to do instead? Use at least three things you saw in this practical (for example: sweeps, comparing groups across runs, the distance function and scaling, a second round, interpretation in context, being careful with scores and with proxies).

Credits¶

Photo records: public Flickr metadata (location and time only). Base map: Natural Earth (public domain). Course: INM433 Visual Analytics, with the SmartIterator approach of G. Andrienko and N. Andrienko.