Final thoughts on K Nearest Neighbors

Welcome to the 19th part of our

Machine Learning with Python tutorial series

. We're going to cover a few final thoughts on the K Nearest Neighbors algorithm here, including the value for K, confidence, speed, and the pros and cons of the algorithm now that we understand more about how it works.

After performing a test of 100 samples, the average accuracy of the Scikit-Learn neighbors.KNeighborsClassifier classifier compared to our custom-made classifier was identical, with 0.97, or 97%, accuracy. Don't go patting yourself on the back through, since this algorithm is so very simple and basic. The real value in a K Nearest Neighbors classifier code is not so much in the accuracy, that's a given, it's in the speed. The main downfall of the K Nearest Neighbors classifier is indeed the speed with which you can perform the operations.

The speed, per round of the Scikit-Learn version of KNN was 0.044 seconds, vs our 0.55 seconds, per classification. Thus, while we achieved identical results, we're significantly slower than Scikit-Learn. The good news is, if you are curious how they do it, you can view the source code! We also mentioned that we'd discuss one major way to speed things up overall as well. K Nearest Neighbors doesn't actually have much in the way of training. The training is simply loading points into memory. You could keep the training data in memory, but the real pain point for the K Nearest Neighbors classifier is comparing to every point to find the closest one. Then, what happens when you have say 1,000 datasets that you're attempting to classify? Yikes! One option for us is to use threading. There's no benefit to running this all linearly, ie: 1 after another. Our method has us doing that, using only a tiny bit of our processing power overall. Instead, we can probably calculate at least 100-200 of these at the same time even on a cheap processor. If you want to learn how to thread, check out this threading tutorial. With Scikit-Learn, the KNN classifier comes with a parallel processing parameter called n_jobs. You can set this to be any number that you want to run simultaneous operations for. If you want to run 100 operations at a time, n_jobs=100. If you just want to run as many as you can, you set n_jobs=-1. Learn more about the options at your disposal by checking out the Nearest Neighbors documentation. There are ways of only comparing your data to data within a certain radius. If you are interested in speeding up KNN to be more similar to the Scikit-Learn version, you may want to look into that first.

Finally, one last point I will make is on actual prediction confidence. There are two ways to measure confidence. One way is by comparing how many examples you got correct vs incorrect in the testing stage, but, another way, is by checking the vote percentage. For example, your overall algorithm may be 97% accurate, but on some of the classifications the votes may have been 3 to 2. While 3 is the majority, it's only 60% vote rather than 100% which would be ideal. In terms of telling someone whether or not they have breast cancer, like the automatic car differentiating between a blob of tar and a child in a blanket, you probably prefer 100%! Thus, in the case of 60% vote on a 97% accurate classifier, you can be 97% sure that you are only 60% certain about your classification. It's totally possible that this 60% vote is responsible for part of the 3% that was inaccurately measured.

Alright, so we just wrote our own classifier that has 97% accuracy, but doesn't perform well on everything. K Nearest Neighbors is very useful since it performs well on both linear and non-linear data. The main downfall is in scale, with outliers, and with any bad data (recall our useless inclusion of the ID column).

Sticking with supervised machine learning, specifically classification, we're going to cover the Support Vector Machine next. Ending code:

import numpy as np
from math import sqrt
import warnings
from collections import Counter
import pandas as pd
import random

def k_nearest_neighbors(data, predict, k=3):
    if len(data) >= k:
        warnings.warn('K is set to a value less than total voting groups!')
    distances = []
    for group in data:
        for features in data[group]:
            euclidean_distance = np.linalg.norm(np.array(features)-np.array(predict))
            distances.append([euclidean_distance, group])

    votes = [i[1] for i in sorted(distances)[:k]]
    vote_result = Counter(votes).most_common(1)[0][0]
    confidence = Counter(votes).most_common(1)[0][1] / k
  
    return vote_result, confidence


df = pd.read_csv("breast-cancer-wisconsin.data.txt")
df.replace('?',-99999, inplace=True)
df.drop(['id'], 1, inplace=True)
full_data = df.astype(float).values.tolist()
random.shuffle(full_data)

test_size = 0.4
train_set = {2:[], 4:[]}
test_set = {2:[], 4:[]}
train_data = full_data[:-int(test_size*len(full_data))]
test_data = full_data[-int(test_size*len(full_data)):]

for i in train_data:
    train_set[i[-1]].append(i[:-1])
    
for i in test_data:
    test_set[i[-1]].append(i[:-1])

correct = 0
total = 0

for group in test_set:
    for data in test_set[group]:
        vote,confidence = k_nearest_neighbors(train_set, data, k=5)
        if group == vote:
            correct += 1
        total += 1
print('Accuracy:', correct/total)

The next tutorial: Support Vector Machine introduction