Data Mining

Answer: (iii) Naive Bayes

Naive Bayes is explicitly probabilistic: it applies Bayes' theorem, $P(C \mid X) = \dfrac{P(X \mid C)\,P(C)}{P(X)}$, assuming naively that features are conditionally independent given the class, and predicts the class with the maximum posterior probability. Its output can be read directly as class probabilities.

A decision tree chooses splits by information gain or Gini impurity — a deterministic, rule-based model — and an SVM finds a maximum-margin hyperplane by convex optimisation, not by a probability model. KNN does give a rough frequency estimate through neighbour voting, but it has no underlying probabilistic model; the unambiguously probabilistic classifier here is Naive Bayes.

Answer: (ii) Classification

SVM is a supervised learning algorithm used mainly for classification. It finds the hyperplane $w \cdot x + b = 0$ that separates the two classes with the maximum margin; prediction is then just the sign of $w \cdot x + b$. SVM can be extended to regression (SVR) using an ε-insensitive loss, but classification is its primary and standard application.

Clustering groups unlabelled data (unsupervised) and association rule mining discovers co-occurring items — neither is what SVM does. Since the question asks for the main use, regression (i) is not the best answer even though SVR exists.

Answer: (i) The attributes are correlated

An ordinary decision tree can only make axis-parallel splits of the form $A \le v$ on a single attribute. An oblique tree instead splits a node on a linear combination of several attributes, e.g. $w_1A_1 + w_2A_2 + \dots + w_nA_n \le c$, which produces an oblique (non-axis-parallel) decision boundary in attribute space.

Such a split is useful precisely when the attributes are correlated, because the classes then cannot be separated cleanly by one axis-aligned cut; a linear combination captures the joint effect. If attributes are independent, a simple single-attribute split already works. Two attributes or all-categorical attributes are handled perfectly well by ordinary trees, so (iii) and (iv) are not the reason for using an oblique tree.

Answer: (iii) Classification, Clustering

Predictive data mining builds a model that predicts a target (labelled) attribute for new or unseen cases, and classification does exactly that: it learns a model from labelled training data and assigns class labels to future records. Descriptive data mining discovers patterns with no target variable to predict; clustering groups objects purely by their inherent similarity in unlabelled data, so it is descriptive.

Association rule mining (e.g. Apriori over market-basket data) is also a descriptive technique, not a predictive one, so options (i) and (ii) are wrong; option (iv) simply reverses the two roles.

Answer: (i) Supervised, Unsupervised

Classification learns from data in which the class label of every example is already known — a 'supervisor' supplies the correct output that the model is trained to reproduce — so it is supervised learning. Clustering receives unlabelled data and must discover the group structure on its own, with no target output to guide it, so it is unsupervised learning.

Option (ii) swaps the two. Options (iii) and (iv) are wrong because machine learning is the umbrella category that contains both supervised and unsupervised learning, not the counterpart of supervised learning.

Answer: (i) supervised learning

Predicting the magnitude (a continuous numeric value) of the next earthquake from seismic-activity data is a prediction/regression task. Because we train a model using historical data that already includes known outcomes (earthquake magnitudes) and then predict a numeric value for new data, it is a supervised learning problem.

Why the others are wrong:

• (ii) unsupervised learning — no hidden structure/labels are being found; we are predicting a specific numeric value from labelled historical examples.
• (iii) serration — a typo/nonsense option (no such learning category).
• (iv) dimensionality reduction — that is a preprocessing/feature-compression technique (like PCA), not the task of predicting a magnitude.

Hence predicting the magnitude of the next earthquake is an example of supervised learning.

Answer: Supervised vs Unsupervised Classification

• Supervised classification: class labels are known in advance. A set of data objects with known class labels (the training set) is used to build a classification model; this model is then applied to assign class labels to new/unseen objects. In other words, the model is trained on pre-labelled data and the classes are predefined categories.

• Unsupervised classification: the class label is unknown. It attempts to discover the natural classes/clusters directly from the data itself (using clustering); the number of classes and their boundaries are not known in advance, and are derived by the algorithm (e.g., k-Means clustering, hierarchical clustering).

Known labels ──▶ Supervised classification ──▶ model ──▶ assign classes to new data
Unknown labels ──▶ Unsupervised classification ──▶ discover natural groupings/clusters from the data itself

In data mining: supervised classification = predicting a categorical class from a labelled training set; unsupervised classification = clustering (grouping similar objects without predefined labels).

Answer: (i) a class of learning algorithm that tries to find an optimum classification of a set of examples using the probabilistic theory

Bayesian classifiers are a family of statistical classifiers based on Bayes' theorem:

$$P(C_i \mid X) = \frac{P(X \mid C_i)\,P(C_i)}{P(X)}$$

A tuple $X$ is assigned to the class $C_i$ with the maximum posterior probability $P(C_i \mid X)$. They therefore model classification as a probability calculation over the attributes — exactly the probabilistic-theory approach described in option (i).

Why the others are wrong:

• (ii) describes a search-space/inductive-bias mechanism (constraining a hypothesis space) — not specifically Bayesian.
• (iii) describes case-based learning / reasoning (adapting explanations from familiar experiences) — that is not a Bayesian approach.
• (iv) None of the above — incorrect since (i) is correct.

Hence Bayesian classifiers are the probabilistic-theory classification approach — option (i).

Answer: (iii) arbitrary

In nearest-neighbour (k-NN) classification, a new object is assigned to the class most common among its $k$ closest labelled training objects. The decision boundaries it produces are exactly the perimeters of Voronoi diagrams: each training object owns a "cell" of the feature space containing all points closer to it than to any other object, and cell boundaries (perpendicular bisectors) form the class boundaries.

• These boundaries are not restricted to axis-parallel rectilinear lines (option i),
• nor to fixed oblique/hyperplanar shapes such as SVM or logistic-regression bounds (option ii).

For that reason the textbook (Han & Kamber) states that the decision boundaries of nearest-neighbour classifiers are arbitrary — they can take any irregular, data-driven shape determined purely by where the local training points lie.

Hence the correct answer is (iii) arbitrary.

Solution

Correct Answer: (ii) 90%

Explanation

Accuracy = (correctly classified instances) / (total instances)

Accuracy = 180 / 200 = 0.90 = 90%

In confusion-matrix terms: Accuracy = (TP + TN) / (TP + TN + FP + FN).

Why other options are incorrect:

• (i) 80% = 160/200, (iii) 85% = 170/200, (iv) 95% = 190/200.

Answer: (ii) 90%

Answer: (iii) $d = \frac{2}{\|w\|}$

Explanation

For a linear SVM with separating hyperplane

$$w \cdot x + b = 0$$

the perpendicular distance from the origin to the plane is $|b|/\|w\|$. If the margin is defined by the two boundary hyperplanes

$$w \cdot x + b = +1 \quad \text{and} \quad w \cdot x + b = -1$$

then the total margin (width) is the distance between them:

$$d = \frac{|1 - (-1)|}{\|w\|} = \frac{2}{\|w\|}$$

This is the quantity maximised by SVM: maximising the margin $2/\|w\|$ is equivalent to minimising $\frac12\|w\|^2$ subject to the classification constraints.

Why the others are wrong:

• (i) $1/|w|$ — that is the distance of one of the boundary planes from the hyperplane centre (the half-margin), not the full margin.
• (ii) $1/(2|w|)$ — half of option (i), not the margin.
• (iv) $1/|w|^2$ — has no such role in the SVM margin formula.

Hence the margin of the decision boundary in SVM is $d = 2/\|w\|$.

Solution

Correct Answer: (i) Cross-validation

Explanation

In k-fold cross-validation the data is split into k parts (folds). The model is trained on k-1 folds and tested on the remaining fold, repeating k times so every fold is used once for testing. The average score gives a more reliable estimate of performance, and because the model is tested on unseen data each time, it helps detect and reduce overfitting.

Why other options are incorrect:

• (ii) Increasing noise - makes the model worse.
• (iii) Data duplication - causes test data leakage and over-optimistic results.
• (iv) Removing the test set - removes any way to measure performance on unseen data.

Answer: (i) Cross-validation

Answer: (i) Assigning data to predefined classes

Classification is a supervised learning task in which a model is first trained on a labelled training set (tuples for which the class label is already known), and then the learned model is used to assign new, unseen data objects to one of the predefined classes.

For example, an e-mail classifier is trained on a set of e-mails already labelled "spam" or "not-spam", and thereafter predicts the label of every incoming e-mail.

Why the others are wrong:

• (ii) Dividing data into clusters — this is clustering, an unsupervised task with no predefined class labels.
• (iii) Summarizing data — this describes data characterization/summarization, not classification.
• (iv) Cleaning data — this is data preprocessing, not classification.

So classification is fundamentally about assigning data objects to predefined classes.

Answer: (iv) All of the above

According to Han, Kamber & Pei (Data Mining: Concepts and Techniques), classification and prediction methods are evaluated/affected by the following criteria:

