रैंडम फॉरेस्ट

This article is about मशीन सीखने की तकनीक. For अन्य प्रकार के बेतरतीब जंगल, see बेतरतीब जंगल.

File:Random forest diagram complete.png

एक बेतरतीब निर्णय जंगल का आरेख

यादृच्छिक वन या यादृच्छिक निर्णय वन सांख्यिकीय वर्गीकरण, प्रतिगमन विश्लेषण और अन्य कार्यों के लिए एक समेकित सीखने की विधि है ,जो प्रशिक्षण समय पर निर्णय ट्री सीखने की भीड़ का निर्माण करके संचालित होता है। वर्गीकरण कार्यों के लिए, बेतरतीब जंगल का उत्पादन अधिकांश ट्री के माध्यम से चयनित वर्ग है। प्रतिगमन कार्यों के लिए, अलग-अलग ट्री का माध्य या औसत पूर्वानुमान दिया जाता है। यादृच्छिक निर्णय वन अपने प्रशिक्षण सेट के लिए निर्णय पेड़ों की ओवरफट्टिंग की आदत के लिए सही हैं। रैंडम फॉरेस्ट सामान्यतः निर्णय ट्री सीखना से अधिक अच्छा प्रदर्शन करते हैं, किन्तु ग्रेडिएंट बूस्टेड ट्री की समानता में उनकी त्रुटिहीनता कम होती है। चूँकि, डेटा विशेषताएँ उनके प्रदर्शन पर प्रभाव डाल सकती हैं।

बेतरतीब निर्णय जंगलों के लिए पहला एल्गोरिथम 1995 में तिन कम हो के माध्यम से बनाया गया था इसमें बेतरतीब उपस्थान विधि का उपयोग किया गया था, जो हो के सूत्रीकरण में, यूजीन क्लेनबर्ग द्वारा प्रस्तावित वर्गीकरण के लिए "स्टोकेस्टिक भेदभाव" दृष्टिकोण को लागू करने का एक विधि है।

एल्गोरिथम का एक विस्तार लियो ब्रिमन के माध्यम से विकसित किया गया था और एडेल कटलर,जिसने पंजीकरण कराया 2006 में ट्रेडमार्क के रूप में बेतरतीब जंगल (as of 2019, जिसका स्वामित्व मिनिटैब, इंक.) के पास है। यह विस्तार ब्रीमन के बूटस्ट्रैप एकत्रीकरण विचार और सुविधाओं के क्रमहीनता चयन को जोड़ता है, जिसे पहले हो के माध्यम से प्रस्तुत किया गया थाऔर बाद में अमित और डोनाल्ड जेमन के माध्यम से स्वतंत्र रूप से नियंत्रित विचरण वाले निर्णय ट्री का संग्रह बनाने के लिए।

बेतरतीब जंगल का अधिकांशतः व्यवसायों में ब्लैक बॉक्स मॉडल के रूप में उपयोग किया जाता है, क्योंकि वे थोड़े विन्यास की आवश्यकता होने पर डेटा की एक विस्तृत श्रृंखला में उचित भविष्यवाणियां उत्पन्न करते हैं।

इतिहास

बेतरतीब निर्णय जंगलों की सामान्य विधि पहली बार 1995 में हो के माध्यम से प्रस्तावित की गई थी।हो ने स्थापित किया कि तिरछे हाइपरप्लेन के साथ बंटने वाले ट्री के जंगल त्रुटिहीनता प्राप्त कर सकते हैं क्योंकि वे ओवरट्रेनिंग से पीड़ित हुए बिना बढ़ते हैं, जब तक कि जंगलों को बेतरतीब रूप से एकमात्र चयनित फ़ीचर (मशीन लर्निंग) आयामों के प्रति संवेदनशील होने के लिए प्रतिबंधित किया जाता है। उसी प्रणाली पर आगे का कामनिष्कर्ष निकाला कि अन्य विभाजन विधियाँ समान रूप से व्यवहार करती हैं, जब तक कि वे असंबद्धता ढंग से कुछ फीचर आयामों के प्रति असंवेदनशील होने के लिए मजबूर हैं। ध्यान दें कि एक अधिक जटिल वर्गीकरणकर्ता (एक बड़ा जंगल) का यह अवलोकन एकमात्र नीरस रूप से अधिक त्रुटिहीन हो जाता है, यह आम धारणा के ठीक विपरीत है कि ओवरफिटिंग से चोट लगने से पहले एक वर्गीकरणकर्ता की जटिलता एकमात्र एक निश्चित स्तर की त्रुटिहीनता तक बढ़ सकती है। क्लेनबर्ग के स्टोकेस्टिक भेदभाव के सिद्धांत में ओवरट्रेनिंग के लिए जंगल पद्धति के प्रतिरोध की व्याख्या पाई जा सकती है।

बेतरतीब जंगलों की ब्रेमन की धारणा का शुरुआती विकास अमित और के काम से प्रभावित था

जेमनजिन्होंने बेतरतीब उपसमुच्चय पर खोज करने का विचार प्रस्तुत किया

