Unit 14: Machine learning algorithms

I. Foundations of machine learning

Machine learning uses algorithms that infer patterns from data so that a program can predict numerical values, assign categories, or discover structure without every decision rule being explicitly programmed.

• Dataset: A collection of observations; rows usually represent samples and columns represent features.
• Features (X): Measurable input variables, such as house area, customer age, or flower petal length.
• Target (y): The value to predict in supervised learning, such as a price or class label.
• Supervised learning: Learns from labelled examples (X, y).
  • Regression: Predicts continuous quantities, such as £245,000.
  • Classification: Predicts discrete classes, such as "spam" or "not spam".
• Unsupervised learning: Finds patterns in unlabelled feature data X; clustering is a central example.
• Training and testing: A model learns from a training set and is evaluated on unseen test data. This tests generalisation rather than memorisation.
• Preprocessing: Missing values, categorical variables, and feature scales should be handled consistently. Distance-based algorithms particularly require scaling.
• Overfitting: A model fits training noise and performs poorly on new data; excessive tree depth is one cause.
• Underfitting: A model is too simple to represent the underlying pattern; fitting a straight line to strongly curved data is one example.
• Evaluation: Appropriate metrics include mean squared error for regression, accuracy for classification, and silhouette score for clustering.
• Reproducibility: Parameters such as random_state=42 make random splits and model construction repeatable.

II. Linear regression — Predicting continuous values

A. Linear regression

Linear regression models a continuous target as a linear combination of one or more input features.

• Simple model: With one feature, the fitted relationship is:

ŷ = b₀ + b₁x

• ŷ is the predicted target, x is the feature, b₀ is the intercept, and b₁ is the slope.
• A slope of b₁ = 3 means that increasing x by one unit increases the prediction by three units.

• Multiple regression: For p features, the model becomes:

ŷ = b₀ + b₁x₁ + b₂x₂ + ... + bₚxₚ

• xⱼ is feature j, bⱼ is its coefficient, and p is the number of features.

• Fitting principle: Ordinary least squares chooses coefficients that minimise the sum of squared residuals:

SSE = Σ(yᵢ - ŷᵢ)²

• yᵢ is the observed target, ŷᵢ is its prediction, and each residual is yᵢ - ŷᵢ.

• Worked example: If ŷ = 20 + 4x, an item with x = 6 has prediction 20 + 4(6) = 44.
• Python implementation:

from sklearn.linear_model import LinearRegression

model = LinearRegression()
model.fit(X_train, y_train)
predictions = model.predict(X_test)

• fit estimates coefficients from training data; predict applies the fitted equation.

B. Applications and limitations

Linear regression is effective when the target-feature relationship is approximately linear and coefficient interpretation matters.

• Applications: Typical uses include estimating sales from advertising expenditure and predicting energy use from temperature.
• Interpretability: model.coef_ reports slopes, while model.intercept_ reports b₀.
• Evaluation: Mean squared error averages squared prediction errors:

MSE = (1/n)Σ(yᵢ - ŷᵢ)²

• n is the number of evaluated samples; lower MSE indicates smaller errors.
  • Assumptions: Classical inference assumes linearity, independent errors, roughly constant error variance, and limited multicollinearity.
  • Limitations: Outliers can strongly alter the fitted line, while nonlinear relationships require transformed features or another model.

III. K-nearest neighbours — Prediction by local similarity

A. K-nearest neighbours

K-nearest neighbours (KNN) predicts from the k training samples closest to a new observation.

• Distance: Euclidean distance between samples a and b is:

d(a, b) = √Σ(aⱼ - bⱼ)²

• aⱼ and bⱼ are values of feature j; smaller d means greater similarity.

• Classification: The predicted class is the majority class among the k neighbours. With neighbours labelled A, A, B and k = 3, the prediction is A.
• Regression: The prediction is commonly the neighbours’ mean target. Targets 10, 13, 16 produce (10 + 13 + 16) / 3 = 13.
• Choice of k:
  1. Small k: Produces flexible boundaries but is sensitive to noise; k = 1 can memorise training data.
  2. Large k: Produces smoother boundaries but may hide small local patterns.
• Scaling requirement: If income ranges to 100000 but age ranges to 100, income dominates Euclidean distance unless features are standardised.
• Python implementation:

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(n_neighbors=5)
model.fit(X_train, y_train)
predictions = model.predict(X_test)

B. Applications and limitations

KNN suits smaller datasets in which nearby observations are expected to have similar outcomes.

• Applications: Uses include pattern recognition, simple recommendation, and classification from physical measurements.
• Advantages: Training is minimal because KNN stores examples rather than estimating an explicit equation.
• Validation: Values of k should be compared using validation data rather than selected from test-set performance.
• Limitations: Prediction becomes slow as the training set grows because distances must be calculated at prediction time.
• Dimensionality: In many dimensions, points often become similarly distant—the “curse of dimensionality”—reducing the meaning of neighbourhoods.
• Sensitivity: Missing values, irrelevant features, class imbalance, and unscaled measurements can distort results.

IV. Decision trees — Learning hierarchical rules

A. Decision trees

A decision tree repeatedly splits data using feature-based conditions, producing a path from a root node to a prediction at a leaf.

