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

Question

Imagine que tiene un conjunto de cinco elementos (AE) 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} 

Primero, Tengo que detectar si hay diferencias significativas en los niveles promedio. Entonces corro de una manera ANOVA usando el Statistical package provided by Apache Commons Math. Sin problemas hasta el momento, obtengo un booleano que me dice si se encuentran diferencias o no.

Segunda, si se encuentran diferencias, necesito saber el elemento (o elementos) que es diferente del resto. Planeo usar unpaired t-tests, comparando cada par de elementos (A con B, A con C .... D con E), para saber si un elemento es diferente al 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 los demás (C en el ejemplo, pero podría ser más de uno).

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

Parece ser un problema donde se podría aplicar la teoría de gráficos. Estoy usando el lenguaje Java para la implementación, si eso es útil.

Editar: Los elementos son personas y los valores medidos son los tiempos necesarios para completar una tarea. Necesito detectar quién está tomando demasiado o muy poco tiempo 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 Commons Math para hacer operaciones estadísticas y Trove para trabajar con colecciones de tipos primitivos.

Busca el/los elemento (s) con el grado más alto (la idea se basa en los comentarios hechos por @Pace y @Aniko, gracias).

Creo que el algoritmo final es O (n^2), las sugerencias son bienvenidas. Debería funcionar para cualquier problema que involucre una variable cualitativa versus una cuantitativa, asumiendo la 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

Su edición da buenos detalles; gracias,

En base a eso, supongo que una distribución de tiempos bastante buena (normal, o posiblemente gamma, depende de qué tan cerca de cero llegue su tiempo) para respuestas típicas. Rechazar una muestra de esta distribución podría ser tan simple como calcular una desviación estándar y ver qué muestras son más que n stdevs de la media, o tan complejas como tomar subconjuntos que excluyen valores atípicos hasta que sus datos se establezcan en un buen montón (p. deja de moverse 'mucho').

Ahora, usted tiene una arruga agregada si supone que una persona que monos con una prueba montará con otra. Entonces estás tratando de discriminar entre una persona que simplemente es rápida (o lenta) contra una que está "haciendo trampa". Podrías hacer algo como calcular el rango stdev de cada puntaje (se me olvida el nombre propio para esto: si un valor es dos stdevs por encima de la media, el puntaje es '2'), y usar eso como tu estadística.

Luego, dada esta nueva estadística, hay algunas hipótesis que deberá probar. Por ejemplo, mi sospecha es que la estadística de esta estadística será más alta para los tramposos que para alguien que es uniformemente más rápido que otras personas, pero necesitaría datos para verificarlo.

¡Buena suerte con eso!

Answer 3

Debería ejecutar la prueba t pareada (o la prueba pairwise que desee implementar) y aumentar los recuentos en un hash donde la clave es la Persona y el recuento es el número de veces que fue diferente.

Supongo que también podría tener un arrayList que contenga objetos de personas. El objeto de personas podría almacenar su ID y los tiempos de diferencia. Implement comparable y luego puedes ordenar el arraylist por count.

Answer 4

Si los elementos de la lista se ordenaron en orden numérico, puede recorrer dos listas al mismo tiempo, y cualquier diferencia puede reconocerse fácilmente como inserciones o eliminaciones. 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.