bin.h 19.7 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
#ifndef LIGHTGBM_BIN_H_
#define LIGHTGBM_BIN_H_

Guolin Ke's avatar
Guolin Ke committed
8
#include <LightGBM/meta.h>
9
#include <LightGBM/utils/common.h>
Guolin Ke's avatar
Guolin Ke committed
10
#include <LightGBM/utils/file_io.h>
11

12
13
#include <limits>
#include <string>
Guolin Ke's avatar
Guolin Ke committed
14
#include <functional>
15
#include <sstream>
16
17
#include <unordered_map>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
18
19
20

namespace LightGBM {

21
22
23
24
25
26
27
28
29
30
31
enum BinType {
  NumericalBin,
  CategoricalBin
};

enum MissingType {
  None,
  Zero,
  NaN
};

32
typedef double hist_t;
Guolin Ke's avatar
Guolin Ke committed
33
34
35
typedef uint64_t hist_cnt_t;
// check at compile time
static_assert(sizeof(hist_t) == sizeof(hist_cnt_t), "Histogram entry size is not correct");
36

37
38
const size_t kHistEntrySize = 2 * sizeof(hist_t);
const int kHistOffset = 2;
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const double kSparseThreshold = 0.7;

#define GET_GRAD(hist, i) hist[(i) << 1]
#define GET_HESS(hist, i) hist[((i) << 1) + 1]

inline static void HistogramSumReducer(const char* src, char* dst, int type_size, comm_size_t len) {
  comm_size_t used_size = 0;
  const hist_t* p1;
  hist_t* p2;
  while (used_size < len) {
    // convert
    p1 = reinterpret_cast<const hist_t*>(src);
    p2 = reinterpret_cast<hist_t*>(dst);
    *p2 += *p1;
    src += type_size;
    dst += type_size;
    used_size += type_size;
56
  }
57
}
58
59
60
61

/*! \brief This class used to convert feature values into bin,
*          and store some meta information for bin*/
class BinMapper {
Nikita Titov's avatar
Nikita Titov committed
62
 public:
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
  BinMapper();
  BinMapper(const BinMapper& other);
  explicit BinMapper(const void* memory);
  ~BinMapper();

  bool CheckAlign(const BinMapper& other) const {
    if (num_bin_ != other.num_bin_) {
      return false;
    }
    if (missing_type_ != other.missing_type_) {
      return false;
    }
    if (bin_type_ == BinType::NumericalBin) {
      for (int i = 0; i < num_bin_; ++i) {
        if (bin_upper_bound_[i] != other.bin_upper_bound_[i]) {
          return false;
Guolin Ke's avatar
Guolin Ke committed
79
        }
80
81
82
83
84
      }
    } else {
      for (int i = 0; i < num_bin_; i++) {
        if (bin_2_categorical_[i] != other.bin_2_categorical_[i]) {
          return false;
85
        }
86
87
      }
    }
88
89
    return true;
  }
90

91
92
93
94
  /*! \brief Get number of bins */
  inline int num_bin() const { return num_bin_; }
  /*! \brief Missing Type */
  inline MissingType missing_type() const { return missing_type_; }
Lingyi Hu's avatar
Lingyi Hu committed
95
96
  /*! \brief True if bin is trivial (contains only one bin) */
  inline bool is_trivial() const { return is_trivial_; }
97
98
99
100
101
102
  /*! \brief Sparsity of this bin ( num_zero_bins / num_data ) */
  inline double sparse_rate() const { return sparse_rate_; }
  /*!
  * \brief Save binary data to file
  * \param file File want to write
  */
103
  void SaveBinaryToFile(const VirtualFileWriter* writer) const;
104
105
106
107
108
109
110
111
112
113
  /*!
  * \brief Mapping bin into feature value
  * \param bin
  * \return Feature value of this bin
  */
  inline double BinToValue(uint32_t bin) const {
    if (bin_type_ == BinType::NumericalBin) {
      return bin_upper_bound_[bin];
    } else {
      return bin_2_categorical_[bin];
Guolin Ke's avatar
Guolin Ke committed
114
    }
115
  }
Guolin Ke's avatar
Guolin Ke committed
116

117
118
119
120
121
  /*!
  * \brief Get sizes in byte of this object
  */
  size_t SizesInByte() const;
  /*!
122
  * \brief Mapping feature value into bin
123
124
125
126
127
128
129
130
131
132
133
134
  * \param value
  * \return bin for this feature value
  */
  inline uint32_t ValueToBin(double value) const;

