Дерево решений - это структура, подобная блок-схеме, в которой каждый внутренний узел представляет test на объекте (например, выпадает ли подбрасывание монеты орлом или решкой), каждый листовой узел представляет class label (решение, принятое после вычисления всех функций), а ветви представляют соединения функций, которые приводят к этим меткам классов. Пути от корня к листу представляют classification rules. На диаграмме ниже показан основной поток дерева решений для принятия решений с пометками (Дождь (Да), Нет Дождя (Нет)).
Дерево решений - это один из подходов к прогнозному моделированию, используемых в statistics, data mining и machine learning.
Деревья решений строятся с помощью алгоритмического подхода, который определяет способы разделения набора данных на основе различных условий. Это один из наиболее широко используемых и практичных методов обучения с учителем. Деревья решений - это непараметрический метод обучения с учителем, используемый как для задач классификации, так и регрессии.
Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. Деревья решений, в которых целевая переменная может принимать непрерывные значения (обычно действительные числа), называются деревьями регрессии. Дерево классификации и регрессии (CART) - это общий термин для этого.
В этом посте я попытаюсь объяснить это на примерах.
Формат данных
Данные поступают в виде записей форм.
(x,Y)=(x1,x2,x3,....,xk,Y)Зависимая переменная Y - это целевая переменная, которую мы пытаемся понять, классифицировать или обобщить. Вектор x состоит из функций x1, x2, x3 и т. Д., Которые используются для этой задачи.
Пример
training_data = [
['Green', 3, 'Apple'],
['Yellow', 3, 'Apple'],
['Red', 1, 'Grape'],
['Red', 1, 'Grape'],
['Yellow', 3, 'Lemon'],
]
# Header = ["Color", "diameter", "Label"]
# The last column is the label.
# The first two columns are features.Подход к составлению дерева решений
При построении дерева решений на каждом узле дерева мы задаем вопросы разного типа. На основании заданного вопроса мы рассчитаем соответствующий ему информационный выигрыш.
Получение информации
Полученная информация используется для того, чтобы решить, какие функции следует разделять на каждом этапе построения дерева. Лучше всего простота, поэтому мы хотим, чтобы наше дерево было небольшим. Для этого на каждом шаге мы должны выбирать разбиение, которое приводит к чистейшим дочерним узлам. Обычно используемый показатель чистоты называется информацией. Для каждого узла дерева информационное значение измеряет, сколько information функция дает нам о классе. Разделение с наибольшим приростом информации будет считаться первым разбиением, и процесс будет продолжаться до тех пор, пока все дочерние узлы не станут чистыми или пока прирост информации не станет равным 0.
Задавая вопрос
class Question: """A Question is used to partition a dataset.This class just records a 'column number' (e.g., 0 for Color) and a 'column value' (e.g., Green). The 'match' method is used to compare the feature value in an example to the feature value stored in the question. See the demo below. """def __init__(self, column, value): self.column = column self.value = valuedef match(self, example): # Compare the feature value in an example to the # feature value in this question. val = example[self.column] if is_numeric(val): return val >= self.value else: return val == self.valuedef __repr__(self): # This is just a helper method to print # the question in a readable format. condition = "==" if is_numeric(self.value): condition = ">=" return "Is %s %s %s?" % ( header[self.column], condition, str(self.value))
Давайте попробуем задавать вопросы и их результаты.
Question(1, 3) ## Is diameter >= 3?
Question(0, "Green") ## Is color == Green?Теперь мы попробуем разделить набор данных на основе заданного вопроса. На каждом этапе данные будут разделены на два класса.
def partition(rows, question): """Partitions a dataset.For each row in the dataset, check if it matches the question. If so, add it to 'true rows', otherwise, add it to 'false rows'. """ true_rows, false_rows = [], [] for row in rows: if question.match(row): true_rows.append(row) else: false_rows.append(row) return true_rows, false_rows # Let's partition the training data based on whether rows are Red. true_rows, false_rows = partition(training_data, Question(0, 'Red')) # This will contain all the 'Red' rows. true_rows ## [['Red', 1, 'Grape'], ['Red', 1, 'Grape']] false_rows ## [['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]
Алгоритм построения дерева решений обычно работает сверху вниз, выбирая переменную на каждом шаге, которая best разбивает набор элементов. В разных алгоритмах используются разные метрики для измерения best.
Джини примеси
Сначала давайте разберемся, что означает чистый и нечистый.
Чистый
Чистый означает, что в выбранной выборке набора данных все данные принадлежат одному классу (PURE).
Нечистый
Нечистота означает, что данные представляют собой смесь разных классов.
Определение примеси Джини
Примесь Джини - это измерение вероятности неправильной классификации нового экземпляра случайной величины, если этот новый экземпляр был случайно классифицирован в соответствии с распределением меток классов из набора данных.
Если наш набор данных Pure, тогда вероятность неправильной классификации равна 0. Если наша выборка представляет собой смесь разных классов, вероятность неправильной классификации будет высокой.
Расчет примеси Джини.
def gini(rows):
"""Calculate the Gini Impurity for a list of rows.
There are a few different ways to do this, I thought this one was
the most concise. See:
https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity
"""
counts = class_counts(rows)
impurity = 1
for lbl in counts:
prob_of_lbl = counts[lbl] / float(len(rows))
impurity -= prob_of_lbl**2
return impurity
Пример
# Demo 1:
# Let's look at some example to understand how Gini Impurity works.
#
# First, we'll look at a dataset with no mixing.
no_mixing = [['Apple'],
['Apple']]
# this will return 0
gini(no_mixing) ## output=0
## Demo 2:
# Now, we'll look at dataset with a 50:50 apples:oranges ratio
some_mixing = [['Apple'],
['Orange']]
# this will return 0.5 - meaning, there's a 50% chance of misclassifying
# a random example we draw from the dataset.
gini(some_mixing) ##output=0.5
## Demo 3:
# Now, we'll look at a dataset with many different labels
lots_of_mixing = [['Apple'],
['Orange'],
['Grape'],
['Grapefruit'],
['Blueberry']]
# This will return 0.8
gini(lots_of_mixing) ##output=0.8
#######Шаги по созданию дерева решений
- Получить список строк (набор данных), которые учитываются при построении дерева решений (рекурсивно на каждом узле).
- Вычислите
uncertanityнашего набора данных илиGini impurity, или сколько нашегоdata is mixed upи т. Д. - Сгенерируйте список всех вопросов, которые нужно задать на этом узле.
- Разделите строки на
True rowsиFalse rowsв зависимости от каждого заданного вопроса. - Рассчитайте прирост информации на основе примеси Джини и разделения данных из предыдущего шага.
- Обновите максимальный объем информации на основе каждого заданного вопроса.
- Обновите лучший вопрос на основе получения информации (более высокий объем информации).
- Разделите узел на лучший вопрос. Повторите еще раз с шага 1, пока мы не получим чистый узел (листовые узлы).
Код для вышеперечисленных шагов
def find_best_split(rows): """Find the best question to ask by iterating over every feature / value and calculating the information gain.""" best_gain = 0 # keep track of the best information gain best_question = None # keep train of the feature / value that produced it current_uncertainty = gini(rows) n_features = len(rows[0]) - 1 # number of columnsfor col in range(n_features): # for each featurevalues = set([row[col] for row in rows]) # unique values in the columnfor val in values: # for each valuequestion = Question(col, val)# try splitting the dataset true_rows, false_rows = partition(rows, question)# Skip this split if it doesn't divide the # dataset. if len(true_rows) == 0 or len(false_rows) == 0: continue# Calculate the information gain from this split gain = info_gain(true_rows, false_rows, current_uncertainty)# You actually can use '>' instead of '>=' here # but I wanted the tree to look a certain way for our # toy dataset. if gain >= best_gain: best_gain, best_question = gain, questionreturn best_gain, best_question ####### # Demo: # Find the best question to ask first for our toy dataset. best_gain, best_question = find_best_split(training_data) best_question ## output - Is diameter >= 3?
Теперь создайте дерево решений на основе описанного выше шага рекурсивно на каждом узле.
def build_tree(rows): """Builds the tree.Rules of recursion: 1) Believe that it works. 2) Start by checking for the base case (no further information gain). 3) Prepare for giant stack traces. """# Trypartitioningthe dataset on each of the unique attribute, # calculate the information gain, # and return the question that produces the highest gain. gain, question = find_best_split(rows)# Base case: no further info gain # Since we can ask no further questions, # we'll return a leaf. if gain == 0: return Leaf(rows)# If we reach here, we have found a useful feature / value # to partition on. true_rows, false_rows = partition(rows, question)# Recursively build the true branch. true_branch = build_tree(true_rows)# Recursively build the false branch. false_branch = build_tree(false_rows)# Return a Question node. # This records the best feature / value to ask at this point, # as well as the branches to follow # dependingo on the answer. return Decision_Node(question, true_branch, false_branch)
Построение дерева решений
Построим дерево решений на основе данных обучения.
training_data = [
['Green', 3, 'Apple'],
['Yellow', 3, 'Apple'],
['Red', 1, 'Grape'],
['Red', 1, 'Grape'],
['Yellow', 3, 'Lemon'],
]
# Header = ["Color", "diameter", "Label"]
# The last column is the label.
# The first two columns are features.
my_tree = build_tree(training_data)
print_tree(my_tree)Вывод
Is diameter >= 3?
--> True:
Is color == Yellow?
--> True:
Predict {'Lemon': 1, 'Apple': 1}
--> False:
Predict {'Apple': 1}
--> False:
Predict {'Grape': 2}Из вышеприведенного вывода мы видим, что на каждом шаге данные делятся на True и False строк. Этот процесс повторяется до тех пор, пока мы не дойдем до листового узла, где информационный прирост равен 0, и дальнейшее разделение данных невозможно, поскольку узлы являются чистыми.
Преимущество дерева решений
- Легко использовать и понимать.
- Может обрабатывать как категориальные, так и числовые данные.
- Устойчив к выбросам, поэтому требует небольшой предварительной обработки данных.
Недостаток дерева решений
- Склонен к переобучению.
- Требуется какое-то измерение того, насколько хорошо они справляются.
- Будьте осторожны с настройкой параметров.
- Может создавать предвзятые заученные деревья, если некоторые классы доминируют.
Как избежать переобучения модели дерева решений
Переоснащение - одна из основных проблем для каждой модели машинного обучения. Если модель переоборудована, она плохо переносится на новые образцы. Чтобы дерево решений не переоснащалось , мы удаляем ветви, в которых используются маловажные функции. Этот метод называется обрезкой или последующей обрезкой. Таким образом мы уменьшим сложность дерева и, следовательно, улучшим точность прогнозов за счет уменьшения переобучения.
Сокращение должно уменьшать размер дерева обучения без снижения точности прогнозов, измеряемой набором перекрестной проверки. Есть 2 основных метода обрезки.
- Минимальная ошибка. Дерево сокращается до точки, в которой ошибка перекрестной проверки является минимальной.
- Наименьшее дерево. Дерево обрезается немного дальше, чем минимальная ошибка. Технически отсечение создает дерево решений с ошибкой перекрестной проверки в пределах 1 стандартной ошибки минимальной ошибки.
Ранняя остановка или предварительная обрезка
Альтернативный метод предотвращения переобучения - это попытаться остановить процесс построения дерева на раннем этапе, прежде чем он даст листья с очень маленькими образцами. Эта эвристика известна как ранняя остановка, но также иногда известна как предварительное сокращение деревьев решений.
На каждом этапе разбиения дерева мы проверяем ошибку перекрестной проверки. Если ошибка не уменьшилась достаточно значительно, то останавливаемся. Ранняя остановка может оказаться недостаточной из-за слишком ранней остановки. Текущее разбиение может принести мало пользы, но, сделав его, последующие разбиения значительно уменьшают ошибку.
Раннюю остановку и обрезку можно использовать вместе, по отдельности или совсем не использовать. Деревья решений после обрезки более строгие с математической точки зрения, поиск дерева по крайней мере не хуже ранней остановки. Ранняя остановка - это эвристика быстрого исправления. Если использовать вместе с обрезкой, ранняя остановка может сэкономить время. В конце концов, зачем строить дерево только для того, чтобы его снова обрезать?
Дерево решений в реальной жизни
- Выбор рейса для путешествия
Предположим, вам нужно выбрать рейс для следующего путешествия. Как мы это делаем? Сначала мы проверяем, доступен ли рейс в этот день или нет. Если он недоступен, мы будем искать другую дату, но если она доступна, мы ищем, возможно, продолжительность полета. Если мы хотим иметь только прямые рейсы, мы смотрим, входит ли цена этого рейса в ваш заранее определенный бюджет или нет. Если это слишком дорого, мы ищем другие рейсы, иначе бронируем!
- Как справиться с ночной тягой
В реальной жизни существует гораздо больше применений дерева решений. Вы можете отметить это и это, чтобы узнать о других приложениях дерева решений.
В этой статье я попытался объяснить основы дерева решений и то, как оно в основном работает. Вы можете найти исходный код, использованный в этой статье, на github.
Надеюсь, вам понравилась эта статья. По поводу любых изменений, предложений, пожалуйста, напишите мне прямо в этой статье или в LinkedIn. Удачного обучения - Ура :)
