كيفية اختيار عينات بيانات عشوائية (صغيرة) باستخدام الخريطة/تقليل؟

Question

أرغب في كتابة خريطة/تقليل الوظيفة لتحديد عدد من العينات العشوائية من مجموعة بيانات كبيرة استنادًا إلى حالة مستوى الصف. أريد تقليل عدد المفاتيح الوسيطة.

كود مزيف:

for each row 
  if row matches condition
    put the row.id in the bucket if the bucket is not already large enough

هل فعلت شيئًا كهذا؟ هل هناك أي خوارزمية معروفة؟

عينة تحتوي على صفوف متسلسلة جيدة أيضًا.

شكرًا.

Answer 1

يعمل نهج Karl بشكل جيد ، لكن يمكننا تقليل كمية البيانات التي تنتجها المخططات بشكل كبير.

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

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

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

في المخفض الخاص بك ، سيقوم Hadoop بالمسح تلقائيًا من خلال المفاتيح من أجل أدنى إلى أعلى. تنبعث من الصفوف المقابلة للأول ك المفاتيح التي تراها ( ك أدنى) ، ثم استقال.

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

Answer 2

MAPPERS: إخراج جميع القيم المؤهلة ، ولكل منها مفتاح عدد صحيح عشوائي.

مخفض واحد: إخراج قيم N الأولى ، ورمي المفاتيح.

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

بشكل عام ، أود أن أقوم ببناء أدوات Mapper/المخفض البسيطة مثل هذه التي تستخدم أكبر قدر ممكن من آلات Hadoop ؛ انتهى بي الأمر إعادة استخدامها في مهام مختلفة.

Answer 3

ربما يكون نهج Bkkbrad هو الأكثر كفاءة في أن عدد السجلات المرسلة من كل خريطة هي (على الأكثر) K. المخفض.

عندما لا يكون هذا هو الحال ، قد تميل إلى استخدام نهج موزعة بالكامل حيث يتم تعيين كل صف مطابق بواسطة Mapper عددًا صحيحًا عشوائيًا في {1 ، .. ، K} ثم تختار مرحلة الحد من عنصر واحد لكل مفتاح (انظر أيضا هذا السؤال). إن المشكلة في هذا النهج هي أنه قد يكون الأمر هو أنه من خلال الصدفة ، لا يتم تعيين صف إلى مفاتيح معينة ، وفي هذه الحالة سيكون للعينة النهائية أقل من عناصر K. على الرغم من أن هذا يحدث مع احتمال صغير إذا كان K أصغر بكثير من العدد الإجمالي للصفوف N ، إلا أنه سيحدث مع احتمال ثابت إذا كان K جزءًا ثابتًا من N (على سبيل المثال عندما يكون K = N/3).

الحل الذي يعمل هو ما يلي: لنفترض أن لدينا دلاء B وننشئ ترتيبًا عشوائيًا للعناصر أولاً عن طريق وضع كل عنصر في دلو عشوائي ثم إنشاء ترتيب عشوائي في كل دلو. تعتبر العناصر الموجودة في الدلو الأول أصغر (فيما يتعلق بالترتيب) من العناصر الموجودة في الدلو الثاني وما إلى ذلك. ثم ، إذا أردنا اختيار عينة من الحجم K ، فيمكننا جمع جميع العناصر في دلاء J الأولى إذا كانت تحتوي بشكل عام على عدد من العناصر أقل من K ، ثم اختر عناصر KT المتبقية من الدلو التالي. هنا B هي معلمة بحيث تناسب عناصر N/B الذاكرة. الجانب الرئيسي هو أنه يمكن معالجة الدلاء بالتوازي.

MAPPER: إخراج جميع الصفوف المؤهلة ، لكل منها مفتاح عشوائي (J ، R) ، حيث J هو عدد صحيح عشوائي في {1 ، .. ، b} و r هو تعويم عشوائي. بالإضافة إلى ذلك ، تتبع عدد العناصر مع مفتاح أقل من J (لـ 1 <= j <= b) ونقل هذه المعلومات إلى المخفضات.

خلط ورق اللعب: التقسيم فوق J ، والفرز الثانوي فوق ص.

المخفض: ضع في اعتبارك دلو J وافترض أن المخفض يعرف عدد العناصر الموجودة في دلاء أقل من J وكم في دلو J (عن طريق تجميع المعلومات التي يتلقاها المخططات). إذا كان عدد العناصر في الدلاء أقل أو متساوية من J أقل أو مساوية من K ، فإن جميع العناصر في دلو J ؛ إذا كان عدد العناصر التي تحتوي على دلو أقل تمامًا من J ، فسيتم تشغيل أخذ عينات من الخزان لاختيار العناصر العشوائية K - T من الدلو ؛ في الحالة المتبقية ، يكون ذلك عندما يكون عدد العناصر في الدلاء أقل من J على الأقل K ، لا تخرج أي شيء.

لست على دراية بحل أبسط لهذه المشكلة ، لكن سيكون من الجيد أن يكون هناك واحد.

يمكنك العثور على مزيد من التفاصيل هنا على مدونتي.