طريقة تدريجية لحساب الكميات لمجموعة كبيرة من البيانات

Question

أحتاج إلى حساب الكميات لمجموعة كبيرة من البيانات.

لنفترض أنه لا يمكننا الحصول على البيانات إلا من خلال بعض الأجزاء (أي صف واحد من مصفوفة كبيرة). لحساب كمية Q3 يحتاج المرء إلى الحصول على جميع أجزاء البيانات وتخزينها في مكان ما ، ثم فرزها وحساب الكمية:

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

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

ملحوظة:

• مجموعات البيانات هذه كبيرة حقًا (عناصر CA 5000 في كل صف)
• يمكن تقدير Q3 ، لا يجب أن تكون قيمة دقيقة.
• أدعو أجزاء من "صفوف" البيانات ، ولكن يمكن أن يكون لها leghts مختلفة! عادة ما لا يختلف كثيرا (+/- بضع مئات من العينات) ولكنه يختلف!

هذا السؤال مشابه ل خوارزميات "عبر الإنترنت" (ITerator) لتقدير الوسيط الإحصائي ، الوضع ، الانحراف ، التقرح, ، لكني بحاجة إلى حساب الكميات.

أيضا هناك عدد قليل من المقالات في هذا الموضوع ، أي:

• خوارزمية فعالة لمشكلة اختيار الوسيط التقريبي
• تقدير كمي إضافي للتتبع الضخم

قبل محاولة تنفيذ هذه الأساليب ، تساءلت عما إذا كانت هناك أي طرق أخرى أسرع لحساب الكمية 0.25/0.75؟

Answer 1

مستوحاة من هذا الجواب لقد قمت بإنشاء طريقة تقدر الكميات جيدة جدًا. إنه قرب بما يكفي لأغراضي.

الفكرة تتبع: الكمية 0.75 هي في الواقع وسيطة من جميع القيم التي تقع فوق الوسيط العالمي. وعلى التوالي ، 0.25 كمية هي وسيطة لجميع القيم أسفل الوسيط العالمي.

لذلك إذا تمكنا من تقريب الوسيط ، فيمكننا أن نتقارب الكميات بشكل مماثل.

double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;

foreach( var value in listOfValues) // or stream, or any other large set of data...
{
    median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{ 
    if(p.Int < median)
        q1 += eta*Math.Sign(p.Int - q1);
    else
        q3 += eta*Math.Sign(p.Int - q3);
}

ملاحظات:

• إذا كان توزيع بياناتك غريبًا ، فستحتاج إلى أكبر eta من أجل ملاءمة البيانات الغريبة. لكن الدقة ستكون أسوأ.
• إذا كان التوزيع غريبًا ، لكنك تعرف الحجم الكلي لمجموعتك (أي N) يمكنك ضبط eta المعلمة بهذه الطريقة: في مجموعة التسول eta لتكون متساوية تقريبا بعض القيمة الكبيرة (أي 0.2). مع مرور الحلقة ، خفض قيمة eta لذلك عندما تصل إلى نهاية المجموعة تقريبًا ، eta سيكون متساويًا تقريبًا 0 (على سبيل المثال ، في حلقة حسابها على هذا النحو: eta = 0.2 - 0.2*(i/N);

Answer 2

أنا الثاني فكرة استخدام الدلاء. لا تقصر نفسك على 100 دلاء - قد تستخدم أيضًا مليون. الجزء الصعب هو اختيار نطاقات الجرافة الخاصة بك بحيث لا ينتهي كل شيء في دلو واحد. ربما تكون أفضل طريقة لتقدير نطاقات الجرافة الخاصة بك هي أخذ عينة عشوائية معقولة من بياناتك ، وحساب الكميات بنسبة 10 ٪ و 90 ٪ باستخدام خوارزمية الفرز البسيطة ، ثم إنشاء دلاء متساوية في الحجم لملء هذا النطاق. هذا ليس مثاليًا ، ولكن إذا لم تكن بياناتك من توزيع فائق Weird ، فيجب أن تعمل.

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

Answer 3

هناك خوارزمية أكثر حداثة وأبسط بكثير لهذا يوفر تقديرات جيدة للغاية للكميات القصوى.

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

يرى https://github.com/tdunning/t-digest

Answer 4

1. استرجاع البيانات التي تحتاجها حقًا - أي ، مهما كانت القيمة (القيمة) التي يتم استخدامها/يتم استخدامها كمفتاح للفرز ، وليس كل شيء آخر مرتبط به.
2. من المحتمل أن تستخدم خوارزمية Tony Hoare الخاصة بـ Tony Hoare للعثور على الكمية بسرعة أكبر من فرز جميع البيانات.

Answer 5

إذا كانت بياناتك تحتوي على توزيع غاوسي ، فيمكنك تقدير الكميات من الانحراف المعياري. أفترض أن بياناتك ليست موزعة Gaussian أو كنت تستخدم فقط SD على أي حال.

إذا تمكنت من المرور عبر بياناتك مرتين ، فسأفعل ما يلي:

• الممر الأول ، حساب الحد الأقصى ، Min ، SD و Mean.
• الممر الثاني ، قسّم النطاق [دقيقة ، كحد أقصى] إلى عدد من الدلاء (على سبيل المثال 100) ؛ افعل الشيء نفسه لـ (يعني - 2*SD ، يعني + 2*SD) (مع دلاء إضافية للقيم المتطرفة). ثم قم بالركض من خلال البيانات مرة أخرى ، وقم بإلقاء الأرقام في هذه الدلاء.
• عد الدلاء حتى تكون بنسبة 25 ٪ و 75 ٪ من البيانات. إذا كنت ترغب في الحصول على فائدة إضافية ، فيمكنك الاستيفاء بين قيم الجرافة. (أي إذا كنت بحاجة إلى 10 ٪ من دلو لضرب الكمية الخامسة والعشرين ، افترض أن القيمة هي 10 ٪ من الطريق من الحد الأدنى إلى الحد الأعلى.)

يجب أن يمنحك هذا خوارزمية جيدة جدًا للوقت الذي يعمل بشكل جيد لمعظم مجموعات البيانات غير المنطقية.

Answer 6

Q-Digest هي خوارزمية تقريبية عبر الإنترنت تتيح لك حساب الكمية: http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

هنا تنفيذ:

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/quantiledigest.java