• Structure:
  • Root: Contains the initial dataset.
  • Internal node: Tests a condition such as age <= 30.
  • Branch: Represents an outcome of the test.
  • Leaf: Stores a class or numerical prediction.
• Classification split: A tree seeks purer child nodes. Gini impurity is:

Gini = 1 - Σpᶜ²

• pᶜ is the proportion of samples belonging to class c. Gini is 0 when a node contains only one class.

• Regression split: Splits are often chosen to reduce squared error; a leaf predicts the mean target of samples reaching it.
• Recursive learning: The algorithm evaluates possible feature thresholds, chooses the split with the largest impurity reduction, and repeats on each child.
• Python implementation:

from sklearn.tree import DecisionTreeClassifier

model = DecisionTreeClassifier(max_depth=4, random_state=42)
model.fit(X_train, y_train)
predictions = model.predict(X_test)

B. Applications and limitations

Decision trees provide understandable nonlinear models but need controls to prevent overfitting.

• Applications: Trees support credit-risk screening, fault diagnosis, and rule-based classification involving mixed conditions.
• Interpretability: A path such as income > 30000 followed by debt <= 5000 forms a readable decision rule.
• Nonlinearity: Trees capture interactions without manually adding terms; the effect of one feature may depend on an earlier split.
• Overfitting controls: max_depth, min_samples_split, and min_samples_leaf restrict complexity; pruning removes weak branches.
• Advantages: Feature scaling is usually unnecessary because splits compare individual feature thresholds.
• Limitations: Small data changes can produce a substantially different tree, and axis-aligned splits may approximate smooth boundaries inefficiently.

V. Random forests — Combining many decision trees

A. Random forests

A random forest is an ensemble that trains many diverse decision trees and combines their predictions.

• Bootstrap sampling: Each tree trains on a random sample drawn with replacement from the training set; some observations may occur repeatedly.
• Feature randomness: At each split, only a random subset of features is considered, preventing all trees from repeatedly choosing the same dominant feature.
• Aggregation:
  1. Classification: Trees vote, and the class with the most votes is predicted.
  2. Regression: Tree predictions are averaged.
• Error reduction: Individual trees have high variance, but averaging many partly independent trees produces a more stable model.
• Python implementation:

from sklearn.ensemble import RandomForestClassifier

model = RandomForestClassifier(
    n_estimators=200, max_depth=8, random_state=42
)
model.fit(X_train, y_train)
predictions = model.predict(X_test)

• n_estimators=200 creates 200 trees; increasing this generally improves stability but costs computation.

B. Applications and limitations

Random forests are strong general-purpose predictors for structured, tabular data.

• Applications: Common uses include fraud detection, customer churn prediction, and classification from many interacting measurements.
• Advantages over one tree: The forest is less sensitive to a single noisy sample and usually generalises better.
• Out-of-bag evaluation: Samples omitted from a tree’s bootstrap sample can evaluate that tree, providing an internal performance estimate.
• Feature importance: Importance scores can indicate useful variables, although correlated features and impurity-based measures may make interpretation misleading.
• Limitations: Hundreds of trees consume more memory and prediction time than one tree.
• Interpretability: The ensemble cannot usually be expressed as a small set of readable rules, even though each component is a decision tree.

VI. K-means clustering — Discovering groups without labels

A. K-means clustering

K-means partitions unlabelled observations into k clusters by assigning each sample to the nearest cluster centre, or centroid.

• Objective: The algorithm minimises within-cluster squared distance:

J = Σᵢ ||xᵢ - μc(i)||²

• J is the clustering cost, xᵢ is sample i, c(i) is its assigned cluster, and μc(i) is that cluster’s centroid.

• Iterative process:
  1. Initialise k centroids, commonly using the k-means++ method.
  2. Assign every sample to its nearest centroid.
  3. Replace each centroid with the mean of its assigned samples.
  4. Repeat assignment and updating until assignments stabilise or centroid movement becomes sufficiently small.
• Centroid example: Points (2, 4), (4, 6), and (6, 8) have centroid ((2+4+6)/3, (4+6+8)/3) = (4, 6).
• Python implementation:

from sklearn.cluster import KMeans

model = KMeans(n_clusters=3, random_state=42, n_init=10)
labels = model.fit_predict(X_scaled)
centres = model.cluster_centers_

• labels gives each sample’s cluster index; centres contains the centroid coordinates.

B. Applications and limitations

K-means is useful when compact, approximately spherical groups can be represented by their means.

• Applications: It supports customer segmentation, image colour compression, and grouping documents represented by numeric features.
• Choosing k: The elbow method plots within-cluster cost against k; a bend suggests where extra clusters yield diminishing improvement.
• Evaluation: Silhouette score compares cohesion with separation and ranges from -1 to 1; larger values generally indicate better-defined clusters.
• Scaling: Standardisation is important because a large-scale feature otherwise dominates centroid distances.
• Initialisation: Different starting centroids can produce different local solutions; multiple initialisations reduce this risk.
• Limitations: The user must select k, outliers can pull centroids, and K-means performs poorly on elongated, overlapping, unequal-density, or non-convex clusters.