View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.stat.inference;
18  
19  import org.apache.commons.math.MathException;
20  import org.apache.commons.math.distribution.ChiSquaredDistribution;
21  import org.apache.commons.math.distribution.ChiSquaredDistributionImpl;
22  import org.apache.commons.math.distribution.DistributionFactory;
23  
24  /**
25   * Implements Chi-Square test statistics defined in the
26   * {@link UnknownDistributionChiSquareTest} interface.
27   *
28   * @version $Revision: 620312 $ $Date: 2008-02-10 12:28:59 -0700 (Sun, 10 Feb 2008) $
29   */
30  public class ChiSquareTestImpl implements UnknownDistributionChiSquareTest {
31  
32      /** Distribution used to compute inference statistics. */
33      private ChiSquaredDistribution distribution;
34    
35      /**
36       * Construct a ChiSquareTestImpl 
37       */
38      public ChiSquareTestImpl() {
39          this(new ChiSquaredDistributionImpl(1.0));
40      }
41  
42      /**
43       * Create a test instance using the given distribution for computing
44       * inference statistics.
45       * @param x distribution used to compute inference statistics.
46       * @since 1.2
47       */
48      public ChiSquareTestImpl(ChiSquaredDistribution x) {
49          super();
50          setDistribution(x);
51      }
52       /**
53       * {@inheritDoc}
54       * <p><strong>Note: </strong>This implementation rescales the 
55       * <code>expected</code> array if necessary to ensure that the sum of the
56       * expected and observed counts are equal.</p>
57       * 
58       * @param observed array of observed frequency counts
59       * @param expected array of expected frequency counts
60       * @return chi-square test statistic
61       * @throws IllegalArgumentException if preconditions are not met
62       * or length is less than 2
63       */
64      public double chiSquare(double[] expected, long[] observed)
65          throws IllegalArgumentException {
66          if ((expected.length < 2) || (expected.length != observed.length)) {
67              throw new IllegalArgumentException(
68                      "observed, expected array lengths incorrect");
69          }
70          if (!isPositive(expected) || !isNonNegative(observed)) {
71              throw new IllegalArgumentException(
72                  "observed counts must be non-negative and expected counts must be postive");
73          }
74          double sumExpected = 0d;
75          double sumObserved = 0d;
76          for (int i = 0; i < observed.length; i++) {
77              sumExpected += expected[i];
78              sumObserved += observed[i];
79          }
80          double ratio = 1.0d;
81          boolean rescale = false;
82          if (Math.abs(sumExpected - sumObserved) > 10E-6) {
83              ratio = sumObserved / sumExpected;
84              rescale = true;
85          }
86          double sumSq = 0.0d;
87          double dev = 0.0d;
88          for (int i = 0; i < observed.length; i++) {
89              if (rescale) {
90                  dev = ((double) observed[i] - ratio * expected[i]);
91                  sumSq += dev * dev / (ratio * expected[i]);
92              } else {
93                  dev = ((double) observed[i] - expected[i]);
94                  sumSq += dev * dev / expected[i];
95              }
96          }
97          return sumSq;
98      }
99  
100     /**
101      * {@inheritDoc}
102      * <p><strong>Note: </strong>This implementation rescales the 
103      * <code>expected</code> array if necessary to ensure that the sum of the
104      * expected and observed counts are equal.</p>
105      * 
106      * @param observed array of observed frequency counts
107      * @param expected array of expected frequency counts
108      * @return p-value
109      * @throws IllegalArgumentException if preconditions are not met
110      * @throws MathException if an error occurs computing the p-value
111      */
112     public double chiSquareTest(double[] expected, long[] observed)
113         throws IllegalArgumentException, MathException {
114         distribution.setDegreesOfFreedom(expected.length - 1.0);
115         return 1.0 - distribution.cumulativeProbability(
116             chiSquare(expected, observed));
117     }
118 
119     /**
120      * {@inheritDoc}
121      * <p><strong>Note: </strong>This implementation rescales the 
122      * <code>expected</code> array if necessary to ensure that the sum of the
123      * expected and observed counts are equal.</p>
124      * 
125      * @param observed array of observed frequency counts
126      * @param expected array of expected frequency counts
127      * @param alpha significance level of the test
128      * @return true iff null hypothesis can be rejected with confidence
129      * 1 - alpha
130      * @throws IllegalArgumentException if preconditions are not met
131      * @throws MathException if an error occurs performing the test
132      */
133     public boolean chiSquareTest(double[] expected, long[] observed, 
134             double alpha) throws IllegalArgumentException, MathException {
135         if ((alpha <= 0) || (alpha > 0.5)) {
136             throw new IllegalArgumentException(
137                     "bad significance level: " + alpha);
138         }
139         return (chiSquareTest(expected, observed) < alpha);
140     }
141     
142     /**
143      * @param counts array representation of 2-way table
144      * @return chi-square test statistic
145      * @throws IllegalArgumentException if preconditions are not met
146      */
147     public double chiSquare(long[][] counts) throws IllegalArgumentException {
148         
149         checkArray(counts);
150         int nRows = counts.length;
151         int nCols = counts[0].length;
152         
153         // compute row, column and total sums
154         double[] rowSum = new double[nRows];
155         double[] colSum = new double[nCols];
156         double total = 0.0d;
157         for (int row = 0; row < nRows; row++) {
158             for (int col = 0; col < nCols; col++) {
159                 rowSum[row] += (double) counts[row][col];
160                 colSum[col] += (double) counts[row][col];
161                 total += (double) counts[row][col];
162             }
163         }
164         
165         // compute expected counts and chi-square
166         double sumSq = 0.0d;
167         double expected = 0.0d;
168         for (int row = 0; row < nRows; row++) {
169             for (int col = 0; col < nCols; col++) {
170                 expected = (rowSum[row] * colSum[col]) / total;
171                 sumSq += (((double) counts[row][col] - expected) * 
172                         ((double) counts[row][col] - expected)) / expected; 
173             }
174         } 
175         return sumSq;
176     }
177 
178     /**
179      * @param counts array representation of 2-way table
180      * @return p-value
181      * @throws IllegalArgumentException if preconditions are not met
182      * @throws MathException if an error occurs computing the p-value
183      */
184     public double chiSquareTest(long[][] counts)
185     throws IllegalArgumentException, MathException {
186         checkArray(counts);
187         double df = ((double) counts.length -1) * ((double) counts[0].length - 1);
188         distribution.setDegreesOfFreedom(df);
189         return 1 - distribution.cumulativeProbability(chiSquare(counts));
190     }
191 
192     /**
193      * @param counts array representation of 2-way table
194      * @param alpha significance level of the test
195      * @return true iff null hypothesis can be rejected with confidence
196      * 1 - alpha
197      * @throws IllegalArgumentException if preconditions are not met
198      * @throws MathException if an error occurs performing the test
199      */
200     public boolean chiSquareTest(long[][] counts, double alpha)
201     throws IllegalArgumentException, MathException {
202         if ((alpha <= 0) || (alpha > 0.5)) {
203             throw new IllegalArgumentException("bad significance level: " + alpha);
204         }
205         return (chiSquareTest(counts) < alpha);
206     }
207     
208     /**
209      * @param observed1 array of observed frequency counts of the first data set
210      * @param observed2 array of observed frequency counts of the second data set
211      * @return chi-square test statistic
212      * @throws IllegalArgumentException if preconditions are not met
213      * @since 1.2
214      */
215     public double chiSquareDataSetsComparison(long[] observed1, long[] observed2)
216         throws IllegalArgumentException {
217         
218         // Make sure lengths are same
219         if ((observed1.length < 2) || (observed1.length != observed2.length)) {
220             throw new IllegalArgumentException(
221                     "oberved1, observed2 array lengths incorrect");
222         }
223         // Ensure non-negative counts
224         if (!isNonNegative(observed1) || !isNonNegative(observed2)) {
225             throw new IllegalArgumentException(
226                 "observed counts must be non-negative");
227         }
228         // Compute and compare count sums
229         long countSum1 = 0;
230         long countSum2 = 0;
231         boolean unequalCounts = false;
232         double weight = 0.0;
233         for (int i = 0; i < observed1.length; i++) {
234             countSum1 += observed1[i];
235             countSum2 += observed2[i];   
236         }
237         // Ensure neither sample is uniformly 0
238         if (countSum1 * countSum2 == 0) {
239             throw new IllegalArgumentException(
240              "observed counts cannot all be 0"); 
241         }
242         // Compare and compute weight only if different
243         unequalCounts = (countSum1 != countSum2);
244         if (unequalCounts) {
245             weight = Math.sqrt((double) countSum1 / (double) countSum2);
246         }
247         // Compute ChiSquare statistic
248         double sumSq = 0.0d;
249         double dev = 0.0d;
250         double obs1 = 0.0d;
251         double obs2 = 0.0d;
252         for (int i = 0; i < observed1.length; i++) {
253             if (observed1[i] == 0 && observed2[i] == 0) {
254                 throw new IllegalArgumentException(
255                         "observed counts must not both be zero");
256             } else {
257                 obs1 = (double) observed1[i];
258                 obs2 = (double) observed2[i];
259                 if (unequalCounts) { // apply weights
260                     dev = obs1/weight - obs2 * weight;
261                 } else {
262                     dev = obs1 - obs2;
263                 }
264                 sumSq += (dev * dev) / (obs1 + obs2);
265             }
266         }
267         return sumSq;
268     }
269 
270     /**
271      * @param observed1 array of observed frequency counts of the first data set
272      * @param observed2 array of observed frequency counts of the second data set
273      * @return p-value
274      * @throws IllegalArgumentException if preconditions are not met
275      * @throws MathException if an error occurs computing the p-value
276      * @since 1.2
277      */
278     public double chiSquareTestDataSetsComparison(long[] observed1, long[] observed2)
279         throws IllegalArgumentException, MathException {
280         distribution.setDegreesOfFreedom((double) observed1.length - 1);
281         return 1 - distribution.cumulativeProbability(
282                 chiSquareDataSetsComparison(observed1, observed2));
283     }
284 
285     /**
286      * @param observed1 array of observed frequency counts of the first data set
287      * @param observed2 array of observed frequency counts of the second data set
288      * @param alpha significance level of the test
289      * @return true iff null hypothesis can be rejected with confidence
290      * 1 - alpha
291      * @throws IllegalArgumentException if preconditions are not met
292      * @throws MathException if an error occurs performing the test
293      * @since 1.2
294      */
295     public boolean chiSquareTestDataSetsComparison(long[] observed1, long[] observed2,
296             double alpha) throws IllegalArgumentException, MathException {
297         if ((alpha <= 0) || (alpha > 0.5)) {
298             throw new IllegalArgumentException(
299                     "bad significance level: " + alpha);
300         }
301         return (chiSquareTestDataSetsComparison(observed1, observed2) < alpha);
302     }
303 
304     /**
305      * Checks to make sure that the input long[][] array is rectangular,
306      * has at least 2 rows and 2 columns, and has all non-negative entries,
307      * throwing IllegalArgumentException if any of these checks fail.
308      * 
309      * @param in input 2-way table to check
310      * @throws IllegalArgumentException if the array is not valid
311      */
312     private void checkArray(long[][] in) throws IllegalArgumentException {
313         
314         if (in.length < 2) {
315             throw new IllegalArgumentException("Input table must have at least two rows");
316         }
317         
318         if (in[0].length < 2) {
319             throw new IllegalArgumentException("Input table must have at least two columns");
320         }    
321         
322         if (!isRectangular(in)) {
323             throw new IllegalArgumentException("Input table must be rectangular");
324         }
325         
326         if (!isNonNegative(in)) {
327             throw new IllegalArgumentException("All entries in input 2-way table must be non-negative");
328         }
329         
330     }
331     
332     //---------------------  Protected methods ---------------------------------
333     /**
334      * Gets a DistributionFactory to use in creating ChiSquaredDistribution instances.
335      * @deprecated inject ChiSquaredDistribution instances directly instead of
336      *             using a factory.
337      */
338     protected DistributionFactory getDistributionFactory() {
339         return DistributionFactory.newInstance();
340     }
341     
342     //---------------------  Private array methods -- should find a utility home for these
343     
344     /**
345      * Returns true iff input array is rectangular.
346      * 
347      * @param in array to be tested
348      * @return true if the array is rectangular
349      * @throws NullPointerException if input array is null
350      * @throws ArrayIndexOutOfBoundsException if input array is empty
351      */
352     private boolean isRectangular(long[][] in) {
353         for (int i = 1; i < in.length; i++) {
354             if (in[i].length != in[0].length) {
355                 return false;
356             }
357         }  
358         return true;
359     }
360     
361     /**
362      * Returns true iff all entries of the input array are > 0.
363      * Returns true if the array is non-null, but empty
364      * 
365      * @param in array to be tested
366      * @return true if all entries of the array are positive
367      * @throws NullPointerException if input array is null
368      */
369     private boolean isPositive(double[] in) {
370         for (int i = 0; i < in.length; i ++) {
371             if (in[i] <= 0) {
372                 return false;
373             }
374         }
375         return true;
376     }
377     
378     /**
379      * Returns true iff all entries of the input array are >= 0.
380      * Returns true if the array is non-null, but empty
381      * 
382      * @param in array to be tested
383      * @return true if all entries of the array are non-negative
384      * @throws NullPointerException if input array is null
385      */
386     private boolean isNonNegative(long[] in) {
387         for (int i = 0; i < in.length; i ++) {
388             if (in[i] < 0) {
389                 return false;
390             }
391         }
392         return true;
393     }
394     
395     /**
396      * Returns true iff all entries of (all subarrays of) the input array are >= 0.
397      * Returns true if the array is non-null, but empty
398      * 
399      * @param in array to be tested
400      * @return true if all entries of the array are non-negative
401      * @throws NullPointerException if input array is null
402      */
403     private boolean isNonNegative(long[][] in) {
404         for (int i = 0; i < in.length; i ++) {
405             for (int j = 0; j < in[i].length; j++) {
406                 if (in[i][j] < 0) {
407                     return false;
408                 }
409             }
410         }
411         return true;
412     }
413  
414     /**
415      * Modify the distribution used to compute inference statistics.
416      * 
417      * @param value
418      *            the new distribution
419      * @since 1.2
420      */
421     public void setDistribution(ChiSquaredDistribution value) {
422         distribution = value;
423     }
424 }