1. Accuracy — the ability of the model to correctly predict the class label of new or previously unseen data.
2. Speed — the computation cost of both building the model (training time) and using it (classification time).
3. Robustness — the ability of the model to handle missing values, noise, and outliers, and to make correct predictions even when the data is imperfect.
4. Scalability — performance as the amount of data grows (not listed but part of the same set).
5. Interpretability/comprehensibility — the extent to which the model is understandable to the user.

Since accuracy, speed, and robustness are all standard criteria that affect classification/prediction methods, the correct option is (iv) All of the above.

Answer: (iii) Neural Networks

Backpropagation is the standard learning (training) algorithm for multilayer feed-forward neural networks. It works in two phases:

1. Forward pass — the input is propagated layer by layer through the network, and the output at the output layer is computed.
2. Backward pass — the error (difference between actual output and expected output) is propagated backwards through the network to update each weight using the gradient descent rule:

$$w_{ij} \leftarrow w_{ij} + \eta\, \delta_j \, x_{ij}$$

where $\eta$ is the learning rate, $\delta_j$ is the error term of node $j$, and $x_{ij}$ is the input arriving along weight $w_{ij}$.

Why the others are wrong:

• (i) Decision Trees use attribute-selection measures such as information gain / Gini index, not backpropagation.
• (ii) Association Rules are found using algorithms like Apriori or FP-growth.
• (iv) Hierarchical Clustering uses distance-based agglomeration (AGNES/DIANA), not backpropagation.

Hence backpropagation is commonly used in Neural Networks.

Answer: (iii) an approach to the design of learning algorithms that is inspired by the fact that when people encounter new situations, they often explain them by reference to familiar experiences, adapting the explanations to fit the new situation

Case-based learning (case-based reasoning, CBR) solves a new problem by recalling and adapting solutions of similar stored past cases — mirroring how humans refer to familiar experiences and adapt them to a new situation. It is a lazy / instance-based learning approach.

Why the others are wrong:

• (i) describes a probabilistic (Bayesian) classifier, not case-based learning.
• (ii) describes an inductive-bias / hypothesis-space constraining mechanism, not case-based learning.
• (iv) None of the above — incorrect since (iii) is correct.

Hence case-based learning is the "adapt familiar experiences to new situations" learning paradigm — option (iii).

Answer: (ii) high, low

In an Artificial Neural Network (ANN), the training time is high while the testing (application) time is low:

• Training (high): learning uses the backpropagation algorithm, which requires many forward-backward passes over the training data, repeated over many epochs, adjusting weights by gradient descent until the error converges. This is computationally expensive and slow — especially for large datasets and deep networks.

• Testing (low): once the network is trained, classifying a new input is just a single forward pass through the fixed-weight network (a sequence of weighted sums and activation functions), which is very fast.

Training phase (slow):  data ──▶ [weight initialization] ──▶ [forward pass]
                                            ▲                  │
                                            └── backward pass / weight update ◀── error
Testing phase (fast):   single forward pass ──▶ output class

Why the others are wrong:

• (i) low, high — the reverse of the truth.
• (iii) low, low — training of ANNs is definitely not fast.
• (iv) high, high — testing is fast, not high.

Hence training time is high and testing time is low for ANN — option (ii).

Instance-Based Classifiers

How an instance-based classifier works

Instance-based (lazy) classifiers do not build an explicit global model (such as a decision tree or a weight vector) during a separate training phase. Instead they store the training tuples and, at classification time, compare a new tuple with those stored tuples by a similarity/distance measure, then assign it a class based on the local neighbourhood of the most similar stored instances.

k-Nearest Neighbour (k-NN) is the classic algorithm:

1. Given a new, unseen query tuple $x_q$, compute its distance (usually Euclidean) to every stored training tuple.
2. Select the $k$ closest tuples; $k$ is typically an odd number (to avoid ties) chosen empirically by cross-validation.
3. Assign $x_q$ to the class held by the majority of these $k$ nearest neighbours.

      Training set (stored)          New tuple
      (features, class)                │
              │  distance
              ▼
          select k nearest neighbours
              │  majority vote
              ▼
           predicted class

Nearest-neighbour classifiers may also use weighted voting (nearer neighbours vote more heavily).

Two instance-based classifiers:

1. k-Nearest Neighbours (k-NN) — lazy, non-parametric, the workhorse of instance-based classification.
2. Case-based reasoning (CBR) — stores previously solved cases (problem–solution pairs); a new problem is solved by retrieving the most similar stored case(s) and adapting their solutions.
3. Rote classifier — pure lookup: a new tuple is classified only if there is an exactly matching stored tuple (no generalisation at all; fragile when no exact match exists).

(For the exam, k-NN and case-based reasoning are the two commonly named.)

Under-fitting and Over-fitting of a Classification Model

Over-fitting (Overfitting)

Overfitting occurs when a classification model fits the training data too well — including its random noise, outliers, and accidental patterns — at the cost of generalisation to new/unseen data. Such a model typically has very low (even zero) training error but high test error.

When does it happen?

• The model is too complex for the underlying problem (e.g., a very deep decision tree, a high-degree polynomial, too many neural-network hidden units).
• Training continues too long, so the learner starts memorising noise.
• The training set is small and noisy relative to the model's capacity.

Under-fitting (Underfitting)

Underfitting occurs when the model is too simple to capture the genuine structure of the data, so it fails to learn even the training set: both training and test errors are high (a high-bias situation).

When does it happen?

• The model is too simple (e.g., a linear model for a curved relationship, a one-leaf tree).
• Too few relevant attributes are provided, or the data are over-aggregated/discretized.
• Training is stopped too early, or the wrong model class is used.

          Training error   Test error
Overfit:     very low           high
Underfit:     high              high
(good model): low-mid          low-mid (small gap)

Diagnosis & remedies:

• Overfit: reduce model complexity, use cross-validation, prune trees, add more data, apply regularisation, early stopping, or ensemble (bagging/random forest).
• Underfit: increase model complexity, engineer/add more relevant features, choose a richer model class, and ensure training runs long enough.

Both problems stem from mismatch between model complexity and the data's true complexity — too complex ⇒ overfit; too simple ⇒ underfit.

Analogy

Fitting a curve to measurements: overfit = wiggly curve passing exactly through every noisy point (terrible on new points); underfit = a straight line through strongly curved data (misses the trend).

Support Vector Machine (SVM)

Definition. An SVM is a supervised (mainly binary) classification algorithm that learns the hyperplane

$$w \cdot x + b = 0$$

which separates the two classes with the maximum margin.

1. Maximum-margin idea

• Many hyperplanes may separate two classes; SVM chooses the one farthest from the nearest point of each class — the margin, of width $2/\|w\|$ for the canonical hyperplanes $w \cdot x + b = \pm 1$.
• Hard-margin optimisation: $\min_{w,b} \; \tfrac{1}{2}\|w\|^2$ subject to $y_i (w \cdot x_i + b) \ge 1$ for every training point. Minimising $\|w\|^2$ is the same as maximising the margin.
• Soft margin — when the classes overlap, slack variables $\xi_i \ge 0$ are permitted with a penalty $C \sum_i \xi_i$; the parameter $C$ trades margin width against training error.
• This is structural risk minimisation: a wider margin gives a better bound on generalisation error, so the model is not merely fitting the training set.

2. Support vectors

• The training points that lie on the margin (or violate it) are called support vectors.
• Only the support vectors determine the hyperplane — deleting any other training point changes nothing, so the model is sparse and robust.
• All other points can be discarded after training; prediction depends only on the support vectors, which keeps the stored model small.

3. Kernel trick

• If the data is not linearly separable, it is mapped by $\phi$ into a higher-dimensional space in which a linear separator exists.
• The kernel function $K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)$ evaluates that inner product directly, without ever constructing $\phi$ explicitly.
• Common kernels: linear $x \cdot y$, polynomial $(x \cdot y + c)^d$, RBF / Gaussian $\exp(-\gamma \, \|x - y\|^2)$, and sigmoid.
• Kernels let SVM model complex non-linear decision boundaries at modest computational cost.

4. Comparison with other classifiers

Aspect	SVM	Decision tree	Naive Bayes	KNN
Core idea	Max-margin hyperplane	Recursive attribute splits	Bayes' rule + independence	Vote of k nearest points
Non-linearity	Kernel trick	Inherent (axis-parallel splits)	Limited	Inherent
High-dimensional data	Very good	Overfits easily	Good	Suffers from distance concentration
Training cost	High (quadratic programming)	Low	Very low	None (lazy learner)
Prediction cost	Low (only support vectors)	Low	Low	High (scans training set)
Robustness to noise	Soft margin absorbs it	Sensitive	Moderate	Very sensitive
Interpretability	Low (black box)	High (readable rules)	Medium	Low

5. Merits and limitations

• Advantages — performs well in high dimensions, memory-efficient (stores only support vectors), solves a convex problem with a unique global optimum, and has strong theoretical generalisation guarantees.
• Limitations — training is slow on very large datasets, results are sensitive to the choice of kernel and $C$, the formulation is inherently binary (multiclass handled by one-vs-one or one-vs-rest), and it does not naturally output calibrated probabilities.

Conclusion

SVM recasts classification as a convex quadratic optimisation problem with a unique global solution, maximises the separating margin, and extends to non-linear boundaries through the kernel trick — the reasons it became one of the most reliable classifiers for medium-sized, high-dimensional datasets.

