Train a multinomial Naive Bayes classifier and label new messages.
What to build
A program that trains Naive Bayes with add-one smoothing and classifies messages.
Requirements
- Training lines are
label: text; lowercase and split on whitespace. V is the number of distinct training words. - For a message, ignore words that never occurred in training. A class's score is ln(prior) plus the sum over the remaining words (repeats included) of ln((count of the word in the class + 1) ÷ (word tokens in the class + V)).
- For each message print the best label, then each label's score as
label=Swith three decimal places, labels in alphabetical order. On a tie, choose the alphabetically first label.
Input
Line 1: n. Then n training lines. Then m and m messages.
Output
m lines.
Constraints
n ≤ 500; m ≤ 100.
Example
Input:
4
spam: win money now
spam: win a free prize now
ham: meeting at noon
ham: lunch at noon with the team
2
free lunch now
lunch at noon
Output:
spam ham=-9.273 spam=-8.035
ham ham=-7.076 spam=-9.827
Why it works
Adding log probabilities is the same as multiplying the prior by each word's likelihood, so the highest score is the class that makes the message most probable, and smoothing keeps every class possible.
Examples
4 spam: win money now spam: win a free prize now ham: meeting at noon ham: lunch at noon with the team 2 free lunch now lunch at noon
spam ham=-9.273 spam=-8.035 ham ham=-7.076 spam=-9.827
3 pos: good fun neg: bad boring pos: great 2 good movie boring
pos neg=-3.045 pos=-1.792 neg neg=-2.351 pos=-2.485
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
score = `math.log(prior)` plus, for each known word of the message, `math.log((count + 1) / (class words + V))`.
Hint 2
`max(labels, key=lambda c: scores[c])` with labels in alphabetical order returns the alphabetically first label on a tie.
Solution
Show one correct solution (try it yourself first)
import math
n = int(input())
docs, counts, totals, vocab = {}, {}, {}, []
for _ in range(n):
label, text = input().split(":", 1)
label = label.strip()
docs[label] = docs.get(label, 0) + 1
counts.setdefault(label, {})
totals.setdefault(label, 0)
for w in text.lower().split():
counts[label][w] = counts[label].get(w, 0) + 1
totals[label] += 1
if w not in vocab:
vocab.append(w)
labels = sorted(docs)
for _ in range(int(input())):
words = [w for w in input().lower().split() if w in vocab]
scores = {}
for label in labels:
s = math.log(docs[label] / n)
for w in words:
s += math.log((counts[label].get(w, 0) + 1) / (totals[label] + len(vocab)))
scores[label] = s
best = max(labels, key=lambda c: scores[c])
print(best, " ".join(f"{c}={scores[c]:.3f}" for c in labels))