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

В дальнейшем я подведу итоги четырех лет моего университета.Хоть он и не идеален, я очень старался делать все, что хотел.

Алгоритмическое мышление

Дерево решений — это не просто бинарное дерево, оно также может иметь несколько ответвлений.

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

? Древовидная структура

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

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

Если-то правило:

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

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

1. Понятие энтропии

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

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

H(p)=-Σ_{i=1}^{n}p_ilog{p_i}

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

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

входить: обучающий набор данных D и функция A.

вывод: прирост информации g(D, A) функции A к набору обучающих данных D.

?‍♂️Три шага~

Шаг 1. Рассчитайте эмпирическую энтропию H(D) набора данных D.

H(D)=-Σ_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}

Шаг 2. Рассчитайте эмпирическую условную энтропию H(D|A) объекта A для набора данных D.

Шаг 3 Рассчитайте формулу получения информации

g(D,A)=H(D)-H(D|A)

Прирост информации представляет собой степень, в которой неопределенность информации класса Y уменьшается благодаря знанию признака А.

Есть много формул, головокружение? ? Будет понятно после прочтения примеров вопросов~

3. Объяснение примеров

Вход: обучающий набор данных D

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

Шаг 1 Рассчитайте эмпирическую формулу энтропии

В этом наборе обучающих данных, D = 15, есть две окончательные классификации: да (9), нет (6)

Подставьте в расчет, чтобы получить эмпирическую энтропию:

Шаг 2 Рассчитайте эмпирическую формулу условной энтропии

Пусть А₁: возраст, А₂: Есть ли работа, А₃: У тебя есть свой дом, А₄: Кредитная ситуация

① Возраст

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

Когда i=1 молодежь:

Когда i=2 средний возраст:

При i=3 старости:

Окончательная эмпирическая условная энтропия:

Шаг 3 Рассчитайте формулу получения информации

Точно так же мы можем рассчитать информационный прирост других функций.

Продолжите расчет трех предыдущих шагов и сведите результаты в таблицу:

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

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

? Как уменьшить влияние принятия большего количества ценностей?

не волнуйся,коэффициент усиления информацииприходи~

коэффициент усиления информации

Энтропия обучающего набора данных D по отношению к признаку A:

H_A(D)=Σ_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}

Коэффициент усиления информации:

g_R(D,A)=\frac{g(D,A)}{H_A(D)}

как рассчитать $H_A(D)$ Шерстяная ткань?

показать $A_1=возраст$ Например:

Аналогично продолжаем вычислять A₂, А₃, А₄Коэффициент прироста информации, соответствующий признаку, указан в таблице:

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

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

Алгоритм генерации дерева решений

1. Алгоритм ID3

входить: обучающий набор данных $D$ , набор функций $A$ , порог $\varepsilon$

вывод: Древо решений $T$

шаг 1 решение $T$ Вам нужно выбрать функции для создания дерева решений?

Case 1как $D$ Все экземпляры принадлежат одному и тому же классу, тогда T — количество отдельных узлов, запишите класс экземпляра. $C_k$ , который используется как маркер класса узла и возвращает $T$

Case 2как $D$ Все экземпляры в не имеют функций ( $A=\emptyset$ ),но $T$ Для дерева с одним узлом запишите $D$ категория с наибольшим количеством экземпляров, и $C_k$ В соответствии с принципом мажоритарного голосования используйте это как метку класса узла и верните $T$ .

Шаг 2. В противном случае рассчитайте информационный прирост каждой функции в A и выберите функцию A с наибольшим информационным приростом._g

Case 1как $A_g$ Прирост информации меньше, чем $\varepsilon$ ,но $T$ Для дерева с одним узлом запишите $D$ Категория с наибольшим количеством экземпляров $C_k$ ,

Case 2В противном случае следуйте $A_g$ все возможные значения $a_i$ ,будет $D$ Разделить на несколько непустых подмножеств $D_i$ ,будет $D_i$ В качестве маркера используется категория с наибольшим количеством экземпляров, и строится дочерний узел, состоящий из узла и его дочерних узлов. $T$ , и вернуться $T$

шаг 3 $i$ дочерние узлы, с $D_i$ это тренировочный набор, $A-A_g$ Для набора функций рекурсивно вызовите вышеуказанные шаги, чтобы получить поддерево $T_i$

У меня кружится голова ? Гораздо проще посмотреть на вопросы-примеры~

Пример объяснения

Еще последний пример

Вход: обучающий набор данных D

Выход: дерево решений $T$ .

шаг 1 решение $T$ Вам нужно выбрать функции для создания дерева решений?

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

∴ $T$ Необходимо выбрать функции для создания дерева решений

Шаг 2. Рассчитайте информационный прирост каждой функции в A и выберите функцию A с наибольшим информационным приростом._g

можно дать искусственно $\varepsilon=0.001$ , и из значений прироста информации, полученных выше, видно, что все больше, чем $\varepsilon$ , поэтому нет оснований говорить, что это дерево с одним узлом

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

Следовательно, мы можем определить, что корневой узел имеет наибольший прирост информации.у тебя есть собственный дом?По этому признаку обучающую выборку можно разделить на $D_1$ и $D_2$

特征A<sub>3</sub>=是否自己的房子的统计表格 Видно, что у него есть свой дом $D_1$ Все соглашаются на кредит, поэтому в это время можно получить один листовой узел. без собственного дома $D_2$ Существуют как согласованные кредиты, так и несогласованные кредиты, поэтому необходимо найти признаки, соответствующие внутренним узлам в соответствии с выбором признаков (рассчитать максимальный информационный прирост по этим трем признакам).

Во-первых, по возрастному признаку:

Из вышеприведенной таблицы видно, есть ли обучающий набор собственного дома, есть 9 экземпляров без собственного дома, 6 из них согласны на кредит, 3 не согласны на кредит, тогдаэмпирическая энтропияза

$i=1$ Молодость:

$i=2$ В среднем возрасте:

Видно, что для этого подмножества заем не согласован, тогда его эмпирическая условная энтропия равна 0

$i=3$ В старости:

Окончательная эмпирическая условная энтропия $H(D_2|A_1)$ за:

возраст $A_1$ Информационная выгода это:

Таким же образом вычислить, есть ли работа $A_2$ , кредитная ситуация $A_4$ прирост информации, перечисленные в следующей таблице:

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

生成的决策树

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

Требование одного листового узла выполнено, поэтому генерация дерева решений завершена~?

2. Алгоритм С4.5

Если вы изучите алгоритм ID3, алгоритм C4.5 будет очень простым.

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

Код приведенного выше примера находится по адресу ?git ee.com/new-month-pro…

Добро пожаловать в гигантский указатель~

Использованная литература:Доктор Джейн - Генерация дерева решений