Application: GA on Decision Trees

Source: Unit 5 §7

The problem: a mobile service provider wants to classify customer types. Build a system that classifies the Mobile User Dataset using decision trees optimised by a genetic algorithm.

≡FactsWhy mobile-user classification is not ordinary classification

• It uses context-information attributes, not just general attributes.
• Not all attributes contribute equally to the classification, so a tree grown greedily on gain alone is a poor fit.

The pipeline

The tree is not the deliverable. It is a rule generator whose output the GA then optimises.

→StepsThe four stages

1. Preprocessing of the raw mobile-user data.
2. Rule generation from decision trees, using entropy, gain ratio and split information.
3. Optimisation of the rules by a genetic algorithm.
4. Testing the optimised rules.

Coding the rules for the GA

≡FactsThe encoding

• Each chromosome is one classification rule, binary-encoded.
• Some chromosomes end up as the solution; the final rule set is sorted by rule quality.

→StepsRule-based ordering when classifying a new sample

1. Try the best rule first.
2. If it cannot recognise the sample, try the next rule down the sorted list.
3. If no rule matches, assign the default class.

≡FactsWhy a GA on top of a tree at all

A decision tree is built greedily, one locally best split at a time, so the rule set it produces is a local optimum. The GA treats the rules as a population and searches the space of rule sets, which is exactly the global perspective the greedy construction lacks.