10

The scikit-learn implementation of DecisionTreeClassifier has a parameter as class_weight. As per documentation:

Weights associated with classes in the form {class_label: weight}. If not given, all classes are supposed to have weight one.

and

The “balanced” mode uses the values of y to automatically adjust weights inversely proportional to class frequencies in the input data as n_samples / (n_classes * np.bincount(y))

My understanding is that it should be used in case of imbalanced classes.

Question: How does the DT (classification) algorithm use this parameter while determining the ideal split for a given node? Does it consider some kind of "weighted" majority class instead of simple majority class in a region in the prediction space?

Supratim Haldar
  • 309
  • 1
  • 3
  • 10

2 Answers2

7

When deciding on a split at a node, the algorithm basically calculates some metric (entropy or gini impurity) for the given node and for the two resulting left and right nodes after the split. Comparing them tells you how much the split would improve the result.

The statistics for the child nodes are weighted by the number of samples in the left and right node, respectively.

When you use sample_weight this adjusts the count and replaces it with the sum of the sample weights. class_weight gives equal sample weights for each sample based on its class according to its class proportion.

For example, the improvement in impurity is calculated as

$$ \frac{N_{parent}}{N_{total}} * (impurity_{parent} - \frac{N_{right}}{N_{parent}} * impurity_{right-child} - \frac{N_{left}}{N_{parent}} * impurity_{left-child}) $$

Without class_weight or sample_weights, the $N$s are just counts. With class_weight you replace them with the corresponding weights.

The idea is the same for entropy, even though calculated differently.

source code

oW_
  • 6,347
  • 4
  • 28
  • 47
  • Thank you @oW_♦ for the wonderful explanation! – Supratim Haldar Aug 07 '19 at 05:22
  • 1
    Dear @oW_♦ how exactly the above formula causes the decision tree algorithm to make less error for highly weighted examples. Can you give an example? – Sanyo Mn Apr 19 '20 at 12:27
  • 1
    This is actually a bit misleading, as the impurity itself will be affected by the weights, not just the information gain. Check my answer for a more complete explanation. – Maverick Meerkat Dec 11 '23 at 14:09
1

The way to incorporate weights into a tree is in the split criteria. These are sample weights, meaning each observation $i$ has an associated weight to it $w_i$.

E.g., in the case of classification with the Gini impurity, we calculate it for node $t$: $$GINI_t = 1-\sum_{c=1}^C p_{t,c}^2 $$ The $p_{t,c}$ are calculated according to these weights: $$ p_{t,c} = \frac{\sum_{y_i=c,i \in t} w_i}{\sum_{i \in t} w_i} $$

Where $i\in t$ means that the observation is in node $t$. Notice that when the weights $w_i$ are all equal to 1, this is the regular proportion of each class in a node $=\frac{n_{tc}}{n_t}$.

Now, there could be a case where we have an imbalanced data-set, or for what-ever other reason, we would like to give different weights to different classes (e.g., we care more about a certain class than another). This is done by setting class weights: which is simply giving identical sample weights to each class.

For example, a popular way to balance an imbalanced dataset is by giving each class weights equal to the inverse proportion of that class. Suppose I have 100 observations, 80 of class 0, and 20 of class 1. If I give a weight of $\frac{100}{80}$ to class 0, and $\frac{100}{20}$ to class 1, they will have equal weights:

$$ 80\cdot \frac{100}{80} = 20 \cdot \frac{100}{20} $$

In order that the weight is normalized to $n=100$, I also have to divide by the number of classes, in this case 2.

This is what sklearn does. When you set class_weight in a DecisionTreeClassifier, it will calculate the sample weights according to what I mentioned. The code here calls the code here to calculate sample weights according to the class weights. Then the code here will calculate the Gini impurity according to the sample weights.

Update: I made a video about this on my channel, in case you're interested.

Maverick Meerkat
  • 230
  • 2
  • 8