समस्या
एंट्रॉपी लेबल के समूह की अनिश्चितता मापती है: H(S) = -Σ pₖ × log₂(pₖ), जहाँ pₖ क्लास k वाले लेबल का अनुपात है। इन्फ़ॉर्मेशन गेन यह है कि किसी फ़ीचर से समूह को बाँटने पर एंट्रॉपी कितनी घटती है:
IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)
जहाँ Sᵥ उन सैंपल के लेबल हैं जिनका फ़ीचर v के बराबर है। डिसीज़न ट्री सबसे ज़्यादा गेन वाला फ़ीचर चुनते हैं।
information_gain(feature, labels) लागू करें।
इनपुट
feature: हर सैंपल का फ़ीचर मान।
labels: हर सैंपल का क्लास लेबल (समान लंबाई)।
आउटपुट
इन्फ़ॉर्मेशन गेन को बिट्स में, दशमलव संख्या के रूप में लौटाएँ।
सीमाएँ
1 ≤ लंबाई ≤ 10,000
हर मान और लेबल 1 से 20 अक्षर का है
उदाहरण
इनपुट:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]
अपेक्षित आउटपुट:
expected = 1.0
इनपुट:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
अपेक्षित आउटपुट:
double expected = 1.0;
इनपुट:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};
अपेक्षित आउटपुट:
double expected = 1.0;
व्याख्या
लेबल आधे yes और आधे no हैं, इसलिए H = 1 बिट। मौसम से बाँटने पर दो शुद्ध समूह (हर एक का H = 0) मिलते हैं, इसलिए गेन 1 - 0 = 1 है: यह फ़ीचर सब कुछ बता देता है।
इनपुट:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]
अपेक्षित आउटपुट:
expected = 0.0
इनपुट:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
अपेक्षित आउटपुट:
double expected = 0.0;
इनपुट:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};
अपेक्षित आउटपुट:
double expected = 0.0;
व्याख्या
समूह a और b में अब भी एक-एक yes और no है (H = 1), इसलिए बचा हुआ हिस्सा 0.5 × 1 + 0.5 × 1 = 1 है और गेन 1 - 1 = 0: यह फ़ीचर बेकार है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
किसी भी split से पहले label uncertainty पहले मापें, फिर उसे हर feature group की uncertainty से compare करें.
संकेत 2
Samples को feature value के हिसाब से group करें, हर group में labels गिनें, और data में उसके हिस्से के साथ हर group की entropy combine करें.
संकेत 3
Repeated values और उस case का ध्यान रखें जहाँ किसी group में सिर्फ एक label हो, क्योंकि तब उसकी entropy contribution zero होती है.
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।