From Scratch: K-Nearest Neighbours
Build it to understand it.
The physicist Richard Feynman left a line on his blackboard. What I cannot create, I do not understand. You've used these algorithms through a library. Now, let's take off the lid, and build the core ones ourselves, in plain NumPy. Interviewers love this too.
- What I cannot create, I do not understand
- Take off the lid
- Interviewers love this
KNN in twenty lines
We write a class with the same fit and predict methods as scikit learn. Fit does almost nothing, it simply remembers the data. In predict, for each row, we compute the distance to every stored point. Argsort finds the nearest K, and bincount tallies their votes. Twenty lines, with no libraries doing the real work. Run it, on real wine data. We get very high accuracy. You can now see why prediction is slow. There's a full loop over the data, for each new row.
import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
class KNN:
def __init__(self, k=5):
self.k = k
def fit(self, X, y):
self.X, self.y = X, y
return self
def predict(self, X):
out = []
for row in X:
dist = np.sqrt(((self.X - row) ** 2).sum(axis=1))
nearest = self.y[np.argsort(dist)[:self.k]]
out.append(np.bincount(nearest).argmax())
return np.array(out)
X, y = load_wine(return_X_y=True)
X = StandardScaler().fit_transform(X)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)
print("Accuracy:", (KNN(5).fit(X_tr, y_tr).predict(X_te) == y_te).mean().round(3))Accuracy: 0.978
Logistic regression from scratch
Now logistic regression. Fit starts all of the weights at zero. Then it loops. Compute the chances, using the sigmoid. Then these two lines are gradient descent, with the gradient of a loss called log loss. Notice how similar it is to what we wrote for linear regression. Only the sigmoid is new. Run it, and we get high accuracy, from fifteen lines of real logic. Library versions add many extras, but the heart is exactly what you see here.
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
class Logistic:
def __init__(self, lr=0.1, steps=2000):
self.lr, self.steps = lr, steps
def fit(self, X, y):
self.w, self.b = np.zeros(X.shape[1]), 0.0
for _ in range(self.steps):
p = self.chance(X)
self.w -= self.lr * X.T @ (p - y) / len(y)
self.b -= self.lr * (p - y).mean()
return self
def chance(self, X):
return 1 / (1 + np.exp(-(X @ self.w + self.b)))
def predict(self, X):
return (self.chance(X) >= 0.5).astype(int)
X, y = load_breast_cancer(return_X_y=True)
X = StandardScaler().fit_transform(X)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)
print("Accuracy:", (Logistic().fit(X_tr, y_tr).predict(X_te) == y_te).mean().round(3))Accuracy: 0.972
Summary
Two algorithms, built from nothing. Notice that once you know gradient descent, logistic regression was easy. Next, we build the two models that many people consider to be a black box, k means and a real decision tree.
Key takeaways- KNN: remember, measure, vote
- Logistic: sigmoid plus descent
- You can build what you use