Random Forests with modified partitioning criteria

Here is the context of my question : I'm doing binary classification with unbalanced classes. The measure of performance I'd like to maximise is a modified F-measure : $$F_{\alpha} = \frac{1}{\frac{\alpha}{P}+\frac{1-\alpha}{R}} = \frac{1}{\frac{\alpha}{\frac{TP}{TP+FP}}+\frac{1-\alpha}{\frac{TP}{TP+FN}}}=\frac{TP}{VP+\alpha FP+(1-\alpha)FN}$$ with $\alpha = 0.25$. P=precision ; R=recall ; TP = true positive ; FN = False negative and FP = false positive. This criteria is not to be discussed. Consider it as given.

So in order to classify my observations I'm using random forests. In this model, in order to partition the space of predictors two common criterias are used : either the accuracy or the gini indice. At a given step we are looking for the potential predictor which once divided minimizes the most the misclassification error rate or the gini indice (or sometimes the cross entropy).

But since my final objective is the $F_{0.25}$ measure, why shouldn't I use it directly as the criteria for partitioning ? That is to say at a given step, looking for the predictor which once divided maximises the $F_{0.25}$.

Then two questions : has someone had that kink of idea ? Is there some already implemented variants of random forests with different criteria of partitioning then the usual ones ? Or is it completely a stupid idea..?

Hope my explanations are clear enough. Cheers.

1 Answer

It is a good observation. If you want to optimize some objective function, using another one as a proxy might not be the best idea. If function $f$ and function $g$ measure kind of the same thing, minimizing $f$ will reduce $g$, but it is not a given that it will minimize it.

In some cases, it is acceptable to use the standard cost functions for growing a tree. If the function you want to minimize is related to the function for growing the tree, it might still be a good idea to use the Gini or Entropy cost function, as they are very fast to compute. This will allow you to grow more trees in the same time, which may lead to a better model once average.

However, if your cost function is measuring something else (or something opposite!) than the Gini or Entropy cost function, your model will not have much meaning in the context you are evaluating it in. In such cases, adapting the cost function might help.

Existing options

After a quick look, I don't think Matlab, Scikit-learn nor R support custom cost functions for single tree growing or Random Forest. However, it is possible to add class weight. By putting more or less weight on the positive class, you might be able to manipulate the precision and recall of the grown tree. If you are already familiar with Random Forest in one of those environments, it might be the easiest thing to try first. It just becomes one additional hyperparameter.

I think that the reason to why tree growing is so limited in term of cost functions comes down to efficiency. The number of split points to be evaluated is huge, and the function needs to be evaluated quickly. But there is an effort going on to be able to minimize arbitrary cost function using simple techniques, known as Gradient Boosting (Wikipedia).

Gradient Boosting allows the optimization of any cost function, and it fits trees sequentially by selecting the tree that best corrects the error of the current model, according to your cost function. One thing you should be careful about, is that you should probably consider the True Positives and other measures with regard to a soft assignment, using the probability that the class is a positive instead of the $0,1$ approach, in order to smooth the function. Boosting seems to be used with good results in the Learning to rank problem (Wikipedia), and I think this may be due in part to the ability to adapt to the cost functions used in this framework. Most environment propose gradient boosting, Scikit-Learn, R, XGBoost.

Another option would be to implement trees and random forests using the F-score as a split criterion, but you might suffer through a lot of technical details needed to get your implementation to par with existing systems.

• OK. Thank you very much for this detailed answer. If I summarize, your point is : prior weights may be a convenient simpler solution and implementing a new cost function may be complicated regarding programming detailed and maybe regarding computational intensity. I'm going to think about this. But I'm not sure that taking the $F_{0.25}$ is much more computationally costly than the other ones. Regarding boosting, I'm going to check this. It could be a really good way to tackle my issue. Anyway thanks for your help! If anybody has thoughts about this, feel free to share them. Mar 31 '16 at 18:17
• partykit in its extree_fit has an input "svsplitfun" which is defined as "an optional function for selecting splits". You can define your own split functions. If you could make one, then you could "homebrew" your ensemble, and take either the average (for continuous domain) or the most highly candidated (for binomial classes) as the output. I think 'caret' might allow non-homebrew ensembles, possibly including ex_tree ensembles, both in parallel (forest) as well as in series (gbm). Jan 14 '19 at 22:12