Question

Below is a example of a ID3 algorithm in Unity using C# im not sure how the ID3Example works in the whole thing can someone explain the whole thing in more detail please. i am trying to use it with this data set a txt file

Alternates?:Bar?:Friday?:Hungry?:#Patrons:Price:Raining?:Reservations?:Type:EstWaitTime:WillWait?
Yes:No:No:Yes:Some:$$$:No:Yes:French:0-10:True
Yes:No:No:Yes:Full:$:No:No:Thai:30-60:False
No:Yes:No:No:Some:$:No:No:Burger:0-10:True
Yes:No:Yes:Yes:Full:$:Yes:No:Thai:10-30:True
Yes:No:Yes:No:Full:$$$:No:Yes:French:>60:False
No:Yes:No:Yes:Some:$$:Yes:Yes:Italian:0-10:True
No:Yes:No:No:None:$:Yes:No:Burger:0-10:False
No:No:No:Yes:Some:$$:Yes:Yes:Thai:0-10:True
No:Yes:Yes:No:Full:$:Yes:No:Burger:>60:False
Yes:Yes:Yes:Yes:Full:$$$:No:Yes:Italian:10-30:False
No:No:No:No:None:$:No:No:Thai:0-10:False
Yes:Yes:Yes:Yes:Full:$:No:No:Burger:30-60:True

Learning to use decision trees

We already learned the power and flexibility of decision trees for adding a decision-making component to our game. Furthermore, we can also build them dynamically through supervised learning. That's why we're revisiting them in this chapter.

There are several algorithms for building decision trees that are suited for different uses such as prediction and classification. In our case, we'll explore decision-tree learning by implementing the ID3 algorithm.

Getting ready…

Despite having built decision trees in a previous chapter, and the fact that they're based on the same principles as the ones that we will implement now, we will use different data types for our implementation needs in spite of the learning algorithm.

We will need two data types: one for the decision nodes and one for storing the examples to be learned.

The code for the DecisionNode data type is as follows:

Copy

using System.Collections.Generic;

public class DecisionNode
{
    public string testValue;
    public Dictionary<float, DecisionNode> children;

    public DecisionNode(string testValue = "")
    {
        this.testValue = testValue;
        children = new Dictionary<float, DecisionNode>();
    }
}

The code for the Example data type is as follows:

Copy

using UnityEngine;
using System.Collections.Generic;

public enum ID3Action
{
    STOP, WALK, RUN
}

public class ID3Example : MonoBehaviour
{
    public ID3Action action;
    public Dictionary<string, float> values;
    
    public float GetValue(string attribute)
    {
        return values[attribute];
    }
}

How to do it…

We will create the ID3 class with several functions for computing the resulting decision tree.

Create the ID3 class:

Copy

using UnityEngine;
using System.Collections.Generic;
public class ID3 : MonoBehaviour
{
    // next steps
}

Start the implementation of the function responsible for splitting the attributes into sets:

Copy

public Dictionary<float, List<ID3Example>> SplitByAttribute(
        ID3Example[] examples,
        string attribute)
{
    Dictionary<float, List<ID3Example>> sets;
    sets = new Dictionary<float, List<ID3Example>>();
    // next step
}

Iterate though all the examples received, and extract their value in order to assign them to a set:

Copy

foreach (ID3Example e in examples)
{
    float key = e.GetValue(attribute);
    if (!sets.ContainsKey(key))
        sets.Add(key, new List<ID3Example>());
    sets[key].Add(e);
}
return sets;

Create the function for computing the entropy for a set of examples:

Copy

public float GetEntropy(ID3Example[] examples)
{
    if (examples.Length == 0) return 0f;
    int numExamples = examples.Length;
    Dictionary<ID3Action, int> actionTallies;
    actionTallies = new Dictionary<ID3Action, int>();
    // next steps
}

Iterate through all of the examples to compute their action quota:

Copy

foreach (ID3Example e in examples)
{
    if (!actionTallies.ContainsKey(e.action))
        actionTallies.Add(e.action, 0);
    actionTallies[e.action]++;
}

Compute the entropy :

Copy