  /*!
  * \brief Get the default bin when value is 0
  * \return default bin
  */
  inline uint32_t GetDefaultBin() const {
    return default_bin_;
  }
Guolin Ke's avatar
Guolin Ke committed
135
136
137
138
139

  inline uint32_t GetMostFreqBin() const {
    return most_freq_bin_;
  }

140
141
  /*!
  * \brief Construct feature value to bin mapper according feature values
142
  * \param values (Sampled) values of this feature, Note: not include zero.
143
144
145
146
147
  * \param num_values number of values.
  * \param total_sample_cnt number of total sample count, equal with values.size() + num_zeros
  * \param max_bin The maximal number of bin
  * \param min_data_in_bin min number of data in one bin
  * \param min_split_data
148
  * \param pre_filter
149
150
151
  * \param bin_type Type of this bin
  * \param use_missing True to enable missing value handle
  * \param zero_as_missing True to use zero as missing value
152
  * \param forced_upper_bounds Vector of split points that must be used (if this has size less than max_bin, remaining splits are found by the algorithm)
153
  */
154
  void FindBin(double* values, int num_values, size_t total_sample_cnt, int max_bin, int min_data_in_bin, int min_split_data, bool pre_filter, BinType bin_type,
155
               bool use_missing, bool zero_as_missing, const std::vector<double>& forced_upper_bounds);
156
157
158
159
160
161
162
163
164

  /*!
  * \brief Use specific number of bin to calculate the size of this class
  * \param bin The number of bin
  * \return Size
  */
  static int SizeForSpecificBin(int bin);

  /*!
165
  * \brief Serializing this object to buffer
166
167
168
169
170
  * \param buffer The destination
  */
  void CopyTo(char* buffer) const;

  /*!
171
  * \brief Deserializing this object from buffer
172
173
174
175
176
177
178
179
180
181
182
183
  * \param buffer The source
  */
  void CopyFrom(const char* buffer);

  /*!
  * \brief Get bin types
  */
  inline BinType bin_type() const { return bin_type_; }

  /*!
  * \brief Get bin info
  */
184
  inline std::string bin_info_string() const {
185
186
187
188
189
190
191
    if (bin_type_ == BinType::CategoricalBin) {
      return Common::Join(bin_2_categorical_, ":");
    } else {
      std::stringstream str_buf;
      str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
      str_buf << '[' << min_val_ << ':' << max_val_ << ']';
      return str_buf.str();
192
    }
193
  }
Guolin Ke's avatar
Guolin Ke committed
194

Nikita Titov's avatar
Nikita Titov committed
195
 private:
196
197
198
199
200
  /*! \brief Number of bins */
  int num_bin_;
  MissingType missing_type_;
  /*! \brief Store upper bound for each bin */
  std::vector<double> bin_upper_bound_;
Lingyi Hu's avatar
Lingyi Hu committed
201
202
  /*! \brief True if this feature is trivial */
  bool is_trivial_;
203
204
205
206
207
208
209
210
  /*! \brief Sparse rate of this bins( num_bin0/num_data ) */
  double sparse_rate_;
  /*! \brief Type of this bin */
  BinType bin_type_;
  /*! \brief Mapper from categorical to bin */
  std::unordered_map<int, unsigned int> categorical_2_bin_;
  /*! \brief Mapper from bin to categorical */
  std::vector<int> bin_2_categorical_;
211
  /*! \brief minimal feature value */
212
213
214
215
216
  double min_val_;
  /*! \brief maximum feature value */
  double max_val_;
  /*! \brief bin value of feature value 0 */
  uint32_t default_bin_;
Guolin Ke's avatar
Guolin Ke committed
217
218

