IB COMPUTER SCIENCE | A4.3.2 Classification (HL)

Lesson objective

Explain how K-nearest neighbours and decision trees use labelled examples to predict discrete categories, including distance, voting, decision paths and limitations.

Learn

A4.3.2 | CLASSIFICATION (HL ONLY)

01 | THE ANSWER IS A LABEL

A sorting system receives an item and must decide which category it belongs to. It might predict “type A” or “type B”. Unlike predicting a duration of 14.6 minutes, the required answer is a category.

Classification is the prediction of a discrete class label from input features. In supervised classification, training examples pair their features with known labels, so the system can learn or use relationships between inputs and categories.

This HL lesson develops two approaches: K-nearest neighbours (K-NN) and decision trees. You will trace how each reaches a label, then consider recommendations and medical decision support as applications. The interactive data are fictional teaching examples.

02 | DISCRETE DOES NOT MEAN THE INPUTS MUST BE WORDS

The output is discrete because it is selected from separate categories. Examples include spam/not spam, a recognised digit from 0 to 9, or one of several document types.

The inputs can still be continuous measurements, such as width, mass or a numerical image descriptor. A classifier can read two measured numbers and output the category “type A”.

A numeric code can also represent a class. If 0 means standard handling and 1 means special handling, predicting a label of 1 is classification, not a claim that the outcome is a continuously measured quantity.

03 | LABELLED EXAMPLES PROVIDE THE SUPERVISION

Example Feature 1 Feature 2 Known class label
P1 2 2 Type A
P2 3 2 Type A
P3 2 4 Type A
P4 4 3 Type A
P5 7 7 Type B
P6 8 7 Type B
P7 7 9 Type B

Each row represents one known item. The two features are fictional comparable-scale descriptors on a 0–10 range. Their values are inputs; Type A or Type B is the known target label.

A new item has measured descriptors but no supplied target. The classifier uses the labelled examples to predict the missing label. It must not be given the true new label as an input.

These small groups make the reasoning visible. Real datasets can overlap, contain incorrect labels or omit important kinds of examples. The demonstration is not evidence that these categories are always separable.

04 | CLASSIFICATION IS DIFFERENT FROM CLUSTERING

Supervised classification uses predefined labels attached to training examples. The task is to predict one of those labels for an unseen example.

Clustering groups observations by similarity without using known target labels in the same way. A cluster discovered from data does not automatically have the meaning of a predefined class.

K-NN is not K-means. In K-NN, k is how many nearby labelled examples are consulted. In K-means, k specifies a requested number of clusters. Similar names do not make them the same process.

05 | K-NN: CONSULT THE NEARBY LABELLED EXAMPLES

K-nearest neighbours classifies a new item by finding the k training examples closest to it under a chosen distance rule. In the simple version here, each selected neighbour gets one vote, and the most common class is predicted.

The reasoning is that nearby examples in a useful feature representation may have similar labels. This depends on meaningful features, appropriate scales and representative training data. It is not a guarantee that the closest label is correct.

For k = 3, consult three examples, not three categories. Those examples may all have the same label, or the votes may be split between labels.

06 | WHAT DOES TRAINING MEAN FOR K-NN?

A basic K-NN fit retains the labelled training examples, together with any fitted preprocessing and possibly a search structure. It does not learn a single regression equation or a set of tree split rules.

Much of the classification work happens when a new query arrives: compare its coordinates, find neighbours and count their labels. This is often called instance-based or lazy learning.

“Lazy” does not mean no preparation is required. Cleaning, scaling, feature selection, search-index construction and choosing k can involve substantial work. The training examples and their labels remain essential to prediction.

07 | CALCULATE A DISTANCE ONE COORDINATE AT A TIME

For two comparable numerical features, a common rule is Euclidean distance: square the coordinate differences, add them and take the square root.

Use the new query Q = (3, 3). For P2 = (3, 2), the differences are 0 and 1, so distance = √(0² + 1²) = 1. For P1 = (2, 2), the differences are 1 and 1, giving √2 ≈ 1.414.

The class labels are not part of the distance calculation. First compare the input coordinates; then use the known labels of the selected neighbours to vote.

08 | SORT THE DISTANCES, THEN VOTE

Rank for Q = (3,3) Example Distance Known label
1 P2 1.000 Type A
2 P4 1.000 Type A
3 P1 √2 ≈ 1.414 Type A
4 P3 √2 ≈ 1.414 Type A
5 P5 √32 ≈ 5.657 Type B
6 P6 √41 ≈ 6.403 Type B
7 P7 √52 ≈ 7.211 Type B

With k = 3, the selected examples are P2, P4 and P1 under the stated tie policy. Their labels give Type A three votes and Type B zero, so the predicted class is Type A.