int actionCount = actionTallies.Keys.Count;
if (actionCount == 0) return 0f;
float entropy = 0f;
float proportion = 0f;
foreach (int tally in actionTallies.Values)
{
    proportion = tally / (float)numExamples;
    entropy -= proportion * Mathf.Log(proportion, 2);
}
return entropy;

Implement the function for computing the entropy for all the sets of examples. This is very similar to the preceding one; in fact, it uses it:

Copy

public float GetEntropy(
        Dictionary<float, List<ID3Example>> sets,
        int numExamples)
{
    float entropy = 0f;
    foreach (List<ID3Example> s in sets.Values)
    {
        float proportion;
        proportion = s.Count / (float)numExamples;
        entropy -= proportion * GetEntropy(s.ToArray());
    }
    return entropy;
}

Define the function for building a decision tree:

Copy

public void MakeTree(
        ID3Example[] examples,
        List<string> attributes,
        DecisionNode node)
{
    float initEntropy = GetEntropy(examples);
    if (initEntropy <= 0) return;
    // next steps
}

Declare and initialize all the required members for the task:

Copy

int numExamples = examples.Length;
float bestInfoGain = 0f;
string bestSplitAttribute = "";
float infoGain = 0f;
float overallEntropy = 0f;
Dictionary<float, List<ID3Example>> bestSets;
bestSets = new Dictionary<float, List<ID3Example>>();
Dictionary<float, List<ID3Example>> sets;

Iterate through all the attributes in order to get the best set based on the information gain:

Copy

foreach (string a in attributes)
{
    sets = SplitByAttribute(examples, a);
    overallEntropy = GetEntropy(sets, numExamples);
    infoGain = initEntropy - overallEntropy;
    if (infoGain > bestInfoGain)
    {
        bestInfoGain = infoGain;
        bestSplitAttribute = a;
        bestSets = sets;
    }
}

Select the root node based on the best split attribute, and rearrange the remaining attributes for building the rest of the tree:

Copy

node.testValue = bestSplitAttribute;
List<string> newAttributes = new List<string>(attributes);
newAttributes.Remove(bestSplitAttribute);

Iterate through all the remaining attributes. calling the function recursively:

Copy

foreach (List<ID3Example> set in bestSets.Values)
{
    float val = set[0].GetValue(bestSplitAttribute);
    DecisionNode child = new DecisionNode();
    node.children.Add(val, child);
    MakeTree(set.ToArray(), newAttributes, child);
}

How it works…

The class is modular in terms of functionality. It doesn't store any information but is able to compute and retrieve everything needed for the function that builds the decision tree. SplitByAttribute takes the examples and divides them into sets that are needed for computing their entropy. ComputeEntropy is an overloaded function that computes a list of examples and all the sets of examples using the formulae defined in the ID3 algorithm. Finally, MakeTree works recursively in order to build the decision tree, getting hold of the most significant attribute.

Answer 1

Abstract

This paper details the ID3 classification algorithm. Very simply, ID3 builds a decision tree from a fixed set of examples. The resulting tree is used to classify future samples. The example has several attributes and belongs to a class (like yes or no). The leaf nodes of the decision tree contain the class name whereas a non-leaf node is a decision node. The decision node is an attribute test with each branch (to another decision tree) being a possible value of the attribute. ID3 uses information gain to help it decide which attribute goes into a decision node. The advantage of learning a decision tree is that a program, rather than a knowledge engineer, elicits knowledge from an expert.

Introduction

J. Ross Quinlan originally developed ID3 at the University of Sydney. He first presented ID3 in 1975 in a book, Machine Learning, vol. 1, no. 1. ID3 is based off the Concept Learning System (CLS) algorithm. The basic CLS algorithm over a set of training instances C:

Step 1: If all instances in C are positive, then create YES node and halt.

If all instances in C are negative, create a NO node and halt.

Otherwise select a feature, F with values v1, ..., vn and create a decision node.

Step 2: Partition the training instances in C into subsets C1, C2, ..., Cn according to the values of V.

Step 3: apply the algorithm recursively to each of the sets Ci.

