Predictive Modeling and Machine Learning Fundamentals Questions

Hypothesis:

• H0: Segment-based targeting does not change conversion rate vs. control.
• H1: Segment-based targeting increases conversion rate.

Primary metric:

• Primary: conversion rate (binary: purchase/sign-up within campaign window). Use uplift (treatment_conversion − control_conversion) as effect.

Sample size estimation:

• Choose significance α=0.05, power=0.8. Estimate baseline conversion p0 from historical data (e.g., 2%). Define minimum detectable effect (MDE) relative or absolute (e.g., +20% relative → p1=0.024). For proportions, approximate per-arm sample:
  n = [ (Z_{1-α/2}√(2p̄(1−p̄)) + Z_{power}√(p0(1−p0)+p1(1−p1)))^2 ] / (p1−p0)^2
• Compute total = 2n. If testing per-segment effects, adjust by multiplicity (see below) or size each segment accordingly.

Randomization strategy:

• Unit: customer. Randomize at customer level to treatment (segment-based personalized creatives/offers) or control (generic campaign). Implement deterministic assignment (hashed user_id + experiment_salt) to ensure consistency across channels and repeat exposures.

Stratification and blocking:

• Stratify randomization by key confounders: segment (the K-Means label), geography, and prior activity (e.g., recency). Within each stratum, randomize 50/50 to ensure balance and reduce variance.

Multiple segments / analysis plan:

• Primary analysis: intent-to-treat (ITT) comparison of overall conversion rates using two-proportion z-test (or logistic regression with covariates). Report absolute and relative lift with 95% CIs.
• Segment-level analysis: estimate lift per segment with interaction term in logistic regression: logit(p) = β0 + β1treatment + Σγ_segment + Σδ_segmenttreatment + covariates. Test δ coefficients for heterogenous effects.
• Correct for multiple comparisons: pre-specify hierarchy — first test overall effect; only if significant, test segments (closed testing). Alternatively control FDR (Benjamini-Hochberg) or use Bonferroni for conservative control.
• Optional: Bayesian hierarchical model to borrow strength across segments and get shrinkage estimates.

Interpretation and stopping rules:

• Predefine primary metric, sample size, and fixed-horizon analysis to avoid peeking. If using sequential monitoring, apply alpha spending (e.g., O’Brien-Fleming). Consider practical significance (business value) and heterogeneity: if overall lift is small but some segments show large positive lift, consider targeting those segments only.

Monitoring and validity:

• Monitor balance checks, ensure no differential attrition, log assignment and exposures. Run falsification tests (placebo metrics) to detect issues.

Actionable decision rules:

• If overall lift significant and positive → rollout. If overall null but certain segments show robust positive lift after correction → targeted rollout to those segments. If negative → rollback and analyze model/creative.

Geometric differences and assignment

• Euclidean (L2): distance = sqrt(sum (xi - xj)^2). Voronoi regions are based on Euclidean balls; decision boundaries are curved/rounded. Clusters tend to be spherical (isotropic) in feature space.
• Manhattan (L1): distance = sum |xi - xj|. Voronoi regions are polytopes whose “balls” look like diamonds (axis-aligned octahedra in higher dims). Decision boundaries are piecewise-linear; clusters align more with axes.

Centroid computation and objective

• Standard K‑Means (L2) minimizes sum of squared Euclidean distances. The optimal cluster center is the mean of points in the cluster (L2-optimal).
• If you replace the objective with sum of L1 distances, the optimal center is the coordinate-wise median, not the mean. Practically you’d use k‑medians or k‑medoids (medoid = an actual data point) algorithms instead of vanilla Lloyd’s K‑Means, because the mean no longer minimizes L1.

Effects on cluster shape and behavior

• L2 encourages compact, spherical clusters and is sensitive to large deviations in any direction (distance grows as square).
• L1 yields diamond/axis-aligned cluster shapes and is more robust to a single large deviation because contributions sum linearly; using medians reduces sensitivity to outliers.

When to prefer one over the other

• Use L2/K‑Means when cluster geometry is roughly spherical, features are continuous and roughly Gaussian, and you want mean-based centers (common default).
• Use L1/k‑medians or k‑medoids when data is high-dimensional or sparse, contains outliers, or when you want robustness and interpretability (medoids are actual samples). L1 can perform better when features have heavy tails or when axis-aligned differences matter.

