tree.h 17.3 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
6
7
8
#ifndef LIGHTGBM_TREE_H_
#define LIGHTGBM_TREE_H_

#include <LightGBM/dataset.h>
9
#include <LightGBM/meta.h>
Guolin Ke's avatar
Guolin Ke committed
10
11

#include <string>
12
#include <map>
13
14
15
#include <memory>
#include <unordered_map>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
16
17
18

namespace LightGBM {

Guolin Ke's avatar
Guolin Ke committed
19
20
#define kCategoricalMask (1)
#define kDefaultLeftMask (2)
Guolin Ke's avatar
Guolin Ke committed
21
22
23
24
25

/*!
* \brief Tree model
*/
class Tree {
Nikita Titov's avatar
Nikita Titov committed
26
 public:
Guolin Ke's avatar
Guolin Ke committed
27
28
29
30
31
32
33
34
35
  /*!
  * \brief Constructor
  * \param max_leaves The number of max leaves
  */
  explicit Tree(int max_leaves);

  /*!
  * \brief Construtor, from a string
  * \param str Model string
36
  * \param used_len used count of str
Guolin Ke's avatar
Guolin Ke committed
37
  */
38
  Tree(const char* str, size_t* used_len);
Guolin Ke's avatar
Guolin Ke committed
39
40
41
42

  ~Tree();

  /*!
Qiwei Ye's avatar
Qiwei Ye committed
43
44
45
  * \brief Performing a split on tree leaves.
  * \param leaf Index of leaf to be split
  * \param feature Index of feature; the converted index after removing useless features
Guolin Ke's avatar
Guolin Ke committed
46
  * \param real_feature Index of feature, the original index on data
47
  * \param threshold_bin Threshold(bin) of split
48
  * \param threshold_double Threshold on feature value
Guolin Ke's avatar
Guolin Ke committed
49
50
  * \param left_value Model Left child output
  * \param right_value Model Right child output
Guolin Ke's avatar
Guolin Ke committed
51
52
  * \param left_cnt Count of left child
  * \param right_cnt Count of right child
Guolin Ke's avatar
Guolin Ke committed
53
  * \param gain Split gain
Guolin Ke's avatar
Guolin Ke committed
54
55
  * \param missing_type missing type
  * \param default_left default direction for missing value
Guolin Ke's avatar
Guolin Ke committed
56
57
  * \return The index of new leaf.
  */
58
59
  int Split(int leaf, int feature, int real_feature, uint32_t threshold_bin,
            double threshold_double, double left_value, double right_value,
60
            int left_cnt, int right_cnt, float gain, MissingType missing_type, bool default_left);
Guolin Ke's avatar
Guolin Ke committed
61

62
63
64
65
66
67
68
  /*!
  * \brief Performing a split on tree leaves, with categorical feature
  * \param leaf Index of leaf to be split
  * \param feature Index of feature; the converted index after removing useless features
  * \param real_feature Index of feature, the original index on data
  * \param threshold_bin Threshold(bin) of split, use bitset to represent
  * \param num_threshold_bin size of threshold_bin
69
70
  * \param threshold Thresholds of real feature value, use bitset to represent
  * \param num_threshold size of threshold
71
72
73
74
75
76
77
  * \param left_value Model Left child output
  * \param right_value Model Right child output
  * \param left_cnt Count of left child
  * \param right_cnt Count of right child
  * \param gain Split gain
  * \return The index of new leaf.
  */
78
79
  int SplitCategorical(int leaf, int feature, int real_feature, const uint32_t* threshold_bin, int num_threshold_bin,
                       const uint32_t* threshold, int num_threshold, double left_value, double right_value,
80
                       int left_cnt, int right_cnt, float gain, MissingType missing_type);
81

Guolin Ke's avatar
Guolin Ke committed
82
  /*! \brief Get the output of one leaf */
83
  inline double LeafOutput(int leaf) const { return leaf_value_[leaf]; }
Guolin Ke's avatar
Guolin Ke committed
84

Guolin Ke's avatar
Guolin Ke committed
85
86
87
88
89
  /*! \brief Set the output of one leaf */
  inline void SetLeafOutput(int leaf, double output) {
    leaf_value_[leaf] = output;
  }

Guolin Ke's avatar
Guolin Ke committed
90
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
91
  * \brief Adding prediction value of this tree model to scores
Guolin Ke's avatar
Guolin Ke committed
92
93
94
95
  * \param data The dataset
  * \param num_data Number of total data
  * \param score Will add prediction to score
  */
96
97
98
  void AddPredictionToScore(const Dataset* data,
                            data_size_t num_data,
                            double* score) const;
Guolin Ke's avatar
Guolin Ke committed
99
100

