Speed up Nearest Neighbour classification in highly duplicated data I have a classification problem on a data set with 3 features and 2,000,000 examples. I have decided that I want to use K-Nearest Neighbors.
Is there a way I can leverage the fact that the data only has 5000-ish unique values to speed up the training and prediction step. By this I mean there are multiple repeated rows.
I assume I can modify the weights parameter on SKLearn, but I don't actually know what I would need to do?
 A: I don’t think you could do anything about the scikit-learn’s implementation, but you could implement it by yourself. $k$-NN in prediction time measures the distance from observation to all the training samples and peaks $k$ samples with the smallest distance. What you could do is to keep only the unique rows and for each row record the count of how often it was observed. Say that $i$-th row is the closest. It was repeated $n_i$ times in the data. When $n_i \ge k$ you pick it as the prediction. When $n_i < k$ you take this row together with the next row, repeating the above procedure, then you take a weighted average of the rows, using the $n_i$ counts as weights. In practice, this reduces to calculating a cumulative sum of the $n_i$ weights and cutting-off it when it reaches $k$, with possible arithmetic corrections if it exceeds $k$. You should expect speedups since the total number of rows is smaller when computing the distances and searching, the most expensive steps in $k$-NN.
Moreover, if you can expect similar repetitions at the prediction time, you could use memorization. You would query the memorized predictions and compute the distances only for the data not observed before. To cut on the storage, you can keep memoized only the samples with the highest $n_i$'s, i.e. the most likely ones.
