Histogram aggregation speeds decision-tree splitting by replacing a continuous feature’s many unique values with bin boundaries used as candidate split points. This avoids repeatedly scanning every possible value, which becomes costly for large datasets and gradient-boosted decision trees. section 5.4.3
A practical split-search workflow is:
- Choose a feature and a split-scoring function, such as Gini impurity. section 5.4.3
- Use every unique feature value for the basic search, or compute a fixed-width histogram and inspect its bin boundaries. section 5.4.3
- Evaluate each candidate and retain the feature threshold producing the best objective improvement. section 5.4.3
Latitude and Manhattan price ranges
For a classifier predicting whether a Manhattan host belongs to an upper or lower price range, latitude has many possible thresholds. Testing every unique value took 46.9 seconds, while testing 256 histogram boundaries found the same threshold and score in about 562 milliseconds. section 5.4.3
Listing 5.14 The histogram split
import numpy as np
def gini_impurity(y):
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs**2) #1
def histogram_split(x, y, use_histogram, n_bins=256):
if use_histogram:
hist, thresholds = np.histogram(
x, bins=n_bins, density=False
) #2
else:
thresholds = np.unique(x) #3
best_score = -1
best_threshold = None #4
for threshold in thresholds: #5
left_mask = x <= threshold
right_mask = x > threshold
left_y = y[left_mask]
right_y = y[right_mask] #6
score = (
gini_impurity(left_y) * len(left_y)
+ gini_impurity(right_y) * len(right_y)
) #7
if score > best_score: q #8
best_threshold = threshold
best_score = score
return best_threshold, best_score #9
Inspect the NumPy implementation to compare exact unique-value search with 256-bin threshold search and weighted Gini scoring. section 5.4.3
