Hi i'd like to know a bit more about kNN-like approach implementations for classification problems, and specifically classification problems where we want to have a probability distribution as an output (to compute logloss like metrics for example)

In packages such as knn for R, a distance matrix is asked as an input. but thats highly inefficient for even medium sized data sets, as such matrix size is n^2 where n is the number of data.

but i can see an easy (empirical) approach where we hash all data into hypercubes, and return for the test set, the implied observed distribution of the train data in the corresponding hypercube it hashes into.

Of course, such an approach has many flaws - it will suffer the curse of dimensionality, but might it not work in there is a lot of data, but not many variables (2,3,4,5 ?) for example ?? - if the data density is heterogeneous, there would be some hypercubes with little data, and others a lot of data. one might then like to zoom on some areas which are overpopulated....

the advantage of hashing is that its computationally efficient and more like linear time/memory than quadratic time/memory

I don't think i'm discovering the moon, so what do you guys think about it ? if there already some algos/libraries basically doing that or much better, which are those ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.