tree.h 16.3 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
#include "model.pb.h"
Guolin Ke's avatar
Guolin Ke committed
7
8
9

#include <string>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
10
#include <memory>
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
32
33
34

/*!
* \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
35
36
37
38
39
40
  /*!
  * \brief Construtor, from a protobuf object
  * \param model_tree Model protobuf object
  */
  explicit Tree(const LightGBM::Model_Tree& model_tree);

Guolin Ke's avatar
Guolin Ke committed
41
42
43
  ~Tree();

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

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

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

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

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

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

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

121
  inline void PredictContrib(const double* feature_values, int num_features, double* output);
122

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

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

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

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

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

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

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

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

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

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

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

wxchan's avatar
wxchan committed
175
176
177
  /*! \brief Serialize this object to protobuf object*/
  void ToProto(Model_Tree& model_tree) const;

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

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

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

207
208
private:

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

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

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

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

252
253
254
255
256
257
258
259
260
261
262
263
  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;
    }
264
265
266
    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)) {
267
268
269
270
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
271

272
  inline int CategoricalDecisionInner(uint32_t fval, int node) const {
273
274
275
    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)) {
276
277
278
279
      return left_child_[node];
    }
    return right_child_[node];
  }
Guolin Ke's avatar
Guolin Ke committed
280

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,
                    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
299
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
300
  * \brief Find leaf index of which record belongs by features
Guolin Ke's avatar
Guolin Ke committed
301
302
303
  * \param feature_values Feature value of this record
  * \return Leaf index
  */
304
  inline int GetLeaf(const double* feature_values) const;
Guolin Ke's avatar
Guolin Ke committed
305

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

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

312
  double ExpectedValue() const;
Guolin Ke's avatar
Guolin Ke committed
313

314
315
316
317
  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
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339

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

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

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

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

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

393
394
395
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
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]++;
}

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

438
inline int Tree::PredictLeafIndex(const double* feature_values) const {
Guolin Ke's avatar
Guolin Ke committed
439
440
441
442
443
444
  if (num_leaves_ > 1) {
    int leaf = GetLeaf(feature_values);
    return leaf;
  } else {
    return 0;
  }
wxchan's avatar
wxchan committed
445
446
}

447
448
inline void Tree::PredictContrib(const double* feature_values, int num_features, double* output) {
  output[num_features] += ExpectedValue();
449
  // Run the recursion with preallocated space for the unique path data
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
  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);
  }
466
467
}

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

}  // namespace LightGBM

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