bdlsta_linefit.h

Go to the documentation of this file.

/// @file bdlsta_linefit.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bdlsta_linefit.h                                                   -*-C++-*-
#ifndef INCLUDED_BDLSTA_LINEFIT
#define INCLUDED_BDLSTA_LINEFIT
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
// BDE_VERIFY pragma: -LL01 // Link is just too long
 
/// @defgroup bdlsta_linefit bdlsta_linefit
/// @brief  Online algorithm for computing the least squares regression line.
/// @addtogroup bdl
/// @{
/// @addtogroup bdlsta
/// @{
/// @addtogroup bdlsta_linefit
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bdlsta_linefit-purpose"> Purpose</a>
/// * <a href="#bdlsta_linefit-classes"> Classes </a>
/// * <a href="#bdlsta_linefit-description"> Description </a>
///   * <a href="#bdlsta_linefit-usage"> Usage </a>
///     * <a href="#bdlsta_linefit-example-1-calculating-line-fit-variance-and-mean"> Example 1: Calculating line fit, variance, and mean </a>
///
/// # Purpose {#bdlsta_linefit-purpose}
/// Online algorithm for computing the least squares regression line.
///
/// # Classes {#bdlsta_linefit-classes}
///
/// -  bdlsta::LineFit: online calculation of least squares regression line
///
/// # Description {#bdlsta_linefit-description}
/// This component provides a mechanism, `bdlsta::LineFit`, that
/// provides online calculation of the least squares line fit.  Online
/// algorithms process the data in one pass, while maintaining accuracy.  The
/// online algorithm used is developed in the implementation notes (it is
/// similar to the Welford online algorithm for computing variance).  The
/// formulae for line fit are taken from:
/// https://en.wikipedia.org/wiki/Simple_linear_regression#Fitting_the_regression_line
///
/// Note that the behavior is undefined if there are less than 2 data points, or
/// if all the X's (dependent variable) are the same.
///
/// ## Usage {#bdlsta_linefit-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Calculating line fit, variance, and mean {#bdlsta_linefit-example-1-calculating-line-fit-variance-and-mean}
///
///
/// This example shows how to accumulate a set of values, and calculate the
/// line fit parameters, variance, and mean.
///
/// First, we create example input and instantiate the appropriate mechanism:
/// @code
/// double inputX[] = { 1.0, 2.0, 4.0, 5.0 };
/// double inputY[] = { 1.0, 2.0, 4.0, 4.5 };
/// bdlsta::LineFit lineFit;
/// @endcode
/// Then, we invoke the `add` routine to accumulate the data:
/// @code
/// for(int i = 0; i < 4; ++i) {
///     lineFit.add(inputX[i], inputY[i]);
/// }
/// @endcode
/// Finally, we assert that the alpha, beta, variance, and mean are what we
/// expect:
/// @code
/// double alpha, beta;
/// ASSERT(4    == lineFit.count());
/// ASSERT(3.0  == lineFit.xMean());
/// ASSERT(1e-3 >  fabs(2.875    - lineFit.yMean()));
/// ASSERT(1e-3 >  fabs(3.33333  - lineFit.variance()));
/// ASSERT(0    == lineFit.fitIfValid(&alpha, &beta));
/// ASSERT(1e-3 >  fabs(0.175 - alpha));
/// ASSERT(1e-3 >  fabs(0.9   - beta ));
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bdl
 * @{
 */
/** @addtogroup bdlsta
 * @{
 */
/** @addtogroup bdlsta_linefit
 * @{
 */
 
// BDE_VERIFY pragma: +LL01
 
#include <bdlscm_version.h>
 
#include <bsl_cmath.h>
 
#include <bsls_assert.h>
#include <bsls_review.h>
 
 
namespace bdlsta {
 
                            // =============
                            // class LineFit
                            // =============
 
/// This class provides an efficient online algorithm for calculating linear
/// square line fit.  The class also calculates the mean for the X's and
/// Y's, and variance for the X's. These are byproducts of calculating the
/// line fit.  The online algorithm is detailed in the implementation notes.
///
/// See @ref bdlsta_linefit 
class LineFit {
  private:
    // DATA
    int    d_count; // Number of data points.
    double d_xMean; // Mean of X's.
    double d_xSum;  // Sum of X's.
    double d_ySum;  // Sum of Y's.
    double d_M2;    // 2nd moment
    double d_xySum; // Sum of Xi*Yi
 
  public:
    // CONSTANTS
    enum {
        e_SUCCESS         = 0,
        e_INADEQUATE_DATA = -1
    };
 
    // CREATORS
 
    /// Create an empty `LineFit` object.
    LineFit();
 
    // MANIPULATORS
 
    /// Add the specified `(xValue, yValue)` point to the data set.
    void add(double xValue, double yValue);
 
    // ACCESSORS
 
    /// Returns the number of elements in the data set.
    int count() const;
 
    /// Calculate line fit coefficients `Y = Alpha + Beta * X`, and populate
    /// the specified `alpha` (intercept) and `beta` (slope).  
    /// 
    /// \pre The behavior is undefined   if `2 > count` or all X's are identical.
    void fit(double *alpha, double *beta) const;
 
    /// Calculate line fit coefficients `Y = Alpha + Beta * X`, and populate
    /// the specified `alpha` (intercept) and `beta` (slope).  Return 0 on
    /// success, and non-zero otherwise.  The computations is unsuccessful
    /// if `2 > count` or all X's are identical.
    int fitIfValid(double *alpha, double *beta) const;
 
    /// Return the variance of the data set X's.  
    /// 
    /// \pre The behavior is undefined   unless `2 <= count`.
    double variance() const;
 
    /// Load into the specified `result`, the variance of the data set X's.
    /// Return 0 on success, and a non-zero value otherwise.  Specifically,
    /// `e_INADEQUATE_DATA` is returned if `2 > count`.
    int varianceIfValid(double *result) const;
 
    /// Return the mean of the data set X's.  
    /// 
    /// \pre The behavior is undefined   unless `1 <= count`.
    double xMean() const;
 
    /// Load into the specified `result`, the mean of the data set X's.
    /// Return 0 on success, and a non-zero value otherwise.  Specifically,
    /// `e_INADEQUATE_DATA` is returned if `1 > count`.
    int xMeanIfValid(double *result) const;
 
    /// Return the mean of the data set Y's.  
    /// 
    /// \pre The behavior is undefined   unless `1 <= count`.
    double yMean() const;
 
    /// Load into the specified `result`, the mean of the data set Y's.
    /// Return 0 on success, and a non-zero value otherwise.  Specifically,
    /// `e_INADEQUATE_DATA` is returned if `1 > count`.
    int yMeanIfValid(double *result) const;
};
 
// ============================================================================
//                               INLINE DEFINITIONS
// ============================================================================
 
                        // ---------------------
                        // class bdlsta::LineFit
                        // ---------------------
 
// CREATORS
inline
LineFit::LineFit()
: d_count(0)
, d_xMean(0.0)
, d_xSum(0.0)
, d_ySum(0.0)
, d_M2(0.0)
, d_xySum(0.0)
{
}
 
// MANIPULATORS
inline
void LineFit::add(double xValue, double yValue)
{
    const double delta = xValue - d_xMean;
    ++d_count;
    d_xSum += xValue;
    d_ySum += yValue;
    d_xMean = d_xSum / static_cast<double>(d_count);
    const double delta2 = xValue - d_xMean;
    d_M2 += delta * delta2;
    d_xySum += xValue * yValue;
}
 
// ACCESSORS
inline
int LineFit::count() const
{
    return d_count;
}
 
inline
void LineFit::fit(double *alpha, double *beta) const
{
    BSLS_ASSERT(2 <= d_count && 0.0 != d_M2);
 
    const double n = static_cast<double>(d_count);
    double tmpBeta = (d_xySum - d_xSum * d_ySum / n) / d_M2;
    *beta = tmpBeta;
    *alpha = (d_ySum - d_xSum * tmpBeta) / n;
}
 
inline
int LineFit::fitIfValid(double *alpha, double *beta) const
{
    if (2 > d_count || 0.0 == d_M2) {
        return e_INADEQUATE_DATA;                                     // RETURN
    }
    const double n = static_cast<double>(d_count);
    double tmpBeta = (d_xySum - d_xSum * d_ySum / n) / d_M2;
    *beta = tmpBeta;
    *alpha = (d_ySum - d_xSum * tmpBeta) / n;
    return 0;
}
 
inline
double LineFit::variance() const
{
    BSLS_ASSERT(2 <= d_count);
 
    return d_M2 / (d_count - 1);
}
 
inline
int LineFit::varianceIfValid(double *result) const
{
    if (2 > d_count) {
        return e_INADEQUATE_DATA;                                     // RETURN
    }
    *result = variance();
    return 0;
}
 
inline
double LineFit::xMean() const
{
    BSLS_ASSERT(1 <= d_count);
 
    return d_xSum / static_cast<double>(d_count);
}
 
inline
int LineFit::xMeanIfValid(double *result) const
{
    if (1 > d_count) {
        return e_INADEQUATE_DATA;                                     // RETURN
    }
    *result = xMean();
    return 0;
}
 
inline
double LineFit::yMean() const
{
    BSLS_ASSERT(1 <= d_count);
 
    return d_ySum / static_cast<double>(d_count);
}
 
inline
int LineFit::yMeanIfValid(double *result) const
{
    if (1 > d_count) {
        return e_INADEQUATE_DATA;                                     // RETURN
    }
    *result = yMean();
    return 0;
}
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2017 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */