ما هي شجرة القرار؟

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

على سبيل المثال ، دعنا نتخيل أنك كنت تحاول تقييم ما إذا كان يجب عليك ركوب الأمواج أم لا ، يمكنك استخدام قواعد القرار التالية لاتخاذ قرار:

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

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

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

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

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

خوارزمية هانت (Hunt)، التي تم تطويرها في ستينيات القرن العشرين لنمذجة التعلم البشري في علم النفس، تشكل الأساس للعديد من خوارزميات شجرة القرار الشائعة، مثل ما يلي:

- ID3: يعود الفضل إلى Ross Quinlan في تطوير ID3، وهو اختصار لعبارة "المُقسِّم الثنائيّ التكراريّ 3". تستفيد هذه الخوارزمية من الانتروبيا وكسب المعلومات كمقاييس لتقييم التقسيمات المرشحة. يمكن العثور على بعض أبحاث Quinlan حول هذه الخوارزمية من عام 1986 هنا.

- C4.5: تعتبر هذه الخوارزمية تكرارًا لاحقًا لـ ID3، والذي تم تطويره أيضًا بواسطة Quinlan. يمكنها استخدام نسب كسب المعلومات أو الكسب لتقييم نقاط الانقسام داخل أشجار القرار.

- CART: المصطلح CART هو اختصار لعبارة "أشجار التصنيف والانحدار" وقد قدمه Leo Breiman. تستخدم هذه الخوارزمية عادة شوائب جيني (Gini) لتحديد السمة المثالية للانقسام عليها. تقيس شوائب جيني عدد المرات التي يتم فيها تصنيف سمة تم اختيارها عشوائيا بشكل خاطئ. عند التقييم باستخدام شوائب جيني ، تكون القيمة الأقل أكثر مثالية.

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

من الصعب تفسير الحصول على المعلومات دون مناقشة الانتروبيا أولاً. الانتروبيا هو مفهوم ينبع من نظرية المعلومات، التي تقيس شوائب قيم العينة. وتُعرَّف بالصيغة التالية، حيث:

• يمثل S مجموعة البيانات التي يتم حساب الإنتروبيا 
• c يمثل الفئات في المجموعة ، S
• p(c) تمثل نسبة نقاط البيانات التي تنتمي إلى الفئة c إلى عدد نقاط البيانات الإجمالية في المجموعة، S

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

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

حيث

• أ يمثل سمة معينة أو تسمية فئة معينة
• إنتروبي(S) هو إنتروبي مجموعة البيانات، S
• |Sv|/|S| يمثل نسبة القيم في S_v إلى عدد القيم في مجموعة البيانات، S.

دعونا نأخذ مثالاً لتوضيح هذه المفاهيم. تخيل أن لدينا مجموعة البيانات التعسفية التالية:

بالنسبة لمجموعة البيانات هذه ، تكون الإنتروبيا 0.94. يمكن حساب ذلك من خلال إيجاد نسبة الأيام التي يكون فيها "لعب التنس" هو "نعم" ، وهو 9/14 ، ونسبة الأيام التي يكون فيها "لعب التنس" هو "لا" ، وهو 5/14. بعد ذلك ، يمكن توصيل هذه القيم بصيغة الإنتروبيا أعلاه.

الإنتروبيا (تنس) = - (9/14) log2 (9/14) - (5/14) log2 (5/14) = 0.94

يمكننا بعد ذلك حساب اكتساب المعلومات لكل سمة على حدة. على سبيل المثال، سيكون اكتساب المعلومات للسمة «الرطوبة» كما يلي:

الربح (التنس والرطوبة) = (0.94) - (7/14) * (0.985) — (7/14) * (0.592) = 0.151

كملخص ،

- 7/14 يمثل نسبة القيم التي تساوي فيها الرطوبة "عالية" إلى إجمالي عدد قيم الرطوبة. في هذه الحالة ، يكون عدد القيم التي تساوي فيها الرطوبة "عالية" هو نفس عدد القيم التي تساوي فيها الرطوبة "طبيعية".

- 0.985 هي الإنتروبيا عندما تكون الرطوبة = "عالية"

- 0.59 هي الإنتروبيا عندما الرطوبة = "طبيعية"

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

شوائب جيني هي احتمال تصنيف نقطة البيانات العشوائية بشكل غير صحيح في مجموعة البيانات إذا تم تصنيفها بناء على التوزيع الطبقي لمجموعة البيانات. على غرار الانتروبيا، إذا تم ضبطها، S ، فهي نقية—أي تنتمي إلى فئة واحدة) إذن، شوائبها صفر. يشار إلى ذلك بالصيغة التالية:

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

• - سهولة التفسير: المنطق المنطقي والتمثيلات المرئية لأشجار القرار تجعل من السهل فهمها واستهلاكها. كما أن الطبيعة الهرمية لشجرة القرارات تجعل من السهل معرفة السمات الأكثر أهمية، وهو ما لا يتضح دائمًا مع الخوارزميات الأخرى، مثل الشبكات العصبية.
  
  
• لا يتطلب data preparation إلا قليلاً أو لا يتطلب أي إعداد للبيانات: تتمتع أشجار القرار بعدد من الخصائص التي تجعلها أكثر مرونة من المصنفات الأخرى. يمكنها التعامل مع أنواع البيانات المختلفة—أي يمكن تحويل القيم المنفصلة أو المستمرة والقيم المستمرة إلى قيم فئوية من خلال استخدام العتبات. بالإضافة إلى ذلك، يمكنها أيضًا التعامل مع القيم ذات القيم المفقودة، والتي يمكن أن تكون مشكلة للمصنفات الأخرى، مثل بايز الساذج (Naïve Bayes).
  
  
• أكثر مرونة: يمكن استخدام شجرة القرار لعمليات التصنيف والانحدار، مما يجعلها أكثر مرونة من بعض خوارزميات الحل الأخرى. كذلك عدم الحساسية للعلاقات الأساسية بين السمات، هذا يعني أنه إذا كان هناك متغيران مرتبطان ارتباطا وثيقا ، فستختار الخوارزمية ميزة واحدة فقط للتقسيم عليها.

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