G15: Data engineering, clustering, and defensible inference

Prerequisites and observable goals#

The central question: what does one row represent?#

A dataset is not just a matrix. A row represents an entity, event, interval, measurement, or aggregation under a collection process. A column may be a value observed at prediction time, an outcome observed later, or a summary inadvertently using the future. Define the row’s grain: one session, one player, one device-hour, or another explicit unit. Two tables with compatible-looking column names can have different grains and incompatible measurement assumptions.

For a latency model, distinguish event time, ingestion time, prediction time, and label-availability time. A field computed after a failure cannot legitimately predict that failure in an earlier real-time decision. Even a split based on event time can leak a future-derived feature. State the intended operational question before choosing preprocessing and joins. SQL constraints help enforce recorded relationships; they do not prove that the recorded measurements represent the intended real-world concepts. The SQLite and Python references describe execution behavior, not the meaning of a dataset. [G-SQLITE]

Joins can silently change the unit of analysis#

Suppose a player has two purchase rows and three session rows. Joining both child tables directly on player ID produces six combinations for that player. Summing purchase amount afterward counts each purchase three times. The query can run without an error and still answer the wrong question.

If the desired output is one row per player, first aggregate each child table to that grain, then join the summaries. Alternatively, choose an event-level relationship that genuinely links one purchase to one session, with a suitable key. An arbitrary DISTINCT is not a general repair: equal values can be legitimate separate purchases, and distinctness across all columns may leave the duplication unchanged.

A conceptual query shape is:

WITH purchase_totals AS (
  SELECT player_id, SUM(amount) AS amount
  FROM purchase GROUP BY player_id
), session_totals AS (
  SELECT player_id, COUNT(*) AS sessions
  FROM session GROUP BY player_id
)
SELECT p.id, t.amount, s.sessions
FROM player AS p
LEFT JOIN purchase_totals AS t ON t.player_id = p.id
LEFT JOIN session_totals AS s ON s.player_id = p.id;

Whether absent totals should become zero is a semantic decision. No observed purchases may mean zero purchases in a complete ledger, but it may mean missing coverage in an incomplete feed. SQL NULL is not automatically a numerical zero. Record coverage, keys, and missingness assumptions alongside the query.

Split by the future question, then fit preprocessing#

When evaluating on new users, put all rows of each user in one partition. When evaluating a future period, respect the ordering and availability of features and labels. A grouped random split answers a different question from a chronological split on recurring users. Neither procedure is universally best. GP2 uses disjoint synthetic groups to demonstrate an explicit new-group question; it does not model every deployment scenario.

The lab’s split_groups takes group identifiers, sorts the unique set, shuffles it with a local seeded generator, assigns roughly 60/20/20 percent of groups, then maps the choices back to row indices. The size boundary is expressed in groups, so row counts can differ when group sizes differ. Sorting first avoids dependence on a set’s iteration order. Random seeds make a particular computation reproducible; they do not certify representative sampling.

Fit each feature mean and population-scale standard deviation only on training rows:

Transform a later value using $(x_j-\mu_j)/s_j$. The reference replaces a zero training scale by one so a constant training feature remains numerically defined. That convention does not magically make a previously unseen varying feature informative. Save the training means, scales, column order, and conventions with the model artifact.

For training values $(0,2)$, $\mu=1,s=1$. A held-out value 1000 transforms to 999. Re-estimating the scale using 1000 would alter the representation based on evaluation data. The large value may indicate a distribution change or outlier; diagnose it rather than silently refitting at test time.

Derive k-means as alternating conditional minimization#

For points $x_i\in\R^d$, labels $c_i\in\{1,\ldots,k\}$, and centers $\mu_j$, the squared-distance objective is

With fixed centers, assigning a point to a nearest center minimizes that point’s contribution. With fixed nonempty assignments, differentiate the terms of one cluster with respect to its center:

Setting the derivative to zero gives the arithmetic mean. The quadratic Hessian is $2n_jI$, positive definite for $n_j>0$, so that mean is the unique conditional minimizer. Each full assignment/update cycle cannot increase the ideal squared-error objective under these conditions. This is not a proof of reaching the global optimum across all assignments. The primary course notes discuss this alternating algorithm and its limitations. [G-ML]

For one-dimensional points $(0,2,8,10)$ and initial centers $(0,10)$, nearest assignments form $(0,2)$ and $(8,10)$. New centers are $(1,9)$ and the squared error is $1+1+1+1=4$. Assignments remain stable on another cycle. Different initial centers can lead to different local outcomes on other datasets.

If a cluster receives no points, the mean is undefined. The lab retains that center instead of dividing by zero or randomly moving it. This is a defined empty-cluster policy, not a guarantee that every center will become useful. Ties choose the lowest center index for determinism. The reference bounds iterations and returns an objective history; a small increase beyond roundoff tolerance signals a defect in the compared objective or update implementation.

Distances encode assumptions about representation#

Squared Euclidean distance treats coordinate scales as meaningful. A feature measured in milliseconds can dominate another measured in seconds solely because of units. Scaling may be justified, but a default scaler does not decide what semantic similarity should mean. Clusters are outputs of a representation and objective, not discovered categories guaranteed to exist in nature.

Principal-component analysis offers a different objective: approximate centered data with a low-dimensional linear subspace, commonly obtained through SVD. Fit the centering and subspace on training data when the representation feeds a held-out predictive evaluation. PCA emphasizes variance rather than class discrimination; a low-variance direction may contain useful labels. A clustering score on the same data used to choose the representation cannot by itself establish a useful operational grouping. Detailed PCA implementation is a continuation beyond this chapter’s assigned k-means lab, building on foundation A02.

Associations and aggregate rates require a denominator#

