# 1. The K-Nearest Neighbors Algorithm K-Nearest Neighbors (KNN) classifies a new data point by looking at the labels of the $k$ closest points to it in the training data, and predicting whichever label is most common among them. ```python def KNN(training_data, new_data_point, k): # Calculate distances between new_data_point and all points in training_data distances = [] for point in training_data: distance = EuclideanDistance(point['coordinates'], new_data_point) distances.append((distance, point['label'])) # Sort the distances in ascending order distances.sort(key=lambda x: x[0]) # Select the top 'k' nearest neighbors top_k_neighbors = distances[:k] # Get the labels of the top 'k' neighbors labels = [label for _, label in top_k_neighbors] # Return the most frequent label (majority vote) return max(set(labels), key=labels.count) def EuclideanDistance(point1, point2): # Assume points are lists or arrays containing coordinates dimensions = len(point1) # Number of dimensions (e.g., 2 for 2D, 3 for 3D) sum_of_squares = 0 for i in range(dimensions): difference = point1[i] - point2[i] squared_difference = difference ** 2 sum_of_squares += squared_difference distance = sum_of_squares ** 0.5 return distance ``` **How it works, step by step:** the KNN function starts by iterating over every point in the training dataset. For each training point, it calculates the distance between that point and the new data point being classified, and stores each distance alongside its corresponding label. Once every distance has been calculated, the full list is sorted from smallest to largest. The algorithm then picks the top $k$ closest neighbors based on that sorted distance, looks at their labels, and assigns the new data point whichever label appears most frequently among those $k$ neighbors. # 2. Additional Notes **KNN for regression.** The process is nearly identical to classification, except that instead of taking a majority vote over the $k$ nearest neighbors' labels, the algorithm averages their target *values* to produce a continuous prediction. **Choice of $k$.** $k$ is a hyperparameter that needs to be tuned rather than guessed — it's typically chosen through experimentation or cross-validation, balancing a small $k$ (which can overfit to noise in the nearest few points) against a large $k$ (which can smooth over genuinely meaningful local structure). **Distance metric.** Euclidean distance is the most common choice, but other metrics — Manhattan, Minkowski, and others — can be more appropriate depending on the structure of the data (see the Statistical Knowledge and Data Science and ML Knowledge notes for more on Euclidean vs. Manhattan distance).