tree.h 17.3 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
5
6
7
8
#ifndef LIGHTGBM_TREE_H_
#define LIGHTGBM_TREE_H_

#include <LightGBM/meta.h>
#include <LightGBM/dataset.h>

#include <string>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
9
#include <memory>
10
#include <map>
Guolin Ke's avatar
Guolin Ke committed
11
12
13

namespace LightGBM {

14
#define kMaxTreeOutput (100)
Guolin Ke's avatar
Guolin Ke committed
15
16
#define kCategoricalMask (1)
#define kDefaultLeftMask (2)
Guolin Ke's avatar
Guolin Ke committed
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/*!
* \brief Tree model
*/
class Tree {
public:
  /*!
  * \brief Constructor
  * \param max_leaves The number of max leaves
  */
  explicit Tree(int max_leaves);

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

  ~Tree();

  /*!
Qiwei Ye's avatar
Qiwei Ye committed
39
40
41
  * \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
42
  * \param real_feature Index of feature, the original index on data
43
  * \param threshold_bin Threshold(bin) of split
44
  * \param threshold_double Threshold on feature value
Guolin Ke's avatar
Guolin Ke committed
45
46
  * \param left_value Model Left child output
  * \param right_value Model Right child output
Guolin Ke's avatar
Guolin Ke committed
47
48
  * \param left_cnt Count of left child
  * \param right_cnt Count of right child
Guolin Ke's avatar
Guolin Ke committed
49
  * \param gain Split gain
Guolin Ke's avatar
Guolin Ke committed
50
51
  * \param missing_type missing type
  * \param default_left default direction for missing value
Guolin Ke's avatar
Guolin Ke committed
52
53
  * \return The index of new leaf.
  */
54
55
  int Split(int leaf, int feature, int real_feature, uint32_t threshold_bin,
            double threshold_double, double left_value, double right_value,
56
            int left_cnt, int right_cnt, float gain, MissingType missing_type, bool default_left);
Guolin Ke's avatar
Guolin Ke committed
57

58
59
60
61
62
63
64
  /*!
  * \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
65
66
  * \param threshold Thresholds of real feature value, use bitset to represent
  * \param num_threshold size of threshold
67
68
69
70
71
72
73
  * \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.
  */
74
75
  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,
76
                       int left_cnt, int right_cnt, float gain, MissingType missing_type);
77

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

Guolin Ke's avatar
Guolin Ke committed
81
82
83
84
85
  /*! \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
86
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
87
  * \brief Adding prediction value of this tree model to scores
Guolin Ke's avatar
Guolin Ke committed
88
89
90
91
  * \param data The dataset
  * \param num_data Number of total data
  * \param score Will add prediction to score
  */
92
93
94
  void AddPredictionToScore(const Dataset* data,
                            data_size_t num_data,
                            double* score) const;
Guolin Ke's avatar
Guolin Ke committed
95
96

  /*!
Qiwei Ye's avatar
Qiwei Ye committed
97
  * \brief Adding prediction value of this tree model to scorese
Guolin Ke's avatar
Guolin Ke committed
98
99
100
101
102
103
  * \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
104
                            const data_size_t* used_data_indices,
105
                            data_size_t num_data, double* score) const;
Guolin Ke's avatar
Guolin Ke committed
106
107

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

115
  inline int PredictLeafIndex(const double* feature_values) const;
116
117
  inline int PredictLeafIndexByMap(const std::unordered_map<int, double>& feature_values) const;

Guolin Ke's avatar
Guolin Ke committed
118

119
  inline void PredictContrib(const double* feature_values, int num_features, double* output);
120

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

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

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

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

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

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

149
150
151
152
  inline double shrinkage() const {
    return shrinkage_;
  }

Guolin Ke's avatar
Guolin Ke committed
153
154
155
156
157
158
159
160
161
  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;
  }

162
163
164
165
166
167
  inline void AsConstantTree(double val) {
    num_leaves_ = 1;
    shrinkage_ = 1.0f;
    leaf_value_[0] = val;
  }

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

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

174
  /*! \brief Serialize this object to if-else statement*/
Guolin Ke's avatar
Guolin Ke committed
175
  std::string ToIfElse(int index, bool is_predict_leaf_index) const;
176

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

Guolin Ke's avatar
Guolin Ke committed
185
186
187
188
189
190
191
  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
192
    } else {
Guolin Ke's avatar
Guolin Ke committed
193
      (*decision_type) &= (127 - mask);
Guolin Ke's avatar
Guolin Ke committed
194
195
196
    }
  }

Guolin Ke's avatar
Guolin Ke committed
197
198
199
200
201
202
203
204
205
  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);
  }

206
207
  void RecomputeMaxDepth();

208
209
private:

Guolin Ke's avatar
Guolin Ke committed
210
  std::string NumericalDecisionIfElse(int node) const;
Guolin Ke's avatar
Guolin Ke committed
211

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

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

236
237
238
239
240
241
242
243
244
245
246
247
  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];
248
    } else {
249
      return right_child_[node];
250
251
    }
  }
Guolin Ke's avatar
Guolin Ke committed
252

253
254
255
256
257
258
259
260
261
262
263
264
  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;
    }
265
266
267
    int cat_idx = int(threshold_[node]);
    if (Common::FindInBitset(cat_threshold_.data() + cat_boundaries_[cat_idx],
                             cat_boundaries_[cat_idx + 1] - cat_boundaries_[cat_idx], int_fval)) {
268
269
270
271
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
272

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

282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
  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,
299
                    double left_value, double right_value, int left_cnt, int right_cnt, float gain);
Guolin Ke's avatar
Guolin Ke committed
300
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
301
  * \brief Find leaf index of which record belongs by features
Guolin Ke's avatar
Guolin Ke committed
302
303
304
  * \param feature_values Feature value of this record
  * \return Leaf index
  */
305
  inline int GetLeaf(const double* feature_values) const;
306
  inline int GetLeafByMap(const std::unordered_map<int, double>& feature_values) const;
Guolin Ke's avatar
Guolin Ke committed
307

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

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

314
315
  std::string NodeToIfElseByMap(int index, bool is_predict_leaf_index) const;

316
  double ExpectedValue() const;
Guolin Ke's avatar
Guolin Ke committed
317

318
319
  /*! \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
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341

  /*!
  * \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) {}
  };

  /*! \brief Polynomial time algorithm for SHAP values (https://arxiv.org/abs/1706.06060) */
  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;
342

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

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

  /*! 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
351
  static double UnwoundPathSum(const PathElement *unique_path, int unique_depth, int path_index);
352

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

396
inline void Tree::Split(int leaf, int feature, int real_feature,
397
                        double left_value, double right_value, int left_cnt, int right_cnt, float gain) {
398
399
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
  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]++;
}

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

441
442
443
444
445
446
447
448
449
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];
  }
}

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

459
460
461
462
463
464
465
466
467
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;
  }
}

468
469
inline void Tree::PredictContrib(const double* feature_values, int num_features, double* output) {
  output[num_features] += ExpectedValue();
470
  // Run the recursion with preallocated space for the unique path data
471
  if (num_leaves_ > 1) {
472
473
474
475
    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);
476
477
478
479
480
481
482
483
  }
}

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
484
485
    RecomputeLeafDepths(left_child_[node], depth + 1);
    RecomputeLeafDepths(right_child_[node], depth + 1);
486
  }
487
488
}

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

503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
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
518
519
}  // namespace LightGBM

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