Эффективный алгоритм для определения различных элементов в коллекции

Question

Представьте у вас есть набор из пяти элементов (АЭ) с некоторыми числовыми значениями измеряемой собственности (несколько наблюдений для каждого элемента, например, «сердечный ритм»):

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, используя Statistical package provided by Apache Commons Math. Никаких проблем до сих пор, я получаю логическое значение, которое говорит мне, существуют ли различия или нет.

Второй, если различия найдены, мне нужно знать элемент (или элементы), который отличается от остальных. Я планирую использовать unpaired t-tests, сравнивая каждую пару элементов (A с B, A с C .... D с E), чтобы узнать, отличается ли элемент от другого. Таким образом, на данный момент у меня есть информация о списке элементов, которые представляют существенные различия с другими, например:

C is different than B 
C is different than D 

Но мне нужен общий алгоритм для эффективного определения, с той информацией, какой элемент отличается другие (C в примере, но могут быть более одного).

Оставив статистические вопросы в стороне, вопрос может быть (в общих чертах): «Учитывая информацию о равенстве/неравенстве каждой из пар элементов в коллекции, как бы вы могли определить элемент/s, который является/отличаются от других? "

Кажется, проблема, в которой может применяться теория графов. Я использую язык Java для реализации, если это полезно.

Редактировать: Элементы - это люди, а измеренные значения необходимы для выполнения задачи. Мне нужно определить, кто принимает слишком много или слишком мало времени для выполнения задачи в какой-то системе обнаружения мошенничества.

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

Answer 2

Ваше редактирование дает хорошие данные; спасибо,

Основываясь на этом, я бы предположил, что для типичных ответов достаточно правильное распределение времени (нормальное или, возможно, гамма, зависит от того, насколько близко к нулю ваше время). Отклонение выборки из этого распределения может быть таким же простым, как вычисление стандартного отклонения и видение того, какие образцы лежат больше, чем n stdevs из среднего значения, или такие же сложные, как взятие подмножеств, которые исключают выбросы, пока ваши данные не окажутся в хорошей куче (например, средняя перестает двигаться «много»).

Теперь у вас есть добавленная морщина, если вы предполагаете, что человек, который обезьяны с одним испытанием обезьяны с другим. Таким образом, вы пытаетесь различить человека, который просто бывает быстрым (или медленным) против того, кто «обманывает». Вы могли бы сделать что-то вроде вычисления ранга stdev каждого балла (я забыл собственное имя для этого: если значение равно двум stdevs выше среднего, оценка равна «2») и использовать это как вашу статистику.

Затем, учитывая эту новую статистику, есть некоторые гипотезы, которые вам нужно будет проверить. Например, мое подозрение в том, что stdev этой статистики будет выше для читеров, чем для тех, кто просто равномерно быстрее других людей, - но для этого вам нужны данные, чтобы проверить это.

Удачи вам!

Answer 3

Вам нужно будет запустить парный t-тест (или любой другой парный тест, который вы хотите реализовать), и приращение счетчиков в хеше, где ключ является Лицом, а число - это число раз, когда оно было другим.

Я думаю, у вас также может быть массив, содержащий объекты людей. Объект people может хранить свой идентификатор и подсчет времени, когда они были разными. Внесите сопоставимые результаты, и тогда вы сможете сортировать аррайалиста по счету.

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.