Decision tree

From 2015 to 2025 the Earth had 19,073 earthquakes of magnitude 5 and above. For more than one in three, somebody sent a report to the USGS seismology service “Did You Feel It?”. Can one tell in advance, from the magnitude and from how far away the nearest town is, whether a shock will be felt? A decision tree builds the answer from simple questions: each splits the shocks into two groups, and the next question is asked within a group. Below, the tree learns from 2015–2021 and is checked on 2022–2025, which it has not seen.

The tree's first question is not about magnitude but about distance: “is the nearest town no further than 106.5 km?”. Only someone nearby can feel a shock. A tree of depth 3, eight rectangles, guesses 79.0 % of the shocks of the later years; always answering “nobody felt it” gives 62.9 %. Now move the depth towards twenty. On the training years the share of right answers rises to 86.7 %, while on the later years it falls to 74.6 %: the tree cuts the plane into thousands of pieces and memorises accidents.

The idea

Ask one question “feature ≤ threshold?”, the one that best separates the answers. In each of the two resulting groups ask the next best question, and so on, until the groups become uniform or the questions run out. The answer for a new example is whatever was the majority in the group its questions led it to.

Trees are loved because they can be read. Here is the top of the tree from the scene, three levels, eight leaves; in brackets, how many training shocks were felt out of how many.

km to a town <= 106.5?  (4291/11933 felt, gain 0.172 bits)
  yes km to a town <= 44.5?  (2772/4034 felt, gain 0.048 bits)
  yes   yes magnitude <= 5.320?  (1440/1753 felt, gain 0.043 bits)
  yes   yes   yes -> felt (870/1147 felt)
  yes   yes   no  -> felt (570/606 felt)
  yes   no  magnitude <= 5.110?  (1332/2281 felt, gain 0.056 bits)
  yes   no    yes -> not felt (441/1021 felt)
  yes   no    no  -> felt (891/1260 felt)
  no  magnitude <= 5.950?  (1519/7899 felt, gain 0.061 bits)
  no    yes km to a town <= 533.5?  (1123/7285 felt, gain 0.043 bits)
  no    yes   yes -> not felt (924/4016 felt)
  no    yes   no  -> not felt (199/3269 felt)
  no    no  km to a town <= 224.5?  (396/614 felt, gain 0.102 bits)
  no    no    yes -> felt (206/239 felt)
  no    no    no  -> felt (190/375 felt)

If the nearest town is no further than 44.5 km, a shock is noticed in three cases out of four even at a magnitude up to 5.32, and above that in 570 cases out of 606. If the town is further than 106.5 km and the magnitude is at most 5.95, most likely not; and beyond 533.5 km such a shock was felt in only 199 cases out of 3269. A strong shock, of magnitude above 5.95, is noticed even from afar, if the town is no more than 224.5 km away.

How to choose a question

What does “best separates” mean? The uncertainty of a group is conveniently measured by entropy, the average number of bits needed to report the answer. If the share of felt shocks in a group is p, then

A uniform group has H = 0: the answer is known in advance. A group where exactly half were felt has H = 1 bit: each answer is a fair coin. For all the training shocks p ≈ 0.36, and H = 0.942 bits. After a question we have two groups with their own entropies; their average, weighted by the sizes of the groups, is the remaining uncertainty. The difference between “before” and “after” is the information gain. The best question is the one with the largest gain.

There are few candidates. The question “x ≤ t?” splits the shocks the same way for all t between two adjacent values of the feature, so it is enough to try the midpoints between adjacent distinct values. If the shocks are sorted by the feature and you go from left to right, moving them one at a time from the right group to the left, the counters of both groups are updated in O(1), and all thresholds of one feature are checked in one pass. Distance to a town gives a gain of 0.172 bits at a threshold of 106.5 km, the best magnitude threshold only 0.042 bits (this is the first problem of the article). Distance wins.

Greed and its price

