شجرة القرار البديلة Alternating decision tree

شجرة القرار البديلة (ADTree) هي طريقة من طرق التعلم الآلي تستخدم لحل مسائل للتصنيف. هذا النواع من أشجار القرار تعمل على تعمييم أشجار القرار العادية و لديها روابط للتعزيز Boosting. التعزيز Boosting في التعلم الآلي ، عبارة عن خوارزمية وصفية جماعية لتقليل التحيز Bias بشكل أساسي ، وكذلك التباين variance في التعلم الخاضع للإشراف.

تتكون شجرة القرار البديلة ADTree من بديل لعقد القرار decision nodes ، والتي تحدد الشرط الأساسي، وعقد التنبؤ prediction nodes ، التي تحتوي على رقم واحد. يتم تصنيف عينة ما بواسطة ADTree باتباع جميع المسارات التي تكون عندها جميع عقد القرار صحيحة ، وتلخيص أي عقد تنبؤية يتم اجتيازها.

عادةً تستخدم خوارزميات التعزيز الأصلية Original boosting algorithms إما جذوع القرار أو أشجار القرار كفرضيات ضعيفة. على سبيل المثال ، يؤدي تعزيز جذوع القرار boosting decision stumps إلى إنشاء مجموعة من جذوع القرار الموزونة بالوزن T (حيث T هو عدد التكرارات المعززة boosting iterations )، والتي تصوت بعد ذلك على التصنيف النهائي وفقًا لأوزانها. يتم ترجيح جذوع القرار الفردية وفقًا لقدرتها على تصنيف البيانات.

ينتج عن تعزيز المتعلم البسيط  Boosting a simple learner مجموعة غير منظمة من فرضيات T ، مما يجعل من الصعب استنتاج الارتباطات بين السمات. تقدم أشجار القرار البديلة بنية لمجموعة الفرضيات من خلال مطالبتهم ببناء فرضية تم إنتاجها في تكرار سابق. يمكن تصور مجموعة الفرضيات الناتجة في شجرة ما بناءً على العلاقة بين الفرضية و “أصلها”.

ميزة أخرى مهمة للخوارزميات المعززة boosted algorithms  هي أن البيانات تُعطى توزيعًا مختلفًا في كل تكرار. يتم إعطاء العينات التي تم تصنيفها بشكل خاطئ وزنًا أكبر بينما يتم إعطاء العينات المصنفة بدقة وزنًا أقل.

هيكلية شجرة القرار البديلة ADTree

تتكون شجرة القرار البديلة من عقد القرار وعقد التنبؤ decision nodes and prediction nodes. تحدد عقد القرار الشرط الأساسي. تحتوي عقد التنبؤ على رقم واحد. تحتوي أشجار ADT دائمًا على عقد توقع مثل الجذر والأوراق. و مثل ما ذكرنا سابقا اعلاه أنه يتم تصنيف عينة ما بواسطة ADTree عن طريق اتباع جميع المسارات التي تكون جميع عقد القرار فيها صحيحة وتلخيص أي عقد تنبؤ يتم اجتيازها. هذا يختلف عن مبدأ عمل أشجار التصنيف الثنائية مثل CART (شجرة التصنيف والانحدار Classification and regression tree) أو C4.5- C4.5 هي خوارزمية تستخدم لإنشاء أشجار القرار طورها روس كوينلان- حيث تتبع العينة مسارًا واحدًا فقط عبر الشجرة.

مثال

تم إنشاء الشجرة التالية باستخدام JBoost لمجموعة بيانات spambase (المتوفرة على موقع الـ UCI). في هذا المثال ، يتم ترميز البريد العشوائي على أنه 1 ويتم ترميز البريد الإلكتروني العادي كـ −1

An ADTree for 6 iterations on the Spambase dataset.

يحتوي الجدول التالي على جزء من النتائج لعينة واحدة.

يتم تقييم القيم المقدرة من خلال جمع كل عقد التنبؤ التي يمر من خلالها. في حالة المثال أعلاه ، يتم حساب النتيجة على أنها

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

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

يجب توخي الحذر عند تفسير العقد الفردية حيث تعكس الدرجات إعادة ترجيح البيانات في كل تكرار.

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

مدخلات خوارزمية شجرة القرار البديل هي:

  • مجموعة من المدخلات (x_1,y_1),\ldots,(x_m,y_m) حيث يكون متجهًا للسمات ويكون إما -1 أو 1. يُطلق على المدخلات أيضًا حالات .
  • مجموعة من الأوزان المقابلة لكل حالة.

العنصر الأساسي لخوارزمية ADTree هي القاعدة. تتكون القاعدة الواحدة من شرط مسبق precondition وشرط condition ودرجتين مقياسين scores . الشرط هو سند للشكل “قيمة السمة <المقارنة>”. الشرط المسبق هو ببساطة اقتران منطقي logical conjunction  للشروط. يتضمن تقييم القاعدة زوجًا من عبارات if المتداخلة:

تتطلب الخوارزمية أيضًا العديد من الدوال المساعدة:

W_+(c) تشير إلى مجموع الأوزان لجميع العينات ذات القيمة الموجبة التي تتقترب من قيمة المقدر c

W_-(c) تشير إلى مجموع الأوزان لجميع العينات ذات القيمة السالبة التي تتقترب من قيمة المقدر c

W(c) = W_+(c) + W_-(c) تشير إلى مجموع الأوزان لجميع العينات التي تتقترب من قيمة المقدر c

الخوارزمية هي على النحو التالي:

تتتطور أو تنمو المجموعة P بشرطين مُسبقين في كل تكرار ، ومن الممكن اشتقاق هيكل الشجرة لمجموعة من القواعد من خلال تدوين الشرط المسبق المستخدم في كل قاعدة متتالية.

Share on facebook
فاسبوك
Share on twitter
تويتر
Share on linkedin
لينكد إن
Share on whatsapp
واتساب

اترك تعليقاً

المشاركات الاخيرة

أحدث التعليقات

أفحص بحثك بالمجان

رفع الملف