Decision Trees

A simple implementation of the Decision Tree learning algorithm as described in chapter 18 of Artificial Intelligence: A Modern Approach; by Stuart Russell and Peter Norvig.
A decision tree is the shortest amount of questions needed to establish wether an object belongs to some set. For example: this object is red, round, and smells sour; is it edible? The algorithm generates such a tree from a number of examples (objects of which you know if they belong to the set or not).

• The decision tree learning algorithm.
• The possibility to give names to all attributes and attribute values, so the decision tree may be printed.

• Functionality to prevent noise and overfitting.

• If an agent wants to use this algorithm to learn which objects belong to a set and which do not, it will have to run the algorithm over all examples each time one is added. Also, all examples need to be stored for later use. This may be tedious and time consuming if there are a lot of attributes or examples. There are also algorithms that dynamically modify the decision tree. I don't know anything about these yet.
• The decision tree is too strict to my taste. It always gives a yes or no answer, even if the examples contradict each other, or there is insufficient data to make a decision. It would be better if a decision tree could also say "probably", "probably not" or "I don't know".
• The book AIMA contains an error in figure 18.8: "Hungry" branches in "No" and "Yes"; these words should be switched.

I've left parts of the code out here, to make it more readable.

CDTModel DecisionTreeModel(ATTRIBUTE_COUNT);
CDTDecisionTree *DecisionTree;

.... more variables ....

// first add the attributes
Attribute = new CDTAttribute("Is there an alternative restaurant nearby?");
Attribute->AddValue(YES, "Yes");
Attribute->AddValue(NO, "No");
DecisionTreeModel.SetAttribute(0, Attribute);

Attribute = new CDTAttribute("Does the restaurant have a comfortable bar?");
Attribute->AddValue(YES, "Yes");
Attribute->AddValue(NO, "No");
DecisionTreeModel.SetAttribute(1, Attribute);

.... more attributes ...

// fill the model with examples
for (int Index=0; Index < EXAMPLE_COUNT; Index++)
{
	// create object from attribute values
	Object = CreateObject(ObjectValues[Index]);

	// let model manage object
	DecisionTreeModel.AddObject(Object);

	// add example to decision tree
	DecisionTreeModel.AddExample(Object, WillWait[Index]);
}

// create sample object
SampleObject = CreateObject(SampleObjectValues);

// learn the decision tree
DecisionTree = DecisionTreeModel.CreateDecisionTree();

// ask the decision tree to decide if we should wait in a certain situation
DecisionValue = DecisionTree->MakeDecision(*SampleObject);

// print the decision tree
printf("%s\n", DecisionTree->ToString().GetBuffer());

// remove data
delete DecisionTree;
delete SampleObject;
                

• Decision Trees - basic definitions A document on the Information measure.