Unit 14: Machine learning algorithms - Subjective Questions

Linear regression is a supervised learning algorithm used to predict a continuous dependent variable from one or more independent variables.

For simple linear regression, the model is:

• Dependent variable (): The continuous value to be predicted.
• Independent variable (): The input feature used to make the prediction.
• Intercept (): The expected value of when .
• Slope (): The expected change in for a one-unit increase in .
• Error term (): The unexplained difference between an observed value and the value predicted by the model.

With several input features, the method is called multiple linear regression.

For observations , the predicted value is:

The least-squares method minimizes the sum of squared errors:

Differentiating with respect to and , setting both derivatives to zero, and solving the resulting normal equations gives:

Therefore, the fitted regression equation is:

The formulas select the line for which the total squared vertical distance between observed and predicted values is minimum.

The major assumptions are:

• Linearity: The relationship between features and the target is approximately linear.
• Independence: Observations and their errors are independent.
• Homoscedasticity: The variance of residuals remains approximately constant.
• Normality of residuals: Residuals are approximately normally distributed, particularly when statistical inference is required.
• Low multicollinearity: Independent variables should not be excessively correlated with one another.

Common evaluation measures include:

• Mean Absolute Error:
• Mean Squared Error:
• Root Mean Squared Error:
• Coefficient of determination:

Lower error values and an value closer to generally indicate a better fit, although validation data should be used to check generalization.

A typical scikit-learn workflow is:

1. Prepare data: Store input features in X and the continuous target in y.
2. Split the data: Use train_test_split to produce training and test sets.
3. Create the model: Instantiate LinearRegression().
4. Train it: Call model.fit(X_train, y_train).
5. Predict: Call model.predict(X_test).
6. Evaluate: Calculate measures such as MAE, MSE, RMSE, and .
7. Interpret: Examine model.coef_ and model.intercept_.

Example outline:

model = LinearRegression()

model.fit(X_train, y_train)

predictions = model.predict(X_test)

The test set must not be used during training because it is intended to estimate performance on unseen observations.

K-nearest neighbours (KNN) is a supervised, instance-based learning algorithm. It does not build an explicit mathematical model during training; instead, it stores the training examples.

To classify a new observation, KNN:

1. Calculates its distance from the training observations.
2. Selects the observations having the smallest distances.
3. Finds the class labels of these neighbours.
4. Assigns the class occurring most frequently among them.

For example, if and three neighbours belong to class A while two belong to class B, the new observation is assigned to class A.

An odd value of is often selected for binary classification to reduce ties. Distance-weighted KNN may give closer neighbours more influence than distant neighbours.

KNN predictions depend directly on distances between observations. A common measure is Euclidean distance:

Other choices include Manhattan and Minkowski distance.

• Feature scaling: A feature with large numeric values can dominate the distance. Standardization or normalization places features on comparable scales.
• Small : Produces flexible decision boundaries but is sensitive to noise and may overfit.
• Large : Produces smoother boundaries but may underfit and favour the majority class.
• Choosing : Test candidate values using a validation set or cross-validation and select the value with the best validation performance.

Scaling parameters must be learned from the training set and then applied to both training and test data to avoid data leakage.

Both methods locate the nearest training observations, but they combine their targets differently.

• KNN classification: Predicts a categorical label using majority voting or a distance-weighted vote.
• KNN regression: Predicts a continuous value, usually by taking the mean of the neighbours' target values:

A weighted regression prediction can be calculated as:

where a common choice is .

Classification may be evaluated using accuracy, precision, recall, or F1-score, whereas regression generally uses MAE, MSE, RMSE, or .

Advantages:

• Simple to understand and implement.
• Makes few assumptions about the underlying data distribution.
• Can model nonlinear decision boundaries.
• Supports both classification and regression.
• Requires little conventional training time.

Limitations:

• Prediction can be slow because distances to many training records must be computed.
• It may require substantial memory to store the training data.
• It is sensitive to feature scales, irrelevant features, noise, and outliers.
• It can be biased toward the majority class.
• Its performance depends strongly on and the distance measure.

In high-dimensional spaces, distances between points tend to become less distinctive. This curse of dimensionality makes identifying meaningful neighbours difficult. Feature selection, dimensionality reduction, and appropriate scaling can reduce this problem.

A decision tree repeatedly splits data into increasingly pure subsets. Each internal node tests a feature, each branch represents an outcome, and each leaf gives a predicted class.

Two common impurity measures are:

• Gini impurity:
• Entropy:

Here, is the proportion of records belonging to class . An entirely pure node has impurity zero.

For entropy, the benefit of a split is measured by information gain:

The algorithm generally selects the split with the largest impurity reduction, applies the same process recursively, and stops when a stopping rule is reached.

A decision tree overfits when it becomes so complex that it learns noise and unusual details in the training set. Such a tree may achieve very high training accuracy but poor test accuracy.

Pre-pruning stops growth before the tree becomes excessively complex. Common restrictions include:

• Maximum tree depth (max_depth).
• Minimum samples required to split a node (min_samples_split).
• Minimum samples allowed in a leaf (min_samples_leaf).
• Maximum number of leaf nodes.
• Minimum impurity reduction required for a split.

Post-pruning first grows a larger tree and then removes branches that provide little predictive benefit. Cost-complexity pruning balances fit against tree size.

Cross-validation should be used to select pruning parameters. Pruning normally reduces variance and improves generalization, although excessive pruning can cause underfitting.

To interpret a prediction, begin at the root and follow the branch selected by each feature test until a leaf is reached. The complete path forms a readable rule, such as if age is at most 30 and income exceeds a threshold, predict class A.

Advantages:

