Эффективный алгоритм для обнаружения различных элементов в наборе
Предположите, что у Вас есть ряд пяти элементов (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 Математика палаты общин. Никакие проблемы до сих пор, я получаю булевскую переменную, которая говорит мне, найдены ли различия или нет.
Во-вторых, если различия найдены, я должен знать элемент (или элементы), который отличается от остальных. Я планирую использовать непарные t-тесты, сравнивая каждую пару элементов (С B, с C.... D с E), чтобы знать, отличается ли элемент, чем другой. Так, в этой точке у меня есть информация списка элементов, которые дарят существенным различиям для других, например:
C is different than B
C is different than D
Но мне нужен универсальный алгоритм для эффективного определения с той информацией, какой элемент отличается, чем другие (C в примере, но мог быть больше чем один).
Оставляя в стороне статистические проблемы, вопрос мог быть (в общих чертах): "Учитывая информацию о равенстве/неравенстве каждой из пар элементов в наборе, как Вы могли определить element/s, который отличается от других?"
Кажется, проблема, где теория графов могла быть применена. Я использую язык Java для реализации, если это полезно.
Править: Элементы являются людьми, и измеренные значения являются временами, должен был выполнить задачу. Я должен обнаружить, кто берет слишком много или лишь немногих время для выполнения задачи в некоторой системе обнаружения мошенничества.
4 ответа
На всякий случай, если кому-то интересен финальный код, использующий 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");
}
}
}
}
Ваша редакция дает хорошие детали; спасибо,
Основываясь на этом, я бы предположил довольно хорошее распределение времени (нормальное или, возможно, гамма; зависит от того, насколько близко к нулю ваше время) для типичных ответов. Отказ от выборки из этого распределения может быть таким же простым, как вычисление стандартного отклонения и определение того, какие образцы лежат более чем на n стандартных отклонений от среднего, или столь же сложным, как взятие подмножеств, исключающих выбросы, до тех пор, пока ваши данные не превратятся в хорошую кучу (например, среднее перестает двигаться "много").
Теперь у вас есть дополнительная морщинка, если вы предположите, что человек, который обезьянничал с одним испытанием, будет обезьянничать с другим. Таким образом, вы буквально пытаетесь отличить человека, который оказывается быстрым (или медленным), от того, кто «жульничает». Вы можете сделать что-то вроде вычисления ранга stdev для каждой оценки (я забыл для этого правильное название: если значение на два stdev выше среднего, оценка будет «2»), и использовать это в качестве статистики.
Затем, учитывая эту новую статистику, вам нужно будет проверить несколько гипотез. Например, я подозреваю, что стандартное отклонение этой статистики будет выше для читеров, чем для тех, кто просто одинаково быстрее, чем другие люди, но вам потребуются данные, чтобы проверить это.
Удачи!
Вам нужно будет запустить парный t-тест (или любой другой парный тест, который вы хотите реализовать) и увеличить счетчики в хеше, где ключ - это человек, а счетчик - это количество раз, когда оно отличалось.
Думаю, у вас также может быть список массивов, содержащий объекты людей. Объект людей мог хранить их ID и счетчик времени, когда они были разными. Реализуйте сопоставимые, а затем вы можете отсортировать массив по количеству.
Если элементы в списке были отсортированы в числовом порядке, вы можете просматривать два списка одновременно, и любые различия можно легко распознать как вставки или удаления. Например,
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.