एकल बढ़ने के संदर्भ में, नोड को विभाजित करते समय उपलब्ध निर्णय निर्णय ट्री। हो से बेतरतीब उपस्थान चयन का विचारबेतरतीब जंगलों के डिजाइन में भी प्रभावशाली था। इस विधि में ट्री का जंगल उगा दिया जाता है, और प्रशिक्षण डेटा को प्रोजेक्ट करके ट्री के बीच भिन्नता प्रस्तुत की जाती है

प्रत्येक पेड़ या प्रत्येक नोड को फिट करने से पहले बेतरतीब रूप से चुने गए रैखिक उप-स्थान में। अंत में, का विचार बेतरतीब नोड अनुकूलन, जहां प्रत्येक नोड पर निर्णय a के माध्यम से चुना जाता है एक नियतात्मक अनुकूलन के अतिरिक्त बेतरतीब प्रक्रिया पहले थी थॉमस जी डायटरिच के माध्यम से प्रस्तुत किया गया।

बेतरतीब जंगलों का उचित परिचय एक कागज में किया गया था

लियो ब्रिमन के माध्यम से। यह पत्र जंगल बनाने की एक विधि का वर्णन करता है एक वर्गीकरण और प्रतिगमन ट्री जैसी प्रक्रिया का उपयोग करते हुए असंबद्ध पेड़, बेतरतीब नोड के साथ संयुक्त अनुकूलन और बूटस्ट्रैप एकत्रीकरण। इसके अतिरिक्त, यह पेपर कई को जोड़ता है

सामग्री, कुछ पहले से ज्ञात और कुछ उपन्यास, जो इसका आधार बनते हैं बेतरतीब जंगलों का आधुनिक अभ्यास, विशेष रूप से:

1. सामान्यीकरण त्रुटि के अनुमान के रूप में आउट-ऑफ-बैग त्रुटि का उपयोग करना।
2. क्रमचय के माध्यम से परिवर्तनशील महत्व को मापना।

रिपोर्ट बेतरतीब जंगलों के लिए पहला सैद्धांतिक परिणाम भी प्रस्तुत करती है

सामान्यीकरण त्रुटि पर एक बाध्यता का रूप जो की ताकत पर निर्भर करता है

जंगल में पेड़ और उनका सहसंबंध।

एल्गोरिथम

प्रारंभिक: निर्णय ट्री सीखना

Main article: निर्णय वृक्ष सीखना

निर्णय ट्री विभिन्न मशीन सीखने के कार्यों के लिए एक लोकप्रिय विधि है। ट्री लर्निंग डेटा खनन के लिए एक ऑफ-द-शेल्फ प्रक्रिया के रूप में सेवा करने के लिए आवश्यकताओं को पूरा करने के सबसे निकट है, ट्रेवर हेस्टी एट अल कहते हैं, क्योंकि यह स्केलिंग और फीचर वैल्यू के विभिन्न अन्य परिवर्तनों के अनुसार अपरिवर्तनीय है, समावेशन के लिए मजबूत है अप्रासंगिक सुविधाओं का, और निरीक्षण योग्य मॉडल तैयार करता है। चूंकि, वे संभवतः ही कभी त्रुटिहीन होते हैं।

विशेष रूप से, बहुत गहरे उगने वाले पेड़ अत्यधिक अनियमित पैटर्न सीखने की प्रवृत्ति रखते हैं: वे अपने प्रशिक्षण सेटों को ओवरफिटिंग करते हैं, अर्थात बायस-वैरियंस ट्रेडऑफ़ कम पूर्वाग्रह, किन्तु बहुत उच्च विचरण। बेतरतीब जंगल एक ही प्रशिक्षण सेट के विभिन्न भागों पर प्रशिक्षित कई गहरे निर्णय ट्री को औसत करने का एक विधि है, जिसका लक्ष्य विचरण को कम करना है। यह पूर्वाग्रह में थोड़ी वृद्धि और व्याख्यात्मकता के कुछ हानि की कीमत पर आता है, किन्तु सामान्यतः अंतिम मॉडल में प्रदर्शन को बहुत बढ़ा देता है।

जंगल निर्णय ट्री एल्गोरिथम प्रयासों को एक साथ खींचने जैसा है। कई ट्री की टीम वर्क लेकर इस प्रकार एक बेतरतीब पेड़ के प्रदर्शन में सुधार होता है। चूंकि अधिक समान नहीं हैं, जंगल क्रॉस-सत्यापन (सांख्यिकी)#k-fold_cross-Validation|k-fold क्रॉस सत्यापन का प्रभाव देते हैं।

बैगिंग

Main article: बूटस्ट्रैप एकत्रीकरण

बेतरतीब जंगल के लिए प्रशिक्षण एल्गोरिद्म ट्री शिक्षार्थियों के लिए बूटस्ट्रैप एग्रीगेटिंग या बैगिंग की सामान्य तकनीक लागू करता है। ट्रेनिंग सेट दिया X = x₁, ..., x_n प्रतिक्रियाओं के साथ Y = y₁, ..., y_n, बार-बार बैगिंग (बी बार) एक नमूनाकरण (सांख्यिकी) का चयन करता है # प्रशिक्षण सेट की चयनित इकाइयों का प्रतिस्थापन और इन नमूनों में ट्री को फिट करता है:

