👩‍💻 Поиск оптимального разбиения признака по энтропии (ID3-style)

У вас есть бинарная целевая переменная y (список из 0 и 1) и числовой признак x (такой же длины). Нужно реализовать функцию best_split(x, y), которая найдёт такое значение признака, при разделении по которому (меньше/больше) будет максимально уменьшена энтропия классов.

Иными словами, нужно найти лучший threshold, при котором данные делятся на две группы по x, и у этих групп наименьшая средняя энтропия. Это базовая операция в построении деревьев решений, например, в алгоритме ID3.

Цель:

Вернуть threshold, который даёт наилучшее (наименьшее) значение средневзвешенной энтропии.

Решение задачи🔽

import numpy as np

def entropy(labels):
if len(labels) == 0:
return 0
p = np.bincount(labels) / len(labels)
return -np.sum([pi * np.log2(pi) for pi in p if pi > 0])

def best_split(x, y):
x = np.array(x)
y = np.array(y)
thresholds = sorted(set(x))
best_entropy = float('inf')
best_thresh = None

for t in thresholds:
left_mask = x <= t
right_mask = x > t
left_entropy = entropy(y[left_mask])
right_entropy = entropy(y[right_mask])
w_left = np.sum(left_mask) / len(x)
w_right = 1 - w_left
avg_entropy = w_left * left_entropy + w_right * right_entropy

if avg_entropy < best_entropy:
best_entropy = avg_entropy
best_thresh = t

return best_thresh

# Пример использования
x = [2, 4, 6, 8, 10, 12]
y = [0, 0, 1, 1, 1, 1]

print(best_split(x, y))
# Ожидаемый результат: значение между 4 и 6 (например, 6), так как оно лучше всего делит классы