Why is the Relief algorithm slow for large numbers of observations? I am currently working on a multi-class classification problem and have a dataset of about 130 features and 120000 observations.
Digging through literature I found the Relief feature selection method, or Relief-F as the implementation most used. The concept seems promising however the calculation time is far to long to be of use as a first selection step.
In my example I am using R and the FSelector package. One run of Relief with 10 neighbours and 20 samples takes more than five hours on current hardware. I assume that the implemention is single-threaded.
When looking at the algorithm I do not understand where this massive amount of computational effort is needed. With only 20 samples to analyse I feel this should be a lot quicker. Can anybody shed some light please?
 A: I do not know what the implementers actually did, but a naïve implementation of relief would require you to compute the distance from the 20 sample points to all of the 120000 data points for each of the 130 variables. This gives a total of    

20*120000*130 = 3.12e+08

distance calculations. In your 130 dimensional space, that would require 130 multiplications and 129 additions, so you would need a total of     

20*120000*130*(130+129) = 8.0808e+10 arithmetic operations. 

I guess I am not surprised if that takes a while. 
I just ran relief on a data set with 420 instances of 279 variables using the default of 10 samples. Using the same naïve calculation as above, I think that this should have been     

10*420*279*(279+278) = 6.52e+8 arithmetic operations. 

On my laptop, that took about 7 minutes. So my guess is that on my laptop, your calculation would take     

8.0808e+10 /6.52e+8 * 7 = 867.6 minutes  or about 14.5 hours. 

A: You could also try the Relief-F implementation in the CORElearn package, I am not sure how the implementations differ, but I commonly run ReliefF using CORElearn on datasets of about 100k records and about 20 predictors without taking too much time (minutes not hours).
