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.LearningDecisionTreeLearningBase
      Accord.MachineLearning.DecisionTrees.LearningID3Learning

Namespace:  Accord.MachineLearning.DecisionTrees.Learning
Assembly:  Accord.MachineLearning (in Accord.MachineLearning.dll) Version: 3.7.0
Syntax
[SerializableAttribute]
public class ID3Learning : DecisionTreeLearningBase, 
	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.
(Inherited from DecisionTreeLearningBase.)
Protected propertyAttributeUsageCount
Gets how many times each attribute has already been used in the current path. In the original C4.5 and ID3 algorithms, attributes could be re-used only once, but in the framework implementation this behaviour can be adjusted by setting the Join property.
(Inherited from DecisionTreeLearningBase.)
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). If set to zero, a single variable can participate as many times as needed. Default is 1.
(Inherited from DecisionTreeLearningBase.)
Public propertyMaxHeight
Gets or sets the maximum allowed height when learning a tree. If set to zero, the tree can have an arbitrary length. Default is 0.
(Inherited from DecisionTreeLearningBase.)
Public propertyModel
Gets or sets the decision trees being learned.
(Inherited from DecisionTreeLearningBase.)
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 methodAdd
Adds the specified variable to the list of Attributes.
(Inherited from DecisionTreeLearningBase.)
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 methodGetEnumerator
Returns an enumerator that iterates through the collection.
(Inherited from DecisionTreeLearningBase.)
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 MethodToT
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.)
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 input data , 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");

// 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 teacher ID3 algorithm
var id3learning = new ID3Learning()
{
    // 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:

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

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