用于检测集合中不同元素的高效算法

以防万一有人对最终代码感兴趣，使用Apache Commons Math进行统计运算，并使用Trove来处理基元类型的集合。

它寻找具有最高程度的元素（这个想法是基于@Pace的评论，@Aniko，谢谢）。

我认为最终的算法是O（n^2），欢迎提出建议。它应该适用于涉及一个归约变量与一个归因变量的任何问题，假设观测值的正态性。

import gnu.trove.iterator.TIntIntIterator;
import gnu.trove.map.TIntIntMap;
import gnu.trove.map.hash.TIntIntHashMap;
import gnu.trove.procedure.TIntIntProcedure;
import gnu.trove.set.TIntSet;
import gnu.trove.set.hash.TIntHashSet;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.math.MathException;
import org.apache.commons.math.stat.inference.OneWayAnova;
import org.apache.commons.math.stat.inference.OneWayAnovaImpl;
import org.apache.commons.math.stat.inference.TestUtils;


public class TestMath {
    private static final double SIGNIFICANCE_LEVEL = 0.001; // 99.9%

    public static void main(String[] args) throws MathException {
        double[][] observations = {
           {150.0, 200.0, 180.0, 230.0, 220.0, 250.0, 230.0, 300.0, 190.0 },
           {200.0, 240.0, 220.0, 250.0, 210.0, 190.0, 240.0, 250.0, 190.0 },
           {100.0, 130.0, 150.0, 180.0, 140.0, 200.0, 110.0, 120.0, 150.0 },
           {200.0, 230.0, 150.0, 230.0, 240.0, 200.0, 210.0, 220.0, 210.0 },
           {200.0, 230.0, 150.0, 180.0, 140.0, 200.0, 110.0, 120.0, 150.0 }
        };

        final List<double[]> classes = new ArrayList<double[]>();
        for (int i=0; i<observations.length; i++) {
            classes.add(observations[i]);
        }

        OneWayAnova anova = new OneWayAnovaImpl();
//      double fStatistic = anova.anovaFValue(classes); // F-value
//      double pValue = anova.anovaPValue(classes);     // P-value

        boolean rejectNullHypothesis = anova.anovaTest(classes, SIGNIFICANCE_LEVEL);
        System.out.println("reject null hipothesis " + (100 - SIGNIFICANCE_LEVEL * 100) + "% = " + rejectNullHypothesis);

        // differences are found, so make t-tests
        if (rejectNullHypothesis) {
            TIntSet aux = new TIntHashSet();
            TIntIntMap fraud = new TIntIntHashMap();

            // i vs j unpaired t-tests - O(n^2)
            for (int i=0; i<observations.length; i++) {
                for (int j=i+1; j<observations.length; j++) {
                    boolean different = TestUtils.tTest(observations[i], observations[j], SIGNIFICANCE_LEVEL);
                    if (different) {
                        if (!aux.add(i)) {
                            if (fraud.increment(i) == false) {
                                fraud.put(i, 1);
                            }
                        }
                        if (!aux.add(j)) {
                            if (fraud.increment(j) == false) {
                                fraud.put(j, 1);
                            }
                        }
                    }           
                }
            }

            // TIntIntMap is sorted by value
            final int max = fraud.get(0);
            // Keep only those with a highest degree
            fraud.retainEntries(new TIntIntProcedure() {
                @Override
                public boolean execute(int a, int b) {
                    return b != max;
                }
            });

            // If more than half of the elements are different
            // then they are not really different (?)
            if (fraud.size() > observations.length / 2) {
                fraud.clear();
            }

            // output
            TIntIntIterator it = fraud.iterator();
            while (it.hasNext()) {
                it.advance();
                System.out.println("Element " + it.key() + " has significant differences");             
            }
        }
    }
}

您的编辑提供了很好的细节;谢谢

基于此，我假设一个相当表现良好的时间分布（正常，或者可能是伽马;取决于你的时间接近于零）的典型响应。从此分布中剔除样本可以像计算标准差并查看哪些样本距离均值超过n个stdevs一样简单，也可以像取排除异常值的子集一样复杂，直到您的数据稳定下来到一个漂亮的堆中（例如，均值停止在“很多”周围移动）。

现在，如果你假设一个用一个试验猴子的人会和另一个试验一起猴子，你就会有一个额外的皱纹。因此，你错误地试图区分一个碰巧快（或慢）的人和一个“作弊”的人。你可以做一些事情，比如计算每个分数的标准开发排名（我忘记了正确的名称：如果一个值比平均值高两个stdevs，则分数是“2”），并将其用作你的统计数据。

然后，鉴于这个新的统计数据，您需要测试一些假设。例如，我怀疑这个统计数据的标准对于作弊者来说会比那些比其他人快得多的人更高 - 但你需要数据来验证这一点。

祝你好运！