شجرة التصنيف والانحدار/CART

CART هي طريقة تعلم لتوزيع الاحتمالات الشرطية للمتغير العشوائي الناتج Y مع الأخذ في الاعتبار المتغير العشوائي المدخل X.

تعريف

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

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

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

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

إنشاء أشجار الانحدار

افترض أن X وY هما متجهان للإدخال والإخراج على التوالي، وأن Y هو متغير مستمر. بالنظر إلى مجموعة بيانات التدريب فكر في كيفية إنشاء شجرة انحدار.

تتوافق شجرة الانحدار مع قسم من مساحة الإدخال (أي مساحة الميزة) وقيمة الإخراج لكل وحدة في القسم. افترض أن مساحة الإدخال قد تم تقسيمها إلى وحدات M $latex R_{1}، R_{2}، \ldots، R_{M}$ وهناك قيمة إخراج ثابتة $latex c_{m} $ على كل وحدة $latex R_{m} $ ثم يمكن التعبير عن نموذج شجرة الانحدار على النحو التالي $latex f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right) $

عند تحديد تقسيم مساحة الإدخال، يمكن استخدام خطأ التربيع$latex \sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$

لتمثيل خطأ التنبؤ لشجرة الانحدار لبيانات التدريب، يتم حل قيمة الإخراج المثلى لكل وحدة باستخدام معيار خطأ المربع الأدنى. من السهل أن نرى أن القيمة المثلى $latex c_{m} $ للوحدة $latex R_{m} $ هي متوسط الناتج $latex y_{i} $ لجميع حالات الإدخال $latex x_{i} $ على $latex R_{m} $، أي

السؤال هو كيفية تقسيم مساحة الإدخال. هنا نستخدم طريقة استدلالية لاختيار الأول ج المتغيرات $latex x^{(j)}$ والقيم التي يأخذها س ، كمتغير التجزئة ونقطة التجزئة، وتحديد منطقتين:

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

للمتغيرات المدخلة الثابتة ج يمكن العثور على نقطة الانقسام المثالية س

قم باجتياز جميع متغيرات الإدخال والعثور على متغير التجزئة الأمثل ج ، مما يشكل زوجًا $latex (j، s) $، والذي بدوره يقسم مساحة الإدخال إلى منطقتين. ثم يتم تكرار عملية التقسيم أعلاه لكل منطقة حتى يتم الوصول إلى شرط التوقف.

إنشاء أشجار التصنيف

تستخدم شجرة التصنيف مؤشر جيني لاختيار الميزة المثلى وتحديد نقطة القطع الثنائية المثلى للميزة.

مؤشر جيني

في عملية التصنيف، بافتراض وجود K فئة، فإن احتمال أن تنتمي نقطة العينة إلى الفئة k هو $latex p_{k} $، ثم يتم تعريف مؤشر جيني لتوزيع الاحتمالات على النحو التالي:

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

بالنسبة لمجموعة العينة D المعينة، فإن مؤشر جيني الخاص بها هو:

ومن بينها، $latex C_{k} $ هي المجموعة الفرعية من العينات في D التي تنتمي إلى الفئة k، وK هو عدد الفئات.

إذا تم تقسيم مجموعة العينة D إلى قسمين، $latex D_{1}$ و$latex D_{2}$، وفقًا لما إذا كانت الميزة A تأخذ قيمة محتملة معينة a، فإن هذا يكون:

ثم تحت شرط الميزة A، يتم تعريف مؤشر جيني للمجموعة D على النحو التالي:

يمثل مؤشر جيني $latex {Gini}(D) $ عدم اليقين للمجموعة D، ويمثل مؤشر جيني $latex {Gini}(D, A) $ عدم اليقين للمجموعة D بعد التقسيم بواسطة A=a. كلما كان مؤشر جيني أكبر، كلما كان عدم اليقين في مجموعة العينة أكبر، وهو ما يشبه الإنتروبيا.

الخوارزميات التوليدية

الإدخال: مجموعة بيانات التدريب D، شروط إيقاف الحساب

الإخراج: شجرة قرار CART

وفقًا لمجموعة بيانات التدريب، بدءًا من العقدة الجذرية، قم بإجراء العمليات التالية بشكل متكرر على كل عقدة لبناء شجرة قرار ثنائية:

1. افترض أن مجموعة بيانات التدريب الخاصة بالعقدة هي D، واحسب معامل جيني للميزات الموجودة لمجموعة البيانات. في هذا الوقت، لكل ميزة A، ولكل قيمة ممكنة a، يتم تقسيم D إلى قسمين، $latex D_{1} $ و$latex D_{2} $، وفقًا لما إذا كان اختبار نقطة العينة A=a هو "نعم" أو "لا"، ويتم حساب مؤشر جيني عندما A=a
2. من بين جميع الميزات الممكنة A وجميع نقاط الانقسام الممكنة a، حدد الميزة ذات أصغر مؤشر جيني ونقطة الانقسام المقابلة لها باعتبارها الميزة المثالية ونقطة الانقسام المثالية. بناءً على الميزة المثالية ونقطة الانقسام المثالية، قم بإنشاء عقدتين فرعيتين من العقدة الحالية وقم بتوزيع مجموعة بيانات التدريب على العقدتين الفرعيتين وفقًا للميزات.
3. قم باستدعاء (1) و (2) بشكل متكرر للعقدتين الفرعيتين حتى يتم استيفاء شرط التوقف.
4. إنشاء شجرة قرار CART