زراعة أشجار اتخاذ القرار

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

تعمل معظم الخوارزميات المستخدَمة لتدريب أشجار القرارات باستخدام استراتيجية تقسيم و تقويض جشع. تبدأ الخوارزمية بإنشاء عقدة واحدة (الجذر) ثم تنمو شجرة القرارات بشكل تصاعدي ومتكرّر.

في كل عقدة، يتم تقييم جميع الشروط المحتمَلة واحتساب درجات لها. وتختَر الالتوائية الحالة "الأفضل"، أي الحالة التي تحقّق أعلى نتيجة. في الوقت الحالي، ما عليك سوى معرفة أنّ النتيجة هي مقياس مرتبط بال tâche، ويتم اختيار الشروط لزيادة هذا المقياس إلى أقصى حدّ.

على سبيل المثال، في مجموعة بيانات Palmer Penguins (التي يتم استخدامها لأمثلة الرموز البرمجية لاحقًا في هذه الدورة التدريبية)، يبلغ طول مناقير معظم طيور البطريق من نوعَي Adelie وChinstrap أكثر من 16 مم، في حين أنّ طول مناقير معظم طيور البطريق من نوع Gentoo أصغر. لذلك، يقدّم الشرط bill_length_mm ≥ 16 توقّعات مثالية تقريبًا لأنواع البطريق Gentoo، ولكن لا يمكنه التفريق بين أنواع البطريق Adelies وChinstrap. من المرجّح أن تختار الخوارزمية هذا الشرط.

شرط واحد يؤدي إلى ورقة واحدة الشرط هو "bill_length_mm >= 16".
إذا كان الأمر كذلك، تكون الورقة من نوع "آديلي أو شريط الذقن".  إذا لم يكن الأمر كذلك، تكون الورقة
من النوع "Gentoo".

الشكل 7. الخطوة الأولى في زراعة شجرة

 

بعد ذلك، تتكرّر الخوارزمية بشكل متكرّر ومستقل في كلتا العقدتَين الفرعيتَين. عندما لا يتم العثور على أيّ شروط مُرضية، تصبح العقدة ورقة. يتم تحديد توقّع الأوراق على أنّه قيمة التصنيف الأكثر تمثيلاً في الأمثلة.

في ما يلي الخوارزمية:

def train_decision_tree(training_examples):
  root = create_root() # Create a decision tree with a single empty root.
  grow_tree(root, training_examples) # Grow the root node.
  return root

def grow_tree(node, examples):
  condition = find_best_condition(examples) # Find the best condition.

  if condition is None:
    # No satisfying conditions were found, therefore the grow of the branch stops.
    set_leaf_prediction(node, examples)
    return

  # Create two childrens for the node.
  positive_child, negative_child = split_node(node, condition)

  # List the training examples used by each children.
  negative_examples = [example for example in examples if not condition(example)]
  positive_examples = [example for example in examples if condition(example)]

  # Continue the growth of the children.
  grow_tree(negative_child, negative_examples)
  grow_tree(positive_child, positive_examples)

لنطّلِع على خطوات تدريب شجرة قرارات معيّنة بمزيد من التفصيل.

الخطوة 1: أنشئ جذرًا:

عقدة عليها علامة استفهام

الخطوة 2: توسيع العقدة رقم 1 تم العثور على الشرط "x1 ≥ 1". يتم إنشاء عقدتَين فرعيتَين:

عقدة جذر
   تؤدي إلى عقدتَين غير محدّدتَين

الخطوة 3: توسيع العقدة رقم 2 لم يتم العثور على أيّ شروط مُرضية. وبالتالي، عليك تحويل العقدة إلى ورقة:

عقدة جذر
   تؤدي إلى عقدتَين غير محدّدتَين

الخطوة 4: تنمية العقدة رقم 3 تم العثور على الشرط "x2 ≥ 0.5". يتم إنشاء node ثنتان فرعيتان.

عقدة جذر وحال
وثلاث أوراق

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

رمز YDF
في YDF، يتمّ إنشاء أشجار القرارات باستخدام خوارزمية "تقسيم واتّباع المنتصر" الموضّحة أعلاه تلقائيًا. بدلاً من ذلك، يمكنك تفعيل النمو العميق على مستوى الموقع باستخدام المَعلمة growing_strategy="BEST_FIRST_GLOBAL". راجِع المستندات للحصول على مزيد من التفاصيل.

استنادًا إلى عدد ميزات الإدخال ونوعها، يمكن أن يكون عدد الشروط المحتمَلة لعقدة معيّنة كبيرًا، أو غير محدود بشكل عام. على سبيل المثال، في حال توفّر شرط حدّ أدنى featureit، يكون مجموع كل قيم الحدّ الأدنى الвозможного tR لانهائيًا.

يُطلق على الإجراء المسؤول عن العثور على أفضل شرط اسم المقسِّم. ولأنّها تحتاج إلى اختبار الكثير من الشروط المحتمَلة، فإنّ العناصر المُقسّمة تشكّل عنق الزجاجة عند تدريب شجرة القرارات.

تعتمد النتيجة التي يحقّقها المُقسِّم على المهمة. على سبيل المثال:

هناك العديد من خوارزميات التقسيم، ولكل منها ميزات مختلفة تشمل ما يلي:

  • نوع السمات، على سبيل المثال، رقمية أو فئوية أو نصية
  • المهمة، على سبيل المثال، التصنيف الثنائي والتصنيف المتعدّد الفئات والانحدار
  • نوع الشرط، على سبيل المثال، شرط الحدّ الأدنى، أو شرط ضمن المجموعة، أو شرط مائل
  • معايير التنظيم، على سبيل المثال، الفواصل الدقيقة أو التقريبية لشروط الحدود الدنيا

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

رمز YDF
في YDF، يتم اختيار المُقسِّمات بشكل ضمني من نوع الميزة الذي يتم رصده تلقائيًا (أو يتم تحديده يدويًا)، والمَعلمات الفائقة، وسرعة كل مُقسِّم مقدَّرة (أثناء التدريب، يُشغِّل YDF نموذجًا صغيرًا لتوقّع سرعة كل مُقسِّم مُحتمَل).