Day 7 · k-NN, k-Means, PCA, Embeddings

Suggested pace: 1–1.5 hrs learn · 2–3 hrs code · rest to debug and document

What you should know first ☐ Day 1 and Day 2: vectors, dot product and shapes ☐ Day 5: why features should be on a similar scale ☐ Day 1: mean (centroids are means) If one of these feels shaky, spend 15 minutes revisiting it before starting. That is normal and saves time later.

Goal of today Get familiar (not expert) with four important ideas: k-NN, k-Means, PCA and embeddings. Tomorrow you use them in your first complete mini ML project.

Big picture — read this first An embedding represents an item as a vector so that useful relationships can be measured geometrically. Cosine similarity focuses on direction rather than raw magnitude. This is why it is useful for semantic similarity. The key bridge to GenAI: *text can become vectors; vectors can be compared; similar content can be retrieved. A vector database* is an optimized system for storing and searching these vector representations.

PART A — DISTANCE & SIMILARITY

1. Why distance?

Many algorithms rely on one idea: similar things are close together. To use that, we need a way to measure “closeness” between two data points (each is a list of numbers).

Example: two people described by (age, salary in lakhs): P1 = (25, 6), P2 = (30, 8).

Worked Problem · Find The Nearest Person

Problem. People as (age, salary in lakhs): P1 = (25, 6), P2 = (30, 8), P3 = (55, 20). Who is closest to P1?

1. Distance P1–P2 = √(5² + 2²) = √29 ≈ 5.39.
2. Distance P1–P3 = √(30² + 14²) = √1096 ≈ 33.1.
3. P2 is much nearer, so P2 is most similar to P1.

import numpy as np
P = {"P2": (30, 8), "P3": (55, 20)}
p1 = np.array([25, 6])
print({k: round(float(np.linalg.norm(p1 - np.array(v))), 2) for k, v in P.items()})

{'P2': 5.39, 'P3': 33.11}

Answer. P2 (5.39) is closer than P3 (33.11).

2. Common measures

Euclidean distance (straight line — “as the crow flies”)

d = √[(x₁−y₁)² + (x₂−y₂)² + ...]

P1↔P2: √[(25−30)² + (6−8)²] = √(25+4) = √29 ≈ 5.39

Manhattan distance (city blocks)

d = |x₁−y₁| + |x₂−y₂| + ... → 5 + 2 = 7

Cosine similarity (angle, ignores length)

cos = (a·b) / (‖a‖‖b‖)

Best for text and embeddings, where direction = meaning and length doesn’t matter.

*Watch out Scale matters! If salary ranges 0–1,000,000 and age ranges 20–60, distance is dominated by salary. Always standardize features* for distance-based algorithms.

from sklearn.preprocessing import StandardScaler
X = StandardScaler().fit_transform(X)

Worked Problem · Euclidean And Manhattan Distance

Problem. Two people are described by (age, salary in lakhs): P1 = (25, 6) and P2 = (30, 8). Compute the Euclidean and Manhattan distances.

1. Differences: 30 − 25 = 5 and 8 − 6 = 2.
2. Euclidean distance = √(5² + 2²) = √29 ≈ 5.385 (the straight-line distance).
3. Manhattan distance = |5| + |2| = 7 (walking along the grid).
4. Check with code.

import numpy as np
p1 = np.array([25, 6]); p2 = np.array([30, 8])
print(round(np.linalg.norm(p1 - p2), 3), np.abs(p1 - p2).sum())

5.385 7

Answer. Euclidean 5.385, Manhattan 7.

Your Turn · The Measure Can Change The Answer

Problem. From A = (0, 0), is B = (3, 4) or C = (6, 0) nearer under Euclidean distance? Under Manhattan distance?

Try it on paper or in a notebook first. Then check the solution.

Solution — Step By Step

