Machine Learning Landscape & Unsupervised Clustering

13.1 Machine Learning Landscape & Project Workflow

Machine learning models operating on big data need a structured lifecycle and clear operational definitions. In industry projects, data scientists and engineers build end-to-end pipelines that turn raw business tasks into evaluated predictive models.

13.1.1 Core Definitions & Learning Paradigms

Machine learning differs from traditional software engineering in the direction of the pipeline:

The broader landscape spans three major paradigms:

1. Supervised Learning: Algorithms learn from labeled datasets containing explicit input–output pairs.

• Example: Predicting whether a person is labeled “fat” or “thin” from millions of past samples with weight \(x \in \mathbb{R}\) and height \(y \in \mathbb{R}\) (and a binary outcome label).
• Supervised learning splits into two sub-problems:
• Classification: Predict a target \(y\) from a small, finite set of discrete class labels (e.g., movie ratings as categories \(\{1,2,3,4,5\}\), or low / medium / high popularity).
• Regression: Predict a continuous target \(y \in \mathbb{R}\) from an effectively infinite continuous set (e.g., exact scores such as \(3.23\), \(5.27\), or \(9.98\)).

1. Unsupervised Learning: Algorithms operate on unlabeled datasets where ground-truth labels are absent. The goal is to discover structural patterns or groupings in the data space.

• Example: Segmenting the population of India on demographic features. The algorithm forms clusters by feature similarity.
• Key distinction: The algorithm may find that there are \(k\) groups, but it cannot name them. A domain expert must interpret clusters as super senior citizens, senior citizens, working population, teenagers, or toddlers.

1. Reinforcement Learning: Algorithms learn without a static labeled batch. An agent interacts with an environment by trial and error and receives numeric rewards or penalties.

• Analogy (professor): Learning to ride a bicycle. Falling is a heavy penalty; moving forward a few inches is a reward. Over time the agent finds an action sequence that maximizes cumulative reward.
• Where the analogy breaks: bicycle balance is continuous and physical; digital RL often uses discrete actions and designer-chosen reward scales.

13.1.2 Artificial Intelligence vs. Machine Learning vs. Deep Learning

Artificial Intelligence (AI) is the overarching domain: any system that shows intelligent behavior. Machine Learning (ML) is a subset of AI that uses statistical algorithms to learn patterns from data. Deep Learning (DL) is a further subset of ML that uses multi-layered artificial neural networks.

Visual intuition: picture three nested circles. The outer circle is AI. Inside it sits ML. Inside ML sits DL. Traditional algorithms such as Decision Trees, Support Vector Machines, and K-Means live in the ML ring but outside the DL ring.

• Non-human-brain approach (traditional ML): Distinct mathematical algorithms tailored to engineered feature sets.
• Human-brain approach (deep learning): Layers of artificial neurons that learn hierarchical feature representations automatically.
• Explainability dilemma: Business stakeholders often demand why a prediction was made. Traditional ML models usually offer clearer mathematical interpretability. Deep learning models often behave as opaque black boxes: strong predictive performance, weaker pathway explanation.

13.1.3 End-to-End Machine Learning Project Phases

Every real-world machine learning initiative follows five core operational phases:

1. Data Gathering: Collect raw feeds from distributed logs, databases, real-time streams, or third-party APIs.
2. Data Cleaning: Handle missing values, filter noise, remove corrupt records, and normalize formats.
3. Feature Engineering: Extract domain attributes, transform raw variables, and build feature vectors.
4. Model Execution: Train candidate algorithms on the processed data.
5. Model Evaluation: Quantify performance with objective metrics before deployment.

Real-world & domain connection: In freelancing proposals and enterprise delivery, inexperienced teams often code models while omitting the evaluation framework. A proposal without predefined metrics is technically incomplete. The same discipline appears in industrial tomato sorting: accuracy and false-reject rate must be agreed before comparing sorter versions.

13.1.4 Student Questions and Answers

13.2 Clustering Fundamentals & Data Clusterability (Hopkins Statistic)

Clustering (grouping similar points without labels) is an unsupervised technique that partitions observations by pairwise feature similarity so that intra-cluster similarity is high and inter-cluster similarity is low. Reference texts state the same objective: maximize inter-cluster distance and minimize intra-cluster distance.

13.2.1 Spatial Visualization & Feature Dimensions

Data with two features can be drawn on a 2D plane (e.g., weight on the horizontal axis, height on the vertical axis). A third feature such as age needs a 3D view. With four, five, or hundreds of dimensions, visual inspection fails. Distance geometry still works in any \(d\)-dimensional space \(\mathbb{R}^d\): each observation is a vector \(\mathbf{x} = (x_1, \dots, x_d)\).

