0
$\begingroup$

I want to know the details of feature importance computing of random forest with gini index. I refer to this Chinese blog:https://www.jianshu.com/p/7a876bb876b9. But I don't understand clearly these mathematical forms in blog.

for example

As the node m after twos branches(Il, Ir) splitting, the gini index is computing as following VIM1

And feature Xj in the decision ith tree ,and be in nodel of M set, and the feature importance of Xj in the ith tree is computing as following:

VIM2

And I confusing about M set, what's the meaning of M set? I think that the feature Xj in ith tree just one node not a M set? If you guys have detailed computing method, please tell me!

$\endgroup$
2
$\begingroup$

Let's start with this formula for the Variable Importance Measure (VIM) based in Gini Impurity (GI)*:

$$VIM_{jm}^{(Gini)} = GI_m - GI_l - GL_r$$

Here, $m$ is a given node in a single decision tree which performs a split on feature $j$. For this node you can compute the Gini Impurity $GI_m$ (see * note at the very bottom for the formula). Now this node has two childs: a left node $l$ and a right node $r$. For these the Gini Impurities are $GI_l$ and $GL_r$ respectively. If you substract the Gini impurities of the child nodes from the Gini Impurity of node $m$, then you know by how much the split performed by this node has decreased the overall Gini Impurity. Because before the split it was $GI_m$ and after the split the remaining impurity is the sum of $GL_l$ of $GL_R$. Therefore, the difference ($GI_m - (GI_l + GL_r) = GI_m - GI_l - GL_r$) is the corresponding impurity reduction.

(as a side node: this is the unweighted gini importance calculation since $GI_l$ and $GI_r$ are considered with equal weights. There are also different weighted versions. For details and a comparison please refer to "The effect of splitting on random forests", Hemant Ishwaran, Mach Learn (2015) 99:75–118)

For feature importance however, you're interested in the overall importance of each feature and not a single node. And a given feature can be present in different branches of a tree.

Here is an example:

Decission Tree example

(Source: "Artificial intelligence - a modern approach"; Norvig, Russell; 2010; 3rd Ed)

As you can see "Alternate?" is being used at multiple nodes. That is why they use set $M$ in the blog you posted to derive the overall importance of a feature $j$ in a tree $i$:

$$VIM_{ij}^{(Gini)} = \sum_{m \in M}VIM_{jm}^{(Gini)}$$

As a side node: in some papers and books the authors do not calculate the impurity indexed by features $j$ but indexed by a split value of a given node, e.g. $s$, (which of course operates on features). Don't get confused by that.


* The Gini Impurity of a given node $m$ with $k \in K$ being the classes is defined as follows: $$GI_m = \sum_{k \in K} \hat{p}_k(m)(1- \hat{p}_k(m)).$$

Where $\hat{p}_k(m)$ is the class frequency of class $k$ in node $m$.

$\endgroup$
5
  • $\begingroup$ thanks for your detailed explanation. I think initially that one feature can be only used one time in a tree. you are so good at the random forest. Do you have own site or blog link? $\endgroup$ – tktktk0711 Dec 18 '19 at 1:07
  • $\begingroup$ @tktktk0711 Happy to help! If you think this sufficiently answers your question please accept the answer so the system marks your question as done. I do not have a blog or website :) $\endgroup$ – Sammy Dec 18 '19 at 6:20
  • $\begingroup$ I have accepted, do you have other contact way, I want to communicate with you about tree model research topic $\endgroup$ – tktktk0711 Dec 18 '19 at 6:35
  • $\begingroup$ Unfortunately there is no feature to send personal messages on this site. You could open a chat room to discuss. But everyone else will be able to see the content. $\endgroup$ – Sammy Dec 18 '19 at 8:01
  • $\begingroup$ thanks. If possible, you can sent me email to me: 285662034@qq.com $\endgroup$ – tktktk0711 Dec 18 '19 at 9:43

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.