Энтропия измеряет неопределённость набора меток: 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 символов
Примеры
Ввод:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]
Ожидаемый вывод:
expected = 1.0
Ввод:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
Ожидаемый вывод:
double expected = 1.0;
Ввод:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};
Ожидаемый вывод:
double expected = 1.0;
Пояснение
Метки наполовину yes и наполовину no, поэтому H = 1 бит. Разбиение по погоде даёт две чистые группы (H = 0 у каждой), поэтому прирост равен 1 - 0 = 1: признак говорит всё.
Ввод:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]
Ожидаемый вывод:
expected = 0.0
Ввод:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
Ожидаемый вывод:
double expected = 0.0;
Ввод:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};
Ожидаемый вывод:
double expected = 0.0;
Пояснение
В каждой группе a и b по-прежнему один yes и один no (H = 1), поэтому остаток равен 0.5 × 1 + 0.5 × 1 = 1, а прирост — 1 - 1 = 0: признак бесполезен.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сначала измерьте неопределённость метки до любого разбиения, затем сравните её с неопределённостью внутри каждой группы признака.
Подсказка 2
Сгруппируйте примеры по значению признака, посчитайте метки в каждой группе и сложите энтропию каждой группы с учётом её доли данных.
Подсказка 3
Осторожно с повторяющимися значениями и случаем, когда в группе только одна метка: тогда вклад энтропии равен нулю.
Ожидаемая сложность
O(n) по времени, O(n) по дополнительной памяти
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.