  uint32_t most_freq_bin_;
219
220
221
222
223
224
};

/*!
* \brief Interface for ordered bin data. efficient for construct histogram, especially for sparse bin
*        There are 2 advantages by using ordered bin.
*        1. group the data by leafs to improve the cache hit.
225
*        2. only store the non-zero bin, which can speed up the histogram construction for sparse features.
226
227
228
229
*        However it brings additional cost: it need re-order the bins after every split, which will cost much for dense feature.
*        So we only using ordered bin for sparse situations.
*/
class OrderedBin {
Nikita Titov's avatar
Nikita Titov committed
230
 public:
231
232
  /*! \brief virtual destructor */
  virtual ~OrderedBin() {}
Guolin Ke's avatar
Guolin Ke committed
233
234

  /*!
235
236
237
238
  * \brief Initialization logic.
  * \param used_indices If used_indices.size() == 0 means using all data, otherwise, used_indices[i] == true means i-th data is used
           (this logic was build for bagging logic)
  * \param num_leaves Number of leaves on this iteration
Guolin Ke's avatar
Guolin Ke committed
239
  */
240
  virtual void Init(const char* used_indices, data_size_t num_leaves) = 0;
Guolin Ke's avatar
Guolin Ke committed
241
242

  /*!
243
244
245
246
  * \brief Construct histogram by using this bin
  *        Note: Unlike Bin, OrderedBin doesn't use ordered gradients and ordered hessians.
  *        Because it is hard to know the relative index in one leaf for sparse bin, since we skipped zero bins.
  * \param leaf Using which leaf's data to construct
247
248
  * \param gradients Gradients, Note:non-ordered by leaf
  * \param hessians Hessians, Note:non-ordered by leaf
249
  * \param out Output Result
Guolin Ke's avatar
Guolin Ke committed
250
  */
251
  virtual void ConstructHistogram(int leaf, const score_t* gradients,
252
    const score_t* hessians, hist_t* out) const = 0;
253
254
255
256
257
258

  /*!
  * \brief Construct histogram by using this bin
  *        Note: Unlike Bin, OrderedBin doesn't use ordered gradients and ordered hessians.
  *        Because it is hard to know the relative index in one leaf for sparse bin, since we skipped zero bins.
  * \param leaf Using which leaf's data to construct
259
  * \param gradients Gradients, Note:non-ordered by leaf
260
261
  * \param out Output Result
  */
262
  virtual void ConstructHistogram(int leaf, const score_t* gradients, hist_t* out) const = 0;
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277

  /*!
  * \brief Split current bin, and perform re-order by leaf
  * \param leaf Using which leaf's to split
  * \param right_leaf The new leaf index after perform this split
  * \param is_in_leaf is_in_leaf[i] == mark means the i-th data will be on left leaf after split
  * \param mark is_in_leaf[i] == mark means the i-th data will be on left leaf after split
  */
  virtual void Split(int leaf, int right_leaf, const char* is_in_leaf, char mark) = 0;

