I have a dataset that contains roughly 21m 768-dimension vectors (which comes in at 60GB large!). I am looking to using Sklearn to train an 8-nearest neighbour model on this data, but I'm not sure how long it would take or if it would be feasible. The following is my code, which is fairly standard:

knn = KNeighborsClassifier(n_neighbors = 8)

I've tried looking into this but there appears to be little on it. How long, very roughly, would this take to complete? Would PCA be a good way to reduce the amount of data being used during learning?

I know this may not be a StackExchange-type question, but sklearn is very scarce on forums and communities. Thanks

  • $\begingroup$ KNN is likely a terrible algorithm to use with that many dimensions $\endgroup$
    – astel
    Sep 22 '20 at 20:56
  • $\begingroup$ @astel Oh, really? I could, of course reduce the dimensions. Would there be any others, like Random Forest, that could be good? $\endgroup$
    – JCunn
    Sep 22 '20 at 21:06
  • $\begingroup$ You can try with a random subsample of your data $\endgroup$
    – Ale
    Sep 22 '20 at 21:40

Like @astel says, KNN is a bad choice for high dimensional data because of the curse of dimensionality(everything seems close to everything else in high dimensional spaces because the "volume" of the space increases exponentially). Not to mention, you have 21 million data points, which makes it time consuming to figure out the nearest neighbors, computationally. If you really want to try a non-parametric model, like you said, random forests are a good choice, but what I have found is that based on the depth of the individual trees, these models themselves can consume a lot of memory. If you have access to a cluster of machines to do your work, I recommend trying Spark's MlLib. You could also reduce the dimensionality of the data, and that might or might not help, and depends on the data.

Parametric models like logistic regression, or SVM(with kernels if you want non-linearity) might also be easier to run using sklearn.


Theoretically, zero.

The K-NN doesn't actually fit anything, it just stores where each datum is.

Now, prediction would take a while, because you'd need to compare new data with each 21M samples in training data.

  • $\begingroup$ I didn't thinking of the amount of comparisons that would have to be done. Do you think it's no a model I should go for then? $\endgroup$
    – JCunn
    Sep 22 '20 at 21:08
  • $\begingroup$ @JCunn there are variants of K-NN for big data. You could look into that, if you want to stick to the K-NN. $\endgroup$
    – Firebug
    Sep 22 '20 at 23:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.