• Easy to visualize and explain.
• Models nonlinear relationships and feature interactions.
• Requires little feature scaling.
• Works with classification and regression problems.
• Performs implicit feature selection through its splits.

Disadvantages:

• Deep trees are prone to overfitting.
• Small changes in data may produce a very different tree.
• Greedy split selection does not guarantee a globally optimal tree.
• A tree can be biased toward features offering many possible splits.
• Axis-aligned splits may require a complex tree for some decision boundaries.

Interpretability decreases as the tree becomes larger.

A regression tree predicts a continuous target. For each candidate feature and split point, it divides the records into child nodes and measures the resulting prediction error.

If the prediction in a node is its mean target value, the node's squared error is:

The tree selects a split that produces the greatest reduction in total error:

Splitting continues recursively until a stopping condition is satisfied. For a new observation, feature tests are followed from the root to a leaf. The prediction is usually the mean target value of the training observations in that leaf.

Unlike linear regression, a regression tree produces piecewise-constant predictions and can naturally model nonlinear relationships.

A random forest is an ensemble learning algorithm that combines many decision trees.

Each tree is usually trained as follows:

1. Draw a bootstrap sample from the training data by sampling records with replacement.
2. At each node, consider only a random subset of features when searching for the best split.
3. Grow the tree, usually without requiring it to match the structure of other trees.

The individual predictions are combined:

• For classification, the forest uses majority voting or averaged class probabilities.
• For regression, it averages the tree predictions:

Bootstrap sampling and random feature selection make the trees less correlated. Combining these diverse trees reduces variance and usually improves generalization.

Decision tree:

• Uses one tree to make predictions.
• Is easy to visualize and interpret.
• Trains and predicts relatively quickly.
• Has high variance and can overfit.
• May change substantially following a small change in training data.

Random forest:

• Combines predictions from many randomized trees.
• Usually achieves better test performance.
• Is more stable and resistant to overfitting than one unrestricted tree.
• Requires more computation and memory.
• Is harder to explain as a complete model.

A single tree is appropriate when transparent decision rules are especially important. A random forest is often preferred when stronger predictive performance and robustness are more important than direct model interpretation.

Bootstrap aggregation, or bagging, trains each tree on a sample drawn with replacement from the training set. Some records may appear several times in a tree's sample, while others are omitted.

Random feature selection allows only a subset of features to be considered at each split. It prevents a few dominant features from making all trees too similar and therefore increases diversity.

Records omitted from a tree's bootstrap sample are called its out-of-bag (OOB) observations. Each training record can be predicted using only trees for which that record was out of bag. Comparing these predictions with the true targets gives the OOB score or OOB error.

OOB evaluation provides an internal estimate of generalization performance without requiring a separate validation set, although a final untouched test set is still valuable.

Important hyperparameters include:

• n_estimators: Number of trees; more trees generally improve stability but increase computation.
• max_features: Number or proportion of features considered at each split.
• max_depth: Maximum depth of each tree.
• min_samples_split: Minimum records needed to split a node.
• min_samples_leaf: Minimum records required in a leaf.
• bootstrap: Whether bootstrap samples are used.
• class_weight: Weights used to address class imbalance.

Feature importance can be estimated with:

• Impurity-based importance: Adds the weighted impurity reductions produced by each feature. It is fast but may favour continuous or high-cardinality features.
• Permutation importance: Shuffles one feature and measures the decline in predictive performance. It is often easier to interpret but can be affected by correlated features.

Hyperparameters should be tuned using cross-validation rather than the final test set.

K-means is an unsupervised algorithm that divides observations into clusters. It attempts to minimize the within-cluster sum of squares:

where is cluster and is its centroid.

The algorithm performs these steps:

1. Select initial centroids.
2. Assignment step: Assign every observation to its nearest centroid.
3. Update step: Recalculate each centroid as the mean of the observations assigned to its cluster.
4. Repeat assignment and update steps until assignments stop changing, centroid movement is sufficiently small, or a maximum number of iterations is reached.

K-means converges to a local minimum, so different initial centroids can produce different results.

• Elbow method: Run K-means for several values of and plot inertia against . A possible choice is the bend after which additional clusters yield relatively small reductions in inertia.
• Silhouette score: For observation , let be its average distance within its cluster and its smallest average distance to another cluster. Then:

A score near suggests a well-separated observation, a score near suggests overlap, and a negative score may indicate poor assignment.

• Feature scaling: Since K-means uses distances, high-magnitude features can dominate. Standardization is commonly applied.
• Initialization: Poor initial centroids can produce weak local solutions. K-means++ spreads initial centroids apart, and multiple initial runs increase the chance of finding a better solution.

Statistical measures should be considered alongside domain knowledge when selecting .

Assignment step: Compare each observation with the initial centroids and .

• , , and are closer to , so .
• , , and are closer to , so .

Update step: Calculate the mean of each cluster:

The updated centroids are therefore and . Repeating the assignment step does not change the clusters, so the algorithm has converged for these initial centroids.

The final within-cluster sum of squares is:

• Linear regression: A supervised method for predicting continuous values. It is appropriate when relationships are reasonably linear and coefficient interpretation is useful.
• KNN: A supervised, distance-based method supporting both classification and regression. It is useful for smaller scaled datasets with meaningful local neighbourhoods.
• Decision tree: A supervised method supporting classification and regression. It is suitable when nonlinear rules, interactions, and model interpretability are important.
• Random forest: A supervised ensemble of decision trees supporting classification and regression. It is useful for robust prediction on complex tabular data.
• K-means: An unsupervised clustering method. It groups unlabelled observations into clusters based on distance from centroids.

The first four methods learn from labelled targets, whereas K-means does not use target labels. Algorithm selection should consider target type, data size, feature scaling, interpretability, computational cost, expected relationship shape, and validation performance.