1. Euclidean to B: √(9 + 16) = 5. To C: √36 = 6. B is nearer.
2. Manhattan to B: 3 + 4 = 7. To C: 6 + 0 = 6. C is nearer.
3. So the choice of distance can change who the “nearest neighbor” is.

import numpy as np
A = np.array([0, 0]); B = np.array([3, 4]); C = np.array([6, 0])
print(np.linalg.norm(A - B), np.linalg.norm(A - C))
print(np.abs(A - B).sum(), np.abs(A - C).sum())

5.0 6.0
7 6

Answer. Euclidean: B is nearer (5 vs 6). Manhattan: C is nearer (6 vs 7).

PART B — k-NN (k-Nearest Neighbors)

3. The idea: “Tell me who your neighbors are and I’ll tell you

who you are”

To predict a new point: 1. Compute its distance to every training point 2. Pick the k closest ones 3. Classification: majority vote among them. Regression: average their values.

Example (k = 3) A new fruit; its 3 nearest neighbors are: apple, apple, orange → predict apple.

    o  o
 o     ← new point
●   ●    (● = 2 of class A, o = 1 of class B in the 3 nearest)

Worked Problem · Classify With K-Nn By Hand

Problem. Training points: (1,1) A, (2,1) A, (4,4) B, (5,4) B, (5,5) B. Classify the query (2, 2) with k = 3.

1. Compute the distance from (2, 2) to every training point: (1,1) → 1.414, (2,1) → 1.0, (4,4) → 2.828, (5,4) → 3.606, (5,5) → 4.243.
2. Pick the 3 nearest: (2,1) A, (1,1) A, (4,4) B.
3. Vote: A has 2, B has 1. A wins.
4. Confirm with scikit-learn.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
X = np.array([[1, 1], [2, 1], [4, 4], [5, 4], [5, 5]]); y = np.array(list("AABBB"))
print(KNeighborsClassifier(n_neighbors=3).fit(X, y).predict([[2, 2]])[0])

A

Answer. The query is class A.

Your Turn · Change K, Change The Answer

Problem. Using the same training points, classify (2.5, 2.5) with k = 1 and with k = 5.

Try it on paper or in a notebook first. Then check the solution.

Solution — Step By Step

1. With k = 1 only the single nearest point votes. The nearest to (2.5, 2.5) is (2, 1) (distance ≈ 1.58), which is class A.
2. With k = 5 every point votes: 2 are A and 3 are B, so B wins.
3. Small k follows the nearest point (noisy). Large k follows the overall majority (smooth).

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
X = np.array([[1, 1], [2, 1], [4, 4], [5, 4], [5, 5]]); y = np.array(list("AABBB"))
for k in (1, 5):
    print(k, KNeighborsClassifier(n_neighbors=k).fit(X, y).predict([[2.5, 2.5]])[0])

1 A
5 B

Answer. k = 1 gives A, k = 5 gives B.

4. Choosing k

5. Properties

• No training — it just stores data (“lazy learner”). All the work happens at prediction time.
• ✓ Simple, intuitive, no assumptions

⊠ Slow with big data (must compare with all points) ⊠ Needs scaling ⊠ Struggles with many features (curse of dimensionality)

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors = 5).fit(X_train, y_train)
knn.score(X_test, y_test)

Connection to the future: vector databases do “nearest neighbor search” over embeddings — that’s k-NN at scale (RAG!).

Worked Problem · Why Scaling Matters

Problem. Two people differ by 10 years of age and ₹1,000 in salary. A third pair differs by 1 year and ₹5,000. Which pair looks “closer” before scaling, and after scaling age to 0–100 and salary to 0–100,000?

1. Before scaling: pair 1 distance ≈ √(10² + 1000²) ≈ 1000.05 and pair 2 ≈ √(1² + 5000²) ≈ 5000. Salary completely dominates.
2. Scale age by 1/100 and salary by 1/100,000 so both lie in 0–1.
3. Pair 1 becomes (0.10, 0.01) with distance ≈ 0.1005. Pair 2 becomes (0.01, 0.05) with distance ≈ 0.051.
4. Now age matters too, and pair 2 is the closer pair.