के लिए b = 1, ..., B:

# नमूना, प्रतिस्थापन के साथ, n प्रशिक्षण के उदाहरण X, Y; इन्हें कॉल करें X_b, Y_b.

1. एक वर्गीकरण या प्रतिगमन ट्री को प्रशिक्षित करें f_b पर X_b, Y_b.

प्रशिक्षण के बाद, अनदेखी नमूने के लिए भविष्यवाणियां x' सभी अलग-अलग प्रतिगमन ट्री से भविष्यवाणियों के औसत से बनाया जा सकता है x':

${\hat {f}}={\frac {1}{B}}\sum _{b=1}^{B}f_{b}(x')$

या ले कर बहुमत वर्गीकरण ट्री के स्थितियोंमें।

यह बूटस्ट्रैपिंग प्रक्रिया अधिक अच्छा मॉडल प्रदर्शन की ओर ले जाती है क्योंकि यह पूर्वाग्रह को बढ़ाए बिना मॉडल की पूर्वाग्रह-विचरण दुविधा को कम करती है। इसका अर्थ यह है कि एक पेड़ की भविष्यवाणियां अपने प्रशिक्षण सेट में शोर के प्रति अत्यधिक संवेदनशील होती हैं, जब तक पेड़ सहसंबद्ध नहीं होते हैं, तब तक कई ट्री का औसत नहीं होता है। बस एक ही प्रशिक्षण सेट पर कई ट्री को प्रशिक्षित करने से दृढ़ता से सहसंबद्ध पेड़ (या यहां तक ​​​​कि एक ही पेड़ कई बार, यदि प्रशिक्षण एल्गोरिथ्म नियतात्मक है); बूटस्ट्रैप नमूनाकरण ट्री को अलग-अलग प्रशिक्षण सेट दिखाकर डी-सहसंबद्ध करने का एक विधि है।

इसके अतिरिक्त, भविष्यवाणी की अनिश्चितता का अनुमान सभी व्यक्तिगत प्रतिगमन ट्री से भविष्यवाणियों के मानक विचलन के रूप में बनाया जा सकता है x':

$\sigma ={\sqrt {\frac {\sum _{b=1}^{B}(f_{b}(x')-{\hat {f}})^{2}}{B-1}}}.$

नमूनों/ट्री की संख्या, B, एक मुफ़्त पैरामीटर है। सामान्यतः, प्रशिक्षण सेट के आकार और प्रकृति के आधार पर, कुछ सौ से लेकर कई हज़ार ट्री का उपयोग किया जाता है। ट्री की इष्टतम संख्या B क्रॉस-सत्यापन (सांख्यिकी) | क्रॉस-सत्यापन का उपयोग करके, या आउट-ऑफ-बैग त्रुटि को देखकर पाया जा सकता है: प्रत्येक प्रशिक्षण नमूने पर औसत भविष्यवाणी त्रुटि x_i, एकमात्र उन ट्री का उपयोग करना जिनके पास नहीं था x_i उनके बूटस्ट्रैप नमूने में।

कुछ ट्री के फिट होने के बाद प्रशिक्षण और परीक्षण त्रुटि का स्तर कम हो जाता है।

बैगिंग से बेतरतीब जंगलों तक

Main article: रैंडम सबस्पेस विधि

उपरोक्त प्रक्रिया ट्री के लिए मूल बैगिंग एल्गोरिथम का वर्णन करती है। बेतरतीब जंगल में एक अन्य प्रकार की बैगिंग योजना भी सम्मलित है: वे एक संशोधित ट्री लर्निंग एल्गोरिथम का उपयोग करते हैं, जो सीखने की प्रक्रिया में विभाजित प्रत्येक उम्मीदवार पर एक रैंडम सबस्पेस विधि का चयन करता है। इस प्रक्रिया को कभी-कभी फीचर बैगिंग कहा जाता है। ऐसा करने का कारण एक साधारण बूटस्ट्रैप नमूने में ट्री का सहसंबंध है: यदि प्रतिक्रिया चर (लक्ष्य आउटपुट) के लिए एक या कुछ फ़ीचर (मशीन लर्निंग) बहुत मजबूत भविष्यसमया हैं, तो इन सुविधाओं को कई में चुना जाएगा B पेड़, जिससे वे सहसंबद्ध हो जाते हैं। कैसे बैगिंग और बेतरतीब उप-अंतरिक्ष प्रक्षेपण विभिन्न परिस्थितियों में त्रुटिहीनता लाभ में योगदान का विश्लेषण हो के माध्यम से दिया गया है।

सामान्यतः, एक वर्गीकरण समस्या के लिए p विशेषताएँ, √p (राउंड डाउन) सुविधाओं का उपयोग प्रत्येक विभाजन में किया जाता है। प्रतिगमन समस्याओं के लिए आविष्कारक सलाह देते हैं p/3 (राउंड डाउन) डिफ़ॉल्ट के रूप में 5 के न्यूनतम नोड आकार के साथ। व्यवहार में, इन पैरामीटरों के लिए सर्वोत्तम मूल्यों को हर समस्या के लिए स्थिति-दर-स्थिति आधार पर ट्यून किया जाना चाहिए।

अतिरिक्त पेड़

रेंडमाइजेशन के एक और चरण को जोड़ने से अत्यधिक रैंडमाइज्ड ट्री या एक्स्ट्राट्रीज मिलते हैं। चूँकि सामान्य बेतरतीब जंगलों के समान ही वे अलग-अलग ट्री का एक समूह हैं, दो मुख्य अंतर हैं: पहला, प्रत्येक पेड़ को पूरे सीखने के नमूने (बूटस्ट्रैप नमूने के अतिरिक्त) का उपयोग करके प्रशिक्षित किया जाता है, और दूसरा, शीर्ष-नीचे विभाजन में ट्री शिक्षार्थी बेतरतीब है। विचाराधीन प्रत्येक सुविधा के लिए स्थानीय रूप से इष्टतम कट-पॉइंट की गणना करने के अतिरिक्त (उदाहरण के लिए, सूचना लाभ या गिन्नी अशुद्धता के आधार पर), एक बेतरतीब कट-पॉइंट का चयन किया जाता है। यह मान फीचर की अनुभवजन्य सीमा (पेड़ के प्रशिक्षण सेट में) के भीतर एक समान वितरण से चुना गया है। फिर, सभी बेतरतीब ढंग से उत्पन्न विभाजनों में, उच्चतम स्कोर देने वाले विभाजन को नोड को विभाजित करने के लिए चुना जाता है। साधारण बेतरतीब जंगलों के समान, प्रत्येक नोड पर विचार किए जाने वाले बेतरतीब रूप से चयनित सुविधाओं की संख्या निर्दिष्ट की जा सकती है। इस पैरामीटर के लिए डिफ़ॉल्ट मान हैं ${\sqrt {p}}$ वर्गीकरण के लिए और $p$ प्रतिगमन के लिए, जहां $p$ मॉडल में सुविधाओं की संख्या है।

गुण

परिवर्तनीय महत्व

प्राकृतिक तरीके से प्रतिगमन या वर्गीकरण समस्या में चर के महत्व को रैंक करने के लिए बेतरतीब जंगलों का उपयोग किया जा सकता है। ब्रिमन के मूल पेपर में निम्नलिखित तकनीक का वर्णन किया गया थाऔर R (प्रोग्रामिंग भाषा) पैकेज randomForest में लागू किया गया है। डेटा सेट में चर महत्व को मापने का पहला चरण ${\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}$ डेटा के लिए एक बेतरतीब जंगल फिट करना है। फिटिंग प्रक्रिया के समय प्रत्येक डेटा बिंदु के लिए आउट-ऑफ़-बैग त्रुटि रिकॉर्ड की जाती है और जंगल पर औसत होती है (यदि प्रशिक्षण के समय बैगिंग का उपयोग नहीं किया जाता है तो एक स्वतंत्र परीक्षण सेट पर त्रुटियों को प्रतिस्थापित किया जा सकता है)।

के महत्व को मापने के लिए $j$प्रशिक्षण के बाद -थ फीचर, के मूल्य $j$-वें फीचर को प्रशिक्षण डेटा के बीच अनुमति दी जाती है और इस परेशान डेटा सेट पर आउट-ऑफ-बैग त्रुटि की फिर से गणना की जाती है। के लिए महत्व स्कोर $j$-वें फीचर की गणना सभी ट्री पर क्रमपरिवर्तन से पहले और बाद में आउट-ऑफ-बैग त्रुटि में अंतर के औसत से की जाती है। इन अंतरों के मानक विचलन के माध्यम से स्कोर को सामान्य किया जाता है।

इस स्कोर के लिए बड़े मान उत्पन्न करने वाली सुविधाओं को छोटे मान उत्पन्न करने वाली सुविधाओं की समानता में अधिक महत्वपूर्ण माना जाता है। चर महत्व माप की सांख्यिकीय परिभाषा झू एट अल के माध्यम से दी गई और उसका विश्लेषण किया गया। परिवर्तनशील महत्व के निर्धारण की इस पद्धति में कुछ कमियां हैं। विभिन्न स्तरों के साथ श्रेणीबद्ध चर सहित डेटा के लिए, बेतरतीब जंगल अधिक स्तरों के साथ उन विशेषताओं के पक्ष में पक्षपाती हैं। आंशिक क्रमपरिवर्तन जैसे तरीकेऔर निष्पक्ष पेड़ उगाना समस्या को हल करने के लिए उपयोग किया जा सकता है। यदि डेटा में आउटपुट के लिए समान प्रासंगिकता की सहसंबद्ध विशेषताओं के समूह होते हैं, तो बड़े समूहों पर छोटे समूहों का पक्ष लिया जाता है।

निकटतम पड़ोसियों से संबंध

बेतरतीब जंगलों और के-निकटतम निकटतम एल्गोरिदम के बीच संबंध k-निकटतम एल्गोरिथम (k-एनएन) को 2002 में लिन और जीन के माध्यम से इंगित किया गया था। यह पता चला है कि दोनों को तथाकथित भारित पड़ोस योजनाओं के रूप में देखा जा सकता है। ये एक प्रशिक्षण सेट से निर्मित मॉडल हैं $\{(x_{i},y_{i})\}_{i=1}^{n}$ जो भविष्यवाणी करते हैं ${\hat {y}}$ नए बिंदुओं के लिए x' बिंदु के पड़ोस को देखकर, वजन समारोह के माध्यम से औपचारिक रूप दिया गया W:

${\hat {y}}=\sum _{i=1}^{n}W(x_{i},x')\,y_{i}.$

यहाँ, $W(x_{i},x')$ का गैर-ऋणात्मक भार है i'वाँ प्रशिक्षण बिंदु नए बिंदु के सापेक्ष x' उसी पेड़ में। किसी विशेष के लिए x', अंकों के लिए भार $x_{i}$ एक होना चाहिए। वजन कार्य निम्नानुसार दिए गए हैं:

• में k-एनएन, वजन हैं $W(x_{i},x')={\frac {1}{k}}$ यदि x_i उनमे से एक है k के सबसे निकट स्थित है x', और शून्य अन्यथा।
• एक पेड़ में, $W(x_{i},x')={\frac {1}{k'}}$ यदि x_i उनमे से एक है k' उसी पत्ते में इंगित करता है x', और शून्य अन्यथा।

चूंकि एक जंगल औसत के एक सेट की भविष्यवाणी करता है m व्यक्तिगत भार कार्यों वाले पेड़ $W_{j}$, इसकी भविष्यवाणियां हैं

${\hat {y}}={\frac {1}{m}}\sum _{j=1}^{m}\sum _{i=1}^{n}W_{j}(x_{i},x')\,y_{i}=\sum _{i=1}^{n}\left({\frac {1}{m}}\sum _{j=1}^{m}W_{j}(x_{i},x')\right)\,y_{i}.$

इससे पता चलता है कि पूरा जंगल फिर से एक भारित पड़ोस योजना है, वजन के साथ जो कि अलग-अलग ट्री का औसत है। के निकटतम x' इस व्याख्या में बिंदु हैं $x_{i}$ किसी पेड़ में एक ही पत्ते को बांटना $j$. इस प्रकार, के पड़ोस x' ट्री की संरचना पर और इस प्रकार प्रशिक्षण सेट की संरचना पर एक जटिल तरीके से निर्भर करता है। लिन और जीन बताते हैं कि एक बेतरतीब जंगल के माध्यम से उपयोग किए जाने वाले पड़ोस का आकार प्रत्येक सुविधा के स्थानीय महत्व के अनुकूल होता है।

बेतरतीब जंगलों के साथ अनियंत्रित शिक्षा

उनके निर्माण के भाग के रूप में, बेतरतीब जंगल भविष्यवक्ता स्वाभाविक रूप से प्रेक्षणों के बीच एक असमानता माप का नेतृत्व करते हैं। बिना लेबल वाले डेटा के बीच एक बेतरतीब जंगल असमानता माप को भी परिभाषित किया जा सकता है: विचार एक बेतरतीब जंगल भविष्यसमया का निर्माण करना है जो उपयुक्त रूप से उत्पन्न सिंथेटिक डेटा से देखे गए डेटा को अलग करता है।

देखे गए डेटा मूल लेबल रहित डेटा हैं और सिंथेटिक डेटा एक संदर्भ वितरण से तैयार किए गए हैं। एक बेतरतीब जंगल असमानता आकर्षक हो सकती है क्योंकि यह मिश्रित चर प्रकारों को बहुत अच्छी प्रकार से संभालती है, इनपुट चर के मोनोटोनिक परिवर्तनों के लिए अपरिवर्तनीय है, और बाहरी टिप्पणियों के लिए मजबूत है। बेतरतीब जंगल असमानता अपने आंतरिक चर चयन के कारण बड़ी संख्या में अर्ध-निरंतर चर से आसानी से निपटती है; उदाहरण के लिए अतिरिक्त 1 बेतरतीब जंगल डिसिमिलैरिटी प्रत्येक वेरिएबल के योगदान को मापता है कि यह अन्य वेरिएबल्स पर कितना निर्भर है। विभिन्न प्रकार के अनुप्रयोगों में बेतरतीब जंगल असमानता का उपयोग किया गया है, उदा। ऊतक मार्कर डेटा के आधार पर रोगियों के समूहों को खोजने के लिए।

वेरिएंट

निर्णय ट्री के अतिरिक्त, रैखिक मॉडल प्रस्तावित किए गए हैं और बेतरतीब जंगलों में आधार अनुमानक के रूप में मूल्यांकन किया गया है, विशेष रूप से बहुराष्ट्रीय रसद प्रतिगमन और सहज बेयस क्लासिफायरियर में। ऐसे स्थितियों में जहां भविष्यवाणियों और लक्ष्य चर के बीच संबंध रैखिक है, आधार शिक्षार्थियों के पास समेकित शिक्षार्थी के समान उच्च त्रुटिहीनता हो सकती है।

कर्नेल बेतरतीब जंगल

मशीन लर्निंग में, कर्नेल बेतरतीब जंगल (केआरएफ) बेतरतीब जंगल और कर्नेल विधियों के बीच संबंध स्थापित करता है। उनकी परिभाषा को थोड़ा संशोधित करके, बेतरतीब जंगलों को कर्नेल विधियों के रूप में फिर से लिखा जा सकता है, जो अधिक व्याख्यात्मक और विश्लेषण करने में आसान हैं।

इतिहास

लियो ब्रिमन बेतरतीब जंगल और कर्नेल विधियों के बीच की कड़ी को नोटिस करने वाले पहले व्यक्ति थे। उन्होंने बताया कि बेतरतीब जंगल जो i.i.d. का उपयोग करके उगाए जाते हैं। ट्री निर्माण में बेतरतीब वैक्टर सच्चे मार्जिन पर अभिनय करने वाले कर्नेल के समान होते हैं। लिन और जीन बेतरतीब जंगलों और अनुकूली निकटतम निकटतम के बीच संबंध स्थापित किया, जिसका अर्थ है कि बेतरतीब जंगलों को अनुकूली कर्नेल अनुमानों के रूप में देखा जा सकता है। डेविस और घरमनी प्रस्तावित बेतरतीब जंगल कर्नेल और दिखाते हैं कि यह अनुभवजन्य रूप से अत्याधुनिक कर्नेल विधियों से अधिक अच्छा प्रदर्शन कर सकता है। स्कॉर्नेटपहले केआरएफ अनुमानों को परिभाषित किया और केआरएफ अनुमानों और बेतरतीब जंगल के बीच स्पष्ट लिंक दिया। उन्होंने केन्द्रित बेतरतीब जंगल के आधार पर गुठली के लिए स्पष्ट अभिव्यक्तियाँ भी दीं और समान बेतरतीब जंगल, बेतरतीब जंगल के दो सरलीकृत मॉडल। उन्होंने इन दो केआरएफ को केंद्रित केआरएफ और यूनिफॉर्म केआरएफ नाम दिया, और उनकी स्थिरता की दरों पर ऊपरी सीमा सिद्ध की।

नोटेशन और परिभाषाएँ

प्रारंभिक: केंद्रित जंगल

केन्द्रित जंगलब्रेमेन के मूल बेतरतीब जंगल के लिए एक सरलीकृत मॉडल है, जो समान रूप से सभी विशेषताओं के बीच एक विशेषता का चयन करता है और पूर्व-चयनित विशेषता के साथ सेल के केंद्र में विभाजन करता है। एल्गोरिथ्म बंद हो जाता है जब स्तर का एक पूर्ण बाइनरी ट्री $k$ बनाया गया है, जहां $k\in \mathbb {N}$ एल्गोरिथम का एक पैरामीटर है।

एक समान जंगल

वर्दी का जंगलब्रेमेन के मूल बेतरतीब जंगल के लिए एक और सरलीकृत मॉडल है, जो समान रूप से सभी सुविधाओं के बीच एक विशेषता का चयन करता है और सेल के किनारे पर समान रूप से खींचे गए बिंदु पर विभाजित करता है, पूर्व-चयनित सुविधा के साथ।

बेतरतीब जंगल से केआरएफ तक

प्रशिक्षण का मॉडल दिया ${\mathcal {D}}_{n}=\{(\mathbf {X} _{i},Y_{i})\}_{i=1}^{n}$ का $[0,1]^{p}\times \mathbb {R}$स्वतंत्र प्रोटोटाइप जोड़ी के रूप में वितरित मूल्यवान स्वतंत्र बेतरतीब चर $(\mathbf {X} ,Y)$, कहाँ $\operatorname {E} [Y^{2}]<\infty$. हमारा उद्देश्य प्रतिक्रिया की भविष्यवाणी करना है $Y$, बेतरतीब चर के साथ जुड़ा हुआ है $\mathbf {X}$, प्रतिगमन फ़ंक्शन का अनुमान लगाकर $m(\mathbf {x} )=\operatorname {E} [Y\mid \mathbf {X} =\mathbf {x} ]$. एक बेतरतीब प्रतिगमन जंगल का एक समूह है $M$ बेतरतीब प्रतिगमन पेड़। निरूपित $m_{n}(\mathbf {x} ,\mathbf {\Theta } _{j})$ बिंदु पर अनुमानित मूल्य $\mathbf {x}$ से $j$-वाँ पेड़, जहाँ $\mathbf {\Theta } _{1},\ldots ,\mathbf {\Theta } _{M}$ स्वतंत्र बेतरतीब चर हैं, एक सामान्य बेतरतीब चर के रूप में वितरित $\mathbf {\Theta }$, नमूने से स्वतंत्र ${\mathcal {D}}_{n}$. इस बेतरतीब चर का उपयोग नोड विभाजन और ट्री निर्माण के लिए नमूनाकरण प्रक्रिया से प्रेरित बेतरतीब ता का वर्णन करने के लिए किया जा सकता है। परिमित जंगल अनुमान बनाने के लिए ट्री को जोड़ा जाता है $m_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})={\frac {1}{M}}\sum _{j=1}^{M}m_{n}(\mathbf {x} ,\Theta _{j})$. प्रतिगमन ट्री के लिए, हमारे पास है $m_{n}=\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})}}$, कहाँ $A_{n}(\mathbf {x} ,\Theta _{j})$ युक्त कोशिका है $\mathbf {x}$, बेतरतीब ता के साथ डिजाइन किया गया $\Theta _{j}$ और डेटासेट ${\mathcal {D}}_{n}$, और $N_{n}(\mathbf {x} ,\Theta _{j})=\sum _{i=1}^{n}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})}$.

