1
$\begingroup$

I'm wondering whether I'm understanding the process of choosing a node correctly and would like to see if this example makes sense. using the following data :

> df
  Y A B C
1 1 0 1 1
2 0 0 0 1
3 1 1 1 0
4 1 0 1 0
5 1 1 0 1
6 1 0 0 1

I will split the data on A,B,C and evaluate the entropy of each split, where the entropy is computed using

$$ p \; \log_2(p) + (1-p)\; \log_2(1-p) $$

where $p$ is the proportion of successes for a particular split.

When splitting on A I have

  Y A B C
3 1 1 1 0
5 1 1 0 1

and

  Y A B C
1 1 0 1 1
2 0 0 0 1
4 1 0 1 0
6 1 0 0 1

For $A = 1$ (the first data table) I have $p = 1$, then entropy is 0.

for $A=0$ (second table) I have $p=0.75$ and entropy 0.81

So for splitting on $A$ I would state that the entropy is

$$ 0 + 0.81 = 0.81 $$

This is then carried out in a similar manner for $B,C$.

For $B=1$ I find $p=1$ so entropy = 1

For $B=0$ I find $p=0.66$ so entropy = 0.91

Then the entropy for splitting on $B$ is

$$ 0 + 0.91 = 0.91 $$

For $C=1$ I find $p=0.75$ so entropy = 0.81

For $C=0$ I find $p=1$ so entropy = 0

Then the entropy for splitting on $C$ is

$$ 0.81 + 0 = 0.81 $$

Given the above the split which has the highest entropy is $B$, therefore I would choose to split on $B$ first.

I now have a decision tree with one node, and need to select the next node for each branch of $B = 1$ and $B=0$.

This selection is carried out in the same manner as the above.

Is the computation and reasoning in the above valid?

$\endgroup$
1
$\begingroup$

Some corrections in the above:

  • While calculating entropy of a split, you should take into account the weights - fraction of instances in each branch:

$$ entropy(A) = 0 * (2/6) + 0.81 * (4/6) = 0.54\\ entropy(B) = 0 * (3/6) + 0.91 * (3/6) = 0.45\\ entropy(C) = 0 * (2/6) + 0.81 * (4/6) = 0.54 $$

  • While choosing an attribute to split, you should choose the one with lowest entropy after the split. Entropy is the uncertainty, so you want to minimise it. As an example, if the split was perfect (all 0's on one side, and all 1's on the other), then entropy will be 0.

After selection of one node, the tree is built out recursively, as you mention.

$\endgroup$

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.