Автор: Юань Минкай | Инженер по тестированию и развитию Tencent IEG
Основные концепции деревьев решений
Дерево решений — это способ использования древовидной структуры для исследования поведения, анализа решений и машинного обучения, а также базовый метод классификации в машинном обучении. Дерево решений (Дерево решений) основано на известной вероятности возникновения различных ситуаций, путем формирования дерева решений для получения вероятности того, что ожидаемое значение чистой приведенной стоимости больше или равно нулю, оценки риска проекта и судить о его осуществимости.Графический метод, интуитивно использующий вероятностный анализ. Поскольку эта ветвь решений изображается в виде графа, подобного ветвям дерева, она называется деревом решений. Деревья решений используются для моделирования процесса от условий к решениям. Посмотрите пример графика:
Пример показывает, подходит ли игра в зависимости от погодных условий: солнечно, дождливо, облачно, ветрено и влажность. Как видно из рисунка, дерево решений представляет собой древовидную структуру, в которой каждый внутренний узел представляет тест атрибута, каждая ветвь представляет результат теста, а каждый конечный узел представляет категорию. После построения дерева решений по информации можно определить результат решения для данной ситуации по дереву решений. Алгоритм дерева решений - это разновидность обучения с учителем.Так называемое обучение с учителем заключается в том, что при наличии набора образцов каждый образец имеет набор атрибутов и категорию, эти категории определяются заранее, а классификатор получается путем обучения , а классификатор может Объекту присваивается правильная классификация. Такое машинное обучение называется обучением с учителем.
В машинном обучении дерево решений — это прогностическая модель, представляющая сопоставление между атрибутами объекта и значениями объекта. Каждый узел в дереве представляет объект, и каждый путь бифуркации представляет возможное значение атрибута, и каждый конечный узел соответствует объекту, представленному путем от корневого узла к конечному узлу. Можно видеть, что наиболее критической точкой дерева решений является выбор приоритета условий принятия решений каждого узла ветви решения, чтобы лучше гарантировать, что более критические условия принятия решений находятся на верхнем уровне дерева. то в методе отбора, если сплит Точки (признаки) могут разделить все текущие узлы на две категории, так что каждая категория будет очень "чистой", то есть точность каждой категории очень высока, то есть большинство из них относятся к одному и тому же целевому результату, то это хорошая точка сегментации. Существует два алгоритма количественной оценки «чистоты» этой сегментации: Примесь Джини (Gini Impurity) примесь) и энтропия.
Джини примеси
Примесь Джини относится к ожидаемой частоте ошибок элемента данных, когда результат из набора случайным образом применяется к набору, что является мерой степени смешения, предсказанной деревьями решений.
количество информации
Энтропия может относиться к трудности описания вещи, например, с какой стороны восходит солнце, мне нужно сказать только на востоке; и какая команда выиграет чемпионат мира, мне нужно сказать, может быть, Бразилия, может быть, Германия, может быть, это Испания, может быть...; на следующих трех картинках C легче всего описать и содержит наименьшее количество информации, а A сложнее всего описать и содержит больше всего информации. Другими словами, чем «чистее» вещь, тем она менее информативна.
Как измерить количество информации? На самом деле, это описание того, сколько битов памяти нужно использовать для этой вещи. Независимо от того, является ли результат подбрасывания монеты орлом или решкой, требуется сохранить 0 или 1, а количество информации составляет 1 бит. Кто выиграет чемпионат мира 32 командам нужно максимум 5-битное хранилище. Очевидно, что количество информации – это все возможности события.
логарифм по основанию 2
. Следовательно, чем больше неопределенность части информации, тем больше места необходимо для ее хранения и тем больший объем информации она имеет. События с вероятностью 0 или 1 очень детерминированы, и их информация равна 0. Однако не все исходы событий имеют такую же вероятность возникновения, как подбрасывание монеты. Например, на самом деле 32 команды на чемпионате мира имеют разную вероятность победы в чемпионате, как в этом случае рассчитать количество информации? Вывод из предыдущей формулы:
,ПредполагатьPдля мероприятияNВероятность каждого исхода в , когда каждый исход имеет одинаковую вероятность, формула выглядит следующим образом.
И если вероятности разные, помните
за каждый результатx1вероятности, то формула принимает вид:Формула энтропии Шеннона:
,Энтропия Шеннона таким образом количественно определяет и вычисляет размер информации.Построение дерева решений состоит в выборе признака.После разделения данных, чем меньше количество информации, тем легче ее описать, и тем более "чисто", тем лучше, так что это тоже так.Чем меньше значение после расчета формулы, тем лучше. Давайте возьмем случай погоды для расчета энтропии Шеннона, Если это исходный объем информации и условия не увеличиваются,
,Если добавить разделение по погодным условиям, то будет:
В солнечный день вы воспроизвели объем данных информации:
В дождливые дни, стоит ли играть с объемом данных:
Облачно, стоит ли играть с объемом данных информации:
Затем ожидается, что количество информации будет добавлено, чтобы получить сумму разделенной информации:
путем сравнения установлено, что количество информации после сегментации погоды наименьшее, и оно меньше, чем исходное количество информации, поэтому эта сегментация является наилучшей. Аналогичным образом информативность остальных признаков рассчитывается вниз по соответствующим узлам до тех пор, пока информативность не станет равной 0 или перестанет уменьшаться.
переоснащение
л Синяя линия-распределение Джини, а красная линия-распределение энтропии.Было проверено, что алгоритм дерева решений может быть разветвлен более точно; эффективность энтропии немного медленнее, чем у Джини, из-за операции журнала;
l Оба могут быть оценены только в целом на основе определенного признака (например, хукоу), но не могут быть специфичными для конкретной категории в рамках признака.Например, облачная погода подходит для выхода на улицу и имеет высокую степень дискриминации, но не может быть использован этими двумя Это может быть достигнуто только путем модификации алгоритма и оценки разницы в эффекте.
l Как упоминалось в предыдущей статье, если облачная погода в образце на 100% подходит для игры, если в один прекрасный день облачная погода слишком ветреная, чтобы выйти на улицу, решение будет отклонено. Поэтому легко попасть в проблему переобучения при построении дерева решений.Если определенные ограничения не установлены, набор обучающих данных может достигать 100% точности, например, генерировать конечный узел для каждых данных.
Случаи, такие как использование размера для различения апельсинов и грейпфрутов, апельсины в основном меньше, чем грейпфруты, поэтому теоретически можно обучить, что большинство апельсинов в меньшем диапазоне - это апельсины, а другой диапазон - грейпфруты, такой узел листа дерева решений . Но если нет ограничений, дерево решений, скорее всего, станет апельсинами 21 см3, апельсинами шириной 32 см3, грейпфрутами шириной 85 см3, оно на 100% точно для обучающего набора, но не для данных, отличных от обучающего набора Хорошее решение.
Как правило, есть два способа избежать переобучения: деревья решений с ограничениями и обрезка.
Ограниченное дерево решений
Существует множество методов дерева решений с ограничениями, которые необходимо выбирать или комбинировать в зависимости от ситуации или потребностей:
1. Установите минимальное количество выборок для каждого конечного узла, что позволит избежать того, что определенная категория признаков подходит только для очень небольшого количества выборок;
2. Установите минимальное количество выборок на узел, как указано выше, но оно начинается с корневого узла, чтобы избежать переобучения;
3. Установите максимальную глубину дерева, чтобы избежать бесконечного деления вниз;
4. Установите максимальное количество конечных узлов, чтобы избежать бесконечных категорий деления;
5. Установите максимальное количество функций при оценке данных сегментации, избегайте каждый раз рассматривать все функции как «лучшие» и используйте метод случайного выбора, чтобы избежать переобучения;
Насколько подходят приведенные выше данные?Необходимо использовать реальный тестовый набор для проверки точности принятия решений при различных ограничениях.
обрезка
Сокращение заключается в том, чтобы сначала построить дерево решений, а затем настроить его.Общая идея состоит в том, чтобы сократить каждый узел или его поддерево и использовать некоторые алгоритмы для оценки того, уменьшилась ли прогностическая способность модели дерева решений до и после сокращения.Описание может быть обрезанный.
Несколько часто используемых методов оценки обрезки:
l Сокращение числа ошибок (REP)
а) пройти узлы, используя некоторый порядок
б) удалить поддерево с корнем в этом узле
в) Сделать этот узел листовым узлом
г) Назначить этому узлу класс с наибольшей вероятностью признака узла в обучающей выборке (то есть этот узел представляет этот класс)
e) Рассчитайте общий процент ложных срабатываний или коэффициент точности, если он лучше, чем до обрезки, то удалите его.
l Пессимистичное обширное обрезку (PEP)
а) Оцените, обрезан ли один узел (не поддерево)
б) Оцените, используя сумму ошибок всех листовых узлов под узлом
в) Когда частота ошибок до и после резки не превышает определенного стандартного значения, то резка
l Снижение сложности затрат (CCP)
а) Подробно описан в алгоритме CART
Преимущества и недостатки алгоритма дерева решений
Преимущества: простой и понятный; может обрабатывать как числовые, так и категориальные данные; для использования требуется лишь небольшое количество обучающих наборов; при использовании модели белого ящика каждый шаг можно четко наблюдать; более высокая производительность при обработке больших объемов данных ;Ближе к человеческому образу мышления, чем другие алгоритмы.
Недостатки: Точность не так хороша, как у других алгоритмов, трудно прогнозировать непрерывные поля, особенно данные в хронологическом порядке, что требует больше работы по предварительной обработке; устойчивость дерева недостаточна, небольшое изменение обучающей выборки может вызывают радикальные изменения во всем дереве, что приводит к изменениям в окончательном прогнозе; легко переобучить; когда дерево решений обрабатывает данные признаков, содержащие разные числовые категории, оно имеет тенденцию выбирать признаки с большим количеством значений в качестве узлов сегментации и данные с серьезным полем специализация, такая как анализ игровых пользователей.Имена пользователей более склонны к переобучению, и чем больше категорий, тем быстрее будет увеличиваться ошибка.
ID3- Iterative Dichotomiser 3
ID3, также известный как итеративная дихотомия третьего поколения, представляет собой базовый алгоритм построения деревьев решений. Алгоритм ID3 — это жадный алгоритм, используемый для построения дерева решений.Каждый шаг выбирает текущее оптимальное решение, а не общее видимое оптимальное решение. Алгоритм ID3 произошел от Системы обучения понятий (CLS) и использует скорость снижения информационной энтропии в качестве критерия для выбора тестовых атрибутов, то есть в каждом узле атрибут с наибольшим информационным приростом, который еще не использовался для в качестве критерия деления выбрано деление, а затем продолжать этот процесс до тех пор, пока результирующее дерево решений не сможет идеально классифицировать обучающие примеры. Алгоритм основан на теории информации и использует информационную энтропию и прирост информации в качестве стандартов измерения, чтобы реализовать индукцию и классификацию данных.
Информационная энтропия
Понятие количества информации было введено выше, а здесь оно объяснено с другой стороны. Энтропия — это понятие, полученное из физики, которое используется для измерения степени беспорядка в термодинамической системе.Чем более неупорядочена система, тем больше значение энтропии системы. В теории информации энтропия используется для измерения неопределенности событий, и чем выше неопределенность, тем больше информационная энтропия. Если результат события был определен до того, как событие произошло, например, оно должно произойти или не должно произойти, то информационная энтропия стремится к нулю. Шеннон дал математическую формулу для измерения информационной энтропии. Для случайной величины X ее диапазон значений равен {x1, x2, ..., xn}, а pi — функция плотности вероятности появления xi, тогда энтропия случайной величины X равна:
, из определения информационной энтропии, чем шире диапазон значений случайной величины X, тем равномернее распределение вероятностей, тем больше значение информационной энтропии, соответствующее случайной величине. До того, как событие произойдет, чем сложнее угадать результат, тем больше информационная энтропия, содержащаяся в событии. Еще возьмем данные о погоде в качестве примера:
Для столбца данных Play 9 дней из 14 подходят для игры, а 5 дней не подходят. игра следующая:
получение информации
Данные обычно содержат несколько значений характеристик, например, данные о погоде содержат данные о влажности, ветре, осадках и т. д. Если погода сначала классифицируется по определенному признаку, а затем вычисляется информационная энтропия других столбцов данных, то разница между информационной энтропией до классификации и информационной энтропией после классификации представляет собой прирост информации, полученный после классификации данных по к определенному столбцу атрибутов. Предполагая, что ее можно разделить на n категорий в соответствии с определенным атрибутом, каждая категория равна Ti, а |Ti| представляет количество. Метод расчета энтропии разделенной информации следующий:
, H(x) и H(p) имеют один и тот же смысл. Прирост информации рассчитывается следующим образом:
, или возьмем в качестве примера данные о погоде, рассчитаем, подходит ли прирост информации этого столбца данных для воспроизведения, деленный на температуру. Температура делится на три типа: жарко, мягко и прохладно.Данные о том, пора ли играть погоде, разделены на три части в зависимости от температуры:
Количество информации после деления равно:
Тогда прирост информации о том, подходят ли данные для воспроизведения в зависимости от температуры, составляет: 0,940–0,911 = 0,029 бит.
Ядро алгоритма ID3
Алгоритм ID3 — это жадный алгоритм, использующий концепцию получения информации. Шаги алгоритма следующие:
1) Рассчитайте прирост информации, вызванный каждым решением данных атрибута, в свою очередь, для всех данных, и выберите атрибут с наибольшим приростом информации в качестве корневого узла дерева решений.На самом деле, наоборот, атрибут с наименьшей информационной энтропией выбран в качестве корневого узла. .
2) Классифицировать атрибуты, выбранные на первом этапе данных, создать и вычислить информационный прирост оставшихся атрибутов для каждого классифицированного подмножества данных по очереди и выбрать атрибут с наибольшим информационным приростом в качестве конечного узла корневого узла.
3) Повторять шаг 2) до тех пор, пока все подмножества не будут содержать только один элемент или все атрибуты не станут узлами дерева решений.
Следует отметить, что алгоритм ID3 является жадным алгоритмом, и на каждом шаге в качестве узла выбирается атрибут, соответствующий максимальному приросту информации о текущем подмножестве. Результат окончательного дерева решений, построенного для этого примера погоды с использованием ID3, выглядит следующим образом:
У ID3 есть определенные требования к используемым выборочным данным. Во-первых, непрерывные данные не могут быть обработаны, и требуются дискретные данные, если непрерывные данные не разлагаются на данные нечеткой категории; во-вторых, требуется достаточный размер выборки, поскольку достаточно данных, чтобы различать каждую категорию признаков данных. имеет чрезмерную связанность, чтобы лучше устранить влияние данных в особых случаях, в-третьих, нецелесообразно использовать прирост информации в качестве стандарта разделения узлов, и он будет иметь тенденцию выбирать больше значений.
Алгоритмические недостатки ID3
1. Из метода расчета прироста информации прирост информации не может напрямую обрабатывать атрибутивные данные с непрерывными значениями, а может обрабатывать только дискретные данные.
2. Метод расчета прироста информации должен классифицировать столбец атрибутов.Если атрибутом является идентификатор, после классификации по идентификатору все классификации содержат только один элемент, то есть идентификатор является атрибутом с наибольшим приростом информации, что вызывает алгоритм ID3 не работает.
3. Если в данных прогноза есть ситуация, которая не появляется в обучающей выборке, ID3 никак не может с ней справиться. С целью устранения дефектов алгоритма ID3 впоследствии были изобретены C4.5, CART, random forest и другие алгоритмы.