import numpy as np
s = np.array([100, 100000])
for d in ((10, 1000), (1, 5000)):
    d = np.array(d); print(round(np.linalg.norm(d), 2), round(np.linalg.norm(d /
        s), 4))

1000.05 0.1005
5000.0 0.051

Answer. Unscaled 1000.05 and 5000; scaled 0.1005 and 0.051. Always scale features before k-NN.

PART C — k-MEANS CLUSTERING

6. Unsupervised learning

No labels! The algorithm finds hidden groups by itself. Uses: customer segmentation, grouping news articles, image compression.

Worked Problem · Supervised Or Unsupervised?

Problem. Decide: (a) group customers by buying habits with no labels, (b) predict whether a customer will cancel using past cancel/stay labels, (c) compress 50 features into 2 for a chart.

1. Does the data come with the right answers (labels)?
2. (a) No labels, we want groups → unsupervised (clustering).
3. (b) Labels exist → supervised (classification).
4. (c) No labels, only restructuring → unsupervised (dimensionality reduction).

Answer. (a) unsupervised, (b) supervised, (c) unsupervised.

7. The k-Means algorithm

Goal: split data into k groups (clusters). Each cluster has a centroid (its center point).

Steps: 1. Choose k (e.g. 3) 2. Initialize k random centroids 3. Assign every point to its nearest centroid 4. Update each centroid = mean of its assigned points 5. Repeat 3–4 until centroids stop moving

Start After assign After update Converged random centroids nearest centroid move to the mean no more changes

1 3 10 12 1 3 10 12 1 3 10 12 1 3 10 12 X • • ... Same six points as the worked problem below. X = centroid; blue and orange = the two clusters; gray = not yet assigned.

from sklearn.cluster import KMeans
km = KMeans(n_clusters = 3, n_init = 10, random_state = 42)
labels = km.fit_predict(X_scaled)      # cluster id for each row
km.cluster_centers_                     # centroids
km.inertia_
# sum of squared distances to centroid (lower = tighter)

Worked Problem · Two Rounds Of K-Means

Problem. Cluster the 1-D points [1, 2, 3, 10, 11, 12] into k = 2 clusters, starting with centroids 2 and 3.

1. Assign each point to the nearest centroid. 1 → 2 (distance 1 vs 2), 2 → 2, 3 → 3, and 10, 11, 12 → 3.
2. Move each centroid to the mean of its points: cluster 1 = [1, 2] → 1.5, cluster 2 = [3, 10, 11, 12] → 9.
3. Assign again with centroids 1.5 and 9: 1, 2, 3 are closer to 1.5; 10, 11, 12 are closer to 9.
4. New means: [1, 2, 3] → 2 and [10, 11, 12] → 11.
5. Assign again: nothing changes, so the algorithm has converged.

import numpy as np
x = np.array([1, 2, 3, 10, 11, 12.]); c = np.array([2., 3.])
for it in range(3):
    lab = np.abs(x[:, None] - c[None, :]).argmin(axis=1)
    c = np.array([x[lab == k].mean() for k in range(2)])
    print(c.tolist())

[1.5, 9.0]
[2.0, 11.0]
[2.0, 11.0]

Answer. Centroids go [1.5, 9.0] → [2.0, 11.0] → [2.0, 11.0]. The final clusters are {1, 2, 3} and {10, 11, 12}.

Your Turn · Inertia

Problem. For the final clusters {1, 2, 3} (centroid 2) and {10, 11, 12} (centroid 11), compute the inertia (sum of squared distances to the centroid).

Try it on paper or in a notebook first. Then check the solution.

Solution — Step By Step

1. Cluster 1: (1−2)² + (2−2)² + (3−2)² = 1 + 0 + 1 = 2.
2. Cluster 2: (10−11)² + (11−11)² + (12−11)² = 1 + 0 + 1 = 2.
3. Total inertia = 2 + 2 = 4.

