4. Top Crash Clustering with DBSCAN on Stack Features

Why Density-Based Clustering Fits Crash Stacks

Crash triage rarely has labels at ingestion time. A build ships, crashes arrive, and the bug ID that explains them is assigned days later by a human. DBSCAN is attractive here because it discovers groups from the data itself: it needs no preset cluster count, it tolerates irregular cluster shapes, and it explicitly marks sparse points as noise — which in crash analytics maps naturally to "one-off, possibly environmental or flaky" crashes that should not pollute a real regression cluster.

The core idea is that a crash is a core point if at least min_samples crashes (including itself) lie within distance eps in feature space. Core points within eps of each other are density-connected and join the same cluster; points reachable from a core point but not themselves dense become border points; everything else is noise (label -1). The two parameters therefore encode a concrete engineering statement: "crashes closer than eps are the same bug, and a real bug produces at least min_samples crashes."

Turning Stack Traces into Stack Features

DBSCAN needs a numeric vector per crash. The most defensible representation for stack data is a binary bag of normalized frames: each crash becomes a set of tokens drawn from its top frames, and the feature vector marks presence/absence. Normalization matters more than the clustering algorithm — strip addresses, offsets, and volatile paths so that the same code path yields the same token across builds and devices.

import re
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.cluster import DBSCAN
from sklearn.metrics import adjusted_rand_score

ADDR = re.compile(r"0x[0-9a-fA-F]+")
VOLATILE = re.compile(r"(/data/user/\d+|/tmp/[^/]+|builds/[^/]+)")

def normalize_frame(frame: str) -> str:
    # "libfoo.so+0x1a2c in com.acme.Sync.push(Sync.java:88)"
    f = ADDR.sub("", frame)
    f = VOLATILE.sub("<volatile>", f)
    f = re.sub(r"\(\w+\.java:\d+\)", "(src)", f)   # drop line numbers
    return f.strip()

def stack_features(trace: dict, top_k: int = 8) -> dict:
    frames = [normalize_frame(fr) for fr in trace["frames"][:top_k]]
    feats = {f"frame::{fr}": 1 for fr in frames}
    feats[f"module::{trace['module']}"] = 1
    feats[f"exc::{trace['exception_type']}"] = 1
    return feats

Two design choices are worth calling out. First, top_k=8 keeps the feature space small and focuses on the frames nearest the throw site, which are the most bug-discriminating. Second, adding module and exception_type as tokens lets DBSCAN separate crashes that share a generic framework frame (e.g., a common Handler.dispatch) but differ in the actual failing module.

Choosing eps and min_samples from the Data

With binary features, a natural distance is Jaccard distance, which ignores shared absence and rewards shared frames. DBSCAN accepts a precomputed distance matrix, so we compute it once and reuse it for parameter sweeps.

from sklearn.metrics import pairwise_distances

vec = DictVectorizer(sparse=False)
X = vec.fit_transform([stack_features(t) for t in traces])
D = pairwise_distances(X, metric="jaccard")

# k-distance heuristic: sort each point's distance to its k-th neighbor
k = 4
kth = np.sort(D, axis=1)[:, k]
kth_sorted = np.sort(kth)
# eps is chosen near the "knee" of this curve; inspect before committing
for eps in (0.15, 0.20, 0.25, 0.30):
    labels = DBSCAN(eps=eps, min_samples=k, metric="precomputed").fit_predict(D)
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
    noise = (labels == -1).mean()
    print(f"eps={eps:.2f} clusters={n_clusters} noise={noise:.1%}")

The k-distance plot is the standard diagnostic: distances rise slowly for points inside dense regions and then jump at the boundary of the sparse tail. Pick eps at the knee. If the knee is ambiguous, prefer the smaller eps — over-merging distinct bugs is worse for triage than leaving a few extra noise points, because a merged cluster sends two unrelated bugs to one owner.

Evaluating Cluster Purity Against Bug IDs

Bug IDs are the ground truth we withheld from the algorithm. Two complementary metrics tell different stories:

• Purity — for each cluster, the fraction of its members sharing the majority bug ID, averaged weighted by cluster size. High purity means clusters are internally coherent, but purity alone can be gamed by many tiny clusters.
• Adjusted Rand Index (ARI) — a chance-corrected agreement between cluster labels and bug IDs. ARI penalizes both over-splitting and over-merging, so it is the better single number for comparing eps settings.

def purity(labels, bug_ids):
    total, correct = 0, 0
    for c in set(labels):
        if c == -1:
            continue
        members = [b for l, b in zip(labels, bug_ids) if l == c]
        if not members:
            continue
        total += len(members)
        correct += max(members.count(b) for b in set(members))
    return correct / total if total else 0.0

labels = DBSCAN(eps=0.20, min_samples=4, metric="precomputed").fit_predict(D)
print("purity:", round(purity(labels, bug_ids), 3))
print("ARI   :", round(adjusted_rand_score(bug_ids, labels), 3))

Report purity and ARI together, and always alongside the noise rate. A configuration with purity 0.95 but 40% noise has effectively abandoned a large share of crashes; a configuration with purity 0.70 has merged distinct bugs and will misroute tickets.

Reading the Result and Acting on It

The SVG above shows the full path and the three outcomes that matter operationally. Cluster A and B are healthy: high purity, meaningful size, and a single dominant bug ID — these can be auto-linked to their bug and routed. Cluster C is the failure mode to hunt: purity 0.62 means two or more bugs were merged, usually because eps was too generous or the feature set lacked a discriminating token (often a missing module or exception_type). The noise bucket is not garbage — it is the queue for manual review, and a sudden spike in noise rate between builds is itself a signal that a new crash family appeared.

A practical tuning loop: fix min_samples at the smallest cluster size you would actually triage (often 3–5), sweep eps across the k-distance knee region, and pick the setting that maximizes ARI while keeping noise below an agreed ceiling (for example 15%). Then inspect the lowest-purity non-noise cluster by hand — that single cluster usually reveals whether the problem is a parameter or a missing feature.

Deliverable: Cluster Review Sheet

For each non-noise cluster produced by the chosen configuration, fill one row. This is the artifact a triage engineer actually consumes.

Acceptance for this task: the chosen eps/min_samples pair is justified by the k-distance knee, purity and ARI are reported on a held-out labeled slice, and every non-noise cluster has a documented action. If cluster C cannot be split by adding a feature, that is a legitimate finding — it means the two bugs are genuinely indistinguishable from stack features alone and need runtime context (the subject of a later case) to separate.