Effizienter Algorithmus zum Erfassen verschiedene Elemente in einer Sammlung

Question

Stellen Sie sich vor Sie haben eine Reihe von fünf Elementen (A-E) mit einigen numerischen Werten einer gemessenen Eigenschaft (mehrere Beobachtungen für jedes Element, zum Beispiel „Herzfrequenz“):

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}

Erste , ich habe zu erkennen, ob es signifikante Unterschiede auf dem durchschnittlichen Niveau. So laufe ich eine Einweg ANOVA die bereitgestellt Statistisches Paket von Apache Commons Math . Keine Probleme bisher, erhalte ich eine boolean, das mir sagt, ob Unterschiede gefunden werden oder nicht.

Zweite , wenn Unterschiede gefunden werden, muss ich die Element (oder Elemente) kennen, die anders als die anderen ist . Ich plane ungepaarten t-Tests zu verwenden, wobei jedes Paar von Elementen zu vergleichen (A mit B, A mit C .... D mit E), zu wissen, ob ein Element anders als die andere ist. Also, an dieser Stelle habe ich die Informationen von der Liste der Elemente, die gegenwärtig erhebliche Unterschiede mit anderen, zum Beispiel:

C is different than B
C is different than D

Aber ich brauche einen generischen Algorithmus, um effizient zu bestimmen, mit dieser Information, welches Element ist anders als die andere (C in dem Beispiel, könnte aber mehr sein als ein).

beiseite statistischen Fragen Weggehen, könnte die Frage (im Allgemeinen) sein: "die Information über die Gleichheit / Ungleichheit von jedem der Paare von Elementen in einer Sammlung gegeben, wie Sie das Element bestimmen könnte / s, dass ist / von den anderen unterscheidet sind? "

Es scheint ein Problem zu sein, wo die Graphentheorie angewandt werden könnte. Ich bin mit Java Sprache für die Umsetzung, wenn das sinnvoll ist.

Edit: Elemente sind Menschen und Messwerte sind Zeiten benötigt, um eine Aufgabe zu beenden. Ich muß erkennen, die zu viel nimmt oder zu wenig Zeit, um die Aufgabe in irgendeiner Art von Betrugserkennungssystem abzuschließen.

Answer 1

Für den Fall, jemand interessiert sich für die endgültige Code, mit Apache Commons Math statistische Operationen zu machen, und Trove Arbeit mit Sammlungen von primitiven Typen.

Es sieht für das Element (e) mit dem höchsten Grad (die Idee basiert auf Kommentare von @Pace und @Aniko, danke).

ich glaube, der letzte Algorithmus ist O (n ^ 2), Vorschläge sind willkommen. Es sollte für jedes Problem umgehen ein cualitative vs einer cuantitative Variable beteiligt, die Normalität der Beobachtungen angenommen wird.

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

Ihre Bearbeitung gibt gute Details; Dank,

Auf der Grundlage, dass ich eine ziemlich gut erzogene Verteilung der Zeiten vermuten würde (normal, oder möglicherweise gamma; hängt davon ab, wie nah Ihre Zeit bekommt auf Null) für typische Reaktionen. eine Probe aus dieser Verteilung abweisen könnte so einfach sein eine Standardabweichung und sehen, welche Proben liegen mehr als n stdevs aus dem Mittelwert, oder so komplex wie Untergruppen nehmen die Ausreißer, bis Ihre Daten absetzt in einen schönen Haufen (zB die mittleren ausschließen als Rechen stoppt die Bewegung um 'viel').

Nun, Sie haben eine zusätzliche Falten, wenn Sie davon ausgehen, dass eine Person, die Affen mit einem Versuch Willen Affen mit einem anderen. So versucht man erally zwischen einer Person zu unterscheiden, die nur zufällig schnell sein (oder langsam) gegenüber einem, den ‚Betrug‘ ist. Man könnte so etwas wie Compute der STDEV Rang jeder Partitur tun (ich den richtigen Namen für das vergessen: wenn ein Wert zwei stdevs über dem Mittelwert ist, die Partitur ist ‚2‘), und verwenden Sie diese als Ihre Statistik.

Dann gegeben, diese neue Statistik, gibt es einige Hypothesen Sie testen müssen. Zum Beispiel, mein Verdacht ist, dass die STDEV dieser Statistik für Betrüger höher sein als für jemanden, der gerade gleichmäßig schneller als andere Menschen -. Aber Sie würden Daten, die überprüfen müssen

Viel Glück damit!

Answer 3

würden Sie haben den gepaarten t-Test (oder was auch immer paarweise Test Sie implementieren mögen) laufen zu lassen und das Schrittweite der Zählungen in einem Hash, wo der Schlüssel die Person ist und die Zählung ist die Zahl mal war es anders.

Ich denke, man könnte auch eine Arraylist haben die Menschen Objekte enthält. Die Menschen Objekt konnte speichern ihre ID und die Grafen von Zeit sie waren anders. Implementieren vergleichbar und dann könnten Sie die Arraylist von Graf sortieren.

Answer 4

Wenn die Elemente in der Liste in numerischer Reihenfolge sortiert wurden, können Sie zwei Listen gleichzeitig laufen, und alle Unterschiede können leicht als Einfügungen oder Löschungen erkannt werden. Zum Beispiel

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.