Энтропия измеряет неопределённость набора меток: H(S) = -Σ pₖ × log₂(pₖ), где pₖ — доля меток класса k. Прирост информации — это то, насколько падает энтропия при разбиении набора по признаку:
IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)
где Sᵥ содержит метки примеров, у которых признак равен v. Деревья решений выбирают признак с наибольшим приростом.
Реализуйте information_gain(feature, labels).
Входные данные
feature: значение признака для каждого примера.
labels: метка класса каждого примера (той же длины).
Выходные данные
Верните прирост информации в битах как дробное число.
Ограничения
1 ≤ длина ≤ 10 000
Каждое значение и метка — от 1 до 20 символов
Примеры
Ввод:
labels = ["no", "no", "yes", "yes"]
feature = ["sunny", "sunny", "rain", "rain"]
Ожидаемый вывод:
expected = 1.0Ввод:
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
Ожидаемый вывод:
double expected = 1.0;Ввод:
string[] labels = new string[] {"no", "no", "yes", "yes"};
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
Ожидаемый вывод:
double expected = 1.0;Пояснение
Метки наполовину yes и наполовину no, поэтому H = 1 бит. Разбиение по погоде даёт две чистые группы (H = 0 у каждой), поэтому прирост равен 1 - 0 = 1: признак говорит всё.
Ввод:
labels = ["yes", "yes", "no", "no"]
feature = ["a", "b", "a", "b"]
Ожидаемый вывод:
expected = 0.0Ввод:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
std::vector<std::string> feature = {"a", "b", "a", "b"};
Ожидаемый вывод:
double expected = 0.0;Ввод:
string[] labels = new string[] {"yes", "yes", "no", "no"};
string[] feature = new string[] {"a", "b", "a", "b"};
Ожидаемый вывод:
double expected = 0.0;Пояснение
В каждой группе a и b по-прежнему один yes и один no (H = 1), поэтому остаток равен 0.5 × 1 + 0.5 × 1 = 1, а прирост — 1 - 1 = 0: признак бесполезен.
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.