الانتقال إلى المحتوى
العودة إلى نتائج البحث

شجرة القرار الفورية

قدّمه
Domingos, P. & Hulten, G.
السنة
2000
النوع
Incremental supervised classifier
العائلة
Machine learning

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

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

الفكرة الحدسية وراء الطريقة

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

التاريخ

الخوارزمية الأساسية، شجرة القرار السريعة جداً (VFDT) أو شجرة هوفدينغ، قدمها دومينغوس وهولتن في مؤتمر KDD عام 2000. طبقت متباينة هوفدينغ لتحديد الخطأ في اختيار سمات الانقسام من تدفق البيانات، مما أتاح استقراء الشجرة الصحيح تقاربياً دون تخزين الأمثلة. قام هولتن وسبنسر ودومينغوس بتوسيع هذا ليشمل تدفقات انجراف المفهوم في عام 2001. أصبح هذا النهج حجر الزاوية في إطار MOA (التحليل الضخم الفوري) وأثر على جيل من طرق التجميع الفورية.

متى تُستخدم

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

الحدود والاعتبارات

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

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

يصل كل مثال مُصنَّف واحداً تلو الآخر من تدفق البيانات. تقوم الشجرة بتوجيهه من الجذر عبر الانقسامات الموجودة إلى الورقة المناسبة، وتقدم تنبؤاً للحالة قبل تصنيفها.

2

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

3

يحدد حد هوفدينغ (أو تشيرنوف) إبسيلون = sqrt(R^2 * ln(1/delta) / (2n)) الحد الأقصى للخطأ بين أفضل سمة انقسام مُلاحَظة وأفضل انقسام حقيقي باحتمالية لا تقل عن 1 - دلتا. كلما زادت n، تقل إبسيلون نحو الصفر.

الصيغة
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}
4

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

5

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

الأخطاء الشائعة

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

الأسئلة الشائعة

كيف تختلف شجرة هوفدينغ عن شجرة قرار CART القياسية؟

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

هل تتعامل شجرة القرار الفورية مع انجراف المفهوم؟

لا تكتشف شجرة هوفدينغ الأساسية الانجراف تلقائياً. يمكن للإضافات مثل شجرة القرار السريعة جداً المتكيفة مع المفهوم (CVFDT) والإصدارات المدمجة مع كاشفات الانجراف ADWIN أو Page-Hinkley استبدال الأشجار الفرعية القديمة عند اكتشاف الانجراف.

ما هي فترة السماح وكيف يجب أن أضبطها؟

فترة السماح هي عدد الأمثلة التي تصل إلى ورقة بين التقييمات المتتالية للانقسام. تزيد القيمة الأكبر من تقليل الحساب ولكنها تؤخر الانقسامات؛ بينما تقوم القيمة الأصغر بتقييم الانقسامات بشكل متكرر بتكلفة وحدة معالجة مركزية أعلى. تتراوح القيم الافتراضية النموذجية من 200 إلى 1000 مثال.

هل شجرة القرار الفورية مناسبة لمجموعات البيانات الصغيرة والثابتة؟

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

كيف تقارن الدقة بالطرق الدفعية على مجموعة بيانات ثابتة؟

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

طرق ذات صلة

المصادر

  1. Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.

    افتح مرجع المنشور
    تم النسخ.
  2. Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.

    افتح مرجع DOI
    تم النسخ.