Feature scaling interaction

• Both metrics are sensitive to scale: features with larger numeric ranges dominate distances. L2 is particularly sensitive because squared terms amplify differences; L1 is less extreme but still additive.
• Always scale/normalize features (standardization, min-max, or domain-specific scaling) before clustering. Consider using feature weighting if some dimensions are more important.
• If using cosine similarity for direction-focused clusters (scale-invariant), neither L1 nor L2 is appropriate without preprocessing.

Practical note

• Implementation: scikit-learn’s KMeans uses L2 and means. For L1 objectives, use sklearn-extra’s KMedoids or implement k-medians; convergence and computational costs differ (medoid updates can be O(n^2) per step unless optimized).

Brief overview:

• Random initialization: choose k points uniformly at random from data. Simple but often yields poor starting centroids that lead to suboptimal clusters or slow convergence.
• k-means++: chooses the first centroid uniformly, then samples subsequent centroids with probability proportional to squared distance (D^2) from nearest existing centroid. This spreads seeds across the space and dramatically reduces bad starts.
• Domain-informed seeding: initialize centroids using known prototypes, cluster centers from a related dataset, or stratified samples (e.g., class means). Useful when reliable prior knowledge exists.

Why poor initialization hurts:

• K-Means optimizes a non-convex objective; bad seeds can trap it in poor local minima (high within-cluster variance).
• Can produce empty clusters, imbalanced cluster sizes, or require many iterations to converge.
• Sensitive to outliers if they become initial centroids.

Why k-means++ helps:

• The D^2 sampling substantially reduces the probability of very close/duplicate seeds, improving final objective and often reducing iterations.
• Theoretically gives an O(log k)-approximation in expectation versus arbitrary initialization.

Practical recommendations:

• Use k-means++ (default in scikit-learn) for general use.
• Set n_init (number of restarts) to at least 10 for experiments; for production/stable deployments use 20–50 if clustering stability matters and compute allows.
• Fix random_state (seed) for reproducibility across runs and pipelines.
• Preprocess: scale features, remove/clip outliers, and consider PCA for high-dimensional data.
• If you have trusted domain centroids, seed with them and optionally run a few k-means++ restarts to validate.

Elbow method

• How computed: Run K‑Means for a range of k (e.g., 1..10) and plot the within‑cluster sum of squared distances (WCSS or inertia) vs k. Look for the “elbow” point where WCSS reduction slows.
• What it measures: Marginal gain in explained variance / compactness as k increases.
• Practical advantages: Simple, fast, intuitive; easy to compute on large datasets.
• Common failure modes: No clear elbow (smooth curve), high‑dimensional/noisy data where inertia keeps decreasing, clusters of unequal size or non‑spherical shape — leads to misleading elbows. Sensitive to scaling and initialization.

Silhouette score

• How computed: For each point i compute a(i)=avg distance to points in same cluster, b(i)=min avg distance to points in other clusters; silhouette s(i)=(b−a)/max(a,b). Average s(i) over all points for each k; choose k maximizing score.
• What it measures: Combined measure of cohesion (within‑cluster tightness) and separation (distance to nearest other cluster).
• Practical advantages: Interpretable bounded score (−1..1); works without ground truth; per‑sample values help diagnose poor clusters/outliers.
• Common failure modes: Biased toward convex/spherical clusters; sensitive to distance metric; can be misleading when clusters overlap or have varying densities; expensive for very large datasets (O(n^2) naive).

Gap statistic

• How computed: Compute log(WCSS) for the data for each k. Generate B reference datasets from a null distribution (usually uniform within data bounding box or PCA‑aligned), compute average log(WCSS_ref) across B. Gap(k)=E[log(WCSS_ref)]−log(WCSS). Choose smallest k within one standard error of the first k with large gap (or maximize gap).
• What it measures: How much clustering structure improves over random/no‑structure baseline.
• Practical advantages: Principled, accounts for sampling variability and dataset scale; less likely to overfit than inertia alone.
• Common failure modes: Choice of reference distribution matters (can misrepresent structure); computationally expensive (many references); sensitive to outliers and to high dimensionality unless preprocessed.

