001/*
002 * Copyright (c) 2020, 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.xgboost;
018
019import ml.dmlc.xgboost4j.java.Booster;
020import ml.dmlc.xgboost4j.java.XGBoostError;
021import org.tribuo.ImmutableFeatureMap;
022import org.tribuo.Model;
023
024import java.util.AbstractMap;
025import java.util.ArrayList;
026import java.util.Comparator;
027import java.util.LinkedHashMap;
028import java.util.List;
029import java.util.Map;
030import java.util.stream.Collectors;
031import java.util.stream.Stream;
032
033import static ml.dmlc.xgboost4j.java.Booster.FeatureImportanceType.*;
034
035/**
036 * Generate and collate feature importance information from the XGBoost model. This wraps the underlying functionality
037 * of the XGBoost model, and should provide feature importance metrics compatible with those provided by XGBoost's R
038 * and Python APIs. For a more treatment of what the different importance metrics mean and how to interpret them, see
039 * <a href="https://xgboost.readthedocs.io/en/latest/R-package/discoverYourData.html">here</a>. In brief
040 *
041 * <ul>
042 *     <li><b>Gain</b> measures the improvement in accuracy that a feature brings to the branches on which it appears.
043 *     This represents the sum of situated marginal contributions that a given feature makes to the each branching
044 *     chain in which it appears.</li>
045 *     <li><b>Cover</b> measures the number of examples a given feature discriminates across, relative to the total
046 *     number of examples all features discriminate across.</li>
047 *     <li><b>Weight</b> measures the number a times a feature occurs in the model. Due to the way the model builds trees,
048 *     this value is skewed in favor of continuous features.</li>
049 *     <li><b>Total Gain</b> is similar to gain, but not locally averaged by weight, and thus not skewed in the way that
050 *     weight can be skewed.</li>
051 *     <li><b>Total Cover</b> is similar to cover, but not locally averaged by weight, and thus not skewed in the way that
052 *     weight can be skewed.</li>
053 * </ul>
054 */
055public class XGBoostFeatureImportance {
056
057    /**
058     * An instance of feature importance values for a single feature. See {@link XGBoostFeatureImportance} for details
059     * on interpreting the metrics.
060     */
061    public static class XGBoostFeatureImportanceInstance {
062
063        private final String featureName;
064        private final double gain;
065        private final double cover;
066        private final double weight;
067        private final double totalGain;
068        private final double totalCover;
069
070        XGBoostFeatureImportanceInstance(String featureName, double gain, double cover, double weight, double totalGain, double totalCover) {
071            this.featureName = featureName;
072            this.gain = gain;
073            this.cover = cover;
074            this.weight = weight;
075            this.totalGain = totalGain;
076            this.totalCover = totalCover;
077        }
078
079        /**
080         * The feature name.
081         * @return The feature name.
082         */
083        public String getFeatureName() {
084            return featureName;
085        }
086
087        /**
088         * The information gain a feature provides when split on.
089         * @return The gain.
090         */
091        public double getGain() {
092            return gain;
093        }
094
095        /**
096         * The number of examples a feature discriminates between.
097         * @return The cover.
098         */
099        public double getCover() {
100            return cover;
101        }
102
103        /**
104         * The number of times a feature is used in the model.
105         * @return The number of times the feature is used to split.
106         */
107        public double getWeight() {
108            return weight;
109        }
110
111        /**
112         * The total gain across all times the feature is used to split.
113         * @return The total gain.
114         */
115        public double getTotalGain() {
116            return totalGain;
117        }
118
119        /**
120         * The total number of examples a feature discrimnates between.
121         * @return The total cover.
122         */
123        public double getTotalCover() {
124            return totalCover;
125        }
126
127        @Override
128        public String toString() {
129            return String.format("XGBoostFeatureImportanceRecord(feature=%s, gain=%.2f, cover=%.2f, weight=%.2f, totalGain=%.2f, totalCover=%.2f)",
130                    featureName, gain, cover, weight, totalGain, totalCover);
131        }
132    }
133
134    private final Booster booster;
135    private final ImmutableFeatureMap featureMap;
136    private final Model<?> model;
137
138    XGBoostFeatureImportance(Booster booster, Model<?> model) {
139        this.booster = booster;
140        this.model = model;
141        this.featureMap = model.getFeatureIDMap();
142    }
143
144    private String translateFeatureId(String xgbFeatName) {
145        return featureMap.get(Integer.parseInt(xgbFeatName.substring(1))).getName();
146    }
147
148    private Stream<Map.Entry<String, Double>> getImportanceStream(String importanceType) {
149        try {
150            return booster.getScore("", importanceType).entrySet().stream()
151                    .sorted(Comparator.comparingDouble((Map.Entry<String, Double> e) -> e.getValue()).reversed());
152        } catch (XGBoostError e) {
153            throw new IllegalStateException("Error generating feature importance for " + importanceType + " caused by", e);
154        }
155    }
156
157    private LinkedHashMap<String, Double> coalesceImportanceStream(Stream<Map.Entry<String, Double>> str) {
158        return str.collect(Collectors.toMap(e -> translateFeatureId(e.getKey()),
159                Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
160    }
161
162    /**
163     * Gain measures the improvement in accuracy that a feature brings to the branches on which it appears.
164     * This represents the sum of situated marginal contributions that a given feature makes to the each branching
165     * chain in which it appears.
166     * @return Ordered map where the keys are feature names and the value is the gain, sorted descending
167     */
168    public LinkedHashMap<String, Double> getGain() {
169        return coalesceImportanceStream(getImportanceStream(GAIN));
170    }
171
172    /**
173     *
174     * Gain measures the improvement in accuracy that a feature brings to the branches on which it appears.
175     * This represents the sum of situated marginal contributions that a given feature makes to the each branching
176     * chain in which it appears. Returns only the top numFeatures features.
177     * @param numFeatures number of features to return
178     * @return Ordered map where the keys are feature names and the value is the gain, sorted descending
179     */
180    public LinkedHashMap<String, Double> getGain(int numFeatures) {
181        return coalesceImportanceStream(getImportanceStream(GAIN).limit(numFeatures));
182    }
183
184    /**
185     * Cover measures the number of examples a given feature discriminates across, relative to the total
186     * number of examples all features discriminate across.
187     * @return Ordered map where the keys are feature names and the value is the cover, sorted descending
188     */
189    public LinkedHashMap<String, Double> getCover() {
190        return coalesceImportanceStream(getImportanceStream(COVER));
191    }
192    /**
193     *
194     * Cover measures the number of examples a given feature discriminates across, relative to the total.
195     * number of examples all features discriminate across. Returns only the top numFeatures features.
196     * @param numFeatures number of features to return
197     * @return Ordered map where the keys are feature names and the value is the cover, sorted descending
198     */
199    public LinkedHashMap<String, Double> getCover(int numFeatures) {
200        return coalesceImportanceStream(getImportanceStream(COVER).limit(numFeatures));
201    }
202
203    /**
204     * Weight measures the number a times a feature occurs in the model. Due to the way the model builds trees,
205     * this value is skewed in favor of continuous features.
206     * @return Ordered map where the keys are feature names and the value is the weight, sorted descending
207     */
208    public LinkedHashMap<String, Double> getWeight() {
209        return coalesceImportanceStream(getImportanceStream(WEIGHT));
210    }
211    /**
212     * Weight measures the number a times a feature occurs in the model. Due to the way the model builds trees,
213     * this value is skewed in favor of continuous features. Returns only the top numFeatures features.
214     * @param numFeatures number of features to return
215     * @return Ordered map where the keys are feature names and the value is the weight, sorted descending
216     */
217    public LinkedHashMap<String, Double> getWeight(int numFeatures) {
218        return coalesceImportanceStream(getImportanceStream(WEIGHT).limit(numFeatures));
219    }
220
221    /**
222     * Total Gain is similar to gain, but not locally averaged by weight, and thus not skewed in the way that
223     * weight can be skewed.
224     * @return Ordered map where the keys are feature names and the value is the total gain, sorted descending
225     */
226    public LinkedHashMap<String, Double> getTotalGain() {
227        return coalesceImportanceStream(getImportanceStream(TOTAL_GAIN));
228    }
229    /**
230     * Total Gain is similar to gain, but not locally averaged by weight, and thus not skewed in the way that
231     * weight can be skewed. Returns only top numFeatures features.
232     * @param numFeatures number of features to return
233     * @return Ordered map where the keys are feature names and the value is the total gain, sorted descending
234     */
235    public LinkedHashMap<String, Double> getTotalGain(int numFeatures) {
236        return coalesceImportanceStream(getImportanceStream(TOTAL_GAIN).limit(numFeatures));
237    }
238
239    /**
240     * Total Cover is similar to cover, but not locally averaged by weight, and thus not skewed in the way that
241     * weight can be skewed.
242     * @return Ordered map where the keys are feature names and the value is the total gain, sorted descending
243     */
244    public LinkedHashMap<String, Double> getTotalCover() {
245        return coalesceImportanceStream(getImportanceStream(TOTAL_COVER));
246    }
247    /**
248     * Total Cover is similar to cover, but not locally averaged by weight, and thus not skewed in the way that
249     * weight can be skewed. Returns only top numFeatures features.
250     * @param numFeatures number of features to return
251     * @return Ordered map where the keys are feature names and the value is the total gain, sorted descending
252     */
253    public LinkedHashMap<String, Double> getTotalCover(int numFeatures) {
254        return coalesceImportanceStream(getImportanceStream(TOTAL_COVER).limit(numFeatures));
255    }
256
257    /**
258     * Gets all the feature importances for all the features.
259     * @return records of all importance metrics for each feature, sorted by gain.
260     */
261    public List<XGBoostFeatureImportanceInstance> getImportances() {
262        Map<String, LinkedHashMap<String, Double>> importanceByType = Stream.of(GAIN, COVER, WEIGHT, TOTAL_GAIN, TOTAL_COVER)
263                .map(importanceType -> new AbstractMap.SimpleEntry<>(importanceType, coalesceImportanceStream(getImportanceStream(importanceType))))
264                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
265        // this is already sorted by gain
266        List<String> features = new ArrayList<>(importanceByType.get(GAIN).keySet());
267        return features.stream().map(featureName -> new XGBoostFeatureImportanceInstance(featureName,
268                importanceByType.get(GAIN).get(featureName),
269                importanceByType.get(COVER).get(featureName),
270                importanceByType.get(WEIGHT).get(featureName),
271                importanceByType.get(TOTAL_GAIN).get(featureName),
272                importanceByType.get(TOTAL_COVER).get(featureName)))
273                .collect(Collectors.toList());
274    }
275
276    /**
277     * Gets the feature importances for the top n features sorted by gain.
278     * @param numFeatures number of features to return
279     * @return records of all importance metrics for each feature, sorted by gain.
280     */
281    public List<XGBoostFeatureImportanceInstance> getImportances(int numFeatures) {
282        Map<String, LinkedHashMap<String, Double>> importanceByType = Stream.of(GAIN, COVER, WEIGHT, TOTAL_GAIN, TOTAL_COVER)
283                .map(importanceType -> new AbstractMap.SimpleEntry<>(importanceType, coalesceImportanceStream(getImportanceStream(importanceType))))
284                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
285        // this is already sorted by gain
286        List<String> features = new ArrayList<>(importanceByType.get(GAIN).keySet()).subList(0, Math.min(importanceByType.get(GAIN).keySet().size(), numFeatures));
287        return features.stream().map(featureName -> new XGBoostFeatureImportanceInstance(featureName,
288                importanceByType.get(GAIN).get(featureName),
289                importanceByType.get(COVER).get(featureName),
290                importanceByType.get(WEIGHT).get(featureName),
291                importanceByType.get(TOTAL_GAIN).get(featureName),
292                importanceByType.get(TOTAL_COVER).get(featureName)))
293                .collect(Collectors.toList());
294    }
295
296    @Override
297    public String toString() {
298        return String.format("XGBoostFeatureImportance(model=%s)", model.toString());
299    }
300}