предисловие

Я и раньше была занята выпускным оформлением и выпускным, блог давно не обновлялся, и теперь снова возьмусь за него.

На этот раз в этой статье представлен очень полезный алгоритм под названиемДрево решений(Древо решений). Его применение очень широкое, и некоторые основанные на нем методы, такие как случайный лес, GBDT и т. д., также широко используются в соревнованиях по науке о данных, таких как kaggle.

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

текст

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

Построение дерева решений

Так как же алгоритм дерева решений автоматически изучает структуру дерева решений на основе данных? Чтобы ответить на этот вопрос, нам сначала нужно понять некоторые точки знаний, связанные с теорией информации, и понять некоторые алгоритмы дерева решений (ID3, C4.5).

Информационная энтропия (Энтропия)

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

$H(X)=-\sum\limits_{x\in\mathcal{X}}p(x)\log p(x)$

В формуле X представляет собой случайную величину, такую как $X\in\{肥宅,不是肥宅\}$ ,и p(x) представляет функцию массы вероятности.

так или иначеЧем выше энтропия, тем хаотичнее все множество.. Понятие и понимание информационной энтропии здесь подробно объясняться не будет.Вам нужно только понять, что означает размер информационной энтропии.Если вас это интересует, вы можете обратиться к нему.Что такое информационная энтропия? - Ответ Д. Хана - Зная.

Большая информационная энтропия (слева) и малая информационная энтропия (справа)

Выберите, какой атрибут разделить

В дереве решений нам нужно автоматически разделить набор по атрибутам.Конечная цель — классифицировать все данные, так как же нам выбрать, какой атрибут использовать сейчас?

Прирост информации

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

Мы будем использовать прирост информации для определения порядка разделения атрибутов.

Если разделить на «еженедельную частоту фитнеса», прирост информации составит:

$entropy_{pat} = -\frac{15}{27}\cdot log_{2}\frac{15}{27}-\frac{12}{27}\cdot log_{2}\frac{12}{27} = -0.471-0.520 = 0.991$ $entropy_{avgchild} = (\frac{10}{27}\cdot0.469) + (\frac{8}{27}\cdot0.954) + (\frac{9}{27}\cdot0) = 0.456$

Принимая «люблю пить толстяка счастливую воду» в качестве разделения, информационный прирост составляет: $entropy_{pat} = -\frac{15}{27}\cdot log_{2}\frac{15}{27}-\frac{12}{27}\cdot log_{2}\frac{12}{27} = -0.471-0.520 = 0.991$ $entropy_{avgchild} = (\frac{16}{27}\cdot0.811) + (\frac{11}{27}\cdot0.845) = 0.481 + 0.344 = 0.825$

Поскольку прирост информации составляет 0,535 > 0,166, более эффективно выбрать разделение по частоте пригодности, чем выбрать Happy Water, как Fat Boy.

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

Обрезка деревьев решений

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

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

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

Когда использовать деревья решений

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

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

постскриптум

использованная литература

Введение в искусственный интеллект - Вашингтонский университет Машинное обучение — Чжоу Чжихуа