इस प्रकार बेतरतीब जंगल अनुमान सभी के लिए संतुष्ट करते हैं $\mathbf {x} \in [0,1]^{d}$, $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)$. रैंडम रिग्रेशन फ़ॉरेस्ट में औसत के दो स्तर होते हैं, पहले एक पेड़ के लक्ष्य सेल में नमूनों पर, फिर सभी ट्री पर। इस प्रकार उन प्रेक्षणों का योगदान जो डेटा बिंदुओं के उच्च घनत्व वाले कक्षों में होते हैं, उन प्रेक्षणों की समानता में कम होते हैं जो कम आबादी वाले कक्षों से संबंधित होते हैं। बेतरतीब जंगल विधियों में सुधार करने और गलत आकलन की भरपाई करने के लिए, स्कॉर्नेट के माध्यम से परिभाषित केआरएफ न फ़ंक्शन है,

${\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})},$

जो के माध्य के समान है $Y_{i}$युक्त कोशिकाओं में गिर रहा है $\mathbf {x}$ जंगल में। यदि हम के कनेक्शन फ़ंक्शन को परिभाषित करते हैं $M$ परिमित जंगल के रूप में $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})}$, अर्थात बीच में साझा की गई कोशिकाओं का अनुपात $\mathbf {x}$ और $\mathbf {z}$, तो एकमात्र निश्चित रूप से हमारे पास है ${\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 })}}$, जो केआरएफ को परिभाषित करता है।

