Classification, Performance Measures, and Overfitting

This lecture is a working session on classification. We revise supervised versus unsupervised learning and the split between classification and regression, then follow a full classification project from raw table to deployed model. The middle of the lecture is devoted to performance measures: how to score a regression model, how to score a classification model, the confusion matrix, accuracy, precision, recall, and F1. We then look at how to divide data into train and test sets, including cross-validation, at the practical issues that matter when you choose a classifier, and at the two failure modes every learner must recognize: underfitting and overfitting.

By the end of this session you should be able to answer three kinds of questions: Is this problem supervised or unsupervised, and classification or regression? — the taxonomy from the first sections; How good is my model, and in what sense? — the performance measures in the middle; and Where did the model go wrong, and how do I stop it happening again? — the train-test split, cross-validation, and the underfitting-overfitting tradeoff at the end. The same arc — build, measure, validate, diagnose — is what you will repeat on every real project.

6.1 Supervised and Unsupervised Learning

6.1.1 The Two Families of Data Mining Methods

Data mining offers two families of methods: supervised learning and unsupervised learning.

In supervised learning you are given the data and the corresponding class labels, and the job is prediction. The word supervised is the key: a supervisor — the data set itself — already knows the answer for every training example, and the model's job is to learn the pattern that connects the inputs to those known answers, so it can predict answers for new, unseen examples. Weather prediction systems, tsunami detection systems, and credit card fraud detection systems are all supervised prediction tasks: each one is trained on past cases where the outcome is already known (yesterday's weather, past tsunamis, historical fraud cases) and then asked to predict the outcome for new cases.

In unsupervised learning you are only given $X$. You are not predicting anything; you are finding patterns and structure inside the data. There is no answer key to check against. The classic example is clustering, which we come back to later in the course — grouping customers, documents, or genes by how similar they are, without anyone having labelled the groups beforehand.

The training class labels are known in supervised learning and unknown in unsupervised learning. That single fact is the cleanest way to tell the families apart: ask "does the training data carry an answer column?" If yes, supervised; if no, unsupervised.

Real-world & domain connection. Supervised learning runs production systems that most people use daily without noticing: email spam filters trained on labelled spam/ham archives, credit card fraud scorers trained on labelled transactions, and weather services whose forecasts are supervised models over years of labelled historical weather. Unsupervised learning is the standard tool for exploration phases: market segmentation (find customer groups without pre-defined categories), document clustering, and anomaly scanning before you know what you are looking for. The two families are not competitors — a typical industrial pipeline uses unsupervised methods first to explore and clean data, then supervised methods to make the final predictions.

6.1.2 Classification versus Regression

Supervised learning divides into two types: classification and regression. In both cases you are given $X$ and $Y$.

If $Y$ takes discrete values, we call those values class labels and the problem is classification. A discrete value means a value chosen from a fixed, countable set — "spam" or "not spam", "malware" or "benign", "yes" or "no". If $Y$ is a continuous value, the problem is regression. A continuous value means any number on a scale — 74.3 dollars, 101.5 degrees, 12,845 transactions. Petrol price prediction, oil price prediction, and gold price prediction are regression problems: the price is a number on a scale, not a label from a fixed list.

Both families are prediction models; the difference is only what they predict. Classification predicts discrete, nominal values — the class labels. Regression predicts a continuous value.

When to pick which: look at the answer column in your table. If the answers you want to predict are labels, it is classification; if they are numbers on a scale, it is regression. When the professor's definition comes up, keep the pair in mind: discrete Y means classification, continuous Y means regression.

6.2 Classification Problems in the Wild

6.2.1 Spam Detection

The email inbox is a classification stage: for each incoming mail, decide whether it is spam or non-spam. The class labels of this problem are "spam" and "non-spam."

Every message that arrives lands in exactly one of two buckets, and the decision is made by a model long before you see it. The training material is easy to gather at scale: users label messages by reporting spam or by letting a message sit in the inbox, so the data set naturally carries its answer column — exactly what supervised learning needs. The features used by modern spam filters include the sender address, header fields, word frequencies, links, and metadata such as whether the message arrived in a burst.

6.2.2 Malware Detection

An antivirus takes a test file and tells you whether it is a malware file or a benign file. Benign means a good file — one that is safe to run. The class labels are "malware" and "benign."

The file to be scanned is the input, and the output is a verdict. The training set is a large labelled collection of files: known malware samples on one side, known-clean files on the other. Because the model only predicts on a customer's machine and never modifies its own decision rule there, an antivirus deployment is a pure prediction pipeline — this is the same train-build-test-deploy rhythm that section 6.3 walks through in detail.

6.2.3 Cancer Detection

A system takes an image of a cell and predicts whether the cell contains a cancerous, malignant cell or a benign one. The class labels are "malignant" and "benign."

