Деревья решений - один из самых известных алгоритмов в области машинного обучения. Есть много методов, основанных на дереве решений, таких как XgBoost, Random Forest, Hoeffding tree и многие другие. Дерево решений представляет функцию T: X- ›Y, где X - это набор характеристик, а Y может быть непрерывным значением или классом. Давайте разберемся здесь: мы можем поставить любую функцию в качестве условия для любого узла при выращивании нашего дерева, и, в конечном итоге, мы сделаем тройник, который может классифицировать данные (это не будет оптимальным и обобщенным, но он обязательно классифицирует приведенные данные с очень высокой точностью). Итак, вот большой вопрос: как выбрать, какую функцию использовать в первую очередь для создания родительского узла, а какие - для создания дочернего узла. Нам также необходимо знать условие, которое следует поставить для классификации данных. Прежде чем мы перейдем к более подробному рассмотрению деревьев решений, мы должны спросить себя, почему это дерево решений, когда у нас есть множество других алгоритмов. Деревья решений очень эффективны и могут моделировать очень сложные сценарии. Они быстро дают результаты и, что самое важное, они считаются наиболее интерпретируемым алгоритмом в ИИ. Результаты дерева решений легко понять даже неспециалисту. Итак, без лишних слов, давайте углубимся в теорию, лежащую в основе дерева решений.
Давайте определим дерево решений на более формальном языке. Найдите дерево T такое, что для (x, f (x)), взятого из D (распределение), в среднем, T (x) аналогичен f (x) . Риск R дерева T относительно f - это ожидаемое значение потерь (T (x), f (x)) с x, взятым из D. На практике мы обычно не знаем D,, поэтому мы не можем вычислить риск tree T, не говоря уже о том, чтобы найти дерево с минимальным риском. Поэтому практические алгоритмы изучения деревьев решений будут использовать эвристику для поиска дерева , которое является небольшим и в то же время хорошо обобщается. Давайте разберемся с помощью нескольких изображений, чего мы здесь пытаемся достичь. Ниже приводится набор данных, который говорит нам о том, от какого напитка нас тошнит.
Все напитки, которые продаются в цилиндрических стаканах или, если они находятся в стакане другой формы, должны быть не оранжевого цвета, чтобы быть безопасными. Приведенная выше диаграмма показывает нам, как мы можем отделить плохие напитки от хороших, но мы сделали это визуально, как тогда сделать это математически? Нам нужно решить, какая функция должна быть помещена в какой узел, для выполнения этой задачи мы используем то, что называется приростом информации или индексом Джини (мера примеси). Первое, что приходит в голову, когда вы слышите энтропию, - это хаос, и это именно то, что вам нужно. Нам нужно построить дерево таким образом, чтобы оно уменьшало энтропию системы или увеличивало получение информации при создании каждого дочернего узла. Ниже приведено уравнение энтропии (блог - это журнал с основанием 2 или двоичный журнал). Чтобы быть точным, энтропия называется энтропией класса (для DT), и, используя ее, мы вычисляем прирост информации. Прирост информации - это ожидаемое снижение энтропии, если мы добавим определенную функцию в качестве условия в данном узле на определенной глубине. Давайте разберемся в этом на примере. Но прежде чем мы пойдем дальше, давайте разберемся с еще одним термином, называемым индексом Джини.
Индекс Джини является показателем неравенства в выборке. В практических целях мы используем индекс Джини, а не сбор информации. Он имеет значение от 0 до 0,5. Индекс Джини со значением 0 означает, что выборки идеально однородны и все элементы похожи, тогда как индекс Джини со значением 0,5 означает максимальное неравенство между элементами. Это сумма квадрата вероятностей каждого класса.
Давайте попробуем понять дерево решений с помощью нашего набора данных игрушек 2, который показан в приведенной выше таблице. Этот набор данных говорит нам, когда мы можем пойти на замечательный теннисный матч, а когда нет. У нас есть 5 функций, а именно прогноз (солнечно, пасмурно, осадки), температура (жарко, умеренно, холодно) , влажность ( высокая, нормальная) и ветер (слабый, сильный), нам нужно выбрать один функция из этих 4 функций, которая будет нашим первым корневым узлом. Эта функция приведет к максимальному снижению энтропии. Сначала мы увидим внешний вид функции и рассчитаем индекс Джини для его категориального значения (солнечно, пасмурно, дожди и пасмурно).
Из 5 солнечных в приведенной выше таблице у нас есть 3 «Да» и 2 «Нет». Итак, наш индекс Джини рассчитывается следующим образом:
Индекс Джини (прогноз = солнечный) = 1- (2/5) ²- (3/5) ² = 1- 0,16–0,36 = 0,48
Аналогично, мы рассчитываем индекс Джини для остальных 3 категорий перспективного прогноза.
Индекс Джини (прогноз = облачность) = 1- (4/4) ²- (0/4) ² = 1–1–0 = 0
Индекс Джини (прогноз = количество осадков) = 1- (3/5) ² - (2/5) ² = 1–0,36–0,16 = 0,48
После расчета индекса Джини для каждой категории в данной функции мы вычисляем взвешенную сумму индекса Джини для перспективы функции. Здесь 5/14 доли солнечного света, 4/14 доли облачности и 5/14 осадков, ниже приведено расчетное значение взвешенного индекса Джини:
Джини (прогноз) = (5/14) * 0,48 + (4/14) * 0 + (5/14) * 0,48 = 0,342
Мы следуем той же процедуре для температуры, влажности и ветра. Результаты для всех 4 функций показаны в таблице ниже. Из приведенной ниже таблицы видно, что индекс Джини для функции Outlook самый низкий. Итак, мы получаем внешний вид нашего корневого узла.
Мы повторяем ту же процедуру, но на этот раз мы смотрим на субданные о солнечном свете, пасмурности и осадках. Сначала мы вычисляем результаты из приведенной выше таблицы при солнечной температуре, затем при пасмурной погоде, а затем при осадке. Делая это для солнечного света, мы получаем, что влажность дает нам самый низкий индекс Джини, поэтому мы выбираем влажность, чтобы разделить наш узел. мы продолжаем делать этот процесс до тех пор, пока точность проверки не увеличится или все наши функции не будут исчерпаны.
После определенной глубины точность дерева решений начинает снижаться. Мы должны быть осторожны, чтобы не зарастать наши деревья, так как они могут легко переобучиться после определенной глубины, что показано на приведенном выше графике. Вот еще вопрос, когда нам перестать выращивать дерево?
У нас есть два варианта: осторожное разделение и пост-обрезка. Осторожное разделение заключается в том, что мы пытаемся угадать точность невидимых данных, это в основном точность данных проверки. Пост-обрезка - это обучение всего дерева с последующим удалением узлов, которые имеют очень мало элементов в своих конечных узлах или если обрезка этого узла не приводит к значительному изменению точности. Отказ от обрезки - обычно очень плохая идея (в большинстве современных реализаций алгоритмов DT уже есть встроенная обрезка)
Вот полный псевдокод для нисходящего дерева решений индукции. Создайте тест, а затем выберите лучший тест (из всех мер примесей выберите тот, который дает лучший результат). Разделите данные на основе наилучшего теста и продолжайте увеличивать дерево, пока узел не станет чистым узлом (все элементы в узле принадлежат к одному классу). И, наконец, подрежьте дерево, чтобы избежать переобучения.
То, что мы показали выше, предназначалось только для категориальных данных, но этот метод работает даже с числовыми данными. Для числовых данных нам просто нужно ввести пороговый член для каждой функции. Мы вычисляем индекс Джини функции, сортируя эту функцию и затем применяя порог к каждому значению в этой функции, а затем выбирая функцию с самым низким индексом Джини в качестве кандидата на роль корневого узла. Как правило, дерево решений создает границу решения, параллельную оси, но мы можем подогнать наклонные линии также, изменив best_test в приведенном выше псевдокоде. На приведенных ниже изображениях показан результат как для параллельных, так и для наклонных деревьев.
И последнее, что касается деревьев решений, это то, что они всегда должны иметь строго вогнутую меру примесей. На диаграмме ниже показано, как рассчитывается усиление. Если мера примеси не вогнутая (см. Треугольный случай), то даже для разных пропорций положительного и отрицательного образца усиление все равно останется нулевым. Мы получим выигрыш только тогда, когда один из дочерних узлов имеет класс, отличный от класса его родительского узла, в случае невыпуклой функции примесей. (Прочтите текст, написанный на изображении ниже, чтобы понять концепцию строго выпуклой функции примесей)
Я надеюсь, что теперь вы знаете немного больше о дереве решений, если кто-то из вас хочет получить код дерева решений с нуля, прокомментируйте ниже. А также подскажите, что вы хотите узнать дальше.
СЧАСТЛИВОГО УЧЕНИЯ…