Univariate data has a single scalar feature per observation (e.g., only heights across a region). Clustering still applies on the real line using absolute difference as distance.

13.2.2 Partitioning vs. Hierarchical Clustering

Clustering methods fall into two structural paradigms (also reflected in textbook taxonomies of partitional vs hierarchical methods):

Consider classifying living organisms on Earth:

• Partitioning: Strict buckets — dogs in cluster 1, cats in 2, humans in 3, birds in 4, insects in 5, microbes in 6.
• Hierarchical: Dogs and cats merge into an “Animals” super-cluster; birds and insects into “Flying Organisms”; an extraterrestrial viewer might treat all Earth life as one top-level cluster.

When to pick which: choose partitioning when you need a fixed number of non-overlapping segments; choose hierarchical when you need multi-resolution structure or do not want to commit to \(k\) up front.

13.2.3 Data Clusterability & The Hopkins Statistic

Before running any clustering algorithm, evaluate whether the dataset has true underlying clusters or is only uniformly distributed random noise.

The Hopkins Statistic \(H\) is a statistical test of clustering tendency (whether data is cluster-worthy).

Mathematical Formulation of Hopkins Statistic

In words: \(H\) is the total nearest-neighbor distance of synthetic points divided by that total plus the total nearest-neighbor distance of sampled real points. Because the numerator is part of the denominator, \(H \in [0, 1]\).

Interpretation Thresholds

• \(H \approx 0.5\) (unclusterable / uniform): Real and synthetic nearest-neighbor distance sums are comparable (\(\sum V_d \approx \sum U_d\)). Example: \(\frac{100}{100+100} = 0.5\). Do not treat the data as cluster-worthy.
• \(H > 0.5\) (cluster-worthy): Real points sit in tight groups, so \(\sum U_d\) is small while random synthetic points land far from real mass, making \(\sum V_d\) large. Example: \(\sum V_d = 100\), \(\sum U_d = 5\) gives

\[ H = \frac{100}{100+5} \approx 0.952. \] Values significantly above \(0.5\) support clustering.

• \(H < 0.5\) (regular / grid): Points are more regularly spaced than uniform random noise (lattice-like structure).

Visual intuition: Imagine a scatter plot with two tight blobs. Sampled real points almost always find a neighbor inside their blob (short \(U_d\)). Uniform synthetic darts often land in empty space and must travel far to the nearest real point (long \(V_d\)). The ratio \(H\) then rises toward 1. On a uniform fog of points, both dart types travel similar distances and \(H\) hugs \(0.5\).

Real-world & domain connection: Marketing teams segmenting India’s demographics, or e-commerce teams clustering clickstreams, must confirm clusterability first. Otherwise “segments” are artifacts and campaign targeting wastes budget.

13.3 Partitioning Clustering: K-Means Algorithm & Variants

K-Means is a centroid-based partitioning algorithm: it divides a dataset into \(k\) predefined, non-overlapping clusters by alternating assignment to the nearest center and recomputing each center as a mean.

13.3.1 Distance Metrics: Euclidean vs. Manhattan

Evaluating proximity needs a distance between vectors \(\mathbf{x}_1 = (x_{11}, x_{12})\) and \(\mathbf{x}_2 = (x_{21}, x_{22})\).

13.3.2 Step-by-Step K-Means Algorithm Workflow

Use the procedural spine for this algorithm.

Complexity & cost: with \(n\) points, \(k\) clusters, \(I\) iterations, and dimension \(d\), time is on the order of \(O(n \cdot k \cdot I \cdot d)\) — linear in \(n\) for fixed \(k, I, d\). Space is about \(O(n \cdot d)\). Cost blows up when \(k\) or \(I\) is large, or when poor seeds force many wasted iterations.

13.3.3 Comprehensive Worked Computation: 1D Dataset Walkthrough

Trial 1: Seeds \(c_1 = 2\), \(c_2 = 4\), \(c_3 = 13\)

Iteration 1 — Assignment

Clusters: \[ S_1 = \{1,2\},\quad S_2 = \{4,5\},\quad S_3 = \{10,11,13,14,15,19,20,22\}. \]

Iteration 1 — Centroid update

\[ \begin{aligned} c_1 &= \frac{1+2}{2} = 1.5, \\ c_2 &= \frac{4+5}{2} = 4.5, \\ c_3 &= \frac{10+11+13+14+15+19+20+22}{8} = \frac{104}{8} = 13.0. \end{aligned} \]

Notation note: A verbal walkthrough sometimes cited a later mid-run center near \(16.3\). That value is not the mean of this Trial-1 \(S_3\). Algebraically, \(\frac{104}{8} = 13\). The figure \(16.2 \approx 16.3\) appears correctly as a Trial-2 centroid below.

