Algoritmo eficiente para a detecção de diferentes elementos em uma coleção

Question

Imagine que você tem um conjunto de cinco elementos (A-E) com alguns valores numéricos de uma medida de propriedade (várias observações para cada elemento, por exemplo, "taxa de coração"):

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}

Primeira, Tenho para detectar se existem diferenças significativas nos níveis médios.Então eu executar uma maneira de ANOVA usando o Pacote estatístico fornecido pelo Apache Commons Matemática.Sem problemas até agora, eu obter um valor booleano que informa se são encontradas diferenças ou não.

Segunda, se forem encontradas diferenças, eu preciso saber o elemento (ou elementos) que é diferente do resto.Eu pretendo usar t não pareado testes, comparando a cada par de elementos de A com B, A com C ....D E E), para saber se um elemento é diferente do que os outros.Então, nesse ponto, eu tenho a informação de que a lista de elementos que não apresentam diferenças significativas com os outros, por exemplo:

C is different than B
C is different than D

Mas eu preciso de um algoritmo genérico para determinar com eficiência, com essa informação, qual o elemento é diferente do que as outras (C no exemplo, mas poderia ser mais do que um).

Deixando questões estatísticas de lado, a questão poderia ser (em termos gerais): "Dada a informação sobre a igualdade/desigualdade de cada um dos pares de elementos em uma coleção, como você pode determinar o elemento (s) que é (são) diferente dos outros?"

Parece ser um problema onde o gráfico teoria poderia ser aplicada.Eu estou usando Java a linguagem para a implementação, se o que é útil.

Editar: Elementos são as pessoas e os valores medidos são de vezes que for necessário para concluir uma tarefa.Preciso detectar que está tendo muito ou pouco tempo para concluir a tarefa em algum tipo de sistema de detecção de fraudes.

Answer 1

Apenas caso alguém esteja interessado no código final, usando Apache Commons Math fazer operações estatísticas e Trove trabalhar com coleções de tipos primitivos.

Ele procura os elementos com o mais alto grau (a idéia é baseada nos comentários feitos por @pace e @aniko, obrigado).

Eu acho que o algoritmo final é O (n^2), as sugestões são bem -vindas. Ele deve funcionar para qualquer problema que envolva uma variável clássica versus uma variável cuantitativa, assumindo a normalidade das observações.

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

Sua edição fornece bons detalhes; obrigado,

Com base nisso, presumiria uma distribuição bastante bem-comportada de vezes (normal ou possivelmente gama; depende de quão perto de zero seus tempos ficam) para respostas típicas. Rejeitar uma amostra dessa distribuição pode ser tão simples quanto calcular um desvio padrão e ver quais amostras estão mais do que n stdevs da média, ou tão complexo quanto pegar subconjuntos que excluem outliers até que seus dados se acalmem em um bom monte (por exemplo, a média para de se mover 'muito').

Agora, você tem uma ruga adicional se assumir que uma pessoa que macaco com um julgamento irá macaco com outro. Então, você está tentando discriminar entre uma pessoa que por acaso é rápida (ou lenta) e alguém que está 'trapaceando'. Você pode fazer algo como calcular a classificação STDEV de cada pontuação (eu esqueço o nome correto para isso: se um valor for dois STDEVs acima da média, a pontuação é '2') e usá -la como sua estatística.

Então, dada a nova estatística, existem algumas hipóteses que você precisará testar. Por exemplo, minha suspeita é que o stdev dessa estatística será mais alto para trapaceiros do que para alguém que é uniformemente mais rápido que outras pessoas-mas você precisaria de dados para verificar isso.

Boa sorte com isso!

Answer 3

Você teria que executar o teste t pareado (ou qualquer que seja o par de teste que você deseja implementar) e a incrementar a contagem em um hash onde a chave é a Pessoa e o contador é o número de vezes que ele era diferente.

Eu acho que você poderia também ter um arrayList que contém objetos de pessoas.As pessoas objeto pode armazenar o seu ID e a contagem de tempo, elas eram diferentes.Implementar comparável e, em seguida, você pode ordenar a arraylist por contagem.

Answer 4

Se os itens da lista foram classificados em ordem numérica, você poderá andar duas listas simultaneamente e quaisquer diferenças poderão ser facilmente reconhecidas como inserções ou exclusões. Por exemplo

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.