Click or drag to resize
Accord.NET (logo) ID3Learning Class
ID3 (Iterative Dichotomizer 3) learning algorithm for Decision Trees.
Inheritance Hierarchy
SystemObject
  Accord.MachineLearningParallelLearningBase
    Accord.MachineLearning.DecisionTrees.LearningID3Learning

Namespace:  Accord.MachineLearning.DecisionTrees.Learning
Assembly:  Accord.MachineLearning (in Accord.MachineLearning.dll) Version: 3.4.0
Syntax
[SerializableAttribute]
public class ID3Learning : ParallelLearningBase, 
	ISupervisedLearning<DecisionTree, int[], int>
Request Example View Source

The ID3Learning type exposes the following members.

Constructors
Properties
  NameDescription
Public propertyAttributes
Gets or sets the collection of attributes to be processed by the induced decision tree.
Public propertyJoin
Gets or sets how many times one single variable can be integrated into the decision process. In the original ID3 algorithm, a variable can join only one time per decision path (path from the root to a leaf).
Public propertyMaxHeight
Gets or sets the maximum allowed height when learning a tree. If set to zero, no limit will be applied. Default is zero.
Public propertyModel
Gets or sets the decision trees being learned.
Public propertyParallelOptions
Gets or sets the parallelization options for this algorithm.
(Inherited from ParallelLearningBase.)
Public propertyRejection
Gets or sets whether all nodes are obligated to provide a true decision value. If set to false, some leaf nodes may contain null. Default is false.
Public propertyToken
Gets or sets a cancellation token that can be used to cancel the algorithm while it is running.
(Inherited from ParallelLearningBase.)
Top
Methods
  NameDescription
Public methodComputeError Obsolete.
Computes the prediction error for the tree over a given set of input and outputs.
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodLearn
Learns a model that can map the given inputs to the given outputs.
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodRun Obsolete.
Runs the learning algorithm, creating a decision tree modeling the given inputs and outputs.
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Extension Methods
  NameDescription
Public Extension MethodHasMethod
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by Matrix.)
Top
Remarks

References:

Examples

In this example, we will be using the famous Play Tennis example by Tom Mitchell (1998). In Mitchell's example, one would like to infer if a person would play tennis or not based solely on four input variables. Those variables are all categorical, meaning that there is no order between the possible values for the variable (i.e. there is no order relationship between Sunny and Rain, one is not bigger nor smaller than the other, but are just distinct). Moreover, the rows, or instances presented above represent days on which the behavior of the person has been registered and annotated, pretty much building our set of observation instances for learning:

DataTable data = new DataTable("Mitchell's Tennis Example");

data.Columns.Add("Day", "Outlook", "Temperature", "Humidity", "Wind", "PlayTennis");

data.Rows.Add(   "D1",   "Sunny",      "Hot",       "High",   "Weak",    "No"  );
data.Rows.Add(   "D2",   "Sunny",      "Hot",       "High",  "Strong",   "No"  ); 
data.Rows.Add(   "D3",  "Overcast",    "Hot",       "High",   "Weak",    "Yes" );
data.Rows.Add(   "D4",   "Rain",       "Mild",      "High",   "Weak",    "Yes" ); 
data.Rows.Add(   "D5",   "Rain",       "Cool",     "Normal",  "Weak",    "Yes" ); 
data.Rows.Add(   "D6",   "Rain",       "Cool",     "Normal", "Strong",   "No"  ); 
data.Rows.Add(   "D7",  "Overcast",    "Cool",     "Normal", "Strong",   "Yes" );
data.Rows.Add(   "D8",   "Sunny",      "Mild",      "High",   "Weak",    "No"  );  
data.Rows.Add(   "D9",   "Sunny",      "Cool",     "Normal",  "Weak",    "Yes" ); 
data.Rows.Add(   "D10", "Rain",        "Mild",     "Normal",  "Weak",    "Yes" ); 
data.Rows.Add(   "D11",  "Sunny",      "Mild",     "Normal", "Strong",   "Yes" );
data.Rows.Add(   "D12", "Overcast",    "Mild",      "High",  "Strong",   "Yes" ); 
data.Rows.Add(   "D13", "Overcast",    "Hot",      "Normal",  "Weak",    "Yes" ); 
data.Rows.Add(   "D14",  "Rain",       "Mild",      "High",  "Strong",   "No"  );

In order to try to learn a decision tree, we will first convert this problem to a more simpler representation. Since all variables are categories, it does not matter if they are represented as strings, or numbers, since both are just symbols for the event they represent. Since numbers are more easily representable than text string, we will convert the problem to use a discrete alphabet through the use of a codebook.

A codebook effectively transforms any distinct possible value for a variable into an integer symbol. For example, “Sunny” could as well be represented by the integer label 0, “Overcast” by “1”, Rain by “2”, and the same goes by for the other variables. So:

// Create a new codification codebook to 
// convert strings into integer symbols
Codification codebook = new Codification(data,
  "Outlook", "Temperature", "Humidity", "Wind", "PlayTennis");

// Translate our training data into integer symbols using our codebook:
DataTable symbols = codebook.Apply(data); 
int[][] inputs  = symbols.ToArray<int>("Outlook", "Temperature", "Humidity", "Wind"); 
int[]   outputs = symbols.ToArray<int>("PlayTennis");

Now that we already have our learning input/ouput pairs, we should specify our decision tree. We will be trying to build a tree to predict the last column, entitled “PlayTennis”. For this, we will be using the “Outlook”, “Temperature”, “Humidity” and “Wind” as predictors (variables which will we will use for our decision). Since those are categorical, we must specify, at the moment of creation of our tree, the characteristics of each of those variables. So:

// Gather information about decision variables
DecisionVariable[] attributes =
{
  new DecisionVariable("Outlook",     3), // 3 possible values (Sunny, overcast, rain)
  new DecisionVariable("Temperature", 3), // 3 possible values (Hot, mild, cool)  
  new DecisionVariable("Humidity",    2), // 2 possible values (High, normal)    
  new DecisionVariable("Wind",        2)  // 2 possible values (Weak, strong) 
};

int classCount = 2; // 2 possible output values for playing tennis: yes or no

//Create the decision tree using the attributes and classes
DecisionTree tree = new DecisionTree(attributes, classCount);

Now we have created our decision tree. Unfortunately, it is not really very useful, since we haven't taught it the problem we are trying to predict. So now we must instantiate a learning algorithm to make it useful. For this task, in which we have only categorical variables, the simplest choice is to use the ID3 algorithm by Quinlan. Let’s do it:

// Create a new instance of the ID3 algorithm
ID3Learning id3learning = new ID3Learning(tree);

// Learn the training instances!
id3learning.Run(inputs, outputs);

The tree can now be queried for new examples through its Compute(Double) method. For example, we can use:

string answer = codebook.Translate("PlayTennis",
  tree.Compute(codebook.Translate("Sunny", "Hot", "High", "Strong")));

In the above example, answer will be "No".

See Also