Building a Decision Tree — Height/Gender Data

Step 1: Discretize Height into the given ranges

Gender	Height (m)	Range	Class
F	1.6	(0,1.6]	Short
M	2.0	(1.9,2.0]	Tall
F	1.9	(1.8,1.9]	Medium
F	1.88	(1.8,1.9]	Medium
F	1.7	(1.6,1.7]	Short
M	1.85	(1.8,1.9]	Medium
F	1.6	(0,1.6]	Short
M	1.7	(1.6,1.7]	Short
M	2.2	(2.0,5.0]	Tall
M	2.1	(2.0,5.0]	Tall
F	1.8	(1.7,1.8]	Medium
M	1.95	(1.9,2.0]	Medium
F	1.9	(1.8,1.9]	Medium
F	1.8	(1.7,1.8]	Medium
F	1.75	(1.7,1.8]	Medium

Class distribution: Short = 4, Medium = 8, Tall = 3 (15 tuples).

Step 2: Root entropy

$$H(D) = -\frac{4}{15}\log_2\frac{4}{15} -\frac{8}{15}\log_2\frac{8}{15} -\frac{3}{15}\log_2\frac{3}{15} \approx 1.46$$

Step 3: Choose the best attribute by Information Gain

Splitting on Height ranges (each row of the discretization table):

Range	Tuples	Classes	Entropy
(0,1.6]	2	Short, Short	0
(1.6,1.7]	2	Short, Short	0
(1.7,1.8]	3	Medium ×3	0
(1.8,1.9]	4	Medium ×4	0
(1.9,2.0]	2	Tall, Medium	1
(2.0,5.0]	2	Tall, Tall	0

Weighted entropy $= \frac{2}{15}(1) = 0.13$; therefore

$$\text{Gain(Height)} = 1.46 - 0.13 = 1.33$$

Splitting on Gender:

• Female (9): Short 3, Medium 6 → $H(F) = 0.92$, contributes $\frac{9}{15}\cdot0.92 = 0.55$
• Male (6): Short 1, Medium 2, Tall 3 → $H(M) = 1.46$, contributes $\frac{6}{15}\cdot1.46 = 0.58$

$$\text{Gain(Gender)} = 1.46 - (0.55+0.58) = 0.33$$

Since Gain(Height) = 1.33 > Gain(Gender) = 0.33, split on Height at the root.

Step 4: Resulting Decision Tree

                      Height range?
        ┌──────────────┬────────────┬───────────┬────────--┬──────────┬──────────┐
      (0,1.6]      (1.6,1.7]   (1.7,1.8]  (1.8,1.9]   (1.9,2.0]    (2.0,5.0]
         │             │            │          │           │             │
      Short         Short       Medium     Medium        │           Tall
                                                         │
                                             Height ≥ 2.0 ?
                                            /             \
                                      Tall            Medium
                                     (2.0)            (1.95)

Explanation

• Every range except (1.9,2.0] is already pure (all classes identical), so it becomes a leaf directly.
• The range (1.9,2.0] contains two male students: height 2.0 → Tall, height 1.95 → Medium — Gender cannot separate them (both M), so the only distinguishing feature left is a finer height threshold (≥ 2.0 → Tall, else Medium).
• The final tree separates students into the three classes Short / Medium / Tall using their height, giving perfect classification on this training set.

What are Over-fitting and Under-fitting? When do they happen?

Over-fitting

Over-fitting — the model learns the training data too precisely, capturing random noise, outliers, and chance coincidences in addition to the true signal. Result: near-zero training error but poor accuracy on new/unseen data (high variance).

When does it occur?

• Model too complex — too many parameters/leaves compared with the amount of data (e.g., a fully-grown, unpruned decision tree; a very deep neural net; a high-order polynomial).
• Training for too many epochs/iterations, especially on small, noisy data sets.
• Using too many irrelevant/multivalued attributes so the learner finds spurious patterns.

Under-fitting

Under-fitting — the model is too simple to represent the underlying relationship, so it fails to capture even the main trend: both training and test errors are high (high bias).

When does it occur?

• Model too simple for the data (e.g., a linear model fitted to clearly non-linear data; a single-leaf tree).
• Not enough useful features/attributes; inappropriate discretization.
• Training stopped too early or the wrong type of model is chosen.

          Training   Test
Overfit:     low       high      (low bias, high variance)
Underfit:   high       high      (high bias)
Good:       low-mid    low-mid   (balanced)

Why (the bias–variance trade-off)

Overfitting is driven by increased variance: excessively flexible models respond to every random fluctuation. Underfitting is driven by high bias: overly rigid models cannot express the data's true relation. The ideal model complexity balances both.

When they matter / detection

The clearest sign is a large gap between training and validation (test) accuracy — low train / high test ⇒ over-fit; both high ⇒ under-fit. We detect and fix them with cross-validation, pruning /regularisation, adjusting model complexity, and gathering more or better data.

Q4(a) - Building a Decision Tree (ID3, Information Gain)

Method. At every node we test the attribute that yields the largest information gain, i.e. the largest reduction of entropy (class impurity):

$$H(S)=-\sum_{i}p_i\log_2 p_i, \qquad Gain(S,A)=H(S)-\sum_{v\in Values(A)}\frac{|S_v|}{|S|}H(S_v)$$

Height binning. A value lying exactly on a boundary is taken into the higher range, so the given ranges are read as $[0,1.6),[1.6,1.7),[1.7,1.8),[1.8,1.9),[1.9,2.0),[2.0,5.0]$. (With the opposite convention every range comes out pure and the tree is even shallower; the choice of the root attribute does not change.)

Step 1 - Count tables (15 records)

Class counts inside each height range:

Height range	Short	Medium	Tall	Total
$[0,1.6)$	0	0	0	0
$[1.6,1.7)$	2	0	0	2
$[1.7,1.8)$	2	1	0	3
$[1.8,1.9)$	0	4	0	4
$[1.9,2.0)$	0	3	0	3
$[2.0,5.0]$	0	0	3	3
Total	4	8	3	15

Class counts by gender:

Gender	Short	Medium	Tall	Total
F	3	6	0	9
M	1	2	3	6
Total	4	8	3	15

Step 2 - Entropy of the whole data set

$$H(S)=-\frac{4}{15}\log_2\frac{4}{15}-\frac{8}{15}\log_2\frac{8}{15}-\frac{3}{15}\log_2\frac{3}{15}=0.5085+0.4837+0.4644=\mathbf{1.4566\ \text{bits}}$$

Step 3 - Candidate splits

(a) Height - multi-way split over the given ranges

Only the range $[1.7,1.8)$ is impure (2 Short + 1 Medium):

$$H([1.7,1.8))=-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.3900+0.5283=0.9183$$

All other non-empty ranges are pure, so their entropy is 0. Therefore

$$Gain(\text{Height})=1.4566-\frac{3}{15}(0.9183)=1.4566-0.1837=\mathbf{1.2729}$$

(b) Gender - two-way split

$$H(F)=-\frac{3}{9}\log_2\frac{3}{9}-\frac{6}{9}\log_2\frac{6}{9}=0.5283+0.3900=0.9183$$

$$H(M)=-\frac{1}{6}\log_2\frac{1}{6}-\frac{2}{6}\log_2\frac{2}{6}-\frac{3}{6}\log_2\frac{3}{6}=0.4308+0.5283+0.5000=1.4591$$

$$Gain(\text{Gender})=1.4566-\left(\frac{9}{15}\times0.9183+\frac{6}{15}\times1.4591\right)=1.4566-1.1346=\mathbf{0.3219}$$

(c) Binary threshold splits on height (cross-check)

Split	Left class counts (S, M, T)	Right class counts (S, M, T)	Gain
height < 1.7	(2, 0, 0)	(2, 8, 3)	0.300
height < 1.8	(4, 1, 0)	(0, 7, 3)	0.628
height < 1.9	(4, 5, 0)	(0, 3, 3)	0.462
height < 2.0	(4, 8, 0)	(0, 0, 3)	0.722

Root = Height, because 1.2729 is by far the largest gain (Gender gives only 0.3219).

Step 4 - Grow each branch

• $[0,1.6)$ - no records, ignored.
• $[1.6,1.7)$ - 2 Short, already pure, so leaf = Short.
• $[1.7,1.8)$ - 2 Short + 1 Medium, so split with the remaining attribute Gender:
  • F gives 1 Short (1.70 m) and 1 Medium (1.75 m): a 1-1 tie, entropy 1.0.
  • M gives one record (1.70 m, Short): pure, leaf = Short.
  • Split gain $=0.9183-\big(\frac{2}{3}\times1+\frac{1}{3}\times0\big)=0.2516>0$, so the split is justified.
• $[1.8,1.9)$ - 4 Medium, pure, leaf = Medium.
• $[1.9,2.0)$ - 3 Medium, pure, leaf = Medium.
• $[2.0,5.0]$ - 3 Tall, pure, leaf = Tall.

