Node Importance in scikit learn

Question

I'm trying to understand exactly how feature_importances in scikit-learn's RandomForestClassifier works. I managed to find this helpful link explaining most of the process: https://towardsdatascience.com/the-mathematics-of-decision-trees-random-forest-and-feature-importance-in-scikit-learn-and-spark-f2861df67e3

I just have two questions about the equation for ni_j (equation for node importance, first equation in the section on feature importance):

1. What is meant by weighted number of samples reaching node j? Are they running all the training samples through the tree and counting how many reach node j? If so, why is the word 'weighted' necessary?
2. Can we be mathematically certain that ni_j >= 0?

Edit: Looking at the code for forest.py, I see this rather mystifying function:

def feature_importances_(self):
        """Return the feature importances (the higher, the more important the
           feature).
        Returns
        -------
        feature_importances_ : array, shape = [n_features]
        """
        check_is_fitted(self, 'estimators_')

        all_importances = Parallel(n_jobs=self.n_jobs,
                                   backend="threading")(
            delayed(getattr)(tree, 'feature_importances_')
            for tree in self.estimators_)

        return sum(all_importances) / len(self.estimators_)

I can see it's calculating a feature importance at each tree, and then taking the mean over all trees. But how it manages to calculate the feature importance at a tree without calling any functions to count samples or compute impurities, I don't understand.

Answer 1

weighted number of samples reaching node j

We have to compare the Parent to two children, then the children's impurity must be weighted.

Let's say the Parent has 100 samples and impurity=5
Children has the same data as [20, 2] and [80, 4]

Dip = 5 - (0.2 * 2 + 0.8 * 4)
=> 5 - 3.6
=> Dip = 1.4

"Weighted" means applying the appropriate ratio i.e. 0.2 and 0.8 here.

Answer 2

Question 1: Decision trees (and therefore random forests) allow weighted samples: you can provide different positive real-valued weights for each row in your training data, and the loss function cares more about the higher-weighted rows. When you use sample weights, you need to adjust all of your calculations, and so "number of samples" becomes "total sample weight" or "weighted number of samples", etc. (Note that in the formula in question, the impurities are also calculated using sample weights.)

Question 2: You've followed this up at Proof that Gini Impurity in a Decision Tree is Monotone Decreasing?

Edit and comments: To follow up on the comments tracing the source code: when you get into the actual tree construction, you get into cython and things get harder to track down. But in this case it's easy enough to just test things out; using the iris dataset, without weights, n_node_samples is the same as weighted_n_node_samples:

clf = DecisionTreeClassifier(max_leaf_nodes=3, random_state=0)
clf.fit(X, y)
print(clf.tree_.n_node_samples)
# [150  50 100  54  46]
print(clf.tree_.weighted_n_node_samples)
# [150.  50. 100.  54.  46.]

And with weights (in this case using class weights, which is equivalent to sample-weighting the rows of each class separately), nodes get affected depending on what their class mix is like:

wclf = DecisionTreeClassifier(max_leaf_nodes=3, random_state=0, class_weight={0: 1, 1: 2, 2: 1})
wclf.fit(X, y)
print(wclf.tree_.n_node_samples)
# [150  50 100  54  46]
print(wclf.tree_.weighted_n_node_samples)
# [200.  50. 150. 103.  47.]

(Specifically, at the root node there are all 150 rows, but the 50 of those that are class 1 get counted double toward the weighted number of samples. At node 5 there are 46 rows, one of which is class 1 and so gets counted double.