ตัวจำแนกแบบ Naive Bayes

Naive Bayes สมมติว่าฟีเจอร์เป็นอิสระต่อกันเมื่อรู้คลาสแล้ว และเลือกคลาสที่มีคะแนนสูงที่สุด:

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 ในตัวอย่างฝึก และ query ส่วน +1 (การปรับเรียบแบบลาปลาซ) ป้องกันไม่ให้ค่าที่ไม่เคยเห็นทำให้คะแนนเป็น 0

คืนค่าคลาสที่มีคะแนนสูงที่สุด ถ้าคะแนนเท่ากันให้คืนคลาสที่น้อยกว่า การคูณความน่าจะเป็นเล็กๆ จำนวนมากอาจทำให้ค่าเล็กจนปัดเป็นศูนย์ จึงควรบวกลอการิทึมแทน

จงเขียน naive_bayes_predict(features, labels, query)

อินพุต

features: หนึ่งแถวของฟีเจอร์แบบหมวดหมู่ n ตัวต่อตัวอย่างฝึก

labels: คลาสของแต่ละตัวอย่างฝึก

query: ฟีเจอร์ n ตัวของตัวอย่างที่ต้องการจำแนก

เอาต์พุต

คืนค่าคลาสที่ทำนายได้

เงื่อนไข

1 ≤ จำนวนตัวอย่าง ≤ 1,000, 1 ≤ n ≤ 20

0 ≤ ค่าฟีเจอร์และป้ายกำกับแต่ละค่า ≤ 100

ตัวอย่าง

อินพุต:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
    [0, 1],
    [0, 0],
    [1, 1],
    [1, 0],
    [0, 1]
]

ผลลัพธ์ที่คาดหวัง:
expected = 1

อินพุต:
std::vector<long long> query = {0, 1};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<std::vector<long long>> features = {
    {0, 1},
    {0, 0},
    {1, 1},
    {1, 0},
    {0, 1}
};

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;

อินพุต:
long[] query = new long[] {0, 1};
long[] labels = new long[] {1, 1, 0, 0, 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 expected = 1;

อินพุต:
query = [2]
labels = [0, 0, 1]
features = [
    [0],
    [0],
    [1]
]

ผลลัพธ์ที่คาดหวัง:
expected = 0

อินพุต:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
    {0},
    {0},
    {1}
};

ผลลัพธ์ที่คาดหวัง:
long long expected = 0;

อินพุต:
long[] query = new long[] {2};
long[] labels = new long[] {0, 0, 1};
long[][] features = new long[][] {
    new long[] {0},
    new long[] {0},
    new long[] {1}
};

ผลลัพธ์ที่คาดหวัง:
long expected = 0;

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

• scikit-learn, Naive Bayes (CategoricalNB)
• Stanford CS229 Machine Learning, lecture notes