KNN: Classifying by Looking at Your Neighbors

Lecture 4a: KNN, the most "model-less" model there is. No coefficient to fit, no gradient, no normal equation. Just a ruler.

The dataset: wines, 3 cultivars

New dataset: load_wine, 178 bottles, 13 chemical measurements (alcohol content, acidity, magnesium, and so on) and 3 classes, the grape cultivar. The professor picks two columns so it's plottable on a plane: flavanoids (index 6) and color_intensity (index 9).

from sklearn.datasets import load_wine
X, y = load_wine(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
feats = [6, 9]

The idea: there's no training, just memory

Every model I've seen up to now (regression, the thresholded classifier) fits parameters: finds a w that minimizes some error. KNN does none of that. Its "training" is literally just storing the data:

class K1NN(BaseEstimator, ClassifierMixin):
    def fit(self, X, y):
        self.X = X
        self.y = y
        return self

    def distance_(self, x):
        return np.sum((self.X - x)**2, axis=1)**0.5

    def predict(self, X):
        y_pred = np.empty((X.shape[0],))
        for i, x in enumerate(X):
            distances = self.distance_(x)
            min_idx = np.argmin(distances)
            y_pred[i] = self.y[min_idx]
        return y_pred

To classify a new wine, it computes the Euclidean distance to every training wine, finds the closest match, and copies its class. This is called K1NN because it only looks at the single nearest neighbor, K=1.

Output: 0.97 test accuracy. Identical to scikit-learn's KNeighborsClassifier(n_neighbors=1) run on the same data.

Bishop treats this as a special case of a more general result (section 2.5.2): if you draw a sphere around a new point until it contains exactly $K$ neighbors, and look at which class is the majority among them, the posterior probability of each class is simply $K_k/K$ (the fraction of the $K$ neighbors belonging to that class). Classifying by the most common class among the $K$ nearest neighbors is applying Bayes' theorem to that result. $K=1$ is just the most extreme case: the "sphere" grows until it touches a single point, and you copy its class with no voting at all.

Interactive: nudging K for real

Instead of running one cell per K value like the notebook does, you can watch the decision boundary shift live. This is my own reconstruction on top of the 142 real training wines (the same two columns, flavanoids and color_intensity), running the same majority-vote algorithm:

Click through each K value and notice: at K=1, the colored regions have a bunch of little isolated islands, each one hugging a single training point, the boundary is all jagged. With a bigger K, the islands disappear and the regions turn into smoother, more continuous blocks.

K is a smoothing parameter, not "the bigger the better"

The professor tries K=1, 3, 5, 13 on the real test data:

Counterintuitive at first: I'd expect looking at more neighbors to give a more "reliable" result, but here accuracy only gets worse as K grows. Bishop calls K exactly that, a smoothing parameter: a small K keeps the decision boundary tightly wrapped around the training data (low bias, but sensitive to every individual point, including noise), while a large K blurs the boundary, mixing in neighbors from different regions when voting (more bias, less sensitive to noise). In this specific dataset, with only 142 training points spread across 3 classes, increasing K starts pulling neighbors from a different cultivar into the vote too quickly, so the sweet spot here sits close to K=1.

That doesn't mean "always use K=1." Bishop cites an interesting result: in the limit of infinite training data, the nearest-neighbor classifier (K=1) never makes more than twice the error of the theoretically optimal classifier, a surprisingly strong guarantee for such a simple method. But with little data (like here, 142 points), K=1 might just be "memorizing" training, and the right K is an empirical question, not a fixed rule. I'll come back to this more rigorously (validation, not just "I tried it and K=1 won") in the next post.

A quick reminder: distance also demands normalization

I already saw this in the previous post: since KNN decides by distance, one large-scale variable dominates the computation on its own. It's no different here, and the next (bonus) post shows the real size of the damage and the right way to avoid it, with Pipeline.

Wrapping up

Practical application

I use the same wine dataset, now with all 13 variables (not just the 2 that were plottable), to see the effect of normalization in practice, something I'd only described in words up to here.

model_raw = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train)
model_norm = KNeighborsClassifier(n_neighbors=k).fit(X_train_normalized, y_train)

Without normalizing, accuracy bounces around and never breaks 0.81 (13 variables at very different scales, like proline, which goes up to nearly 1700, against hue, which stays under 2, so distance ends up decided almost entirely by proline). Normalized, accuracy hits 0.9444 at every one of the three K values, a huge jump, and here's the interesting part: after normalizing, the choice of K stops mattering nearly as much, all three give the exact same result on this test. That tracks: once every variable genuinely contributes to distance (instead of one variable dominating everything), the neighborhood gets "right" much sooner, leaving less work for fine-tuning K to fix.