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

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

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

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

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

يمكن تلخيص خوارزمية شجرة القرار المتناوبة Alternating decision tree بالخطوات التالية:

1. تهيئة شجرة فارغة.
2. حدد ميزتين و قيمة عتبة لتقسيم البيانات إلى مجموعتين فرعيتين.
3. إذا كانت المجموعات الفرعية نقية (أي أن جميع الأمثلة تنتمي إلى نفس الفئة) ، فقم بإنشاء عقدة توقع مع تسمية الفئة المقابلة وقم بإرجاعها.
4. إذا تم الوصول إلى الحد الأقصى لعمق الشجرة ، فأنشئ عقدة توقع مع تسمية فئة الأغلبية وقم بإرجاعها.
5. إذا كانت العقدة الحالية هي عقدة قرار ، فأنشئ عقدتين فرعيتين وقم بتطبيق الخوارزمية بشكل متكرر على كل مجموعة فرعية.
6. إذا كانت العقدة الحالية هي عقدة توقع ، فقم بتحديث تسمية الفئة إذا كانت المجموعة الفرعية المقابلة لها فئة أغلبية مختلفة عن تسمية الفئة الحالية.
7. كرر الخطوات من 2 إلى 6 حتى يتم استيفاء معايير الإيقاف.

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

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

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

تتكون شجرة القرار البديلة من عقد القرار وعقد التنبؤ. تحدد عقد القرار الشرط الأساسي. بينما تحتوي عقد التنبؤ على رقم واحد. تحتوي هذه الخوارزمية دائمًا على عقد توقع مثل الجذر و الأوراق. و مثل ما ذكرنا سابقا اعلاه أنه يتم تصنيف عينة ما بواسطة الخوارزمية هذه عن طريق اتباع جميع المسارات التي تكون جميع عقد القرار فيها صحيحة وتلخيص أي عقد تنبؤ يتم اجتيازها. مبدأ عمل هذه الخوارزمية تختلف عن مبدأ عمل أشجار التصنيف الثنائية مثل (شجرة التصنيف و الانحدار Classification and regression tree).

مثال على الخوارزمية في بايثون

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

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

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

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

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

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

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

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

• مجموعة من المدخلات حيث يكون متجهًا للسمات ويكون إما -1 أو 1. يُطلق على المدخلات أيضًا حالات .
• مجموعة من الأوزان المقابلة لكل حالة.

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

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

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

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

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

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

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