You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2023/09/26 16:24:16 UTC
[commons-statistics] branch master updated (022a8bd -> 9b05092)
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
from 022a8bd Replace Double.min/max with Math.min/max functions
new 0443768 Refactor two-pass algorithm to FirstMoment
new a0a258e Refactor two-pass algorithm to SumOfSquaredDeviations
new 9b05092 Lower test tolerance due to failure in the random order test
The 3 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../statistics/descriptive/FirstMoment.java | 71 ++++++++++++----
.../commons/statistics/descriptive/Mean.java | 54 ++----------
.../commons/statistics/descriptive/Statistics.java | 3 +-
.../descriptive/SumOfSquaredDeviations.java | 96 +++++++++++++++++-----
.../commons/statistics/descriptive/Variance.java | 67 +++------------
.../statistics/descriptive/VarianceTest.java | 2 +-
6 files changed, 152 insertions(+), 141 deletions(-)
[commons-statistics] 03/03: Lower test tolerance due to failure in the random order test
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
commit 9b050920e609df992c9ec3cc6adbfd2c0a9fb608
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Tue Sep 26 17:23:16 2023 +0100
Lower test tolerance due to failure in the random order test
---
.../java/org/apache/commons/statistics/descriptive/VarianceTest.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/VarianceTest.java b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/VarianceTest.java
index 86e9768..9ceae49 100644
--- a/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/VarianceTest.java
+++ b/commons-statistics-descriptive/src/test/java/org/apache/commons/statistics/descriptive/VarianceTest.java
@@ -33,7 +33,7 @@ final class VarianceTest {
private static final int ULP_STREAM = 5;
- private static final int ULP_COMBINE_ACCEPT = 6;
+ private static final int ULP_COMBINE_ACCEPT = 8;
private static final int ULP_COMBINE_OF = 2;
[commons-statistics] 02/03: Refactor two-pass algorithm to SumOfSquaredDeviations
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
commit a0a258ed5016c59a35ab3a9f6878cadf44798c04
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Tue Sep 26 17:20:16 2023 +0100
Refactor two-pass algorithm to SumOfSquaredDeviations
Allows reuse in a StandardDeviation statistic
---
.../descriptive/SumOfSquaredDeviations.java | 96 +++++++++++++++++-----
.../commons/statistics/descriptive/Variance.java | 67 +++------------
2 files changed, 89 insertions(+), 74 deletions(-)
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/SumOfSquaredDeviations.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/SumOfSquaredDeviations.java
index 895b25f..a06f645 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/SumOfSquaredDeviations.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/SumOfSquaredDeviations.java
@@ -46,30 +46,83 @@ package org.apache.commons.statistics.descriptive;
* because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()}
* provides the necessary partitioning, isolation, and merging of results for
* safe and efficient parallel execution.
+ *
+ * <p>References:
+ * <ul>
+ * <li>Chan, Golub, Levesque (1983)
+ * Algorithms for Computing the Sample Variance,
+ * American Statistician, vol. 37, no. 3, pp. 242-247.
+ * </ul>
*/
class SumOfSquaredDeviations extends FirstMoment {
/** Sum of squared deviations of the values that have been added. */
- private double squaredDevSum;
+ private double sumSquaredDev;
/**
- * Create a SumOfSquaredDeviations instance.
+ * Create an instance.
*/
SumOfSquaredDeviations() {
// No-op
}
/**
- * Create a SumOfSquaredDeviations instance with the given sum of
- * squared deviations and a FirstMoment instance.
+ * Create an instance with the given sum of
+ * squared deviations and first moment.
*
- * @param squaredDevSum Sum of squared deviations.
- * @param mean Mean of values.
+ * @param sumSquaredDev Sum of squared deviations.
+ * @param m1 First moment.
* @param n Number of values.
- * @param nonFiniteValue Sum of values.
+ * @param nonFiniteValue Running sum of values seen so far.
+ */
+ SumOfSquaredDeviations(double sumSquaredDev, double m1, long n, double nonFiniteValue) {
+ super(m1, n, nonFiniteValue);
+ this.sumSquaredDev = sumSquaredDev;
+ }
+
+ /**
+ * Returns a {@code SumOfSquaredDeviations} instance that has the variance of all input values, or {@code NaN}
+ * if:
+ * <ul>
+ * <li>the input array is empty,</li>
+ * <li>any of the values is {@code NaN},</li>
+ * <li>an infinite value of either sign is encountered, or</li>
+ * <li>the sum of the squared deviations from the mean is infinite</li>
+ * </ul>
+ *
+ * <p>Note: {@code SumOfSquaredDeviations} computed using
+ * {@link SumOfSquaredDeviations#accept SumOfSquaredDeviations.accept()} may be different
+ * from this instance.
+ *
+ * <p>See {@link SumOfSquaredDeviations} for details on the computing algorithm.
+ *
+ * @param values Values.
+ * @return {@code SumOfSquaredDeviations} instance.
*/
- SumOfSquaredDeviations(double squaredDevSum, double mean, long n, double nonFiniteValue) {
- super(mean, n, nonFiniteValue);
- this.squaredDevSum = squaredDevSum;
+ static SumOfSquaredDeviations of(double... values) {
+ // "Corrected two-pass algorithm"
+ // See: Chan et al (1983) Equation 1.7
+
+ final double m1 = FirstMoment.of(values).getFirstMoment();
+ if (!Double.isFinite(m1)) {
+ return new SumOfSquaredDeviations(Math.abs(m1), m1, values.length, m1);
+ }
+ double s = 0;
+ double ss = 0;
+ for (final double x : values) {
+ final double dx = x - m1;
+ s += dx;
+ ss += dx * dx;
+ }
+ final long n = values.length;
+ // The sum of squared deviations is ss - (s * s / n).
+ // The second term ideally should be zero; in practice it is a good approximation
+ // of the error in the first term.
+ // To prevent sumSquaredDev from spuriously attaining a NaN value
+ // when ss is infinite, assign it an infinite value which is its intended value.
+ final double sumSquaredDev = ss == Double.POSITIVE_INFINITY ?
+ Double.POSITIVE_INFINITY :
+ ss - (s * s / n);
+ return new SumOfSquaredDeviations(sumSquaredDev, m1, n, s + (m1 * n));
}
/**
@@ -78,8 +131,10 @@ class SumOfSquaredDeviations extends FirstMoment {
*/
@Override
public void accept(double value) {
+ // "Updating one-pass algorithm"
+ // See: Chan et al (1983) Equation 1.3b
super.accept(value);
- squaredDevSum += (n - 1) * dev * nDev;
+ sumSquaredDev += (n - 1) * dev * nDev;
}
/**
@@ -87,8 +142,8 @@ class SumOfSquaredDeviations extends FirstMoment {
*
* @return {@code SumOfSquaredDeviations} of all values seen so far.
*/
- public double getSumOfSquaredDeviations() {
- return Double.isFinite(getFirstMoment()) ? squaredDevSum : Double.NaN;
+ double getSumOfSquaredDeviations() {
+ return Double.isFinite(getFirstMoment()) ? sumSquaredDev : Double.NaN;
}
/**
@@ -97,15 +152,16 @@ class SumOfSquaredDeviations extends FirstMoment {
* @param other Another {@code SumOfSquaredDeviations} to be combined.
* @return {@code this} instance after combining {@code other}.
*/
- public SumOfSquaredDeviations combine(SumOfSquaredDeviations other) {
- final long oldN = n;
- final long otherN = other.n;
- if (oldN == 0) {
- squaredDevSum = other.squaredDevSum;
- } else if (otherN != 0) {
+ SumOfSquaredDeviations combine(SumOfSquaredDeviations other) {
+ final long m = other.n;
+ if (n == 0) {
+ sumSquaredDev = other.sumSquaredDev;
+ } else if (m != 0) {
+ // "Updating one-pass algorithm"
+ // See: Chan et al (1983) Equation 1.5b (modified for the mean)
final double diffOfMean = other.getFirstMoment() - m1;
final double sqDiffOfMean = diffOfMean * diffOfMean;
- squaredDevSum += other.squaredDevSum + sqDiffOfMean * (((double) oldN * otherN) / ((double) oldN + otherN));
+ sumSquaredDev += other.sumSquaredDev + sqDiffOfMean * (((double) n * m) / ((double) n + m));
}
super.combine(other);
return this;
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java
index 2f9efe8..21b10fe 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java
@@ -110,30 +110,7 @@ public abstract class Variance implements DoubleStatistic, DoubleStatisticAccumu
* @return {@code Variance} instance.
*/
public static Variance of(double... values) {
- final double mean = FirstMoment.of(values).getFirstMoment();
- if (!Double.isFinite(mean)) {
- return StorelessSampleVariance.create(Math.abs(mean), mean, values.length, mean);
- }
- double accum = 0.0;
- double dev;
- double accum2 = 0.0;
- double squaredDevSum;
- for (final double value : values) {
- dev = value - mean;
- accum += dev * dev;
- accum2 += dev;
- }
- final double accum2Squared = accum2 * accum2;
- final long n = values.length;
- // The sum of squared deviations is accum - (accum2Squared / n).
- // To prevent squaredDevSum from spuriously attaining a NaN value
- // when accum is infinite, assign it an infinite value which is its intended value.
- if (accum == Double.POSITIVE_INFINITY) {
- squaredDevSum = Double.POSITIVE_INFINITY;
- } else {
- squaredDevSum = accum - (accum2Squared / n);
- }
- return StorelessSampleVariance.create(squaredDevSum, mean, n, accum2 + (mean * n));
+ return new StorelessSampleVariance(SumOfSquaredDeviations.of(values));
}
/**
@@ -169,63 +146,45 @@ public abstract class Variance implements DoubleStatistic, DoubleStatisticAccumu
* An instance of {@link SumOfSquaredDeviations}, which is used to
* compute the variance.
*/
- private final SumOfSquaredDeviations squaredDeviationSum;
+ private final SumOfSquaredDeviations ss;
/**
- * Creates a StorelessVariance instance with the sum of squared
- * deviations from the mean.
+ * Creates an instance with the sum of squared deviations from the mean.
*
- * @param squaredDevSum Sum of squared deviations.
- * @param mean Mean of values.
- * @param n Number of values.
- * @param sumOfValues Sum of values.
+ * @param ss Sum of squared deviations.
*/
- private StorelessSampleVariance(double squaredDevSum, double mean, long n, double sumOfValues) {
- squaredDeviationSum = new SumOfSquaredDeviations(squaredDevSum, mean, n, sumOfValues);
+ StorelessSampleVariance(SumOfSquaredDeviations ss) {
+ this.ss = ss;
}
/**
- * Create a SumOfSquaredDeviations instance.
+ * Create an instance.
*/
StorelessSampleVariance() {
- squaredDeviationSum = new SumOfSquaredDeviations();
- }
-
- /**
- * Creates a StorelessVariance instance with the sum of squared
- * deviations from the mean.
- *
- * @param squaredDevSum Sum of squared deviations.
- * @param mean Mean of values.
- * @param n Number of values.
- * @param sumOfValues Sum of values.
- * @return A StorelessVariance instance.
- */
- static StorelessSampleVariance create(double squaredDevSum, double mean, long n, double sumOfValues) {
- return new StorelessSampleVariance(squaredDevSum, mean, n, sumOfValues);
+ this(new SumOfSquaredDeviations());
}
@Override
public void accept(double value) {
- squaredDeviationSum.accept(value);
+ ss.accept(value);
}
@Override
public double getAsDouble() {
- final double sumOfSquaredDev = squaredDeviationSum.getSumOfSquaredDeviations();
- final double n = squaredDeviationSum.n;
+ final double sumOfSquaredDev = ss.getSumOfSquaredDeviations();
+ final long n = ss.n;
if (n == 0) {
return Double.NaN;
} else if (n == 1 && Double.isFinite(sumOfSquaredDev)) {
return 0;
}
- return sumOfSquaredDev / (n - 1);
+ return sumOfSquaredDev / (n - 1.0);
}
@Override
public Variance combine(Variance other) {
final StorelessSampleVariance that = (StorelessSampleVariance) other;
- squaredDeviationSum.combine(that.squaredDeviationSum);
+ ss.combine(that.ss);
return this;
}
}
[commons-statistics] 01/03: Refactor two-pass algorithm to FirstMoment
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
commit 0443768c4b10b92b2060d9cbbe632a7bd3833d0f
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Tue Sep 26 16:17:31 2023 +0100
Refactor two-pass algorithm to FirstMoment
---
.../statistics/descriptive/FirstMoment.java | 71 ++++++++++++++++------
.../commons/statistics/descriptive/Mean.java | 54 ++--------------
.../commons/statistics/descriptive/Statistics.java | 3 +-
.../commons/statistics/descriptive/Variance.java | 2 +-
4 files changed, 63 insertions(+), 67 deletions(-)
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/FirstMoment.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/FirstMoment.java
index d9ee25e..2c354c6 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/FirstMoment.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/FirstMoment.java
@@ -47,6 +47,16 @@ import java.util.function.DoubleConsumer;
* because the parallel implementation of {@link java.util.stream.Stream#collect Stream.collect()}
* provides the necessary partitioning, isolation, and merging of results for
* safe and efficient parallel execution.
+ *
+ * <p>References:
+ * <ul>
+ * <li>Chan, Golub, Levesque (1983)
+ * Algorithms for Computing the Sample Variance.
+ * American Statistician, vol. 37, no. 3, pp. 242-247.
+ * <li>Ling (1974)
+ * Comparison of Several Algorithms for Computing Sample Means and Variances.
+ * Journal of the American Statistical Association, Vol. 69, No. 348, pp. 859-866.
+ * </ul>
*/
class FirstMoment implements DoubleConsumer {
/** Count of values that have been added. */
@@ -76,30 +86,65 @@ class FirstMoment implements DoubleConsumer {
private double nonFiniteValue;
/**
- * Create a FirstMoment instance.
+ * Create an instance.
*/
FirstMoment() {
// No-op
}
/**
- * Create a FirstMoment instance with the given first moment and number of values.
+ * Create an instance with the given first moment.
+ *
* @param m1 First moment.
* @param n Number of values.
- * @param nonFiniteValue Running sum of values seen so far (Used as a return value for first moment when it is non-finite).
+ * @param nonFiniteValue Running sum of values seen so far.
*/
- FirstMoment(final double m1, final long n, final double nonFiniteValue) {
+ FirstMoment(double m1, long n, double nonFiniteValue) {
this.m1 = m1;
this.n = n;
this.nonFiniteValue = nonFiniteValue;
}
+ /**
+ * Returns a {@code FirstMoment} instance that has the arithmetic mean of all input
+ * values, or {@code NaN} if the input array is empty.
+ *
+ * <p>Note: {@code FirstMoment} computed using {@link FirstMoment#accept
+ * FirstMoment.accept()} may be different from this instance.
+ *
+ * @param values Values.
+ * @return {@code FirstMoment} instance.
+ */
+ static FirstMoment of(double... values) {
+ // "Corrected two-pass algorithm"
+
+ // First pass
+ final FirstMoment m1 = Statistics.add(new FirstMoment(), values);
+ final double xbar = m1.getFirstMoment();
+ if (!Double.isFinite(xbar)) {
+ return m1;
+ }
+ // Second pass
+ double correction = 0;
+ for (final double x : values) {
+ correction += x - xbar;
+ }
+ // Note: Correction may be infinite
+ correction = Double.isFinite(correction) ? correction : 0;
+ return new FirstMoment(xbar + (correction / values.length), m1.n, m1.nonFiniteValue);
+ }
+
/**
* Updates the state of the statistic to reflect the addition of {@code value}.
+ *
* @param value Value.
*/
@Override
public void accept(double value) {
+ // "Updating one-pass algorithm"
+ // See: Chan et al (1983) Equation 1.3a
+ // This is modified with scaling to avoid overflow for all finite input.
+
n++;
nonFiniteValue += value;
// To prevent overflow, dev is computed by scaling down and then scaling up.
@@ -117,11 +162,11 @@ class FirstMoment implements DoubleConsumer {
*
* <p>When no values have been added, the result is {@code NaN}.
*
- * @return {@code First moment} of all values seen so far, if it is finite.
- * <p> {@code Infinity}, if infinities of the same sign have been encountered.
- * <p> {@code NaN} otherwise.
+ * @return {@code First moment} of all values seen so far, if it is finite;
+ * {@code +/-Infinity}, if infinities of the same sign have been encountered;
+ * {@code NaN} otherwise.
*/
- public double getFirstMoment() {
+ double getFirstMoment() {
if (Double.isFinite(m1)) {
return n == 0 ? Double.NaN : m1;
}
@@ -135,7 +180,7 @@ class FirstMoment implements DoubleConsumer {
* @param other Another {@code FirstMoment} to be combined.
* @return {@code this} instance after combining {@code other}.
*/
- public FirstMoment combine(FirstMoment other) {
+ FirstMoment combine(FirstMoment other) {
if (n == 0) {
n = other.n;
nonFiniteValue = other.nonFiniteValue;
@@ -158,12 +203,4 @@ class FirstMoment implements DoubleConsumer {
}
return this;
}
-
- /**
- * Gets the running sum of the values seen so far.
- * @return Running Sum.
- */
- double getNonFiniteValue() {
- return nonFiniteValue;
- }
}
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Mean.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Mean.java
index ddb590b..0d0ba90 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Mean.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Mean.java
@@ -89,19 +89,7 @@ public abstract class Mean implements DoubleStatistic, DoubleStatisticAccumulato
* @return {@code Mean} instance.
*/
public static Mean of(double... values) {
- final StorelessMean mean = Statistics.add(new StorelessMean(), values);
-
- if (!Double.isFinite(mean.getAsDouble())) {
- return mean;
- }
- final double xbar = mean.getAsDouble();
- double correction = 0;
- for (final double value : values) {
- correction += value - xbar;
- }
- // Correction may be infinite
- correction = Double.isFinite(correction) ? correction : 0;
- return StorelessMean.create(xbar + (correction / values.length), mean.getN(), mean.getNonFiniteValue());
+ return new StorelessMean(FirstMoment.of(values));
}
/**
@@ -132,33 +120,19 @@ public abstract class Mean implements DoubleStatistic, DoubleStatisticAccumulato
private final FirstMoment firstMoment;
/**
- * Creates a StorelessMean instance with an External Moment.
+ * Creates an instance with a moment.
*
* @param m1 First moment.
- * @param n Number of values.
- * @param nonFiniteValue Sum of values, which may be non-finite.
*/
- private StorelessMean(final double m1, final long n, final double nonFiniteValue) {
- firstMoment = new FirstMoment(m1, n, nonFiniteValue);
+ StorelessMean(FirstMoment m1) {
+ firstMoment = m1;
}
/**
- * Create a Mean instance.
+ * Create an instance.
*/
StorelessMean() {
- firstMoment = new FirstMoment();
- }
-
- /**
- * Creates a StorelessMean instance with an External Moment.
- *
- * @param m1 First moment.
- * @param n Number of values.
- * @param nonFinite Sum of values, which may be non-finite.
- * @return A StorelessMean instance.
- */
- static StorelessMean create(final double m1, final long n, final double nonFinite) {
- return new StorelessMean(m1, n, nonFinite);
+ this(new FirstMoment());
}
@Override
@@ -177,21 +151,5 @@ public abstract class Mean implements DoubleStatistic, DoubleStatisticAccumulato
firstMoment.combine(that.firstMoment);
return this;
}
-
- /**
- * Gets the number of values that have been added.
- * @return Number of values.
- */
- long getN() {
- return firstMoment.n;
- }
-
- /**
- * Gets the running sum of the values seen so far.
- * @return Running Sum.
- */
- double getNonFiniteValue() {
- return firstMoment.getNonFiniteValue();
- }
}
}
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Statistics.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Statistics.java
index bd5abfc..6c72e62 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Statistics.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Statistics.java
@@ -17,6 +17,7 @@
package org.apache.commons.statistics.descriptive;
import java.util.Arrays;
+import java.util.function.DoubleConsumer;
/**
* Utility methods for statistics.
@@ -34,7 +35,7 @@ final class Statistics {
* @param values Values.
* @return the statistic
*/
- static <T extends DoubleStatistic> T add(T statistic, double[] values) {
+ static <T extends DoubleConsumer> T add(T statistic, double[] values) {
Arrays.stream(values).forEach(statistic);
return statistic;
}
diff --git a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java
index 731cde7..2f9efe8 100644
--- a/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java
+++ b/commons-statistics-descriptive/src/main/java/org/apache/commons/statistics/descriptive/Variance.java
@@ -110,7 +110,7 @@ public abstract class Variance implements DoubleStatistic, DoubleStatisticAccumu
* @return {@code Variance} instance.
*/
public static Variance of(double... values) {
- final double mean = Mean.of(values).getAsDouble();
+ final double mean = FirstMoment.of(values).getFirstMoment();
if (!Double.isFinite(mean)) {
return StorelessSampleVariance.create(Math.abs(mean), mean, values.length, mean);
}