सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

इन्फ़ॉर्मेशन गेन

किसी फ़ीचर से बाँटने पर एंट्रॉपी कितनी घटती है, यह निकालें, यही ID3 डिसीज़न ट्री का मापदंड है।

आप क्या सीखेंगे

  • विभाजन से पहले और बाद की एंट्रॉपी निकालना
  • उपसमुच्चयों को उनके आकार से भार देना
  • सबसे जानकारी देने वाला फ़ीचर चुनना

समस्या

एंट्रॉपी लेबल के समूह की अनिश्चितता मापती है: 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 अक्षर का है

उदाहरण

उदाहरण 1
इनपुट:
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 है: यह फ़ीचर सब कुछ बता देता है।

उदाहरण 2
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।