4
$\begingroup$

I am trying to port this little piece of R code to python:

rf <- randomForest(features, proximity = T, oob.prox = T, ntree = 2000)
dists <- as.dist(1 - rf$proximity)

with parameters
oob.prox: Should proximity be calculated only on “out-of-bag” data?
proximity: if proximity=TRUE when randomForest is called, a matrix of proximity measures among the input (based on the frequency that pairs of data points are in the same terminal nodes).

I am currently trying using sklearn.ensemble.RandomTreesEmbedding for this task, however there is no functionality for the proximity matrix. I found the following developer comment though:

We don't implement proximity matrix in Scikit-Learn (yet). However, this could be done by relying on the apply function provided in our implementation of decision trees. That is, for all pairs of samples in your dataset, iterate over the decision trees in the forest (through forest.estimators_) and count the number of times they fall in the same leaf, i.e., the number of times apply give the same node id for both samples in the pair.

And so I tried, utilizing numpy's pdist() function along with my custom distance (or in this case, proximity) measure. I still have several problems:

  1. The proximity function is outstandingly slow
  2. How to handle the out-of-bag behaviour
  3. How to recreate the exact behaviour of as.dist(1- rf$proximity): I think I need to normalize my count matrix, then subtract it from 1 and then afterwards compute the euclidean distances between its rows!?

My code as of now looks like this:

# grow a random forest from points
rf = ensemble.RandomTreesEmbedding(n_estimators=200, 
    random_state=0,
    max_depth=5
)
rfdata = rf.fit_transform(xdata);


# define an affinity measure function to use with numpy's pdist
def treeprox(u, v):
    leafcount = 0
    # needs reshaping for single samples
    u = u.reshape(1,-1)
    v = v.reshape(1,-1)
    a = rf.apply(u)
    b = rf.apply(v)
    # count number of times they fall in the same leaf 
    # (use of np forces element-wise)
    c = np.sum(np.array(a)==np.array(b))
    return c

distm = pdist(xdata, proxfun)
distm = squareform(distm)

There must be a better way I guess, since this functionality is readily provided by the R package randomForest.
Any suggestions?
tia

$\endgroup$
  • $\begingroup$ I am just starting looking into the same task. There is a similar question in SO stackoverflow.com/questions/25090773/…? Do you have any updates? $\endgroup$ – Keith Apr 19 '17 at 21:37
  • $\begingroup$ above code is what I have and what technically works, but it is unusable slow. I think the only solution here would be to dig into the actual sklearn.ensemble.RandomTreesEmbedding module and figure out a neat way to build the matrix at runtime (e.g. how it's happening in R). Don't think I will get around to do this soon... $\endgroup$ – Dorian Apr 20 '17 at 7:33
  • $\begingroup$ OK, I intend to do something similar and will update the SO post. FYI, I think np.count_nonzero() is faster than np.sum() $\endgroup$ – Keith Apr 20 '17 at 16:37
1
$\begingroup$

I have written some code for this. It can be found here. In answer to your specific questions:

  1. I have tried to optimize for speed. What I did should be a little faster than the code above.
  2. I do not use out of bag records. In fact the original documentation does not suggest this. I created another post to see if the consequences are understood.
  3. This is handled in my code by normalizing by the total possible leaves that could be matched.
$\endgroup$
  • $\begingroup$ have you tested speed yours against mine? with my dataset of dimension about (3500,340) even using 500 trees took a whole night! $\endgroup$ – Dorian Apr 28 '17 at 14:08
  • $\begingroup$ I could not get your implementation running. What is proxfun? I do that in about 1 hour. I actually made a ticket about making it faster and cut out the slow part. stackoverflow.com/questions/43621977/build-matrix-without-loops/… Maybe add your solution in the format for that question. $\endgroup$ – Keith Apr 28 '17 at 16:14
  • $\begingroup$ On 3500 rows for 500 trees it takes 23 seconds if I include the time it takes to train the tree $\endgroup$ – Keith Apr 28 '17 at 23:23
  • $\begingroup$ c&p mistake; it's the treeprox function. u mean my code takes 23 seconds? have you tested it with 340 variables? $\endgroup$ – Dorian Apr 29 '17 at 16:31
  • $\begingroup$ No mine took 23s. I only have 30 input variables. I am not sure that this would change the call time of apply() much so it may not matter much. If update with a toy example of working code Ill see what the time for yours takes. Otherwise try mine, note that the prox matrix in mine can be calculated for any categorical variable. $\endgroup$ – Keith Apr 30 '17 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.