Iteration 2 — Reassignment with \(c = (1.5, 4.5, 13.0)\)

Boundary checks:

• Point \(10\): \(|10-4.5|=5.5\), \(|10-13|=3\) → stays in \(C_3\).
• Point \(11\): \(|11-4.5|=6.5\), \(|11-13|=2\) → stays in \(C_3\).
• Points \(1,2\) stay in \(C_1\); \(4,5\) stay in \(C_2\).

No point moves. Trial 1 has already converged to the local solution \[ S_1=\{1,2\},\; S_2=\{4,5\},\; S_3=\{10,11,13,14,15,19,20,22\} \] with centroids \(1.5\), \(4.5\), \(13.0\).

Sense-check: two left seeds placed close together produced two tiny left clusters and one oversized right cluster — a classic poor-seed local minimum.

Trial 2: Seeds \(c_1 = 6\), \(c_2 = 19\), \(c_3 = 22\)

Spreading seeds across the domain reaches a balanced partition in four iterations.

Iteration 1 assignment (summary): \[ S_1=\{1,2,4,5,10,11\},\; S_2=\{13,14,15,19,20\},\; S_3=\{22\}. \]

Iteration 1 update: \[ \begin{aligned} c_1 &= \frac{33}{6} = 5.5, \\ c_2 &= \frac{13+14+15+19+20}{5} = \frac{81}{5} = 16.2 \approx 16.3, \\ c_3 &= 22. \end{aligned} \]

Iteration 2: With centers \(5.5\), \(16.2\), \(22\), \[ S_1=\{1,2,4,5,10\},\; S_2=\{11,13,14,15,19\},\; S_3=\{20,22\} \] and updated means \(c_1=4.4\), \(c_2=14.4\), \(c_3=21\).

Iteration 3:

• \(10\) moves to \(C_2\) because \(|10-14.4|=4.4 < |10-4.4|=5.6\).
• \(19\) moves to \(C_3\) because \(|19-21|=2 < |19-14.4|=4.6\).

\[ S_1=\{1,2,4,5\},\; S_2=\{10,11,13,14,15\},\; S_3=\{19,20,22\} \] with \[ c_1=3,\quad c_2=12.6,\quad c_3=\frac{61}{3}\approx 20.33. \]

Iteration 4: Reassignment leaves every point unchanged → convergence.

Final clusters (Trial 2): \[ S_1=\{1,2,4,5\},\; S_2=\{10,11,13,14,15\},\; S_3=\{19,20,22\}. \]

Trial 3 & Sensitivity to Random Initialization

• Trial 2 seeds \((6, 19, 22)\): Spread seeds → clean convergence in 4 iterations to the balanced partition above.
• Trial 3 seeds \((19, 20, 21)\): Corner seeds → redundant iterations and local-minimum risk.

Real-world production pattern: commercial K-Means runs multiple random restarts (\(n_{\mathrm{init}} = 100\)). For each restart compute Sum of Squared Errors (SSE / inertia): \[ \mathrm{SSE} = \sum_{j=1}^{k} \sum_{x \in S_j} (x - c_j)^2. \] Keep the restart with the lowest SSE.

Visual intuition: On a number line, centroids are movable pins. Assignment snaps each tick mark to the nearest pin; update slides each pin to the average of its ticks. Pins stop when the snap-and-slide loop no longer changes membership.

13.3.4 K-Medoids / K-Median Variant

Standard K-Means centroids (e.g., \(2.3\) or \(17.17\)) need not be actual observations. Means are also sensitive to extreme outliers.

Textbook framing: a medoid is like a mean but must be a member of the data; the algorithm iteratively swaps exemplars to reduce total dissimilarity. Use medoids for graphs/non-metric spaces and when interpretability requires “this customer is the prototype.”

13.4 Hierarchical Clustering & Linkage Criteria

Hierarchical clustering builds a tree of nested clusters without requiring \(k\) before the run. Results are typically more consistent across runs than random-seed K-Means because there is no random centroid initialization for a fixed linkage rule.

13.4.1 Agglomerative vs. Divisive Approaches

When to pick which: agglomerative is the common default for teaching and many libraries; divisive is conceptually useful when you start from one population and need successive splits.

13.4.2 Linkage Criteria Metrics

The distance between clusters \(A\) and \(B\) depends on the linkage criterion:

Comparison:

When to pick which: single linkage for elongated / chained structure; complete linkage when you want tight balls; average or centroid when you want a middle ground tied to mean geometry.

13.4.3 Dendrogram Construction & Cluster Extraction

A dendrogram is the tree diagram of agglomerative merge history: the horizontal axis lists points (or leaf labels); the vertical axis is the linkage distance at which merges occurred. Drawing a horizontal cut at height \(h\) yields as many clusters as vertical branches the cut intersects.