केंद्रित केआरएफ

स्तर के केन्द्रित केआरएफ का निर्माण $k$ केंद्रित जंगल के समान ही है, सिवाय इसके कि भविष्यवाणी के माध्यम से की जाती है ${\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})$, संबंधित कर्नेल फ़ंक्शन या कनेक्शन फ़ंक्शन है

${\begin{aligned}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 },\\&{\text{ for all }}\mathbf {x} ,\mathbf {z} \in [0,1]^{d}.\end{aligned}}$

वर्दी केआरएफ

यूनिफ़ॉर्म केआरएफ उसी प्रकार से बनाया गया है जैसे यूनिफ़ॉर्म फ़ॉरेस्ट, सिवाय इसके कि भविष्यवाणी की जाती है ${\tilde {m}}_{M,n}(\mathbf {x} ,\Theta _{1},\ldots ,\Theta _{M})$, संबंधित कर्नेल फ़ंक्शन या कनेक्शन फ़ंक्शन है

$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 {(-\ln |x_{m}|)^{j}}{j!}}\right){\text{ for all }}\mathbf {x} \in [0,1]^{d}.$

गुण

केआरएफ और बेतरतीब जंगल के बीच संबंध

यदि प्रत्येक सेल में बिंदुओं की संख्या नियंत्रित है तो केआरएफ और बेतरतीब जंगलों के माध्यम से दी गई भविष्यवाणियां निकट हैं:

