- डेटा को वर्गीकृत करने के लिए feature space को बार-बार विभाजित करने वाली संरचना, जिसमें हर चरण पर सबसे अधिक information gain देने वाला विभाजन चुना जाता है
- Entropy का उपयोग करके डेटा की purity मापी जाती है, और इसी के आधार पर Information Gain की गणना की जाती है
- ID3 algorithm parent node और child node की entropy के अंतर की गणना करके सबसे उपयुक्त split point ढूँढता है और tree को recursively विस्तार देता है
- Entropy की जगह Gini impurity का भी उपयोग किया जा सकता है, और दोनों तरीके अधिकांश मामलों में मिलते-जुलते परिणाम देते हैं, हालांकि उनकी computational efficiency अलग होती है
- अत्यधिक विभाजन overfitting और instability पैदा कर सकता है, इसलिए pruning या Random Forest से इसे कम किया जाता है
निर्णय वृक्ष की बुनियादी अवधारणा
- निर्णय वृक्ष डेटा को ऊपर से नीचे की ओर विभाजित करता है, और हर चरण में conditional rules लागू करके डेटा को अच्छी तरह अलग होने वाले क्षेत्रों में बाँटता है
- हर विभाजन डेटा के किसी खास feature और threshold value के आधार पर तय होता है
- लक्ष्य यह है कि classification के समय ऐसे pure nodes बनाए जाएँ जिनमें classes स्पष्ट रूप से अलग हों
Entropy की परिभाषा और गुण
- Entropy सूचना की अनिश्चितता को मापने वाला एक मानक है, और probability (p_i) के लिए इसे (H = -\sum p_i \log_2(p_i)) के रूप में परिभाषित किया जाता है
- मुख्य गुण
- जब केवल एक घटना की probability 1 हो और बाकी सभी 0 हों, तब (H=0), यानी कोई अनिश्चितता नहीं
- जब सभी घटनाओं की probabilities समान हों, तब entropy अधिकतम होती है और यह सबसे अधिक impure स्थिति को दर्शाती है
- probabilities जितनी अधिक समान होती जाती हैं, entropy उतनी बढ़ती है
- इसलिए pure node की entropy 0 होती है, जबकि mixed node की entropy अधिक होती है
Information Gain और ID3 algorithm
- Information Gain को विभाजन से पहले और बाद की entropy के अंतर से निकाला जाता है, और यह डेटा विभाजन की दक्षता को दर्शाता है
- सूत्र: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
- ID3 algorithm के चरण
- हर feature की entropy की गणना
- अलग-अलग splitting criteria के आधार पर dataset को बाँटना और information gain की गणना
- सबसे अधिक information gain वाले विभाजन को चुनकर decision node बनाना
- जब आगे विभाजन संभव न हो, तब leaf node बनाना
- सभी subsets पर recursion चलाना, लेकिन यदि सभी elements एक ही class के हों तो रुक जाना
- उदाहरण के तौर पर, Diameter ≤ 0.45 शर्त का information gain 0.574 सबसे अधिक था, इसलिए इसे पहले विभाजन के रूप में चुना गया
Gini impurity और वैकल्पिक मापन
- Gini impurity entropy का एक विकल्प है, जो सूचना की impurity मापने का एक दूसरा तरीका है
- इसमें logarithm की गणना नहीं होती, इसलिए गणना की गति तेज होती है
- imbalanced datasets में entropy कभी-कभी अधिक सावधानीपूर्ण विकल्प हो सकता है
- दोनों तरीके सामान्यतः समान प्रकार के परिणाम देते हैं
Overfitting और instability की समस्या
- ID3 algorithm entropy को न्यूनतम करने के लिए लगातार विभाजन करता रहता है, इसलिए tree बहुत अधिक गहरा हो सकता है
- इससे overfitting होता है और नए डेटा पर generalization performance घट जाती है
- साथ ही डेटा में छोटे बदलाव से भी tree structure बहुत बदल सकता है, जिसे instability (high variance) की समस्या कहा जाता है
- उदाहरण: training data के 5% में हल्का Gaussian noise जोड़ने पर भी पूरी तरह अलग tree बन सकता है
- समाधान के रूप में pruning के जरिए tree की depth, leaf की संख्या, minimum sample count आदि सीमित किए जा सकते हैं
Random Forest तक विस्तार
- एकल निर्णय वृक्ष की instability कम करने के लिए कई trees को अलग-अलग data samples पर train करके उनकी predictions को मिलाने का तरीका इस्तेमाल किया जाता है
- यही तरीका Random Forest कहलाता है, जो अधिक stability और बेहतर generalization performance देता है
- यह निर्णय वृक्ष की कमियों की भरपाई करता है और आज तक के सबसे सफल machine learning algorithms में से एक माना जाता है
निष्कर्ष और आगे की सीख
- निर्णय वृक्ष ऐसा model है जिसे समझना आसान है, जिसकी training तेज है, और जिसकी preprocessing सरल है
- लेकिन overfitting और instability की समस्याओं को हल करने के लिए pruning या ensemble techniques की आवश्यकता होती है
- लेख में regression trees, end-cut preference, hyperparameters आदि पर चर्चा नहीं की गई है, और संबंधित सामग्री के जरिए आगे सीखने की सलाह दी गई है
अभी कोई टिप्पणी नहीं है.