Эффективный алгоритм обнаружения разных элементов в коллекции
https://stackoverflow.com/questions/2326399
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Представьте, что у вас есть набор из пяти элементов (AE) с некоторыми числовыми значениями измеряемого свойства (несколько наблюдений для каждого элемента, например «частота пульса»):
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}
Первый, мне нужно определить, есть ли существенные различия на средних уровнях.Поэтому я бегу в одну сторону Дисперсионный анализ используя Статистический пакет, предоставленный Apache Commons Math..Пока проблем нет, я получаю логическое значение, которое сообщает мне, найдены различия или нет.
Второй, если будут обнаружены различия, мне нужно знать элемент (или элементы), отличающийся от остальных.Я планирую использовать непарные t-критерии, сравнивая каждую пару элементов (А с Б, А с С....D с E), чтобы узнать, отличается ли один элемент от другого.Итак, на данный момент у меня есть информация о списке элементов, которые существенно отличаются от других, например:
C is different than B
C is different than D
Но мне нужен общий алгоритм, чтобы с помощью этой информации эффективно определить, какой элемент отличается от других (в примере C, но их может быть больше одного).
Оставляя в стороне статистические вопросы, вопрос мог бы звучать так (в общих чертах): «Учитывая информацию о равенстве/неравенстве каждой из пар элементов в коллекции, как вы можете определить элемент/ы, которые отличаются/отличаются от других?»
Кажется, это проблема, к которой можно применить теорию графов.Я использую Джава язык для реализации, если это полезно.
Редактировать: Элементы — это люди, а измеренные значения — это время, необходимое для выполнения задачи.Мне нужно определить, кто тратит слишком много или слишком мало времени на выполнение задачи, с помощью какой-то системы обнаружения мошенничества.
Решение
На всякий случай кого-то интересует окончательный код, используя Apache Commons Математика производить статистические операции и Находка работать с коллекциями примитивных типов.
Он ищет элемент(ы) с наивысшей степенью (идея основана на комментариях @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 стандартных отклонений, или настолько сложным, как взятие подмножеств, исключающих выбросы, до тех пор, пока ваши данные не соберутся в красивую кучу (например,среднее значение перестает «значительно» перемещаться).
Теперь у вас появится дополнительная проблема, если вы предположите, что человек, который обманывает одно испытание, будет обманывать и другое.Итак, вы изначально пытаетесь отличить человека, который просто оказался быстрым (или медленным), от человека, который просто работает быстро (или медленно).тот, кто «обманывает».Вы могли бы сделать что-то вроде вычисления стандартного ранга каждого балла (я забыл правильное название:если значение на два стандартного отклонения выше среднего, оценка равна «2») и используйте ее в качестве статистики.
Затем, учитывая эту новую статистику, вам нужно будет проверить несколько гипотез.Например, я подозреваю, что стандартное отклонение этой статистики будет выше для мошенников, чем для тех, кто одинаково быстрее других людей, но вам потребуются данные, чтобы проверить это.
Удачи в этом!
Вам придется запустить парный t-тест (или любой другой парный тест, который вы хотите реализовать) и увеличить счетчики в хэше, где ключом является Person, а счетчиком является количество раз, когда оно отличалось.
Я думаю, у вас также может быть массив arrayList, содержащий объекты людей.Объект «Люди» может хранить их идентификаторы и количество раз, когда они были разными.Реализуйте сравнение, и тогда вы сможете отсортировать список массивов по количеству.
Если элементы в списке были отсортированы в числовом порядке, вы можете просматривать два списка одновременно, и любые различия можно легко распознать как вставки или удаления.Например
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.