Final decision tree

                          [ Height ]
    +-----------+-----------+-------------+------------+------------+------------+
 [0,1.6)    [1.6,1.7)   [1.7,1.8)     [1.8,1.9)   [1.9,2.0)   [2.0,5.0]
  empty        Short        Gender         Medium      Medium       Tall
                              |
                 +------------+------------+
                 F                        M
             Short *                    Short
         (1 Short, 1 Medium)

Resulting classification rules

1. Height $\in[2.0,5.0]$ gives Tall
2. Height $\in[1.8,2.0)$ gives Medium
3. Height $\in[1.6,1.7)$ gives Short
4. Height $\in[1.7,1.8)$ and Gender = M gives Short; Gender = F is a 1-1 tie broken by any fixed rule (e.g. Short)

The tree classifies 14 of the 15 training records correctly (93%); the only ambiguity is the female pair inside $[1.7,1.8)$, which no available attribute can separate.

Over-fitting and Under-fitting of a Model

1. Definitions

• Over-fitting: the model learns the training data too well. Besides the true underlying pattern it also memorises the random noise, outliers and accidental regularities peculiar to that sample. It gives an extremely low (often zero) error on the training data but a large error on unseen data, i.e. it fails to generalise.
• Under-fitting: the model is too simple to capture the structure present in the data. It does not learn even the training relationship, so it has high error both on the training set and on the test set. Such a model has high bias.

2. When do they happen?

Over-fitting occurs when:

1. The model is far too complex for the amount of data - e.g. a fully grown, unpruned decision tree that creates one leaf per record, a very high-degree polynomial, or a neural network with far more parameters than samples.
2. Training continues too long, or the same data is reused with constant hyper-parameter tuning (the test data is indirectly used for training).
3. The training data is small, noisy, unrepresentative or contains outliers that the model tries to explain.
4. No validation, pruning or regularisation is used.

Under-fitting occurs when:

1. The model is too simple to represent the data - e.g. a decision stump, a linear model fitted to clearly non-linear data, a tree with too few levels.
2. Too few or uninformative features are used, or useful features are discarded.
3. Training stops too early (premature stopping), or the regularisation strength is set too high.
4. The learning algorithm itself cannot express the true relationship (a high-bias model).

3. Bias-variance view

	Over-fitting	Under-fitting
Model complexity	Too high	Too low
Training error	Very low	High
Test / validation error	High	High
Bias	Low	High
Variance	High (sensitive to the data)	Low
Typical cause	Too much flexibility, too little data	Too little flexibility

Total prediction error = Bias + Variance + irreducible noise; the goal is the sweet spot where this sum is minimum.

 Error
  |  \___                     __--  training error
  |      \____          ____--
  |           \____--~~     gap between the two curves
  |            ^   ^          = over-fitting
  |            |   validation error
  +------------+--------------------------------> Model complexity
          under-fitted   good fit     over-fitted

4. Detection and control

• Detect: split the data into training and validation sets (k-fold cross-validation) and compare the two error curves; plot a learning curve (error vs. amount of training data).
• Cure over-fitting: collect more training data, post-pruning / pre-pruning of the tree, regularisation, dropout and early stopping, feature selection, ensemble methods such as bagging and random forests, or a simpler model.
• Cure under-fitting: use a richer model, add better features, train longer, reduce regularisation.

Naïve Bayesian Classification — Why "Naïve" & Main Ideas

Why is it called "naïve"?

The naïve Bayes classifier applies Bayes' theorem but makes one strong ("naïve") simplifying assumption: it assumes that all attributes are conditionally independent of one another given the class label. In other words, the value of one attribute is assumed to have no influence on any other attribute once the class is known:

$$P(X \mid C) = P(x_1, x_2, \dots, x_n \mid C) = \prod_{k=1}^{n} P(x_k \mid C)$$

This independence assumption is rarely true in real-world data — for example, "age" and "income", or "smoking" and "lung disease", are usually correlated. Because this simplifying assumption is unrealistic, the classifier is called naïve.

Major Ideas of Naïve Bayesian Classification

1. Estimate probabilities from training data. For each class $C_i$ compute:

   • the class prior $P(C_i)$ — the proportion of training tuples belonging to $C_i$;
   • the conditional probabilities $P(x_k \mid C_i)$ for each attribute value $x_k$ (from frequency counts; Gaussian density for continuous attributes).

2. Classify by the maximum-a-posteriori (MAP) rule. For a new tuple $X = (x_1, \dots, x_n)$, Bayes' theorem gives:

$$P(C_i \mid X) = \frac{P(X \mid C_i)\, P(C_i)}{P(X)}$$

Since $P(X)$ is the same for every class, assign $X$ to the class with the maximum value of $P(X \mid C_i)\, P(C_i)$:

$$\text{assign } X \text{ to } C_i \text{ that maximises } P(C_i)\prod_{k=1}^{n} P(x_k \mid C_i)$$

3. Independence assumption makes it computable — the joint probability becomes a simple product of per-attribute probabilities, so the classifier is very fast even for high-dimensional data.

4. Laplacian (add-one) smoothing — avoids a single zero conditional probability $P(x_k \mid C_i)=0$ from forcing the whole product to zero.

Advantages: extremely fast, works well on high-dimensional data such as text, robust to irrelevant attributes, probabilistically principled. Major limitation: the independence assumption is usually violated in real data, which can reduce accuracy — yet in practice (e.g., spam filtering) it still performs surprisingly well.

Boosting — Concept and Why It Improves Decision Tree Accuracy

What is Boosting?

Boosting is an ensemble method that combines several weak learners (classifiers only slightly better than random guessing) into a single strong classifier by training them sequentially, gradually focusing more weight on the tuples that earlier learners misclassified.

Main (AdaBoost-style) idea:

1. Assign an equal initial weight to every training tuple.
2. Train a weak learner (typically a single-level decision tree / decision stump) on the weighted data.
3. Increase the weights of misclassified tuples and decrease the weights of correctly classified ones, so the next learner concentrates on the "hard" cases.
4. Repeat for $T$ rounds; each new learner specialises in the mistakes of its predecessors.
5. Combine all $T$ models by weighted voting, where each classifier's vote is weighted by its accuracy:

$$\text{final}_{}(x) = \operatorname{sign}\left(\sum_{t=1}^{T} \alpha_t \, h_t(x)\right), \qquad \alpha_t = \frac12 \ln\frac{1-\varepsilon_t}{\varepsilon_t}$$

   weighted data ──▶ T1 ──▶ raise weights of errors ──▶ T2 ──▶ ... ──▶ weighted vote
                    (weak)                                          (strong ensemble)

Why boosting may improve the accuracy of decision tree induction

• Focuses on hard instances. Instead of a single tree that may miss complex regions, boosting builds many simple trees, each paying special attention to tuples the earlier trees got wrong — so subtle patterns that no single stump could capture are learned by the committee.
• Reduces variance and bias. Decision trees are unstable (small data changes → very different trees). Averaging many trees in an ensemble drastically reduces variance; the committee can also express relationships that are beyond any single shallow tree, reducing bias.
• Margin-based generalisation. Weighted combinations of weak classifiers tend to produce large margins on the training points, and larger margins yield better theoretical generalisation bounds.

Limitation / caution: boosting aggressively emphasises hard tuples, so it is sensitive to noise and outliers — with very noisy data it can overfit. Also, the rounds are sequential, so it is not trivially parallelised.

Experimental Framework for Evaluating a Classification Model

The aim is to measure how well the model will work on unseen data, reliably and fairly.

Step 1: Prepare the data

Clean the data, handle missing values, encode and scale features. Fix a random seed so results can be repeated.

Step 2: Training and testing datasets

• Hold-out: split the data, for example 70% training / 30% testing (or 80/20). Use a stratified split so the class proportions are the same in both sets.
• Training set: used to build (fit) the model.
• Validation set (optional): used to tune hyperparameters (e.g. tree depth).
• Test set: used only once at the end; never used for training or tuning, to avoid leakage.

Step 3: Cross-validation

k-fold cross-validation (k = 10 is common):

1. Split the data into k equal folds.
2. Train on k-1 folds, test on the remaining fold.
3. Repeat k times so every fold is used once for testing.
4. Average the k scores.

This gives a more reliable estimate than a single split and reduces overfitting. Variants: stratified k-fold, leave-one-out (small data) and bootstrap.

Step 4: Confusion matrix

	Predicted Positive	Predicted Negative
Actual Positive	TP	FN
Actual Negative	FP	TN

Step 5: Evaluation measures

Measure	Formula	Meaning
Accuracy	(TP + TN) / (TP + TN + FP + FN)	Overall fraction correct; misleading for imbalanced classes
Precision	TP / (TP + FP)	Of the predicted positives, how many are truly positive
Recall (sensitivity, TPR)	TP / (TP + FN)	Of the actual positives, how many were found
F1-score	2 x Precision x Recall / (Precision + Recall)	Harmonic mean of precision and recall
Specificity	TN / (TN + FP)	Of the actual negatives, how many were correct
False positive rate (FPR)	FP / (FP + TN)	Used on the ROC curve

Example: TP = 40, FP = 10, FN = 5, TN = 45 (100 instances)

