Construire un arbre : divisions, nœuds et feuilles

A decision tree is a flowchart-like structure where each internal node asks a yes/no question about one feature, each branch represents an answer, and each leaf node contains a prediction. To classify a new sample, you start at the root, follow branches according to feature values, and arrive at a leaf whose label is the prediction. Decision trees are interpretable by design — you can trace exactly why any prediction was made by reading the sequence of questions answered, which makes them popular in regulated industries like finance and healthcare.

A decision tree has three types of components: root node (the first question asked — the most informative split of the entire dataset), internal nodes (intermediate questions that further partition subsets of the data), and leaf nodes (terminal nodes where predictions are stored). Each internal node splits data into two or more subsets based on a feature threshold. The depth of a tree is the length of the longest path from root to any leaf. Deeper trees can represent more complex patterns but are more prone to overfitting.

Decision tree construction is a greedy, recursive algorithm. At each node, it evaluates every possible split on every feature and threshold, picks the split that best separates the classes (measured by Gini impurity or information gain), applies that split, and then recursively repeats the process on each resulting subset. This continues until a stopping criterion is met: maximum depth reached, minimum samples per node, or no more useful splits exist. Greedy means the locally best split is chosen at each step, without backtracking — this can miss globally optimal splits but makes the algorithm tractable.

Decision trees in scikit-learn always use axis-aligned (orthogonal) splits: each question asks if one feature is above or below a threshold (e.g., age <= 35?). This creates rectangular decision regions in 2D feature space. While this approach is simple and interpretable, it cannot efficiently represent diagonal decision boundaries — for example, separating two classes along a 45-degree line requires many splits. Tree ensembles (Random Forests) overcome this by combining many trees, each with different axis-aligned splits that together approximate any boundary shape.

Scikit-learn's DecisionTreeClassifier trains in a single call to fit(). Key parameters include max_depth (maximum tree depth — critical for controlling overfitting), criterion (split quality measure: 'gini' or 'entropy'), and min_samples_split (minimum samples to split a node — prevents splitting tiny groups). The tree is ready to predict immediately after fitting. Unlike KNN, prediction is O(log N) — just follow the learned branches — making decision trees fast at inference time.

The power of decision trees is that you can trace every prediction step by step. The decision_path() method returns a sparse matrix indicating which nodes each sample passed through. The apply() method returns the leaf node index for each sample. These tools let you explain to a user exactly which questions were asked and what answers led to the prediction — essential for compliance, debugging, and building trust with non-technical stakeholders.

Each leaf node stores a class distribution from the training samples that reached it. For classification, the predicted class is the majority class in the leaf. For probability estimation, predict_proba() returns the fraction of each class in the leaf. A leaf containing 10 samples: 9 class A, 1 class B predicts class A with probability 0.9. Trees with fewer samples per leaf produce less reliable probability estimates, which is why regularisation parameters like min_samples_leaf matter for calibrated probability outputs.

DecisionTreeRegressor works the same way as the classifier but predicts the mean target value of training samples in each leaf. The split criterion changes: instead of Gini impurity, it minimises mean squared error (or mean absolute error) within each resulting child node. Regression trees produce step-function predictions — constant values within rectangular regions. With enough depth, they can fit any training data exactly, but this leads to severe overfitting. Control depth and min_samples_leaf to regularise the regression tree.

After fitting, tree.feature_importances_ provides a measure of how much each feature contributed to the splits. Feature importance is calculated as the total reduction in impurity (Gini or entropy) attributed to each feature, weighted by the fraction of samples reaching each split. Values sum to 1.0. The most important feature gets the highest score. This provides a quick, interpretable way to identify which inputs drive predictions most — useful for feature selection, business insight, and detecting potential data issues.

A key practical advantage of decision trees is that they are completely scale-invariant. A split on income <= 50000 and a split on income_thousands <= 50 produce identical tree structures. Adding 100 to all values in a feature, or multiplying by 1000, does not change which splits are chosen. You never need to apply StandardScaler or MinMaxScaler before a decision tree. This also means decision trees handle features on wildly different scales without any preprocessing, making pipelines simpler.

Decision trees handle missing values more gracefully than many algorithms. Scikit-learn's DecisionTreeClassifier supports missing values natively when splitter='best' — samples with missing values in the split feature are sent to the child that minimises impurity on the non-missing data. Alternatively, you can use surrogate splits: when the primary split feature is missing for a sample, a correlated feature is used instead. This robustness to missing data is one practical advantage of tree-based models over distance-based methods like KNN that require complete feature vectors.

In this lesson you learned: how decision trees recursively partition data using axis-aligned splits, that each leaf stores the class distribution for majority-vote prediction, and that decision trees are scale-invariant and require no feature scaling. Next up we explore Gini impurity and information gain — the criteria that determine which split to choose at each node.