شجرة القرار المتناوبة

شجرة القرار المتناوبة (ADTree) هي طريقة تعلم آلي للتصنيف. وهي تعمم أشجار القرار وترتبط بتقنية التعزيز .

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

طُوِّرت خوارزمية ADTrees بواسطة يواف فرويند وليو ماسون. ^{[ 1 ]} إلا أن الخوارزمية بصيغتها الأصلية احتوت على عدة أخطاء مطبعية. وقد قُدِّمت توضيحات وتحسينات لاحقة بواسطة برنارد بفاهرينجر وجيفري هولمز وريتشارد كيركبي. ^{[ 2 ]} وتتوفر تطبيقاتها في برنامجي Weka وJBoost.

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

يؤدي تعزيز متعلم بسيط إلى مجموعة غير منظمة من${\displaystyle T}$تُصعّب الفرضيات استنتاج الارتباطات بين السمات. تُضفي أشجار القرار المتناوبة بنيةً على مجموعة الفرضيات من خلال اشتراط بنائها على فرضيةٍ تمّ التوصل إليها في تكرارٍ سابق. ويمكن تمثيل مجموعة الفرضيات الناتجة في شجرةٍ بناءً على العلاقة بين كل فرضيةٍ و"فرضيتها الأصلية".

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

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

مثال

تم إنشاء الشجرة التالية باستخدام JBoost على مجموعة بيانات spambase ^{[ 3 ]} (المتاحة من مستودع UCI للتعلم الآلي). ^{[ 4 ]} في هذا المثال، تم ترميز البريد العشوائي على النحو التالي:1 ويتم ترميز البريد الإلكتروني العادي على النحو التالي:-1 .

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

حالة يجب تصنيفها

ميزة	قيمة
char_freq_bang	0.08
تردد الكلمات	0.4
أطول فترة تشغيل رأس المال	4
تردد الحرف بالدولار	0
إزالة تردد الكلمة	0.9
تردد_الكلمة_جورج	0
ميزات أخرى	...

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

النتيجة للمثال المذكور أعلاه

التكرار	0	1	2	3	4	5	6
قيم المثيل	— غير متوفر	0.08 < 0.052 = f	0.4 < 0.195 = f	0 < 0.01 = t	0 < 0.005 = t	— غير متوفر	0.9 < 0.225 = f
تنبؤ	-0.093	0.74	-1.446	-0.38	0.176	0	1.66

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

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

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

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

• مجموعة من المدخلات${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$أين${\displaystyle x_{i}}$هو متجه من السمات و${\displaystyle y_{i}}$تكون إما -1 أو 1. وتسمى المدخلات أيضًا بالحالات.
• مجموعة من الأوزان${\displaystyle w_{i}}$بما يتوافق مع كل حالة.

العنصر الأساسي في خوارزمية ADTree هو القاعدة. تتكون القاعدة الواحدة من شرط مسبق، وشرط، وقيمتين. الشرط هو عبارة عن دالة منطقية على شكل "الخاصية <المقارنة> القيمة". الشرط المسبق هو ببساطة ربط منطقي بين شرطين. يتضمن تقييم القاعدة زوجًا من عبارات if المتداخلة.

1 إذا (شرط مسبق) 2 إذا (الشرط) 3. إرجاع النتيجة الأولى 4 وإلا 5 أعد النتيجة الثانية 6 نهاية الشرط 7 وإلا 8 إرجاع 0 9 نهاية إذا

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

• ${\displaystyle W_{+}(c)}$تُعيد مجموع أوزان جميع الأمثلة المصنفة إيجابياً والتي تحقق الشرط.${\displaystyle c}$
• ${\displaystyle W_{-}(c)}$تُعيد هذه الدالة مجموع أوزان جميع الأمثلة المصنفة سلبًا والتي تحقق الشرط.${\displaystyle c}$
• ${\displaystyle W(c)=W_{+}(c)+W_{-}(c)}$تُعيد مجموع أوزان جميع الأمثلة التي تُحقق الشرط${\displaystyle c}$

الخوارزمية كالتالي:

1 دالة ad_treeمجموعة إدخال مكونة من m من حالات التدريب 3 4 w i = 1/ m لجميع i 5 ${\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(صحيح)}{W_{-}(صحيح)}}}$ 6 R 0 = قاعدة ذات درجات a و 0 ، وشرط مسبق "صحيح" وشرط "صحيح". 7 ${\displaystyle {\mathcal {P}}=\{true\}}$ 8 ${\displaystyle {\mathcal {C}}=}$مجموعة جميع الشروط الممكنة 9 لـ${\displaystyle j=1\dots T}$ 10 ${\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}$احصل على القيم التي تقلل${\displaystyle z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)}$ 11 ${\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}$ 12 ${\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}$ 13 ${\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}$ 14 R j = قاعدة جديدة مع شرط مسبق p ، وشرط c ، وأوزان a 1 و a 2 15 ${\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}$ 16 نهاية لـ 17 مجموعة إرجاع R j

المجموعة${\displaystyle {\mathcal {P}}}$ينمو بمقدار شرطين مسبقين في كل تكرار، ومن الممكن استنتاج بنية الشجرة لمجموعة من القواعد من خلال ملاحظة الشرط المسبق المستخدم في كل قاعدة متتالية.

يوضح الشكل 6 في الورقة الأصلية ^{[ 1 ]} أن أشجار ADTrees عادةً ما تكون بنفس قوة أشجار القرار المعززة وجذوع القرار المعززة . وعادةً ما يمكن تحقيق دقة مكافئة باستخدام بنية شجرية أبسط بكثير من خوارزميات التقسيم المتكرر.

• مقدمة في تقنية التعزيز وأشجار القرار المتناوبة (تحتوي على العديد من الأمثلة الرسومية لأشجار القرار المتناوبة في الممارسة العملية).
• برنامج JBoost الذي ينفذ أشجار ADTrees.