algorithme efficace pour détecter des éléments différents dans une collection

Question

Imaginez que vous avez un ensemble de cinq éléments (AE) avec des valeurs numériques d'une propriété mesurée (plusieurs observations pour chaque élément, par exemple « fréquence cardiaque »):

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} 

D'abord, je dois détecter s'il y a des différences significatives sur les niveaux moyens. Donc, je cours d'une manière ANOVA en utilisant le Statistical package provided by Apache Commons Math. Aucun problème jusqu'à présent, j'obtiens un booléen qui me dit si des différences sont trouvées ou non.

Deuxième, si les différences se trouvent, je dois savoir l'élément (ou éléments) qui est différent du reste. Je prévois d'utiliser unpaired t-tests, en comparant chaque paire d'éléments (A avec B, A avec C .... D avec E), pour savoir si un élément est différent de l'autre. Donc, à ce stade, j'ai les informations de la liste des éléments qui présentent des différences significatives avec les autres, par exemple:

C is different than B 
C is different than D 

Mais je besoin d'un algorithme générique pour déterminer efficacement, avec cette information, quel élément est différent les autres (C dans l'exemple, mais pourraient être plus d'un). Laissant de côté les problèmes statistiques, la question pourrait être (en termes généraux): "Étant donné les informations sur l'égalité/l'inégalité de chacune des paires d'éléments dans une collection, comment pourriez-vous déterminer le ou les éléments qui sont/sont différents des autres? "

Semble être un problème où la théorie des graphes pourrait être appliquée. J'utilise le langage Java pour l'implémentation, si cela est utile.

Édition: Les éléments sont des personnes et les valeurs mesurées sont des temps nécessaires pour effectuer une tâche. J'ai besoin de détecter qui prend trop ou trop peu de temps pour terminer la tâche dans un système de détection de fraude.

Answer 1

Juste au cas où quelqu'un est intéressé par le code final, en utilisant Apache Commons Math pour faire des opérations statistiques et Trove de travailler avec des collections de types primitifs.

Il recherche le (s) élément (s) avec le plus haut degré (l'idée est basée sur les commentaires faits par @Pace et @Aniko, merci).

Je pense que l'algorithme final est O (n^2), les suggestions sont les bienvenues. Cela devrait fonctionner pour n'importe quel problème impliquant une variable qualitative versus une variable cuantitative, en supposant la normalité des observations.

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

Votre vérification donne de bons détails; Merci,

Sur la base de cela, je suppose une distribution des temps assez sages (normal, ou éventuellement gamma, dépend de la façon dont près de zéro votre temps) pour les réponses typiques. Rejeter un échantillon de cette distribution pourrait être aussi simple que de calculer un écart-type et de voir quels échantillons se situent à plus de n stdevs de la moyenne, ou aussi complexe que de prendre des sous-ensembles qui excluent les valeurs aberrantes. arrête de bouger 'beaucoup').

Maintenant, vous avez une ride ajoutée si vous supposez qu'une personne qui singe avec un essai singe avec un autre. Donc, vous essayez de faire la distinction entre une personne qui arrive à être rapide (ou lente) et celle qui triche. Vous pouvez faire quelque chose comme calculer le rang stdev de chaque score (j'oublie le nom propre pour cela: si une valeur est deux stdevs au-dessus de la moyenne, le score est '2'), et l'utiliser comme statistique. Ensuite, compte tenu de cette nouvelle statistique, il y a quelques hypothèses dont vous aurez besoin pour tester. Par exemple, je soupçonne que la statistique de cette statistique sera plus élevée pour les tricheurs que pour quelqu'un qui est uniformément plus rapide que les autres - mais vous aurez besoin de données pour vérifier cela.

Bonne chance avec ça!

Answer 3

Vous devrez exécuter le test t apparié (ou tout autre test par paire que vous souhaitez implémenter) et incrémenter les comptages dans un hachage où la clé est la Personne et le nombre est le nombre de fois qu'il était différent.

Je suppose que vous pourriez aussi avoir une arrayList qui contient des objets people. L'objet personnes pourrait stocker leur carte d'identité et le nombre de fois où ils étaient différents. Mettre en œuvre comparable et ensuite vous pourriez trier l'arraylist par le nombre.

Answer 4

Si les éléments de la liste ont été triés par ordre numérique, vous pouvez parcourir deux listes simultanément et toutes les différences peuvent facilement être identifiées comme des insertions ou des suppressions. Par exemple

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.