Эффективный алгоритм обнаружения различных элементов в коллекции

Question

Представьте, что у вас есть набор из пяти элементов (A-E) с некоторыми числовыми значениями измеряемого свойства (несколько наблюдений для каждого элемента, например, «частота сердечных сокращений»):

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}

Сначала , я должен определить, есть ли существенные различия в средних уровнях. Поэтому я запускаю односторонний ANOVA , используя Статистический пакет, предоставленный Apache Commons Math . Пока никаких проблем, я получаю логическое значение, которое сообщает мне, найдены различия или нет.

Второй , если обнаружены различия, мне нужно знать элемент (или элементы), который отличается от остальных . Я планирую использовать непарные t-тесты , сравнивающие каждую пару элементов (A с B, A с C .... D с E), чтобы узнать, отличается ли один элемент от другого. Итак, на данный момент у меня есть информация о списке элементов, которые представляют существенные различия с другими, например:

C is different than B
C is different than D

Но мне нужен общий алгоритм, чтобы с этой информацией эффективно определить, какой элемент отличается от других (в примере C, но может быть больше одного).

Если оставить в стороне статистические вопросы, вопрос может быть (в общих чертах): "Учитывая информацию о равенстве / неравенстве каждой из пар элементов в коллекции, как вы можете определить элемент (ы), который отличается от других? "

Кажется, это проблема, где теория графов может быть применена. Я использую Java язык для реализации, если это полезно.

Редактировать: Элементы - это люди, и измеренные значения - это время, необходимое для выполнения задачи. Мне нужно определить, кому требуется слишком много или слишком мало времени, чтобы выполнить задачу в какой-то системе обнаружения мошенничества.

Answer 1

На всякий случай, если кто-то заинтересован в конечном коде, используя Apache Commons Math для выполнения статистических операций и Trove для работы с коллекциями примитивных типов.

Он ищет элементы с наивысшей степенью (идея основана на комментариях, сделанных @Pace и @Aniko, спасибо).

Я думаю, что последний алгоритм O (n ^ 2), предложения приветствуются. Он должен работать для любой проблемы, включающей одну качественную или одну количественную переменную, предполагая нормальность наблюдений.

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

Вам потребуется запустить парный t-тест (или любой другой попарный тест, который вы хотите реализовать) и увеличить значение счетчика в хэше, где ключом является Person, а счетчиком - число раз, которое было другим. *

Полагаю, вы могли бы также иметь arrayList, содержащий объекты людей. Объект люди могут хранить свои идентификационные данные и время, в течение которого они были разными. Реализуйте сравнимо, и тогда вы можете отсортировать массив по количеству.

Answer 3

Если элементы в списке были отсортированы в числовом порядке, вы можете пройти два списка одновременно, и любые различия могут быть легко распознаны как вставки или удаления. Например

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.

Answer 4

Ваше редактирование дает хорошие детали; спасибо,

Исходя из этого, я бы предположил, что для типичных ответов довольно хорошо ведет себя распределение времен (нормальное или, возможно, гамма-значение; зависит от того, насколько близки к нулю ваши времена). Отказ от выборки из этого распределения может быть таким же простым, как вычисление стандартного отклонения и определение, какие выборки лежат более чем на n stdevs от среднего значения, или таким же сложным, как выбор подмножеств, исключающих выбросы, пока ваши данные не окажутся в хорошей куче (например, среднее перестает двигаться "много").

Теперь у вас есть дополнительные складки, если вы предполагаете, что человек, который обезьяны с одним испытанием будет обезьяна с другим. Таким образом, вы все время пытаетесь провести различие между человеком, который оказался быстрым (или медленным) и человеком, который «обманывает». Вы можете сделать что-то вроде вычисления рейтинга stdev для каждой оценки (я забыл правильное имя для этого: если значение на два stdevs выше среднего значения, оценка равна '2'), и использовать это как статистику.

Затем, учитывая эту новую статистику, есть несколько гипотез, которые вам нужно проверить. Например, я подозреваю, что значение этой статистики будет выше для мошенников, чем для кого-то, кто просто одинаково быстрее других людей - но вам понадобятся данные для проверки этого.

Удачи с этим!