WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Дерево принятия решений (также может называться деревом классификации или регрессионным деревом) — средство поддержки принятия решений, использующееся в машинном обучении, анализе данных и статистике. Структура дерева представляет собой «листья» и «ветки». На рёбрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение. Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе.

Каждый лист представляет собой значение целевой переменной, изменённой в ходе движения от корня по листу. Каждый внутренний узел соответствует одной из входных переменных. Дерево может быть также «изучено» разделением исходных наборов переменных на подмножества, основанные на тестировании значений атрибутов. Это процесс, который повторяется на каждом из полученных подмножеств. Рекурсия завершается тогда, когда подмножество в узле имеет те же значения целевой переменной, таким образом, оно не добавляет ценности для предсказаний. Процесс, идущий «сверху вниз», индукция деревьев решений (TDIDT)^[1], является примером поглощающего «жадного» алгоритма, и на сегодняшний день является наиболее распространённой стратегией деревьев решений для данных, но это не единственная возможная стратегия. В интеллектуальном анализе данных, деревья решений могут быть использованы в качестве математических и вычислительных методов, чтобы помочь описать, классифицировать и обобщить набор данных, которые могут быть записаны следующим образом:

${\displaystyle (x,Y)=(x_{1},x_{2},x_{3}\dots x_{k},Y)}$

Зависимая переменная Y является целевой переменной, которую необходимо проанализировать, классифицировать и обобщить. Вектор ${\displaystyle x}$ состоит из входных переменных ${\displaystyle x_{1}}$ , ${\displaystyle x_{2}}$ , ${\displaystyle x_{3}}$ и т. д., которые используются для выполнения этой задачи.

Основные определения

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

Дерево решений состоит из трёх типов узлов:

• Узлы решения — обычно представлены квадратами
• Вероятностные узлы — представляются в виде круга
• Замыкающие узлы — представляются в виде треугольника

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

Типология деревьев

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

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

Упомянутые выше термины впервые были введены Брейманом и др.^[2] Перечисленные типы имеют некоторые сходства (рекурсивный алгоритмы построения), а также некоторые различия, такие, как критерии выбора разбиения в каждом узле.^[2]

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

1. Бэггинг над деревьями решений, наиболее ранний подход. Строит несколько деревьев решений, неоднократно интерполируя данные с заменой (бутстреп), и в качестве консенсусного ответа выдаёт результат голосования деревьев (их средний прогноз);^[3]
2. Классификатор «Случайный лес» основан на бэггинге, однако в дополнение к нему случайным образом выбирает подмножество признаков в каждом узле, с целью сделать деревья более независимыми;
3. Бустинг над деревьями может быть использован для задач как регрессии, так и классификации.^[4] Одна из реализаций бустинга над деревьями, алгоритм XGBoost, неоднократно использовался победителями соревнований по анализу данных.
4. «Вращение леса» — деревья, в которых каждое дерево решений анализируется первым применением метода главных компонент (PCA) на случайные подмножества входных функций.^[5]

Алгоритмы построения дерева

Есть различные способы выбирать очередной атрибут:

• Алгоритм ID3, где выбор атрибута происходит на основании прироста информации (англ. Gain), либо на основании критерия Джини.
• Алгоритм C4.5 (улучшенная версия ID3), где выбор атрибута происходит на основании нормализованного прироста информации (англ. Gain Ratio).
• Алгоритм CART и его модификации — IndCART, DB-CART.
• Автоматический детектор взаимодействия Хи-квадрат (CHAID). Выполняет многоуровневое разделение при расчёте классификации деревьев;^[6]
• MARS: расширяет деревья решений для улучшения обработки цифровых данных.

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

Достоинства метода

Среди прочих методов Data Mining, метод дерева принятия решений имеет несколько достоинств:

• Прост в понимании и интерпретации. Люди способны интерпретировать результаты модели дерева принятия решений после краткого объяснения
• Не требует подготовки данных. Прочие техники требуют нормализации данных, добавления фиктивных переменных, а также удаления пропущенных данных.
• Способен работать как с категориальными, так и с интервальными переменными. Прочие методы работают лишь с теми данными, где присутствует лишь один тип переменных. Например, метод отношений может быть применён только на номинальных переменных, а метод нейронных сетей только на переменных, измеренных по интервальной шкале.
• Использует модель «белого ящика». Если определённая ситуация наблюдается в модели, то её можно объяснить при помощи булевой логики. Примером «черного ящика» может быть искусственная нейронная сеть, так как результаты данной модели поддаются объяснению с трудом.
• Позволяет оценить модель при помощи статистических тестов. Это даёт возможность оценить надёжность модели.
• Является надёжным методом. Метод хорошо работает даже в том случае, если были нарушены первоначальные предположения, включённые в модель.
• Позволяет работать с большим объёмом информации без специальных подготовительных процедур. Данный метод не требует специального оборудования для работы с большими базами данных.

Недостатки метода

• Проблема получения оптимального дерева решений является NP-полной с точки зрения некоторых аспектов оптимальности даже для простых задач^[7][8]. Таким образом, практическое применение алгоритма деревьев решений основано на эвристических алгоритмах, таких как алгоритм «жадности», где единственно оптимальное решение выбирается локально в каждом узле. Такие алгоритмы не могут обеспечить оптимальность всего дерева в целом.
• В процессе построения дерева решений могут создаваться слишком сложные конструкции, которые недостаточно полно представляют данные. Данная проблема называется переобучением^[9]. Для того, чтобы её избежать, необходимо использовать метод «регулирования глубины дерева».
• Существуют концепты, которые сложно понять из модели, так как модель описывает их сложным путём. Данное явление может быть вызвано проблемами XOR, чётности или мультиплексарности. В этом случае мы имеем дело с непомерно большими деревьями. Существует несколько подходов решения данной проблемы, например, попытка изменить репрезентацию концепта в модели (составление новых суждений)^[10], или использование алгоритмов, которые более полно описывают и репрезентируют концепт (например, метод статистических отношений, индуктивная логика программирования).
• Для данных, которые включают категориальные переменные с большим набором уровней (закрытий), больший информационный вес присваивается тем атрибутам, которые имеют большее количество уровней.^[11]

Регулирование глубины дерева

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

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

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

Пример задачи

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

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

У нас есть некоторая статистика на этот счёт:

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

См. также

• Random forest − классификатор, основанный на применении комитетов из решающих деревьев
• Переобучение
• Машинное обучение
• Таблица принятия решений

Примечания

Ссылки

• Конспект лекции по деревьям принятия решений
• Decision trees applet provides several sample data sets of examples to learn and classify

Литература

• Левитин А. В. Глава 10. Ограничения мощи алгоритмов: Деревья принятия решения // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 409–417. — 576 с. — ISBN 978-5-8459-0987-9
  <a href='https://wikidata.org/wiki/Track:Q21694518'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a><a href='https://wikidata.org/wiki/Track:Q21694522'></a>
• Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд.. — СПб: Питер, 2013. — С. 428-472. — ISBN 978-5-459-00717-6.