Pessimistic Pruning

Madcap

Hi, I was hoping someone could explain (simply!) how pessimistic pruning works in relation to post pruning decision trees and how confidence level comes into it?
I understand it is similar to cost complexity however if I am being honest I don't have the best grasp of that either.
I have been on the Decision Tree page from RapidMiner but it didn't give me much of a hint.
Thanks for any help!
-Madcap

varunm1

Hello @Madcap

Pessimistic pruning is a post-pruning approach. 

In post pruning, trees are built based on rules until they classify all the labels. Once the tree is built, each rule is removed and an error rate is checked to see if it went up or went down. Based on this error rate change the algorithm decides whether it should keep (if error increased) that rule in the tree or remove it (if error rate decreases). This is also the way how pessimistic pruning works.

rfuentealba

Pessimistic pruning is top-down:

1. Start from the root.
2. Remove the left node. If the % error increases, mark it as "don't cut". If it decreases, mark it as "cut".
3. Remove the right node. If the % error increases, mark it as "don't cut". If it decreases, mark it as "cut".
4. Rinse and repeat until having the smallest possible tree using this approach.

The optimistic pruning is bottom-up. It begins in the leaves, cutting from there to the top.

Hope this helps,

Rodrigo.

varunm1

Hello @Madcap

Pessimistic pruning is a post-pruning approach. 

In post pruning, trees are built based on rules until they classify all the labels. Once the tree is built, each rule is removed and an error rate is checked to see if it went up or went down. Based on this error rate change the algorithm decides whether it should keep (if error increased) that rule in the tree or remove it (if error rate decreases). This is also the way how pessimistic pruning works.

rfuentealba

Pessimistic pruning is top-down:

1. Start from the root.
2. Remove the left node. If the % error increases, mark it as "don't cut". If it decreases, mark it as "cut".
3. Remove the right node. If the % error increases, mark it as "don't cut". If it decreases, mark it as "cut".
4. Rinse and repeat until having the smallest possible tree using this approach.

The optimistic pruning is bottom-up. It begins in the leaves, cutting from there to the top.

Hope this helps,

Rodrigo.

Madcap

Thanks for your help guys.
This community is great for helping out people.
-Madcap