Изучение дерева решений - Decision tree learning

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

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

Общий

Дерево, показывающее выживаемость пассажиров на Титанике («sibsp» - это количество супругов или братьев и сестер на борту). Цифры под листьями показывают вероятность выживания и процент наблюдений в листе. Подводя итог: ваши шансы на выживание были хорошими, если вы были (i) женщиной или (ii) мужчиной моложе 9,5 лет и имели строго менее трех братьев и сестер.

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

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

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

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

Данные поступают в виде записей в форме:

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

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

Типы дерева решений

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

  • Классификационный древовидный анализ - это когда прогнозируемым результатом является класс (дискретный), к которому принадлежат данные.
  • Анализ дерева регрессии - это когда прогнозируемый результат можно рассматривать как действительное число (например, стоимость дома или продолжительность пребывания пациента в больнице).

Термин « анализ дерева классификации и регрессии» (CART) - это общий термин, используемый для обозначения любой из вышеупомянутых процедур, впервые введенный Breiman et al. в 1984 году. Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторое сходство, но также и некоторые различия, такие как процедура, используемая для определения места разделения.

Некоторые методы, часто называемые ансамблевыми методами, позволяют построить более одного дерева решений:

  • Усиленные деревья Постепенное построение ансамбля путем обучения каждого нового экземпляра, чтобы подчеркнуть ранее неправильно смоделированные обучающие экземпляры. Типичный пример - AdaBoost . Их можно использовать для задач регрессионного и классификационного типов.
  • Агрегированные (или упакованные) деревья решений начальной загрузки, метод раннего ансамбля, строят несколько деревьев решений путем многократной повторной выборки обучающих данных с заменой и голосования деревьев для согласованного прогноза.
  • Лес вращения - в котором каждое дерево решений обучается путем применения анализа главных компонентов (PCA) к случайному подмножеству входных функций.

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

Известные алгоритмы дерева решений включают:

  • ID3 (Итерационный дихотомайзер 3)
  • C4.5 (преемник ID3)
  • КОРЗИНА (дерево классификации и регрессии)
  • Автоматическое обнаружение взаимодействия по хи-квадрат (CHAID). Выполняет многоуровневое разбиение при вычислении деревьев классификации.
  • MARS : расширяет деревья решений для лучшей обработки числовых данных.
  • Деревья условного вывода. Подход, основанный на статистике, который использует непараметрические тесты в качестве критериев разделения, скорректированный для множественного тестирования, чтобы избежать переобучения. Этот подход приводит к беспристрастному выбору предикторов и не требует отсечения.

ID3 и CART были изобретены независимо примерно в одно и то же время (между 1970 и 1980 годами), но следуют аналогичному подходу к изучению дерева решений из обучающих кортежей.

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

Метрики

Алгоритмы построения деревьев решений обычно работают сверху вниз, выбирая на каждом шаге переменную, которая наилучшим образом разделяет набор элементов. Разные алгоритмы используют разные метрики для измерения «лучшего». Обычно они измеряют однородность целевой переменной в подмножествах. Ниже приведены некоторые примеры. Эти показатели применяются к каждому подмножеству кандидатов, а полученные значения объединяются (например, усредняются), чтобы обеспечить меру качества разделения.

Примесь Джини

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

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

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

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

Используется алгоритмами построения деревьев ID3 , C4.5 и C5.0. Получение информации основано на концепции энтропии и информационного содержания из теории информации .

Энтропия определяется следующим образом

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

Усредняя по возможным значениям ,

То есть ожидаемый информационный выигрыш - это взаимная информация, а это означает, что в среднем уменьшение энтропии T - это взаимная информация.

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

Рассмотрим пример набора данных с четырьмя атрибутами: прогноз (солнечно, пасмурно, дождливо), температура (жарко, умеренно, прохладно), влажность (высокая, нормальная) и ветреная (правда, ложь) с двоичным значением (да или нет). целевая переменная, игра и 14 точек данных. Чтобы построить дерево решений на основе этих данных, нам нужно сравнить информационный прирост каждого из четырех деревьев, каждое из которых разделено на одну из четырех характеристик. Разделение с наибольшим приростом информации будет принято как первое разбиение, и процесс будет продолжаться до тех пор, пока все дочерние узлы не будут иметь согласованные данные, или пока прирост информации не станет 0.

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

Разделение с использованием функции windy приводит к появлению двух дочерних узлов, один для значения windy, равного true, и один, для значения windy, равного false. В этом наборе данных есть шесть точек данных с истинным значением ветра , три из которых имеют значение play (где play - целевая переменная) да, а три - значение воспроизведения no. Восемь оставшихся точек данных с ветреным значением false содержат два «нет» и шесть «да». Информация об узле ветреный = истинный рассчитывается с использованием приведенного выше уравнения энтропии. Поскольку в этом узле равное количество «да» и «нет», мы имеем

Для узла, где windy = false, было восемь точек данных, шесть «да» и два «нет». Таким образом, мы имеем

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

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

Чтобы построить дерево, необходимо рассчитать информационный прирост каждого возможного первого разбиения. Лучшее первое разделение - это такое, которое обеспечивает наибольшее количество информации. Этот процесс повторяется для каждого нечистого узла, пока дерево не будет завершено. Этот пример адаптирован из примера, приведенного в Witten et al.

