 Open Access
 Total Downloads : 473
 Authors : Ms.Priti Phalak, Mr.Kiran Bhandari, Dr. Rekha Sharma
 Paper ID : IJERTV3IS030302
 Volume & Issue : Volume 03, Issue 03 (March 2014)
 Published (First Online): 14032014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Analysis of Decision TreeA Survey
Ms. Priti Phalak
Computer Engineering TCET
Mumbai, India.
Mr. Kiran Bhandari
Dy. HOD of Computer Engineering TCET,
Mumbai
Dr. Rekha Sharma
HOD of Computer Engineering TCET
Mumbai, India.
AbstractDecision tree is a fast and efficient classification prediction algorithm in data mining which is most widely used for decision making. It is one of the most popular datamining techniques for knowledge discovery. It systematically analyses the information contained in a large data source to extract valuable rules and relationships. It recursively partitions a data set of records using depthfirst greedy approach or breadthfirst approach, until all the data items belong to a particular class are identified. Decision trees are categorized as a supervised method that trying to find the relationship between input attributes and target attributes which represent the relationship in structure as a model. It first compare the attribute values of the object, and select optimal attribute as the root node, then depend on attribute to determine the leaf node of the tree branch from the root down.
Most decision tree classifiers perform classification in two phases: Treegrowing (or building) and Treepruning. The tree building is done in topdown manner. During this phase the tree is recursively partitioned till all the data items belong to the same class label. In the tree pruning phase the full grown tree is cut back to prevent over fitting and improve the accuracy of the tree in bottom up fashion. It is used to improve the prediction and classification accuracy of the algorithm by minimizing the over fitting. There are various techniques for pruning decision trees such as Cost Complexity Pruning, Reduced Error Pruning, Pessimistic Pruning, Minimum Error Pruning, ErrorBased Pruning and for decision tree induction algorithms such as ID3, C4.5, CART.
Index Terms Decision Tree, Classification, Pruning, Pruning methods, Splitting Criteria.

INTRODUCTION
Decision tree is one of the most popular and efficient technique in data mining. This technique has been established and wellexplored by many researchers. A decision tree is a flowchartlike tree structure, where each internal node is denoted by rectangles, and leaf nodes are denoted by ovals. All internal nodes have two or more child nodes. All internal nodes contain splits, which test the value of an expression of the attributes. Arcs from an internal node to its children are labeled with distinct outcomes of the test. Each leaf node has a class label associated with it. Decision trees are a reliable and effective decision making technique that provide high classification accuracy with a simple representation of gathered knowledge. Classification is the process of categorization of data for its most effective and
efficient use. Decision tree algorithms have characteristics as follows:

Structure of the decision tree is simple and easy to understand.

Decision tree is more appropriate for the case of a large amount of training set.

Decision tree has high accuracy.
Classification is a supervised learning technique in data mining where training data is given to classifier that builds classification rules .Classification of data objects is a data mining and knowledge management technique used in grouping similar data objects together. There are many classification algorithms available in literature such as SVM, Naive Bayes, decision tree induction algorithm (ID3, C4.5 and CART) etc., but decision tree is the most commonly used because of its ease of execution and easier to understand compared to other classification algorithms. Classification of data is one of the important tasks in data mining. Decision tree is one of the most widely used technique, and is very popular among researchers because of their simplicity, intelligibility, ease of implementation, decision tree construction faster and produce better accuracy then other classification algorithms.
Decision tree can be represented by two types of structures: Tree structure (hierarchical structure) and Rules (if then statement). If decision tree is complicated, tree structure and rules might be wasted. Some decision tree algorithms may produce a large structure of tree size and it is difficult to understand. Further it leads to misclassification of data which often occurs in learning process. For such a complex tree, pruning procedures must be developed to facilitate the interpretation. Pruning methods have been introduced to reduce the complexity of tree structure without decreasing the accuracy of classification. Pruning is a method that reduces the size of the tree by removing parts of the tree that are not meaningful to avoid unnecessary complexity and to avoid overfitting of the dataset. Pruning decision trees is a fundamental step in optimizing the computational efficiency as well as classification accuracy of such a model. The complexity of tree is clearly controlled by the pruning methods.
The main objective of this seminar is to study topdown algorithmic framework for decision tree induction, decision tree construction process and pruning process, types of decision tree induction algorithm such as C4.5, ID3, CHAID,
QUEST and CART etc. along with various pruning methods (CostComplexity Pruning, Reduced Error Pruning, Minimum Error Pruning, Pessimistic Pruning, ErrorBased Pruning, Optimal Pruning, Minimum Description Length Pruning), also comparative study of decision tree induction algorithms such as C4.5, ID3 and CART etc. and to study the application of decision tree induction algorithm.
Seminar report is organized as Follows:
Section 1: Introduction of decision trees, motivation and objective of seminar report.
Section 2: Types of decision tree induction and different types of pruning methods.
Chapter 3: Comparative study of decision tree induction algorithms.
Chapter 4: Explain the application of decision tree algorithm. Chapter 5: Comparative analysis of decision tree induction algorithm and comparative analysis of pruning methods.
Chapter 6: Conclusion.


