Quinlan uses the notion of expected information from communication theory. (also called entropy and uncertainty (not to be confused with certainty factors))

In communication theory, expected information is a number describing a set of messages, M = {m₁,m₂, ..., m_n}.

Each message m_i in the set has probability p(m_i) and contains an amount of information, I(m_i), defined as

I(m_i) = -log₂ p(m_i)

Thus information is an inverse monotonic function of probability.

The expected information or entropy of a message set U(M), is the sum of the information in the several possible messages multiplied by their probabilities:

U(M) = - _i p(m_i) log₂ p(m_i)        for i = 1 to n

Note: Such a formula gives you a high number when a test produces highly inhomogeneous sets and a low number when a test produces completely homogeneous sets.

Quinlan's assumptions:

• A correct decision tree for C will classify objects in the same proportion as their representation in C. Suppose that p denotes the number of objects of class P in C and n denotes the number of objects of class N in C. Thus an unseen object will belong to class P with probability p/(p +n) and to class N with probability n/(p +n).

• Given an object to classify, a decision tree can be regarded as the source of a message, P or N. The entropy associated with the message set M = {P,N} is given by

  U(M) = -p/(p + n)*log₂ p/(p+n) - n/(p + n)*log₂ n/(p+n)

Suppose you had a set that contains members of just two classes, class A and class B. If the number of members from class A and the number of members of class B are perfectly balanced, the measured disorder is 1, the maximum possible value:

-1/2log₂1/2 - 1/2log₂1/2 = 1/2 + 1/2 = 1

On the other hand, if there were only all A's or all B's, the measured disorder is 0, the minimum possible value:

-1 log₂1 -0 log₂0 = -0 - 0 = 0

As you move from perfect balance and perfect homogeneity, disorder varies smoothly between 0 and 1. The disorder is 0 when the set is perfectly homogeneous, and the disorder is 1 when the set is perfectly inhomogeneous.

We want to minimize average disorder.

It is convenient to write this 'two-message' (P (+) and N (-)) case of entropy as a function of the two arguments:

EI(p,n) = -p/(p + n)*log₂ p/(p+n) - n/(p + n)*log₂ n/(p+n)

Given a test T with outcomes A₁, A₂, ... A_n producing a partition {C₁, C₂, ... C_n} as before, suppose C_i that contains pi objects of class P and ni objects of class N . The entropy of the subtree is given by EI(p_i,n_i). The entropy of the larger tree with T at its root is then given by the weighted average:

E(T) = _i [(p_i + n_i) / (p + n)] * EI(p_i ,n_i)     for i=1 to n

The ratio (p_i + n_i)/ (p + n) corresponds to the weight for the ith branch in a tree. It represents the proportion of the objects in C that belong to C_i.

Heuristic: In deciding what attribute to branch on next, ID3 uses select the test that gains the most information.

The information gained by carrying out a test is given by

EI(p,n) - E(T)

Such heuristics are sometimes described as 'minimum entropy' because maximizing information gain corresponds to minimizing uncertainity or disorder.

Example: [Quinlan,1983]

Consider collection C [height,hair,eyes] below :

C = short,blond,blue: + short,dark,blue:- tall,blond,brown:- tall,dark,blue:- tall,red,blue:+ tall,blond,blue:+ tall,dark,brown:- short,blond,brown:-

Selecting the second attribute to form the root yields .

Subcollections of 'dark' and 'red' contain objects of only a single class, and so require no more work.

Choosing the third attribute forms
.

With class names

Consider a "bad" choice of the first attribute at the start:

Another example (of the calculation):

Consider the choice of the first attribute of the tree:

The collection C of objects contains 3 in class '+' and 5 in '-' so for the entropy of the message set

EI(p,n) = -3/8 log₂ 3/8 - 5/8 log₂ 5/8 = 0.954

Testing the first attribute gives the results (consider yourself...)

The entropy of the subtrees (or the information still needed for a rule for the "tall" and "short" branches)

Tall subtree
= -2/5 log₂ 2/5 - 3/5 log₂ 3/5 = 0.971

Short subtree
= -1/3 log₂ 1/3 - 2/3 log₂ 2/3 = 0.918

Thus the expected information content for this subtree

E(T) = _i [(p_i + n_i) / (p + n)] * EI(p_i ,n_i)          for i=1 to n

E(C, "height") = 5/8 * 0.971 + 3/8 * 0.918 = 0.951

The information gained by carrying out a test is given by

EI(p,n) - E(T)

0.954 - 0.951 = 0.003 (which is negligible)

The tree arising from testing the second attribute:
         notice the first two subtrees are homogenous - disorder EI(p,n) for each is 0. The third subtree is evenly distributed, EI(p,n) = 1

E(C, "hair") = 3/8 * 0 + 1/8 * 0 + 4/8 * 1 = 0.5

The information gained by carrying out a test is 0.954-0.5 = 0.454

In a similar way the information gained by 'eyes' comes to 0.347

So we have:

height - 0.003
hair - 0.5
eyes - 0.347

The most information is gained using hair.
We have maximized information gain by minimizing uncertainity or disorder.

Other example (data about suntan lotion needs):
The average disorder produced by the various tests when the complete sample set is used as the window:

Test          Disorder

Hair          0.5
Height       0.69
Weight      0.94
Lotion       0.61

Which test should be used first? Why?

Test            Disorder

Height          0.5
Weight         1
Lotion          0

Which test?

Note how this techniques also shows that some attributes are irrelevant.

Pluses:

• When the concept space is very large, decision tree learning algorithms run more quickly than version space

• The methods converge rapidly; typically only 4 iterations were required to find a correct decision tree.

• The process is not very sensitive to parameters such as the initial window size.

• The time to obtain a correct decision tree increases linearly with the difficulty of the problem.

  (Its computational complexity hinges on the cost of choosing the next test to branch on, which is itself a linear function of the product of the number of objects in the training set and the number of attributes used to describe them.)

• Typically we have no a priori reason to believe that a class-characterizing model can be expressed as a single combination of values for a subset of the attributes.

• Nor does one have reason to believe the samples are noise free. (both of these needed for version spaces)

• Disjunction is more straight-forward

  Drawbacks:

• Large complex decision trees can be difficult for humans to understand. Thus the system may have a hard time explaining the reasons for its classification.

  (This is common for numerical approaches; they are efficient and resistant to noise, but they yield rules or concepts which are in general incomprehensible to humans.)

• The method is not incremental. One cannot consider additional training data without reconsidering the classification of previous instances.

• ID3 is not guaranteed to find the simplest decision tree because the information-theoretic evaluation function for choosing attributes is only a heuristic.

  (satisfice vs. optimize)

  It is computationally impractical to find the smallest possible identification tree when many tests are required, so one must be content with a procedure that tends to build small trees, albeit trees that are not guaranteed to be the smallest.

  General Points:

• ID3 takes a numerical approach in that it optimizes the global parameter of entropy.

• Its aim is to show a set of descriptors which are the 'best' relative to this optimization.

• It also has as a consequence, the generation of 'clusters' of examples.

-- Attributes with numeric values