In medicine the cost of the two mistakes is not symmetric: missing a malignant cell is far more dangerous than flagging a benign cell for a second look. That asymmetry is one reason medical classifiers are judged with recall (section 6.7) rather than plain accuracy — the system must not let positive cases slip through. The input here is not a row of numbers but an image, which gets converted into a feature representation before classification.

6.2.4 What Unifies These Problems

All three are classification problems because none of them predicts a continuous value. Each predicts a class label: spam/non-spam, malware/benign, malignant/benign. That pattern is the test for whether something is classification: the answer is a label from a small set, not a number on a scale.

The three problems share the same skeleton even though the domains differ completely — email, executables, cells. Each has:

• Inputs $X$ — a message, a file, an image, converted into a feature vector;
• A small fixed set of labels $Y$ — exactly two classes in all three examples;
• A labelled training set — past messages, past files, past cells with confirmed diagnoses.

If you can write the answer column as two or more named categories, you are doing classification.

6.3 Training and Testing a Classifier

6.3.1 The Data Table: Features and Class Labels

Suppose you want to build an antivirus with a data mining algorithm. You start by gathering a tabular data set. The rows represent files: file 1, file 2, file 3, and so on. The columns hold features: attribute 1, attribute 2, attribute 3. The last column is the class label.

A domain expert built this table by hand: for file 1 he looked at the attributes, marked attribute 1 as 1 when present and 0 when missing, wrote numeric values such as 50 or 10 where they applied, and supplied the class label for the file. One means malware, zero means benign, a good file. Attribute engineering and label assignment are done by the domain expert, and the table is gathered over time.

Three roles are already visible in this table. The domain expert decides which attributes exist and what each file's label truly is. The features are the columns the model is allowed to look at. The class label is the answer column the model will learn to predict. Notice what the domain expert does not do: he does not decide how the features combine into a decision — that is the learning algorithm's job.

6.3.2 Splitting into Training and Test Data

As a data mining expert your first move is to take the table and divide it into two parts: train data, also called training data, and test data. You can do a random sampling over the rows, and each row lands in one part or the other. Train and test are mutually exclusive sets — a sample cannot appear in both. The proportion is chosen by convention, which we come back to when we discuss splits.

The split exists to enforce a basic honesty rule: the model must never be evaluated on data it has already seen. If you measured a model on its training rows, it would look brilliant even when it had merely memorized them. The test rows are held out precisely so that every row the model is scored on is a row it has never met.

6.3.3 Building the Model on the Training Data

The training data builds the model. Suppose you pick the decision tree classification algorithm and train it on the training data. In the classic table used here there are four columns: refund, marital status, taxable income, and cheat. Cheat is the class label; the other three are candidate attributes for building the tree.

By magic of this example, refund is the attribute that best tells you whether the case cheats, so refund sits at the top. The rule to remember: the attribute carrying the highest information goes at the top of the tree, and attributes carrying less information move toward the lower end. The leaves of the tree are always class labels.

A decision tree is a sequence of questions: at each internal node, split the training rows by one attribute, and keep splitting until the rows in a branch are (nearly) all of one class. The "information" the professor refers to is made precise by measures such as entropy or the Gini index — an attribute that separates the classes cleanly is information-rich and earns the top position. The leaves are class labels because a tree's final answer must be a verdict, not a split.

6.3.4 Testing the Tree and Deploying It

Once the tree is built, you test it with the data you held out.

This is the whole training-and-testing rhythm: train data builds the model, test data checks whether the model is good. If the accuracy is 50 percent, you modify or redraw the tree. If the accuracy is 95 percent, the tree is good enough and you can deploy it at the customer end for real-world use.

Real-world & domain connection. This train-build-test-deploy loop is how antivirus vendors ship signature-free detection: the model is trained on labelled malware collections and then runs on customer machines where it only predicts — it never learns, updates, or changes its own rules in the field. The same loop, with the same honesty rule about held-out data, appears in credit scoring, medical screening, and every other deployed classifier.

6.4 Performance Measures for Regression

6.4.1 The Model and the Per-Sample Error

In a regression problem you are given $X$ and $Y$, where $Y$ is continuous: $X_1,X_2,X_3$ with $Y_1,Y_2,Y_3$, and you want to build a function $H$ that takes an ${\mathbf{x}}_i$ and predicts $y_i$. Here ${\mathbf{x}}_i$ is the feature vector of test sample $i$, $y_i$ is the actual continuous value, and ${\hat{y}}_i=H({\mathbf{x}}_i)$ is the predicted value.

Many candidate functions may be available — one could come from a decision tree, another from linear regression — so you need a way to judge them. On the test data you know both the attributes and the true $Y$. You pass $X_1$ into the model; it predicts ${\hat{y}}_1$. If ${\hat{y}}_1$ equals $y_1$, the prediction was perfect and the error is zero. The per-sample error is the difference between prediction and truth:

