k-NN, SVM and Naive Bayes
Level 4 · Classic models
Three classic ways to sort examples into groups: by the nearest neighbours, by the odds, or by the widest gap. Plus how suggestions on film sites work.
Course contentsLesson 9 of 18
Level 1 · How a machine learns
Level 2 · Getting the data ready
Level 3 · Kinds of learning
Level 4 · Classic models
Level 5 · Neural networks
Level 6 · Better models, real tools
After this lesson you can
- Explain how k-NN picks a group
- Describe how Naive Bayes adds up clues
- Say what an SVM looks for
13 mincovers 4 glossary entries
Worth reading first: Classification vs Regression
Three classic ways to sort examples into groups
k-nearest neighbors, Naive Bayes and support vector machines are three classic ways to sort examples into groups. k-NN copies the nearest known examples. Naive Bayes adds up the odds from each clue. An SVM draws the widest gap between two groups. All three were in wide use long before deep learning.
k-nearest neighbors, or k-NN, keeps every training example. For a new one, it finds the k closest, where k is a small number like 5, and takes a vote. If 4 of the 5 nearest fruits are apples, the new fruit is an apple. It does no work in training and all its work when asked.
That makes k-NN easy to grasp, but slow on big data. Every question means measuring the distance to every stored row. Distance also needs scaled features. If income runs to 200,000 and age to 100, the nearest neighbours are picked almost by income alone.
A recommendation system often uses the same idea. Find people whose ratings look like yours, and suggest what they liked that you have not seen. One big film service has said its suggestions shape about 80% of the hours people watch. In 2009 it paid a 1 million dollar prize to a team that made its guesses 10% better.
Naive Bayes sorts by odds. For spam, it counts how often each word shows up in spam and in real mail. To sort a new email, it combines the odds from every word in it. It is called naive because it treats each word as if it had nothing to do with the others, which is false but works well.
It is fast and needs little data, which made it the classic spam filter. An essay from 2002 helped make this kind of spam filter popular. Its weak spot is words that only mean something together. It reads 'not good' as two separate clues.
A support vector machine, or SVM, splits two groups with the widest gap it can find. Only the points nearest the gap, called support vectors, decide where the line goes. A clever trick lets it draw curved borders too. Before deep learning, SVMs were among the most accurate models for many jobs, from text to faces.
The three side by side
| Model | How it decides | Good at | Weak at |
|---|---|---|---|
| k-NN | A vote of the k nearest examples | Small data, easy to explain | Slow on big data |
| Naive Bayes | Adds up the odds of each clue | Text, with little data | Clues that only count together |
| SVM | The widest gap between groups | Clear borders, many features | Millions of rows |
Which one to pick
- 1
Pick k-NN
When the data is small and you want to show which past cases led to each answer.
- 2
Pick Naive Bayes
When you sort text and have little data or little time.
- 3
Pick an SVM
When two groups have a clear border and you have thousands of rows, not millions.
Worked example
Emma sorts fruit at her stall
Emma's scale and camera measure each fruit's weight and colour. She has stored 300 fruits she already named.
A new fruit's 5 nearest stored fruits are 4 pears and 1 apple, so k-NN calls it a pear. Checking all 300 takes under a second.
The words for this lesson4
Check yourself
How does k-NN decide the group of a new example?
Finished this lesson?
Marking it complete also marks its 4 glossary entries learned, which updates your roadmap and your saved page. 0 are already marked.