P1 and P3 are equally far from Q. This demonstration orders equal-distance candidates by their numeric example ID. That makes the cutoff reproducible. Other implementations can use different tie rules; document the rule rather than relying on accidental row order.

All selected labels agreeing does not establish certainty. A new query far outside the represented population can still receive a unanimous vote.

09 | CHANGING K CHANGES THE NEIGHBOURHOOD

With k = 1, a single nearest example determines the label. That can capture local detail but can also follow a mislabelled or noisy example.

A larger k considers a broader neighbourhood and can reduce sensitivity to one unusual example. However, it can smooth away a small genuine group or favour the more common class. Taking every training example eventually gives a global vote, ignoring where the query lies.

Choose k using appropriate validation. It is a hyperparameter, a configuration choice rather than a label learned from one new query. There is no universally best value.

10 | TIES, VOTES AND PROBABILITY

With two classes and equal-weight voting, an odd k avoids a tie in the class vote. It does not prevent equal-distance examples at the selection cutoff. With three or more classes, an odd k can still give a tied top vote, such as 1–1–1.

If the vote is tied, a classifier needs a stated policy, such as a defined priority or an abstain-and-review outcome. Different choices can change the predicted label. The interactive example uses two classes and allows only odd k, with IDs resolving distance ties.

A vote fraction such as 2 of 3 is not automatically a calibrated 66.7% chance that the label is correct. Distance-weighted K-NN is another variant, but the demonstration uses equal votes so the process is transparent.

11 | MOVE A QUERY AND INSPECT ITS NEIGHBOURS

Choose the two query descriptors and k. The plot highlights the selected neighbours and links them to the query. The table shows every distance and whether the example contributes a vote.

Try Q = (7, 7) with k = 1, 3 and 7. With all seven examples voting, the four Type A labels outweigh the three Type B labels even though the query lies in the Type B group. This illustrates why increasing k is not always an improvement.

12 | FEATURE SCALE CAN CHANGE THE NEIGHBOURS

If one input is mass in grams and another is width in metres, the numerical mass differences may dominate an unscaled Euclidean distance even when width matters. A change of units should not silently decide what “similar” means.

Fit appropriate scaling using training data, then apply the same transformation to validation, test and query inputs. Do not independently refit the scale on each query batch.

Scaling alone does not make irrelevant features useful. Many noisy dimensions can weaken distance comparisons, linking K-NN to feature selection and the curse of dimensionality. The demonstration starts with comparable-scale descriptors rather than mixing units.

13 | K-NN FOR RECOMMENDATIONS

A recommendation service can represent users through their recorded preferences, such as ratings of shared items. A neighbourhood-based collaborative filter identifies users with similar preference patterns, then uses their feedback to rank items the current user has not seen.

For example, similar users who liked the same science videos may provide evidence to recommend another video. Missing ratings need careful treatment: “not rated” is not necessarily a dislike. Similarity can be based on users or on items.

This is an application of nearest-neighbour ideas, not a requirement that every recommender use majority-vote classification. Recommendations may involve rating prediction or ranking. If the defined output is “likely to like” versus “unlikely to like”, that specific output is a categorical prediction.

14 | DECISION TREES: FOLLOW LEARNED QUESTIONS

A decision tree classifier predicts a label by asking questions about features. Start at the root, follow the branch matching the input and continue until a leaf provides the predicted class.

An internal decision node might ask “mass ≤ 2 kg?”. Its branches represent the possible answers. A leaf stores a class decision, often based on the labelled training examples reaching it.

Unlike K-NN, a fitted tree need not calculate distances to stored examples for each prediction. It uses learned tests. Classification trees output class labels; trees can also be used for regression, but that is a different response task.

15 | SEE THE LABELLED DATA BEHIND A SMALL TREE

Parcel Fragile? Mass (kg) Known handling class
T1 No 0.5 Standard
T2 No 1.5 Standard
T3 No 2.0 Standard
T4 No 2.5 Special
T5 No 3.0 Special
T6 Yes 1.0 Special
T7 Yes 2.0 Special
T8 Yes 3.0 Special

The inputs are fragile status and mass. The target is the historical handling label. This fictional example supplies a small tree consistent with these labels so you can trace its operation. It is not a real parcel policy.

The supplied tree first checks fragile status. If Yes, predict Special. If No, check whether mass is at most 2 kg: Yes predicts Standard; No predicts Special.

A real training procedure searches candidate tests using labelled data. It may choose a different but equally good first split. The interactive activity applies this supplied tree; it does not run a tree-training algorithm.

16 | VISUALISE THE TREE WITHOUT LOSING THE BRANCHES

ROOT | FRAGILE?

Inspect the parcel’s fragile input.