  virtual data_size_t NonZeroCount(int leaf) const = 0;
};

/*! \brief Iterator for one bin column */
class BinIterator {
Nikita Titov's avatar
Nikita Titov committed
278
 public:
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
  /*!
  * \brief Get bin data on specific row index
  * \param idx Index of this data
  * \return Bin data
  */
  virtual uint32_t Get(data_size_t idx) = 0;
  virtual uint32_t RawGet(data_size_t idx) = 0;
  virtual void Reset(data_size_t idx) = 0;
  virtual ~BinIterator() = default;
};

/*!
* \brief Interface for bin data. This class will store bin data for one feature.
*        unlike OrderedBin, this class will store data by original order.
*        Note that it may cause cache misses when construct histogram,
*        but it doesn't need to re-order operation, So it will be faster than OrderedBin for dense feature
*/
class Bin {
Nikita Titov's avatar
Nikita Titov committed
297
 public:
298
299
300
301
302
303
304
305
306
307
308
  /*! \brief virtual destructor */
  virtual ~Bin() {}
  /*!
  * \brief Push one record
  * \pram tid Thread id
  * \param idx Index of record
  * \param value bin value of record
  */
  virtual void Push(int tid, data_size_t idx, uint32_t value) = 0;


309
  virtual void CopySubrow(const Bin* full_bin, const data_size_t* used_indices, data_size_t num_used_indices) = 0;
310
311
312
313
  /*!
  * \brief Get bin iterator of this bin for specific feature
  * \param min_bin min_bin of current used feature
  * \param max_bin max_bin of current used feature
Guolin Ke's avatar
Guolin Ke committed
314
  * \param most_freq_bin
315
316
  * \return Iterator of this bin
  */
Guolin Ke's avatar
Guolin Ke committed
317
  virtual BinIterator* GetIterator(uint32_t min_bin, uint32_t max_bin, uint32_t most_freq_bin) const = 0;
318
319
320
321
322

  /*!
  * \brief Save binary data to file
  * \param file File want to write
  */
323
  virtual void SaveBinaryToFile(const VirtualFileWriter* writer) const = 0;
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350

  /*!
  * \brief Load from memory
  * \param memory
  * \param local_used_indices
  */
  virtual void LoadFromMemory(const void* memory,
    const std::vector<data_size_t>& local_used_indices) = 0;

  /*!
  * \brief Get sizes in byte of this object
  */
  virtual size_t SizesInByte() const = 0;

  /*! \brief Number of all data */
  virtual data_size_t num_data() const = 0;

  virtual void ReSize(data_size_t num_data) = 0;

  /*!
  * \brief Construct histogram of this feature,
  *        Note: We use ordered_gradients and ordered_hessians to improve cache hit chance
  *        The naive solution is using gradients[data_indices[i]] for data_indices[i] to get gradients,
           which is not cache friendly, since the access of memory is not continuous.
  *        ordered_gradients and ordered_hessians are preprocessed, and they are re-ordered by data_indices.
  *        Ordered_gradients[i] is aligned with data_indices[i]'s gradients (same for ordered_hessians).
  * \param data_indices Used data indices in current leaf
351
352
  * \param start start index in data_indices
  * \param end end index in data_indices
353
354
355
356
357
  * \param ordered_gradients Pointer to gradients, the data_indices[i]-th data's gradient is ordered_gradients[i]
  * \param ordered_hessians Pointer to hessians, the data_indices[i]-th data's hessian is ordered_hessians[i]
  * \param out Output Result
  */
  virtual void ConstructHistogram(
358
    const data_size_t* data_indices, data_size_t start, data_size_t end,
359
    const score_t* ordered_gradients, const score_t* ordered_hessians,
360
    hist_t* out) const = 0;
361

362
  virtual void ConstructHistogram(data_size_t start, data_size_t end,
363
    const score_t* ordered_gradients, const score_t* ordered_hessians,
364
    hist_t* out) const = 0;
365
366
367
368
369
370
371
372
373

  /*!
  * \brief Construct histogram of this feature,
  *        Note: We use ordered_gradients and ordered_hessians to improve cache hit chance
  *        The naive solution is using gradients[data_indices[i]] for data_indices[i] to get gradients,
  which is not cache friendly, since the access of memory is not continuous.
  *        ordered_gradients and ordered_hessians are preprocessed, and they are re-ordered by data_indices.
  *        Ordered_gradients[i] is aligned with data_indices[i]'s gradients (same for ordered_hessians).
  * \param data_indices Used data indices in current leaf
374
375
  * \param start start index in data_indices
  * \param end end index in data_indices
376
377
378
  * \param ordered_gradients Pointer to gradients, the data_indices[i]-th data's gradient is ordered_gradients[i]
  * \param out Output Result
  */
379
  virtual void ConstructHistogram(const data_size_t* data_indices, data_size_t start, data_size_t end,
380
                                  const score_t* ordered_gradients, hist_t* out) const = 0;
381

382
  virtual void ConstructHistogram(data_size_t start, data_size_t end,
383
                                  const score_t* ordered_gradients, hist_t* out) const = 0;
384
385
386
387
388