<ब्लॉककोट>

मान लें कि अनुक्रम सम्मलित हैं $(a_{n}),(b_{n})$ ऐसा कि, एकमात्र निश्चित रूप से,

$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}.$

तब एकमात्र निश्चित रूप से,

$|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} ).$

</ब्लॉककोट>

अनंत केआरएफ और अनंत बेतरतीब जंगल के बीच संबंध

जब ट्री की संख्या $M$ अनंत तक जाता है, तो हमारे पास अनंत बेतरतीब जंगल और अनंत केआरएफ हैं। यदि प्रत्येक कोशिका में प्रेक्षणों की संख्या सीमित है तो उनके अनुमान निकट हैं:

<ब्लॉककोट>

मान लें कि अनुक्रम सम्मलित हैं $(\varepsilon _{n}),(a_{n}),(b_{n})$ ऐसा है कि, एकमात्र निश्चित रूप से

• $\operatorname {E} [N_{n}(\mathbf {x} ,\Theta )]\geq 1,$
• $\operatorname {P} [a_{n}\leq N_{n}(\mathbf {x} ,\Theta )\leq b_{n}\mid {\mathcal {D}}_{n}]\geq 1-\varepsilon _{n}/2,$
• $\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,$

तब एकमात्र निश्चित रूप से,

