Description

the K Nearest Neighbors algo is used to determine what group a data point belongs to by checking the k nearest neighbors to it and seeing what group is the most prominant

Runtime

O(n^2)

Visualization

Pseudocode

calculate the distance to all points
sort the points based on the distance
get the k nearest points
count which group is the most common
return that group type

Code

def knn(k, point, points):
    k_nearest = [] #heap would be better?

    for other_point in points:
        d = dist(point.point, other_point.point)
        k_nearest.append((d, other_point.key))
        
    k_nearest.sort(key=lambda p:p[0], reverse=True)

    key_map = {}
    for key in k_nearest[:k]:
        if key not in key_map:
            key_map[key] = 0
        else:
            key_map[key] += 1

    return max(key_map, key=key_map.get)[1]