decision trees编辑历史

# Decision Tree

## 1 Introduction

A decision tree is a supervised machine learning algorithm used for classification and regression tasks. It models decisions and their possible consequences as a tree-like structure, where internal nodes represent tests on input features, branches correspond to the outcomes of those tests, and leaf nodes represent final predictions (class labels or continuous values). Decision trees are valued for their interpretability, simplicity, and ability to handle both numerical and categorical data. Common algorithms for building decision trees include ID3, C4.5, and CART, each employing different splitting criteria such as information gain, Gini impurity, or variance reduction.

### 1.1 History and Evolution

The concept of decision trees dates back to the 1960s, with early work by Morgan and Sonquist (1963) on regression trees and the Automatic Interaction Detection (AID) algorithm. In the 1970s and 1980s, the field saw significant progress: Quinlan introduced the ID3 algorithm (Iterative Dichotomiser 3) in 1986, based on information theory, and later refined it into C4.5 in 1993. Around the same time, Breiman, Friedman, Olshen, and Stone developed the Classification and Regression Trees (CART) algorithm in 1984. These foundational methods remain widely used, with modern extensions including ensemble methods and pruning techniques.

### 1.2 Basic Terminology

#### 1.2.1 Root Node

The topmost node in a decision tree. It represents the entire dataset and is the first point where a split on a feature occurs. The root node has no incoming branches.

#### 1.2.2 Internal Node

A node that has incoming and outgoing branches. Internal nodes represent a test on a feature, and each outgoing branch corresponds to a possible outcome of that test.

#### 1.2.3 Leaf Node

A terminal node with no outgoing branches. Each leaf node holds a predicted value (class label for classification or a numeric value for regression) based on the subset of training d