Browse and solve 1,200+ machine learning coding challenges on Deep-ML. Filter by difficulty (beginner, intermediate, advanced) and category (linear algebra, machine learning, deep learning, NLP, computer vision). Write Python solutions in the browser and get instant feedback against test cases.
Deep-ML | Probabilistic KNN with a Mahalanobis Metric and the Error-vs-K CurveProbabilistic KNN with a Mahalanobis Metric and the Error-vs-K Curve
Probabilistic KNN with a Mahalanobis Metric and the Error-vs-K Curve
MediumMachine Learning
Example:
Input:
```python
import numpy as np
X = np.array([[1, 0], [0, 1], [1, 1], [-2, 0], [0, -2], [3, 3], [-3, 3]])
y = np.array([1, 1, 1, 0, 0, 0, 0])
P = knn_proba(X, y, np.array([[0, 0]]), K=5, n_classes=2)
print(np.round(P, 4).tolist())
```
Output:
[[0.4, 0.6]]
Reasoning:
The five nearest training points to the origin are at squared distances 1, 1, 2, 4 and 4 (indices 0, 1, 2, 3, 4) with labels 1, 1, 1, 0, 0, so the query gets p(y = 0) = 2/5 and p(y = 1) = 3/5, as in Figure 16.1a. The two far points never enter the neighbourhood.
A K nearest neighbour classifier does not have to return a single label. Murphy defines it as a distribution over classes, the fraction of the K nearest training points that carry each label:
p(y=c∣x,D)=K1∑n∈NK(x,D)I(yn=c)
Neighbours are found with the Mahalanobis distance dM(x,x′)=(x−x′)⊤M(x−x′) for a positive definite M; M=I gives the Euclidean distance.
Implement two functions.
knn_proba(X_train, y_train, X_query, K, n_classes, M=None) returns an array of shape (n_query, n_classes) whose row i is the distribution above for query i.
M=None means the Euclidean distance.
Break distance ties by training index: when several training points are equally far, the one with the smaller index is the nearer neighbour.
Labels are integers in 0,…,C−1.
error_vs_k(X_train, y_train, X_test, y_test, Ks, n_classes, M=None) returns two lists of floats, the training and the test misclassification rates for each K in Ks.
The predicted label is the class with the largest probability; ties go to the smallest class index.
Training points are classified against the full training set, including themselves, so a point is always its own nearest neighbour at distance 0.