الغابة العشوائية

لقياس أهمية ميزة ما في مجموعة بيانات${\displaystyle {\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}}$في البداية، يتم تدريب نموذج الغابة العشوائية على البيانات. أثناء التدريب، يتم تسجيل خطأ العينة الخارجية لكل نقطة بيانات، ثم يتم حساب متوسطه على مستوى الغابة. (إذا لم يتم استخدام تجميع البيانات أثناء التدريب، فيمكننا بدلاً من ذلك حساب الأخطاء على مجموعة اختبار مستقلة).

بعد التدريب، تُبدَّل قيم الخاصية في عينات خارج الحقيبة، ويُعاد حساب خطأ خارج الحقيبة على مجموعة البيانات المُعدَّلة هذه. تُحسب أهمية الخاصية عن طريق حساب متوسط ​​الفرق في خطأ خارج الحقيبة قبل وبعد التبديل على جميع الأشجار. تُقسَّم النتيجة على الانحراف المعياري لهذه الفروق.

تُصنّف الخصائص التي تُنتج قيمًا عالية لهذا المؤشر على أنها أكثر أهمية من الخصائص التي تُنتج قيمًا منخفضة. وقد قدّم تشو وآخرون ^{[ 25 ]} التعريف الإحصائي لمقياس أهمية المتغير وحلّلوه .

تتضمن هذه الطريقة لتحديد أهمية المتغيرات بعض العيوب:

• عندما تحتوي السمات على أعداد مختلفة من القيم، تُفضّل الغابات العشوائية السمات ذات القيم الأكثر. تشمل حلول هذه المشكلة التباديل الجزئية ^{[ 26 ] [ 27 ] [ 28 ]} وتنمية الأشجار غير المتحيزة. ^{[ 29 ] [ 30 ]}
• إذا احتوت البيانات على مجموعات من السمات المترابطة ذات الصلة المماثلة، فإن المجموعات الأصغر تُفضّل على المجموعات الكبيرة. ^{[ 31 ]}
• في حال وجود سمات متداخلة، قد تفشل العملية في تحديد السمات المهمة. ويتمثل الحل في تبديل مجموعات السمات المترابطة معًا. ^{[ 32 ]}

يُركز هذا النهج في تحديد أهمية الميزات في الغابات العشوائية على المتغيرات التي تُقلل بشكل كبير من عدم التجانس أثناء عملية التقسيم. ^{[ 33 ]} وقد وُصف هذا النهج في كتاب "أشجار التصنيف والانحدار" لليو بريمان ^{[ 34 ]} ، وهو التطبيق الافتراضي في scikit learnلغة البرمجة R. التعريف هو:$${\displaystyle {\text{متوسط ​​الأهمية غير المعياري}}(x)={\frac {1}{n_{T}}}\sum _{i=1}^{n_{T}}\sum _{{\text{node }}j\in T_{i}|{\text{split variable}}(j)=x}p_{T_{i}}(j)\Delta i_{T_{i}}(j),}$$أين

• ${\displaystyle x}$هي ميزة
• ${\displaystyle n_{T}}$عدد الأشجار في الغابة
• ${\displaystyle T_{i}}$شجرة${\displaystyle i}$
• ${\displaystyle p_{T_{i}}(j)={\frac {n_{j}}{n}}}$هي نسبة العينات التي تصل إلى العقدة${\displaystyle j}$
• ${\displaystyle \Delta i_{T_{i}}(j)}$هل التغير في الشوائب في الشجرة${\displaystyle i}$عند العقدة${\displaystyle j}$.

يمكن استخدام الإحصائيات التالية كمقياس للشوائب للعينات التي تقع في عقدة معينة:

• إنتروبيا
• معامل جيني
• متوسط ​​مربع الخطأ

ثم يتم الحصول على الأهمية المعيارية عن طريق التطبيع على جميع الميزات، بحيث يكون مجموع أهمية الميزات المعيارية هو 1.

يمكن للتنفيذ الافتراضي scikit learnأن يبلغ عن أهمية الميزات بشكل مضلل: ^{[ 32 ]}

• يفضل السمات ذات العدد الكبير
• يستخدم إحصائيات التدريب وبالتالي لا يعكس مدى فائدة الميزة للتنبؤات على مجموعة الاختبار ^{[ 35 ]}

الغابة المركزية ^{[ 47 ]} هي نموذج مبسط للغابة العشوائية الأصلية لبريمان، حيث يتم اختيار سمة واحدة بشكل عشوائي من بين جميع السمات، ثم يتم تقسيم الخلية في مركزها بناءً على هذه السمة المختارة مسبقًا. تتوقف الخوارزمية عندما يتم إنشاء شجرة ثنائية كاملة من المستوى${\displaystyle k}$تم بناؤها، حيث${\displaystyle k\in \mathbb {N} }$هو أحد معلمات الخوارزمية.

