The OneR classifier

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, then errors E, then one rule per value as VALUE -> 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

Example 1 · Input
6 2
outlook windy
sunny no no
sunny yes no
rain no yes
rain yes no
overcast no yes
overcast yes yes
Expected output
feature outlook
errors 1
overcast -> yes
rain -> no
sunny -> no
Example 2 · Input
4 1
colour
red a
red a
blue b
green a
Expected output
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]}")

Lesson: What machine learning is →