Fall 2025 • Machine Learning Course
PCA and K-Means from Scratch
Classifying into many classes, compressing data into fewer dimensions, and finding groups in unlabeled data are three tasks that show up in almost every real machine learning pipeline. In this assignment we built the standard tool for each from scratch in NumPy and SciPy, so every step, from the loss function to the eigendecomposition, is code we wrote and can explain.
What We Built
- Multinomial logistic regression. A linear classifier for k classes that minimizes the multinomial deviance (cross entropy), written with log-sum-exp for numerical stability and optimized with SciPy.
- PCA and kernel PCA. PCA centers the data and takes the top eigenvectors of its covariance, then projects new points onto them. Kernel PCA does the same through a kernel matrix, so it can capture curved structure.
- k-means. Lloyd's algorithm with random starting centers, repeated 100 times to keep the run with the lowest objective, plus a sweep over k from 2 to 9 to choose the number of clusters.
- Kernel k-means. Clustering through a Gaussian kernel, which can separate shapes such as two interleaving moons that plain k-means cannot.
Experiments used two synthetic four class datasets: in Model 1 the class centers sit along a diagonal line, and in Model 2 they sit in the four quadrants.
Results
Multiclass classifier: accuracy by training set size n
| n | Train M1 | Train M2 | Test M1 | Test M2 |
|---|---|---|---|---|
| 16 | 0.9250 | 0.9938 | 0.7325 | 0.8579 |
| 32 | 0.8844 | 0.9844 | 0.7940 | 0.8903 |
| 64 | 0.8625 | 0.9578 | 0.8246 | 0.8940 |
| 128 | 0.8594 | 0.9383 | 0.8327 | 0.9174 |
More training data narrows the gap between training and test accuracy: test accuracy climbs from 73% to 83% on Model 1 and from 86% to 92% on Model 2.
PCA: accuracy after projecting to k dimensions
| Dimensions k | Train M1 | Train M2 | Test M1 | Test M2 |
|---|---|---|---|---|
| 1 | 0.8545 | 0.6509 | 0.8437 | 0.6272 |
| 2 | 0.8538 | 0.9412 | 0.8375 | 0.9169 |
One principal component is enough for Model 1, whose classes lie along a single direction. Model 2 needs both: dropping to one dimension costs about 30 points of accuracy.
k-means: objective value for each number of clusters
The objective always falls as k grows, so we looked for the elbow: big drops from 2 to 3 and 3 to 4, then gains under 0.2 per extra cluster. We chose k = 4.
What We Learned
- Whether dimensionality reduction helps depends entirely on the shape of the data, not on a rule of thumb.
- PCA also acts as a regularizer: training and test accuracy stayed within 1 to 3 points of each other after projection.
- Adding clusters always lowers the k-means objective, so the number of clusters has to be read from how fast the objective improves, not from its value.
Completed as a pair assignment with a teammate. The code stays private since it is graded coursework.
Python
NumPy