A4.2.3 · Data preprocessing
Dimensionality reduction
By the end you can
Explain the curse of dimensionality and why reducing the number of features makes models simpler, faster and less likely to overfit.
A in machine learning is just a feature. A customer table with age, income and city has three. A photo has one for every pixel, which can be millions. You might expect that more features always help, but past a point they hurt. The problems that arrive with large numbers of features are called the .
What goes wrong#
| Problem | What happens |
|---|---|
| Every extra feature multiplies the size of the space. With 10 ranges per feature, 2 features make 100 regions but 6 make a million. The same number of examples is spread so thinly that most regions have none. | |
| Distances lose meaning | In high dimensions nearly all points are about the same distance from each other, so “nearest neighbour” stops meaning something. k-NN and clustering suffer most. |
| Overfitting | With many features and relatively few examples, a model can find patterns that are only coincidences in the training set. |
| Computation and memory | Calculations and storage grow with the number of features, so training gets slow and may become impractical. |
| Visualisation | People can see only two or three dimensions, so patterns in a hundred are hard to spot. |
| Sample size | To keep the same coverage, the number of examples needed grows exponentially with the dimensions. |
Nearest ÷ farthest distance
0.30
Random points. Closer to 1 means near and far look alike.
Regions to cover (10 per feature)
100,000
Data needed to have a few examples in each region
Forty random points in a unit cube, and one query point. In two dimensions the nearest point is much closer than the farthest. By a thousand dimensions they are almost the same distance away, which is why nearest-neighbour methods struggle there.
How to reduce dimensions#
The aim is to . There are a few routes.
- Select the most informative existing features and drop the rest. This is feature selection (A4.2.2): remove the irrelevant, and the redundant.
- Combine features that say the same thing. If queue length and waiting time both measure how busy the canteen is, keep one, or merge them.
- Build new, fewer features from the originals so that most of the information is kept. Techniques such as principal component analysis (PCA) do this; both textbooks mention it, but the course does not ask you to carry out or explain the mathematics.
- Test different sets of features and keep the smallest one that predicts nearly as well as the full set.
Reducing dimensions is a trade: you give up some detail to gain speed, simplicity and reliability. Reduce too far and you throw away signal.
Check yourself
Dimensionality reduction
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
5 questions · 13 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Define dimensionality reduction.
[1]Define: Give the precise meaning of the term.
2.Explain what is meant by the curse of dimensionality.
[4]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.Outline three benefits of reducing the dimensionality of a data set.
[3]Outline: A brief account: the main points, without much detail.
4.To cover each feature with 10 equal ranges, a data set needs 10 to the power of the number of features regions. Calculate how many more regions are needed for 5 features than for 3.
[2]Calculate: Work out the number, showing the working.
5.A data set about school lunches has the features: type of food, price, colour of the food, temperature outside, length of the queue and waiting time. Suggest how the number of features could be reduced.
[3]Suggest: Put forward a sensible answer for the situation given, with a reason. There may be several good answers.
In a nutshell
- A dimension is a feature. Dimensionality reduction cuts the number of features while keeping the useful information.
- The curse of dimensionality: more features means sparse data, distances that stop meaning anything, overfitting, more computation and memory, and the need for far more data.
- Benefits: simpler and faster models, less overfitting, less storage, and data that can be visualised in two or three dimensions.
- Ways to reduce: select the best existing features (A4.2.2), merge features that say the same thing, or build a smaller set of new features that capture most of the information (for example PCA, which is named in the books but is beyond the course).