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

تبدأ هذه الإجراءات من العقدة الأخيرة في الشجرة (أدنى نقطة). وباتباعها بشكل متكرر نحو الأعلى، تحدد مدى أهمية كل عقدة على حدة. إذا لم تُحدد أهمية العقدة للتصنيف، تُحذف أو تُستبدل بورقة. وتكمن ميزة هذه الطريقة في عدم فقدان أي أشجار فرعية ذات صلة. تشمل هذه الطرق: تقليم الخطأ المُخفَّض (REP)، وتقليم التعقيد ذي التكلفة الدنيا (MCCP)، وتقليم الخطأ الأدنى (MEP).

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

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

يؤدي تقليم تعقيد التكلفة إلى توليد سلسلة من الأشجار${\displaystyle T_{0}\dots T_{m}}$أين​​${\displaystyle T_{0}}$⁠ هي الشجرة الأولية و ⁠${\displaystyle T_{m}}$الجذر وحده. في الخطوة${\displaystyle i}$يتم إنشاء الشجرة عن طريق إزالة شجرة فرعية من الشجرة${\displaystyle i-1}$واستبدالها بعقدة طرفية بقيمة مختارة كما في خوارزمية بناء الشجرة. ويتم اختيار الشجرة الفرعية التي تتم إزالتها على النحو التالي:

1. حدد معدل الخطأ للشجرة${\displaystyle T}$على مجموعة البيانات${\displaystyle S}$كما​​${\displaystyle \operatorname {err} (T,S)}$⁠ .
2. الشجرة الفرعية${\displaystyle t}$ذلك يقلل${\displaystyle {\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}}$يتم اختيارها للإزالة.

الوظيفة​${\displaystyle \operatorname {prune} (T,t)}$يُعرّف الشجرة التي تم الحصول عليها عن طريق تقليم الأشجار الفرعية .${\displaystyle t}$من الشجرة​${\displaystyle T}$⁠ . بمجرد إنشاء سلسلة الأشجار، يتم اختيار أفضل شجرة عن طريق الدقة المعممة كما تم قياسها بواسطة مجموعة التدريب أو التحقق المتبادل.

من أمثلة التقليم المسبق تحديد الحد الأقصى لعمق شجرة القرار. لنفترض استخدام مجموعة بيانات تحتوي على 1000 عينة لتدريب مصنف، حيث يبني خوارزمية التدريب شجرة بعمق 20. تبلغ دقة التدريب 99%، لكنها تنخفض إلى 85% عند تطبيقها على مجموعة التحقق، مما يشير إلى فرط التخصيص. بتحديد عمق أقصى قدره 5 كمعيار للتقليم المسبق، يتم بناء شجرة أقل عمقًا بكثير، قد تحقق دقة تدريب 88% ودقة تحقق 87%، أي تعميمًا أفضل. ^{[ 2 ]} تشمل معايير التوقف الشائعة الأخرى للتقليم المسبق الحد الأدنى لعدد العينات لكل ورقة (مثل التوقف إذا احتوت عقدة على أقل من 10 عينات) أو عتبة لتقليل الشوائب.

لنفترض وجود شجرة قرار مبنية على مجموعة بيانات مقسمة إلى مجموعتي تدريب (80%) وتحقق (20%). بعد اكتمال نمو الشجرة على مجموعة التدريب، يقوم تقليم تقليل الخطأ بفحص كل عقدة غير طرفية من الأسفل إلى الأعلى. عند كل عقدة، يتم استبدال الشجرة الفرعية مؤقتًا بالفئة الأكثر شيوعًا للحالات التي تصل إلى تلك العقدة، ويتم تقييم الدقة على مجموعة التحقق. إذا حققت الشجرة المُقَلَّمة نفس دقة التحقق أو دقة أعلى، يتم استبدال الشجرة الفرعية بشكل دائم. على سبيل المثال، قد تؤدي عقدة ذات شجرة فرعية تُصنِّف 200 حالة تدريب بدقة 90%، بينما تُصنِّف ورقتها المُختزلة نفس الـ 200 حالة بدقة 88%، إلى تحسين دقة التحقق من 80% إلى 83%، مما ينتج عنه نموذج أبسط وأكثر قوة. ^{[ 3 ]}

يستخدم تقليم تعقيد التكلفة، المعروف أيضًا باسم تقليم أضعف حلقة، مُعامل ضبط α يُوازن بين حجم الشجرة وخطأ التدريب. بدءًا من شجرة كاملة، تُنتج الخوارزمية سلسلة من الأشجار الفرعية مع زيادة قيمة α. لكل قيمة α، يتم تحديد الشجرة الفرعية التي تُقلل من${\displaystyle {\text{error}}+\alpha \cdot ({\text{number leaves}})}$يتم اختيارها. على سبيل المثال، عند α = 0، تُحفظ الشجرة كاملةً؛ وعند α = 0.01، قد تكون الشجرة متوسطة الحجم هي الأمثل؛ وعند α = 0.1، قد تبقى العقدة الجذرية فقط. يتم اختيار أفضل قيمة لـ α من خلال التحقق المتقاطع ذي العشر طيات على مجموعة التدريب. هذه الطريقة هي أساس خطوة التقليم في خوارزمية CART. ^{[ 4 ]}

يُستخدم التقليم على نطاق واسع في التعلم العميق لضغط الشبكات العصبية عن طريق إزالة أوزان فردية (التقليم غير المنظم) أو خلايا عصبية/مرشحات كاملة (التقليم المنظم). ومن الأساليب غير المنظمة الشائعة التقليم القائم على الحجم: فبعد التدريب، تُضبط الأوزان ذات أصغر القيم المطلقة على الصفر. ثم تُضبط الشبكة بدقة لاستعادة دقتها. على سبيل المثال، قام هان وآخرون (2015) بتقليم شبكة AlexNet عن طريق إزالة أكثر من 90% من معاييرها مع انخفاض في الدقة أقل من 1%، مما يُظهر فعالية التقليم في ضغط النموذج وتسريع الاستدلال. ^{[ 5 ]} أما التقليم المنظم، حيث تُزال قنوات أو طبقات كاملة، فيمكنه إنتاج نماذج تعمل بكفاءة على الأجهزة القياسية دون الحاجة إلى عمليات المصفوفات المتفرقة.