Снижение дисперсии

Введенное в CART сокращение дисперсии часто используется в тех случаях, когда целевая переменная является непрерывной (дерево регрессии), что означает, что использование многих других метрик сначала потребует дискретизации перед применением. Уменьшение дисперсии узла N определяется как общее уменьшение дисперсии целевой переменной Y из-за разделения в этом узле:

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

Мера «добра»

Используемая CART в 1984 году мера «совершенства» - это функция, которая стремится оптимизировать баланс возможностей разделения кандидатов на создание чистых детей с его способностью создавать детей одинакового размера. Этот процесс повторяется для каждого нечистого узла, пока дерево не будет завершено. Функция , где является кандидатом на разделение в узле , определяется следующим образом.

где и - левый и правый дочерние элементы узла, использующего split , соответственно; и - пропорции записей в и , соответственно; и и - пропорции записей класса в и , соответственно.

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

Покупатель Экономия Ресурсы Доход (1000 долларов) Риск кредита
1 Середина Высокий 75 Хороший
2 Низкий Низкий 50 Плохой
3 Высокий Середина 25 Плохой
4 Середина Середина 50 Хороший
5 Низкий Середина 100 Хороший
6 Высокий Высокий 25 Хороший
7 Низкий Низкий 25 Плохой
8 Середина Середина 75 Хороший

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

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

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

Использует

Преимущества

Среди других методов интеллектуального анализа данных деревья решений имеют ряд преимуществ:

  • Просто понять и интерпретировать. Люди могут понять модели дерева решений после краткого объяснения. Деревья также могут отображаться графически таким образом, чтобы их было легко интерпретировать неспециалистам.
  • Может обрабатывать как числовые, так и категориальные данные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. (Например, правила отношения могут использоваться только с номинальными переменными, в то время как нейронные сети могут использоваться только с числовыми переменными или категориальными значениями, преобразованными в значения 0-1.) Ранние деревья решений были способны обрабатывать только категориальные переменные, но более поздние версии, такие как как C4.5, не имеют этого ограничения.
  • Требуется небольшая подготовка данных. Другие методы часто требуют нормализации данных. Поскольку деревья могут обрабатывать качественные предикторы, нет необходимости создавать фиктивные переменные .
  • Использует модель белого или открытого ящика. Если данная ситуация наблюдается в модели, объяснение условия легко объяснить с помощью булевой логики. Напротив, в модели черного ящика объяснение результатов обычно трудно понять, например, с помощью искусственной нейронной сети .
  • Возможна проверка модели с помощью статистических тестов. Это позволяет учитывать надежность модели.
  • Непараметрический подход, который не делает никаких предположений об обучающих данных или остатках прогноза; например, отсутствие предположений о распределении, независимости или постоянной дисперсии
  • Хорошо работает с большими наборами данных. Большие объемы данных можно анализировать с использованием стандартных вычислительных ресурсов в разумные сроки.
  • Более точно отражает процесс принятия решений человеком, чем другие подходы. Это может быть полезно при моделировании решений / поведения человека.
  • Устойчив к коллинеарности, особенно к повышению
  • Встроенный выбор функций . Дополнительные нерелевантные функции будут реже использоваться, чтобы их можно было удалить при последующих запусках. Иерархия атрибутов в дереве решений отражает важность атрибутов. Это означает, что функции сверху наиболее информативны.
  • Деревья решений могут аппроксимировать любую логическую функцию, например XOR .

Ограничения

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

Реализации

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

Примеры включают

  • Salford Systems CART (которая лицензировала проприетарный код оригинальных авторов CART),
  • IBM SPSS Modeler ,
  • RapidMiner ,
  • SAS Enterprise Miner ,
  • Матлаб ,
  • R (программная среда с открытым исходным кодом для статистических вычислений, которая включает несколько реализаций CART, таких как пакеты rpart, party и randomForest),
  • Weka (бесплатный пакет для интеллектуального анализа данных с открытым исходным кодом, содержащий множество алгоритмов дерева решений),
  • Оранжевый ,
  • KNIME ,
  • Microsoft SQL Server [1] и
  • scikit-learn (бесплатная библиотека машинного обучения с открытым исходным кодом для языка программирования Python ).

Расширения

Графики решений

В дереве решений, все пути от корневого узла к узлу листа проследовать путем конъюнкция, или и . В графе решений можно использовать дизъюнкции (OR), чтобы объединить еще два пути вместе с использованием минимальной длины сообщения (MML). Графы решений были дополнительно расширены, чтобы дать возможность динамически изучать ранее неустановленные новые атрибуты и использовать их в разных местах на графике. Более общая схема кодирования приводит к лучшей точности прогнозирования и вероятностной оценке логарифмических потерь. В общем, графы решений выводят модели с меньшим количеством листьев, чем деревья решений.

Альтернативные методы поиска

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

Также можно выполнить выборку дерева с помощью MCMC .

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

Смотрите также

использованная литература

дальнейшее чтение

  • Джеймс, Гарет; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2017). «Древовидные методы» (PDF) . Введение в статистическом обучение: с приложениями в R . Нью-Йорк: Спрингер. С. 303–336. ISBN 978-1-4614-7137-0.

внешние ссылки