algoritmo eficiente para la detección de diferentes elementos en una colección

Question

Imagine que tiene un conjunto de cinco elementos (A-E) con algunos valores numéricos de una propiedad medida (varias observaciones para cada elemento, por ejemplo, "la frecuencia cardíaca"):

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}

Primera , tengo que detectar si existen diferencias significativas en los niveles medios. Así que corro una manera ANOVA utilizando el paquete estadístico proporcionadas por Apache Commons Matemáticas . No hay problemas hasta ahora, obtienen un valor lógico que me dice si las diferencias se encuentran o no.

Segundo , si se encuentran diferencias, lo que necesito saber el elemento (o elementos) que es diferente del resto . Voy a utilizar desapareado t-pruebas , comparando cada par de elementos (A con B, a con C .... D con E), para saber si un elemento es diferente que el otro. Por lo tanto, en este momento tengo la información de la lista de elementos que presentan diferencias significativas con otros, por ejemplo:

C is different than B
C is different than D

Pero necesito un algoritmo genérico para determinar de manera eficiente, con esa información, qué elemento es diferente a los demás (C en el ejemplo, pero podría haber más de uno).

Dejando cuestiones estadísticas aparte, la pregunta podría ser (en términos generales): "Teniendo en cuenta la información sobre la igualdad / desigualdad de cada uno de los pares de elementos en una colección, ¿cómo podría determinar el elemento / s que es / son diferentes de los demás? "

Parece ser un problema donde la teoría de grafos podría aplicarse. Estoy usando Java idioma de la aplicación, si eso es útil.

Editar son las personas y los valores medidos son tiempos necesarios para completar una tarea. Necesito para detectar que está tomando demasiado tiempo o demasiado pocos para completar la tarea en algún tipo de sistema de detección de fraude.

Answer 1

Por si acaso alguien está interesado en el código final, utilizando Apache Comunes de Matemáticas para realizar operaciones estadísticas y Trove para trabajar con colecciones de tipos primitivos.

Parece que el elemento (s) con el más alto grado (la idea se basa en las observaciones formuladas por @Pace y @Aniko, gracias).

Creo que el algoritmo final es O (n ^ 2), las sugerencias son bienvenidas. Se debe trabajar para cualquier problema que afecta a uno cualitativo frente a una variable cuantitativa, asumiendo normalidad de las observaciones.

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

Tu edición da buenos detalles; Gracias,

Sobre la base de que iba a suponer una distribución bastante buen comportamiento de veces (normal, o posiblemente gamma; depende de qué tan cerca a cero los tiempos se ponen) para las respuestas típicas. Rechazo de una muestra a partir de esta distribución podría ser tan simple como el cálculo de una desviación estándar y el ver que las muestras se encuentran más de n stdevs de la media, o tan complejo como teniendo subconjuntos que excluyen los valores atípicos hasta que sus datos se establece en un montón agradable (por ejemplo, la media deja de moverse alrededor de 'mucho').

Ahora, usted tiene una arruga añadido si se asume que una persona que monos con un ensayo mono voluntad con otro. Así que usted está tratando ralmente para discriminar entre una persona que sólo pasa a ser rápido (o lento) frente a uno que es 'hacer trampa'. Se podría hacer algo como el rango de cómputo DESVEST de cada puntuación (no recuerdo el nombre propio para esto: si un valor es de dos stdevs por encima de la media, la puntuación es de '2'), y el uso que, como su estadística.

A continuación, les da esta nueva estadística, hay algunas hipótesis que necesitará para la prueba. Por ejemplo, mi sospecha es que el DESVEST de esta estadística será mayor para los tramposos que para alguien que es uniformemente más rápido que otras personas -., Pero que había necesidad de datos para verificar que

Buena suerte con eso!

Answer 3

tendría que ejecutar la prueba t pareada (o lo que sea la prueba por parejas desea implementar) y el incremento de los recuentos en un hash donde la clave es la Persona y la cuenta es el número de veces que era diferente.

supongo que también podría tener un ArrayList que contiene objetos de las personas. El objeto las personas podría almacenar su identificación y el recuento de tiempo que eran diferentes. Implementar comparable y entonces se podría ordenar la ArrayList mediante el recuento.

Answer 4

Si los elementos de la lista se ordenan en orden numérico, se puede caminar dos listas simultáneamente, y cualquier diferencia puede ser fácilmente reconocida como inserciones o deleciones. Por ejemplo

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.