OneR ("one rule") is a real, surprisingly strong baseline: it picks the single feature whose simple table of rules makes the fewest mistakes.
What to build
A program that learns a OneR classifier from a table of categorical features and prints its rules.
Requirements
- For each feature and each of its values, the rule predicts the most common label among the rows with that value. If labels tie, choose the alphabetically first.
- A feature's error count is how many training rows its rules get wrong. Choose the feature with the fewest errors; on a tie, the one that comes first.
- Print
feature NAME, thenerrors E, then one rule per value asVALUE -> LABEL, values in alphabetical order.
Input
Line 1: n and k. Line 2: the k feature names. Then n rows, each with k values and a label, separated by spaces.
Output
The chosen feature, its error count and its rules.
Constraints
1 ≤ n ≤ 500, 1 ≤ k ≤ 10; every value and label is one word.
Example
Input:
6 2
outlook windy
sunny no no
sunny yes no
rain no yes
rain yes no
overcast no yes
overcast yes yes
Output:
feature outlook
errors 1
overcast -> yes
rain -> no
sunny -> no
Why it works
Each value's rule is the guess that makes the fewest mistakes inside its group, so adding up the groups gives the feature's best possible score, and comparing those scores picks the most useful single feature.
Examples
6 2 outlook windy sunny no no sunny yes no rain no yes rain yes no overcast no yes overcast yes yes
feature outlook errors 1 overcast -> yes rain -> no sunny -> no
4 1 colour red a red a blue b green a
feature colour errors 0 blue -> b green -> a red -> a
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For one feature, group the rows by that feature's value and find the most common label in each group.
Hint 2
A group's errors are its rows whose label is not the group's most common one; a feature's errors are the sum over its groups.
Hint 3
Break ties between labels alphabetically, and between features by keeping the earlier one.
Solution
Show one correct solution (try it yourself first)
n, k = map(int, input().split())
names = input().split()
rows = [input().split() for _ in range(n)]
best = None
for f in range(k):
groups = {}
for row in rows:
groups.setdefault(row[f], []).append(row[-1])
rules, errors = {}, 0
for value, labels in groups.items():
counts = {}
for label in labels:
counts[label] = counts.get(label, 0) + 1
top = min(counts, key=lambda label: (-counts[label], label))
rules[value] = top
errors += len(labels) - counts[top]
if best is None or errors < best[1]:
best = (f, errors, rules)
f, errors, rules = best
print(f"feature {names[f]}")
print(f"errors {errors}")
for value in sorted(rules):
print(f"{value} -> {rules[value]}")