Unsupervised Oblique RF vs standard unsupervised RF is almost 10x slower

[adam2392]

trafficstars

Here is a snippet from a benchmark I was running increasing sample size and n_features:

==============================
Iteration 020 of 025
==============================

n_samples: 125 and n_features: 50000
Unsupervised RF
Speed: 1.706s
Max depth: 14

Unsupervised Oblique RF
Speed: 214.651s
Max depth: 28


==============================
Iteration 021 of 025
==============================

n_samples: 150 and n_features: 150
Unsupervised RF
Speed: 0.257s
Max depth: 15

Unsupervised Oblique RF
Speed: 0.263s
Max depth: 16


==============================
Iteration 022 of 025
==============================

n_samples: 150 and n_features: 12612
Unsupervised RF
Speed: 1.037s
Max depth: 13

Unsupervised Oblique RF
Speed: 14.797s
Max depth: 22


==============================
Iteration 023 of 025
==============================

n_samples: 150 and n_features: 25075
Unsupervised RF
Speed: 1.567s
Max depth: 14

Unsupervised Oblique RF
Speed: 54.258s
Max depth: 23


==============================
Iteration 024 of 025
==============================

n_samples: 150 and n_features: 37537
Unsupervised RF
Speed: 2.034s
Max depth: 13

Unsupervised Oblique RF
Speed: 107.163s
Max depth: 22


==============================
Iteration 025 of 025
==============================

n_samples: 150 and n_features: 50000
Unsupervised RF
Speed: 2.414s
Max depth: 15

Unsupervised Oblique RF
Speed: 200.495s
Max depth: 23

It seems that unsupervised oblique RF is scaling very poorly. I suspect two possibilities:

1. the tracking of constant features possibly
2. there is a bug I'm not aware of in the code

[PSSF23]

From the observations, it seems that unsupervised oblique RF has much deeper trees when their speed is significantly slower than unsupervised RF.

[adam2392]

I tried again by removing some unnecessary for loops in the code and get this:

==============================
Iteration 020 of 025
==============================

n_samples: 125 and n_features: 50000
Unsupervised RF
Speed: 1.036s
Max depth: 14

Unsupervised Oblique RF
Speed: 159.429s
Max depth: 21


==============================
Iteration 021 of 025
==============================

n_samples: 150 and n_features: 150
Unsupervised RF
Speed: 0.154s
Max depth: 13

Unsupervised Oblique RF
Speed: 0.173s
Max depth: 16


==============================
Iteration 022 of 025
==============================

n_samples: 150 and n_features: 12612
Unsupervised RF
Speed: 0.567s
Max depth: 15

Unsupervised Oblique RF
Speed: 11.728s
Max depth: 20


==============================
Iteration 023 of 025
==============================

n_samples: 150 and n_features: 25075
Unsupervised RF
Speed: 0.785s
Max depth: 16

Unsupervised Oblique RF
Speed: 43.155s
Max depth: 23


==============================
Iteration 024 of 025
==============================

n_samples: 150 and n_features: 37537
Unsupervised RF
Speed: 1.014s
Max depth: 14

Unsupervised Oblique RF
Speed: 89.822s
Max depth: 25


==============================
Iteration 025 of 025
==============================

n_samples: 150 and n_features: 50000
Unsupervised RF
Speed: 1.123s
Max depth: 13

Unsupervised Oblique RF
Speed: 199.696s
Max depth: 20

There seems to be a 1.5-2x performance gain by removing the unnecessary for loops, but the Oblique Res are still an order of magnitude slower...

[adam2392]

I suppose training 2x deeper trees should slow you down, but I'm surprised it's by an order of magnitude. I guess I would think in log terms since it's a tree... so I guess 2x deeper = 200x slower, which is about what we see.

If that is the case, then the question becomes why is it going so much deeper. Perhaps if I change to fastbic, it will improve.

[adam2392]

My suspicion is that there is still a lot from moving the columns that are constant to the front of the array. This is what sklearn does in main and it's the only discernible difference... so maybe that is something I'll look into. For now #114 will improve things slightly already by 1.5-2x for every unsupervised tree.