I am working on an unsupervised clustering/classification algorithm for which I am using a random forest frame work among other things. I am using the OpenMP, for parallel programming to construct individual decision trees which are independent of each other. This significantly reduces the training and testing time. But I am not sure how to represent this in the form of O(N), like how to represent time reduction in terms of this complexity.
What are the bounds on the number of decision trees?. If your algorithm has a non-deterministic component, you might want to get the expected and worst case running times.
The variables that i think should be considered are the number of trees $F$, the cost of processing each tree $T(tree)$ and of course the number of processors as a variable $p$. The number of processors can also be written in terms of $N$.
Try to use these variables (except for $p$) in average case and worst case if it makes sense.
regards.
Cristóbal
Actually the number of trees is constant, also there is an upper bound on the number of iterations so i think the complexity is O(n log n ) where n is the number of training examples since random forest is like "divide and conquer" . But I am confused where to put the "P" the number of cores. Correct me if i am wrong.
Ok so the number of trees is constant and you are running several trees in parallel. Lets say "c" is the constant number of trees, then you have a cost of "c*nlog n = O(nlog n)" when running sequential.
When you run it in parallel, your "c" constant becomes "c/p". This is still a constant that will disappear when using asymptotic notation, because p
- Badges
- Science topic
- Similar topics
- Filing