Final answer:
The k-Nearest Neighbors (k-NN) algorithm can be implemented in Python without using external libraries by calculating Euclidean distances, sorting them, and classifying based on the majority class of the k closest points.
Step-by-step explanation:
The question involves implementing the k-Nearest Neighbors (k-NN) classification algorithm in Python from scratch. This algorithm is commonly used in machine learning to classify data points based on their proximity to points in a training dataset. For k-NN classification, the value of k represents the number of nearest neighbors to consider when making a classification decision.
To address the task, we start by calculating the Euclidean distance between the test data point and each point in the training dataset. Then, we sort these distances and find the k smallest distances. The classification of the new data point is determined by the majority class among these k closest points. Below is the Python code implementing the k-NN classifier:
def euclidean_distance(x1, y1, x2, y2):
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
def knn_classification(x_train, y_train, classes, k, x_test, y_test):
distances = []
for i in range(len(x_train)):
dist = euclidean_distance(x_train[i], y_train[i], x_test, y_test)
distances.append((dist, classes[i]))
distances.sort(key=lambda x: x[0])
neighbors = distances[:k]
votes = [neighbor[1] for neighbor in neighbors]
prediction = max(set(votes), key=votes.count)
return prediction
Using this code, we can predict the class for any given test data point. Following the provided test cases, classifying the point (8, 21) with k=1, and the point (14, 25) with k=1 would result in classes 0 and 1, respectively. Similarly, classifying the point (11, 22) with k=4, and the point (5, 20) with k=4 would result in classes 1 and 0, respectively.