संख्या वाली सुविधाओं के साथ बाइनरी वर्गीकरण के लिए सटीक स्प्लिटर

इस इकाई में, आप सबसे सरल और सबसे ज़्यादा बंटे हुए एल्गोरिदम एल्गोरिदम को एक्सप्लोर करेंगे. इससे, नीचे दी गई सेटिंग में $\mathrm{feature}_i \geq t$ की शर्तें बनती हैं:

• बाइनरी क्लासिफ़िकेशन टास्क
• उदाहरणों में वैल्यू मौजूद न होने से
• उदाहरणों में, पहले से तय किए गए इंडेक्स के बिना

मान लीजिए कि $n$ के सेट को संख्या वाली सुविधा और बाइनरी लेबल के साथ इस्तेमाल करें "orange" &"blue". औपचारिक रूप से, डेटासेट की जानकारी $D$ को इस तरह दें:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

कहां:

• $x_i$, $\mathbb{R}$ में अंकों में मौजूद सुविधा की वैल्यू है (असल के सेट के लिए).
• $y_i$, {नारंगी, नीले} में बाइनरी क्लासिफ़िकेशन लेबल की वैल्यू है.

हमारा लक्ष्य है कि $t$ (थ्रेशोल्ड) की थ्रेशोल्ड वैल्यू बनाई जाए, ताकि $D$ के उदाहरणों को $T(rue)$ और $F(alse)$ से अलग-अलग किया जाए. उदाहरण के लिए, $x_i \geq t$ की शर्त के हिसाब से, लेबल को अलग-अलग किया जा सकता है. उदाहरण के लिए, $T&t&t& &t & & &t में खास उदाहरण.

शैनन एंट्रॉपी यह बीमारी को रोकने का एक तरीका है. बाइनरी लेबल के लिए:

• जब उदाहरणों में लेबल को संतुलित किया जाता है, तो शैनन एंट्रॉपी ज़्यादा से ज़्यादा होती है (50% नीला और 50% नारंगी).
• जब उदाहरणों में लेबल शुद्ध (100% नीला या 100% नारंगी) होते हैं, तो शैनन एंट्रॉपी कम से कम (वैल्यू शून्य) पर होती है.

आठवीं इमेज. तीन अलग-अलग एंट्रॉपी लेवल.

 

औपचारिक रूप से, हम ऐसी शर्त ढूंढना चाहते हैं जो $T$ और $F$ में लेबल के डिस्ट्रिब्यूशन के वेटेड योग को कम कर दे. इससे जुड़ा स्कोर जानकारी का फ़ायदा है, जो $D$' एंट्रॉपी और {$T$,$F$} एंट्रॉपी के बीच का अंतर है. इस अंतर को जानकारी हासिल करने वाला कहा जाता है.

नीचे दिए गए आंकड़े में ऐसा खराब स्प्लिट दिखाया गया है जिसमें एंट्रॉपी ज़्यादा बनी हुई है और जानकारी कम हो रही है:

तीसरा डायग्राम. गलत तरीके से बांटने से, लेबल की एंट्री को कम नहीं किया जाता है.

 

इसके उलट, नीचे दिया गया आंकड़ा एक बेहतर स्प्लिट दिखाता है जिसमें एंट्रॉपी कम होती है (और जानकारी ज़्यादा बढ़ती है):

10वीं इमेज. कॉन्टेंट को अच्छे से बांटने पर, लेबल की परफ़ॉर्मेंस कम हो जाती है.

 

औपचारिक रूप से:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

कहां:

• $IG(D,T,F)$ $D$ को $T$ और $F$ में बांटने की जानकारी मिलती है.
• $H(X)$, $X$ के उदाहरणों के सेट की एंट्री है.
• $|X|$, सेट $X$ के एलिमेंट की संख्या है.
• $t$ थ्रेशोल्ड की वैल्यू है.
• ऊपर दिए गए उदाहरण में, $pos$ पॉज़िटिव लेबल की वैल्यू है. उदाहरण के लिए, "blue" . किसी दूसरे लेबल को "पॉज़िटिव लेबल&quot के तौर पर चुनने से, एंट्रॉपी की वैल्यू या जानकारी में होने वाले बदलाव पर कोई असर नहीं पड़ता.
• $R(X)$, $X$ उदाहरणों में पॉज़िटिव लेबल वैल्यू का अनुपात है.
• $D$ डेटासेट है (जैसा कि इस इकाई में पहले बताया गया है).

नीचे दिए गए उदाहरण में, हम बाइनरी कैटगरी वाले डेटासेट को एक ही संख्या वाली $x$ डॉलर का इस्तेमाल करके देखते हैं. नीचे दी गई इमेज में अलग-अलग थ्रेशोल्ड $t$ (x-एक्सिस) का डेटा दिखाया गया है:

1. $x$ सुविधा का हिस्टोग्राम.
2. थ्रेशोल्ड वैल्यू के मुताबिक, $D$, $T$, और $F$ के सेट में "blue" के अनुपात.
3. $D$, $T$ और $F$ में एंट्रॉपी.
4. जानकारी मिलती है; यानी, $D$ और {$T$,$F$} के बीच एंट्रॉपी डेल्टा का उदाहरण दिया जाता है.