PRELIMINARIES
Technical terms and notations used in this paper are as follows:
Entropy:
Entropy is a measure of the number of random ways in which a system may be arranged. For a data set S containing n records the information entropy is defined as
Entropy S P1 log2 P1
(Here P1 is the proportion of S belonging to class 1.)
Gain
Gain or the expected information gain is the change in information entropy from a prior state to a state that takes some information. The information gain of example set S on attribute A is defined as
according to the attributes of the data. Categorical data are always nominal whereas nominal data need not be categorical. Nominal data means, a type of categorical data in which objects fall into unordered categories. For example, gender is a categorical variable having two categories (male and female). Generally, discrete data are counts.

Continuous attributes Has real numbers as attribute values Examples: temperature, height, or weight. Practically, real values can only be measured and represented using a finite number of digits. Continuous attributes are typically represented as floatingpoint variables. Generally, continuous data come from measurements.


TYPE OF DECISION TREE
A. ID3
Iterative Dichotomiser 3 is a simple decision tree learing algorithm introduced by Quinlan Ross. It is serially implemented and based on Hunts algorithm. The basic idea of ID3 algorithm is to construct the decision tree by employing a topdown, greedy search through the given sets to test each attribute at every tree node. It is a topdown approach starting with selecting the best attribute to test at the root of the tree. The selection of the best attribute in ID3 is based on an information theory approach or entropy. Entropy is a measure of the amount of uncertainty present in a set of data. When all data in a set belong to a single class, there is no uncertainty and hence, the entropy is zero. In general, the value of entropy falls between 0 and 1and reaches a maximum when the probabilities are all the same. ID3 does not apply any pruning procedure. It does not handle numeric attributes neither missing values. It does not give accurate result when there is noise. Thus an intensive preprocessing of data is carried out before building a
Gain S, A
Entropy s
Sv vvaluesA S
Entropy (Sv )
decision tree model with ID3. Given a set S, containing two examples (positive and negative) of target concept, the entropy of a set S relative to this binary classification is defined as:
where Value(A) is the set of all possible values of attribute A, Sv is the subset of S for which attribute A has value v,
Sv is the number of elements in Sv and
E S
P( positive)log2 P( positive)

P(negative)log2 P(negative )
 S  is the number of elements in S.
Gini index
Gini index for a data set S is defined as
Gini S 1 PI
and for a 2split
Where P(positive) and P(negative) are the fraction of positive and negative examples in S.
Information gain calculates the expected reduction in entropy. Gain (S, X) of an attribute X, relative to a collection of examples S is,
gini S n1 gini S n2 gini S
 Sv 
split n 1 n 2
Gain(S, X) E(S) E(Sv) (2)
Hunts algorithm
Hunts method algorithm for decision tree construction trains the data set with recursive partition using depth first greedy technique, till all the record data sets belong to the class label.
There are following types of attributes used in decision tree algorithm

Categorical attribute is also called as discrete or nominal attributes. In Categorical Data, a set of data is sorted or divided into different categories,

vvalues( x)  S 
where, values (X) = set of all possible values for attribute
X.
Sv = subset of S for which attribute X has value v (ie. Sv = {sS  X(s) = v})
E(S) = entropy of the original collection S.
ID3 select splitting attributes with the highest information gain. It can handle only nominal attributes. Modifications and
improvements on the ID3 algorithm culminated into the popular C4.5 algorithm.
Splitinfo A i log ( i )
2
v  S   S 
i1  S   S 
(6)

