blob: d7b06f4a711283f1d94293a1c5823d595efdc599 [file] [log] [blame]
 // Copyright 2018 The Chromium Authors // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef CHROMECAST_BASE_STATISTICS_WEIGHTED_MOVING_LINEAR_REGRESSION_H_ #define CHROMECAST_BASE_STATISTICS_WEIGHTED_MOVING_LINEAR_REGRESSION_H_ #include #include #include "chromecast/base/statistics/weighted_mean.h" namespace chromecast { // Performs linear regression over a set of weighted (x, y) samples. // Calculates a weighted moving average over a set of weighted (x, y) points. // The points do not need to be evenly distributed on the X axis, but the // X coordinate is assumed to be generally increasing. // // Whenever a new sample is added using AddSample(), old samples whose // x coordinates are farther than |max_x_range_| from the new sample's // x coordinate will be removed from the regression. Note that |max_x_range_| // must be non-negative. class WeightedMovingLinearRegression { public: struct Sample { int64_t x; int64_t y; double weight; }; explicit WeightedMovingLinearRegression(int64_t max_x_range); WeightedMovingLinearRegression(const WeightedMovingLinearRegression&) = delete; WeightedMovingLinearRegression& operator=( const WeightedMovingLinearRegression&) = delete; ~WeightedMovingLinearRegression(); // Returns the current number of samples that are in the regression. size_t num_samples() const { return samples_.size(); } // Adds a weighted (x, y) sample to the set. Note that |weight| // should be positive. void AddSample(int64_t x, int64_t y, double weight); // Gets a y value estimate from the linear regression: y = a*x + b, where // a and b are the slope and intercept estimates from the regression. The // standard error of the resulting y estimate is also provided. // Returns false if the y value cannot be estimated, in which case y and // |error| are not modified. Returns true otherwise. bool EstimateY(int64_t x, int64_t* y, double* error) const; // Gets the current estimated slope and slope error from the linear // regression. Returns false if the slope cannot be estimated, in which // case |slope| and |error| are not modified. Returns true otherwise. bool EstimateSlope(double* slope, double* error) const; // Dumps samples currently in the linear regression. void DumpSamples() const; // Returns a const reference to the samples currently captured. Very // useful for debugging. const std::deque& samples() { return samples_; } // Reserves space for |count| samples, to reduce memory allocation during use. void Reserve(int count); // Resets to initial state. void Reset(); private: // Adds (x, y) to the set if |weight| is positive; removes (x, y) from the // set if |weight| is negative. void UpdateSet(int64_t x, int64_t y, double weight); const int64_t max_x_range_; WeightedMean x_mean_; WeightedMean y_mean_; double covariance_ = 0.0; std::deque samples_; double slope_ = 0.0; double slope_variance_ = 0.0; double intercept_variance_ = 0.0; bool has_estimate_ = false; }; } // namespace chromecast #endif // CHROMECAST_BASE_STATISTICS_WEIGHTED_MOVING_LINEAR_REGRESSION_H_