समस्या
डिसीज़न ट्री डेटा को जितना हो सके उतने शुद्ध समूहों में बाँटते हैं। जिनी इम्प्योरिटी मापती है कि किसी समूह के लेबल कितने मिले-जुले हैं:
Gini = 1 - Σ pₖ²
जहाँ pₖ क्लास k वाले लेबल का अनुपात है। एक ही क्लास वाले समूह की इम्प्योरिटी 0 होती है; दो क्लास के बराबर मिश्रण की इम्प्योरिटी 0.5 होती है।
gini_impurity(labels) लागू करें।
इनपुट
labels: समूह के क्लास लेबल।
आउटपुट
जिनी इम्प्योरिटी को दशमलव संख्या के रूप में लौटाएँ।
सीमाएँ
1 ≤ लंबाई ≤ 10,000
हर लेबल 1 से 20 अक्षर का है
उदाहरण
इनपुट:
labels = ["yes", "yes", "no", "no"]
अपेक्षित आउटपुट:
expected = 0.5
इनपुट:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
अपेक्षित आउटपुट:
double expected = 0.5;
इनपुट:
string[] labels = new string[] {"yes", "yes", "no", "no"};
अपेक्षित आउटपुट:
double expected = 0.5;
व्याख्या
आधे yes हैं और आधे no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, दो क्लास वाले समूह का सबसे ज़्यादा मिश्रण।
इनपुट:
labels = ["cat", "cat", "cat"]
अपेक्षित आउटपुट:
expected = 0.0
इनपुट:
std::vector<std::string> labels = {"cat", "cat", "cat"};
अपेक्षित आउटपुट:
double expected = 0.0;
इनपुट:
string[] labels = new string[] {"cat", "cat", "cat"};
अपेक्षित आउटपुट:
double expected = 0.0;
व्याख्या
केवल एक क्लास: 1 - 1² = 0। समूह शुद्ध है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
किस label की कितनी बार occurrence है, यह गिनें, क्योंकि impurity सिर्फ label distribution पर depend करती है।
संकेत 2
Counts को पूरे group के fractions में बदलें, फिर मापें कि group purity से कितना दूर है।
संकेत 3
सिर्फ एक label वाले group का result zero होना चाहिए, जबकि balanced mix का value ज़्यादा होगा।
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(k)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।