Visual intuition: The dendrogram looks like a sports tournament bracket turned upward. Low horizontal bars are early “easy” merges; the tall final bar is the hardest join. Your cut height is the similarity threshold you are willing to accept.

Real-world & domain connection: News aggregators nest stories into topics and subtopics (sports → basketball → a single game). Hierarchical clustering matches that multi-resolution taxonomy better than a single flat \(k\).

13.5 Comparative Analysis & Big Data Execution in Apache Spark (MLlib)

13.5.1 K-Means vs. Hierarchical Clustering Comparison

Textbook alignment: hierarchical methods generally produce consistent trees; K-Means is simple and efficient with linear growth in \(n\), but needs \(k\) and can depend on random starts. Neither replaces a Hopkins-style clusterability check.

13.5.2 Horizontal Scalability: Scikit-Learn vs. Apache Spark MLlib

In architectures that meet the 3 V’s (Volume, Velocity, Variety), framework choice sets the scalability ceiling.

Spark MLlib unifies batch processing, Spark Streaming, and ML pipelines under a standard API pattern:

1. Load a distributed dataset into a Spark DataFrame.
2. Transform raw columns with VectorAssembler into feature vectors.
3. Instantiate and fit an estimator such as KMeans().
4. Evaluate cluster quality with distributed metrics (e.g., SilhouetteEvaluator).

DataFrame  →  VectorAssembler  →  features
features   →  KMeans(k=...).fit(...)  →  model
model      →  SilhouetteEvaluator  →  score

Visual intuition: Scikit-Learn is one kitchen with many burners. Spark MLlib is a chain of kitchens sharing the same recipe card (KMeans) while each cooks a partition of the ingredients (data shards). Horizontal scale adds kitchens; vertical scale only upgrades one kitchen’s burners.

Real-world & domain connection: Telemetry and web-scale click logs that outgrow laptop RAM use Spark MLlib K-Means for customer or session segmentation. Hierarchical clustering remains a lab / mid-size tool for taxonomy discovery.

Exam Guidance Summary

• Model Evaluation Strategy: Always finalize evaluation criteria before executing algorithms. Workflow questions expect you to state why metrics must precede model training — never judge models by developer mood.
• Hopkins Statistic Formula: Memorize

\[ H = \frac{\sum V_d}{\sum V_d + \sum U_d}. \] Exams may give \(\sum V_d\) and \(\sum U_d\) and ask whether data is cluster-worthy. Rule: \(H > 0.5\) → clusterable; \(H \le 0.5\) → do not cluster (uniform/random or non-worthy under the lecture rule).

• K-Means Numerical Walkthrough: Expect multi-mark 1D or 2D calculations. Show every distance, assignment, and mean update. State convergence when zero points move. Watch seed sensitivity and report SSE when comparing restarts.
• Linkage Metrics: Define and compute Single (min), Complete (max), Average, and Centroid linkage. Be ready to cut a dendrogram for a stated \(k\).
• K-Means vs. Hierarchical Trade-offs: Contrast complexity (\(O(n\cdot k\cdot I)\) vs \(O(n^2\log n)\)/\(O(n^3)\)), whether \(k\) is required up front, determinism, geometry assumptions, and big-data fitness (Spark MLlib K-Means vs hierarchical on one node).

Key Industry Applications

• Tomato Quality Classification: Industrial agricultural sorting systems use supervised feature vectors (size, color intensity, mass) to automate high-quality vs. bad-quality tomato classification — the lecture’s running Mitchell \(T\)/\(E\)/\(P\) example.
• Demographic Population Segmentation: Enterprise marketing platforms use unsupervised clustering to segment large populations into demographic tiers for targeted communication; domain experts name the anonymous clusters afterward.
• Content Recommendation Engines: Digital news platforms and media apps (e.g., Android minus-one news screens) use reinforcement learning to recommend trending articles (World Cup, politics), learning from positive clicks and explicit deletion penalties.
• E-Commerce Customer Segmentation: Sites such as Amazon cluster user clickstreams (electronics, apparel, home decor) to target promotional offers — a classic partitioning use case once Hopkins confirms structure.
• Multiple Random Restarts (\(n_{\mathrm{init}}\)): Production ML systems set \(n_{\mathrm{init}} = 100\) for K-Means, keep the model with lowest total SSE / inertia, and avoid shipping a poor local minimum from one unlucky seed.
• Distributed Clustering with Apache Spark MLlib: Large-scale telemetry and web-scale log pipelines deploy Spark MLlib K-Means to scale horizontally when datasets exceed single-node RAM; Scikit-Learn remains the single-node prototyping tool.