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

 

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

 

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

Что такое дерево решений?

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

 

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

 

Давайте представим это на примере. Мы собрали данные о прошлых планах человека по плаванию, т. Е. О том, выходил ли человек из плавания или нет, основываясь на различных внешних условиях – или «входных характеристиках» – например, скорости ветра в узлах, максимальной температуре, прогнозе, а также на том, Лодка была в зимнем хранилище. Входные функции часто также называют нецелевыми атрибутами или независимыми переменными. Теперь мы хотим построить дерево решений, которое будет предсказывать результаты плавания (да или нет). Функция результата плавания также известна как целевая или зависимая переменная.

 

Если бы мы знали точные правила классификации, мы могли бы построить дерево решений вручную. Но это редко так. Обычно у нас есть данные: входные объекты с одной стороны и целевые объекты для прогнозирования с другой стороны. Ряд автоматических процедур может помочь нам извлечь правила из данных для построения такого дерева решений, как C4.5, ID3 или алгоритм CART (Дж. Росс Куинлан). Во всех из них цель состоит в том, чтобы обучить дерево решений для определения правил для прогнозирования целевой переменной, которая в нашем примере состоит в том, пойдем ли мы в новый день или нет.

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

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

 

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

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

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

 

Например, в дереве на рисунке 1 разделение в первом узле включает функцию «Хранилище» и разделяет входное подмножество на два подмножества: одно, где «Хранилище» – «да», и другое, где «Хранилище» – «нет». Если мы следуем путь к строкам данных, где Storage = yes, мы находим второе правило разделения. Здесь входной набор данных разделен на два набора данных: один, где «Ветер»> 6, и другой, где «Ветер» <= 6. Как алгоритм решает, какую функцию использовать в каждой точке для разделения входного подмножества?

 

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

Меры качества

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

 

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

Энтропия

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

 

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

080219 pic2 - От дерева решений к Random Forest

Где p – весь набор данных, N – количество классов, а i – частота класса i в том же наборе данных.

 

Чтобы лучше понять энтропию, давайте поработаем над двумя различными примерами наборов данных, оба с двумя классами, соответственно представленными в виде синих точек и красных крестиков (рис. 2). В примере набора данных слева у нас есть смесь синих точек и красных крестов. В примере набора данных справа у нас есть только красные кресты. Эта вторая ситуация – набор данных только с выборками из одного класса – это то, к чему мы стремимся: «чистое» подмножество данных.

Давайте теперь посчитаем энтропию для этих двух наборов двоичных данных.

 

Для примера слева вероятность составляет 7/13 для класса с красными крестиками и 6/13 для класса с синими точками. Обратите внимание, что здесь у нас почти столько же точек данных для одного класса, сколько для другого. Приведенная выше формула приводит к значению энтропии 0,99.

 

Для примера справа вероятность составляет 13/13 = 1,0 для класса с красными крестиками и 0/13 = 0,0 для класса с синими точками. Обратите внимание, что здесь у нас есть только красные точки пересечения. В этом случае приведенная выше формула приводит к значению энтропии 0,0.

 

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

 

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

Рисунок 3. Разделение в узле дерева должно переместиться из набора данных с более высокой энтропией в подмножества с более низкой общей энтропией.

Получение информации (ID3)

Чтобы оценить, насколько хорош признак для разделения, вычисляется разница в энтропии до и после разделения.

 

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

Где «до» – это набор данных до разделения, K – количество подмножеств, созданных разделением, и (j, после) – это подмножество j после разделения.

 

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

Коэффициент усиления (C4.5)

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

 

Коэффициент усиления затем рассчитывается путем деления информационного усиления алгоритма ID3 на значение SplitInfo.

080219 pic6 - От дерева решений к Random Forest

Где «до» – это набор данных до разделения, K – количество подмножеств, созданных разделением, и (j, после) – это подмножество j после разделения.

Индекс Джини (CART)

Другой показатель чистоты – или фактически примеси – используемый алгоритмом CART – это индекс Джини.

 

Индекс Джини основан на примесях Джини. Примесь Джини определяется как 1 минус сумма квадратов вероятностей классов в наборе данных.

080219 pic7 - От дерева решений к Random Forest

Где p – весь набор данных, N – количество классов, а i – частота класса i в том же наборе данных.

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

Для набора данных с двумя классами диапазон индекса Джини составляет от 0 до 0,5: 0, если набор данных чистый, и 0,5, если два класса распределены одинаково. Таким образом, функция с самым низким индексом Джини используется как следующая функция разделения.

080219 pic8 - От дерева решений к Random Forest

Где K – количество подмножеств, сгенерированных разделением, и (j, после) – подмножество j после разделения.

Выявление расколов

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

 

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

Размер и переоснащение

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

080219 pic9 1024x528 - От дерева решений к Random Forest

Рисунок 4. Размер дерева решений важен. Дерево, которое является большим и слишком подробным (справа), может соответствовать обучающим данным, в то время как слишком маленькое дерево (слева) может быть слишком простым для размещения данных.

 

Существует два способа избежать чрезмерно специализированного дерева: обрезка и / или ранняя остановка.

Обрезка

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

 

Есть много разных методов обрезки. Здесь мы хотим объяснить два наиболее часто используемых: сокращение сокращения ошибок и сокращение минимальной длины описания, MDL для краткости .

 

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

 

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

Ранняя остановка

Другой способ избежать переоснащения – это ранняя остановка, основанная на критерии остановки.

 

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

Случайный Лес Деревьев Решений

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

 

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

 

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

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

Начальная загрузка обучающих наборов

Давайте сосредоточимся на «немного по-другому».

 

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

 

Кроме того, входные объекты также могут отличаться от дерева к дереву как случайные подмножества исходного набора объектов. Как правило, если m – это число входных объектов в исходном наборе данных, для обучения каждого дерева решений используется подмножество случайно извлеченных [квадратный корень из m] входных объектов.

Рисунок 6. Деревья решений в случайном лесу все немного по-разному обучаются в подгруженном подмножестве исходного набора данных. Набор входных объектов также варьируется для каждого дерева решений в случайном лесу.

Правило большинства

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

 

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

Out of Bag (OOB) Ошибка

Популярной метрикой для измерения ошибки предсказания случайного леса является ошибка «вне пакета».

 

Ошибка «вне сумки» – это средняя ошибка прогнозирования, рассчитанная для всех обучающих выборок xᵢ, с использованием только деревьев, у которых не было xᵢ в их начальном обучающем наборе. Оценки ошибок из пакета позволяют избежать необходимости в независимом наборе данных проверки, но могут недооценивать фактическое улучшение производительности.

Выводы

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

 

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

 

Теперь давайте его использовать и посмотрим, будем ли мы плыть завтра!

Узнайте о других решениях

Инструменты анализа и визуализации данных

Решения аналитики данных

Напишите нам

и мы ответим в течении часа

support@asu-analitika.ru

Несколько видео о наших продуктах

085 - От дерева решений к Random Forest
Проиграть видео
Презентация аналитической платформы Tibco Spotfire
106 - От дерева решений к Random Forest
Проиграть видео
Отличительные особенности Tibco Spotfire 10X
1 11 - От дерева решений к Random Forest
Проиграть видео
Как аналитика данных помогает менеджерам компании
2020-07-03T21:52:16+02:00Август 10th, 2020|Рубрики: Data Mining|Метки: , , , , , , , , |
Social Media Auto Publish Powered By : XYZScripts.com