Practical tips

• Preprocess (scaling, PCA/feature selection) and run multiple initializations.
• Use these methods together + domain knowledge and visualization (t‑SNE/UMAP) rather than relying on a single metric.

Approach summary:
To handle anisotropic (elongated/rotated) clusters, replace isotropic Euclidean distances with Mahalanobis distance using per-cluster covariance estimates, or move to a full Gaussian Mixture Model (GMM) fitted by EM. Mahalanobis K-Means is a lightweight extension: iteratively assign points to clusters by Mahalanobis distance d_k(x) = (x-µ_k)^T Σ_k^{-1} (x-µ_k), then update µ_k and Σ_k (regularized). For richer modeling and soft assignments use full GMM (means, covariances, priors) with EM.

Pseudocode (Mahalanobis K-Means with regularized covariances):

# pseudocode (Python-like)
initialize K means µ_k (k=1..K) by k-means++ or random
for k: Σ_k = I (dxd identity)
for iter in 1..T:
    # Assignment step using Mahalanobis distance
    for each point x_i:
        assign to cluster c = argmin_k ( (x_i-µ_k).T @ inv(Σ_k) @ (x_i-µ_k) )
    # Update step
    for k in 1..K:
        X_k = points assigned to k
        if |X_k| == 0: reinitialize µ_k, Σ_k
        µ_k = mean(X_k)
        Σ_k = cov(X_k) + λ I   # regularize to ensure PD
        # optionally shrink toward global covariance: Σ_k = α Σ_k + (1-α) Σ_global
    if assignments converged: break
return {µ_k, Σ_k}

Key reasoning:

• Mahalanobis accounts for orientation and scale of clusters; per-cluster Σ_k models anisotropy.
• Regularization λ>0 prevents singular Σ_k when |X_k| ≤ d or when points are collinear.
• Shrinking toward a global covariance improves stability when clusters small.

Numerical stability:

• Use Cholesky or SVD for Σ_k^{-1} and log-determinant computations. If Σ_k is near-singular, add λ I (e.g., λ = 1e-6 * trace(Σ_k)/d).
• For high-dim data, reduce dimensionality (PCA retaining >95% variance) before estimating covariances to reduce variance and computational cost.
• Monitor condition number; cap it to avoid unstable inverse.

Complexity:

• Per iteration: assignment cost O(N K d^2) if inverting Σ_k naively; but precompute Σ_k^{-1} (O(K d^3) per update). For moderate d, cost manageable. GMM-EM has similar per-iteration cost but also computes responsibilities (soft assignments) and log-likelihood; number of iterations may differ.

Alternatives & trade-offs:

• Full GMM (full covariances) handles anisotropy naturally with principled likelihood; supports soft clusters and model selection (BIC/AIC). Drawback: slower, sensitive to initialization.
• Constrained covariances (diagonal / tied) reduce params and variance.
• Spectral clustering or DBSCAN if shapes are non-ellipsoidal.

Validation experiments (synthetic):

1. Datasets: generate 2D/10D mixtures with K clusters, vary:
   • Aspect ratio (eigenvalue ratios of Σ_k: 1, 5, 20)
   • Rotation angles uniformly random
   • Cluster overlap (Mahalanobis distance between means)
   • Different cluster sizes
2. Baselines: Euclidean K-Means, Mahalanobis K-Means, GMM (full cov), spectral clustering.
3. Metrics: Adjusted Rand Index (ARI), Silhouette (Mahalanobis-aware), average log-likelihood (for GMM), runtime, convergence iterations.
4. Ablations: test λ values, PCA preprocessing, tied vs per-cluster covariances.
5. Visualization: 2D scatter with ellipses for estimated covariances; plot ARI vs aspect ratio and overlap.

Expected outcome:
Mahalanobis K-Means significantly improves clustering for elongated/rotated ellipsoidal clusters over Euclidean K-Means with modest extra cost; full GMM gives best likelihood and smoother boundaries but at higher runtime and sensitivity to initialization. Regularization and dimensionality reduction are critical for numerical stability in practice.