k-nearest neighbours and naive Bayes

Warm-up

One question before the lesson. Choose an answer and check it.

Try it yourself

Drag the new student and change k. The k nearest students are circled, and their vote decides. Then measure study in minutes and watch the neighbours change, and standardise both inputs.

Practice problems

Work each problem out on paper, then type your answer and press Check. Every problem has hints and a full solution.

Programming exercise

Write k-nearest neighbours and a naive Bayes spam filter in plain Python. Save classify.py and test_classify.py in the same folder, fill in each function in classify.py, and run the tests:

python test_classify.py

"""k-nearest neighbours and naive Bayes: programming exercise. Write two classifiers in plain Python: k-nearest neighbours, which labels anew example by the vote of the k nearest ones, and a naive Bayes spam filterwith Laplace smoothing, worked in logs. Run the tests from this folder:     python test_classify.py A point is a list of numbers, such as [hours studied, hours slept]. A labelis 1 or 0: pass or fail, spam or not spam. An email is a list of words."""  def distance(a, b):    """Return the straight-line distance between points a and b: the square root of the sum of (a[i] - b[i]) squared."""    raise NotImplementedError  def nearest(points, query, k):    """Return the positions in points of the k points nearest to query, nearest first.     If two points are the same distance away, the one earlier in the list comes first.    """    raise NotImplementedError  def knn_predict(points, labels, query, k):    """Return the label the k nearest points vote for: 1 if more than half of their labels are 1, otherwise 0.     k is odd, so the vote of two labels cannot tie.    """    raise NotImplementedError  def standardise(values):    """Return each value standardised: (value - mean) / standard deviation.     Work out the standard deviation dividing by n, the number of values, as    scikit-learn's StandardScaler does.    """    raise NotImplementedError  def count_words(emails):    """Return a dictionary from each word to how many times it appears in all the emails together."""    raise NotImplementedError  def word_prob(word, counts, total, vocab_size):    """Return P(word | class) with Laplace smoothing: (count of word + 1) / (total + vocab_size).     counts is the class's dictionary from count_words, total is how many words    the class's emails have in all, and vocab_size is how many different words    all the training emails use. A word the class never saw has a count of 0.    """    raise NotImplementedError  def log_score(words, prior, counts, total, vocab_size):    """Return the class's log score for an email: ln(prior) plus ln P(word | class) for each word in it."""    raise NotImplementedError  def nb_predict(emails, labels, words):    """Train naive Bayes on emails and their labels (1 for spam, 0 for not spam), and classify words.     The prior of each class is its share of the emails. Return 1 if the spam    log score is higher than the other class's, otherwise 0.    """    raise NotImplementedError 

Stuck? sorted(range(len(points)), key=lambda i: distance(points[i], query)) lists the positions from nearest to furthest. math.log(x) is ln x. The Solution tab has one way to write each function.

In practice: neighbours and Bayes at scale

Finding neighbours fast. Comparing a query with every stored example takes time in proportion to how many there are, which is too slow for millions of them. Libraries build an index first: a k-d tree for a few inputs, or an approximate nearest-neighbour index such as FAISS or HNSW for embeddings with hundreds of numbers. The retrieval step of the AI applications in Module 7 is a nearest-neighbour search over embeddings, by cosine similarity.

Too many inputs. With hundreds of inputs, the distances between random examples all come out nearly the same, so the nearest neighbour is hardly nearer than any other. This is called the curse of dimensionality. kNN works best with a few inputs, or on embeddings trained so that distance means similarity.

Naive Bayes as a baseline. It trains in one pass of counting, needs little data and is hard to beat on short texts, so it is a good first model to compare anything fancier against. Its probabilities are poor, though: by treating words as independent it counts the evidence of words that go together more than once, and its chances come out too close to 0 or 1. In scikit-learn it is MultinomialNB, where alpha=1.0 is Laplace smoothing.

Test your knowledge

1. 01Why is k usually odd when there are two classes?Show answer

   So the vote cannot tie. With k = 4, two votes each way would leave the prediction undecided.

2. 02What happens with k = 1, and with k equal to the number of training examples?Show answer

   With k = 1 the model copies the nearest example, noise and all, so it overfits: its training error is 0. With k = n every new example gets the majority class, so it underfits. The best k is in between, chosen on a validation set.

3. 03Why must the inputs be scaled for kNN?Show answer

   Distance adds up the squared difference of every input, so an input measured in big units swamps the others. Standardising each input, (x − mean) ÷ standard deviation, makes a difference of 1 mean the same in every input.

4. 04What does “naive” mean in naive Bayes?Show answer

   It treats the words as independent once the class is known, so the probability of an email’s words is the product of each word’s probability. Real words are not independent, but the model often classifies well anyway.

5. 05Why does naive Bayes need smoothing?Show answer

   A word never seen in a class gets probability 0 there, and one 0 makes the whole product 0, whatever the other words say. Adding 1 to every count keeps every probability above 0.

Exit ticket

One last question on the main idea of the lesson.