Note, the trainer (the expert) decides which feature to select.

ID3 improves on CLS by adding a feature selection heuristic. ID3 searches through the attributes of the training instances and extracts the attribute that best separates the given examples. If the attribute perfectly classifies the training sets then ID3 stops; otherwise it recursively operates on the n (where n = number of possible values of an attribute) partitioned subsets to get their "best" attribute. The algorithm uses a greedy search, that is, it picks the best attribute and never looks back to reconsider earlier choices.

Discussion

ID3 is a nonincremental algorithm, meaning it derives its classes from a fixed set of training instances. An incremental algorithm revises the current concept definition, if necessary, with a new sample. The classes created by ID3 are inductive, that is, given a small set of training instances, the specific classes created by ID3 are expected to work for all future instances. The distribution of the unknowns must be the same as the test cases. Induction classes cannot be proven to work in every case since they may classify an infinite number of instances. Note that ID3 (or any inductive algorithm) may misclassify data.

Data Description

The sample data used by ID3 has certain requirements, which are:

• Attribute-value description - the same attributes must describe each example and have a fixed number of values.

• Predefined classes - an example's attributes must already be defined, that is, they are not learned by ID3.

• Discrete classes - classes must be sharply delineated. Continuous classes broken up into vague categories such as a metal being "hard, quite hard, flexible, soft, quite soft" are suspect.

• Sufficient examples - since inductive generalization is used (i.e. not provable) there must be enough test cases to distinguish valid patterns from chance occurrences.

Attribute Selection

How does ID3 decide which attribute is the best? A statistical property, called information gain, is used. Gain measures how well a given attribute separates training examples into targeted classes. The one with the highest information (information being the most useful for classification) is selected. In order to define gain, we first borrow an idea from information theory called entropy. Entropy measures the amount of information in an attribute.

Given a collection S of c outcomes

Entropy(S) = S -p(I) log2 p(I)

where p(I) is the proportion of S belonging to class I. S is over c. Log2 is log base 2.

Note that S is not an attribute but the entire sample set.

Example 1

If S is a collection of 14 examples with 9 YES and 5 NO examples then

Entropy(S) = - (9/14) Log2 (9/14) - (5/14) Log2 (5/14) = 0.940

Notice entropy is 0 if all members of S belong to the same class (the data is perfectly classified). The range of entropy is 0 ("perfectly classified") to 1 ("totally random").

Gain(S, A) is information gain of example set S on attribute A is defined as

Gain(S, A) = Entropy(S) - S ((|S_v| / |S|) * Entropy(S_v))

Where:

S is each value v of all possible values of attribute A

S_v = subset of S for which attribute A has value v

|S_v| = number of elements in S_v

|S| = number of elements in S

Example 2

Suppose S is a set of 14 examples in which one of the attributes is wind speed. The values of Wind can be Weak or Strong. The classification of these 14 examples are 9 YES and 5 NO. For attribute Wind, suppose there are 8 occurrences of Wind = Weak and 6 occurrences of Wind = Strong. For Wind = Weak, 6 of the examples are YES and 2 are NO. For Wind = Strong, 3 are YES and 3 are NO. Therefore

Gain(S,Wind)=Entropy(S)-(8/14)*Entropy(S_weak)-(6/14)*Entropy(S_strong)

= 0.940 - (8/14)*0.811 - (6/14)*1.00

= 0.048

Entropy(S_weak) = - (6/8)*log2(6/8) - (2/8)*log2(2/8) = 0.811

Entropy(S_strong) = - (3/6)*log2(3/6) - (3/6)*log2(3/6) = 1.00

For each attribute, the gain is calculated and the highest gain is used in the decision node.

Example of ID3

Suppose we want ID3 to decide whether the weather is amenable to playing baseball. Over the course of 2 weeks, data is collected to help ID3 build a decision tree (see table 1).

The target classification is "should we play baseball?" which can be yes or no.

The weather attributes are outlook, temperature, humidity, and wind speed. They can have the following values:

outlook = { sunny, overcast, rain }

temperature = {hot, mild, cool }

humidity = { high, normal }

wind = {weak, strong }