algorithme efficace pour la détection de différents éléments dans une collection

Question

Imaginez que vous avez un ensemble de cinq éléments (A-E) avec des valeurs numériques d'une propriété mesurée (plusieurs observations pour chaque élément, par exemple « de la 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}

Première , je dois détecter si des différences significatives sur les niveaux moyens. Alors, je lance une façon ANOVA utilisant paquet statistique fourni par Apache Commons Math . Pas de problème jusqu'à présent, j'obtenir un booléen qui me dit si les différences se trouvent 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 apparié tests t , la comparaison de chaque paire d'éléments (A avec B, A à C .... D à 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 de celui des autres (C dans l'exemple, mais pourrait être plus d'un).

Laissant les problèmes statistiques mis à part, la question pourrait être (en termes généraux): «Étant donné les informations sur l'égalité / inégalité de chacune des paires d'éléments dans une collection, comment pourriez-vous déterminer l'élément / s qui est / sont différents des autres? "

Il semble être un problème où la théorie des graphes pourrait être appliquée. J'utilise Java langue pour la mise en œuvre, si cela est utile.

Modifier sont les gens et les valeurs mesurées sont temps nécessaires pour accomplir une tâche. Je dois détecter qui prend trop ou trop peu de temps pour terminer la tâche dans une sorte de système de détection de la 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 pour travailler avec des collections de types primitifs.

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

Je pense que l'algorithme final est O (n ^ 2), les suggestions sont les bienvenus. Il devrait fonctionner pour tout problème impliquant un cualitative vs 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 modification donne de bons détails; merci,

D'après ce que je présume une distribution des temps assez bien comportés (normal, ou peut-être gamma, dépend de la façon proche de zéro vos temps sont) pour les réponses typiques. Rejetant un échantillon de cette distribution pourrait être aussi simple que le calcul d'un écart-type et de voir quels échantillons se situent plus n stdevs de la moyenne, ou aussi complexe que de prendre des sous-ensembles qui excluent les valeurs aberrantes jusqu'à ce que vos données s'installe dans un tas agréable (par exemple, la moyenne cesse de se déplacer autour de 'beaucoup').

Maintenant, vous avez une ride supplémentaire si vous supposez qu'une personne qui singes avec un essai sera singe avec un autre. Donc, vous ralement à tenter de distinguer entre une personne qui se trouve être rapide (ou lent) par rapport à celui qui est « tricher ». Vous pourriez faire quelque chose comme calculer le rang stdev de chaque partition (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 de tester. Par exemple, je soupçonne que la stdev de cette statistique sera plus élevé pour les tricheurs que pour quelqu'un qui est juste uniforme plus vite que les autres -. Mais vous auriez besoin de données pour vérifier que

Bonne chance avec elle!

Answer 3

Vous devez exécuter le test t apparié (ou tout autre essai par paire que vous voulez mettre en œuvre) et l'augmentation des comptes 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 un arrayList contenant des objets personnes. L'objet des gens pourrait stocker leur carte d'identité et les comptes de temps ils étaient différents. Comparables et mettre en œuvre, vous pouvez trier les arraylist par le comte.

Answer 4

Si les éléments de la liste ont été classés par ordre numérique, vous pouvez marcher deux listes simultanément, et toute différence peut facilement être reconnu 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.