Наивный Байес предполагает, что при известном классе признаки независимы, и выбирает класс с наибольшей оценкой:
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 ≤ число примеров ≤ 1000, 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;Пояснение
В классе 1 три примера, в классе 0 — два. Признак 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.
Ввод:
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;Пояснение
Значение 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.
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.