$|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).$

</ब्लॉककोट>

संगति परिणाम

ये मान लीजिए $Y=m(\mathbf {X} )+\varepsilon$, जहाँ $\varepsilon$ से स्वतंत्र एक केंद्रित गाऊसी शोर है $\mathbf {X}$, परिमित विचरण के साथ $\sigma ^{2}<\infty$. इसके अतिरिक्त, $\mathbf {X}$ पर समान रूप से वितरित है $[0,1]^{d}$ और $m$ लिप्सचिट्ज़ है। स्कॉर्नेटकेंद्रित केआरएफ और वर्दी केआरएफ के लिए स्थिरता की दरों पर ऊपरी सीमा सिद्ध हुई।

केंद्रित केआरएफ की संगति

उपलब्ध कराने के $k\rightarrow \infty$ और $n/2^{k}\rightarrow \infty$, एक स्थिर सम्मलित है $C_{1}>0$ ऐसा कि, सभी के लिए $n$,

$\mathbb {E} [{\tilde {m}}_{n}^{cc}(\mathbf {X} )-m(\mathbf {X} )]^{2}\leq C_{1}n^{-1/(3+d\log 2)}(\log n)^{2}$.

वर्दी केआरएफ की संगति

उपलब्ध कराने के $k\rightarrow \infty$ और $n/2^{k}\rightarrow \infty$, एक स्थिर सम्मलित है $C>0$ ऐसा है कि,

