خوارزمية فعالة للكشف عن عناصر مختلفة في مجموعة

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 باستخدام الحزمة الإحصائية التي قدمتها أباتشي العموم الرياضيات.لا مشاكل حتى الآن أنا الحصول على منطقية أن يقول لي ما إذا كانت الاختلافات موجودة أو لا.

الثاني, إذا الاختلافات وجدت أنني بحاجة إلى معرفة عنصر (أو العناصر) التي تختلف عن بقية.أنا تخطط لاستخدام المفردة t-اختبارات, ومقارنة كل زوج من العناصر (A مع B مع C ....د مع ه) ، لمعرفة إذا كان عنصر يختلف عن الآخر.حتى في هذه النقطة لدي معلومات من قائمة العناصر التي تشكل الخلافات مع الآخرين, على سبيل المثال:

C is different than B
C is different than D

ولكن أنا في حاجة الى عام خوارزمية بكفاءة تحديد ، مع أن هذا العنصر هو مختلف عن الآخرين (C في المثال ، ولكن يمكن أن يكون أكثر من واحد).

وترك المسائل الإحصائية جانبا مسألة يمكن أن تكون (عامة): "نظرا المعلومات حول المساواة/عدم المساواة في كل واحدة من أزواج العناصر في مجموعة, كيف يمكنك تحديد العنصر/s هو/هي مختلفة عن الآخرين؟"

يبدو أن مشكلة حيث الرسم البياني نظرية يمكن تطبيقها.أنا باستخدام جافا لغة التنفيذ ، إذا كان ذلك مفيدا.

تحرير: العناصر الناس و القيم المقاسة هي الأوقات اللازمة لإتمام المهمة.أنا بحاجة إلى الكشف عن من هو أخذ الكثير أو القليل جدا من الوقت لإكمال المهمة في نوع من الاحتيال نظام الكشف.

Answer 1

فقط في حالة اهتمام أي شخص بالرمز النهائي ، باستخدام أباتشي كومونز الرياضيات لجعل العمليات الإحصائية ، و الدفين للعمل مع مجموعات من الأنواع البدائية.

إنه يبحث عن العنصر (العوامل) التي تحتوي على أعلى درجة (تعتمد الفكرة على التعليقات التي أدلى بها 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

تحرير الخاص بك يعطي جيدة التفاصيل ؛ شكرا

على أساس أنني أفترض إلى حد ما حسن تصرف توزيع مرات (عادي أو ربما غاما;يعتمد على مدى ما يقرب من الصفر الخاص بك تحصل على أوقات) على الردود نموذجية.رفض عينة من هذا التوزيع يمكن أن تكون بسيطة مثل حساب الانحراف المعياري ورؤية التي عينات الكذب أكثر من ن stdevs من الوسط أو معقدة كما أخذ فرعية التي استبعاد القيم الشاذة حتى البيانات الخاصة بك يستقر في لطيفة كومة (مثلا ، يعني توقف التحرك 'كثيرا').

الآن لديك إضافة التجاعيد إذا كنت تفترض أن الشخص الذي القرود مع واحد محاكمة القرد مع آخر.لذلك كنت erally تحاول أن تميز بين الشخص الذي يحدث لمجرد أن يكون سريع (أو بطيئة) مقابلواحد الذي هو "الغش".هل يمكن أن تفعل شيئا مثل حساب الشبكة على رتبة كل درجة (نسيت الاسم الصحيح لهذا:إذا كانت قيمة اثنين stdevs فوق يعني النتيجة '2') ، استخدم مثل الإحصائية.

ثم بالنظر إلى هذا الجديد إحصائية ، هناك بعض الفرضيات سوف تحتاج إلى اختبار.E. g. ، في ظني هو أن stdev من هذه الإحصائية سوف يكون أعلى الغشاشين من شخص هو مجرد موحد أسرع من غيرها من الناس-ولكن كنت في حاجة إلى بيانات للتحقق من ذلك.

حظا سعيدا مع ذلك!

Answer 3

يجب عليك تشغيل اختبار t المقترن (أو أي اختبار زوج الذي تريد تنفيذه) والزيادة في التهم في التجزئة حيث يكون المفتاح هو الشخص والعد هو أوقات العدد التي كان مختلفًا.

أعتقد أنه يمكن أن يكون لديك أيضًا قائمة ArrayList التي تحتوي على كائنات للأشخاص. يمكن للكائن الأشخاص تخزين هويتهم وتهم الوقت الذي كانوا مختلفون. قم بتنفيذ قابلة للمقارنة وبعد ذلك يمكنك فرز قائمة ArrayList حسب العد.

Answer 4

إذا تم فرز العناصر الموجودة في القائمة بالترتيب العددي ، فيمكنك المشي قائمتين في وقت واحد ، ويمكن بسهولة التعرف على أي اختلافات كإدراج أو عمليات حذف. علي سبيل المثال

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.