Learning decision trees using id3 - artificial intelligence, Computer Engineering

Learning Decision Trees Using ID3

Specifying the Problem

We now have to look at how you mentally created your decision tree when deciding what to do at the weekend. One way would be to use some background information as axioms and assume what to do. For example, you could know that your parents actually like going to the cinema, and that your parents are in town, so therefore (using something  like Modus Ponens)  you would choose to go to the cinema.

Other way in which you could have made up your mind was by generalizing from last experiences. suppose  that you remembered all the times when you had a really great weekend. A few weeks before, it was sunny and your parents were not tripping, you played tennis and it was good.  Before a month, it was raining outside and you were  cleaned out,  but  a  trip  to  the  cinema  cheered  you  up.  And  so on.  This information must have guided your decision making, and if that was the case, you might have used an inductive, rather than deductive, procedure to create your

decision tree. actually, it's like human reasons to solve decisions using both inductive and deductive methods. We may state the problem of  learning decision trees as given below:

We have a group of examples exactly categorized into categories (decisions). We also have a set of features defining the examples, and every feature has a fixed set of data which it may possibly have. We need to use the examples to learn the arrangement of a decision tree which may be used to choose the category of an unseen example.

supposing that there are no inconsistencies in the data (when two examples have just similar values for the features, but are categorized dissimilarly), it  is obvious that we may always make a decision tree to exactly decide for the training cases with 100% correctness. All we need to do is make sure each condition is catered for down some branch of the decision tree. Definitely, 100% accuracy may point to over fitting.

The basic idea

In the decision tree given on top, it is major that the "parents visiting" node came at the top of the tree. We don't know accurately the reason for this, as we didn't see the example weekends from which the tree was constructed. However, it is likely that the number of weekends the parents tripped was relatively more, and each weekend they visited, there was a trip to the cinema. Assume, for example, the parents have tripped each fortnight for a year, and on every event the  family went to cinema. This means that there is no proof in favor of doing anything other than watching a movie when the parents come. Given that we are learning laws from examples, this means that if the parents come, the decision is already done. Hence we may keep this at the top of the decision tree, and disregard all the examples where the parents tripped when creating the rest of the tree. Need not to worry about a group of examples will do the construction job more easy.

This sort  of thinking  underlies the ID3 algorithm for  learning  decisions trees, which we will define more formally below. However, the reasoning is a little more delicate, as (in our example) it would also take into account the examples when the parents did not visit.


Keeping together a decision tree is all a matter of deciding which feature to check at every node in the tree. We shall describe a measure known as information gain which will be used to choose which feature to check at every node. Information gain is itself deliberate using a measure known as entropy, which we first define for the case of a binary decision problem and then define for the common case.

Given a binary categorization, C, and a group of examples, S, for which the proportion of examples categorized as positive by C is p+  and the proportion of examples categorized as negative by C is p-, then the entropy of S is:

2357_learing using dision tyree.png

The reason we described entropy first for a binary decision problem is because it is more easy to have an impression of what it is trying to measure. Tom Mitchell keeps this quite good:

"In order to describe information gain shortly, we start by describing a measure generally used in information theory, known as entropy that characterizes the impurity of an arbitrary group of examples."

Suppose having a group of boxes with some balls in. If all the balls were in a single box, then this should be well ordered, and it would be very easy to search a particular ball. If, however, the balls were distributed amongst the boxes, this would not be well ordered, and it should have quite a while to search a particular ball. If we were going to describe a measure based on this notion of purity, we would need to be able to calculate a value for every box based on the number of balls in that, then have the sum of these as the complete measure.  We would  need  to  reward two conditions: closely blank boxes (very clear), and boxes with closely all the balls in (also very clear). This is the basis for the common entropy measure, which is described as follows:

1636_learing using dision tyree1.png

Given an random categorization, C into categories c1, ..., cn, and a set of examples, S, for which the amount of examples in ci is pi, then the entropy of S is:

This measure assures our criteria, because of the -p*log2(p) production: when p gets near to zero (i.e., the category has just  a few examples in it), then the log(p) becomes a wide negative number, but the p part leads the calculation, so the entropy works out to  be closely zero.  Remembering that  entropy calculates the confusion in the data sequence, this low score is good, as it reflects our wish to reward

categories with some examples in. And the same, if p gets near to 1 (i.e., the category has major of the examples in), then the log(p) part gets very near to zero, and it is this which dominates the calculation, so the overall value gets close to zero. Hence we notice that both when the category is closely or completely blank, or when the category closely includes or completely contains  all the examples, the score for the category would be close to zero, which models what we needed it to. Notice that 0*ln(0) is taken to be zero by convention.

Posted Date: 10/3/2012 1:11:40 AM | Location : United States

Related Discussions:- Learning decision trees using id3 - artificial intelligence, Assignment Help, Ask Question on Learning decision trees using id3 - artificial intelligence, Get Answer, Expert's Help, Learning decision trees using id3 - artificial intelligence Discussions

Write discussion on Learning decision trees using id3 - artificial intelligence
Your posts are moderated
Related Questions
Artificial Life - artificial intelligence: Give birth to new exits forms.  A swot of Artificial Life will certainly direct on what it means for a complex system to be 'aliv

write alp to perform bcd addition without using procedure

Types of Structure Charts Transaction structure - control module calls subordinate modules, each of which handles a certain transaction More afferent processes Le

Q.  Develop a Menu driven program with following menu: 1.  Gray code 2.  BCD 3.  Excess-3 code 4.  Exit I/P must be a valid Binary number. Fractional numbers are all

One way of demonstrating the importance of good ID is by showing tangible benefits that can be talked about in cash terms. Within a business, good ID can lead to benefits such as h

Multiple Layers of Intranet Security Security requirements vary from organisation to organisation. They also vary on the content that the organisations intend to place on their

A Queue is a FIFO ( rst in, rst out) data structure. Given the following queue interface: public interface Queue { int size(); // current queue size boolean isEmpty(); //

Does the minimum spanning tree of a graph give the shortest distance between any 2 specified nodes? No. The Minimal spanning tree makes sure that the total weight of the tree i

Hazards of pipeline - computer architecture: Hazards : When a programmer (or compiler) writes assembly program code, they make the supposition that each instruction is execut