k-nearest neighbors and feature scaling
k-nearest neighbors (k-NN) is one of the simplest learning methods. There is no training phase: the algorithm stores the labelled examples, and to classify a new point it finds the k stored examples closest to it and returns the majority label. It is called a lazy learner because all the work happens at prediction time.
Python
train = [((1.0, 1000), "A"), ((1.1, 3000), "A"), ((5.0, 1100), "B"), ((5.2, 3100), "B")]
def make_scaler(points):
lows = [min(p[i] for p in points) for i in range(2)]
highs = [max(p[i] for p in points) for i in range(2)]
return lambda p: tuple((p[i] - lows[i]) / (highs[i] - lows[i]) for i in range(2))
def knn(train, query, k, scaled):
scale = make_scaler([point for point, _ in train]) if scaled else (lambda p: p)
q = scale(query)
ordered = sorted(train, key=lambda item: sum((a - b) ** 2 for a, b in zip(scale(item[0]), q)))
votes = [label for _, label in ordered[:k]]
return max(set(votes), key=votes.count)
print(knn(train, (1.2, 2000), 1, False))
print(knn(train, (1.2, 2000), 1, True))