Предполагается изучение литературы 😮
Решающие деревья - строго математично
Задание на реализацию дерева решений из курса МГУ
Дополнительно, если интересно:
Основные понятия машинного обучения
Деревья бывают разные - черный, белые, красные. И все их одинаково хочется запрограммировать. Но возникает резонный вопрос - а где же их использовать и зачем они вообще нужны? Мы с вами уже бегло познакомились с обычным бинарным деревом поиска, когда писали своё множество (Set), чтобы хранить только уникальные объекты, причем эффективно. Дальнейшим развитием идеи мог бы стать словарь (Ductionary, Map). Для его эффективной реализации нам бы стоило познакомиться с типом данных 2-3-дерево или красно-черное дерево.
В общем случае, как вы уже поняли, деревья используют для поиска и для создания какого-то порядка (можно написать сортировку с помощью деревьев). И если развить эту идею дальше, то можно написать алгоритм принятия решений. В этом случае мы будем в дереве искать ответы на вопросы и в результате спустимся к листьям - ответам.
На этой практике мы будем реализовывать структуру данных для принятия решений, используя дерево поиска. На самом деле это уже структура данных из семейства алгоритмов машинного обучения. Таким образом наше дерево в процессе своего построения будет учиться принимать решения и в конце предсказывать некоторые результаты на основе новых данных. То есть будет искать ответы на вопросы, оно же дерево поиска!
Пусть у нас есть некоторый набор данных, который удобно представить в виде таблицы, где в строках - объекты.
Рост, Вес, Гендер называют признаками объектов. Если мы хотим построить модель предсказания пола человека по его весу и росту, тогда мы будем говорить, что Рост, Вес - это известные признаки X, а Гендер - это целевой признак(переменная) Y.
Задача машинного обучения - это найти некоторую функцию f, что $f(X) \rightarrow Y$. Предполагается, что f - это некоторый “закон природы”, который мы можем изучить в процессе обучения, чтобы потом предсказывать значения целевой переменной на новых данных, которые мы никогда не видели.
Рассмотрим пример дерева для датасета о выживших на Титанике.
Как мы видим в узлах задаются вопросы к объектам по какому-то признаку. А в листьях ответы - предсказания.
Но как по большому набору данных построить одно дерево так, чтобы оно лучше всего предсказывало целевую переменную?