  /*!
Qiwei Ye's avatar
Qiwei Ye committed
101
  * \brief Adding prediction value of this tree model to scorese
Guolin Ke's avatar
Guolin Ke committed
102
103
104
105
106
107
  * \param data The dataset
  * \param used_data_indices Indices of used data
  * \param num_data Number of total data
  * \param score Will add prediction to score
  */
  void AddPredictionToScore(const Dataset* data,
Qiwei Ye's avatar
Qiwei Ye committed
108
                            const data_size_t* used_data_indices,
109
                            data_size_t num_data, double* score) const;
Guolin Ke's avatar
Guolin Ke committed
110
111

  /*!
112
  * \brief Prediction on one record
Guolin Ke's avatar
Guolin Ke committed
113
114
115
  * \param feature_values Feature value of this record
  * \return Prediction result
  */
116
  inline double Predict(const double* feature_values) const;
117
  inline double PredictByMap(const std::unordered_map<int, double>& feature_values) const;
118

119
  inline int PredictLeafIndex(const double* feature_values) const;
120
121
  inline int PredictLeafIndexByMap(const std::unordered_map<int, double>& feature_values) const;

Guolin Ke's avatar
Guolin Ke committed
122

123
  inline void PredictContrib(const double* feature_values, int num_features, double* output);
124

Guolin Ke's avatar
Guolin Ke committed
125
126
127
  /*! \brief Get Number of leaves*/
  inline int num_leaves() const { return num_leaves_; }

Guolin Ke's avatar
Guolin Ke committed
128
129
130
  /*! \brief Get depth of specific leaf*/
  inline int leaf_depth(int leaf_idx) const { return leaf_depth_[leaf_idx]; }

wxchan's avatar
wxchan committed
131
  /*! \brief Get feature of specific split*/
Guolin Ke's avatar
Guolin Ke committed
132
  inline int split_feature(int split_idx) const { return split_feature_[split_idx]; }
wxchan's avatar
wxchan committed
133

Guolin Ke's avatar
Guolin Ke committed
134
135
  inline double split_gain(int split_idx) const { return split_gain_[split_idx]; }

136
  /*! \brief Get the number of data points that fall at or below this node*/
Guolin Ke's avatar
Guolin Ke committed
137
  inline int data_count(int node) const { return node >= 0 ? internal_count_[node] : leaf_count_[~node]; }
138

Guolin Ke's avatar
Guolin Ke committed
139
140
  /*!
  * \brief Shrinkage for the tree's output
Qiwei Ye's avatar
Qiwei Ye committed
141
  *        shrinkage rate (a.k.a learning rate) is used to tune the traning process
Guolin Ke's avatar
Guolin Ke committed
142
143
  * \param rate The factor of shrinkage
  */
144
  inline void Shrinkage(double rate) {
145
    #pragma omp parallel for schedule(static, 1024) if (num_leaves_ >= 2048)
Guolin Ke's avatar
Guolin Ke committed
146
    for (int i = 0; i < num_leaves_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
147
      leaf_value_[i] *= rate;
Guolin Ke's avatar
Guolin Ke committed
148
    }
Guolin Ke's avatar
Guolin Ke committed
149
    shrinkage_ *= rate;
Guolin Ke's avatar
Guolin Ke committed
150
151
  }

152
153
154
155
  inline double shrinkage() const {
    return shrinkage_;
  }

Guolin Ke's avatar
Guolin Ke committed
156
157
158
159
160
161
162
163
164
  inline void AddBias(double val) {
    #pragma omp parallel for schedule(static, 1024) if (num_leaves_ >= 2048)
    for (int i = 0; i < num_leaves_; ++i) {
      leaf_value_[i] = val + leaf_value_[i];
    }
    // force to 1.0
    shrinkage_ = 1.0f;
  }

165
166
167
168
169
170
  inline void AsConstantTree(double val) {
    num_leaves_ = 1;
    shrinkage_ = 1.0f;
    leaf_value_[0] = val;
  }

wxchan's avatar
wxchan committed
171
  /*! \brief Serialize this object to string*/
Guolin Ke's avatar
Guolin Ke committed
172
  std::string ToString() const;
Guolin Ke's avatar
Guolin Ke committed
173

wxchan's avatar
wxchan committed
174
  /*! \brief Serialize this object to json*/
Guolin Ke's avatar
Guolin Ke committed
175
  std::string ToJSON() const;
wxchan's avatar
wxchan committed
176

177
  /*! \brief Serialize this object to if-else statement*/
Guolin Ke's avatar
Guolin Ke committed
178
  std::string ToIfElse(int index, bool predict_leaf_index) const;
179

Guolin Ke's avatar
Guolin Ke committed
180
  inline static bool IsZero(double fval) {
Guolin Ke's avatar
Guolin Ke committed
181
    if (fval > -kZeroThreshold && fval <= kZeroThreshold) {
Guolin Ke's avatar
Guolin Ke committed
182
      return true;
Guolin Ke's avatar
Guolin Ke committed
183
    } else {
Guolin Ke's avatar
Guolin Ke committed
184
      return false;
Guolin Ke's avatar
Guolin Ke committed
185
186
187
    }
  }

Guolin Ke's avatar
Guolin Ke committed
188
189
190
191
192
193
194
  inline static bool GetDecisionType(int8_t decision_type, int8_t mask) {
    return (decision_type & mask) > 0;
  }

