4441940
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
about 8 years ago
|
|
| Question | Answer |
| Бинарное решающее дерево | Это бинарное дерево, узлы которого - логические предикаты, а листья - классы объекта. |
| Алгоритм построения решающего дерева ID3 | Суть: на каждом этапе выбираем лучшее разделение на классы по 1 признаку (ищем предикат с максимальной информативностью), проводим разделение и вызываемся рекурсивно. Алгоритм жадный, то есть глобально не оптимален. |
| Критерии ветвления | - Критерий Джини: #{(xi,xj) : yi = yj и B(xi) = B(xj)} - D-критерий В. И. Донского: #{(xi,xj): yi != yj и B(xi) != B(xj)} - Энтропийный критерий - на практике почти тоже самое, чо критерий Джини |
| Обработка пропусков на стадии обучения | Если предикат для объекта не определён, то его исключаем из рассмотрения на данном этапе; Для каждого узла подсчитываем вероятность того, что объект пойдёт налево/направо; Для каждого узла подсчитываем вероятность того, что по достижению этого узла объект потом окажется в каждом конкретном классе. |
| Обработка пропусков на стадии классификации | Если значение предиката не определено, пускаем объект по обеим ветвям, при том результат взвешиваем с соответствующими вероятностями. В качестве конечного результата берём наиболее вероятный класс. |
| Достоинства решающих деревьев | Гибкость, интерпретируемость, терпимость к пропускам, отсутствие необходимости в масштабировании, линейная сложность по длине выборки, нет отказов от классификации. |
| Недостатки решающих деревьев | Переобучение - структура дерева сильно переусложняется; Фрагментация выборки - на листах разбиение статистически ненадёжно; Высокая чувствительность к шуму, составу выборки, критерию информативности. |
| Усечение дерева | Разбиваем выборку на обучающую и контрольную. Каждый лист затем смотрим по контрольной выборке число ошибок: классификацией деревом из данной вершины, из его поддеревьев, отнесением к классу. В зависимости от результата сохраняем поддерево, укорачиваем либо терминируем. |
| CART - обобщение на случай регрессии | Каждому листу соответствует среднее значение целевой функции тех объектов, которые до него дошли. Критерий оптимизации - СКО (с помощью МНК). |
| Идея критерия Minimal Cost-Complexity Pruning | К целевой функции, которая оптимизируется, прибавляется высота листа, помноженная на некую константу регулярности. |
Want to create your own Flashcards for free with GoConqr? Learn more.