C4.5
C4.5 algorithm is an improved version of ID3, this algorithm uses Gain Ratio as a splitting criteria, instead of taking gain in ID3 algorithm for splitting criteria in tree growth phase. Hence C4.5 is an evolution of ID3. This algorithm handles both continuous and discrete attributes In order to handle continuous attributes, C4.5 creates a threshold and then splits the list into those whose attribute value is above the threshold and those that are less than or equal to it. Like ID3 the data is sorted at every node of the tree in order to determine the best splitting attribute. The splitting ceases when the number of instances to be split is below a certain threshold. The main advantages of C4.5 is when building a decision tree, C4.5 can deal with datasets that have patterns with unknown attribute values. C4.5 can also deal with the case of attributes with continuous domains by discretization. This algorithm handles training data with attribute values by allowing attribute values to be marked as missing. Missing attribute values are simply not used in gain and entropy calculations. It has an enhanced method of tree pruning that reduces misclassification errors due to noise or too much detail in the training data set
In general, when a decision tree is built, missing data are simply ignored. The gain ratio is calculated by looking only at the other records, which have a value for that attribute. In order to classify a record with a missing attribute value, the attribute values for the other records can be used to predict the same.
If S is the set of training data denoting a concept with c classes, f(Cj, S) is the frequency of class Cj occurring in that set, then the expected information required to classify a given
C4.5 selects the test to partition the set of available cases is defined as:
gainratio A gain( A)
Splitinfo( A)
C4.5 selects the test that maximizes gain ratio value. The difference between ID3 and C4.5 algorithm is that ID3 uses binary splits, whereas C4.5 algorithm uses multiway splits. In order to reduce the size of the decision tree, C4.5 uses post pruning technique; whereas an optimizer combines the generated rules to eliminate redundancies. The improved version of C4.5 is C5.0, which includes crossvalidation and boosting capabilities.

Classification and Regression Trees (CART)
CART is a nonparametric decision tree algorithm. It produces either classification or regression trees, based on whether the response variable is categorical or continuous. This methodology is a binary recursive partitioning procedure, which always split the node into only two nodes. The partitioning procedure is repeated for every node of the data until it becomes the terminal node. There are three important steps in CART. (i)Tree growing process: It is based on the recursive partitioning algorithm to select the variables using splitting criterion. In CART, gini criterion is used for determining the best split. Let i(T) denote the impurity at node(T), then i(T) must be zero when node(T) is pure and a maximum when the categories are equally represented. The gini impurity for node T is defined as:
class in S is:
c f Cj, S
f (Cj, S)
i T [1 P2 cj ]
j
(8)
S
Info S
j 1
log2 (
)
 S 
(3)
where, P (cj) is the fraction of rows in node T with class cj.
The reduction in impurity of node T is given by:
when an attribute, A, with v values, has been selected as a test attribute, then the expected information needed to identify a class under that test is:
i T i t PLi TL PRi(TR )
(9)
Info
S i info(S )
i