The tree chooses each question without looking ahead. Building the best tree as a whole, for example one with the smallest average number of questions to the answer, is an NP-complete problem: Laurent Hyafil and Ronald Rivest proved this in 1976. So all practical algorithms are greedy, and sometimes greed goes wrong. The classic example is “exclusive or”: the answer is 1 when exactly one of two features equals 1. Each feature on its own says nothing about the answer, the gain of both questions is zero, and a greedy tree may ask neither, although two questions in a row would solve the problem completely.

Overfitting

A tree can be grown until each leaf has one example left, and then it makes no mistakes at all on the training data. But what has to be learned is the pattern, not the training data. The listing builds a tree of depth 20 once (greedy growth does not depend on where it stops, so a tree of depth d is its top part) and checks each top part:

 depth  leaves   train    test
     1       2   76.7%   76.5%
     2       4   78.2%   78.4%
     3       8   79.4%   79.0%
     4      16   80.0%   79.6%
     6      57   80.4%   79.1%
     8     182   81.2%   78.0%
    12     787   83.5%   76.1%
    16    1459   85.6%   75.0%
    20    1836   86.7%   74.6%

Up to depth 4 both shares grow together: the tree finds real rules. Further on the training share keeps growing, while the test share falls. The deep leaves hold a few shocks each, and the questions there no longer answer “will it be felt” but “which particular shocks happened in 2015–2021”. Sixteen leaves explain the later years better than 1836.

The remedies are to limit the depth, forbid leaves below a given size, not split a node if the gain is small, or grow a large tree and then prune the branches that do not pay off on held-out data, as CART does. Which limit to choose is decided by checking on data the tree has not seen. Here this is honest: we learn from the past and check on the future, as one would have to in practice.

Code

The listing reads the catalogue from the server where the code runs. Features are stored as integers, magnitude in hundredths. Gains are compared rounded to 10⁻⁹: that way equal gains are not separated by the last bit of a logarithm, and Python and Go build the same tree. On a tie the earlier feature and the smaller threshold win.

What it costs

In each node the examples are sorted by each of the F features, and that is the main work. At one level of the tree the nodes together hold at most n examples, so a level costs O(F·n log n), and the whole tree of depth h O(h·F·n log n). If the examples are sorted by each feature once and the order within groups is kept when a node is split, the logarithm goes away: this is how fast libraries work. Answering is a walk from the root to a leaf, O(h), and that is one of the reasons trees are loved where answers must be fast.

The lines are almost straight with a slope of about one: time grows as n log n, and the logarithm is hardly noticeable at these sizes. Depth 12 costs one and a half to three times more than depth 4, although there are three times as many levels: many branches stop earlier, when a group becomes uniform.

Where it is used

A single tree is rarely the most accurate model: a small change in the data can change the first question, and with it the whole tree. But trees are convenient building blocks. A random forest (Leo Breiman, 2001) trains hundreds of trees on random subsamples of examples and features and lets them vote. Gradient boosting builds trees one after another, each correcting the errors of the previous ones; the libraries XGBoost, LightGBM and CatBoost do exactly this, and on tabular data, such as applications, transactions or sensor measurements, they often turn out more accurate than neural networks. A single shallow tree remains where a decision has to be explained: it can be printed and checked by eye, as was done above.

History

The first tree for data analysis was proposed by James Morgan and John Sonquist in 1963. Their method AID split data from sociological surveys into groups one after another, without assuming that the effects of features simply add up; it was met mostly with criticism. In 1984 Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone published the book “Classification and Regression Trees”; the abbreviation of the title, CART, became the name of the method, and pruning a tree on held-out data became the standard. Independently of them Ross Quinlan built the ID3 algorithm (a 1986 paper) with information gain by Shannon entropy, and later its successor C4.5. Most of today's trees descend from these two schemes.

Problems

The first problem is the algorithm's main step: the best threshold of one feature in O(n log n), checked on real shocks. The second is a whole tree, but with the Gini measure and exact arithmetic: rules for ties and equal feature values decide everything there.