  /*!
  * \brief Split data according to threshold, if bin <= threshold, will put into left(lte_indices), else put into right(gt_indices)
  * \param min_bin min_bin of current used feature
  * \param max_bin max_bin of current used feature
Guolin Ke's avatar
Guolin Ke committed
389
390
  * \param default_bin default bin for feature value 0
  * \param most_freq_bin
391
392
393
394
395
396
397
398
399
  * \param missing_type missing type
  * \param default_left missing bin will go to left child
  * \param threshold The split threshold.
  * \param data_indices Used data indices. After called this function. The less than or equal data indices will store on this object.
  * \param num_data Number of used data
  * \param lte_indices After called this function. The less or equal data indices will store on this object.
  * \param gt_indices After called this function. The greater data indices will store on this object.
  * \return The number of less than or equal data.
  */
400
  virtual data_size_t Split(uint32_t min_bin, uint32_t max_bin,
Guolin Ke's avatar
Guolin Ke committed
401
    uint32_t default_bin, uint32_t most_freq_bin, MissingType missing_type, bool default_left, uint32_t threshold,
402
403
404
405
406
407
408
    data_size_t* data_indices, data_size_t num_data,
    data_size_t* lte_indices, data_size_t* gt_indices) const = 0;

  /*!
  * \brief Split data according to threshold, if bin <= threshold, will put into left(lte_indices), else put into right(gt_indices)
  * \param min_bin min_bin of current used feature
  * \param max_bin max_bin of current used feature
Guolin Ke's avatar
Guolin Ke committed
409
  * \param most_freq_bin
410
  * \param threshold The split threshold.
411
  * \param num_threshold Number of threshold
412
413
414
415
416
417
418
  * \param data_indices Used data indices. After called this function. The less than or equal data indices will store on this object.
  * \param num_data Number of used data
  * \param lte_indices After called this function. The less or equal data indices will store on this object.
  * \param gt_indices After called this function. The greater data indices will store on this object.
  * \return The number of less than or equal data.
  */
  virtual data_size_t SplitCategorical(uint32_t min_bin, uint32_t max_bin,
Guolin Ke's avatar
Guolin Ke committed
419
                            uint32_t most_freq_bin, const uint32_t* threshold, int num_threshold,
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
                            data_size_t* data_indices, data_size_t num_data,
                            data_size_t* lte_indices, data_size_t* gt_indices) const = 0;

  /*!
  * \brief After pushed all feature data, call this could have better refactor for bin data
  */
  virtual void FinishLoad() = 0;

  /*!
  * \brief Create object for bin data of one feature, used for dense feature
  * \param num_data Total number of data
  * \param num_bin Number of bin
  * \return The bin data object
  */
  static Bin* CreateDenseBin(data_size_t num_data, int num_bin);

  /*!
  * \brief Create object for bin data of one feature, used for sparse feature
  * \param num_data Total number of data
  * \param num_bin Number of bin
  * \return The bin data object
  */
  static Bin* CreateSparseBin(data_size_t num_data, int num_bin);
443
444
445
446
447

  /*!
  * \brief Deep copy the bin
  */
  virtual Bin* Clone() = 0;
448
449
};

450
451

class MultiValBin {
452
 public:
453
454
455
456
457
458
  virtual ~MultiValBin() {}

  virtual data_size_t num_data() const = 0;

  virtual int32_t num_bin() const = 0;

459
  virtual double num_element_per_row() const = 0;
460
461


462
  virtual void PushOneRow(int tid, data_size_t idx, const std::vector<uint32_t>& values) = 0;
463

464
465
466
  virtual void CopySubrow(const MultiValBin* full_bin,
                          const data_size_t* used_indices,
                          data_size_t num_used_indices) = 0;
467

468
469
  virtual MultiValBin* CreateLike(data_size_t num_data, int num_bin,
                                  int num_feature,
470
471
                                  double estimate_element_per_row) const = 0;

472
473
474
475
476
477
478
479
480
481
482
483
484
485
486

  virtual void CopySubcol(const MultiValBin* full_bin,
                          const std::vector<int>& used_feature_index,
                          const std::vector<uint32_t>& lower,
                          const std::vector<uint32_t>& upper,
                          const std::vector<uint32_t>& delta) = 0;

  virtual void ReSize(data_size_t num_data, int num_bin, int num_feature,
                      double estimate_element_per_row) = 0;

  virtual void CopySubrowAndSubcol(
      const MultiValBin* full_bin, const data_size_t* used_indices,
      data_size_t num_used_indices, const std::vector<int>& used_feature_index,
      const std::vector<uint32_t>& lower, const std::vector<uint32_t>& upper,
      const std::vector<uint32_t>& delta) = 0;
487

Guolin Ke's avatar
Guolin Ke committed
488
489
490
491
492
  virtual void ConstructHistogram(const data_size_t* data_indices,
                                  data_size_t start, data_size_t end,
                                  const score_t* gradients,
                                  const score_t* hessians,
                                  hist_t* out) const = 0;
493
494

  virtual void ConstructHistogram(data_size_t start, data_size_t end,
Guolin Ke's avatar
Guolin Ke committed
495
496
497
                                  const score_t* gradients,
                                  const score_t* hessians,
                                  hist_t* out) const = 0;
498
499


Guolin Ke's avatar
Guolin Ke committed
500
501
502
503
504
505
  virtual void ConstructHistogramOrdered(const data_size_t* data_indices,
                                         data_size_t start, data_size_t end,
                                         const score_t* ordered_gradients,
                                         const score_t* ordered_hessians,
                                         hist_t* out) const = 0;

506
507
508
509
510

  virtual void FinishLoad() = 0;

  virtual bool IsSparse() = 0;

511
512
513
514
515
516
517
  static MultiValBin* CreateMultiValBin(data_size_t num_data, int num_bin,
                                        int num_feature, double sparse_rate);

  static MultiValBin* CreateMultiValDenseBin(data_size_t num_data, int num_bin,
                                             int num_feature);

  static MultiValBin* CreateMultiValSparseBin(data_size_t num_data, int num_bin, double estimate_element_per_row);
518
519
520
521

  virtual MultiValBin* Clone() = 0;
};

522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
inline uint32_t BinMapper::ValueToBin(double value) const {
  if (std::isnan(value)) {
    if (missing_type_ == MissingType::NaN) {
      return num_bin_ - 1;
    } else {
      value = 0.0f;
    }
  }
  if (bin_type_ == BinType::NumericalBin) {
    // binary search to find bin
    int l = 0;
    int r = num_bin_ - 1;
    if (missing_type_ == MissingType::NaN) {
      r -= 1;
    }
    while (l < r) {
      int m = (r + l - 1) / 2;
      if (value <= bin_upper_bound_[m]) {
        r = m;
541
      } else {
542
        l = m + 1;
543
544
      }
    }
545
546
547
548
549
550
551
552
553
    return l;
  } else {
    int int_value = static_cast<int>(value);
    // convert negative value to NaN bin
    if (int_value < 0) {
      return num_bin_ - 1;
    }
    if (categorical_2_bin_.count(int_value)) {
      return categorical_2_bin_.at(int_value);
Guolin Ke's avatar
Guolin Ke committed
554
    } else {
555
      return num_bin_ - 1;
Guolin Ke's avatar
Guolin Ke committed
556
557
    }
  }
558
}
Guolin Ke's avatar
Guolin Ke committed
559
560
561

}  // namespace LightGBM

Guolin Ke's avatar
Guolin Ke committed
562
#endif   // LightGBM_BIN_H_