Introduction to Decision Tree Learning
A funny thing about decision trees (or random forests) is how conceptually simple they are, but in terms of implementation they're very non-trivial.<p>There's always a point in the lecture or explanation where they go<p><i>So we just find the optimal split/feature based on entropy</i><p>which no one talks a ton about, but naively implemented is something on the order of O(kNlogN). For each split. Multiply that by the number of leaves (2^depth), and multiply that by the number of trees in your forest.<p>I learned this the hard way when I tried implementing random forests on GPU for a class (would not recommend: efficiently forming decision trees seem to involve a lot of data copying and shifting around). I actually learned a lot from reading sklearn's implementation of decision trees in Cython - it uses quite a number of neat tricks to make things really fast.