पहली इमेज. चार थ्रेशोल्ड वाले प्लॉट.

 

इन इलाकों में ये चीज़ें दिखती हैं:

• "फ़्रीक्वेंसी" प्लॉट दिखाता है कि 18 से 60 के बीच की तुलनाओं के साथ ऑब्ज़र्वेशन बड़ी आसानी से फैलते हैं. इसका प्रसार ज़्यादा होने का मतलब है कि इसमें बहुत सारे संभावित बदलाव हैं, जो मॉडल को ट्रेनिंग देने के लिए अच्छे हैं.

• डेटासेट में "blue" लेबल का अनुपात ~25% है. नीले रंग के लेबल का " अनुपात, प्लॉट दिखाता है कि 20 से 50 के बीच की थ्रेशोल्ड वैल्यू:

  • $T$ सेट में "blue" से ज़्यादा लेबल के उदाहरण हैं (थ्रेशोल्ड की 35% तक की सीमा).
  • $F$ सेट में "blue" लेबल के उदाहरण से एक और भी कम फ़ायदा है (35 के लिए सिर्फ़ 8% के हिसाब से).

  नीले लेबल के कोट और ""entropy" दोनों प्लॉट बताते हैं कि लेबल की थ्रेशोल्ड की सीमा को काफ़ी हद तक अलग किया जा सकता है.

• इस निगरानी की पुष्टि "जानकारी हासिल" प्लॉट में की जाती है. हमने देखा है कि ज़्यादा से ज़्यादा जानकारी पाने के लिए, ~~2.074 की जानकारी पाने की कोशिश की जाती है. इसलिए, स्प्लिट स्प्लिट करने वाले की स्थिति $x \geq 28$ होगी.

• जानकारी मिलना हमेशा सकारात्मक या शून्य होता है. जैसे ही थ्रेशोल्ड वैल्यू अपनी ज़्यादा से ज़्यादा / कम से कम वैल्यू के बराबर होती है, शून्य के बराबर हो जाती है. ऐसे मामलों में, या तो $F$ या $T$ खाली हो जाता है और दूसरे में पूरा डेटासेट होता है और $D$ में बराबर की कोई एंट्रॉपी दिखती है. जब $H(T)$ = $H(F)$ = $H(D)$ होता है, तो जानकारी में बढ़ोतरी शून्य हो सकती है. इसलिए, इन वैल्यू में $\&t और नीले रंग की वैल्यू शामिल होती हैं

रीयल नंबर ($\mathbb{R}$) के सेट में $t$ के लिए उम्मीदवार की वैल्यू असीमित है. हालांकि, उदाहरण के लिए, एक तय संख्या में ही $D$ को $T$ और $F$ में बांटा गया है. इसलिए, $t$ के मान की तय संख्या ही टेस्ट करने के लिए मायने रखती है.

ऐसा करने के लिए आपको x_i वैल्यू को बढ़ते हुए क्रम में लगाना होगा (_x(i):

$$ x_{s(i)} \leq x_{s(i+1)} $$

फिर, $x_i$ की क्रम से लगाई गई वैल्यू के बीच हर वैल्यू के लिए $t$ का टेस्ट करें. उदाहरण के लिए, मान लें कि आपके पास किसी खास सुविधा के लिए फ़्लोटिंग-पॉइंट वैल्यू 1,000 हैं. क्रम से लगाने के बाद, मान लें कि पहले दो मान 8.5 और 8.7 हैं. इस मामले में, जांच के लिए पहली सीमा मान 8.6 होगा.

औपचारिक रूप से, हम t के लिए इन उम्मीदवारों पर विचार करते हैं:

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

इस एल्गोरिदम की समय सीमा $\mathcal{O} ( n \log n) $ है. इसमें नोड में उदाहरण के तौर पर दिए गए $n$ की संख्या (सुविधा के वैल्यू को क्रम से लगाने की वजह से) है. जब किसी फ़ैसले के ट्री पर लागू किया जाता है, तो स्प्लिट नोड एल्गोरिदम हर नोड और हर सुविधा पर लागू होता है. ध्यान दें कि हर नोड को उसके पैरंट उदाहरणों में से ~1/2 मिलता है. इसलिए, मास्टर थ्योरम के मुताबिक, इस स्प्लिटर से यह तय करने में कितना समय लगता है:

$$ \mathcal{O} ( m n \log^2 n ) $$

कहां:

• $m$ सुविधाओं की संख्या है.
• $n$, ट्रेनिंग के उदाहरणों की संख्या है.

इस एल्गोरिदम में, सुविधाओं का मान मायने नहीं रखता; सिर्फ़ ऑर्डर के मामले में मायने रखता है. इस वजह से, यह एल्गोरिदम सुविधा की वैल्यू के स्केल या डिस्ट्रिब्यूशन से अलग काम करता है. यही वजह है कि हमें फ़ैसला लेने वाले पेड़ को ट्रेनिंग देते समय, संख्या वाली सुविधाओं को सामान्य या मापने की ज़रूरत नहीं है.