import numpy as np
a = np.array([1, 2, 3]); b = np.array([10, 11, 12])
print(((a - a.mean()) ** 2).sum() + ((b - b.mean()) ** 2).sum())

4.0

Answer. Inertia = 4.0. Lower inertia means tighter clusters, which is what the elbow plot tracks as k grows.

8. How to choose k?

Elbow method: run k = 1..10, plot inertia_. Pick the “elbow” where improvement slows.

inertias = [KMeans(n_clusters = k, n_init = 10).fit(X).inertia_ for k in range(1,
    11)]
plt.plot(range(1,11), inertias, "o-")

Silhouette score (−1 to 1, higher = better separated): sklearn.metrics.silhouette_score(X, labels).

Worked Problem · Read An Elbow

Problem. Run k-Means on [1, 2, 3, 10, 11, 12] with k = 1, 2, 3 and compare the inertia.

1. Inertia is the total squared distance from each point to its cluster center. It always falls as k grows.
2. k = 1: one center at 6.5, so a big inertia.
3. k = 2: the two natural groups give a small inertia (4).
4. k = 3: it drops only a little more. The “elbow” is where the drop slows down: k = 2.

import numpy as np
from sklearn.cluster import KMeans
X = np.array([1, 2, 3, 10, 11, 12.]).reshape(-1, 1)
print([round(KMeans(k, n_init=10, random_state=0).fit(X).inertia_, 2) for k in (1,
    2, 3)])

[125.5, 4.0, 2.5]

Answer. Inertia [125.5, 4.0, 2.5]. The big drop from k = 1 to k = 2, then a small one, marks the elbow at k = 2.

9. Limitations

• You must choose k
• Assumes roughly round, similar-sized clusters
• Sensitive to scale and random start (use n_init=10)
• Affected by outliers

Worked Problem · K Changes The Story

Problem. Cluster [1, 2, 3, 10, 11, 12] with k = 2 and with k = 3. What do the groups look like?

1. You must choose k before you start; the algorithm will not tell you the “right” answer.
2. k = 2 splits the data into the two obvious groups.
3. k = 3 splits one group into smaller pieces that may mean nothing.

import numpy as np
from sklearn.cluster import KMeans
X = np.array([1, 2, 3, 10, 11, 12.]).reshape(-1, 1)
for k in (2, 3):
    lab = KMeans(k, n_init=10, random_state=0).fit_predict(X)
    print(k, sorted(X[lab == c].ravel().astype(int).tolist() for c in range(k)))

2 [[1, 2, 3], [10, 11, 12]]
3 [[1, 2, 3], [10], [11, 12]]

Answer. k = 2 gives the groups [1, 2, 3] and [10, 11, 12]; k = 3 breaks one of them apart (see the printout). Domain knowledge must guide the choice of k.

PART D — PCA (Principal Component Analysis)

10. The problem: too many features

Datasets may have hundreds of columns. Many are redundant (e.g. height in cm and height in inches). Too many features → slow, noisy, hard to visualize.

Worked Problem · Distances Lose Meaning In Many Dimensions

Problem. Draw 200 random points. Compare the farthest-to-nearest distance ratio from one point in 2 dimensions and in 1,000 dimensions.

1. In 2-D some points are very near and some far, so the ratio is large.
2. In 1,000-D almost every point is about equally far, so the ratio approaches 1.
3. When all distances look alike, “nearest neighbor” stops being informative. Reducing dimensions helps.

import numpy as np
rng = np.random.default_rng(0)
for d in (2, 1000):
    X = rng.random((200, d)); dist = np.linalg.norm(X[1:] - X[0], axis=1)
    print(d, round(dist.max() / dist.min(), 1))

2 14.2
1000 1.1

Answer. A ratio far above 1 for d = 2, and close to 1 for d = 1000: the *curse of dimensionality*.

