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.5.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 MethodIsEqual
Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices.
(Defined by Matrix.)
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

This example shows the simplest way to induce a decision tree with discrete variables.

// In this example, we will learn a decision tree directly from integer
// matrices that define the inputs and outputs of our learning problem.

int[][] inputs =
{
    new int[] { 0, 0 },
    new int[] { 0, 1 },
    new int[] { 1, 0 },
    new int[] { 1, 1 },
};

int[] outputs = // xor between inputs[0] and inputs[1]
{
    0, 1, 1, 0
};

// Create an ID3 learning algorithm
ID3Learning teacher = new ID3Learning();

// Learn a decision tree for the XOR problem
var tree = teacher.Learn(inputs, outputs);

// Compute the error in the learning
double error = new ZeroOneLoss(outputs).Loss(tree.Decide(inputs));

// The tree can now be queried for new examples:
int[] predicted = tree.Decide(inputs); // should be { 0, 1, 1, 0 }

This example shows a common textbook example, and how to induce a decision tree using a codebook to convert string (text) variables into discrete symbols.

// 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:

// Note: this example uses DataTables to represent the inputdata , but this is not required.
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 <see cref="Accord.Statistics.Filters.Codification">codebook</see>.</para>

// 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:</para>

// Create a new codification codebook to 
// convert strings into integer symbols
var codebook = new Codification(data);

// 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) 
};

// Note: It is also possible to create a DecisionVariable[] from a codebook:
// DecisionVariable[] attributes = DecisionVariable.FromCodebook(codebook);

// For this task, in which we have only categorical variables, the simplest choice 
// to induce a decision tree is to use the ID3 algorithm by Quinlan. Let’s do it:

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

// Learn the training instances!
DecisionTree tree = id3learning.Learn(inputs, outputs);

// Compute the training error when predicting training instances
double error = new ZeroOneLoss(outputs).Loss(tree.Decide(inputs));

// The tree can now be queried for new examples through 
// its decide method. For example, we can create a query

int[] query = codebook.Transform(new [,]
{
    { "Outlook",     "Sunny"  },
    { "Temperature", "Hot"    },
    { "Humidity",    "High"   },
    { "Wind",        "Strong" }
});

// And then predict the label using
int predicted = tree.Decide(query);  // result will be 0

// We can translate it back to strings using
string answer = codebook.Revert("PlayTennis", predicted); // Answer will be: "No"
See Also