التصنيف باستخدام خوارزمية شجرة القرار

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

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

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

مثال توضيحي

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

تركيبة شجرة تصنيف الزبائن:

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

ومن الملاحظ في الخوارزمية باعتبارها من خوارزميات التصنيف والتنبؤ فإنها تقسم البيانات في كل فرع بدون إنقاص أي منها. أي أن عدد السجلات الكلي في الفرع الأم يساوي مجموع السجلات في الفرعين المنبثقين منه.

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

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

استخدام شجره القرار في التنبؤ

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

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

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

1. القسم الأول منها ينطبق عليهم السؤال
2. والقسم الثاني لا ينطبق

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

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

تهذيب شجره القرار

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

الشكل أعلاه يوضح شجرة قرار تم تهذيبها.

ويظهر في الشكل أن الشجرة المهذبة أصغر وأقل تعقيدًا من الشجرة الأصلية. فالشجرة المهذبة أسهل للفهم وأسرع في تصنيف البيانات من الشجرة غير المهذبة.

وتنقسم عملية التهذيب إلى مرحلتين:

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

ويُلاحظ في الشكل أعلاه:

أنه تم استبدال الفرع (س3) كله واقتطاعه، واستبداله بورقة شجر واحدة وأعطيت القيمة (الفئة ب) حيث أنها الأكثر تكرارًا في أوراق الشجر في الفرع الذي تم اقتطاعه.

التكرار في شجرة القرار

بالرغم من أن عملية تهذيب شجرة القرار ينتج عنها شجرة مختصرة وأصغر من الشجرة الأصلية، إلاّ أنها يمكن أن تظل كبيرة ومعقدة نسبيًا ولأسباب أخرى، كأن تُعاني من التكرار (بالإنجليزية: Repetition) مما يجعلها صعبة التفسير.

الشكل التالي يوضح نموذج التكرار:

فالتكرار يحدث عند إعادة اختبار سمة من السمات في نفس الفرع في الشجرة، وذلك كما يظهر في الشكل أعلاه، حيث تم السؤال عن العمر أكثر من مرة في نفس الفرع.

الاستنساخ في شجرة القرار

الاستنساخ (بالإنجليزية: Replication) في خوارزمية شجرة القرار هو إعادة تكرار شجرة فرعية كاملة في أماكن متفرقة من الشجرة الرئيسية.

الشكل التالي يوضح الاستنساخ:

ويُلاحظ في الشكل كيف تكررت الشجرة الفرعية المعنونة بـ التصنيف الائتماني.

وسواء في حالة التكرار أو الاستنساخ فإنه تتأثر نسبة التغطية والفهم الصحيح للشجرة.

حل مشكلة التكرار والاستنساخ

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

القاعدة الأولى:

العمر أصغر من 60

القاعدة الثانية:

العمر أكبر من 45

فإنه يمكن دمج القاعدتين أو الشرطين معاً باستخدام معامل الربط المنطقي (و) بالإنجليزية: AND)، ليصبح شكل قاعدة التصنيف كما يلي:

العمر أصغر من 60 وأكبر من 45

كما يمكن استخدام طرق أخرى في تمثيل البيانات مثل قواعد الارتباط بدلا من أشجار القرار.

ويتم استنباط القواعد الشرطية (التي تشتمل على عبارات من نوع: إذا كان فإن) من تفرعات الشجرة.

المصدر

• كتاب التحليل المتقدم وتنقيب البيانات، د. م. مصطفى عبيد، إصدار: دار الفكر العربي، القاهرة، الطبعة الأولى، 2017.