A tree by Gini
Instead of entropy, decision trees often measure uncertainty by Gini impurity; scikit-learn, for example, does so by default. For a group of m examples, c of them ones, we will count it “in pieces”:
$$G(m, c) = m - \frac{c^2 + (m - c)^2}{m}.$$This is m times the probability that two random examples of the group (with replacement) belong to different classes: 0 for a pure group, m/2 for a half-and-half one. Build a tree by these rules and answer the queries.
- In a node with examples S, the questions considered are “xf ≤ v?”, where f is the number of a feature, v is the value of this feature for some example of S, and at least one example of S has the feature greater than v.
- The best question has the smallest sum G(group “yes”) + G(group “no”). On a tie the smaller f is chosen, and for equal f the smaller v. The comparison must be exact.
- A node is split by its best question if its depth is less than D (the root has depth 0), it contains both zeros and ones, and the sum of G after the split is strictly less than G(S). Otherwise it is a leaf, and its answer is 1 if more than half of it are ones, otherwise 0.
One of the tests is the earthquakes of 2015–2021 from the USGS catalogue (features: magnitude in hundredths, depth in tenths of a kilometre, distance to the nearest town in kilometres; the answer is whether anybody felt it), and the queries are the shocks of 2022–2025.
Input
The first line holds n, F, D (1 ≤ n ≤ 2000, 1 ≤ F ≤ 3, 0 ≤ D ≤ 12). Each of the following n lines holds F integer features (from 0 to 10⁶) and the answer 0 or 1. Then q (1 ≤ q ≤ 2000) and q lines of F integer features.
Output
For each query, the tree's answer, 0 or 1, on a separate line.
Examples
Example 1
8 1 2 1 0 2 0 2 0 2 1 3 1 3 1 4 1 4 0 5 0 2 3 4 5
0 0 1 0 0
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is the decision tree from the article, only with a different measure. Start with one node: how do you try all the questions “xf ≤ v?” of one feature in one pass over the sorted examples?
2Hint 2
“The comparison must be exact.” G contains a division. Since the node size m does not depend on the question, what is it enough to compare, and how do you compare two fractions without dividing?
3The idea
The sum of G over two groups equals m − (s₁/m₁ + s₂/m₂), where s = c² + (m − c)². So the best question has the largest fraction (s₁m₂ + s₂m₁)/(m₁m₂), and two such fractions are compared by cross-multiplication in integers. The threshold v is the feature value of the last example of the “yes” group in sorted order, and questions between equal values are not considered: they do not separate such examples.
4Walkthrough
Build the nodes recursively. In a node, for each feature sort its examples stably and go from left to right, counting the ones on the left. At each point where the value changes we get a question: the numerator s₁m₂ + s₂m₁ and the denominator m₁m₂. A new question replaces the best only if it is strictly better, so on a tie the smaller feature and the smaller threshold remain. Split the node if the depth is less than D, the node is not pure and (s₁/m₁ + s₂/m₂) > s/m, that is, impurity really falls. Then send each query down the tree.
The orders of magnitude: s up to 4·10⁶, the numerator up to 1.6·10¹⁰, the denominator up to 10⁶, their products in a comparison up to 1.6·10¹⁶: they fit in 64-bit integers, but no longer exactly in float64.
4+Solution
5Complexity
At each level of the tree each example is sorted by each feature: O(D·F·n log n) to build and O(D) per query.
6Common mistakes
- A question between equal values. If you evaluate a split after each example and take the left value as the threshold, the evaluation belongs to one split, while the question “≤ v” makes another: all equal values go to the left. Earthquake features repeat all the time (magnitudes are multiples of hundredths), and the third test catches this.
- Comparison in floating point. Equal fractions computed by different routes can differ in the last bit, and the tie rule then fires in the wrong place.
- A split without gain. If a question does not reduce impurity, the node must stay a leaf.
- A half-and-half leaf. With equal numbers of zeros and ones the answer is 0: ones must be more than half.