Серия алгоритмов машинного обучения

Линейная регрессия для машинного обучения
Логистическая регрессия и реализация машинного обучения на Python
Борьба с проектами машинного обучения Обнаружение аномалий данных транзакций
Дерево решений для машинного обучения
Реализация дерева решений машинного обучения (Decision Tree) на Python
PCA (анализ основных компонентов) для машинного обучения
разработка функций машинного обучения

На этот раз давайте взглянем на алгоритм дерева решений.

Древо решений

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

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

Как правило, дерево решений содержит корневой узел, несколько внутренних узлов (нелистовых узлов) и несколько конечных узлов.

Корневой узел: первая точка выбора
Внутренние узлы (нелистовые узлы): промежуточный процесс принятия решений
Листовой узел: окончательный результат решения

Процесс обучения дерева решений

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

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

Для конкретного процесса алгоритма, вот изображение из «Машинного обучения» Чжоу Чжихуа, вы можете посмотреть

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

Выбор раздела дерева решений

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

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

Информационная энтропия представляет собой меру неопределенности случайных величин: чем больше энтропия, тем сильнее неопределенность, т. е. ниже чистота;
Чем меньше энтропия, тем слабее неопределенность и выше чистота

Установите набор образцов D, чтобы иметь в общей сложностиобразцов класса, где впервыеДоля образцов класса p_k(k=1,2,...,K) ,ноИнформационная энтропия определяется как:

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

На приведенном выше изображении ось X представляет вероятность положительного образца, а ось Y представляет соответствующую информационную энтропию. Можно видеть, что при вероятности 0,5 соответствующая информационная энтропия наибольшая, то есть неопределенность наибольшая в это время, а когда вероятность больше 0,5 или меньше 0,5, информационная энтропия уменьшится.

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

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

Мы предполагаем, что в наборе признаков есть дискретный признак,она имеетвозможные значения $\{a^1,a^2,...,a^V\}$ ,
Если вы используете функцию a для анализа выборкиразделить, то будетузлы ответвления, гдеНабор образцов, содержащихся в каждом узле ветви. мы записываем как D^v .
Таким образом, прирост информации, полученный путем деления выборки D на признак a, можно рассчитать как:

Gain(D,a) = Ent(D) - {\sum_{v=1}^V}\frac{|D^v|}{|D|}Ent(D^v)

Объясняя вышеприведенную формулу, по сути, прирост информации, полученный при разделении выборки D по признаку a, равен информационной энтропии выборки D за вычетом суммы информационной энтропии каждой ветви после деления. Поскольку каждый узел ветви содержит разное количество выборок, соответствующий вес необходимо умножать при расчете информационной энтропии каждой ветви. $\frac{|D^v|}{|D|}$ , то есть узел ответвления с большим количеством выборок оказывает большее влияние

Далее давайте подробно рассмотрим каштан

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

Очевидно, что наш образец общего класса K = 2 , , среди них доля положительных случаев $p_1 = \frac{9}{14}$ , отрицательная пропорция $p_1 = \frac{5}{14}$ Во-первых, давайте посмотрим, что информационная энтропия, соответствующая выборочному набору D, содержащемуся в корневом узле, равна:

Ent(D) = -\frac{9}{14}log_2\frac{9}{14} - \frac{5}{14}log_2\frac{5}{14} = 0.940

Затем нам нужно рассчитать прирост информации для каждого признака в текущем наборе признаков (погода, температура, влажность, уровень ветра).
Взяв в качестве примера характеристику погоды, если погода разделена, набор данных D можно разделить на три подмножества, обозначенные как: D^1(outlook= sunny),D^2(outlook = overcast)，D^3(outlook = rainy) ,

После деления значения энтропии трех узлов ветвления составляют:

\begin{align*} &Ent(D1) = -\frac{3}{5}log_2\frac{3}{5} - \frac{2}{5}log_2\frac{2}{5} = 0.971\\ &Ent(D2) = 0 \\ &Ent(D3) = -\frac{2}{5}log_2\frac{2}{5} - \frac{3}{5}log_2\frac{3}{5} = 0.971\\ \end{align*}

Затем мы можем рассчитать, что прирост информации, соответствующий прогнозу функции (погоде), составляет:

\begin{align*} Gain(D,outlook) &= Ent(D) - \sum_{v=1}^3 \frac{|D^v|}{|D|}Ent(D^v) \\ &= 0.940 - (\frac{5}{14}*0.971+\frac{4}{14}*0+\frac{5}{14}*0.971) \\ &= 0.247 \end{align*}

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

На самом деле это алгоритм ID3, который использует прирост информации в качестве критерия для разделения признаков.

Скорость получения информации

Давайте подумаем, в чем недостаток использования прироста информации в качестве критерия разделения атрибутов?

