Задание 1 · основа дерева

Как измерить беспорядок

Дереву нужно число, которое говорит, насколько в куче объектов «всё перемешано». Пишем три таких числа: энтропию и индекс Джини для классов и MSE для чисел.

Идея словами

Дерево делит объекты на две кучки. Хорошее деление то, после которого в каждой кучке почти одинаковые ответы. Чтобы сравнивать деления, нужна мера беспорядка: 0, если в кучке всё одинаковое, и больше, чем сильнее перемешано.

Доля класса p

Какая часть кучки относится к классу: 5 чёрных из 6 носков, p = 5/6.

Энтропия

Мера неопределённости из теории информации. Измеряется в битах: 1 бит = один вопрос «да/нет», который ещё нужно задать.

Индекс Джини

Вероятность ошибиться, если взять случайный объект и приписать ему случайную метку из той же кучки.

MSE (для регрессии)

Средний квадрат отклонения от среднего, то есть дисперсия: насколько числа в кучке разбросаны.

log₂

Логарифм по основанию 2: в какую степень возвести 2, чтобы получить число. log₂ 8 = 3, потому что 2³ = 8.

Поиграй: корзина носков

Добавляй и убирай носки трёх цветов и смотри, как меняются энтропия и Джини. Попробуй: все одного цвета; поровну двух цветов; поровну трёх.

Формулы с числами

Кучка [0, 0, 0, 0, 0, 1]: пять нулей и одна единица, доли 5/6 и 1/6.

Код (ячейка с функционалами)

def entropy(y):  # y - массив значений целевой переменной
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()           # доли классов p_k
    return np.sum(p * np.log2(1 / p))   # то же, что -sum(p * log2(p)), но чистый узел даёт 0.0, а не -0.0


def gini_index(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return 1 - np.sum(p ** 2)

def mse(y):
    y = np.asarray(y, dtype=float)
    return np.mean((y - y.mean()) ** 2)

1. np.unique(y, return_counts=True) находит разные значения и сколько раз каждое встретилось. Для [0,0,0,0,0,1] это значения [0, 1] и счётчики [5, 1]. Значения нам не нужны, поэтому _.
2. p = counts / counts.sum() делим счётчики на общее число: [5/6, 1/6]. Делится сразу весь массив, без цикла.
3. np.sum(p * np.log2(1 / p)) формула энтропии. log₂(1/p) = -log₂(p), поэтому минус уходит внутрь. Зачем: для чистой кучки p = 1, и обычная формула даёт «-0.0», а тест сравнивает с 0.0 через ==. Так получается ровно 0.0.
4. 1 - np.sum(p ** 2) Джини: единица минус сумма квадратов долей.
5. np.asarray(y, dtype=float) превращаем список в массив numpy, чтобы вычитать из него число.
6. np.mean((y - y.mean()) ** 2) среднее квадратов отклонений от среднего.

Вопросы на защите