11. The idea: compress, keep the important information

PCA finds new axes (principal components) that capture the most variance (spread = information), then lets you keep only the top few.

Analogy: A 3D cloud of points shaped like a flat pancake. You can describe it well using just 2 axes along the pancake, dropping the thin third.

Original 2D data along a diagonal:    PC1 = the diagonal (most spread)

• • • PC2 = perpendicular (tiny spread)
• • • → keep only PC1: 2D → 1D, little info lost
• • •

12. Steps

1. Standardize data (essential!)
2. Find directions of maximum variance (PC1, PC2, …) — these are perpendicular to each other
3. Project data onto the top-k components

from sklearn.decomposition import PCA
pca = PCA(n_components = 2)
X2 = pca.fit_transform(X_scaled)
print(pca.explained_variance_ratio_)     # e.g. [0.62, 0.21] → 83% info kept
pca95 = PCA(n_components = 0.95)          # automatically keep 95% of variance

Uses: 2D/3D visualization; speeding up models; noise removal; compression. Downside: new features are mixtures — hard to interpret.

Worked Problem · Pca On Points Along A Line

Problem. Points [[1, 2], [2, 4], [3, 6]] lie on a line. Reduce them to 1 dimension with PCA and report the variance kept.

1. Center the data by subtracting the means (2, 4): [[−1, −2], [0, 0], [1, 2]].
2. The points all lie along the direction (1, 2). PCA finds that direction as the first component: (1, 2) ÷ √5.
3. Project each point on it: (−1×1 + −2×2) ÷ √5 = −2.236, then 0, then +2.236.
4. One component explains all of the variance, because the second direction has no spread at all.
5. The sign of a component is arbitrary, so we print absolute values.

import numpy as np
from sklearn.decomposition import PCA
X = np.array([[1, 2], [2, 4], [3, 6]])
p = PCA(n_components=1).fit(X)
print(np.round(np.abs(p.transform(X).ravel()), 3))
print(np.round(p.explained_variance_ratio_, 3))

[2.236 0.    2.236]
[1.]

Answer. Coordinates [2.236, 0, 2.236] (up to sign) and variance kept [1.0]: 2 numbers per point became 1 with nothing lost.

Your Turn · How Many Components?

Problem. The explained-variance ratios of 4 components are [0.60, 0.25, 0.10, 0.05]. How many do you keep to retain at least 90% of the variance?

Try it on paper or in a notebook first. Then check the solution.

Solution — Step By Step

1. Add them up one at a time (cumulative sum): 0.60, 0.85, 0.95, 1.00.
2. The first total that reaches 0.90 is the third (0.95).
3. So keep 3 components.

import numpy as np
print(np.round(np.cumsum([0.60, 0.25, 0.10, 0.05]), 2))

[0.6  0.85 0.95 1.  ]

Answer. Keep 3 components (cumulative variance 0.95).

PART E — EMBEDDINGS ★ (critical for GenAI)

13. The problem

Computers only understand numbers. How do we represent words, sentences, images, users so that similar meanings are similar numbers?

Worked Problem · One-Hot Vectors Know Nothing

Problem. Words cat, dog, car as one-hot vectors: cat = [1,0,0], dog = [0,1,0], car = [0,0,1]. Compute the distance between cat and dog, and between cat and car.

1. cat − dog = [1, −1, 0], so the distance is √2 ≈ 1.414.
2. cat − car = [1, 0, −1], so the distance is also √2.
3. One-hot treats every word as equally different, although cat and dog are related. Embeddings fix this.

import numpy as np
c, d, k = np.eye(3)
print(round(np.linalg.norm(c - d), 3), round(np.linalg.norm(c - k), 3))

1.414 1.414

Answer. Both 1.414: one-hot encoding cannot say that cat is nearer to dog than to car.

14. Bad idea: one-hot / ID

cat=1, dog=2, car=3 — numbers say nothing about meaning. one-hot vectors are all equally far apart.

