# What is node impurity/purity in decision trees in plain english? Why do we need it?

Is it more important in classification than in regression analysis? Do we measure it with Gini index? If so, what are the usual values and implications?

# What is node impurity/purity in decision trees?

### Classification Trees

Intuitively, you can think of a set of examples as the set of atoms in a metallic ball, while the class of an example is like the kind of an atom (e.g. gold).

• If all of the ball's atoms were gold - you would say that the ball is purely gold, and that its purity level is highest (and its impurity level is lowest). Similarly, if all of the examples in the set were of the same class, then the set's purity would be highest.
• If 1/3 of the atoms were gold, 1/3 silver, and 1/3 iron - you would say that for a ball made of 3 kinds of atoms, its purity is lowest. Similarly, if the examples are split evenly between all of the classes, then the set's purity is lowest.

(I took the analogy from here.)

So the purity of a set of examples is the homogeneity of its examples - with regard to their classes.

### Regression Trees

The gist of the idea of purity is quite the same here (which is fortunate, as I am afraid this analogy is less natural).
You can think of a set of examples as the set of pixels in a picture that should contain just a single color, while the value of a target variable (of an example) is like a color on the continuous color spectrum.

• If the color of most of the pixels is very close to purple, you would say that the picture is almost pure purple. Similarly, if the target variables of the examples are very close to each other, then the set's purity is quite high.

# Why do we need purity?

Wikipedia says:

The problem of learning an optimal decision tree is known to be $$NP$$-complete [...]

i.e. any algorithm that is guaranteed to find the optimal decision tree is inefficient (assuming $$P \ne NP$$, which is still unknown), but algorithms that don't guarantee that might be more efficient.

So people came up with such more efficient algorithms, and some of them are based on measures of impurity.

Most of these algorithms use a process called top-down induction of decision trees (TDIDT), and look roughly like this:

1. Denote the examples set $$S$$.
2. If $$S$$ is pure enough, return a single-node tree, labeled with the most common class in $$S$$ (or with the average of target values in $$S$$, in case of a regression tree).
3. Otherwise, find a test that examines a feature (or multiple features) and divides $$S$$ accordingly into disjoint sets $$S_1,...,S_k$$, such that their "overall purity" is highest (e.g. the average purity of $$S_1,...,S_k$$ is highest).
4. Return a tree whose root has $$k$$ sons. The root is the test, and its sons are calculated by recursively calling the algorithm for each of $$S_1,...,S_k$$.

i.e. the most important part of such algorithms - deciding how to split $$S$$ - is determined by purity.

# Do we measure purity with Gini index?

Gini index is one of the popular measures of impurity, along with entropy, variance, MSE and RSS.

I am not sure what you mean by important, but in both cases we try to split S so that the "overall purity" of $$S_1,...,S_k$$ is highest, so i would say that purity is equally important in both kinds of decision trees.