Дерево решений и случайный лес
Содержание
Дерево решений
Определение: |
Дерево решений (англ. decision tree, DT) — алгоритм классификации
| , задающийся деревом (связным ациклическим графом):
Определение: |
Бинарное дерево решений — частный случай дерева решений, для которого
| .
function classify(x):if then else return
Рекурсивный алгоритм построения бинарного дерева решений ID3
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм
Проще всего записать этот алгоритм в виде рекурсивной процедуры , которая строит дерево по заданной подвыборке и возвращает его корневую вершину.
1:function ID3(): 2: if все объекты множества принадлежат одному классу then 3: создать новый лист 4: 5: return v 6: найти предикат с максимальной информативностью : Gain( , ) 7: разбить выборку на две части по предикату : 8: if или then 9: создать новый лист 10: = класс, в котором находится большинство объектов из 11: else 12: создать новую внутреннюю вершину 13: 14: = ID3( ) 15: = ID3( ) 16: return
Информативность ветвления
Определение: |
Частотная оценка вероятности класса | в вершине :
Определение: |
Мера неопределенности (англ. impurity) распределения
где убывает и , например: , , | :
Примеры:
- Энтропия:
- Критерий Джини:
Определение: |
Неопределенность распределения | после ветвления вершины по предикату и разбиения :
Определение: |
Информационный выигрыш от ветвления вершины |
Редукция решающих деревьев
Суть редукции состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.
Предредукция
Предредукция (англ. pre-pruning) или критерий раннего останова досрочно прекращает дальнейшее ветвление в вершине дерева, если информативность
Для этого на шаге 8 алгоритма условие или заменяется условием . Порог является управляющим параметром метода.
Предредукция считается не самым эффективным способом избежать переобучения, так как жадное ветвление по-прежнему остаётся глобально неоптимальным. Более эффективной считается cтратегия постредукции.
Постредукция
Постредукция (англ. post-pruning) просматривает все внутренние вершины дерева и заменяет отдельные вершины либо одной из дочерних вершин (при этом вторая дочерняя удаляется), либо терминальной вершиной. Процесс замен продолжается до тех
пор, пока в дереве остаются вершины, удовлетворяющие критерию замены.
Критерием замены является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов.
Для реализации постредукции контрольная выборка пропускается через
построенное дерево. При этом в каждой внутренней вершине запоминается подмножество попавших в неё контрольных объектов. Если , то вершина считается ненадёжной и заменяется терминальной по мажоритарному правилу:
в качестве берётся тот класс, объектов которого больше всего в обучающей подвыборке , пришедшей в вершину .
Затем для каждой внутренней вершины вычисляется число ошибок, полученных при классификации выборки следующими способами:
- — классификация поддеревом, растущим из вершины ;
- — классификация поддеревом левой дочерней вершины ;
- — классификация поддеревом правой дочерней вершины ;
-
Эти величины сравниваются, и, в зависимости от того, какая из них оказалась
минимальной, принимается, соответственно, одно из четырёх решений:
- сохранить поддерево вершины ;
- заменить поддерево вершины поддеревом левой дочерней вершины ;
- заменить поддерево вершины поддеревом правой дочерней вершины ;
- заменить поддерево терминальной вершиной класса .
Алгоритмы построения деревьев решения
- Алгоритм ID3
- Алгоритм C4.5
- Алгоритм CART
- Алгоритм LISTBB
Композиции решающих деревьев
Для повышения точности модели применяют объединения моделей (классификаторов) в ансамбль.
Виды ансамблей
Бутстрэп
Метод бутстрэпа (англ. bootstrap aggregation) — один из первых и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений и заключается в следующем. Пусть имеется выборка
Обозначим новую выборку через . Повторяя процедуру раз, сгенерируем подвыборок . Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
Бэггинг
Рассмотрим, следующий вид ансамбля — бэггинг (англ. bagging). Пусть имеется обучающая выборка
. С помощью бутстрэпа сгенерируем из неё выборки . Теперь на каждой выборке обучим свой классификатор . Итоговый классификатор будет усреднять ответы всех этих алгоритмов .Случайный лес
Алгоритм построения случайного леса, состоящего из
деревьев на основе обучающей выборки :for (n: 1,...,N): сгенерировать выборкуc помощью бутстрэпа построить решающее дерево по выборке
Итоговый классификатор —
Таким образом, случайный лес — это бэггинг над решающими деревьями, при обучении которых для каждого разбиения признаки выбираются из некоторого случайного подмножества признаков.
Примеры использования (в scikit-learn)
- DecisionTreeClassifier - используется для классификации
from sklearn import tree // X - массив, содержащий описание объектов из обучающей выборки X = [[0, 0], [1, 1]] // Y - значения классов объектов из обучающей выборки Y = [0, 1] clf = tree.DecisionTreeClassifier() // обучение классификатора clf = clf.fit(X, Y) // предсказание значений классов clf.predict(2, 2) // вывод: array([1])
- Для решения задачи регрессии используют DecisionTreeRegressor
from sklearn import tree X = [[0, 0], [2, 2]] y = [0.5, 2.5] clf = tree.DecisionTreeRegressor() clf = clf.fit(X, y) clf.predict(1, 1) // вывод: array([0.5])
- В sklearn.ensemble также представлены методы классификации, основанные на ансамблях, в том числе: бэггинг и случайный лес, которые были описаны выше. Так, в этом примере создается бэггинг ансамбль из классификаторов KNeighborsClassifier, каждый из которых обучен на рандомных подмножествах из 50% объектов из обучающей выборки, и 50% рандомно выбранных признаков.
from sklearn.ensemble import BaggingClassifier from sklearn.neighbors import KNeighborsClassifier bagging = BaggingClassifier(KNeighborsClassifier(), max_samples=0.5, max_features=0.5)
Ссылки
- Classification and Regression Trees — лекции Cosma Shalizi, ноябрь 2009.