Basic Concepts of Decision Trees

Decision Tree is a tree-structured method used for behavioral research, decision analysis, and machine learning. It is a fundamental classification method in machine learning that uses probability analysis to evaluate project risks and determine feasibility. Each internal node represents a test on an attribute, each branch represents a test output, and each leaf node represents a category.

The key to building an effective decision tree is selecting the priority of decision conditions for each branch node. A good split point is one that can divide all current nodes into two classes where each class is "pure" - meaning high accuracy with most instances belonging to the same target result. The "purity" of a split is quantified using two algorithms: Gini Impurity and Entropy.

Gini Impurity measures the expected error rate when randomly applying a result from a set to items in that set, representing the degree of mixing in the data.

Entropy measures the difficulty of describing an event. The more "pure" an event is, the smaller its information content. Events with probability 0 or 1 are certain and have zero information content. When probabilities differ, Shannon Entropy formula is used: H(X) = -ΣP(xi)log2(P(xi)). Building a decision tree involves selecting features that minimize information content after splitting, making the data more "pure".

Overfitting is a common problem where the tree becomes too complex and fits training data perfectly but performs poorly on new data. To avoid overfitting, two main approaches are used: tree constraints (setting minimum samples per leaf/node, maximum tree depth, maximum number of leaf nodes, maximum features per split) and pruning (removing subtrees that don't improve prediction accuracy).

Common pruning methods include Reduced Error Pruning (REP), Pessimistic Error Pruning (PEP), and Cost Complexity Pruning (CCP).

ID3 Algorithm (Iterative Dichotomiser 3) is a basic decision tree construction algorithm that uses information gain as the criterion for selecting test attributes. It selects the attribute with the highest information gain at each node as the splitting criterion. Information gain is the difference between the entropy before splitting and the weighted sum of entropies after splitting.

ID3 has limitations: it can only handle discrete data, requires sufficient sample size, and tends to prefer attributes with more values. These limitations led to the development of C4.5, CART, and Random Forest algorithms.