Задание 1.1 · 5 баллов вместе с 1.2

Своё дерево на ирисах

Пишем дерево с нуля: оно перебирает вопросы «признак < порог?», выбирает тот, что сильнее всего уменьшает беспорядок, и повторяет для каждой половины, пока не сработает критерий остановки.

Данные

Ирисы: 150 цветков трёх видов (setosa, versicolor, virginica), по 50 каждого. Признаки: длина и ширина чашелистика (sepal) и лепестка (petal) в сантиметрах. 70% (105 цветков) на обучение, 30% (45) на проверку.

Узел

Место в дереве, где лежит кучка объектов и задаётся вопрос.

Корень

Самый верхний узел, там вся обучающая выборка.

Лист

Узел без вопроса, в нём ответ: самый частый класс кучки.

Предикат

Вопрос в узле: [x_j < t], «признак j меньше порога t?». Да идёт налево, нет направо.

IG, прирост информации

Насколько уменьшился беспорядок после деления.

Критерий остановки

Правило «этот узел больше не делить».

stratify

При делении на train/test сохранить доли классов, чтобы в test было по 15 цветков каждого вида.

Как выбрать вопрос: прирост информации

Идея: беспорядок до деления минус беспорядок после. Но после деления две кучки разного размера, поэтому беспорядок каждой берём с весом «какая это часть от всех». Это и есть взвешенная формула, которую требует задание.

Попробуй руками

15 точек на одной оси: синие класс 0, оранжевые класс 1. Двигай порог t и смотри, как меняется прирост. Кнопка «Лучший порог» перебирает все t и берёт наибольший IG, так же делает best_split.

Критерии остановки

Код, кусок 1: деление и прирост

impurity_functions = {'entropy': entropy, 'gini': gini_index, 'mse': mse}


def split_node(X, y, feature, threshold):
    mask = (X[feature] < threshold).to_numpy()
    return X[mask], y[mask], X[~mask], y[~mask]


def information_gain(y, y_left, y_right, impurity):
    w_left, w_right = len(y_left) / len(y), len(y_right) / len(y)
    return impurity(y) - (w_left * impurity(y_left) + w_right * impurity(y_right))

1. impurity_functions словарь «название → функция». Ссылки берутся сейчас: в задании 3 имя mse займёт другая функция с двумя аргументами, а дерево должно помнить старую.
2. X[feature] < threshold pandas сравнивает весь столбец с порогом, получается маска True/False.
3. X[mask], X[~mask] строки, где True (налево), и где False (направо). ~ значит «наоборот».
4. w_left, w_right веса: доля объектов в левой и правой части.
5. impurity(y) - (...) ровно формула IG выше. impurity это энтропия, Джини или MSE.

Код, кусок 2: узел и проверка остановки

class TreeNode:
    def __init__(self, value, impurity, n_samples, depth):
        self.value = value          # ответ узла: самый частый класс
        self.impurity = impurity
        self.n_samples = n_samples
        self.depth = depth
        self.feature = None         # лучший предикат и его прирост
        self.threshold = None
        self.gain = 0.0
        self.left = None            # пока потомков нет, узел является листом
        self.right = None

    def is_leaf(self):
        return self.left is None

1. class TreeNode «карточка» узла: ответ, беспорядок, сколько объектов, глубина.
2. feature, threshold, gain вопрос узла и его прирост; у листа их нет.
3. left, right ссылки на детей. Нет детей значит лист (is_leaf).

    def should_stop(self, y, depth):
        too_deep = self.max_depth is not None and depth >= self.max_depth
        too_small = len(y) < 2 * self.min_samples_leaf
        pure = self.impurity(y) <= self.min_impurity
        return too_deep or too_small or pure

1. too_deep достигли максимальной глубины (если она задана).
2. too_small объектов меньше, чем 2 × min_samples_leaf: тогда при любом делении одна половина будет слишком маленькой.
3. pure беспорядок не больше допуска. При допуске 0 это purity: все одного класса.

Код, кусок 3: поиск лучшего вопроса

    def best_split(self, X, y):
        best = (None, None, 0.0)
        for feature in X.columns:
            order = np.argsort(X[feature].to_numpy(), kind='stable')
            values, y_sorted = X[feature].to_numpy()[order], y[order]
            positions = np.flatnonzero(values[1:] != values[:-1]) + 1
            positions = positions[(positions >= self.min_samples_leaf) & (positions <= len(y) - self.min_samples_leaf)]
            for i in positions:
                gain = information_gain(y, y_sorted[:i], y_sorted[i:], self.impurity)
                if gain > best[2]:
                    best = (feature, (values[i - 1] + values[i]) / 2, gain)
        return best

