होफडिंग ट्री एल्गोरिथम क्या है?

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

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

मान लीजिए कि हम रेंज R के साथ एक यादृच्छिक चर r का N स्वतंत्र अवलोकन करते हैं, जहां r एक विशेषता चयन माप है। (संभाव्यता के लिए, आर एक है, और सूचना लाभ के लिए, यह लॉग सी है, जहां सी कक्षाओं की संख्या है।) होफडिंग पेड़ों के मामले में, आर सूचना लाभ है। यदि हम इस नमूने के माध्य, r' की गणना करते हैं, तो Hoeffding बाउंड बताता है कि r का सही मतलब कम से कम r'−ε है, संभावना 1−δ के साथ, जहां उपयोगकर्ता द्वारा निर्दिष्ट है और

$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$

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

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

एल्गोरिदम इनपुट के रूप में प्रशिक्षण उदाहरणों का एक क्रम लेता है, S, विशेषता A द्वारा वर्णित, और सटीकता पैरामीटर, । मूल्यांकन कार्य G(A_i ) की आपूर्ति की जाती है, जो सूचना लाभ, लाभ अनुपात, गिनी इंडेक्स, या कुछ अन्य विशेषता चयन उपाय हो सकता है। डिसीजन ट्री में प्रत्येक नोड पर, हमें G (A_i . को अधिकतम करने की आवश्यकता है ) शेष विशेषताओं में से एक के लिए,A_i . लक्ष्य सबसे छोटी संख्या में टुपल्स, N को खोजना है, जिसके लिए Hoeffding बाउंड संतुष्ट है।

किसी दिए गए नोड के लिए, A_a . दें वह विशेषता हो जो उच्चतम G प्राप्त करती है, और Abbe वह विशेषता जो दूसरी-उच्चतम G प्राप्त करती है। यदि G(A_a ) - जी(ए<उप>बी )> , जहां की गणना की जाती है।

होफडिंग ट्री एल्गोरिथम में बनाए जाने वाले एकमात्र आंकड़े n_ijk की गणनाएं हैं v_j . के मान के लिए विशेषता A_i . का क्लास लेबल y_k . के साथ . इसलिए, यदि d विशेषताओं की संख्या है, v किसी भी विशेषता के लिए मानों की अधिकतम संख्या है, c वर्गों की संख्या है, और l पेड़ की अधिकतम गहराई (या स्तरों की संख्या) है, तो आवश्यक कुल मेमोरी ओ (एलडीवीसी) है।