  inline static void SetDecisionType(int8_t* decision_type, bool input, int8_t mask) {
    if (input) {
      (*decision_type) |= mask;
Guolin Ke's avatar
Guolin Ke committed
195
    } else {
Guolin Ke's avatar
Guolin Ke committed
196
      (*decision_type) &= (127 - mask);
Guolin Ke's avatar
Guolin Ke committed
197
198
199
    }
  }

Guolin Ke's avatar
Guolin Ke committed
200
201
202
203
204
205
206
207
208
  inline static int8_t GetMissingType(int8_t decision_type) {
    return (decision_type >> 2) & 3;
  }

  inline static void SetMissingType(int8_t* decision_type, int8_t input) {
    (*decision_type) &= 3;
    (*decision_type) |= (input << 2);
  }

209
210
  void RecomputeMaxDepth();

Nikita Titov's avatar
Nikita Titov committed
211
 private:
Guolin Ke's avatar
Guolin Ke committed
212
  std::string NumericalDecisionIfElse(int node) const;
Guolin Ke's avatar
Guolin Ke committed
213

Guolin Ke's avatar
Guolin Ke committed
214
  std::string CategoricalDecisionIfElse(int node) const;
215
216
217

  inline int NumericalDecision(double fval, int node) const {
    uint8_t missing_type = GetMissingType(decision_type_[node]);
Guolin Ke's avatar
Guolin Ke committed
218
219
220
221
222
223
224
    if (std::isnan(fval)) {
      if (missing_type != 2) {
        fval = 0.0f;
      }
    }
    if ((missing_type == 1 && IsZero(fval))
        || (missing_type == 2 && std::isnan(fval))) {
225
226
      if (GetDecisionType(decision_type_[node], kDefaultLeftMask)) {
        return left_child_[node];
Guolin Ke's avatar
Guolin Ke committed
227
      } else {
228
        return right_child_[node];
Guolin Ke's avatar
Guolin Ke committed
229
230
      }
    }
231
232
233
234
235
    if (fval <= threshold_[node]) {
      return left_child_[node];
    } else {
      return right_child_[node];
    }
Guolin Ke's avatar
Guolin Ke committed
236
  }
Guolin Ke's avatar
Guolin Ke committed
237

238
239
240
241
242
243
244
245
246
247
248
249
  inline int NumericalDecisionInner(uint32_t fval, int node, uint32_t default_bin, uint32_t max_bin) const {
    uint8_t missing_type = GetMissingType(decision_type_[node]);
    if ((missing_type == 1 && fval == default_bin)
        || (missing_type == 2 && fval == max_bin)) {
      if (GetDecisionType(decision_type_[node], kDefaultLeftMask)) {
        return left_child_[node];
      } else {
        return right_child_[node];
      }
    }
    if (fval <= threshold_in_bin_[node]) {
      return left_child_[node];
250
    } else {
251
      return right_child_[node];
252
253
    }
  }
Guolin Ke's avatar
Guolin Ke committed
254

255
256
257
258
259
260
261
262
263
264
265
266
  inline int CategoricalDecision(double fval, int node) const {
    uint8_t missing_type = GetMissingType(decision_type_[node]);
    int int_fval = static_cast<int>(fval);
    if (int_fval < 0) {
      return right_child_[node];;
    } else if (std::isnan(fval)) {
      // NaN is always in the right
      if (missing_type == 2) {
        return right_child_[node];
      }
      int_fval = 0;
    }
267
    int cat_idx = static_cast<int>(threshold_[node]);
268
269
    if (Common::FindInBitset(cat_threshold_.data() + cat_boundaries_[cat_idx],
                             cat_boundaries_[cat_idx + 1] - cat_boundaries_[cat_idx], int_fval)) {
270
271
272
273
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
274

275
  inline int CategoricalDecisionInner(uint32_t fval, int node) const {
276
    int cat_idx = static_cast<int>(threshold_in_bin_[node]);
277
278
    if (Common::FindInBitset(cat_threshold_inner_.data() + cat_boundaries_inner_[cat_idx],
                             cat_boundaries_inner_[cat_idx + 1] - cat_boundaries_inner_[cat_idx], fval)) {
279
280
281
282
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
283

284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
  inline int Decision(double fval, int node) const {
    if (GetDecisionType(decision_type_[node], kCategoricalMask)) {
      return CategoricalDecision(fval, node);
    } else {
      return NumericalDecision(fval, node);
    }
  }

  inline int DecisionInner(uint32_t fval, int node, uint32_t default_bin, uint32_t max_bin) const {
    if (GetDecisionType(decision_type_[node], kCategoricalMask)) {
      return CategoricalDecisionInner(fval, node);
    } else {
      return NumericalDecisionInner(fval, node, default_bin, max_bin);
    }
  }

  inline void Split(int leaf, int feature, int real_feature,
301
                    double left_value, double right_value, int left_cnt, int right_cnt, float gain);
Guolin Ke's avatar
Guolin Ke committed
302
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
303
  * \brief Find leaf index of which record belongs by features
Guolin Ke's avatar
Guolin Ke committed
304
305
306
  * \param feature_values Feature value of this record
  * \return Leaf index
  */
307
  inline int GetLeaf(const double* feature_values) const;
308
  inline int GetLeafByMap(const std::unordered_map<int, double>& feature_values) const;
Guolin Ke's avatar
Guolin Ke committed
309

wxchan's avatar
wxchan committed
310
  /*! \brief Serialize one node to json*/
Guolin Ke's avatar
Guolin Ke committed
311
  std::string NodeToJSON(int index) const;
wxchan's avatar
wxchan committed
312

313
  /*! \brief Serialize one node to if-else statement*/
Guolin Ke's avatar
Guolin Ke committed
314
  std::string NodeToIfElse(int index, bool predict_leaf_index) const;
Guolin Ke's avatar
Guolin Ke committed
315

Guolin Ke's avatar
Guolin Ke committed
316
  std::string NodeToIfElseByMap(int index, bool predict_leaf_index) const;
317

318
  double ExpectedValue() const;
Guolin Ke's avatar
Guolin Ke committed
319

320
321
  /*! \brief This is used fill in leaf_depth_ after reloading a model*/
  inline void RecomputeLeafDepths(int node = 0, int depth = 0);
Guolin Ke's avatar
Guolin Ke committed
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338

  /*!
  * \brief Used by TreeSHAP for data we keep about our decision path
  */
  struct PathElement {
    int feature_index;
    double zero_fraction;
    double one_fraction;

    // note that pweight is included for convenience and is not tied with the other attributes,
    // the pweight of the i'th path element is the permuation weight of paths with i-1 ones in them
    double pweight;

    PathElement() {}
    PathElement(int i, double z, double o, double w) : feature_index(i), zero_fraction(z), one_fraction(o), pweight(w) {}
  };

339
  /*! \brief Polynomial time algorithm for SHAP values (arXiv:1706.06060)*/
Guolin Ke's avatar
Guolin Ke committed
340
341
342
343
  void TreeSHAP(const double *feature_values, double *phi,
                int node, int unique_depth,
                PathElement *parent_unique_path, double parent_zero_fraction,
                double parent_one_fraction, int parent_feature_index) const;
344

345
  /*! \brief Extend our decision path with a fraction of one and zero extensions for TreeSHAP*/
Guolin Ke's avatar
Guolin Ke committed
346
347
  static void ExtendPath(PathElement *unique_path, int unique_depth,
                         double zero_fraction, double one_fraction, int feature_index);
348
349

  /*! \brief Undo a previous extension of the decision path for TreeSHAP*/
Guolin Ke's avatar
Guolin Ke committed
350
  static void UnwindPath(PathElement *unique_path, int unique_depth, int path_index);
351
352

  /*! determine what the total permuation weight would be if we unwound a previous extension in the decision path*/
Guolin Ke's avatar
Guolin Ke committed
353
  static double UnwoundPathSum(const PathElement *unique_path, int unique_depth, int path_index);
354

Guolin Ke's avatar
Guolin Ke committed
355
356
357
358
359
360
  /*! \brief Number of max leaves*/
  int max_leaves_;
  /*! \brief Number of current levas*/
  int num_leaves_;
  // following values used for non-leaf node
  /*! \brief A non-leaf node's left child */
Guolin Ke's avatar
Guolin Ke committed
361
  std::vector<int> left_child_;
Guolin Ke's avatar
Guolin Ke committed
362
  /*! \brief A non-leaf node's right child */
Guolin Ke's avatar
Guolin Ke committed
363
  std::vector<int> right_child_;
Guolin Ke's avatar
Guolin Ke committed
364
  /*! \brief A non-leaf node's split feature */
Guolin Ke's avatar
Guolin Ke committed
365
  std::vector<int> split_feature_inner_;
Guolin Ke's avatar
Guolin Ke committed
366
  /*! \brief A non-leaf node's split feature, the original index */
Guolin Ke's avatar
Guolin Ke committed
367
  std::vector<int> split_feature_;
Guolin Ke's avatar
Guolin Ke committed
368
  /*! \brief A non-leaf node's split threshold in bin */
Guolin Ke's avatar
Guolin Ke committed
369
  std::vector<uint32_t> threshold_in_bin_;
Guolin Ke's avatar
Guolin Ke committed
370
  /*! \brief A non-leaf node's split threshold in feature value */
Guolin Ke's avatar
Guolin Ke committed
371
  std::vector<double> threshold_;
372
  int num_cat_;
373
374
375
376
  std::vector<int> cat_boundaries_inner_;
  std::vector<uint32_t> cat_threshold_inner_;
  std::vector<int> cat_boundaries_;
  std::vector<uint32_t> cat_threshold_;
Guolin Ke's avatar
Guolin Ke committed
377
  /*! \brief Store the information for categorical feature handle and mising value handle. */
378
  std::vector<int8_t> decision_type_;
Guolin Ke's avatar
Guolin Ke committed
379
  /*! \brief A non-leaf node's split gain */
380
  std::vector<float> split_gain_;
Guolin Ke's avatar
Guolin Ke committed
381
382
  // used for leaf node
  /*! \brief The parent of leaf */
Guolin Ke's avatar
Guolin Ke committed
383
  std::vector<int> leaf_parent_;
Guolin Ke's avatar
Guolin Ke committed
384
  /*! \brief Output of leaves */
Guolin Ke's avatar
Guolin Ke committed
385
  std::vector<double> leaf_value_;
Guolin Ke's avatar
Guolin Ke committed
386
  /*! \brief DataCount of leaves */
387
  std::vector<int> leaf_count_;
Guolin Ke's avatar
Guolin Ke committed
388
389
390
  /*! \brief Output of non-leaf nodes */
  std::vector<double> internal_value_;
  /*! \brief DataCount of non-leaf nodes */
391
  std::vector<int> internal_count_;
Guolin Ke's avatar
Guolin Ke committed
392
  /*! \brief Depth for leaves */
Guolin Ke's avatar
Guolin Ke committed
393
  std::vector<int> leaf_depth_;
Guolin Ke's avatar
Guolin Ke committed
394
  double shrinkage_;
395
  int max_depth_;
Guolin Ke's avatar
Guolin Ke committed
396
397
};

398
inline void Tree::Split(int leaf, int feature, int real_feature,
399
                        double left_value, double right_value, int left_cnt, int right_cnt, float gain) {
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
  int new_node_idx = num_leaves_ - 1;
  // update parent info
  int parent = leaf_parent_[leaf];
  if (parent >= 0) {
    // if cur node is left child
    if (left_child_[parent] == ~leaf) {
      left_child_[parent] = new_node_idx;
    } else {
      right_child_[parent] = new_node_idx;
    }
  }
  // add new node
  split_feature_inner_[new_node_idx] = feature;
  split_feature_[new_node_idx] = real_feature;

  split_gain_[new_node_idx] = Common::AvoidInf(gain);
  // add two new leaves
  left_child_[new_node_idx] = ~leaf;
  right_child_[new_node_idx] = ~num_leaves_;
  // update new leaves
  leaf_parent_[leaf] = new_node_idx;
  leaf_parent_[num_leaves_] = new_node_idx;
  // save current leaf value to internal node before change
  internal_value_[new_node_idx] = leaf_value_[leaf];
  internal_count_[new_node_idx] = left_cnt + right_cnt;
  leaf_value_[leaf] = std::isnan(left_value) ? 0.0f : left_value;
  leaf_count_[leaf] = left_cnt;
  leaf_value_[num_leaves_] = std::isnan(right_value) ? 0.0f : right_value;
  leaf_count_[num_leaves_] = right_cnt;
  // update leaf depth
  leaf_depth_[num_leaves_] = leaf_depth_[leaf] + 1;
  leaf_depth_[leaf]++;
}

434
inline double Tree::Predict(const double* feature_values) const {
Guolin Ke's avatar
Guolin Ke committed
435
436
437
438
  if (num_leaves_ > 1) {
    int leaf = GetLeaf(feature_values);
    return LeafOutput(leaf);
  } else {
439
    return leaf_value_[0];
Guolin Ke's avatar
Guolin Ke committed
440
  }
Guolin Ke's avatar
Guolin Ke committed
441
442
}

443
444
445
446
447
448
449
450
451
inline double Tree::PredictByMap(const std::unordered_map<int, double>& feature_values) const {
  if (num_leaves_ > 1) {
    int leaf = GetLeafByMap(feature_values);
    return LeafOutput(leaf);
  } else {
    return leaf_value_[0];
  }
}

452
inline int Tree::PredictLeafIndex(const double* feature_values) const {
Guolin Ke's avatar
Guolin Ke committed
453
454
455
456
457
458
  if (num_leaves_ > 1) {
    int leaf = GetLeaf(feature_values);
    return leaf;
  } else {
    return 0;
  }
wxchan's avatar
wxchan committed
459
460
}

461
462
463
464
465
466
467
468
469
inline int Tree::PredictLeafIndexByMap(const std::unordered_map<int, double>& feature_values) const {
  if (num_leaves_ > 1) {
    int leaf = GetLeafByMap(feature_values);
    return leaf;
  } else {
    return 0;
  }
}

470
471
inline void Tree::PredictContrib(const double* feature_values, int num_features, double* output) {
  output[num_features] += ExpectedValue();
472
  // Run the recursion with preallocated space for the unique path data
473
  if (num_leaves_ > 1) {
474
475
476
477
    CHECK(max_depth_ >= 0);
    const int max_path_len = max_depth_ + 1;
    std::vector<PathElement> unique_path_data(max_path_len*(max_path_len + 1) / 2);
    TreeSHAP(feature_values, output, 0, 0, unique_path_data.data(), 1, 1, -1);
478
479
480
481
482
483
484
485
  }
}

inline void Tree::RecomputeLeafDepths(int node, int depth) {
  if (node == 0) leaf_depth_.resize(num_leaves());
  if (node < 0) {
    leaf_depth_[~node] = depth;
  } else {
Guolin Ke's avatar
Guolin Ke committed
486
487
    RecomputeLeafDepths(left_child_[node], depth + 1);
    RecomputeLeafDepths(right_child_[node], depth + 1);
488
  }
489
490
}

491
inline int Tree::GetLeaf(const double* feature_values) const {
Guolin Ke's avatar
Guolin Ke committed
492
  int node = 0;
493
  if (num_cat_ > 0) {
Guolin Ke's avatar
Guolin Ke committed
494
    while (node >= 0) {
495
      node = Decision(feature_values[split_feature_[node]], node);
Guolin Ke's avatar
Guolin Ke committed
496
497
498
    }
  } else {
    while (node >= 0) {
499
      node = NumericalDecision(feature_values[split_feature_[node]], node);
Guolin Ke's avatar
Guolin Ke committed
500
501
502
503
504
    }
  }
  return ~node;
}

505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
inline int Tree::GetLeafByMap(const std::unordered_map<int, double>& feature_values) const {
  int node = 0;
  if (num_cat_ > 0) {
    while (node >= 0) {
      node = Decision(feature_values.count(split_feature_[node]) > 0 ? feature_values.at(split_feature_[node]) : 0.0f, node);
    }
  } else {
    while (node >= 0) {
      node = NumericalDecision(feature_values.count(split_feature_[node]) > 0 ? feature_values.at(split_feature_[node]) : 0.0f, node);
    }
  }
  return ~node;
}


Guolin Ke's avatar
Guolin Ke committed
520
521
}  // namespace LightGBM

Guolin Ke's avatar
Guolin Ke committed
522
#endif   // LightGBM_TREE_H_