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

#include <LightGBM/meta.h>
#include <LightGBM/dataset.h>
wxchan's avatar
wxchan committed
6
7
8
#ifdef USE_PROTO
#include "model.pb.h"
#endif // USE_PROTO
Guolin Ke's avatar
Guolin Ke committed
9
10
11

#include <string>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
12
#include <memory>
Guolin Ke's avatar
Guolin Ke committed
13
14
15

namespace LightGBM {

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

/*!
* \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
  */
  explicit Tree(const std::string& str);
wxchan's avatar
wxchan committed
36
37
38
39
40
41
42
  #ifdef USE_PROTO
  /*!
  * \brief Construtor, from a protobuf object
  * \param model_tree Model protobuf object
  */
  explicit Tree(const Model_Tree& model_tree);
  #endif // USE_PROTO
Guolin Ke's avatar
Guolin Ke committed
43
44
45
46

  ~Tree();

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

66
67
68
69
70
71
72
  /*!
  * \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
73
74
  * \param threshold Thresholds of real feature value, use bitset to represent
  * \param num_threshold size of threshold
75
76
77
78
79
80
81
  * \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.
  */
82
83
  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,
84
85
                       data_size_t left_cnt, data_size_t right_cnt, double gain, MissingType missing_type);

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

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

  /*!
Qiwei Ye's avatar
Qiwei Ye committed
105
  * \brief Adding prediction value of this tree model to scorese
Guolin Ke's avatar
Guolin Ke committed
106
107
108
109
110
111
  * \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
112
                            const data_size_t* used_data_indices,
113
                            data_size_t num_data, double* score) const;
Guolin Ke's avatar
Guolin Ke committed
114
115

  /*!
116
  * \brief Prediction on one record
Guolin Ke's avatar
Guolin Ke committed
117
118
119
  * \param feature_values Feature value of this record
  * \return Prediction result
  */
120
  inline double Predict(const double* feature_values) const;
121

122
  inline int PredictLeafIndex(const double* feature_values) const;
Guolin Ke's avatar
Guolin Ke committed
123

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

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

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

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

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

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

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

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

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

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

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

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

wxchan's avatar
wxchan committed
178
179
180
181
182
  #ifdef USE_PROTO
  /*! \brief Serialize this object to protobuf object*/
  void ToProto(Model_Tree& model_tree) const;
  #endif // USE_PROTO

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

Guolin Ke's avatar
Guolin Ke committed
191
192
193
194
195
196
197
  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
198
    } else {
Guolin Ke's avatar
Guolin Ke committed
199
      (*decision_type) &= (127 - mask);
Guolin Ke's avatar
Guolin Ke committed
200
201
202
    }
  }

Guolin Ke's avatar
Guolin Ke committed
203
204
205
206
207
208
209
210
211
  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);
  }

212
213
private:

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

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

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

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

257
258
259
260
261
262
263
264
265
266
267
268
  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;
    }
269
270
271
    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)) {
272
273
274
275
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
276

277
  inline int CategoricalDecisionInner(uint32_t fval, int node) const {
278
279
280
    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)) {
281
282
283
284
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
285

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

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

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

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

319
320
321
322
  int MaxDepth();

  /*! \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
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

  /*!
  * \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;
345

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

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

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

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

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
432
433
inline void Tree::Split(int leaf, int feature, int real_feature,
                        double left_value, double right_value, data_size_t left_cnt, data_size_t right_cnt, double gain) {
  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
inline int Tree::PredictLeafIndex(const double* feature_values) const {
Guolin Ke's avatar
Guolin Ke committed
444
445
446
447
448
449
  if (num_leaves_ > 1) {
    int leaf = GetLeaf(feature_values);
    return leaf;
  } else {
    return 0;
  }
wxchan's avatar
wxchan committed
450
451
}

452
453
inline void Tree::PredictContrib(const double* feature_values, int num_features, double* output) {
  output[num_features] += ExpectedValue();
454
  // Run the recursion with preallocated space for the unique path data
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
  if (num_leaves_ > 1) {
    const int max_path_len = MaxDepth()+1;
    PathElement *unique_path_data = new PathElement[(max_path_len*(max_path_len+1))/2];
    TreeSHAP(feature_values, output, 0, 0, unique_path_data, 1, 1, -1);
    delete[] unique_path_data;
  }
}

inline void Tree::RecomputeLeafDepths(int node, int depth) {
  if (node == 0) leaf_depth_.resize(num_leaves());
  if (node < 0) {
    leaf_depth_[~node] = depth;
  } else {
    RecomputeLeafDepths(left_child_[node], depth+1);
    RecomputeLeafDepths(right_child_[node], depth+1);
  }
471
472
}

473
inline int Tree::GetLeaf(const double* feature_values) const {
Guolin Ke's avatar
Guolin Ke committed
474
  int node = 0;
475
  if (num_cat_ > 0) {
Guolin Ke's avatar
Guolin Ke committed
476
    while (node >= 0) {
477
      node = Decision(feature_values[split_feature_[node]], node);
Guolin Ke's avatar
Guolin Ke committed
478
479
480
    }
  } else {
    while (node >= 0) {
481
      node = NumericalDecision(feature_values[split_feature_[node]], node);
Guolin Ke's avatar
Guolin Ke committed
482
483
484
485
486
487
488
    }
  }
  return ~node;
}

}  // namespace LightGBM

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