PYTHON / MACHINE LEARNING WITH PYTHON
k-nearest neighbours and k-means
Predict labels with KNeighborsClassifier from nearby examples, group unlabelled points with KMeans, and keep the two meanings of k apart.
What you will learn
- Fit KNeighborsClassifier and inspect the actual neighbours with kneighbors()
- Explain how k trades noise sensitivity against blurred class boundaries
- Read KMeans cluster_centers_ and inertia_, and treat labels_ as arbitrary group ids
- Recognise that both methods judge only by distance, so feature scale decides the answer
Understanding k-nearest neighbours and k-means
k-nearest neighbours is supervised and does almost nothing at fit time: it stores the training points and their labels. All the work happens at predict time, when it measures the distance from the query point to every stored point, keeps the k closest, and takes a vote. That is why a single mislabelled training point can dominate a k=1 prediction, and why raising k to 3 or 5 lets correct neighbours outvote it. The cost of this design is that prediction time grows with the size of the training set, the opposite of a fitted linear model.
k-means is unsupervised and has no labels to learn from. It picks k centre points, assigns every sample to its nearest centre, moves each centre to the mean of the samples assigned to it, and repeats until the assignments stop changing. The quantity it drives down is inertia, the sum of squared distances from each point to its own centre. Because it only ever improves from where it started, different initial centres can end at different answers, which is why scikit-learn runs it n_init times and keeps the best.
The letter k is the same in both names and means two unrelated things: how many neighbours to consult, and how many clusters to fit. Another difference matters just as much. KNN's output is a class you already defined, while KMeans' labels_ are group numbers with no inherent meaning; cluster 0 in one run can be cluster 1 in the next, and no cluster corresponds to a real category unless you check. What the two share is that they reason purely with Euclidean distance, so a feature measured in thousands silently outranks one measured in tenths.
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.cluster import KMeans
X = np.array([[1., 1.], [1., 2.], [2., 1.], [2., 2.],
[5., 5.], [5., 6.], [6., 5.], [6., 6.]])
y = np.array([0, 0, 0, 1, 1, 1, 1, 1]) # the point at (2, 2) is labelled 1
query = np.array([[2.2, 2.2]])
for k in (1, 3):
knn = KNeighborsClassifier(n_neighbors=k).fit(X, y)
dist, idx = knn.kneighbors(query)
print(f"k={k} labels={sorted(y[idx[0]].tolist())} "
f"dist={dist[0].round(3).tolist()} pred={knn.predict(query)[0]}")
km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
print("centres:", sorted(km.cluster_centers_.round(2).tolist()))
print("with point 0:", (km.labels_ == km.labels_[0]).astype(int).tolist())Both algorithms decide everything by Euclidean distance in feature space, but KNN's k counts neighbours voting on a known label while k-means' k counts clusters it invents.
Worked examples
Distance weighting can flip a KNN vote
With the same three neighbours, weighting votes by 1/distance changes the predicted class.
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
X = np.array([[1., 1.], [1., 2.], [2., 1.], [2., 2.],
[5., 5.], [5., 6.], [6., 5.], [6., 6.]])
y = np.array([0, 0, 0, 1, 1, 1, 1, 1])
query = np.array([[2.2, 2.2]])
for w in ("uniform", "distance"):
knn = KNeighborsClassifier(n_neighbors=3, weights=w).fit(X, y)
print(w, knn.predict_proba(query).round(2).tolist(), "->", knn.predict(query)[0])Example explained
Line 1The three nearest points are one class-1 point at distance 0.283 and two class-0 points at 1.217.
Line 2weights='uniform' counts heads only, so two beats one and the vote gives class 0 with probability 0.67.
Line 3weights='distance' gives each neighbour weight 1/distance, so the very close class-1 point carries 3.54 against 1.64 for the pair.
Line 4Neither answer is more correct in itself: the choice encodes whether you believe proximity should outrank count.
Inertia cannot choose k for you
Fitting KMeans for k=1 to 4 on two tight groups of four points shows inertia falling forever after the real structure is found.
import numpy as np
from sklearn.cluster import KMeans
X = np.array([[1., 1.], [1., 2.], [2., 1.], [2., 2.],
[5., 5.], [5., 6.], [6., 5.], [6., 6.]])
for k in (1, 2, 3, 4):
km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
print(f"k={k} inertia={km.inertia_:.2f}")Example explained
Line 1inertia_ is the total squared distance from each point to its assigned centre, so it is a fit score, not a quality score.
Line 2The collapse from 68.00 to 4.00 is the two real groups being separated; that sharp bend is the elbow.
Line 3k=3 and k=4 only shave a point off by cutting a real group in half, which is why the curve flattens.
Line 4n_init=10 with a fixed random_state makes each fit reproducible, since a single unlucky start can end in a worse local optimum.
Important notes
KNN stores the whole training set, so memory and prediction latency scale with it; a large training set makes prediction, not fitting, the slow part.
k-means looks for compact, roughly equal-sized blobs around a mean, so it splits elongated or ring-shaped groups down the middle no matter how many restarts you allow.
Common mistakes
Reading KMeans labels_ as class predictions: the numbers are arbitrary group ids, so 'accuracy' against true labels is meaningless and can look near zero even for a perfect clustering.
Picking k for k-means by choosing the k with the lowest inertia: inertia falls monotonically and hits zero when k equals the number of samples, so this always picks the largest k you tried.
Running KNN on unscaled columns such as salary in euros next to years of experience: the salary difference dominates every distance and the experience feature effectively stops existing.
Using an even n_neighbors for two classes, which produces tied votes broken by the class order rather than by the data.
Try it yourself
Change, predict, then run
Take the eight-point dataset from the main example, change the label of the point at (2, 2) back to 0, and re-run the KNN predictions for k=1 and k=3. Then fit KMeans with n_clusters=3 and print cluster_centers_ to see which of the two groups it decides to split.
Open the Python workspaceCheck your understanding
You fit KMeans on the same data with n_clusters from 2 to 8 and inertia_ drops at every step. Why does that not mean 8 clusters is the best model?
- Inertia can only fall as k grows, reaching zero when each point is its own cluster, so minimising it never picks k
- Inertia is only defined for k=2 and returns a meaningless number above that
- KMeans stops converging past k=5, so those later inertia values are unreliable
- Larger k needs a larger n_init, so the extra drop is only luckier initialisation
Show answer
Adding a centre can never make points farther from their nearest centre, so inertia is monotonically non-increasing in k and bottoms out at zero when k equals the sample count; you need the location of the bend, or an outside criterion, to choose k. The n_init option is a real concern for reproducibility, but it addresses local optima at a fixed k and does not explain a drop that continues for every k.