الغابة الموحدة ^{[ 48 ]} هي نموذج مبسط آخر للغابة العشوائية الأصلية لبريمان، والتي تختار بشكل موحد ميزة من بين جميع الميزات وتقوم بعمليات تقسيم عند نقطة مرسومة بشكل موحد على جانب الخلية، على طول الميزة المحددة مسبقًا.

بالنظر إلى عينة تدريبية ${\displaystyle {\mathcal {D}}_{n}=\{(\mathbf {X} _{i},Y_{i})\}_{i=1}^{n}}$ل${\displaystyle [0,1]^{p}\times \mathbb {R} }$متغيرات عشوائية مستقلة ذات قيم موزعة كزوج نموذجي مستقل${\displaystyle (\mathbf {X} ,Y)}$، أين${\displaystyle \operatorname {E} [Y^{2}]<\infty }$نهدف إلى التنبؤ بالاستجابة${\displaystyle Y}$، المرتبطة بالمتغير العشوائي${\displaystyle \mathbf {X} }$، من خلال تقدير دالة الانحدار${\displaystyle m(\mathbf {x} )=\operatorname {E} [Y\mid \mathbf {X} =\mathbf {x} ]}$غابة الانحدار العشوائي هي مجموعة من${\displaystyle M}$أشجار الانحدار العشوائية.${\displaystyle m_{n}(\mathbf {x} ,\mathbf {\Theta } _{j})}$القيمة المتوقعة عند النقطة${\displaystyle \mathbf {x} }$بواسطة${\displaystyle j}$الشجرة رقم -، حيث${\displaystyle \mathbf {\Theta } _{1},\ldots ,\mathbf {\Theta } _{M}}$هي متغيرات عشوائية مستقلة، موزعة كمتغير عشوائي عام${\displaystyle \mathbf {\Theta } }$بغض النظر عن العينة${\displaystyle {\mathcal {D}}_{n}}$يمكن استخدام هذا المتغير العشوائي لوصف العشوائية الناتجة عن تقسيم العقد وإجراءات أخذ العينات لبناء الشجرة. تُدمج الأشجار لتكوين تقدير الغابة المحدودة.${\displaystyle m_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{M}}\sum _{j=1}^{M}m_{n}(\mathbf {x} ,\Theta _{j})}$بالنسبة لأشجار الانحدار، لدينا$//$، أين${\displaystyle A_{n}(\mathbf {x} ,\Theta _{j})}$هل الخلية تحتوي${\displaystyle \mathbf {x} }$، مصمم بشكل عشوائي${\displaystyle \Theta _{j}}$ومجموعة البيانات${\displaystyle {\mathcal {D}}_{n}}$، و${\displaystyle N_{n}(\mathbf {x} ,\Theta _{j})=\sum _{i=1}^{n}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})}}$.

وبالتالي فإن تقديرات الغابات العشوائية تحقق، لجميع${\displaystyle \mathbf {x} \in [0,1]^{d}}$،${\displaystyle m_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{M}}\sum _{j=1}^{M}\left(\sum _{i=1}^{n}{\frac {Y_{i}\mathbf {1} _{\mathbf {X} _ {i}\in A_{n}(\mathbf {x} ,\Theta _{j})}}{N_{n}(\mathbf {x} ,\Theta _{j})}}\right)}$تعتمد غابة الانحدار العشوائي على مستويين من المتوسطات، أولهما على العينات في الخلية المستهدفة للشجرة، ثم على جميع الأشجار. وبالتالي، تكون مساهمات الملاحظات الموجودة في الخلايا ذات الكثافة العالية من نقاط البيانات أقل من مساهمات الملاحظات التي تنتمي إلى الخلايا الأقل كثافة. ولتحسين طرق الغابة العشوائية وتعويض سوء التقدير، عرّف سكورنيت ^{[ 43 ]} غابة الانحدار العشوائي المحسّنة (KeRF) على النحو التالي: $${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{\sum _{j=1}^{M}N_{n}(\mathbf {x} ,\Theta _{j})}}\sum _{j=1}^{M}\sum _{i=1}^{n}Y_{i}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})},}$$ وهو ما يساوي متوسط${\displaystyle Y_{i}}$يسقط في الخلايا التي تحتوي${\displaystyle \mathbf {x} }$في الغابة. إذا حددنا دالة الاتصال لـ${\displaystyle M}$الغابة المحدودة كـ${\displaystyle K_{M,n}(\mathbf {x} ,\mathbf {z} )={\frac {1}{M}}\sum _{j=1}^{M}\mathbf {1} _{\mathbf {z} \in A_{n}(\mathbf {x} ,\Theta _{j})}}$أي نسبة الخلايا المشتركة بين${\displaystyle \mathbf {x} }$و${\displaystyle \mathbf {z} }$إذن، من شبه المؤكد أننا قد حصلنا على${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {\sum _{i=1}^{n}Y_{i}K_{M,n}(\mathbf {x} ,\mathbf {x} _{i})}{\sum _{\ell =1}^{n}K_{M,n}(\mathbf {x} ,\mathbf {x} _{\ell })}}}$، وهو ما يحدد KeRF.

