Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You 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.
  */
 
 package org.apache.mahout.math.stats;
 
Computes on-line estimates of mean, variance and all five quartiles (notably including the median). Since this is done in a completely incremental fashion (that is what is meant by on-line) estimates are available at any time and the amount of memory used is constant. Somewhat surprisingly, the quantile estimates are about as good as you would get if you actually kept all of the samples.

The method used for mean and variance is Welford's method. See

http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm

The method used for computing the quartiles is a simplified form of the stochastic approximation method described in the article "Incremental Quantile Estimation for Massive Tracking" by Chen, Lambert and Pinheiro

See

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580

 
 public class OnlineSummarizer {
 
   private boolean sorted = true;
 
   // the first several samples are kept so we can boot-strap our estimates cleanly
   private DoubleArrayList starter = new DoubleArrayList(100);
 
   // quartile estimates
   private final double[] q = new double[5];
 
   // mean and variance estimates
   private double mean;
   private double variance;
 
   // number of samples seen so far
   private int n;
 
   public void add(double sample) {
      = false;
 
     ++;
     double oldMean = ;
      += (sample - ) / ;
     double diff = (sample - ) * (sample - oldMean);
      += (diff - ) / ;
 
     if ( < 100) {
       .add(sample);
     } else if ( == 100 &&  != null) {
       // when we first reach 100 elements, we switch to incremental operation
       .add(sample);
       for (int i = 0; i <= 4; i++) {
         [i] = getQuartile(i);
       }
       // this signals any invocations of getQuartile at exactly 100 elements that we have
       // already switched to incremental operation
        = null;
     } else {
       // n >= 100 && starter == null
       [0] = Math.min(sample[0]);
       [4] = Math.max(sample[4]);
 
       double rate = 2 * ([3] - [1]) / ;
       [1] += (Math.signum(sample - [1]) - 0.5) * rate;
       [2] += Math.signum(sample - [2]) * rate;
       [3] += (Math.signum(sample - [3]) + 0.5) * rate;
 
       if ([1] < [0]) {
         [1] = [0];
       }
 
       if ([3] > [4]) {
         [3] = [4];
       }
     }
   }
 
   public int getCount() {
     return ;
  }
  public double getMean() {
    return ;
  }
  public double getSD() {
    return Math.sqrt();
  }
  public double getMin() {
    return getQuartile(0);
  }
  private void sort() {
    if (! &&  != null) {
      .sort();
       = true;
    }
  }
  public double getMax() {
    return getQuartile(4);
  }
  public double getQuartile(int i) {
    if ( > 100 ||  == null) {
      return [i];
    } else {
      sort();
      switch (i) {
        case 0:
          if ( == 0) {
            throw new IllegalArgumentException("Must have at least one sample to estimate minimum value");
          }
          return .get(0);
        case 1:
        case 2:
        case 3:
          if ( >= 2) {
            double x = i * ( - 1) / 4.0;
            int k = (int) Math.floor(x);
            double u = x - k;
            return .get(k) * (1 - u) + .get(k + 1) * u;
          } else {
            throw new IllegalArgumentException("Must have at least two samples to estimate quartiles");
          }
        case 4:
          if ( == 0) {
            throw new IllegalArgumentException("Must have at least one sample to estimate maximum value");
          }
          return .get(.size() - 1);
        default:
          throw new IllegalArgumentException("Quartile number must be in the range [0..4] not " + i);
      }
    }
  }
  public double getMedian() {
    return getQuartile(2);
  }
New to GrepCode? Check out our FAQ X