weighted_moving_linear_regression.h 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
  1. // Copyright 2018 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef CHROMECAST_BASE_STATISTICS_WEIGHTED_MOVING_LINEAR_REGRESSION_H_
  5. #define CHROMECAST_BASE_STATISTICS_WEIGHTED_MOVING_LINEAR_REGRESSION_H_
  6. #include <stdint.h>
  7. #include <queue>
  8. #include "chromecast/base/statistics/weighted_mean.h"
  9. namespace chromecast {
  10. // Performs linear regression over a set of weighted (x, y) samples.
  11. // Calculates a weighted moving average over a set of weighted (x, y) points.
  12. // The points do not need to be evenly distributed on the X axis, but the
  13. // X coordinate is assumed to be generally increasing.
  14. //
  15. // Whenever a new sample is added using AddSample(), old samples whose
  16. // x coordinates are farther than |max_x_range_| from the new sample's
  17. // x coordinate will be removed from the regression. Note that |max_x_range_|
  18. // must be non-negative.
  19. class WeightedMovingLinearRegression {
  20. public:
  21. struct Sample {
  22. int64_t x;
  23. int64_t y;
  24. double weight;
  25. };
  26. explicit WeightedMovingLinearRegression(int64_t max_x_range);
  27. WeightedMovingLinearRegression(const WeightedMovingLinearRegression&) =
  28. delete;
  29. WeightedMovingLinearRegression& operator=(
  30. const WeightedMovingLinearRegression&) = delete;
  31. ~WeightedMovingLinearRegression();
  32. // Returns the current number of samples that are in the regression.
  33. size_t num_samples() const { return samples_.size(); }
  34. // Adds a weighted (x, y) sample to the set. Note that |weight|
  35. // should be positive.
  36. void AddSample(int64_t x, int64_t y, double weight);
  37. // Gets a y value estimate from the linear regression: y = a*x + b, where
  38. // a and b are the slope and intercept estimates from the regression. The
  39. // standard error of the resulting y estimate is also provided.
  40. // Returns false if the y value cannot be estimated, in which case y and
  41. // |error| are not modified. Returns true otherwise.
  42. bool EstimateY(int64_t x, int64_t* y, double* error) const;
  43. // Gets the current estimated slope and slope error from the linear
  44. // regression. Returns false if the slope cannot be estimated, in which
  45. // case |slope| and |error| are not modified. Returns true otherwise.
  46. bool EstimateSlope(double* slope, double* error) const;
  47. // Dumps samples currently in the linear regression.
  48. void DumpSamples() const;
  49. // Returns a const reference to the samples currently captured. Very
  50. // useful for debugging.
  51. const std::deque<Sample>& samples() { return samples_; }
  52. // Reserves space for |count| samples, to reduce memory allocation during use.
  53. void Reserve(int count);
  54. // Resets to initial state.
  55. void Reset();
  56. private:
  57. // Adds (x, y) to the set if |weight| is positive; removes (x, y) from the
  58. // set if |weight| is negative.
  59. void UpdateSet(int64_t x, int64_t y, double weight);
  60. const int64_t max_x_range_;
  61. WeightedMean x_mean_;
  62. WeightedMean y_mean_;
  63. double covariance_ = 0.0;
  64. std::deque<Sample> samples_;
  65. double slope_ = 0.0;
  66. double slope_variance_ = 0.0;
  67. double intercept_variance_ = 0.0;
  68. bool has_estimate_ = false;
  69. };
  70. } // namespace chromecast
  71. #endif // CHROMECAST_BASE_STATISTICS_WEIGHTED_MOVING_LINEAR_REGRESSION_H_