In a dataset of ten transactions, suppose item A occurs four times, B five times, and both three times. The association rule A $\Rightarrow$ B has support $3/10$, confidence $3/4$, and lift $(3/4)/(5/10)=1.5$. Lift compares the conditional rate with the marginal rate; it does not establish that buying A causes B. Selection effects, common causes, repeated users, and temporal ordering may explain the association. Small counts can be unstable, and searching many rules creates a selection problem.

A related trap is a reversal between subgroup and aggregate rates. Suppose algorithm A succeeds on 9 of 10 easy cases and 54 of 90 hard cases. Algorithm B succeeds on 72 of 90 easy cases and 5 of 10 hard cases. A has higher success in each stratum: $.9>.8$ and $.6>.5$. But its aggregate rate is $63/100=.63$, lower than B’s $77/100=.77$. A was evaluated much more often on hard cases. The weighted averages use different weights. Equalize the workload mix or specify the deployment mix before interpreting the aggregate as a comparison of methods.

An experiment with random assignment can address some confounding when its assumptions hold. Observational regression can adjust for specified variables under additional assumptions, but does not guarantee removal of unmeasured confounding. Report effect sizes and uncertainty at the appropriate independent unit, and explain what identification assumption supports a causal claim rather than adding the word “causal” to a correlation.

Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

Smallest useful hints#

For .02, pair each purchase with every session. For .04, write a weighted average before comparing methods. For .06, test partitions on groups with unequal numbers of rows as well as the balanced fixture.

Complete solutions: G15#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""G15: group-disjoint splits, training-only scaling, and bounded Lloyd clustering."""
import math
import random


def split_groups(groups, seed=21):
    if not groups or any(type(g) is not str or not g for g in groups):
        raise ValueError("nonempty string group labels required")
    unique = sorted(set(groups))
    if len(unique) < 5:
        raise ValueError("at least five groups required for this split policy")
    random.Random(seed).shuffle(unique)
    a,b = max(1,int(.6*len(unique))), max(1,int(.2*len(unique)))
    partitions = [set(unique[:a]),set(unique[a:a+b]),set(unique[a+b:])]
    return {name:[i for i,g in enumerate(groups) if g in part]
            for name,part in zip(("train","validation","test"),partitions)}


def matrix(X):
    if not X or not X[0] or len(X) > 10000 or len(X[0]) > 64:
        raise ValueError("bounded nonempty matrix required")
    d = len(X[0])
    if any(len(r) != d or any(not math.isfinite(v) for v in r) for r in X):
        raise ValueError("finite rectangular features required")
    return [[float(v) for v in r] for r in X]


def fit_scaler(X):
    X = matrix(X)
    n,d = len(X),len(X[0])
    mean = [math.fsum(r[j] for r in X)/n for j in range(d)]
    scale = [math.sqrt(math.fsum((r[j]-mean[j])**2 for r in X)/n) for j in range(d)]
    if not all(math.isfinite(x) for x in [*mean,*scale]):
        raise ValueError("unsupported feature scale")
    return {"mean":mean,"scale":[s if s > 0 else 1. for s in scale]}


def transform(X, scaler):
    X = matrix(X)
    mu,s = scaler["mean"],scaler["scale"]
    if len(mu) != len(X[0]) or len(s) != len(mu) or any(v <= 0 for v in s):
        raise ValueError("invalid scaler dimensions or scales")
    if not all(math.isfinite(v) for v in [*mu,*s]):
        raise ValueError("nonfinite scaler")
    return [[(x-m)/sd for x,m,sd in zip(row,mu,s)] for row in X]


def kmeans(X, initial, steps=50):
    X,C = matrix(X),matrix(initial)
    if len(C) > len(X) or len(C[0]) != len(X[0]) or type(steps) is not int or not 1 <= steps <= 1000:
        raise ValueError("matching cluster dimensions and bounded step count required")
    d = len(X[0])
    def assign(centers):
        return [min(range(len(centers)),
                    key=lambda j:math.fsum((a-b)**2 for a,b in zip(x,centers[j]))) for x in X]
    history=[]
    for _ in range(steps):
        labels = assign(C)
        new = []
        for j in range(len(C)):
            members = [x for x,l in zip(X,labels) if l == j]
            new.append([math.fsum(x[k] for x in members)/len(members) for k in range(d)]
                       if members else list(C[j]))
        labels = assign(new)
        sse = math.fsum((v-c)**2 for x,l in zip(X,labels) for v,c in zip(x,new[l]))
        if not math.isfinite(sse):
            raise ValueError("nonfinite clustering objective")
        history.append(sse)
        if new == C:
            C = new
            break
        C = new
    return {"centers":C,"labels":labels,"sse":history[-1],"history":history}


def fixture(seed=21, n_groups=30):
    rng = random.Random(seed)
    rows=[]
    for g in range(n_groups):
        group_effect = rng.uniform(-.3,.3)
        for r in range(4):
            x = [rng.uniform(-2,2),rng.uniform(-2,2)]
            noise = rng.uniform(-.4,.4)
            rows.append({"group":f"g{g:03}","x":x,
                         "y":int(x[0]+.6*x[1]+group_effect+noise > 0)})
    return rows


if __name__ == "__main__":
    rows=fixture()
    print({k:len(v) for k,v in split_groups([r["group"] for r in rows]).items()})
    print(kmeans([[0.],[2.],[8.],[10.]],[[0.],[10.]]))

Readiness and continuation#

Given an unfamiliar table, explain its grain, keys, available-at-prediction fields, missingness, and intended evaluation unit before selecting a model. Reproduce the join-duplication and aggregate-reversal counterexamples without notes. Further work includes schema evolution, streaming event-time semantics, database execution plans, causal inference, and robust missing-data models; none is replaced by a successful synthetic clustering run.