• Accuracy = 85/100 = 0.85
• Precision = 40/50 = 0.80
• Recall = 40/45 = 0.889
• F1 = 2(0.80)(0.889)/(0.80 + 0.889) = 0.842

Step 6: ROC-based evaluation

The ROC curve plots TPR (y-axis) against FPR (x-axis) at different classification thresholds.

• A curve close to the top-left corner means a good model.
• The diagonal line is random guessing.
• AUC (area under the curve) summarizes performance: 1.0 is perfect, 0.5 is random.
• ROC is useful for comparing models and for imbalanced data, together with precision-recall curves.

Step 7: Compare and report

Compare against a baseline (such as majority class), compare several models on the same folds, report the mean and standard deviation of the metrics, and check with a significance test if needed.

How ensemble methods improve predictive performance

An ensemble combines several models so that the combined prediction is better than any single model.

Method	Idea	Effect
Bagging (e.g. Random Forest)	Train models on bootstrap samples; vote or average	Reduces variance and overfitting
Boosting (e.g. AdaBoost, Gradient Boosting)	Train models in sequence; each focuses on the previous errors	Reduces bias, gives high accuracy
Stacking	A meta-model learns to combine the outputs of different models	Uses the strengths of diverse models

Ensembles work because different models make different errors, and combining them cancels many of those errors. Ensembles should themselves be evaluated with the same cross-validation framework.

Conclusion

A sound framework uses a clean train/test split, cross-validation, several metrics (accuracy, precision, recall, F1, ROC-AUC) and, where needed, ensembles, to get a trustworthy estimate of how the model will perform in practice.

Entropy and Information Gain

1. Entropy

Entropy is a measure of impurity, disorder or uncertainty of a data set $S$ with respect to its class labels. For a data set that contains $c$ classes with probabilities $p_1, p_2, \dots, p_c$ (estimated as relative frequencies $p_i = |C_i|/|S|$):

$$H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i$$

Units: bits (base 2; base $e$ gives nats).

Properties:

1. $0 \le H(S) \le \log_2 c$.
2. $H(S) = 0$ when the set is pure (all records belong to one class) - no disorder.
3. $H(S)$ is maximum when all classes are equally likely, i.e. $p_i = 1/c$, giving $H = \log_2 c$ (maximum uncertainty).
4. Entropy depends only on the class distribution, not on which attribute is tested.

2. Information gain

Information gain of a test on attribute $A$ with values $v_1 \dots v_n$ is the reduction in entropy (uncertainty about the class) obtained by splitting $S$ on $A$:

$$Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$

The second term is the weighted (expected) entropy after the split - the average impurity of the children, each child weighted by its share of the records. Hence

$$Gain(S,A) = \text{impurity before the split} - \text{average impurity after the split}$$

Interpretation. The larger the gain, the better the attribute separates the classes. The learning algorithm (ID3) at every node chooses the attribute with the maximum information gain; a gain of 0 means the attribute does not separate the classes at all, while a gain equal to $H(S)$ means the split produces perfectly pure children.

3. Worked numeric example

A set $S$ of 10 records has 6 positives and 4 negatives:

$$H(S) = -\frac{6}{10}\log_2 0.6 - \frac{4}{10}\log_2 0.4 = 0.6(0.7370) + 0.4(1.3219) = \mathbf{0.9710\ bits}$$

Attribute $A$ has two values:

Branch	Records	Class mix	$H$ of branch
$A = a_1$	5	5 Pos, 0 Neg	0
$A = a_2$	5	1 Pos, 4 Neg	0.7219

$$E(S,A) = \frac{5}{10}(0) + \frac{5}{10}(0.7219) = 0.3610$$

$$Gain(S,A) = 0.9710 - 0.3610 = \mathbf{0.6100\ bits}$$

So testing $A$ removes about 61% of the initial uncertainty. (For a second candidate attribute with a smaller gain, the algorithm would pick $A$.)

4. Remarks used in exams

• In the decision-tree problem of Q4(a), $H(S) = 1.4566$ bits, $Gain(\text{Height}) = 1.2729$ and $Gain(\text{Gender}) = 0.3219$, so Height is chosen at the root.
• Gain ratio (C4.5) divides gain by the split information $-\sum \frac{|S_v|}{|S|}\log_2\frac{|S_v|}{|S|}$ to remove the bias towards attributes with many values.
• Gini index (CART), $Gini = 1 - \sum p_i^2$, is an impurity measure equivalent in spirit to entropy.

Data Classification — Definition & Difference from Prediction

What is Data Classification?

Data classification is a two-step, supervised process:

1. Learning / model construction step: a classification algorithm analyses a labelled training set (tuples whose class labels are known) and builds a model, e.g., a decision tree, a set of classification rules, a neural network, or an SVM.
2. Classification step: the learned model is applied to new, unseen tuples, assigning each to one of the predefined discrete class labels.

Its output is a categorical label (e.g., low-risk/high-risk, spam/not-spam), and its quality is assessed by accuracy (percentage of correctly classified test tuples).

Classification vs Prediction

Aspect	Classification	Prediction (regression)
Output	Discrete / categorical class labels	Continuous / numeric values
Nature	Predicts class of an object	Predicts a numerical value of an attribute
Evaluation	Accuracy / error rate (count of correct labels)	Mean squared error, mean absolute error, correlation
Examples	Predicting "yes/no", "spam/not-spam", loan rating	Predicting house price, sales figure, temperature
Techniques	Decision tree, rule-based, Bayesian, neural, SVM	Linear/ non-linear regression, neural net regression

Important nuance: In a broad sense, "prediction" covers both numeric prediction (regression) and classification — classification is a special case of prediction when the predicted value is a categorical label. In textbook terminology (Han & Kamber), classification predicts categorical labels while numeric prediction (regression) predicts continuous values; the two together form the "classification and prediction" task that examines both discrete & numeric outputs.

Classification & Prediction + Naïve Bayesian Classification

Classification and Prediction — Definitions

• Classification is a supervised learning process that builds a model from labelled training data and then uses it to assign new/unseen objects to discrete, predefined class labels (e.g., predict whether a loan is low-risk or high-risk). Its output is categorical.
• Prediction is the general task of estimating unknown values. When the value being predicted is numeric/continuous (e.g., predicting the price of a house), it is called prediction or regression; when the unknown value is a categorical class label, it is classification. Prediction is governed by a mean squared error style loss, whereas classification deals with accuracy/error rate.

Bayesian Classification

Bayesian classification is a statistical classification technique based on Bayes' Theorem. It assigns a tuple $X$ to the class $C_i$ for which the posterior probability $P(C_i \mid X)$ is maximum:

$$P(C_i \mid X) = \frac{P(X \mid C_i)\, P(C_i)}{P(X)}$$

Because $P(X)$ is the same for all classes, the maximum a posteriori (MAP) decision rule is:

$$\text{choose } C_i \text{ such that } P(X \mid C_i)\, P(C_i) \text{ is maximum}$$

• $P(C_i)$ — prior probability of class $C_i$ (estimated from training-data frequencies).
• $P(X \mid C_i)$ — likelihood of observing $X$ given the class.

Naïve Bayes — a Simple Example

The naïve assumption is that all attributes are conditionally independent given the class, so:

$$P(X \mid C_i) = \prod_{k=1}^{n} P(x_k \mid C_i)$$

Example: Classify a fruit by its attributes.

Fruit	Colour	Shape	Taste
Apple	Red	Round	Sweet
Apple	Green	Round	Sweet
Mango	Yellow	Oval	Sweet
Mango	Yellow	Oval	Sour

Let a new fruit have attributes $X = (\text{Colour} = \text{Yellow},\ \text{Shape} = \text{Oval})$. We compute:
$P(\text{Mango}) = 2/4 = 0.5$, $P(\text{Apple}) = 0.5$.

• $P(Yellow \mid Mango) = 2/2 = 1$, $P(Oval \mid Mango) = 2/2 = 1$
• $P(Yellow \mid Apple) = 0/2 = 0$, so $P(X \mid Apple) = 0$.

Score mango = $0.5 \times (1 \times 1) = 0.5$; apple score $= 0$. Since $0.5 > 0$, the new fruit is classified as Mango.

Advantages: simple, fast, easily handles high-dimensional data, works well in spam filtering and text classification. Limitation: the independence assumption is often violated in real data.

Designing a K-Nearest Neighbour (k-NN) Classifier for Exam Pass/Fail Prediction

1. Choose the attributes (features)

From the given table, use prediction-relevant attributes and drop identifiers:

Attribute	Type	Role
ID, Cell No.	identifier	ignored (no predictive value)
Language	categorical (nominal): Java/C++/Python	matching feature
Passed all Assignments	binary (Yes/No)	matching feature
GPA	numeric (continuous)	main numeric feature
Passed Exam	binary (Yes/No)	class label to predict

2. Encode attributes for distance computation

• GPA — numeric; normalise it (e.g., min–max or z-score) so its scale does not dominate distances.
• Passed all Assignments — encode as 1 (Yes) / 0 (No).
• Language — a categorical matching indicator: 1 if the student's language equals the new student's language, else 0.
• For "Cell No.", a student's phone number should NOT be used (like an ID — it would destroy the algorithm).

