Source code

001/*
002 * Copyright (c) 2015, 2022, Oracle and/or its affiliates. All rights reserved.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.tribuo.common.tree;
018
019import com.oracle.labs.mlrg.olcut.config.Config;
020import com.oracle.labs.mlrg.olcut.provenance.Provenance;
021import org.tribuo.Dataset;
022import org.tribuo.Example;
023import org.tribuo.ImmutableFeatureMap;
024import org.tribuo.ImmutableOutputInfo;
025import org.tribuo.Output;
026import org.tribuo.Trainer;
027import org.tribuo.provenance.ModelProvenance;
028import org.tribuo.provenance.SkeletalTrainerProvenance;
029import org.tribuo.provenance.TrainerProvenance;
030import org.tribuo.util.Util;
031
032import java.time.OffsetDateTime;
033import java.util.ArrayDeque;
034import java.util.Collections;
035import java.util.Deque;
036import java.util.List;
037import java.util.Map;
038import java.util.SplittableRandom;
039
040/**
041 * Base class for {@link org.tribuo.Trainer}'s that use an approximation of the CART algorithm to build a decision tree.
042 * <p>
043 * See:
044 * <pre>
045 * J. Friedman, T. Hastie, &amp; R. Tibshirani.
046 * "The Elements of Statistical Learning"
047 * Springer 2001. <a href="http://web.stanford.edu/~hastie/ElemStatLearn/">PDF</a>
048 * </pre>
049 */
050public abstract class AbstractCARTTrainer<T extends Output<T>> implements DecisionTreeTrainer<T> {
051
052    /**
053     * Default minimum weight of examples allowed in a leaf node.
054     */
055    public static final int MIN_EXAMPLES = 5;
056
057    /**
058     * Minimum weight of examples allowed in a leaf.
059     */
060    @Config(description="The minimum weight allowed in a child node.")
061    protected float minChildWeight = MIN_EXAMPLES;
062
063    /**
064     * Maximum tree depth. Integer.MAX_VALUE indicates the depth is unlimited.
065     */
066    @Config(description="The maximum depth of the tree.")
067    protected int maxDepth = Integer.MAX_VALUE;
068
069    /**
070     * Minimum impurity decrease. The decrease in impurity needed in order to split the node.
071     */
072    @Config(description="The decrease in impurity needed in order to split the node.")
073    protected float minImpurityDecrease = 0.0f;
074
075    /**
076     * Number of features to sample per split. 1 indicates all features are considered.
077     */
078    @Config(description="The fraction of features to consider in each split. 1.0f indicates all features are considered.")
079    protected float fractionFeaturesInSplit = 1.0f;
080
081    /**
082     * Whether to choose split points for features at random.
083     */
084    @Config(description="Whether to choose split points for features at random.")
085    protected boolean useRandomSplitPoints = false;
086
087    @Config(description="The RNG seed to use when sampling features in a split.")
088    protected long seed = Trainer.DEFAULT_SEED;
089
090    protected SplittableRandom rng;
091
092    protected int trainInvocationCounter;
093
094    /**
095     * After calls to this superconstructor subclasses must call postConfig().
096     * @param maxDepth The maximum depth of the tree.
097     * @param minChildWeight The minimum child weight allowed.
098     * @param minImpurityDecrease The minimum decrease in impurity necessary to split a node.
099     * @param fractionFeaturesInSplit The fraction of features to consider at each split.
100     * @param useRandomSplitPoints Whether to choose split points for features at random.
101     * @param seed The seed for the feature subsampling RNG.
102     */
103    protected AbstractCARTTrainer(int maxDepth, float minChildWeight, float minImpurityDecrease,
104                                  float fractionFeaturesInSplit, boolean useRandomSplitPoints, long seed) {
105        this.maxDepth = maxDepth;
106        this.fractionFeaturesInSplit = fractionFeaturesInSplit;
107        this.useRandomSplitPoints = useRandomSplitPoints;
108        this.minChildWeight = minChildWeight;
109        this.minImpurityDecrease = minImpurityDecrease;
110        this.seed = seed;
111    }
112
113    /**
114     * Used by the OLCUT configuration system, and should not be called by external code.
115     */
116    @Override
117    public synchronized void postConfig() {
118        this.rng = new SplittableRandom(seed);
119
120        if ((fractionFeaturesInSplit <= 0.0f) || (this.fractionFeaturesInSplit > 1.0f)) {
121            throw new IllegalArgumentException("fractionFeaturesInSplit must be greater than 0 and less than or equal" +
122                    " to 1");
123        }
124
125        if (minImpurityDecrease < 0.0f) {
126            throw new IllegalArgumentException("minImpurityDecrease must be greater than or equal to 0");
127        }
128
129        if (maxDepth < 0) {
130            throw new IllegalArgumentException("maxDepth must be non-negative");
131        }
132
133        if (minChildWeight <= 0.0f) {
134            throw new IllegalArgumentException("minChildWeight must be greater than 0");
135        }
136    }
137
138    @Override
139    public int getInvocationCount() {
140        return trainInvocationCounter;
141    }
142
143    @Override
144    public synchronized void setInvocationCount(int invocationCount){
145        if(invocationCount < 0){
146            throw new IllegalArgumentException("The supplied invocationCount is less than zero.");
147        }
148
149        rng = new SplittableRandom(seed);
150
151        for (trainInvocationCounter = 0; trainInvocationCounter < invocationCount; trainInvocationCounter++){
152            SplittableRandom localRNG = rng.split();
153        }
154
155    }
156
157    @Override
158    public float getFractionFeaturesInSplit() {
159        return fractionFeaturesInSplit;
160    }
161
162    @Override
163    public boolean getUseRandomSplitPoints() {
164        return useRandomSplitPoints;
165    }
166
167    @Override
168    public float getMinImpurityDecrease() {
169        return minImpurityDecrease;
170    }
171
172    @Override
173    public TreeModel<T> train(Dataset<T> examples) {
174        return train(examples, Collections.emptyMap());
175    }
176
177    @Override
178    public TreeModel<T> train(Dataset<T> examples, Map<String, Provenance> runProvenance) {
179        return train(examples, runProvenance, INCREMENT_INVOCATION_COUNT);
180    }
181
182    @Override
183    public TreeModel<T> train(Dataset<T> examples, Map<String, Provenance> runProvenance, int invocationCount) {
184        if (examples.getOutputInfo().getUnknownCount() > 0) {
185            throw new IllegalArgumentException("The supplied Dataset contained unknown Outputs, and this Trainer is supervised.");
186        }
187        // Creates a new RNG, adds one to the invocation count.
188        SplittableRandom localRNG;
189        TrainerProvenance trainerProvenance;
190        synchronized(this) {
191            if(invocationCount != INCREMENT_INVOCATION_COUNT) {
192                setInvocationCount(invocationCount);
193            }
194            localRNG = rng.split();
195            trainerProvenance = getProvenance();
196            trainInvocationCounter++;
197        }
198
199        ImmutableFeatureMap featureIDMap = examples.getFeatureIDMap();
200        ImmutableOutputInfo<T> outputIDInfo = examples.getOutputIDInfo();
201
202        int numFeaturesInSplit = Math.min(Math.round(fractionFeaturesInSplit * featureIDMap.size()),featureIDMap.size());
203        int[] indices;
204        int[] originalIndices = new int[featureIDMap.size()];
205        for (int i = 0; i < originalIndices.length; i++) {
206            originalIndices[i] = i;
207        }
208        if (numFeaturesInSplit != featureIDMap.size()) {
209            indices = new int[numFeaturesInSplit];
210        } else {
211            indices = originalIndices;
212        }
213
214        float weightSum = 0.0f;
215        for (Example<T> e : examples) {
216            weightSum += e.getWeight();
217        }
218        float scaledMinImpurityDecrease = getMinImpurityDecrease() * weightSum;
219        AbstractTrainingNode.LeafDeterminer leafDeterminer = new AbstractTrainingNode.LeafDeterminer(maxDepth,
220                minChildWeight, scaledMinImpurityDecrease);
221
222        AbstractTrainingNode<T> root = mkTrainingNode(examples, leafDeterminer);
223        Deque<AbstractTrainingNode<T>> queue = new ArrayDeque<>();
224        queue.add(root);
225
226        while (!queue.isEmpty()) {
227            AbstractTrainingNode<T> node = queue.poll();
228            if ((node.getImpurity() > 0.0) && (node.getDepth() < maxDepth) &&
229                    (node.getWeightSum() >= minChildWeight)) {
230                if (numFeaturesInSplit != featureIDMap.size()) {
231                    Util.randpermInPlace(originalIndices, localRNG);
232                    System.arraycopy(originalIndices, 0, indices, 0, numFeaturesInSplit);
233                }
234                List<AbstractTrainingNode<T>> nodes = node.buildTree(indices, localRNG, getUseRandomSplitPoints());
235                // Use the queue as a stack to improve cache locality.
236                // Building depth first.
237                for (AbstractTrainingNode<T> newNode : nodes) {
238                    queue.addFirst(newNode);
239                }
240            }
241        }
242
243        ModelProvenance provenance = new ModelProvenance(TreeModel.class.getName(), OffsetDateTime.now(), examples.getProvenance(), trainerProvenance, runProvenance);
244        return new TreeModel<>("cart-tree", provenance, featureIDMap, outputIDInfo, false, root.convertTree());
245    }
246
247    /**
248     * Makes the initial training node.
249     * @param examples The dataset to use.
250     * @param leafDeterminer The leaf determination function.
251     * @return The initial training node.
252     */
253    protected abstract AbstractTrainingNode<T> mkTrainingNode(Dataset<T> examples,
254                                                              AbstractTrainingNode.LeafDeterminer leafDeterminer);
255
256    /**
257     * Provenance for {@link AbstractCARTTrainer}. No longer used.
258     */
259    @Deprecated
260    protected static abstract class AbstractCARTTrainerProvenance extends SkeletalTrainerProvenance {
261        private static final long serialVersionUID = 1L;
262
263        /**
264         * Constructs a provenance for the host AbstractCARTTrainer.
265         * @param host The host trainer.
266         * @param <T> The trainer type.
267         */
268        protected <T extends Output<T>> AbstractCARTTrainerProvenance(AbstractCARTTrainer<T> host) {
269            super(host);
270        }
271
272        /**
273         * Deserialization constructor.
274         * @param map The provenance map.
275         */
276        protected AbstractCARTTrainerProvenance(Map<String,Provenance> map) {
277            super(map);
278        }
279    }
280}