where, TL and TR – Left and Right child node of nodes,
i(TL) and i(TR) are their impurities, and PL and PR are
A
v  s 
i1 S
where S1, S2, . . ., Sv is the subset of S all of whose instances possess value i for attribute A.
The information gain is the difference between the expected information needed to identify a class with and without the test on attribute A:
i
v  S 
proportion of examples in the child node TL and TR.. Maximum reduction in impurity is chosen as the split point. The splitting process will continue until no further split is possible and the maximal tree is obtained. The process is stopped when there is only single case in each of the terminal nodes or all cases within each terminal node have the same distribution of predictor variables, making splitting impossible.
Gain(A) Info(S) i Info(S )
i1  S 
(ii) Tree pruning: There are several reasons involved, which may lead to overfit the data. When a tree is overfitted, it will
The attribute giving the maximum information gain is selected as the current split. ID3 used information gain criterion (Equation.6 to select the test for partition. However, the gain criterion is biased towards the high frequency data. To restructure this problem, C4.5 normalizes the information gain by the amount of the potential information generated by dividing T into v subsets:
lead to inaccuracy in estimating prediction errors, which can be overcome by pruning. The type of pruning differs depending upon the application type, i.e., whether the decision tree is used for classification or for prediction or clustering. The popular pruning techniques include costcomplexity pruning, reduced error pruning, pessimistic error pruning, minimum error pruning and minimum description length, bootstrapping etc.


Supervised Learning In Quest (SLIQ)
SLIQ stands for Supervised Learning In Quest, it was one of the first scalable algorithms for decision tree induction. This can be implemented in serial and parallel pattern. It is not based on Hunts algorithm for decision tree classification. It partitions a training data set recursively using breadthfirst greedy strategy that is integrated with presorting technique during the tree building phase. SLIQ uses a vertical data format, meaning all values of an attribute were stored as a list, which was sorted at the start of the algorithm. This means that the attributes need not be sorted repeatedly at each node as was the case in existing algorithms like CART and C4.5. With the presorting technique sorting at decision tree nodes is eliminated and replaced with onetime sort, with the use of list data structure for each attribute to determine the best split point.
Calculation of gini index for each possible split point can be done efficiently by storing class distributions in histograms, one per class per node. However SLIQ uses a memory resident data structure called class list which stores the class labels of each record. This data structure limits the size of the datasets SLIQ can handle. In building a decision tree model SLIQ handles both numeric and categorical attributes. One of the disadvantages of SLIQ is that it uses a class list data structure that is memory resident thereby imposing memory restrictions on the data. It uses Minimum Description length Principle in pruning the tree after constructing it. MDL is an inexpensive technique in tree pruning that uses the least amount of coding in producing tree that are small in size using bottom up technique.
SLIQ decision tree algorithm produces accurate decision trees that are significantly smaller than the trees produced using C4.5 and CART. At the same time, SLIQ executes nearly an order of magnitude faster than CART.

Scalable Parallelizable Induction of decision Tree algorithm (SPRINT)
SPRINT stands for scalable parallelizable induction of decision tree algorithm. It was introduced by Shafer et al in 1996. It presents a more memory efficient version of SLIQ. This algorithm associates the class label along with the record identifier for each value in the attribute lists. It is an enhancement of SLIQ as it can be implemented in both serial and parallel pattern for good data placement and load balancing. It is fast, scalable decision tree classifier. It is not based on Hunts algorithm in constructing the decision tree, rather it partitions the training data set recursively using breadthfirst greedy technique until each partition belong to the same leaf node or class. It can be implemented in both serial and parallel pattern for good data placement and load balancing.
It uses two data structure: attribute list and histogram which is not memory resident making sprint suitable for large data sets, thus it removes all the data memory restrictions on data. It handles both continuous and categorical attributes.


PRUNING METHODS
Pruning is a method that reduces the size of the tree by removing parts of the tree that are not meaningful to avoid unnecessary complexity and to avoid overfitting of the dataset. Pruning decision trees is a fundamental step in optimizing the computational efficiency as well as classification accuracy of such a model. Pruning is done after the complete creation of the tree. It aims to reduce classification errors caused by specialization in the training set. It makes the tree more general. There are various techniques for pruning decision trees
Algorithms
Measures
Attributes
Procedure
Pruning
ID3
Entropy infogain
Categor
ical
Topdown decision tree construction
Pre pruning using a single pass
algorithm
C4.5
Gain ratio
Continuous, Categorical, & Missing values
Top down decision tree
construction
Post pruning using a single pass
algorithm
CART
Gini diversity index
Numeric & Categorical
Constructs binary decision tree
Post pruning based on cost
complexity measure
SLIQ
Gini index
Numeric & Categorical
Decision tree construction
in a breadth first manner
Post pruning based on MDL
principle
SPRINT
Gini index
Continuous & Categorical
Decision tree construction in a breadth first manner
Post pruning based on MDL
principle
TABLE I. COMPARATIVE ANALYSIS OF DECISION TREE METHODS

Cost Complexity Pruning
Cost Complexity Pruning also known as weakest link pruning or error complexity Pruning, it proceeds in two stages. In the first stage, a sequence of trees T0, T1 . . . Tk are built on the training data where T0 is the original tree before pruning and Tk is the root tree. In second stage, one of these trees is chosen as the pruned tree, based on its generalization error estimation. Generalization error is defined as the misclassification rate over the distribution D.
If the given dataset is large enough the authors suggests to break it into training set and pruning set. The trees are constructed using the training set and evaluated on the pruning set. On the other hand, if the given dataset is not large enough they propose to use crossvalidation methodology, despite the computational complexity implications.

ReducedError Pruning
Reduced Error Pruning is simple procedure for pruning decision trees. While traversing over the internal nodes from the bottom to the top, the procedure checks for each internal node, whether replacing it with the most frequent class does not reduce the trees accuracy. In this case, the node is pruned. The procedure continues until any further pruning would decrease the accuracy. It uses pruning set in order to estimate the accuracy. It can be shown that this procedure ends with the smallest accurate sub tree with respect to a given pruning set.

Minimum Error Pruning (MEP)
Minimum Error Pruning has been proposed by Niblett and Bratko. It performs bottomup traversal of the internal nodes. In each node it compares the lprobability error rate estimation with and without pruning. The lprobability error rate estimation is a correction to the simple probability estimation using frequencies.

Pessimistic Pruning
Pessimistic pruning avoids the need of pruning set or cross validation and uses the pessimistic statistical correlation test instead. The basic idea is that the error ratio estimated using the training set is not reliable enough. Instead a more realistic measure known as continuity correction for binomial distribution should be used. The pessimistic pruning procedure performs topdown traversing over the internal nodes. If an internal node is pruned then all its descendants are removed from the pruning process, reulting in a relatively fast pruning.

Errorbased Pruning
Errorbased pruning is a simple method of pruning decision trees. ErrorBased Pruning is an evolution of the pessimistic pruning. It is implemented in the wellknown C4.5 algorithm. It uses the training set error at a node and does not require a validation set. Errorbased pruning (EBP) uses the error that is made at a node of the tree on the training data in an estimate of the test set error at that node. The degree of pruning is controlled by the certainty factor CF parameter. One objection to errorbased pruning is that it has the general effect of underpruning.

If CF is lower then pruning will be done

If CF is higher then no pruning will be done superscripts. Do not put footnotes in the reference list. Use

letters for table footnotes. put footnotes in the reference list. Use letters for table footnotes.
TABLE II. COMPARATIVE ANALYSIS OF PRUNING METHODS
Methods
Steps
Prunin g Set
Traversal strategy
Operator
Features
Cost Comple xity Pruning
2
Yes
All node consider ed together
Pruning any branch
Can use cross validation sets to estimate accuracy
Reduced Error pruning
1
Yes
Bottom up
Pruning any branch
Find optimal prune tree w.r.t pruning sets
Pessimis tic Pruning
1
No
Top down
Pruning any branch
Uses the continuity correction
Minimu m Error Pruning
2
Yes
Bottom up
Pruning any branch
Based on m probability estimate of
the error rate
Error Based Pruning
1
No
Bottom up
Pruning & grafting any branch
Estimate confidence intervals on training data sets


CONCLUSIONS
There are various decision tree induction methods available for classification. Among all others, C4.5 algorithm has highest frequency usage, specificity & high accuracy compared to other algorithms because of its simplicity, robustness and effectiveness.
C4.5 and SPRINT algorithms have a good classification accuracy compared to other algorithms used in the study. C4.5 decision tree has the ability to handle data with missing attribute values better than ID3 decision tree algorithm. It also avoids over fitting the data and reduces error pruning. The C4.5 classifier performs better in performance of rules generated and accuracy than ID3 and CART.
REFERENCES

Lior Rokach and Oded Maimon, TopDown Induction of Decision Trees Classifiers A Survey, IEEE Transactions On Systems, Man And Cyberneticspart C: Application And Reviews Vol. 35, no. 4, November 2005.

Anuja Priyama*, Abhijeeta, Rahul Guptaa, Anju Ratheeb, and Saurabh Srivastavab , Comparative Analysis of Decision Tree Classification Algorithms, International Journal of Current Engineering and Technology, ISSN 2277 – 4106 , Vol.3, No.2 (June 2013), 1 June 2013..

P Venkatesan, N R Yamuna, Treatment Response Classification in Randomized Clinical Trials: A Decision Tree Approach, Indian Journal
of Science and Technology, ISSN:09746846, Vol: 6, Issue: 1, January 2013.

J. Han, and M. Kamber, Data Mining Concepts and Techniques. Morgan Kaufmann Publishers Inc., United States of America, 2001.

M. N. Anyanwu, and S. G. Shiva, Comparative Analysis of Serial Decision Tree Classification Algorithms, Vol (3) Issue (3),Pages 230 239, 2009.

S. R. Safavin and D. Landgrebe. A survey of decision tree classifier methodology. IEEE Trans. on Systems, Man and Cybernetics, 21(3):660 674, 1991.

J. R. Quinlan, C4.5: Programs For Machine Learning. Morgan Kaufmann, Los Altos, 1993.