3. Define the distance measure

Combine the per-attribute differences, e.g. the weighted Euclidean distance:

$$d(q, t) = \sqrt{w_g\,(gpa_q - gpa_t)^2 + w_a\,(\text{assign}_q - \text{assign}_t)^2 + w_l\,(\text{lang}_q - \text{lang}_t)^2}$$

with default weights 1 for each feature (GPA already normalised). Binary/categorical features contribute 0 (match) or 1 (mismatch).

4. Choose $k$ and the voting rule

• Use small odd $k$ (typically $k=3$ or $k=5$) to avoid ties.
• Tune $k$ by leave-one-out cross-validation on the 8 training tuples (training set is small — each tuple is the test set once, rest train).
• Voting: assign the new student the majority class ("Passed Exam? = Yes/No") among the $k$ nearest neighbours. Ties broken by nearer neighbours or by choosing the smaller distance sum.

5. Evaluation

Compute the classifier's accuracy = (correct predictions)/(total test tuples), and measure the confusion matrix showing false positives (predicted pass, actually failed) vs false negatives — important because failing a student who would pass is arguably worse.

6. Algorithm summary

1. Store all training tuples (X, y): X = (GPA, Assign, Language), y = PassedExam.
2. For a new student q:
      a. normalise GPA features consistently;
      b. compute d(q, t_i) for every stored tuple;
      c. take the k tuples with smallest distance;
      d. output = majority class among those k neighbours.
3. Tune k (and weights) by leave-one-out cross-validation.

This design uses the given table as the training set and predicts Passed Exam for any new student using their GPA, assignment performance, and programming language similarity.

Applying k-NN — Predict Student 9's Re-exam Result

Student 9 to classify

ID	Language	Passed all Assignments	GPA	Passed Exam
9	C++	Yes	3.0	??

The training set is table Q5a; I use the features (GPA, Passed all Assignments, Language = C++) with the distance

$$d = \sqrt{(\Delta\text{GPA})^2 + (\Delta\text{Assign})^2 + (\Delta\text{Language})^2}$$

where mismatches count 1. (Normalisation is omitted here only for a clean illustration; in real use GPA would first be min–max normalised.)

Distances from student 9 to every training tuple

T	Language	Assign	GPA	Passed Exam	ΔGPA	ΔAssign	ΔLang	d
1	Java	No	3.1	Yes	0.1	1	1	1.42
2	Java	No	2.0	No	1.0	1	1	1.73
3	C++	Yes	3.5	Yes	0.5	0	0	0.50
4	Python	Yes	2.5	Yes	0.5	0	1	1.12
5	Java	Yes	3.9	No	0.9	0	1	1.35
6	C++	No	2.9	No	0.1	1	0	1.00
7	Java	No	1.9	No	1.1	1	1	1.79
8	Python	Yes	3.2	Yes	0.2	0	1	1.02

k = 3 nearest neighbours

Closest three tuples: #3 (d=0.50, Pass=Yes), #6 (d=1.00, Pass=No), #8 (d=1.02, Pass=Yes).

• Voting: Yes (2) vs No (1) → majority class = Yes.

Answer

Student 9 (C++, passed all assignments, GPA 3.0) is predicted to PASS the re-exam under a k=3 nearest-neighbour classifier.