Предположим, для приведенного выше набора данных мы добавляем столбец функций, данные (дата), для приведенных выше 14 выборочных данных соответствующее значение равно (1,2,3,4,5,6,7,8,9,10,11,12,13,14) , по приведенной выше формуле можно рассчитать, что прирост информации, соответствующий данным (дате), составляет: Gain(D,data) = 0.940 ,
Мы обнаружили, что прирост информации, соответствующий ему, намного больше, чем другим признакам, поэтому хотим ли мы использовать признак данных в качестве основы для разделения первого узла? Таким образом, будет сгенерировано 14 ветвей, и каждая ветвь содержит только один образец.Можно видеть, что чистота каждого узла ветвления достигла максимума, то есть результат каждого узла ветвления очень определен. Однако такое дерево решений определенно не то, что нам нужно, потому что оно вообще не обладает какой-либо способностью к обобщению.

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

Также предположим, что имеется набор данных D и объект a, который имеетвозможные значения $\{a^1,a^2,...,a^V\}$ ,

Если набор данныхв характеристикеПри использовании в качестве разделительного признака коэффициент усиления определяется как:

Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}

IV(a) = - \sum_{v=1}^V \frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

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

IV(a) = - \sum_{v=1}^3 \frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} = -\frac{5}{14}log_2\frac{5}{14}-\frac{4}{14}log_2\frac{4}{14} - \frac{5}{14}log_2\frac{5}{14} = ...

Чем больше соответствующих типов признака а, т.е.больше, то IV(a) Значение обычно больше, и, следовательно, скорость усиления меньше. Таким образом, можно избежать недостатка предпочтения относительно большого количества признаков при получении информации.

Есть ли какие-либо недостатки в прямом использовании скорости получения информации в качестве критерия деления? На самом деле они есть. Критерий скорости увеличения обычно предпочитает меньшее количество атрибутов.
Поэтому подход в C4.5 состоит в том, чтобы сначала найти некоторые признаки, прирост информации которых выше, чем среднее значение из всех текущих признаков, а затем выбрать признак с самым высоким коэффициентом усиления в качестве оптимального признака деления.

Индекс Джини

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

Gini(D) = \sum_{k=1}^{K}p_k(1-p_k) = 1-\sum_{k-1}^{K}p_k^2

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

Непрерывная обработка признаков

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

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

будетЗначения сортируются от меньшего к большему, записываются как $A{a^1,a^2,...a^n}$
на основе точки разделения,будетразделить на две части, из которых не болееЧасть соответствующего набора данных $D_t^{-}$ , больше, чемЧасть соответствующего набора данных $D_t^{+}$
Мы знаем, что для ${a^1,a^2,...a^n}$ Разделив, мы имеемМетод деления, помимо значения соседних атрибутови $a^{i+1}$ за
в интервале $[a^i,a^{i+1})$ Принятие любого значения в t дает тот же результат деления, в свою очередь, набор значений для t:

T_a = \{ \frac{a^i+a^{i+1}}{2} \,\,, 1<=i<=n-1 \}

Затем для каждой точки разделения мы вычисляем прирост информации и выбираем точку разделения, соответствующую наибольшему приросту информации, в качестве точки разделения непрерывного признака a. Формула:
$\begin{align*} Gain(D,a) &= \max_{t\in{T_a}} Gain(D,a,t) \\ &=\max_{t\in{T_a}} \{ Ent(D) - (\frac{|D_t^{-}|}{|D|}Ent(D_t^{-}) + \frac{|D_t^{+}|}{|D|}Ent(D_t^{+})) \} \end{align*}$

Операция обрезки дерева решений

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

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

Предварительная обрезка

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

Итак, каковы конкретные показатели?

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

Поскольку предварительная обрезка выполняется одновременно с построением дерева решений, затраты времени на обучение меньше, и риск переобучения может быть эффективно снижен.
Однако существует проблема с предварительным сокращением, что приведет к риску недостаточного соответствия дереву решений.Показатели 1, 2, 3 и 4 не нуждаются в слишком подробном объяснении.Для 5 показателей,
Хотя текущее деление не может привести к повышению производительности, возможно, последующие деления, основанные на этом, могут значительно улучшить производительность?

после обрезки

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

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

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

Вышеизложенное является основным принципом алгоритма дерева решений.В следующей статье мы реализуем алгоритм дерева решений через python.

Добро пожаловать, чтобы обратить внимание на мою личную общедоступную учетную запись AI Computer Vision Workshop. Эта общедоступная учетная запись будет время от времени публиковать статьи о машинном обучении, глубоком обучении, компьютерном зрении и другие связанные статьи. Приглашаю всех учиться и общаться со мной.