| 17 | |
| 18 | |
| 19 | class KNN(object): |
| 20 | def __init__(self, k): |
| 21 | self.k = k |
| 22 | |
| 23 | def fit(self, X, y): |
| 24 | self.X = X |
| 25 | self.y = y |
| 26 | |
| 27 | def predict(self, X): |
| 28 | N = len(X) |
| 29 | y = np.zeros(N) |
| 30 | |
| 31 | # returns distances in a matrix |
| 32 | # of shape (N_test, N_train) |
| 33 | distances = pairwise_distances(X, self.X) |
| 34 | |
| 35 | |
| 36 | # now get the minimum k elements' indexes |
| 37 | # https://stackoverflow.com/questions/16817948/i-have-need-the-n-minimum-index-values-in-a-numpy-array |
| 38 | idx = distances.argsort(axis=1)[:, :self.k] |
| 39 | |
| 40 | # now determine the winning votes |
| 41 | # each row of idx contains indexes from 0..Ntrain |
| 42 | # corresponding to the indexes of the closest samples |
| 43 | # from the training set |
| 44 | # NOTE: if you don't "believe" this works, test it |
| 45 | # in your console with simpler arrays |
| 46 | votes = self.y[idx] |
| 47 | |
| 48 | # now y contains the classes in each row |
| 49 | # e.g. |
| 50 | # sample 0 --> [class0, class1, class1, class0, ...] |
| 51 | # unfortunately there's no good way to vectorize this |
| 52 | # https://stackoverflow.com/questions/19201972/can-numpy-bincount-work-with-2d-arrays |
| 53 | for i in range(N): |
| 54 | y[i] = np.bincount(votes[i]).argmax() |
| 55 | |
| 56 | return y |
| 57 | |
| 58 | def score(self, X, Y): |
| 59 | P = self.predict(X) |
| 60 | return np.mean(P == Y) |
| 61 | |
| 62 | |
| 63 | if __name__ == '__main__': |