Implementing Your Own k-Nearest Neighbor Algorithm Using Python
A detailed explanation of one of the most used machine learning algorithms, k-Nearest Neighbors, and its implementation from scratch in Python. Enhance your algorithmic understanding with this hands-on coding exercise.
Getting the neighbours to vote on the class of the test points
Finally, using the nearest neighbours you just identified, you can get a prediction for the class of the test instance by majority voting - simply tally up which class comes up the most often among the nearest neighbours.
The [neighbour[1] for neighbour in neighbours] just grabs the class of the nearest neighbours (that's why it was good to also keep the training instance information in _get_tuple_distance instead of keeping track of the distances only).
Next up, Counter, which is a dictionary subclass, counts the number of occurrences of objects. Try out:
Then, the most_common method of Counter can be used to return tuples with the most common elements and their frequencies:
In a similar way, you can grab the classes of the nearest neighbours, tally up how frequently the different class labels occur, and then find the most common label. This most common label will be the class prediction of the test instance.
Running our algorithm
That's about it. Now, just string the data loading and these 3 primary functions together with a main method and run it. Let's set k equal to 5, i.e. look at the 5 nearest neighbours to do the classification of new test instances. Once the predictions for classes of test cases are made, it would be useful to get a report of how good our predictions are. You can get these summary statistics from scikit's accuracy_score and classification_score functions.
This method just brings together the previous functions and should be relatively self-explanatory. One potentially confusing point may be the very end of the script - instead of just calling main() to run the script, it is useful to instead first check if
Refinements
In this implementation, when trying to classify new data points, we calculated the distance between each test instance and every single data point in our training set. This is inefficient, and there exist alterations to kNN which subdivide the search space in order to minimize the number of pairwise calculations (e.g. see k-d trees). Another refinement to the kNN algorithm can be made by weighting the importance of specific neighbours based on their distance from the test case. This would allow closer neighbours to have more of an impact on the class voting process, which is intuitively sensible.
A separate point to keep in mind is that, although here we arbitrarily chose k=5, we could have chosen other values (which would influence accuracy, noise sensitivity, etc.). Ideally, k would be optimized by seeing which value produces the most accurate predictions (see cross-validation).
An excellent overview of kNN can be read here. A more in depth implementation with weighting and search trees is here.
Full script
The full script follows:
Want to learn more? Check out our two-day Data Science Bootcamp:
https://cambridgecoding.com/datascience-bootcamp
Bio: Natasha Latysheva is a computational biology PhD student at the MRC Laboratory of Molecular Biology. Her research is focused on cancer genomics, statistical network analysis, and protein structure. More generally, her research interests lie in data-intensive molecular biology, machine learning (especially deep learning) and data science.
Original. Reposted with permission.
Related:
Finally, using the nearest neighbours you just identified, you can get a prediction for the class of the test instance by majority voting - simply tally up which class comes up the most often among the nearest neighbours.
from collections import Counter # 3) given an array of nearest neighbours for a test case, tally up their classes to vote on test case class def get_majority_vote(neighbours): # index 1 is the class classes = [neighbour[1] for neighbour in neighbours] count = Counter(classes) return count.most_common()[0][0]
The [neighbour[1] for neighbour in neighbours] just grabs the class of the nearest neighbours (that's why it was good to also keep the training instance information in _get_tuple_distance instead of keeping track of the distances only).
Next up, Counter, which is a dictionary subclass, counts the number of occurrences of objects. Try out:
>>> Counter([7,7,7,6,6,9]) Counter({7: 3, 6: 2, 9: 1}) >>> Counter('bananas') Counter({'a': 3, 'n': 2, 's': 1, 'b': 1})
Then, the most_common method of Counter can be used to return tuples with the most common elements and their frequencies:
>>> Counter('bananas').most_common() [('a', 3), ('n', 2), ('s', 1), ('b', 1)]
In a similar way, you can grab the classes of the nearest neighbours, tally up how frequently the different class labels occur, and then find the most common label. This most common label will be the class prediction of the test instance.
Running our algorithm
That's about it. Now, just string the data loading and these 3 primary functions together with a main method and run it. Let's set k equal to 5, i.e. look at the 5 nearest neighbours to do the classification of new test instances. Once the predictions for classes of test cases are made, it would be useful to get a report of how good our predictions are. You can get these summary statistics from scikit's accuracy_score and classification_score functions.
from sklearn.metrics import classification_report, accuracy_score # setting up main executable method def main(): # load the data and create the training and test sets # random_state = 1 is just a seed to permit reproducibility of the train/test split iris = load_iris() X_train, X_test, y_train, y_test = cross_validation.train_test_split(iris.data, iris.target, test_size=0.4, random_state=1) # reformat train/test datasets for convenience train = np.array(zip(X_train,y_train)) test = np.array(zip(X_test, y_test)) # generate predictions predictions = [] # let's arbitrarily set k equal to 5, meaning that to predict the class of new instances, k = 5 # for each instance in the test set, get nearest neighbours and majority vote on predicted class for x in range(len(X_test)): print 'Classifying test instance number ' + str(x) + ":", neighbours = get_neighbours(training_set=train, test_instance=test[x][0], k=5) majority_vote = get_majority_vote(neighbours) predictions.append(majority_vote) print 'Predicted label=' + str(majority_vote) + ', Actual label=' + str(test[x][1]) # summarize performance of the classification print '\nThe overall accuracy of the model is: ' + str(accuracy_score(y_test, predictions)) + "\n" report = classification_report(y_test, predictions, target_names = iris.target_names) print 'A detailed classification report: \n\n' + report if __name__ == "__main__": main()
This method just brings together the previous functions and should be relatively self-explanatory. One potentially confusing point may be the very end of the script - instead of just calling main() to run the script, it is useful to instead first check if
__name__ == "__main__". This would make no difference at all if you only want to run this script as is from the command line or in an interactive shell - when reading the source code, the Python interpreter would set the special __name__ variable to "__main__" and run everything. However, say that you wanted to just import the functions to another module (another .py file) without running all of the code. Then, __name__ would be set to the other module’s name. This would let us use the kNN code without having it execute every time. So, this check allows the script to behave differently based on whether the script is run directly or being imported from somewhere else. Refinements
In this implementation, when trying to classify new data points, we calculated the distance between each test instance and every single data point in our training set. This is inefficient, and there exist alterations to kNN which subdivide the search space in order to minimize the number of pairwise calculations (e.g. see k-d trees). Another refinement to the kNN algorithm can be made by weighting the importance of specific neighbours based on their distance from the test case. This would allow closer neighbours to have more of an impact on the class voting process, which is intuitively sensible.
A separate point to keep in mind is that, although here we arbitrarily chose k=5, we could have chosen other values (which would influence accuracy, noise sensitivity, etc.). Ideally, k would be optimized by seeing which value produces the most accurate predictions (see cross-validation).
An excellent overview of kNN can be read here. A more in depth implementation with weighting and search trees is here.
Full script
The full script follows:
from sklearn.datasets import load_iris from sklearn import cross_validation from sklearn.metrics import classification_report, accuracy_score from operator import itemgetter import numpy as np import math from collections import Counter # 1) given two data points, calculate the euclidean distance between them def get_distance(data1, data2): points = zip(data1, data2) diffs_squared_distance = [pow(a - b, 2) for (a, b) in points] return math.sqrt(sum(diffs_squared_distance)) # 2) given a training set and a test instance, use getDistance to calculate all pairwise distances def get_neighbours(training_set, test_instance, k): distances = [_get_tuple_distance(training_instance, test_instance) for training_instance in training_set] # index 1 is the calculated distance between training_instance and test_instance sorted_distances = sorted(distances, key=itemgetter(1)) # extract only training instances sorted_training_instances = [tuple[0] for tuple in sorted_distances] # select first k elements return sorted_training_instances[:k] def _get_tuple_distance(training_instance, test_instance): return (training_instance, get_distance(test_instance, training_instance[0])) # 3) given an array of nearest neighbours for a test case, tally up their classes to vote on test case class def get_majority_vote(neighbours): # index 1 is the class classes = [neighbour[1] for neighbour in neighbours] count = Counter(classes) return count.most_common()[0][0] # setting up main executable method def main(): # load the data and create the training and test sets # random_state = 1 is just a seed to permit reproducibility of the train/test split iris = load_iris() X_train, X_test, y_train, y_test = cross_validation.train_test_split(iris.data, iris.target, test_size=0.4, random_state=1) # reformat train/test datasets for convenience train = np.array(zip(X_train,y_train)) test = np.array(zip(X_test, y_test)) # generate predictions predictions = [] # let's arbitrarily set k equal to 5, meaning that to predict the class of new instances, k = 5 # for each instance in the test set, get nearest neighbours and majority vote on predicted class for x in range(len(X_test)): print 'Classifying test instance number ' + str(x) + ":", neighbours = get_neighbours(training_set=train, test_instance=test[x][0], k=5) majority_vote = get_majority_vote(neighbours) predictions.append(majority_vote) print 'Predicted label=' + str(majority_vote) + ', Actual label=' + str(test[x][1]) # summarize performance of the classification print '\nThe overall accuracy of the model is: ' + str(accuracy_score(y_test, predictions)) + "\n" report = classification_report(y_test, predictions, target_names = iris.target_names) print 'A detailed classification report: \n\n' + report if __name__ == "__main__": main()
Want to learn more? Check out our two-day Data Science Bootcamp:
https://cambridgecoding.com/datascience-bootcamp
Bio: Natasha Latysheva is a computational biology PhD student at the MRC Laboratory of Molecular Biology. Her research is focused on cancer genomics, statistical network analysis, and protein structure. More generally, her research interests lie in data-intensive molecular biology, machine learning (especially deep learning) and data science.
Original. Reposted with permission.
Related: