# K_nearest_neighbors from scratch [closed]

I wanted to create a script that will perform the k_nearest_neighbors algorithm on the well-known iris dataset. This was mainly for me to better understand the algorithm and process. I think it works, but it could definitely use some tuning up. One thing that has me worried was incorporating multiple features into the calculations.

The process that I have utilized:

1. Read the iris.csv into a pandas dataframe
2. Split the dataframe into a train/test set (0.75/0.25)
3. Create an instance of the k_nearest_neighbor class and "fit" the training set as a numpy array
4. In the prediction phase, I first make sure the testing set is a numpy array
5. Loop through each testing point in the test set
6. Loop through each training point in the train set
7. Append the distances to a list using the euclidean distance formula of each training point to the testing point in question.
8. Sort the list from smallest to largest based on the distances
9. Slice the list up to k that was chosen (default k is set to 1)
10. Count the number of classes found in the neighbors and either return the most found class, or a random class if multiple classes have the same counts (only of the classes with the same counts).
11. Then I simply return a numpy array of the testing dataset but I replace the class it originally had with the predicted one.

major concerns:

1. I did not handle multiple features correctly in the calculations
2. Predictions are coming up a bit less than other sources.

I checked the amount that was accurately predicted and it seems to come a bit short compared to other sites and a book I am going through. However, I have noticed that the algorithm does predict a bit better when I split the data by 0.65/0.35. The last bit was me just trying the check the accuracy. I am hoping another pair of eyes could let me know what I may have missed or done wrong, thanks for any help!

import random
from operator import itemgetter

import math
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

"""
This is a function that will read a csv and return a pandas dataframe
TODO: add functionality to accept other formats
:param dataset_path:
:return:
"""

def split_train_test(dataframe,split=0.75, random_state=0):
"""
This is a function that will split a pandas dataframe into a testing/training dataset.
:param dataframe: pandas dataframe
:param random_state: random state seed, set to 0 by default
:return: training dataframe and a testing dataframe
"""

dataframe_copy = dataframe.copy()

train_set = dataframe_copy.sample(frac=split, random_state=random_state)
test_set = dataframe_copy.drop(train_set.index)

return train_set, test_set

def convert_class_str_to_class_int(classes):
"""
This is a function that will take a set of classes and return a dictionary where the class name is the key
and the index of the class found within the set is the value.
:param classes:
:return:
"""
classes_dict = dict()
for index, class_str in enumerate(classes):
classes_dict[class_str] = int(index)

return classes_dict

class k_nearest_neighbors():
"""
This is a class that houses methods and variables for the k_nearest_neighbor algorithm.
"""

def fit(self, training_dataframe):
"""
This is a function that will fit a training set of data to the class. It accepts a pandas dataframe and pulls
the data, classes, and features from the dataframe.
:param training_dataframe: pandas dataframe
:return: None
"""

self.classes = set(training_dataframe["class"].tolist())
self.features = list(training_dataframe.columns.values)

classes_dict = convert_class_str_to_class_int(self.classes)
training_dataframe = training_dataframe.replace(classes_dict)

self.data = training_dataframe.to_numpy()

def plot(self, x_feature, y_feature):
"""
This is a function that will plot two features of a given dataset.
:param x_feature: name of the desired x feature
:param y_feature: name of the desired y feature
:return: None
"""

x_index = self.features.index(x_feature)
y_index = self.features.index(y_feature)

plt.scatter(self.data[:, x_index], self.data[:, y_index], c=self.data[:, -1], cmap="brg")
plt.xlabel(x_feature)
plt.ylabel(y_feature)
plt.show()

def predict(self, test_data, factor_length, k):
"""
This is a function that will predict what a series of points are based on training data that was already
fitted to the k_nearest_neighbors instance.
:param test_data: test dataset
:param factor_length: number of factors to consider
:param k: number of neighbors to consider
:return: numpy array of test data points with predicted classes
"""

try:
classes_dict = convert_class_str_to_class_int(self.classes)
test_data = test_data.replace(classes_dict)
test_data = test_data.to_numpy()
except AttributeError:
pass

def aggregate_neighbors(neighbors: list):
"""
This function takes all the neighbors found closest to the test data point of interest and takes a count of
the number of classes found from each neighbor. If multiple classes have the same counts, then those classes
are chosen at random.
:param neighbors: neighbors found closest to the test data point
:return: most counted class (or randomly selected from multiple classes)
"""
class_list = list()
class_dict = dict()
for neighbor in neighbors:
class_list.append(neighbor[1])

unique_classes = set(class_list)
for unique_class in unique_classes:
count = class_list.count(unique_class)
class_dict[unique_class] = count

largest_class_value = 0
largest_class = None
multiple_classes_list = list()

for key, value in class_dict.items():
if largest_class is None or value > largest_class_value:
largest_class_value = value
largest_class = key
multiple_classes_list = [key]
elif value == largest_class_value:
multiple_classes_list.append(key)

if len(multiple_classes_list) > 1:
choice = random.choice(multiple_classes_list)
return choice

return largest_class

def euclidean_distance(test_point, train_point, length):
"""
This is a function that will calculate the euclidean distance for each factor.
:param test_point: the test point of interest
:param train_point: the train point of interest
:param length: number of factors to consider
:return: distance between the test_point and train_point
"""
distance = 0
for x in range(length):
distance += pow(test_point[x] - train_point[x], 2)
return math.sqrt(distance)

predicted_points = list()
for index, testing_point in enumerate(test_data):

neighbors = list()
for training_point in self.data:
distance = euclidean_distance(testing_point, training_point, factor_length)
neighbors.append([distance, training_point[-1]])

neighbors = sorted(neighbors, key=itemgetter(0))

final_k_neighbors = neighbors[:k]

prediction = aggregate_neighbors(final_k_neighbors)

predicted_point = list(testing_point[:-1])

predicted_point.append(prediction)

predicted_points.append(predicted_point)

return np.array(predicted_points)

if __name__ == "__main__":

dataset_path = "iris.csv"

train_set, test_set = split_train_test(df)

knn = k_nearest_neighbors()
knn.fit(train_set)

classes_dict = convert_class_str_to_class_int(knn.classes)
test_set_nump = test_set.replace(classes_dict)
test_set_nump = test_set_nump.to_numpy()

predictions = knn.predict(test_set_nump, 4, 1)

misclassed = 0
correct_classed = 0
for test_point, predict_point in zip(test_set_nump, predictions):
if test_point[-1] == predict_point[-1]:
correct_classed += 1
else:
misclassed += 1

print(f"correctly classed: {correct_classed}\nmisclassed: {misclassed}")
print(f"test prediction: {correct_classed/len(test_set)}")


## closed as off-topic by pacmaninbw, Dannnno, Linny, Mast, Malachi♦Oct 21 at 1:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – pacmaninbw, Dannnno, Linny, Malachi
If this question can be reworded to fit the rules in the help center, please edit the question.

• Does this code work to the best of your knowledge? If the answer is no then I suggest you post your question in stack overflow which might be more suitable for non-working code. – bullseye Oct 15 at 12:41
• Welcome to Code Review! We don't review code unless it accomplishes the goal for which it was written. unfortunately we also don't allow for changing the code after answers were given if they invalidate the answers that were given. Please feel free to post a new question when you have fully working code. – Malachi Oct 21 at 1:52

Imports should be ordered alphabetically in groups of standard library imports, third-party imports and local project imports:

import math
from operator import itemgetter
import random

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd


# Make use of comprehensions

You can rewrite

def convert_class_str_to_class_int(classes):
"""
This is a function that will take a set of classes and return a dictionary where the class name is the key
and the index of the class found within the set is the value.
:param classes:
:return:
"""
classes_dict = dict()
for index, class_str in enumerate(classes):
classes_dict[class_str] = int(index)

return classes_dict


as

def get_class_id_mapping(classes):
"""
This is a function that will take a set of classes and return a dictionary where the class name is the key
and the index of the class found within the set is the value.
:param classes:
:return:
"""
return {class_str: index for index, class_str in enumerate(classes)}


Note that you do not need to cast for int(), since enumerate() will always yield ints. Also the original name was a bit misleading, as it did not reflect, what the function actually does.
Also beware, that sets do not have indices. If the input value is actually a set, the corresponding indices given upon iteration will be in random order.

In this block

try:
classes_dict = convert_class_str_to_class_int(self.classes)
test_data = test_data.replace(classes_dict)
test_data = test_data.to_numpy()
except AttributeError:
pass


it is not clear at which line you'll expect the AttributeError to occur. At the first line? At the last line? At any of the three lines?

# Use a main() function

Put the stuff, that you have under the if __name__ = '__main__' guard into a def main(): function and place its call there.

Other than that, your code looks pretty good. The docstrings are informative, the methods mostly named feasibly.