होफडिंग ट्री एल्गोरिदम स्ट्रीम डेटा वर्गीकरण के लिए एक निर्णय ट्री सीखने की विधि है। इसका उपयोग शुरू में वेब क्लिकस्ट्रीम को ट्रैक करने और यह अनुमान लगाने के लिए मॉडल बनाने के लिए किया गया था कि उपयोगकर्ता किन वेब होस्ट और वेब साइटों तक पहुंचने की संभावना रखता है। यह आमतौर पर सबलाइनियर समय में चलता है और पारंपरिक बैच लर्नर के लगभग समान निर्णय ट्री का उत्पादन करता है।
यह होफडिंग ट्री का उपयोग करता है, जो इस विचार का फायदा उठाता है कि एक छोटा नमूना अक्सर एक इष्टतम विभाजन एट्रिब्यूट चुनने के लिए पर्याप्त हो सकता है। यह विचार गणितीय रूप से होफडिंग बाउंड (या योजक चेर्नॉफ बाउंड) द्वारा समर्थित है।
मान लीजिए हम एक रैंडम वेरिएबल r के N स्वतंत्र अवलोकन करते हैं जिसकी रेंज R है, जहां r एक एट्रिब्यूट चयन माप है। (एक संभावना के लिए, R एक है, और सूचना लाभ के लिए, यह log c है, जहां c क्लास की संख्या है।) होफडिंग ट्री के मामले में, r सूचना लाभ है। यदि हम इस नमूने का माध्य, r', गणना करते हैं, तो होफडिंग बाउंड बताता है कि r का वास्तविक माध्य कम से कम r' - ε है, संभावना 1 - δ के साथ, जहां δ उपयोगकर्ता-निर्दिष्ट है और
ε = √(R² ln(1/δ) / 2N)
होफडिंग ट्री एल्गोरिदम विभाजन एट्रिब्यूट का चयन करते समय उच्च संभावना के साथ एक नोड पर आवश्यक उदाहरणों की न्यूनतम संख्या, N, निर्धारित करने के लिए होफडिंग बाउंड का उपयोग करता है। होफडिंग बाउंड संभावना वितरण से स्वतंत्र है, अधिकांश अन्य बाउंड समीकरणों के विपरीत। यह वांछनीय है, क्योंकि सूचना लाभ, या जो भी एट्रिब्यूट चयन माप उपयोग किया जाता है, के संभावना वितरण को जानना असंभव हो सकता है।
एल्गोरिदम इनपुट के रूप में प्रशिक्षण उदाहरणों का एक क्रम, S, एट्रिब्यूट A द्वारा वर्णित, और सटीकता पैरामीटर, δ लेता है। मूल्यांकन फंक्शन G(Aᵢ) प्रदान किया जाता है, जो सूचना लाभ, लाभ अनुपात, गिनी इंडेक्स, या कोई अन्य एट्रिब्यूट चयन माप हो सकता है। निर्णय ट्री में प्रत्येक नोड पर, हमें शेष एट्रिब्यूट Aᵢ में से एक के लिए G(Aᵢ) को अधिकतम करने की आवश्यकता है। लक्ष्य टपल्स की न्यूनतम संख्या, N, ढूंढना है जिसके लिए होफडिंग बाउंड संतुष्ट है।
एक दिए गए नोड के लिए, मान लीजिए Aₐ वह एट्रिब्यूट है जो उच्चतम G प्राप्त करता है, और A_b वह एट्रिब्यूट है जो दूसरा सबसे उच्च G प्राप्त करता है। यदि G(Aₐ) - G(A_b) > ε, जहां ε की गणना की जाती है।
होफडिंग ट्री एल्गोरिदम में बनाए रखने के लिए केवल वही आंकड़े हैं जो एट्रिब्यूट Aᵢ के मूल्य vⱼ के लिए काउंट nᵢⱼₖ हैं जिसका क्लास लेबल yₖ है। इसलिए, यदि d एट्रिब्यूट की संख्या है, v किसी भी एट्रिब्यूट के लिए अधिकतम मूल्यों की संख्या है, c क्लास की संख्या है, और l ट्री की अधिकतम गहराई (या स्तरों की संख्या) है, तो आवश्यक कुल मेमोरी O(ldvc) है।