YES BRANCH

Predict Special

Training leaf: 3 Special, 0 Standard.

NO BRANCH

Mass ≤ 2 kg?

Inspect mass only after taking the No branch.

YES

Predict Standard

3 Standard, 0 Special.

NO

Predict Special

2 Special, 0 Standard.

At each node, follow exactly one matching branch. Do not visit every leaf or vote across all leaves. A leaf summarises the training examples that satisfy its complete path of tests.

The ≤ comparison includes equality. A non-fragile parcel weighing exactly 2 kg reaches Standard in this supplied tree; 2.1 kg reaches Special.

17 | TRACE A NEW EXAMPLE THROUGH THE TREE

New parcel First decision Next decision Prediction
Fragile Yes, mass 1.2 kg Fragile? Yes No further test Special
Fragile No, mass 1.8 kg Fragile? No Mass ≤ 2? Yes Standard
Fragile No, mass 2.0 kg Fragile? No Mass ≤ 2? Yes Standard
Fragile No, mass 2.7 kg Fragile? No Mass ≤ 2? No Special

A prediction follows one route from root to leaf. The first example reaches Special without needing a mass split. The last example requires both tests.

A real leaf need not contain only one class. If training examples reaching a leaf include three Standard and one Special, a majority-class leaf would predict Standard while retaining evidence that the label is not certain.

18 | RUN THE SUPPLIED TREE

Choose a fragile status and mass. The activity highlights the decision path in its explanation and reports the training counts in the reached leaf.

Try No with masses 2 and 2.1, then switch to Yes. The fitted rule will produce labels for masses beyond the training range of 0.5–3 kg too, but that does not demonstrate reliability there. No live data is collected or stored by this activity.

19 | HOW TRAINING CHOOSES QUESTIONS

Tree training considers feature tests and prefers splits that improve class separation under a defined criterion. A node containing mixed labels is less pure than a node containing only one class.

At the root of the example there are 3 Standard and 5 Special labels. Splitting on fragile status creates a Yes group of 3 Special and a No group of 3 Standard plus 2 Special. The Yes group is pure; the No group can be split further by mass.

Criteria such as Gini impurity or information gain quantify this separation. The key idea is that labels guide which questions are useful; the computer does not simply receive a hand-written flowchart as its learned model. The teaching tree above is supplied to make the resulting prediction process visible.

20 | DEPTH, OVERFITTING AND PRUNING

A deep tree can create many detailed rules, including rules that describe a noise point or a mislabelled training example. It may then fit training data very well but generalise poorly.

Limiting maximum depth or requiring enough examples in a leaf can reduce excessive detail. Pruning removes branches under a chosen procedure when their complexity is not justified. Too much restriction can also miss real patterns.

Depth and leaf-size settings are hyperparameters chosen using training/validation procedures. Training purity does not prove a leaf’s future predictions are certain, and the best depth is not a universal constant.

21 | DECISION TREES IN MEDICAL DECISION SUPPORT

A medical classifier can use measured features and recorded patient outcomes to predict a category. A tree provides a traceable sequence of tests, so a practitioner can inspect which observations led to a prediction.

For example, a research model might predict a labelled diagnostic category using symptoms and test results. Real validation must consider data quality, representative populations, class imbalance, missing measurements and the consequences of different errors.

A learned association is not medical proof. Such systems support appropriately qualified assessment rather than replace it. The parcel tree is deliberately non-medical: its thresholds and labels must not be interpreted as clinical guidance.

22 | COMPARE THE TWO CLASSIFIERS

Aspect K-NN classifier Decision tree classifier
How it predicts Find nearby training examples and combine their labels Follow learned feature tests to a leaf
What fitting retains Labelled examples, preprocessing and possibly a search index Learned split structure and leaf decisions
Scale sensitivity Distance can be strongly affected by feature scale Ordinary axis-threshold splits generally do not require scaling
Example configuration k, distance metric, voting weights Maximum depth, minimum leaf size, splitting settings
Typical challenge Prediction cost, noise, dimensionality and meaningful similarity Unstable or overly detailed splits; overfitting
Explanation Show selected neighbours, distances and votes Show the root-to-leaf decision path

Neither method is always better. Select a suitable representation and compare complete validated pipelines for the intended task. Tree thresholds still require consistent units even when numerical scaling is not essential to ordinary tree fitting.

23 | EVALUATE ON GENUINELY UNSEEN LABELLED EXAMPLES

Hold out labelled examples for evaluation, fit preprocessing on training data only and use validation for choices such as k or tree depth. Keep the final test set outside those decisions.

Compare predicted labels with the actual held-out labels. Counts of correct predictions are useful, but a common class can dominate a headline accuracy. Examine which classes are confused and which errors matter; the next lesson develops accuracy, precision, recall and F1 in more detail.

