In a decision tree, a threshold is a cutoff on one feature that divides data points between two branches. Choosing both the feature and its threshold determines how the tree partitions the input space. section 5.6
Let X be an n × d input matrix. For each feature j, form candidate thresholds τj from midpoints of its observed values. Compare feature–threshold pairs by the cost of their resulting partitions, and choose the pair with the lowest cost. Repeat this choice recursively to grow the tree. The search is greedy: it does not solve the globally optimal partitioning problem. section 5.6
For classification, a useful split leaves regions with little class impurity. If πk is the fraction of points in a region belonging to class k, the Gini index measures expected classification error and reaches zero for a pure region. Entropy offers another measure of uncertainty. Tree depth also matters: continuing to split can overfit rather than improve generalization. section 5.6
Listing 5.5 CART decision tree algorithm
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
class TreeNode():
def __init__(self, gini, num_samples, num_samples_class, class_label):
self.gini = gini #1
self.num_samples = num_samples #2
self.num_samples_class = num_samples_class #3
self.class_label = class_label #4
self.feature_idx = 0 #5
self.treshold = 0 #6
self.left = None #7
self.right = None #8
class DecisionTreeClassifier():
def __init__(self, max_depth = None):
self.max_depth = max_depth
def best_split(self, X_train, y_train):
m = y_train.size
if (m <= 1):
return None, None
mk = [np.sum(y_train == k) for k in range(self
.num_classes)] #9
best_gini = 1.0 – sum((n / m) ** 2 for n in mk) #10
best_idx, best_thr = None, None
#iterate over all features
for idx in range(self.num_features):
thresholds, classes = zip(*sorted(zip(X[:,
idx], y))) #11
num_left = [0]*self.num_classes
num_right = mk.copy()
for i in range(1, m): #12
k = classes[i-1]
num_left[k] += 1
num_right[k] -= 1
gini_left = 1.0 - sum(
(num_left[x] / i) ** 2 for x in range(self.num_classes)
)
gini_right = 1.0 - sum(
(num_right[x] / (m - i)) ** 2 for x in
range(self.num_classes)
)
gini = (i * gini_left + (m - i) * gini_right) / m
if thresholds[i] == thresholds[i - 1]:
continue
if (gini < best_gini):
best_gini = gini
best_idx = idx
best_thr = (thresholds[i] +
thresholds[i - 1]) / 2 #13
#end if
#end for
#end for
return best_idx, best_thr
def gini(self, y_train):
m = y_train.size
return 1.0 - sum((np.sum(y_train == k) / m) ** 2 for k in
range(self.num_classes))
def fit(self, X_train, y_train):
self.num_classes = len(set(y_train))
self.num_features = X_train.shape[1]
self.tree = self.grow_tree(X_train, y_train)
def grow_tree(self, X_train, y_train, depth=0):
num_samples_class = [np.sum(y_train == k) for k in
range(self.num_classes)]
class_label = np.argmax(num_samples_class)
node = TreeNode(
gini=self.gini(y_train),
num_samples=y_train.size,
num_samples_class=num_samples_class,
class_label=class_label,
)
if depth < self.max_depth: #14
idx, thr = self.best_split(X_train, y_train)
if idx is not None:
indices_left = X_train[:, idx] < thr
X_left, y_left = X_train[indices_left], y_train[indices_left]
X_right, y_right = X_train[~indices_left], y_train[~indices_left]
node.feature_index = idx
node.threshold = thr
node.left = self.grow_tree(X_left, y_left, depth + 1)
node.right = self.grow_tree(X_right, y_right, depth + 1)
return node
def predict(self, X_test):
return [self.predict_helper(x_test) for x_test in X_test]
def predict_helper(self, x_test):
node = self.tree
while node.left:
if x_test[node.feature_index] < node.threshold:
node = node.left
else:
node = node.right
return node.class_label
if __name__ == "__main__":
#load data
iris = load_iris()
X = iris.data[:, [2,3]]
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2,
random_state=42)
print("decision tree classifier...")
tree_clf = DecisionTreeClassifier(max_depth = 3)
tree_clf.fit(X_train, y_train)
print("prediction...")
y_pred = tree_clf.predict(X_test)
tree_clf_acc = accuracy_score(y_test, y_pred)
print("test set accuracy: ", tree_clf_acc)
The CART implementation stores a feature index and threshold in each node and begins split selection in best_split. section 5.6
A tree-split threshold is distinct from a binary classifier’s classification threshold. Varying the latter changes predicted labels and therefore the confusion-matrix counts; it produces different points on ROC and precision–recall curves. section 5.6 section 5.2