$$e_i={\hat{y}}_i-y_i$$

The professor's words: "the error would be Y dash minus Y. Y dash is essentially what your model is predicting; Y is the actual class value." If the error is zero, the model is good and the journey can stop here. If the error is huge, you must rethink the model.

Notation: some texts write the error the other way round, $e_i=y_i-{\hat{y}}_i$. The sign convention is a choice — the professor uses predicted minus actual. Never mix the two in one calculation; and note that every squared or absolute version used below is identical under either convention, because $({\hat{y}}_i-y_i{)}^2=(y_i-{\hat{y}}_i{)}^2$.

6.4.2 Average Error over the Test Set

You do not judge the model on one sample. You pass all test samples through the model one by one and average the results. With $N$ the number of samples in the test set, the average error is:

$$\bar{e}=\frac{1}{N}\sum _{i=1}^N({\hat{y}}_i-y_i)$$

The verbal description: "average error would be one by N — the number of samples in your test set — and you iterate over all the samples in your test set." In words, this is: build the model on the training set, walk every test sample through it, subtract the predicted value from the original value, and average over all test samples. The result is a single number that tells you how far the model's predictions sit from the truth on average.

6.4.3 Sum of Square Errors

There is another famous quantity in regression problems: the sum of square errors, SSE. It squares the same difference you already have:

$$\text{SSE}=\frac{1}{n}\sum _{i=1}^n({\hat{y}}_i-y_i{)}^2$$

Math reconciliation. The professor described this formula verbally as "one by n y dash minus y square". That spoken form — squared difference averaged over the samples — matches the average squared error as written in the reference text (Sharda et al., Eq. 5.4: $e^2=\frac{1}{n}\sum (y_i-{\hat{y}}_i{)}^2$). The name "sum of square errors" usually refers to the same quantity without the $1/n$: ${\sum }_{i=1}^n({\hat{y}}_i-y_i{)}^2$ (Tan et al., Eq. D.4). The two differ only by the factor $n$: $\text{SSE}=n\cdot \overline{e^2}$. We keep the professor's averaged form here — it is the form he stated and the one the exam follows — and note that when textbooks write "SSE" without $1/n$, they mean the plain sum, which is the same quantity scaled by $n$.

Why square? Two reasons.

Reason 1 — make large errors stand out. As the error grows, its absolute value should grow so that large errors are highlighted. A linear, absolute-value function keeps a linear relationship, so a big error and a medium error look similar in size. Squaring changes that: think of one squared, ten squared, and hundred squared. One squared stays one, ten squared jumps to a hundred, and hundred squared explodes to ten thousand — the largest errors dominate, exactly what you want to spot.

Reason 2 — remove the sign. Squaring handles negative values, since a negative difference becomes positive. Recall the worked example above: errors of $-20$ and $+10$ cancelled in the plain average. After squaring, $-20$ contributes 400 and $+10$ contributes 100 — both push the total up, so "wrong is wrong" regardless of direction. This is the "sign bias" the reference text calls out: without squaring, positive and negative errors can hide each other.

The root mean square, RMSE, is the same idea with a root added:

$$\text{RMSE}=\sqrt{\frac{1}{n}\sum _{i=1}^n({\hat{y}}_i-y_i{)}^2}$$

Math reconciliation. The professor described the root mean square in words — "square function or under root function" — without writing a formula. The standard form, confirmed in the reference texts, is exactly the square root of the averaged squared error above. RMSE answers in the same units as $Y$: if prices are measured in thousands of dollars, RMSE is in thousands of dollars too, which makes it the easiest number to interpret.

Both the square and the root serve the same purpose: they make bigger errors carry bigger values so the model's behaviour is visible. This is how you measure the performance of any regression model.

Visual intuition. Picture the errors as a number line with zero in the middle: errors on the left are under-predictions, on the right over-predictions. The plain average error is the balance point of those signed distances — a beautiful balance can hide terrible misses. Squaring folds the negative side onto the positive side, so the picture becomes a "distance from zero" scale, and RMSE is the typical distance after weighting big distances more heavily. One-sentence takeaway: the average error tells you the direction of the bias, SSE/RMSE tell you the size of the misses.

Where do these measures sit in the bigger evaluation picture? RMSE and SSE give a score for continuous targets only; the scope rule below marks the boundary, and section 6.5 handles the label case with a completely different ruler.

Where students most often go wrong:

Real-world & domain connection. SSE and RMSE are the workhorses of continuous forecasting: energy traders score day-ahead electricity price forecasts with RMSE, central banks measure forecast error of inflation and GDP, and house-price models are judged in the same currency as the target (RMSE in dollars). When a vendor claims "our forecast is off by 12 dollars", that number is almost always an RMSE.

6.5 Performance Measures for Classification

6.5.1 The Error Function

