Karteikarten
1.2) Решающие деревья
Karten in diesem Stapel (10)
- 1Бинарное решающее деревоЭто бинарное дерево, узлы которого - логические предикаты, а листья - классы объекта.
- 2Алгоритм построения решающего дерева ID3Суть: на каждом этапе выбираем лучшее разделение на классы по 1 признаку (ищем предикат с максимальной информативностью), проводим разделение и вызываемся рекурсивно. Алгоритм жадный, то есть глобально не оптимален.
- 3Критерии ветвления- Критерий Джини: #{(xi,xj) : yi = yj и B(xi) = B(xj)}
- D-критерий В. И. Донского: #{(xi,xj): yi != yj и B(xi) != B(xj)}
- Энтропийный критерий - на практике почти тоже самое, чо критерий Джини - 4Обработка пропусков на стадии обученияЕсли предикат для объекта не определён, то его исключаем из рассмотрения на данном этапе;
Для каждого узла подсчитываем вероятность того, что объект пойдёт налево/направо;
Для каждого узла подсчитываем вероятность того, что по достижению этого узла объект потом окажется в каждом конкретном классе. - 5Обработка пропусков на стадии классификацииЕсли значение предиката не определено, пускаем объект по обеим ветвям, при
том результат взвешиваем с соответствующими вероятностями. В качестве конечного результата берём наиболее вероятный класс. - 6Достоинства решающих деревьевГибкость, интерпретируемость, терпимость к пропускам, отсутствие необходимости в масштабировании, линейная сложность по длине выборки, нет отказов от классификации.
- 7Недостатки решающих деревьевПереобучение - структура дерева сильно переусложняется;
Фрагментация выборки - на листах разбиение статистически ненадёжно;
Высокая чувствительность к шуму, составу выборки, критерию информативности. - 8Усечение дереваРазбиваем выборку на обучающую и контрольную. Каждый лист затем смотрим по контрольной выборке число ошибок: классификацией деревом из данной вершины, из его поддеревьев, отнесением к классу. В зависимости от результата сохраняем поддерево, укорачиваем либо терминируем.
- 9CART - обобщение на случай регрессииКаждому листу соответствует среднее значение целевой функции тех объектов, которые до него дошли. Критерий оптимизации - СКО (с помощью МНК).
- 10Идея критерия Minimal Cost-Complexity PruningК целевой функции, которая оптимизируется, прибавляется высота листа, помноженная на некую константу регулярности.
Informationen
- Beschreibung
- Карточки по второй части лекции первой недели курса "Машинное обучение" от Яндекса и ВШЭ на coursera.org
- Erstellt von
- Sergei Fomin
- Aufrufe
- 95
- Tags
- Bewertung