高效算法集合中檢測不同的元素

Question

假設你有一組五個元素（AE）與測量的特性的某些數值（幾個觀測對於每個元件，例如「心臟率」）：

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} 

第一個，我必須檢測平均水平是否存在顯着差異。所以我使用Statistical package provided by Apache Commons Math運行單向ANOVA。到目前爲止沒有問題，我得到一個布爾值，告訴我是否找到差異。

二，如果發現差別，我需要知道元件（或多個元件），其是從所述靜止不同。我打算使用unpaired t-tests，比較每對元素（A與B，A與C .... D與E），以知道元素是否與另一元素不同。所以，在這一點上我有一個展示與他人顯著差異元素列表的信息，例如：

C is different than B 
C is different than D 

但我需要一個通用的算法，有效地確定，處理這些信息，什麼元素比不同其他人（例如C，但可能不止一個）。

不考慮統計問題，問題可以是（一般而言）：「給定關於集合中每對元素的平等/不平等的信息，如何確定這些元素是/與其他人不同？「

似乎是圖論可應用的問題。我使用Java語言來執行，如果這很有用。

編輯：元素是人，測量值是完成任務所需的時間。我需要檢測誰在某種欺詐檢測系統中花費太多或太少時間來完成任務。

Answer 1

萬一有人有興趣的最終代碼，使用Apache Commons Math進行統計操作，並Trove與原始類型的集合工作。

它尋找最高度的元素（這個想法是基於@Pace和@Aniko所做的評論，謝謝）。

我覺得最後的算法是O（n^2），歡迎提出建議。它應該適用於任何涉及一個cualitative與一個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個標準差，或者像獲取排除異常值的子集一樣複雜，直到您的數據穩定到一個很好的堆（例如平均值停止移動'太多'）。

現在，如果您認爲一個人與一個審判猴子將猴子與另一個審判猴子，你有一個額外的皺紋。所以你試圖區分一個剛好快速（或緩慢）的人和一個「作弊」的人。你可以做一些事情，例如計算每個分數的stdev排名（我忘記了這個名字：如果一個值是平均值以上的兩個stdevs，那麼得分是'2'），並將其用作統計量。

然後，鑑於這個新統計量，有一些假設需要測試。例如，我的猜測是，對於作弊者來說，這個統計數據的平均值要高於那些一致性快於其他人的人 - 但是你需要數據來驗證這一點。

祝你好運！

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.