ClassifierEvaluator is slow

[dansbits]

Even for a fairly small data set, Lurn::Evaluation::ClassifierEvaluator can take 10+ seconds to calculate precision and recall. This isn't very complicated math and should be a lot faster.

[carlzimmerman]

It takes me like 45 seconds to do a KNN Regression over 20,000 rows.. but Ruby is single threaded right? Using a Postgresql DB..

[dansbits]

Yeah...I've been meaning to get to this but haven't got around to it. Yes, useful multi-threading is not available in Ruby but I don't think that's the biggest bottle-neck here. The method just isn't written in an efficient way.

I can spend some time speeding this up this week unless you'd like to try.

For benchmarking, are you able to share the specific data and code you're using?

[carlzimmerman]

I'll take a crack at it.. no promises!

[dansbits]

Awesome! Let me know if I can support in any way. Can you clarify, is the 45 seconds how long it takes to make predictions with your KNN model or to run the ClassifierEvaluator?

[carlzimmerman]

It takes around 45 seconds to make a prediction on 20,000 rows with 5 attributes.

[dansbits]

Ok. I see, so this is for the KNN Classifier, not for the ClassifierEvaluator. When I originally wrote this issue it was specifically related to how slow the ClassifierEvaluator was. I think it would make sense to open a new issue about speeding up nearest neighbor search to keep things tidy.

The nearest neighbor search is not very efficient now. It's does a full scan of all data points and computes the distance from your new observation for each. It's possible to only compute the distance metric for a subset of the training data.

KDTrees is one solution. Here is an introduction to KDTrees and how they can be used for speeding up nearest neighbor searches.
https://www.analyticsvidhya.com/blog/2017/11/information-retrieval-using-kdtree/

I know sklearn uses ball trees as another option for nearest neighbor search but if I'm honest I know less about this algorithm. I found this post which explains a bit about KD trees and ball trees.
https://ashokharnal.wordpress.com/tag/ball-tree-explained-in-simple-manner/