In a classification problem, $Y$ holds class labels instead of continuous values. In a binary classification problem there are two classes, say 0 and 1, so the class-label column contains a mix of zeros and ones, with attribute columns before it and one row per file. You split into train and test by random sampling, build a model $H$, and $H(\mathbf{x})$ predicts a class label $\hat{y}$.

To measure performance you build a helper function $F$ that takes the prediction and the true label:

$$F(H(\mathbf{x}),y)=\{\begin{array}{ll}1& H(\mathbf{x})=y\\ 0& H(\mathbf{x})\ne y\end{array}$$

The verbal description: "F will return one when H of X is equal to Y — whatever class label you are predicting is the same as the original class label. It will return zero when you are predicting a class label that is not matching."

Math reconciliation. As spoken, $F$ returns 1 on a correct match — so $F$ is a correctness indicator: averaging $F$ over the test set gives accuracy. The error, however, must count the wrong predictions, so the error uses the complementary indicator that returns 1 on a mismatch. Both readings are needed, and the next subsection shows the mismatch version explicitly. Keeping the professor's $F$ as stated, we have $F=1$ when the prediction is right (this is the accuracy indicator), and the error indicator $1[H({\mathbf{x}}_i)\ne y_i]=1-F$ — the two are complementary, so error and accuracy always sum to 1 over the same test set.

6.5.2 Average Classification Error

The error of the classification model is the average of the indicator over all test samples:

$$\text{Error}=\frac{1}{N}\sum _{i=1}^{N}1[H({\mathbf{x}}_i)\ne y_i]$$

where the indicator $1[\cdot ]$ is 1 when the prediction disagrees with the true label and 0 when they agree, and $N$ is the number of test samples. In classification there is exact equality, never approximation: two labels either match or they do not. The professor's phrasing: "error of your classification model would be one by N — the sum over all the test samples, giving H of X and Y."

The professor's mental model of the sum: if you pass one test sample and the result is 1, that one prediction was wrong; with a large test set you sum the ones and divide by $N$ to get the average error — in other words, the error is simply the fraction of test samples the model misclassified.

6.5.3 Why SSE Does Not Apply to Classification

The professor's terminology contrast: regression errors are measured (how far apart are two numbers), classification errors are counted (how many labels disagree). Squaring is a scaling operation on a numeric distance; if no numeric distance exists between labels, there is nothing to square. Even when labels are encoded as numbers (0 and 1), the encoding is arbitrary bookkeeping — subtracting 1 minus 0 produces a number that carries no information about how wrong the model was.

Real-world & domain connection. The indicator error (equivalently, accuracy) is what vendor benchmarks quote for deployed classifiers — a spam filter that is wrong 1% of the time, a face-recognition system with 99.9% match rate. In high-stakes domains the count is usually broken down further: a cancer-screening model can be "98% accurate" and still fail badly on the rare malignant class, which is why sections 6.6–6.7 split the count into the four cells of the confusion matrix.

6.6 Confusion Matrix and Accuracy

6.6.1 Building the Confusion Matrix

The confusion matrix is a performance measure heavily used in the field, and it is built for the test data. Take the antivirus example with two classes: malware is the positive class and benign is the negative class. On the y-axis you write the true labels — what the correct label of each sample actually is, already available in the test data. On the x-axis you write the predicted labels — what the model $H(\mathbf{x})$ produced.

The matrix then has four cells:

• True positive (TP): the model predicted positive, and the true label was positive. Correct prediction.
• True negative (TN): the model predicted negative, and the true label was negative. Correct prediction.
• False positive (FP): the model predicted positive — it flagged the file as malware — but the true label was negative, a benign sample. Wrong prediction.
• False negative (FN): the model predicted negative, but the true label was positive, an actual malware file. Wrong prediction.

True positive and true negative are the correct predictions of the model; false positive and false negative are the incorrect predictions.

Vocabulary check. False here does not mean "fake" — it means wrongly: a false positive is a prediction of positive that was false (the sample was not positive), and a false negative is a prediction of negative that was false (the sample was not negative). A true positive is a positive prediction that was true.

Visual intuition. Draw the matrix as a square table: the row labels are the true labels (the professor's y-axis), the column labels are the predicted labels (the x-axis). The top-left to bottom-right diagonal holds TP and TN — the correct predictions — and the opposite diagonal holds FP and FN — the mistakes. When you are asked about the confusion matrix later, this is the axis structure to draw first: true labels on one axis, predicted labels on the other. A good classifier puts almost all the mass on the diagonal; a confused one spills mass into the off-diagonal cells.

6.6.2 Accuracy

$$\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}$$

So accuracy answers: of everything the model predicted, what fraction was right? Applied to the worked example above:

$$\text{Accuracy}=\frac{6954+2588}{10,000}=\frac{9542}{10,000}=0.9542$$

Accuracy = 95.42% — 9542 of every 10,000 decisions were correct. Notice this matches the complementary relationship from section 6.5: the 46 + 412 = 458 mistakes give error $458/10,000=0.0458$, and $0.9542+0.0458=1$.

6.6.3 Extending the Matrix to More Classes

For $m$ classes the matrix becomes $m\times m$: one row per true class, one column per predicted class, and $m$ cells on the diagonal — the correct predictions — with $m^2-m$ off-diagonal cells for the different ways to be wrong. In a five-class matrix, cell $(i,j)$ counts the samples of true class $i$ that the model predicted as class $j$. The diagonal stays the good news; the off-diagonal cells now tell you which pairs of classes get confused with each other — for example, "malignant" being frequently predicted for "benign" cells is a different and more dangerous confusion than the reverse.

Real-world & domain connection. Confusion-matrix reasoning runs through every deployed classifier: antivirus vendors tune their products between false alarms (FP) and missed malware (FN), medical screening regulators report both the missed-cancer rate (FN) and the false-positive rate (FP), and credit-card fraud teams balance blocking fraud (TP) against annoying customers with declined cards (FP). The four cells are also the input to cost-benefit analysis — in medicine an FN typically costs far more than an FP, a fact that single-number accuracy cannot express.

6.7 Precision, Recall, and Related Measures

6.7.1 Precision: Positive Predictive Value

$$\text{Precision}=\frac{TP}{TP+FP}$$

Precision is also called the positive predictive value (PPV). The professor's caution about this definition: the obvious answer "how many correct predictions" is wrong because it mixes both classes; precision looks only at the positive column of the matrix — the predictions the model actually made in the positive direction.

Why the students' answers missed: "how many correct predictions" counts TP and TN together (that is accuracy, not precision); "detecting negative among positive" inverts the classes; "predicting the same results" describes consistency, not correctness. Precision is narrower than all three: it deliberately ignores every negative prediction.

6.7.2 Negative Predictive Value

By symmetry, the negative predictive value asks: out of all the negative predictions you made, how many were correct? The correct ones are TN, and the total negative predictions are FN plus TN:

$$\text{NPV}=\frac{TN}{FN+TN}$$

The symmetry is exact: precision divides the correct positive predictions by all positive predictions; NPV divides the correct negative predictions by all negative predictions. If precision is "when the model said malware, was it malware?", NPV is "when the model said benign, was it benign?"

6.7.3 Recall: Sensitivity, True Positive Rate

Recall looks at the other axis of the matrix. Precision asked about predictions you made; recall asks about the positive samples that actually exist in the data set. Out of all positive samples in the data set, how many did you detect properly? In the malware context: the test set contains 500 malware files; how many of those 500 did you actually catch?

$$\text{Recall}=\frac{TP}{TP+FN}$$

Recall is also called sensitivity or the true positive rate. The distinction is worth restating because it is the classic confusion: precision asks, out of 500 malware predictions you made, how many were correct; recall asks, out of 500 malicious samples in your data set, how many you were able to detect.

The professor's one-line mental model: in recall you are looking into the y axis (the true-label rows), in precision you are looking into the x axis (the predicted-label columns).

When to pick which: use precision when a false alarm is costly (flagging benign files wastes a security team's time); use recall when a missed positive is costly (letting malware or cancer through).

6.7.4 True Negative Rate

The symmetric measure for the negative class is the true negative rate: out of all negative samples in the data set, how many did you predict properly?

$$\text{TNR}=\frac{TN}{TN+FP}$$

TNR is also called specificity. It is to NPV what recall is to precision: recall divides the correctly caught positives by all actual positives, TNR divides the correctly cleared negatives by all actual negatives. Where recall says "of all real malware, how much did I find?", TNR says "of all benign files, how much did I clear?"

6.7.5 F1 Score

The F1 score combines precision and recall into a single number:

$$F1=\frac{2\cdot \text{Precision}\cdot \text{Recall}}{\text{Precision}+\text{Recall}}$$

The professor's phrasing: "two into PPV — precision into recall — divided by precision plus recall." F1 is the harmonic mean of precision and recall — a style of average that punishes imbalance. A plain arithmetic average of precision and recall can look fine while one of the two is terrible: precision 1.0 with recall 0.0 averages to 0.5, but any system with recall zero has caught nothing, and F1 correctly returns 0. If either measure is low, F1 is pulled toward it — you cannot hide a weak side behind a strong one. In the extreme case where precision equals recall, F1 equals that common value; when they diverge, F1 sits below their arithmetic mean.

Exam note: expect to compute or explain this formula, and be ready to justify why a harmonic-style combination is used rather than a plain average — the answer is that the harmonic mean collapses to zero when either component is zero, so a model strong on one side cannot mask weakness on the other.

F1 is typically used in text-based analysis; when we reach that topic we will compare how accuracy, precision, and recall are measured there and why F1 might be a better performance measure than accuracy. For now, keep the formula.

6.7.6 Re-explaining Precision and Recall

Real-world & domain connection. Precision and recall define the operating point of real systems. Search engines report recall as "how many of the relevant documents did we return" and precision as "how many of the returned results are relevant"; medical screening optimizes recall (do not miss a cancer) at the price of precision (more false alarms); fraud teams do the reverse arithmetic on the cost of false blocks. In text analysis — the professor's flagged use case — F1 is the standard headline number precisely because both kinds of failure matter there.

6.8 Train-Test Splits and Cross-Validation

6.8.1 Acceptable Split Ratios

There is no thumb rule for the train-test ratio, but the community accepts three values: a 60/40 split, a 70/30 split, and an 80/20 split, where the first number is the training share. 70/30 is the most accepted value. The choice depends on your use case: if you want more testing, use 60/40; if you want less testing, use 80/20.

The trade-off behind the numbers: more training data gives the model more to learn from, while more test data gives a more reliable performance estimate. 70/30 is the community's default because it balances both. With 60/40 you accept a slightly weaker model to get a sharper verdict on it; with 80/20 you prioritise learning over measuring.

6.8.2 Train-Validate-Test

A second version divides the data into three parts: train, validate, and test.

• Train trains the model.
• Validate is part of the training process: it helps you improve the model. If your tree looks like it is chasing noise, the validation set tells you to delete a branch, increase the height of the tree, add a node, or remove a node.
• Test then checks the fine-tuned model.

The key distinction: the validation set participates in model selection and tuning — you look at it, decide to prune a branch or add a node, and re-train — while the test set stays untouched until the very end. If you tune until the validation accuracy is high, the validation set has leaked its information into the model; the test set is the only measurement that is still unbiased. Both the two-way split and the train-validate-test split exist in the literature.

6.8.3 Cross-Validation

The single random split has a hidden assumption: that the distribution of data in the train set and the test set stays the same. Random sampling usually preserves the distribution, but sometimes it does not — sometimes the distribution between the train and test sets ends up different. When that happens, the model was built on a train set with a different distribution than the test set, and the test set no longer gives proper performance measures. Cross-validation solves this.

Take three-fold cross-validation. Divide the data set into three parts:

• Iteration 1: parts one and two are the train set and part three is the test set; measure the accuracy.
• Iteration 2: parts two and three train and part one tests; measure accuracy.
• Iteration 3: parts one and three train and part two tests; measure accuracy.

Finally average the three accuracies:

$$A_{cv}=\frac{1}{k}\sum _{j=1}^k{A}_j$$

Math reconciliation. The professor described the averaging verbally — "average the accuracy here, all the three divided by three" — and the fold-indexed formula above is the direct reconstruction of that description. The reference texts agree on the averaging for this kind of estimation (the accuracy estimate is taken as the average of the accuracies from each iteration); some texts compute the pooled alternative — total correct predictions across all folds divided by the total number of samples — which differs slightly but is the same idea. We keep the professor's averaged form, the one his exam follows.

Visual intuition. Picture the data set as a strip of 900 cells sliced into three equal bands. In each iteration one band is shaded (test) and the other two are training; the shading slides across the strip one band at a time. After three iterations every cell has been shaded exactly once — the "each part gets tested once" property is the whole point of the picture. One-sentence takeaway: cross-validation rotates the test role through the whole data set, so no subset is ever over-represented in training or in testing.

The idea is to make the distribution of the train and test sets uniform. Even if the data is not uniformly distributed, every part gets used as the test set exactly once, and each iteration has a different train-test combination. In general, n-fold cross-validation divides the data into n parts, uses n minus one parts for training and one part for testing, repeats the exercise n times, and averages the values. Five-fold means five parts and five iterations with a different test set each time; seven-fold means seven parts and seven iterations.

The misconception behind the first question: students picture the folds as a sequence and suspect the ordering matters. It does not — the folds are sets, and what matters is which combination is used for training and which single part for testing in each iteration. The second question tightens the same point: the fix for distribution drift is not clever ordering but rotation plus averaging.

Real-world & domain connection. k-fold cross-validation is the standard protocol in model selection pipelines: scikit-learn-style workflows grid-search hyperparameters inside k-fold loops precisely so that the reported score is not an artifact of one random split. In industry the same idea appears as "time-series aware" variants for fraud and churn models, where folds must respect time ordering, and in academic papers the phrase "10-fold cross-validation" is the default claim of evaluation honesty.

6.9 Issues in Classification Methods

6.9.1 Accuracy and Speed

When you judge a classification method, accuracy is the headline: how many correct predictions you make. Precision and recall are more measures you can use on top. Speed is a second issue, measured in two directions:

• Training time — how quickly you build the model.
• Test time — how quickly you predict.

The k-nearest neighbor classifier has absolutely zero training time but very high test time: it stores the training data and does nothing at build time, then at prediction time it must scan and compare against (a large fraction of) the stored samples for every new input. Decision tree and naive Bayes sit on the other side: high training time and comparatively low test time — building the tree or estimating the probabilities is the expensive step, after which each prediction is a short walk down the tree or a small product of probabilities.

In the antivirus context the trade-off is concrete — how quickly can you build the model and deploy it on a machine (train time), and how quickly can the deployed model scan an entire computer (test time)? A classifier that scans a 100 GB disk by comparing every file to every training sample is unusable at the customer end, however accurate; a classifier that cost a day of training to build is fine, because training happens once in the lab.

6.9.2 Robustness

Robustness means how well your model handles noise and missing values in the data. Noise can enter by mistake, or it can be added deliberately with bad intentions: an attacker deliberately injects noise into a system to reduce the performance of a classification model. Defending against that kind of adversarial noise is an active research area. If a model folds when 5 percent of its inputs are corrupted, it cannot handle noise.

Real-world & domain connection. Adversarial noise is not theory: image classifiers can be fooled by imperceptible pixel perturbations, spam filters are probed with obfuscated text, and malware detectors face attackers who deliberately pad or mutate files so the feature values shift. Robustness research — training with corrupted inputs, adversarial training, anomaly-aware pipelines — is one of the professor's flagged thesis directions.

6.9.3 Scalability

Scalability asks how the solution behaves as the data grows. A method may build a decision tree quickly and effectively on a small data set; the question is whether it still builds a good tree quickly when you hand it a huge data set.

A method that is fine for 10,000 rows can become infeasible at 10 million rows if its training cost grows quadratically with the sample count, and a method that produces good trees on tidy data may degrade as the volume forces approximations. The scaling question is separate from accuracy: a method can be both accurate and unscalable, or scalable and weak.

6.9.4 Interpretability and Explainability

Interpretability means how well you can explain your results. The model is a function $H(\mathbf{x})$ that outputs $\hat{y}$, but in most places where these models are applied — malware detection, medical decisions, spam detection — you must be able to explain why the decision was reached. If the process is a black box, nobody will buy your model or your solution. Explainability research — making models that can justify their decisions — is currently a hot topic.

The distinction inside this issue: a decision tree is interpretable by construction — every prediction is a readable chain of questions (refund = no, married → "does not cheat") — while deep or ensemble models explain little about why they fired. When a doctor asks "why did the system flag this cell?", "because a 0.93 score exceeded a threshold" is not an answer; explainability research exists to produce the missing justification.

6.9.5 Fairness and Goodness of Rules

Fairness asks how fair your model is: whether it treats groups evenly or quietly discriminates. Other measures include the goodness of rules, the size of the tree, and the compactness of the tree, which we will revisit when we study the models in detail. These issues — robustness, interpretability, explainability, fairness — are the current research buzzwords. If you want to work on a thesis in this area, that is the direction to pick; building a classification model itself is considered routine these days.

Real-world & domain connection. These issues map to regulatory reality: European and other AI regulations require explainability for high-risk decisions, banks must show fair treatment across demographic groups in credit models, and antivirus vendors publish not just detection rates but false-alarm trade-offs. "Goodness of rules" and tree size, as the professor notes, return when the course studies the models themselves — they are the compactness criteria that make a learned rule set auditable.

6.10 Overfitting and Underfitting

6.10.1 Underfitting: The Straight-Line Limit

Take a binary classification problem with two classes drawn in a plane — say a blue class and a red class. Your classifier is restricted to drawing a straight line, not even a curve: the $H(\mathbf{x})$ you build can only separate the plane with a line.

Any straight line leaves many red samples on the blue side and many blue samples on the red side, so the model's performance is poor. This is underfitting.

Underfitting means the classification algorithm was not good enough to learn the complete data. The data set is complex and spread out, and the limited hypothesis space could not divide it properly, which produces a lot of error. The model is not learning the data; there is too much error left over.

The professor's analogy. The straight line is the defining image: the data forms interlocking clusters, and no single line — wherever you draw it — can separate them. The model is not making a subtle mistake; it was never able to represent the pattern, like trying to draw the coastline with a ruler. The professor's line: in one direction you learn nothing (underfitting).

6.10.2 Overfitting: Learning the Noise

Now build a very complex classification boundary that winds around every point, separating the two classes exactly. This is overfitting: the model learns all the minute details of the data set — and that includes noise.

The classic tell is an isolated red point sitting deep in the blue zone. It is very different from the rest of the data points, and it is probably a noisy point, a measurement that was not gathered correctly. The ideal model should not learn such points.

Overfitting means over-learning: you gather as much information as you can, including the minute details that are actually noise. The professor's summary: in one direction you learn nothing (underfitting); in the other you learn everything, details and noise alike (overfitting). What you want is a model in the middle that learns the general statistics of the data, not the accidental details.

Analogy from daily life. Overfitting is the student who memorizes the textbook's example answers instead of learning the method: they ace the examples they have seen and fail every unseen question, because what they stored was the accidents of the examples, not the pattern. The isolated red point is exactly such an accident — it belongs to the blue region in general, and a well-generalizing model treats it as a fluke.

Real-world & domain connection. Overfitting is the plague of real deployments: a credit model trained until it recognizes every historical applicant will collapse on new applicants, an antivirus that memorizes its training samples misses every novel malware variant, and medical models that chase noise in imaging data fail in the clinic. The generalization problem — separating signal from accident — is the core reason train-test splits and cross-validation (section 6.8) exist at all.

6.10.3 The Error-Complexity Tradeoff

This graph appears again and again in machine learning, so it is worth understanding once, deeply.

• On the x axis is model complexity — a simple straight line on the left, then curves, then very complex boundaries on the right.
• On the y axis is error.

For the train set: when the model is very simple, train error is high; as complexity grows, train error falls steadily and eventually becomes zero, because a complex model memorizes the training data.

For the test set: when the model is very simple, test error is high; as complexity grows, test error falls to a minimum in the middle; beyond that it climbs again.

Underfitting is the left region, where both train and test errors are high. Overfitting is the right region, where train error is very low but test error is very high. The right place for the model is the middle, where test error bottoms out.

error
  |
  |        train error ______
  |                        \  (falls to ~0 on the right)
  |     test error  ___..--''''''--..__
  |                 /  falls to a       \  (climbs again: overfitting)
  |  underfitting  /   minimum here      \
  |  (both high)  +________________________\______  model complexity
  |                                     ^
  |                           sweet spot (lowest test error)

Reading the graph: the train curve is a monotone descent — complexity always helps the training score, so train error can never tell you that you overfit. The test curve is the honest one: it falls, bottoms out at the sweet spot, then rises. The gap between the train and test curves is the signature of overfitting — at the far right the model scores zero on training data while the test error climbs.

The same story in decision-tree terms: a tree with only one node — depth one, just a root — cannot learn anything, so train error is high. As you add nodes, train error drops, and a tree of depth 500 can reach zero train error. The test set follows the same curve as before: it starts high, improves, then worsens as the tree keeps growing. You want to stop in the middle.

Exam Guidance Summary

• The performance-measures block is extremely important. A common interview and exam probe is "what is the recall value?" — be ready to give the number and, more importantly, to explain the significance of that number. Remembering the formula will not help; understanding what each measure means is what counts.
• Be ready to contrast precision and recall with the axis intuition: precision looks at the x axis (predicted labels), recall at the y axis (true labels). Expect questions on accuracy, the four confusion-matrix cells, precision, recall, the true negative rate, and F1.
• For F1, be ready to justify the harmonic-style combination: the harmonic mean collapses toward zero when either precision or recall is low, so a model strong on one side cannot mask weakness on the other — a plain average can.
• The error-versus-model-complexity graph will appear again and again. Know the underfitting region (train and test error both high), the overfitting region (train error low, test error high), and where the model should sit (the sweet spot where test error bottoms out).
• Expect the train-test split conventions (60/40, 70/30, 80/20), the role of the validation set, and the mechanics of cross-validation: n folds, n minus one parts train, one part tests, accuracies averaged.
• Remember the classification-versus-regression test (discrete Y versus continuous Y) and the supervised-versus-unsupervised test (labels known versus unknown) — both are frequent short questions.
• For a thesis or project, the current research directions are robustness, interpretability, explainability, and fairness; building a classifier is considered routine.

Key Industry Applications

• Weather prediction, tsunami detection, and credit card fraud detection are supervised prediction systems in production.
• Petrol, oil, and gold price prediction are regression deployments in finance and energy.
• Spam filtering is classification running inside every email inbox.
• Antivirus and malware detection are classification systems: models trained on labelled malware collections, deployed to scan machines, with file-header attributes used even for empty files.
• Cancer detection from cell images is classification in medicine, predicting malignant versus benign cells — where recall (catching every malignant cell) matters more than avoiding false alarms.
• In industry, k-nearest neighbor is chosen when training time must be zero; decision trees and naive Bayes are chosen when fast prediction matters.
• The F1 score is the standard performance measure in text-based analysis.
• RMSE is the standard forecast-error currency in continuous domains: energy markets, economics, and pricing models all report error in the units of the target.
• Cross-validation is the standard evaluation protocol in model-selection pipelines, with time-aware variants in fraud and churn modelling.
• Adversarial robustness — noise added deliberately to break classifiers — is an active research field, as are explainable models, because customers will not buy a black box.