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

Что такое дерево решений

Дерево решений - это классификатор в виде дерева (здесь под деревом подразумевается дерево информатики). Это дерево обычно имеет 2 типа узлов: Узлы принятия решений и Узлы-листы.

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

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

Пример

Это пример дерева решений, здесь узлы возраста, учащегося и кредитного рейтинга являются узлами решения, потому что они говорят вам, в каком направлении двигаться в дереве. И все узлы да / нет являются листовыми узлами, поскольку они говорят вам о решении.

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

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

Как рекурсивно построить дерево (Пример)

Допустим, у нас есть обучающие данные D, и мы хотим построить на их основе дерево. На изображении мы видим, что мы разделяем обучающие данные D в корневом каталоге, используя атрибут A5, и таким образом мы получаем 2 узла. D1 - это обучающие данные с атрибутом A5 как «Y», а D2 - обучающие данные с атрибутом A5 как «N». Если у нас есть узел со всеми обучающими данными с одинаковой меткой, мы останавливаем дерево там, иначе на каждом узле у нас есть возможность либо вырастить дерево, либо остановить дерево, если мы решим вырастить дерево, мы должны дополнительно решить, какой атрибут чтобы разбить данные на. На изображении предположим, что данные обучения D2 будут иметь ту же метку, поэтому мы останавливаем дерево на этом, но в D1 мы можем вырастить дерево, потому что оно содержит смесь обеих меток (учитывая, что данные обучения имеют 2 метки). Теперь нам нужно использовать другой атрибут для разделения данных D1 с помощью атрибута A2 (здесь мы выбираем атрибут случайным образом, и позже мы обсудим, как выбрать атрибут, чтобы уменьшить дерево). На изображении D11 - это подмножество данных D1, которые имеют атрибут A2 как «Y», а D12 имеют атрибут A2 как «N». Таким образом мы можем рекурсивно вырастить дерево.

Индукция деревьев решений сверху вниз ID3

Это базовая структура алгоритма дерева решений. На каждом узле мы делаем следующее: -

  1. A - лучший атрибут решения для следующего узла.
  2. Назначьте A как атрибут решения для узла.
  3. Для каждого значения A создать нового потомка
  4. Сортировка обучающих примеров по листовым узлам в соответствии со значением Lattribute ветви (это означает разделение обучающих примеров в соответствии с выбранным выше атрибутом A).
  5. Если все обучающие примеры идеально классифицированы (одно и то же значение целевого атрибута), остановитесь, иначе выполните итерацию по новым листовым узлам.

Здесь у нас 3 вопроса,

  1. Учитывая частичное дерево решений, какой узел выбрать для вышеуказанного алгоритма
  2. Для конкретного узла, какой атрибут лучше всего выбрать.
  3. Когда прекратить рубить дерево.

Дерево решений обучения

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

Когда остановиться

  1. Когда мы исчерпали все атрибуты и у нас нет атрибутов для разделения, мы останавливаем разделение, потому что у нас нет другой возможности.
  2. Когда все примеры узла имеют одинаковое целевое значение, мы можем остановить разделение.
  3. Нам также следует прекратить разбиение, если у нас слишком мало примеров для разбиения. Здесь несколько - это субъективный термин, и его право решать, сколько примеров для него слишком мало.

Какой атрибут разбить на

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

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

У нас есть несколько математических показателей, на основе которых мы решаем, какой атрибут выбрать в конкретном узле, и из них мы обсудим энтропию и получение информации.

Энтропия (S)

Энтропия - это мера чистоты или мера неопределенности.

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

Энтропия равна 0, если результат очевиден, и максимальному, если любой исход равновероятен.

Получение информации

Ожидаемое снижение энтропии из-за разделения S по атрибуту A

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

Здесь

  1. Атрибут, по которому происходит расщепление.
  2. Значения (A) - это разные значения, принимаемые атрибутом A
  3. Зв / S - это доля данных с атрибутом A = v.

Мы предпочтем атрибуты, по которым получение информации больше по сравнению с другими.

Пример

Энтропия для значений 29+ и 35 составляет 0,99. И, подставив значения в уравнение для получения информации, мы получим усиление (S, A1) = 0,27 и усиление (S, A2) = 0,12.

Поскольку усиление для атрибута A1 больше, чем A2, мы предпочитаем A1 для разделения, чем A2.

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

Индекс GINI - еще одна мера примеси узлов, определяемая как

Здесь p (c) - вероятность классов в данных.

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

Непрерывный атрибут - двоичное разделение

Для непрерывного атрибута

  1. Разделите непрерывное значение атрибута A на дискретный набор интервалов.
  2. Создайте новый логический атрибут Ac, ища порог c,

рассмотреть все возможные расколы и найти лучший срез.

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

Практические вопросы классификации

  1. Недооснащение и переоборудование.
  2. Недостающие значения
  3. Стоимость классификации

Переоснащение

Говорят, что гипотеза h превосходит обучающие данные, если существует другая гипотеза h ’такая, что h’ имеет больше ошибок на обучающих данных, чем h, но h ’имеет меньше ошибок на тестовых данных, чем h. Или мы говорим, что когда гипотеза h начинает соответствовать шуму в обучающих данных, мы говорим, что она начала переоценивать данные.

Как избежать переобучения в дереве решений

  1. Предварительная обрезка. Прекращение роста дерева, если разбиение данных не является статистически значимым. Или, другими словами, мы прекращаем деление, когда усиление не является существенно положительным (или статистически значимым).
  2. Последующая обрезка: вырастите полное дерево, затем удалите узлы. Для этого нам понадобится набор валидации для оценки ошибки дерева решений. В этом случае мы сначала выращиваем полное дерево (T) и берем поддерево (T1) на полном дереве. Теперь для использования набора проверки мы оцениваем ошибку (T) и ошибку (T-T1). Если error (T-T1) меньше, чем error (T), то поддерево T1 является нашим кандидатом на удаление. Точно так же у нас может быть много поддеревов в данном дереве, и нам нужно оценить то же самое для них, чтобы удалить поддерево.

Уменьшение количества ошибок при сокращении

Это один из алгоритмов обрезки постов.

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

Этот метод использует меньше данных для выращивания дерева, что является одним из недостатков метода.

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

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