1. best = (None, None, 0.0) пока лучшего нет; деление принимаем, только если IG больше 0.
2. for feature in X.columns по очереди каждый признак.
3. np.argsort номера объектов по возрастанию признака. Сортируем значения и ответы в одном порядке.
4. positions места, где значение меняется: только там есть смысл ставить порог. Например, значения 1.4, 1.4, 1.5: порог между двумя 1.4 ничего не делит.
5. вторая строка с positions оставляет только такие места, где слева и справа хотя бы min_samples_leaf объектов.
6. y_sorted[:i], y_sorted[i:] первые i объектов идут налево, остальные направо. После сортировки это и есть деление «меньше порога / не меньше».
7. (values[i - 1] + values[i]) / 2 порог ставим посередине между соседними значениями, как sklearn.

Код, кусок 4: рост дерева и предсказание

    def fit(self, X, y):
        X = pd.DataFrame(X).reset_index(drop=True)
        y = np.asarray(y)
        self.root = self.create_node(X, y, depth=0)
        self.n_leaves = 1
        queue = [(self.root, X, y)] if self.root.gain > 0 else []
        while queue and (self.max_leaves is None or self.n_leaves < self.max_leaves):
            best = max(range(len(queue)), key=lambda k: queue[k][0].gain * queue[k][0].n_samples)
            node, X_node, y_node = queue.pop(best)
            X_left, y_left, X_right, y_right = split_node(X_node, y_node, node.feature, node.threshold)
            node.left = self.create_node(X_left, y_left, node.depth + 1)
            node.right = self.create_node(X_right, y_right, node.depth + 1)
            self.n_leaves += 1
            for child, X_child, y_child in [(node.left, X_left, y_left), (node.right, X_right, y_right)]:
                if child.gain > 0:
                    queue.append((child, X_child, y_child))
        return self

1. create_node делает узел: считает ответ и беспорядок, и если остановка не сработала, сразу ищет лучший вопрос.
2. queue список листьев, которые ещё можно делить (у них нашёлся вопрос с IG > 0).
3. while пока есть что делить и листьев меньше лимита.
4. max(..., key=gain * n_samples) первым делим лист, где деление уменьшает общий беспорядок сильнее всего. Так делает sklearn при max_leaf_nodes.
5. split_node делим кучку; дети создаются через тот же create_node.
6. n_leaves += 1 один лист превратился в два: листьев стало на 1 больше.

    def predict_one(self, row):
        node = self.root
        while not node.is_leaf():
            node = node.left if row[node.feature] < node.threshold else node.right
        return node.value

    def predict(self, X):
        X = pd.DataFrame(X)
        return np.array([self.predict_one(row) for row in X.to_dict('records')])

1. predict_one один цветок спускается от корня: отвечает на вопрос, идёт налево или направо, пока не дойдёт до листа.
2. X.to_dict('records') датафрейм превращается в список строк-словарей вида {'petal length (cm)': 1.4, ...}.
3. predict принимает датафрейм, как требует задание, и возвращает массив ответов.

Поиграй: проведи цветок по дереву

Это настоящее дерево из ноутбука (лимит 5 листьев). Двигай размеры цветка и смотри, по какому пути он идёт: так работает predict_one.

Результат

• Accuracy = доля верных ответов. В test 45 цветков, одна ошибка = 0.022. 0.933 это 42 из 45, 0.889 это 40 из 45.
• Число листьев и глубина совпали с sklearn во всех 4 вариантах: алгоритм тот же.
• Разница в 1-2 цветка из-за ничьих: в корне и «petal length < 2.45», и «petal width < 0.8» одинаково идеально отделяют setosa. Мы берём первый найденный признак, sklearn перебирает признаки в случайном порядке.
• Ошибки только между versicolor и virginica, setosa отделяется без ошибок.

petal length (cm) < 2.45 ?   (объектов 105, хаос 1.585)
    да:  ответ: 0   (объектов 35, хаос 0.000)
    нет: petal width (cm) < 1.55 ?   (объектов 70, хаос 1.000)
        да:  petal length (cm) < 4.95 ?   (объектов 34, хаос 0.191)
            да:  ответ: 1   (объектов 33, хаос 0.000)
            нет: ответ: 2   (объектов 1, хаос 0.000)
        нет: sepal length (cm) < 6.10 ?   (объектов 36, хаос 0.310)
            да:  ответ: 2   (объектов 8, хаос 0.811)
            нет: ответ: 2   (объектов 28, хаос 0.000)

Так выглядит наше дерево с лимитом 5 листьев (печатает метод print_tree). Ответ 0 = setosa, 1 = versicolor, 2 = virginica.

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