$\mathbb {E} [{\tilde {m}}_{n}^{uf}(\mathbf {X} )-m(\mathbf {X} )]^{2}\leq Cn^{-2/(6+3d\log 2)}(\log n)^{2}$.

हानि

जबकि एकल निर्णय के पेड़ों के साथ संबंधित और रैंडम वन अधिकांशतः एकल निर्णय से अधिक अनुशासिता प्राप्त करते हैं, वे निर्णय पेड़ों में निहित निर्वाचनीयता को हानि पहुंचाते हैं। निर्णय के पेड़ एक नियम-आधारित मशीन लर्निंग के कुछ छोटे से परिवारों में से एक होते हैं जो स्वचालित रूप से समझदार होते हैं साथ ही लीनियर मॉडल, रूल-आधारित मॉडल, और ध्यान आधारित मॉडल। निर्णय के पेड़ों में यह निर्वाचनीयता एक अधिक चाहनीय गुण है। यह डेटा से वास्तविक जानकारी सीखा है कि मॉडल ने और इससे अंत उपयोगकर्ताओं को मॉडल द्वारा लिए गए निर्णयो पर विश्वास और आत्मविश्वास होता है।उदाहरण के रूप में, एक निर्णय लेने के लिए एक डिसीजन ट्री द्वारा लिए गए पथ का पालन करना बहुत सरल होता है, लेकिन दसों या सैकड़ों ट्री के पथ का पालन करना कठिन होता है। प्रदर्शन और व्याख्यायता दोनों प्राप्त करने के लिए, कुछ मॉडल संपीड़न तकनीकों का उपयोग किया जा सकता है जो एक रैंडम फॉरेस्ट को एक न्यूनतम "जन्मान्तरित" डिसीजन ट्री में बदलने की अनुमति देते हैं जो एक ही निर्णय कार्य को विश्वसनीय रूप से पुनर्गठित करता है। यदि यह स्थापित होता है कि पूर्वानुमानी गुण लक्ष्य चर के साथ रैखिक रूप से संबंधित हैं, तो रैंडम फॉरेस्ट का उपयोग बेस लर्नर की निखरता को बढ़ाने में सफल नहीं हो सकता है। इसके अलावा, कई श्रेणीबद्ध गुणों वाली समस्याओं में, रैंडम फॉरेस्ट बेस लर्नर की निखरता को बढ़ाने में सक्षम नहीं हो सकता है।

यह भी देखें

• बूस्टिंग  – Method in machine learning
• Decision tree learning
• सीखने को इकट्ठा करो
• ग्रेडिएंट बूस्टिंग
• गैर-पैरामीट्रिक आँकड़े
• यादृच्छिक एल्गोरिदम

अग्रिम पठन

• Prinzie A, Poel D (2007). "Random Multiclass Classification: Generalizing Random Forests to Random MNL and Random NB". Database and Expert Systems Applications. Lecture Notes in Computer Science. Vol. 4653. p. 349. doi:10.1007/978-3-540-74469-6_35. ISBN 978-3-540-74467-2.
• Denisko D, Hoffman MM (February 2018). "Classification and interaction in random forests". Proceedings of the National Academy of Sciences of the United States of America. 115 (8): 1690–1692. Bibcode:2018PNAS..115.1690D. doi:10.1073/pnas.1800256115. PMC 5828645. PMID 29440440.

बाहरी संबंध

• Random Forests classifier description (Leo Breiman's site)
• Liaw, Andy & Wiener, Matthew "Classification and Regression by randomForest" R News (2002) Vol. 2/3 p. 18 (Discussion of the use of the random forest package for R)