Понимание математики, лежащей в основе деревьев решений

Изучение деревьев решений: математические основы, классификация, преимущества и ограничения

В этом посте мы подробно рассмотрим один из самых простых и наиболее интерпретируемых алгоритмов контролируемого обучения - деревья решений. Алгоритмы дерева решений могут использоваться как для классификации, так и для регрессии. Мы обсудим, как работает алгоритм, что такое индукция, параметры, определяющие его структуру, а также его преимущества и ограничения.

Алгоритм дерева решений

Дерево решений - это эффективный алгоритм для описания способа обхода набора данных, а также определения древовидного пути к ожидаемым результатам. Это ветвление в дереве основано на управляющих операторах или значениях, а точки данных лежат по обе стороны от узла разделения, в зависимости от значения конкретной функции.

Структура дерева решений может быть определена корневым узлом, который является наиболее важной функцией разделения. Внутренние узлы - это тесты атрибута. Например, если внутренний узел имеет управляющий оператор (age ‹40), то точки данных, удовлетворяющие этому условию, находятся с одной стороны, а остальные - с другой. Листовые узлы принадлежат доступным классам, которые представляет набор данных.

Алгоритм можно понять с помощью следующего псевдокода:

Присоединяйтесь к более чем 14000 ваших коллег по машинному обучению и исследователей данных. Подпишитесь на главную рассылку новостей по глубокому обучению.

Пример индукции дерева решений

Применяя вышеупомянутый алгоритм к проблеме принятия решения, идти пешком или ехать на автобусе, мы можем разработать дерево решений, выбрав корневой узел, внутренние узлы, листовые узлы, а затем определив шаг за шагом критерии разделения для класса. . Мы выбираем самый важный узел в качестве корневого узла, которым является погода. В зависимости от погоды и других условий, таких как время и голод, мы можем построить наше дерево следующим образом:

Как мы узнаем, где делиться?

Мера выбора атрибута - это эвристика для выбора критерия разделения, который наиболее подходит для принятия решения о том, как разделить данные таким образом, чтобы в результате были выделены отдельные классы. Меры выбора атрибутов также известны как правила разделения, поскольку они определяют, как точки данных должны быть разделены на определенном уровне в дереве решений. Атрибут, имеющий наилучшую оценку для меры, выбирается в качестве атрибута разделения для данных точек данных.

Вот некоторые основные меры по выбору атрибутов:

1. Прирост информации: этот атрибут предоставляет нам атрибут разделения с точки зрения количества информации, необходимой для дальнейшего описания дерева. Прирост информации сводит к минимуму информацию, необходимую для классификации точек данных по соответствующим разделам, и отражает наименьшую случайность или «примесь» в этих разделах.

pi - это вероятность того, что произвольный кортеж в наборе данных D принадлежит классу Ci и оценивается как | Ci, D | / | D |. Информация (D) - это просто средний объем информации, необходимый для определения класса / категории точки данных в D. Используется функция журнала с основанием 2, поскольку в большинстве случаев информация кодируется в битах.

Информация (D) также известна как энтропия набора данных D.

Информационный прирост можно рассчитать следующим образом:

2. Коэффициент выигрыша. Показатель сбора информации смещен в сторону тестов с множеством результатов. Таким образом, он предпочитает выбирать атрибуты с большим количеством значений. Коэффициент усиления - это попытка решить эту проблему.

3. Индекс Джини. Индекс Джини рассчитывается следующим образом:

где pi - вероятность того, что набор в D принадлежит классу Ci и оценивается как | Ci, D | / | D |. Сумма вычисляется по m классам.

Индекс Джини учитывает двоичное разбиение для каждого атрибута. Например, если у возраста есть три возможных значения, а именно {низкий, средний, высокий}, тогда возможными подмножествами являются {низкий, средний, высокий}, {низкий, средний}, {низкий, высокий}, {средний, высокий}, {low}, {medium}, {high} и {} (игнорируя power и super set в наших расчетах).

Обрезка

Когда дерево решений построено, многие ветви будут отражать аномалии в обучающих данных из-за шума или выбросов. Незначительные изменения значений могут привести к совершенно другим результатам.

Для устранения этого несоответствия, вызванного переобучением, используются несколько методов. Обрезка дерева - один из таких методов, который обычно использует статистические меры для удаления наименее надежных ветвей или ветвей, поддерживаемых небольшим количеством выборок.

Обрезанные деревья, как правило, меньше и менее сложны, поэтому их легче понять. Кроме того, они обычно быстрее и лучше классифицируют данные независимых тестов. Для обрезки можно использовать различные методы, такие как предварительная обрезка, последующая обрезка и пессимистическая обрезка.

Реализация деревьев решений в scikit-learn

Чтобы применить алгоритм на Python с помощью sklearn, достаточно четырех строк: импортировать классификатор, создать экземпляр, подогнать данные в обучающий набор и спрогнозировать результаты для тестового набора:

>>> from sklearn.datasets import load_iris
>>> from sklearn.tree import DecisionTreeClassifier
>>> from sklearn.tree.export import export_text
>>> iris = load_iris()
>>> decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2)
>>> decision_tree = decision_tree.fit(iris.data, iris.target)
>>> r = export_text(decision_tree, feature_names=iris['feature_names'])
>>> print(r)
|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal width (cm) <= 1.75
|   |   |--- class: 1
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2
<BLANKLINE>

Настройка параметров в scikit-learn:

1. max_depth: int, по умолчанию = None. определяет максимальную глубину дерева. Если None, то узлы расширяются до тех пор, пока все листья не станут чистыми или пока все листья не будут содержать менее min_samples_split выборок.
2. min_samples_split: int или float, по умолчанию = 2. Минимальное количество выборок, необходимое для разделения узла - минимум 2 выборки требуются для разделения узла. Может быть настроен в соответствии с функциями и их значениями.
3. min_samples_leaf: int или float, по умолчанию = 1. Предоставляет информацию о t минимальном количестве выборок, которое требуется для конечного узла. Это помогает сглаживать модель.