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

नेव बेयस क्लासिफ़ायर

बेयस प्रमेय और लाप्लास स्मूदिंग से कैटेगोरिकल फ़ीचर्स के आधार पर क्लास का अनुमान लगाएँ।

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

  • क्लास की पूर्व प्रायिकता और संभाविता निकालना
  • न देखे गए फ़ीचर मानों पर स्मूदिंग लगाना
  • सबसे संभावित क्लास चुनना

समस्या

नेव बेयस मानता है कि क्लास पता होने पर फ़ीचर एक-दूसरे से स्वतंत्र हैं, और सबसे ऊँचे स्कोर वाली क्लास चुनता है:

score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)

फ़ीचर पूर्णांकों के रूप में एन्कोड की गई श्रेणियाँ हैं। ट्रेनिंग डेटा से प्रायिकताओं का अनुमान लगाएँ:

  • P(c) = (क्लास c के सैंपल की संख्या) / (कुल सैंपल)
  • P(xⱼ = v | c) = (क्लास c के उन सैंपल की संख्या जिनका फ़ीचर j, v के बराबर है + 1) / (क्लास c के सैंपल की संख्या + Kⱼ)

जहाँ Kⱼ ट्रेनिंग सैंपल और क्वेरी में फ़ीचर j के अलग-अलग मानों की संख्या है। +1 (लाप्लास स्मूदिंग) किसी अनदेखे मान को स्कोर शून्य करने से रोकता है।

सबसे ऊँचे स्कोर वाली क्लास लौटाएँ; बराबरी होने पर छोटी क्लास लौटाएँ। कई छोटी प्रायिकताओं को गुणा करने से अंडरफ़्लो हो सकता है, इसलिए गुणा के बजाय लघुगणक जोड़ें।

naive_bayes_predict(features, labels, query) लागू करें।

इनपुट

features: हर ट्रेनिंग सैंपल के लिए n कैटेगोरिकल फ़ीचर की एक पंक्ति।

labels: हर ट्रेनिंग सैंपल की क्लास।

query: वर्गीकृत किए जाने वाले सैंपल के n फ़ीचर।

आउटपुट

अनुमानित क्लास लौटाएँ।

सीमाएँ

1 ≤ सैंपल ≤ 1,000, 1 ≤ n ≤ 20

0 ≤ हर फ़ीचर मान और लेबल ≤ 100

उदाहरण

उदाहरण 1
इनपुट:
features = [
    [0, 1],
    [0, 0],
    [1, 1],
    [1, 0],
    [0, 1]
]
labels = [1, 1, 0, 0, 1]
query = [0, 1]

अपेक्षित आउटपुट:
expected = 1
इनपुट:
std::vector<std::vector<long long>> features = {
    {0, 1},
    {0, 0},
    {1, 1},
    {1, 0},
    {0, 1}
};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<long long> query = {0, 1};

अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long[][] features = new long[][] {
    new long[] {0, 1},
    new long[] {0, 0},
    new long[] {1, 1},
    new long[] {1, 0},
    new long[] {0, 1}
};
long[] labels = new long[] {1, 1, 0, 0, 1};
long[] query = new long[] {0, 1};

अपेक्षित आउटपुट:
long expected = 1;

व्याख्या

क्लास 1 में 3 सैंपल हैं और क्लास 0 में 2। फ़ीचर 1 के मान {0, 1} हैं (K = 2), फ़ीचर 2 के {0, 1} (K = 2)। score(1) = 3/5 × (3+1)/(3+2) × (2+1)/(3+2) = 0.6 × 0.8 × 0.6 = 0.288। score(0) = 2/5 × (0+1)/(2+2) × (1+1)/(2+2) = 0.4 × 0.25 × 0.5 = 0.05। क्लास 1 जीतती है।

उदाहरण 2
इनपुट:
features = [
    [0],
    [0],
    [1]
]
labels = [0, 0, 1]
query = [2]

अपेक्षित आउटपुट:
expected = 0
इनपुट:
std::vector<std::vector<long long>> features = {
    {0},
    {0},
    {1}
};
std::vector<long long> labels = {0, 0, 1};
std::vector<long long> query = {2};

अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long[][] features = new long[][] {
    new long[] {0},
    new long[] {0},
    new long[] {1}
};
long[] labels = new long[] {0, 0, 1};
long[] query = new long[] {2};

अपेक्षित आउटपुट:
long expected = 0;

व्याख्या

मान 2 कभी नहीं आता, इसलिए K = 3 (मान 0, 1 और 2)। score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 और score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083। स्मूदिंग की वजह से कोई भी 0 नहीं है, और ज़्यादा आम क्लास 0 जीतती है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

हर class को score करने के लिए उसके prior को feature likelihoods के साथ independence assumption के तहत combine करें।

संकेत 2

Frequency counts के साथ Laplace smoothing का उपयोग करें, और बहुत छोटे products से बचने के लिए classes की तुलना log space में करें।

संकेत 3

हर feature के distinct value count को तय करते समय query values को शामिल करें, और tie होने पर smaller class चुनें।

अपेक्षित जटिलता

समय O(m × n), अतिरिक्त स्थान O(m × n)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

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

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

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

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

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