在一个集合中检测不同元素的高效算法

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}

首先，我需要检测平均水平上是否存在显著差异。因此，我使用由Apache Commons Math提供的统计软件包运行单向ANOVA。到目前为止没有问题，我得到一个布尔值告诉我是否发现差异。

其次，如果找到了差异，我需要知道与其他元素不同的元素（或元素）。 我计划使用未配对t检验，比较每对元素（A与B，A与C....D与E），以确定一个元素是否与另一个元素不同。因此，此时我已经拥有了呈现与其他元素显著差异的元素列表的信息，例如：

C is different than B
C is different than D

但是我需要一个通用算法，以有效地确定哪个元素与其他元素不同（例如示例中的C，但可能不止一个），具有该信息。离开统计问题不谈，一般问题可能是：“给定关于集合中每对元素的相等/不相等的信息，如何确定与其他元素不同的元素？”似乎这是可以应用图论的问题。我正在使用Java语言进行实现，如果有用的话。

编辑：元素是人员，测量值是完成任务所需的时间。我需要在某种欺诈检测系统中检测谁花费了太多或太少的时间来完成任务。

- Guido

---

非常好格式化的问题。不过这里的“不同元素”是指什么？你是指具有最大差异边缘的元素吗？根据你目前展示的图形示例，看起来你只是在寻找度数最高的元素？ - Pace

请你详细阐述一下你对于“不同”或“显著差异”的定义。一个天真的观点可能会说所有东西都是不同的。但显然，那不是你追求的。 - sfussenegger

@sfussenegger 感谢。我的“不同元素”是指在统计术语中，其测量属性的平均值不同的元素。也就是说，当在给定的置信区间（通常为95%）内发现统计学上的显著差异时。http://en.wikipedia.org/wiki/Statistical_significance - Guido

我的观点是，如果你只是在寻找最高程度，那么根本没有必要创建图表。 只需遍历您的C-B差异，并对每个差异投票一个元素（一个给C和一个给B）。 最后，您可以对投票进行排序并选择具有最多元素的元素。 如果您有更复杂的度量标准，则可能需要一个图表。 - Pace

至少你会想要使用费舍尔的LSD程序，它使用汇总的SD估计，因此具有更多的自由度->更强大。但是，如果大多数均值相等，只有少数不同（即您的情况），则该方法无法控制整体类型I错误率。我建议使用Tukey的HSD。 - Aniko

Answer 1

如果有人对最终代码感兴趣，可以使用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");             
            }
        }
    }
}

- Guido

Answer 2

如果列表中的项目按数字顺序排序，您可以同时遍历两个列表，并且任何差异都可以轻松地识别为插入或删除。例如：

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.

- Scott Smith

Answer 3

你的编辑提供了很好的细节，谢谢。

基于此，我会假设典型响应的时间分布相当规矩（正态分布或可能是伽马分布；这取决于你的时间接近零的程度）。拒绝来自该分布的样本可以简单地计算标准差并查看哪些样本距离平均值超过n个标准差，也可以像排除异常值一样复杂，直到数据稳定下来形成一个漂亮的堆（例如，平均值停止“大幅”移动）。

现在，如果你假设一个人在一个试验中作弊，那么他很可能在另一个试验中也会作弊。因此，你真正想要区分的是一个碰巧很快（或很慢）的人和一个“作弊”的人。你可以计算每个分数的标准差排名（我忘记了这个的正确名称：如果一个值比平均值高两个标准差，则分数为“2”），并将其用作你的统计量。

然后，根据这个新的统计量，你需要测试一些假设。例如，我的怀疑是，作弊者的这个统计量的标准差会比其他人均匀快速的标准差高，但你需要数据来验证这一点。

祝你好运！

- Alex Feinman

---

谢谢。事实上，我认为这就是方差分析（ANOVA）在幕后所做的。 - Guido

好的，那个东西。统计课已经有一段时间了。那么你的问题是什么？你想知道哪里可以找到一个好的ANOVA实现？ - Alex Feinman

不完全是这样。真正的问题在于ANOVA表明存在差异，我甚至可以知道元素X与其他元素Y之间的差异，但我不知道哪一个是不同的。 - Guido

你的分布表现良好。因此，你可以假设异常值位于最大值或最小值处。逐个从数据集中删除异常值，并重新计算平均值，直到它不再变化太多，或者标准差的变化变得很小。 - Alex Feinman

Answer 4

你需要运行成对的t检验（或者你想要实现的任何成对测试），然后在哈希表中增加计数，其中键是人员，计数是不同的次数。

我猜你也可以有一个包含人员对象的ArrayList。人员对象可以存储他们的ID和不同时间的计数。实现可比性，然后你可以按计数对数组列表进行排序。

- TheSteve0