بناء مركز KeRF من المستوى${\displaystyle k}$وهو نفس ما ينطبق على الغابة المركزية، باستثناء أن التنبؤات تتم بواسطة${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})}$، دالة النواة المقابلة، أو دالة الاتصال هي $${\displaystyle K_{k}^{cc}(\mathbf {x} ,\mathbf {z} )=\sum _{k_{1},\ldots ,k_{d},\sum _{j=1}^{d}k_{j}=k}{\frac {k!}{k_{1}!\cdots k_{d}!}}\left({\frac {1}{d}}\right)^{k}\prod _{j=1}^{d}\mathbf {1} _{\lceil 2^{k_{j}}x_{j}\rceil =\lceil 2^{k_{j}}z_{j}\rceil },\qquad {\text{ for all }}\mathbf {x} ,\mathbf {z} \in [0,1]^{d}.}$$

يتم بناء نموذج KeRF الموحد بنفس طريقة بناء نموذج الغابة الموحدة، باستثناء أن التنبؤات تتم بواسطة${\displaystyle {\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})}$، دالة النواة المقابلة، أو دالة الاتصال هي $${\displaystyle K_{k}^{uf}(\mathbf {0} ,\mathbf {x} )=\sum _{k_{1},\ldots ,k_{d},\sum _{j=1}^{d}k_{j}=k}{\frac {k!}{k_{1}!\ldots k_{d}!}}\left({\frac {1}{d}}\right)^{k}\prod _{m=1}^{d}\left(1-|x_{m}|\sum _{j=0}^{k_{m}-1}{\frac {\left(-\ln |x_{m}|\right)^{j}}{j!}}\right){\text{ for all }}\mathbf {x} \in [0,1]^{d}.}$$

تكون التنبؤات التي يقدمها كل من KeRF والغابات العشوائية متقاربة إذا تم التحكم في عدد النقاط في كل خلية:

افترض وجود متتابعات${\displaystyle (a_{n}),(b_{n})}$بحيث يكون ذلك، على الأرجح، $${\displaystyle a_{n}\leq N_{n}(\mathbf {x} ,\Theta )\leq b_{n}{\text{ and }}a_{n}\leq {\frac {1}{M}}\sum _{m=1}^{M}N_{n}{\mathbf {x} ,\Theta _{m}}\leq b_{n}.}$$ ثم على الأرجح، $${\displaystyle |m_{M,n}(\mathbf {x} )-{\tilde {m}}_{M,n}(\mathbf {x} )|\leq {\frac {b_{n}-a_{n}}{a_{n}}}{\tilde {m}}_{M,n}(\mathbf {x} ).}$$

عندما يكون عدد الأشجار${\displaystyle M}$إذا اتجهنا إلى ما لا نهاية، فسنحصل على غابة عشوائية لانهائية وKeRF لانهائية. وتكون تقديراتهما متقاربة إذا كان عدد الملاحظات في كل خلية محدودًا.

افترض وجود متتابعات${\displaystyle (\varepsilon _{n}),(a_{n}),(b_{n})}$بحيث يكون ذلك، على الأرجح

• ${\displaystyle \operatorname {E} [N_{n}(\mathbf {x} ,\Theta )]\geq 1,}$
• ${\displaystyle \operatorname {P} [a_{n}\leq N_{n}(\mathbf {x} ,\Theta )\leq b_{n}\mid {\mathcal {D}}_{n}]\geq 1-\varepsilon _{n}/2,}$
• ${\displaystyle \operatorname {P} [a_{n}\leq \operatorname {E} _{\Theta }[N_{n}(\mathbf {x} ,\Theta )]\leq b_{n}\mid {\mathcal {D}}_{n}]\geq 1-\varepsilon _{n}/2,}$

ثم على الأرجح، $${\displaystyle |m_{\infty ,n}(\mathbf {x} )-{\tilde {m}}_{\infty ,n}(\mathbf {x} )|\leq {\frac {b_{n}-a_{n}}{a_{n}}}{\tilde {m}}_{\infty ,n}(\mathbf {x} )+n\varepsilon _{n}\left(\max _{1\leq i\leq n}Y_{i}\right).}$$

توفير${\displaystyle k\rightarrow \infty }$و${\displaystyle n/2^{k}\rightarrow \infty }$يوجد ثابت${\displaystyle C_{1}>0}$بحيث يكون ذلك، بالنسبة للجميع${\displaystyle n}$، ${\displaystyle \mathbb {E} [{\tilde {m}}_{n}^{cc}(\mathbf {X} )-m(\mathbf {X} )]^{2}\leq C_{1}n^{-1/(3+d\log 2)}(\log n)^{2}}$.

توفير${\displaystyle k\rightarrow \infty }$و${\displaystyle n/2^{k}\rightarrow \infty }$يوجد ثابت${\displaystyle C>0}$بحيث، ${\displaystyle \mathbb {E} [{\tilde {m}}_{n}^{uf}(\mathbf {X} )-m(\mathbf {X} )]^{2}\leq Cn^{-2/(6+3d\log 2)}(\log n)^{2}}$.