15. Embedding = a vector of numbers capturing meaning

"cat"   → [0.21, -0.55, 0.83, ...]   (e.g. 384 or 768 or 1536 numbers)
"dog"   → [0.25, -0.50, 0.80, ...]   ← close to cat
"car"   → [-0.70, 0.31, 0.02, ...]   ← far from cat

• Meaning similarity = vector closeness (measured with cosine similarity — your Days 2–3 assignment!)
• Famous example: vec("king") − vec("man") + vec("woman") ≈ vec("queen")
• Learned automatically by neural networks trained on huge text data.

Think of it as coordinates on a “map of meaning”

(animals region)          (vehicles region)
  cat • • dog                car • • truck

• • lion • bus

Worked Problem · Search By Meaning

Problem. Tiny embeddings: cat = [0.9, 0.1], dog = [0.8, 0.2], car = [0.1, 0.9]. A query “puppy” is [0.85, 0.15]. Rank the words by cosine similarity.

1. Cosine similarity compares direction: dot product ÷ product of lengths.
2. “puppy” points almost the same way as “dog” and “cat”, and nearly opposite in direction from “car”.
3. Compute all three similarities and sort them from high to low.

import numpy as np
E = {"cat": [0.9, 0.1], "dog": [0.8, 0.2], "car": [0.1, 0.9]}
q = np.array([0.85, 0.15])
cos = lambda a, b: np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
for w, v in sorted(E.items(), key=lambda kv: -cos(q, kv[1])):
    print(w, round(cos(q, np.array(v)), 3))

cat 0.998
dog 0.998
car 0.281

Answer. The ranking is printed above: *cat and dog are close to the query, car is far*. Search by meaning is exactly this: find the nearest vectors.

Your Turn · Where Does A New Word Land?

Problem. Using the same three words, which is closest to “truck” = [0.15, 0.95]?

Try it on paper or in a notebook first. Then check the solution.

Solution — Step By Step

1. “truck” points mostly along the second axis, like “car” = [0.1, 0.9].
2. Compute cosine similarity to each word and take the largest.

import numpy as np
E = {"cat": [0.9, 0.1], "dog": [0.8, 0.2], "car": [0.1, 0.9]}
q = np.array([0.15, 0.95])
cos = lambda a, b: np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
print(max(E, key=lambda w: cos(q, np.array(E[w]))))

car

Answer. car.

16. Where embeddings are used (this is the future roadmap!)

17. Tiny semantic search example

# pip install sentence-transformers
from sentence_transformers import SentenceTransformer
import numpy as np
model = SentenceTransformer("all-MiniLM-L6-v2")       # small, free, 384-dim
docs = ["How to reset my password", "Best pizza recipes", "Change account login "
   "credentials"]
D = model.encode(docs)                                 # shape (3, 384)
q = model.encode(["I forgot my password"])            # shape (1, 384)
def cos(A, B):
    A = A / np.linalg.norm(A,axis = 1,keepdims = True) ; B = B / \
        np.linalg.norm(B,axis = 1,keepdims = True)
    return A @ B.T
scores = cos(q, D)[0]
print(docs[scores.argmax()], scores)     # returns the password-related docs

Notice: no shared keywords needed (“forgot password” ↔ “login credentials”) — it matches mean-ing.

Familiarity checklist for today (you need to be able to say):

• k-NN: vote among k nearest neighbors; needs scaling
• k-Means: assign to nearest centroid → move centroid → repeat
• PCA: fewer features keeping most variance
• Embeddings: vectors where closeness = similar meaning Move on when you can… ☐ compute a Euclidean distance by hand ☐ classify a point with k-NN and explain the role of k ☐ run two rounds of k-Means by hand ☐ explain PCA as keeping the directions with the most spread ☐ compare two embeddings with cosine similarity If you cannot tick most of these, repeat the worked problems for this day. Taking an extra day is fine; it is not falling behind.