algoritmo efficiente per rilevare elementi diversi in una raccolta

Question

Immaginate di avere una serie di cinque elementi (A-E) con alcuni valori numerici di una proprietà misurata (diverse osservazioni per ogni elemento, ad esempio "frequenza cardiaca"):

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}

prima , devo rilevare se ci sono differenze significative sui livelli medi. Così ho eseguito un senso unico ANOVA utilizzando il pacchetto statistico nofollow noreferrer" fornito da Apache Commons Math . Nessun problema finora, ottengo un valore booleano che mi dice se le differenze si trovano o meno.

Secondo , se si trovano delle differenze, ho bisogno di sapere il elemento (o gli elementi) che è diverso dal resto . Ho intenzione di usare spaiato t-test , confrontando ogni coppia di elementi (A con B, a con C .... D con E), per sapere se un elemento è diverso rispetto agli altri. Quindi, a questo punto non ho le informazioni della lista di elementi che presentano differenze significative con gli altri, per esempio:

C is different than B
C is different than D

Ma ho bisogno di un algoritmo generico per determinare in modo efficiente, con queste informazioni, quale elemento è diverso rispetto agli altri (C nell'esempio, ma potrebbe essere più di uno).

Lasciando da questioni statistiche a parte, la questione potrebbe essere (in termini generali): "Dato l'informazioni su uguaglianza / disuguaglianza di ciascuna delle coppie di elementi di una collezione, come è possibile determinare l'elemento / s che è / sono diverso dagli altri? "

Sembra essere un problema in cui potrebbe essere applicata teoria dei grafi. Sto usando Java la lingua per l'attuazione, se questo è utile.

Modifica Gli elementi sono le persone ed i valori misurati sono i tempi necessari per completare un compito. Devo rilevare che sta prendendo troppo o troppo poco tempo per completare l'operazione in una sorta di sistema di rilevamento delle frodi.

Answer 1

Nel caso in cui qualcuno è interessato al codice finale, utilizzando Apache Comuni Math per fare operazioni statistiche, e Trove di lavorare con collezioni di tipi primitivi.

Si presenta per l'elemento (s) con il più alto grado (l'idea si basa su commenti fatti da @Pace e @Aniko, grazie).

Credo che l'algoritmo finale è O (n ^ 2), i suggerimenti sono i benvenuti. Dovrebbe funzionare per qualsiasi problema che coinvolge un cualitative contro una variabile cuantitative, assumendo la normalità delle osservazioni.

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

La modifica dà buoni dettagli; grazie,

In base a che avrei presumere una distribuzione abbastanza ben educati di volte (normali, o forse gamma; dipende da come vicino allo zero i tempi ottengono) per le risposte tipiche. Rifiutare un campione di questa distribuzione potrebbe essere semplice come calcolare una deviazione standard e vedendo che i campioni si trovano più di n stdevs dalla media, o complesso come prendere sottoinsiemi che escludono valori anomali fino a quando i dati si assesta in un bel mucchio (ad esempio, la media smette di muoversi 'molto piu').

Ora, si dispone di una ruga aggiunto se si assume che una persona che scimmie con uno studio sarà scimmia con un altro. Quindi stai ralmente cercando di discriminare tra una persona che guarda caso è veloce (o lenta) contro colui che è 'barare'. Si potrebbe fare qualcosa di simile a calcolare il rango stdev di ogni punteggio (non ricordo il nome proprio per questo: se un valore è due stdevs sopra la media, il punteggio è '2'), e l'uso che come statistica.

Quindi, data questa nuova statistica, ci sono alcune ipotesi di cui ha bisogno per provare. Per esempio, il mio sospetto è che la stdev di questa statistica sarà più alto per i truffatori che per qualcuno che è appena uniformemente più velocemente di altre persone -. Ma avresti bisogno di dati per verificare che

Buona fortuna con essa!

Answer 3

Si dovrà eseguire il t-test accoppiato (o qualsiasi altra cosa prova a coppie che si desidera implementare) e l'incremento dei conteggi in un hash in cui la chiave è la Persona e il conteggio è il numero di volte era diverso.

Credo che si potrebbe anche avere un ArrayList che contiene oggetti persone. L'oggetto persone potrebbe memorizzare la loro identificazione e la conta del tempo erano diversi. Implementare comparabili e quindi si poteva ordinare l'arraylist dal conte.

Answer 4

Se le voci nella lista sono stati ordinati in ordine numerico, si può camminare due liste contemporaneamente, e le eventuali differenze possono essere facilmente riconosciuto come inserzioni o delezioni. Ad esempio

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.