有效的算法为一个集合中检测的不同元素

Question

假设你有一组五个元素（A-E）与测量的特性的某些数值（几个观测对于每个元件，例如“心脏率”）：

A = {100, 110, 120, 130}
B = {110, 100, 110, 120, 90}
C = { 90, 110, 120, 100}
D = {120, 100, 120, 110, 110, 120}
E = {110, 120, 120, 110, 120}

<强>第一下，我有，如果有平均水平显著差异来检测。所以我运行一个单向 ANOVA 使用的统计包由Apache的百科全书数学提供。没有问题，到目前为止，我得到一个布尔值，它告诉我，差异是否被发现或没有。

<强>第二下，如果发现差别，我需要知道的元件（或多个元件），其是从所述静止不同。我打算使用非配对t-检验中，比较每个对元素（A与B，A以C .... d与E），要知道如果元素比其他不同。所以，在这一点我有元素的列表，与他人本显著差异，例如的信息：

C is different than B
C is different than D

但我需要一个通用的算法，以有效地确定，与该信息，什么元件比其他不同（C在该示例中，但也可以是一个以上的）。

离开的统计问题不谈，这个问题可能是（一般条款）：“鉴于对平等/在对一个集合中的元素中的每一个的不平等，你怎么能确定信息的要素/ s的那是/从其他不同？“

似乎是其中可以应用图形理论问题。我使用的的Java 语言实现，如果这是有益的。

修改元素是人值和测量值是完成一项任务所需时间。我需要检测谁是服用过多或过少的时间来完成任务某种欺诈检测系统。

Answer 1

万一有人有兴趣的最后的代码，使用阿帕奇下议院数学，以使统计业务和特罗韦与原始类型的集合工作。

它看起来为元素（多个）具有最高程度（的想法是基于由@Pace和@Aniko作出的评论，感谢）。

我认为最终使用的算法是O（n ^ 2），建议，欢迎。它应该工作对于涉及一个cualitative VS一个cuantitative变量的任何问题，假设观测的正常性。

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");             
            }
        }
    }
}

Answer 2

您编辑提供了良好的细节;感谢，

根据我会假定的时间相当乖巧的分布（正常的，或者可能伽马;取决于如何接近零的时候获得）的典型反应。从这个分布拒绝样本可能是简单的计算标准差，看到哪些样本骗了n多stdevs从平均值，或复杂如服用，直到你的数据平息下来，到一个不错的堆其排除离群值的子集（例如平均停止走动 '多'）。

现在，你是否假设有一个额外的皱纹是一个人谁猴子单次试验的猴子与其他。所以，你想erally谁恰好是快（或慢）与一个谁是“欺骗”的人之间进行区分。你可以做这样的事情每个分数的计算STDEV排名（我忘了这样做的正确名称：如果值高于表示两个stdevs，比分是“2”），并使用它作为您的统计。

然后，给这个新的统计数据，有一些假设你需要测试。例如，我的怀疑是，这个统计的STDEV会更高的骗子比别人谁只是均匀的速度比其他人 - 但你需要的数据，以验证

祝你好运吧！

Answer 3

您必须运行配对t检验（或者你想实现什么成对测试）和增量的散列结果，其中的关键是人事和计数的次数是不同的计数。

我想你也可以使用包含人对象的ArrayList。人们对象可以存储他们的ID和时间的计数他们是不同的。实现可比性，那么你可以排序计数ArrayList中。

Answer 4

如果在列表中的项目按数字顺序进行排序，你可以同时走两个列表，任何差别可以很容易地被识别为插入或缺失。例如

List A    List B
  1         1       // Match, increment both pointers
  3         3       // Match, increment both pointers
  5         4       // '4' missing in list A. Increment B pointer only.

List A    List B
  1         1       // Match, increment both pointers
  3         3       // Match, increment both pointers
  4         5       // '4' missing in list B (or added to A). Incr. A pointer only.