(Note: if GPA were normalised the ranking could shift slightly, but the closest student #3 — identical language, same assignment status, close GPA — strongly dominates the vote; the same conclusion typically holds for k=1, 3 and 5.)

ID3 Algorithm for Decision Tree Construction — Description & Limitations

Overview

ID3 (Iterative Dichotomiser 3), by J. Ross Quinlan, builds a decision tree top-down, greedily, choosing the attribute with the highest Information Gain (based on entropy) at each node.

Entropy — the impurity of a data set $D$ with $m$ classes is

$$H(D) = -\sum_{i=1}^{m} p_i \log_2 p_i$$

where $p_i$ is the fraction of tuples in $D$ belonging to class $C_i$.

Information Gain of partitioning $D$ on attribute $A$ with distinct values $\{a_1, \dots, a_v\}$:

$$\text{Gain}(A) = H(D) - \sum_{j=1}^{v} \frac{|D_j|}{|D|}\, H(D_j)$$

where $D_j$ is the subset of $D$ with $A = a_j$.

Algorithm Steps

Algorithm ID3(D: training set, Attributes)
1. Create a root node for D.
2. If all tuples in D belong to the same class C → label node C and return.
3. If Attributes is empty → label node with majority class and return.
4. Else pick A_best = the attribute with maximum Gain(A).
5. Label node with A_best; for each distinct value a_j of A_best create one branch.
6. For each branch: D_j = {tuples with A_best = a_j}
   - if D_j empty → leaf labelled with majority class of D
   - else recursively run ID3(D_j, Attributes − {A_best})
7. Return the resulting tree.

Why ID3 is unsuitable — main limitations

1. Handles only categorical attributes — continuous/numeric data must be discretized first; it cannot branch on < / <= thresholds.
2. Bias toward multi-valued attributes — information gain favours an attribute with many distinct values (e.g. a "customer-ID" attribute would give maximal gain yet be useless), producing poor generalisation. This is fixed in C4.5 by using the gain ratio.
3. No pruning → overfitting — it grows the tree until it fits the training data perfectly, thereby memorising noise and hurting accuracy on unseen test data.
4. Greedy, no backtracking — a locally optimal split may lead to a globally sub-optimal tree.
5. Handles missing values / noise poorly and is unstable — small changes in the training data produce quite different trees.

Despite these limitations, ID3 is the foundation for C4.5 / C5.0 (adding gain ratio, continuous attributes, and pruning) and further scalable classifiers such as CART, SLIQ, SPRINT, and RainForest.

Working of the Decision Tree Method for Classification

What is a Decision Tree?

A decision tree is a flow-chart-like tree structure in which:

• each internal node denotes a test on an attribute,
• each branch represents an outcome of that test,
• each leaf node holds a class label (the prediction),
• the topmost node is the root.

Step-by-Step Construction (Tree Induction)

1. Attribute selection — the best-splitting attribute is chosen at each node using an attribute-selection measure such as Information Gain (used by ID3), Gain Ratio (C4.5), or Gini Index (CART). The attribute that best separates the training tuples (maximally reduces impurity) is selected.
2. Partition/branching — the training set is split according to the distinct values of the chosen attribute.
3. Recursion — the selection-and-split process is repeated on each branch using the remaining attributes.
4. Stopping criteria — a node becomes a leaf when all its tuples belong to the same class, or no attribute remains, or the tuples are too few / other stopping rules apply. The node is labelled with the majority class.
5. Pruning — the fully grown tree is pruned (pre- or post-pruning) to remove branches that overfit the noise, thereby improving generalisation.

To illustrate the attribute-selection idea: given a training set with classes, first compute the entropy of the target attribute $E(S)=-\sum p_i \log_2 p_i$. For each candidate attribute, compute the weighted entropy after splitting by it and take the difference (the information gain); the attribute with the maximum gain becomes the splitting attribute at that node.

Example Dataset

Outlook	Temperature	Play?
Sunny	Hot	No
Overcast	Cool	Yes
Rain	Mild	Yes
Sunny	Mild	Yes

Here the root split is chosen on Outlook (it gives the highest information gain). The resulting tree:

           [Outlook]
         /    |     \
      sunny overcast rain
        |       |      |
      [Temp]   Yes    Yes
      /    \
    Hot     Mild
     |       |
    No      Yes

Classification (Prediction) Phase

A new, unseen tuple is routed from the root down a path whose attribute tests match its values until it reaches a leaf; the class label stored in that leaf is the predicted class.

Advantages

• Easy to understand and interpret; can be directly converted to IF–THEN rules.
• Handles both numeric and categorical attributes.
• Requires little data preparation and no domain knowledge.

Limitations

• Greedy induction — a small change in data can yield a different tree.
• Without pruning it tends to overfit the training data.
• Can be unstable; splitting bias (favours attributes with many values).

Scaling Up SVM for Large Data Sets

The Problem

The standard SVM solves a quadratic programming (QP) problem whose (dual) size is proportional to the number of training tuples $n$. The final classifier depends only on the support vectors, but finding them costs up to O(n²)–O(n³) in time and O(n²) in memory (the full kernel matrix). For large data sets (millions of tuples) that makes straightforward SVM training impractically slow.

Why can it be made scalable?

SVMs satisfy the KKT (Karush–Kuhn–Tucker) optimality conditions, and the solution is captured entirely by the support vectors; most training points do not matter. If we can isolate the support vectors without solving the full QP, training can be made near-linear. All scalable methods exploit this sparsity.

---

Methods for Scalable SVM

1. Chunking (Vapnik).
Never hold the full set in memory: keep a small working set ("chunk"), solve the QP on it, discard the non-support vectors, and bring in the tuples that most violate the KKT conditions from the remaining data. Repeat until all tuples satisfy KKT. Memory drops from O(n^2) to O(chunk^2).

2. Decomposition methods (Osuna).
At each iteration, optimise only a fixed-size sub-problem (a small subset of the variables) while keeping the others fixed at their previous values. The subset is chosen to contain the variables that most violate KKT, and convergence is guaranteed because the objective strictly decreases. This is the framework underlying SVMlight.

3. Sequential Minimal Optimization (SMO).
A special case of decomposition that optimises exactly two Lagrange multipliers per step using a closed-form analytic update — so no inner QP solver is needed. Memory use is minimal and each step is cheap; implemented in libSVM, it converges very quickly in practice (often near-linear). Working-set heuristics pick the most violating pair.

4. Active sampling / core-set methods.
Since only points near the boundary matter, first sample the likely support vectors (points closest to the current separating surface), train a preliminary SVM, then feed back the misclassified / boundary points. Compact core sets (e.g., core-set SVM, RSVM — Reduced SVM) can be built with a guaranteed O(1/ε²) size for a target accuracy ε.

5. Incremental / online learning.
Add tuples one (or a block) at a time: the KKT conditions indicate exactly which existing support vectors must change, so only a local update is needed. This suits streaming or very large data sets and data that grows over time.

6. Parallel and distributed implementations.

• Cascade SVM — split the data across processors; each trains its own SVM; support-vector sets are merged pairwise and retrained until only one compact set remains.
• MapReduce / Spark approaches — map: train local SVMs on partitions; reduce: combine their support-vector sets; iterate until convergence.
• Kernel approximation — use low-rank approximations (Nyström) or random Fourier feature maps so that a simple linear SVM can be trained on the lifted feature space, dramatically speeding up training.

---

Summary Table

Method	Key idea	Efficiency gain
Chunking	solve QP on small working subset	memory reduced to O(k²)
Decomposition	optimise a small subset, fix rest	avoids solving full QP
SMO	exact 2-variable analytic updates	no QP solver, very fast
Core-set / active sampling	train only on boundary candidates	compact O(1/ε) core set
Incremental	sequential KKT updates	streaming-friendly
Cascade / parallel	pool local support vectors across machines	horizontal scaling

Conclusion: because only the support vectors (boundary points) determine an SVM, scalable algorithms identify them by repeatedly concentrating on the KKT-violating points (chunking, decomposition, SMO) or by data-level strategies (sampling, core sets, incremental, parallel) — avoiding the O(n^3) full-QP solve and making SVM practical for large data sets.

Decision Tree for the Weather Data (Entropy-based attribute selection)

Step 1 — Entropy of the root set

14 examples, 9 Yes / 5 No:

$$H(D) = -\frac{9}{14}\log_2\frac{9}{14} - \frac{5}{14}\log_2\frac{5}{14} \approx 0.940$$

Step 2 — Information gain of each attribute

$$\text{Gain}(A) = H(D) - \sum_{v}\frac{|D_v|}{|D|} H(D_v)$$

Outlook

• Sunny (5: Yes 3, No 2) → 0.971; Overcast (4: Yes 4) → 0; Rainy (5: Yes 2, No 3) → 0.971
• $\text{Gain} = 0.940 - \big(\tfrac{5}{14}(0.971) + \tfrac{4}{14}(0) + \tfrac{5}{14}(0.971)\big) = 0.940 - 0.694 = \mathbf{0.246}$

Temperature

• Hot (4: Yes 2, No 2) → 1.0; Mild (6: Yes 4, No 2) → 0.918; Cool (4: Yes 3, No 1) → 0.811
• $\text{Gain} = 0.940 - \big(\tfrac{4}{14}(1.0)+\tfrac{6}{14}(0.918)+\tfrac{4}{14}(0.811)\big) = 0.940 - 0.911 = \mathbf{0.029}$

Humidity

• High (7: Yes 3, No 4) → 0.985; Normal (7: Yes 6, No 1) → 0.592
• $\text{Gain} = 0.940 - \big(\tfrac{7}{14}(0.985)+\tfrac{7}{14}(0.592)\big) = 0.940 - 0.789 = \mathbf{0.151}$

Windy

• False (8: Yes 6, No 2) → 0.811; True (6: Yes 3, No 3) → 1.0
• $\text{Gain} = 0.940 - \big(\tfrac{8}{14}(0.811)+\tfrac{6}{14}(1.0)\big) = 0.940 - 0.892 = \mathbf{0.048}$

Root = Outlook (highest gain 0.246).

Step 3 — Expand each branch

Overcast branch (4 examples, all Yes) → leaf Yes (pure).

Sunny branch (5 examples: Yes 3, No 2):

Attribute	Info	Gain
Temp	(3/5)(0.918)+(2/5)(1.0) = 0.951	0.020
Humidity	(2/5)(1.0)+(3/5)(0.918) = 0.951	0.020
Windy	False: all Yes → 0; True: all No → 0; Info = 0	0.971

→ Split on Windy; both children are pure: Windy=False → Yes, Windy=True → No.

Rainy branch (5 examples: Yes 2, No 3):

Attribute	Info	Gain
Temp	(2/5)(0)+(2/5)(1.0)+(1/5)(0) = 0.400	0.571
Humidity	High: all No → 0; Normal: all Yes → 0; Info = 0	0.971
Windy	(3/5)(0.918)+(2/5)(1.0) = 0.951	0.020

→ Split on Humidity; both children are pure: Humidity=High → No, Humidity=Normal → Yes.

Resulting Decision Tree

                    [Outlook]
            /          |          \
        Sunny      Overcast       Rainy
          |           |             |
        Windy        Yes          Humidity
       /     \                   /        \
   False    True             High        Normal
     |        |                |            |
    Yes      No               No           Yes

Verification

Every leaf is pure, so the tree classifies all 14 training examples correctly (training accuracy 100%). New examples are classified by routing them from the root along the matching attribute values — e.g., (Sunny, Cool, Normal, True) → Outlook=Sunny → Windy=True → No, matching the training example.

The classic textbook result: Outlook is the best root split; within Sunny the differentiator is Windy, and within Rainy it is Humidity.

Lazy Learners and K-Nearest Neighbour Classification

Definition. A lazy learner (instance-based learner) performs no, or almost no, generalisation during training: training only stores the labelled instances, and all computation is deferred until a prediction is requested. KNN is the standard example.

1. Lazy vs eager learners

Aspect	Lazy learner (KNN)	Eager learner (decision tree, neural net)
Training phase	Stores the data only; very fast	Builds an explicit model; slower
Prediction phase	Expensive: queries the whole training set	Cheap: one traversal of the model
Model built	None, the data is the model	Explicit rules, nodes or weights
Incremental data	Added instantly, no retraining	Usually requires rebuilding
Interpretability	Low unless $K$ is tiny	Generally higher
Main weakness	Irrelevant features and feature scale	Rigid model assumptions

Lazy learners adapt naturally to the local shape of the decision boundary but pay for it at query time; eager learners summarise the data, which is faster to use but may miss local detail.

2. KNN algorithm for classification

1. Choose the number of neighbours $K$ (an odd value avoids ties in two-class problems) and a distance metric, Euclidean by default.
2. Standardise or normalise the features so that one attribute does not dominate the distance.
3. For a new instance $x$, compute the distance $d(x, x_i)$ to every training instance.
4. Select the $K$ instances with the smallest distances.
5. Vote: assign the majority class; in weighted voting each neighbour contributes $1/d$ or $1/d^2$.

$$\hat{y} = \arg\max_c \sum_{i \in N_K(x)} w_i \, \mathbb{1}[y_i = c], \qquad w_i = \frac{1}{d(x, x_i)}$$

3. Worked mini-example

Training point	$x_1$	$x_2$	Class
A	1	2	+
B	2	3	+
C	3	1	-
D	6	5	-
E	7	6	-

Classify $T = (5, 4)$ with $K = 3$:

Point	Distance to T
D	$\sqrt{1^2+1^2} = 1.41$
E	$\sqrt{2^2+2^2} = 2.83$
B	$\sqrt{3^2+1^2} = 3.16$
C	$\sqrt{2^2+3^2} = 3.61$
A	$\sqrt{4^2+2^2} = 4.47$

The nearest three are D (-), E (-) and B (+); the majority class is -, so $T$ is classified as -.

4. Practical remarks

• Small $K$ gives a jagged, high-variance boundary (with $K = 1$ there is zero training error but overfitting); large $K$ smooths the boundary and can wash out small clusters.
• KNN is non-parametric, handles multiple classes naturally and needs essentially no training time.
• Its weaknesses: prediction costs $O(nd)$, the whole data set must be kept in memory, and accuracy degrades as dimensionality grows (curse of dimensionality).
• Acceleration structures include KD-trees, ball trees and approximate nearest-neighbour search; distance-weighted voting limits the damage done by distant neighbours.

Support Vector Machines (SVM) — Working & Applications

Working

An SVM is a supervised classification technique that finds the optimal separating hyperplane which best separates the data into two classes and maximises the margin — the distance between the hyperplane and the nearest training points, called support vectors.

        Hyperplane: w·x + b = 0
   class −1        │        class +1
    o   o   o      │        +  +  +  +
      o o     o    │        +      +
        o         (margin)   +      +
   ────────────────────────────
         ↑  margin  ↑
      support vectors

For linearly separable data, the decision boundary is:

$$w \cdot x + b = 0, \quad f(x) = \operatorname{sign}(w \cdot x + b)$$

Maximising the margin $2/\|w\|$ is solved as a constrained convex optimisation problem (using the Lagrangian dual). The separating hyperplane depends only on the support vectors, so the model is sparse.

Key ideas:

1. Maximal margin — choosing the hyperplane with the largest margin gives the best generalisation.
2. Soft margin — real data is often not perfectly separable; slack variables $\xi_i \ge 0$ allow a few misclassified (or margin-violating) points, penalised by a cost parameter $C$:

$$\min \frac{1}{2}\|w\|^2 + C\sum_i \xi_i$$

3. Kernel trick — for non-linear data, a kernel function $K(x_i, x_j)$ (linear, polynomial, RBF/Gaussian, sigmoid) implicitly maps the data into a higher-dimensional feature space where a linear hyperplane can separate the classes:

$$f(x) = \operatorname{sign}\left(\sum_{i} \alpha_i y_i K(x_i, x) + b\right)$$

Applications in Data Mining

• Text / document categorisation — spam detection, topic classification (works extremely well on high-dimensional text features).
• Image recognition — handwritten-digit recognition, face detection.
• Bioinformatics — classification of gene-expression data, protein function prediction.
• Financial data mining — credit scoring, fraud detection, bankruptcy prediction.
• Web mining — web-page classification, personalized recommendations.
• Anomaly/outlier detection — one-class SVM for network intrusion detection and fault monitoring.

Advantages

• Strong theoretical guarantees (maximal-margin → good generalisation), effective in high dimensions, robust to overfitting because only support vectors matter.

Limitations

• Sensitive to kernel choice and parameters; training is slow on huge datasets; the basic method is binary (multi-class handled by one-vs-all / one-vs-one decomposition).

Classification vs Clustering

Definitions. Classification is supervised learning: given a set of records already labelled with predefined classes, it builds a model that predicts the class of unseen records. Clustering is unsupervised learning: it groups records into clusters so that objects within a cluster are similar to each other and dissimilar to those in other clusters, with no labels available.

1. Key differences

Criterion	Classification	Clustering
Learning type	Supervised	Unsupervised
Input data	Training set with class labels	Unlabelled data
Goal	Predict the class of new objects	Discover natural groupings in the data
Output	A classifier (decision tree, rules, network)	A partition, hierarchy or density-based groups
Evaluation	Accuracy, precision, recall, F1, ROC	Internal: silhouette, purity, within-cluster SSE; external: Rand index
Predefined classes?	Yes, fixed in advance	No, number and meaning of clusters emerge from data
Feedback	Errors correct the model (backpropagation, pruning)	No notion of error, only an objective to optimise
Typical algorithms	Decision trees, Naive Bayes, KNN, SVM, neural networks	k-means, hierarchical, DBSCAN, Gaussian mixtures
Cost of labelling	Requires expensive labelled examples	Needs no labels

2. Where each is more appropriate

Classification suits problems where the categories are already known and the objective is prediction:

• Spam detection: classify email as spam or not spam from labelled messages.
• Credit approval: predict good/bad payers from historical applications.
• Disease diagnosis: assign a patient to a diagnosis from symptoms and test results.
• Customer churn: predict which subscriber will cancel, so the model must generalise to future customers.

Clustering suits problems where the categories are unknown or must be discovered:

• Customer segmentation: group buyers by purchase behaviour before designing targeted campaigns.
• Document grouping: organise news articles or research papers into topics with no prior taxonomy.
• Image segmentation: partition an image into homogeneous regions by pixel colour and texture.
• Anomaly/fraud detection: points that do not belong to any dense cluster are flagged as outliers.
• Exploratory analysis: first-pass structure discovery when labels do not exist at all.

3. How they relate

Clustering can feed classification: clusters may be labelled after inspection and used as classes, or cluster indices added as new features. Conversely, classification with labelled data can validate clusters (external validation). Between the two lie semi-supervised methods that exploit a small number of labels together with unlabelled data.

Conclusion: the deciding question is do the class labels already exist? If yes and prediction on new cases matters, classify; if no and the aim is to uncover structure, cluster.

Ensemble Methods — Why and How

Why do we use ensemble methods?

A single classification model may be unstable (small data changes → big model changes, e.g. decision trees), or may be too weak to express the true decision boundary. Ensembles combine several base models and aggregate their predictions to obtain a single, stronger and more stable classifier. Benefits:

1. Improved accuracy — averaging/voting corrects individual model errors; different models make different mistakes, so combining them reduces the overall error.
2. Reduced variance — averaging many unstable models (e.g., trees) smooths out their erratic behaviour.
3. Reduced bias — a committee of models can represent relationships that a single simple model cannot.
4. Robustness — less sensitive to noise, overfitting, and outliers; often better generalisation.

Key Requirement

For an ensemble to help, the base models must be accurate (better than random) and diverse (make different errors).

Bagging (Bootstrap Aggregating) — an ensemble method

Steps:

1. Generate $m$ bootstrap samples from the original training set, each obtained by sampling with replacement (some tuples repeated, others omitted).
2. Train a base classifier (e.g., a decision tree) on each sample — typically grown without pruning (high variance, but diverse).
3. Combine the $m$ classifiers by majority voting for classification (or averaging for regression).

Training set ──bootstrap──▶ S1 ──▶ C1 ─┐
                       S2 ──▶ C2 ─┼─▶ majority vote ─▶ final class
                       ...              │
                       Sm ──▶ Cm ─┘

Why it works: each bootstrap sample differs slightly, so the trees are diverse; voting reduces variance without increasing bias, so overall accuracy improves.

Other ensemble methods

• Random Forest = bagging + random attribute selection at each split.
• Boosting (AdaBoost) = sequential training that re-weights misclassified tuples and combines by weighted vote.
• Stacking = combine heterogeneous base learners with a meta-classifier.

Summary: we use ensembles to get higher, more stable accuracy than any single classifier; a classic simple ensemble is bagging, which trains diverse models on bootstrap samples and votes.

Naïve Bayesian Classification Algorithm

Idea

Naïve Bayes is a statistical/probabilistic classifier based on Bayes' theorem:

$$P(C_i \mid X) = \frac{P(X \mid C_i)\, P(C_i)}{P(X)}$$

where $X = (x_1, x_2, \dots, x_n)$ is a tuple described by $n$ attributes and $C_i$ is a class. Since $P(X)$ is the same for every class, the tuple is assigned to the class with the maximum posterior — the maximum a posteriori (MAP) rule:

$$\text{choose } C_i \text{ that maximises } P(X \mid C_i)\, P(C_i)$$

The "naïve" assumption

To make the computation tractable, naïve Bayes assumes conditional independence of the attributes given the class:

$$P(X \mid C_i) = \prod_{k=1}^{n} P(x_k \mid C_i)$$

Each $P(x_k \mid C_i)$ is estimated separately from the training data, so the classifier is simple and very fast.

Algorithm Steps

Input: training set D (labelled), a new tuple X = (x1, ..., xn)
1. For each class Ci:
     a. Prior:  P(Ci) = (number of training tuples of class Ci) / |D|
     b. For each attribute value xk:
          P(xk | Ci) = (count of tuples of class Ci with xk) / (count of Ci tuples)
          (for continuous attributes use the Gaussian density:
           P(xk|Ci) = 1/(sqrt(2π)·σi) · exp(-(xk-μi)²/(2σi²)) )
2. Score(Ci, X) = P(Ci) · Πk P(xk | Ci)
3. Return the class Ci with the highest score.

Laplacian (add-one) correction: if some $P(x_k \mid C_i) = 0$, the whole product becomes 0. To avoid this, use smoothing:

$$P(x_k \mid C_i) = \frac{\text{count}(x_k, C_i) + 1}{\text{count}(C_i) + m}$$

where $m$ is the number of distinct values of attribute $k$.

Worked Example

Outlook	Temp	Class (Play)
Sunny	Hot	No
Sunny	Mild	Yes
Rainy	Cool	Yes
Rainy	Mild	No
Overcast	Cool	Yes

Predict $X = (\text{Outlook=Sunny},\ \text{Temp=Cool})$.

Priors: $P(Yes)=3/5=0.6$, $P(No)=2/5=0.4$.

Likelihoods:

• $P(Sunny \mid Yes) = 1/3$, $P(Cool \mid Yes) = 2/3$
• $P(Sunny \mid No) = 1/2$, $P(Cool \mid No) = 0$

Scores:

• $\text{Score}(Yes) = 0.6 \times (1/3)(2/3) = 0.133$
• $\text{Score}(No) = 0.4 \times (1/2)(0) = 0$

Since $0.133 > 0$, $X$ is classified as Yes (with Laplacian smoothing, the No score would be tiny but non-zero).

Properties

• Advantages: extremely fast, works well on high-dimensional data (e.g., text/spam filtering), robust to irrelevant attributes, needs only one pass over the training data to estimate probabilities.
• Limitations: the independence assumption is usually violated in real data, which can reduce accuracy; however in practice it often performs surprisingly well.

Naïve Bayes is a core classification method in data mining (Han & Kamber, Chapter 9).