Avoid evaluating a basic one-neighbour classifier by asking it to predict the labels of the identical examples stored in its own training set. Its nearest neighbour may simply be itself. Keep related or duplicated records from leaking between train and test sets.

24 | CHECK THE REASONING, NOT JUST THE LABEL

A clear K-NN explanation follows the chain: useful input representation → distance calculations → select k neighbours → combine their known labels → predict a discrete class. A clear tree explanation follows: learned feature tests → one matching branch per node → reached leaf → class decision.

Use connectives: “The three nearest neighbours have Type A labels, therefore equal voting predicts Type A.” Or: “The parcel is not fragile, so the tree checks mass; mass is at most 2 kg, therefore it reaches Standard.”

Then explain a limit: “A unanimous local vote is not certainty because the training examples may not represent the new case.” For both methods, explain how the label is obtained and why evaluation on independent data is needed.

Further reading: neighbour classification and tie considerations and decision-tree complexity and overfitting.

MATCH THE CLASSIFICATION IDEA TO ITS ROLE

Terminology

Terminology

Classification

Predicting a discrete category label from input features.

Discrete outcome

An outcome selected from separate categories rather than a measured continuum.

Class label

The target category attached to a training example or predicted for a query.

Feature

An input attribute used to represent an example.

Labelled example

An observation paired with its known target category.

Supervised learning

Learning or fitting using examples with known target outcomes.

Binary classification

Classification between two target classes.

Multiclass classification

Classification among more than two mutually exclusive target classes.

Query

The new example whose label is to be predicted.

K-nearest neighbours

Classification using the labels of k nearby training examples under a chosen distance rule.

k

The configured number of neighbours consulted, not the number of classes.

Euclidean distance

The square root of the sum of squared coordinate differences.

Equal-weight voting

Each selected neighbour contributes one vote for its label.

Distance tie

Two candidate neighbours have equal distance, requiring a defined cutoff policy.

Vote tie

Two or more classes share the highest vote count, requiring a defined decision policy.

Instance-based learning

Prediction based on retained training examples rather than a single fitted equation.

Feature scaling

Transforming input magnitudes consistently so numerical scale does not unintentionally dominate.

Hyperparameter

A configuration choice such as k or maximum tree depth.

Collaborative filtering

Recommendation using patterns in users’ feedback or interactions, often via user/item similarity.

Decision tree classifier

A model predicting a class by following learned feature tests to a leaf.

Root

The first decision node in a tree.

Decision node

A point in a tree containing a test of an input feature.

Branch

A route corresponding to a result of a decision test.

Leaf

A terminal node providing a class decision or class counts.

Class purity

How concentrated a node’s examples are in one label.

Tree depth

The number of decision edges along a path; maximum depth limits tree detail.

Pruning

Removing tree branches under a chosen procedure to control unnecessary complexity.

Overfitting

Fitting training-specific detail that does not generalise reliably.

Generalisation

Performance on genuinely new examples from the intended population.

Data leakage

Use of information that should not legitimately influence fitting, tuning or evaluation.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which are classification outputs?
2. Which describe supervised classification?
3. Which describe K-NN?
4. For Q = (3,3) and k = 3 in the supplied data, which are correct?
5. Which are correct tie statements?
6. Which affect K-NN predictions?
7. For the supplied tree, which are correct?
8. Which describe tree training?
9. Which can help control tree overfitting?
10. Which are honest evaluation or application statements?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Explain how supervised classification predicts a discrete outcome.

2. Explain the K-NN process for Q = (3,3), k = 3 in the supplied dataset.

3. Calculate distances from Q = (3,3) to P2 = (3,2) and P1 = (2,2), then explain their order.

4. Explain why increasing k can help or harm classification.

5. Explain the difference between a distance tie and a vote tie.

6. Explain why preprocessing matters for K-NN.

7. Explain how nearest-neighbour ideas can support collaborative filtering.

8. Explain the prediction path for a non-fragile parcel with mass exactly 2 kg.

9. Explain how labelled data guide the creation of a decision tree.

10. Explain how tree complexity affects future predictions.

11. Explain one difference between K-NN and a decision tree at prediction time.

12. Explain why apparently strong training results do not establish reliable classification.

EXPLAIN IT | TWO WAYS TO REACH A LABEL

Explain how K-NN and a decision tree would predict categories from labelled examples. Use distances, neighbours and votes for K-NN, and learned tests, matching branches and leaves for the tree. Explain one representation or overfitting limitation for each and why independent labelled evaluation is necessary.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for A4.3.2 Classification (HL) is coming soon. Complete the matching task and written questions in your exercise book.