Дерево решений и случайный лес
Дерево решений — логический алгоритм классификации, решающий задачи классификации и регрессии.
Содержание
Дерево решений
Определение: |
Дерево решений (англ. decision tree, DT) — алгоритм классификации
| , задающийся деревом (связным ациклическим графом), где:
Определение: |
Бинарное дерево решений — частный случай дерева решений, для которого | .
function classify(x):if else return
Рекурсивный алгоритм построения бинарного дерева решений ID3
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм
(англ. Induction of Decision Tree) заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату , который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида .Информативность ветвления
Для того, чтобы оценивать качество разбиения объектов по предикату
, введем понятие меры неопределенности распределения значений классов среди объектов после разбиения их на множества.
Определение: |
Частотная оценка вероятности класса | в вершине :
Определение: |
Мера неопределенности (англ. impurity) распределения
где убывает и , например: , , | :
Примеры:
- Энтропия:
- Критерий Джини:
Определение: |
Неопределенность распределения | после ветвления вершины по предикату и разбиения :
Определение: |
Информационный выигрыш от ветвления вершины |
Проще всего записать этот алгоритм в виде рекурсивной процедуры , которая строит дерево по заданной подвыборке и возвращает его корневую вершину.
1:function ID3(): 2: if : , // создать листовую вершину c меткой класса 3: v = createLeafVertex( ) 4: return v // найти предикат с максимальной информативностью Gain( , ) // разбить выборку на две части по предикату 5: 6: 7: if || // найти класс, в котором находится большинство объектов из 8: = majorClass( ) 9: v = createLeafVertex( ) else // создать внутреннюю вершину 10: v = createVertex() 11: 12: = ID3( ) 13: = ID3( ) 14: return
Редукция решающих деревьев
Суть редукции состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.
Предредукция
Предредукция (англ. pre-pruning) или критерий раннего останова досрочно прекращает дальнейшее ветвление в вершине дерева, если информативность
Для этого на шаге 8 алгоритма условие или заменяется условием . Порог является управляющим параметром метода.
Предредукция считается не самым эффективным способом избежать переобучения, так как жадное ветвление по-прежнему остаётся глобально неоптимальным. Более эффективной считается cтратегия постредукции.
Постредукция
Постредукция (англ. post-pruning) просматривает все внутренние вершины дерева и заменяет отдельные вершины либо одной из дочерних вершин (при этом вторая дочерняя удаляется), либо терминальной вершиной. Процесс замен продолжается до тех
пор, пока в дереве остаются вершины, удовлетворяющие критерию замены.
Критерием замены является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов.
Для реализации постредукции контрольная выборка пропускается через
построенное дерево. При этом в каждой внутренней вершине запоминается подмножество попавших в неё контрольных объектов. Если , то вершина считается ненадёжной и заменяется терминальной по мажоритарному правилу:
в качестве берётся тот класс, объектов которого больше всего в обучающей подвыборке , пришедшей в вершину .
Затем для каждой внутренней вершины вычисляется число ошибок, полученных при классификации выборки следующими способами:
- — классификация поддеревом, растущим из вершины ;
- — классификация поддеревом левой дочерней вершины ;
- — классификация поддеревом правой дочерней вершины ;
-
Эти величины сравниваются, и, в зависимости от того, какая из них оказалась
минимальной, принимается, соответственно, одно из четырёх решений:
- сохранить поддерево вершины ;
- заменить поддерево вершины поддеревом левой дочерней вершины ;
- заменить поддерево вершины поддеревом правой дочерней вершины ;
- заменить поддерево терминальной вершиной класса .
Алгоритмы построения деревьев решения
- Алгоритм ID3
- Алгоритм C4.5
- Алгоритм CART
- Алгоритм LISTBB
Композиции решающих деревьев
Для повышения точности модели применяют объединения моделей (классификаторов) в ансамбль.
Виды ансамблей
Бутстрэп
Метод бутстрэпа (англ. bootstrap aggregation) — один из первых и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений и заключается в следующем. Пусть имеется выборка
Обозначим новую выборку через . Повторяя процедуру раз, сгенерируем подвыборок . Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
Бэггинг
Рассмотрим, следующий вид ансамбля — бэггинг (англ. bagging). Пусть имеется обучающая выборка
. С помощью бутстрэпа сгенерируем из неё выборки . Теперь на каждой выборке обучим свой классификатор . Итоговый классификатор будет усреднять ответы всех этих алгоритмов .Случайный лес
Алгоритм построения случайного леса, состоящего из
деревьев на основе обучающей выборки :for (n: 1,...,N): сгенерировать выборкуc помощью бутстрэпа построить решающее дерево по выборке
Итоговый классификатор —
Таким образом, случайный лес — это бэггинг над решающими деревьями, при обучении которых для каждого разбиения признаки выбираются из некоторого случайного подмножества признаков.
Примеры использования (в scikit-learn)
- Для решения задач классификации и регрессии используют DecisionTreeClassifier, DecisionTreeRegressor
- В 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)
Пример использования классификатора на случайном лесе:
from sklearn import RandomForestClassifier from sklearn.datasets import make_classification // сгенерируем рандомный обучающий набор с классификацией по n_classes классам X, y = make_classification(n_samples=1000, n_features=4, n_classes = 5) // создадим классификатор на случайном лесе, состоящим из n_estimators деревьев clf = RandomForestClassifier(n_estimators=100, max_depth=2) // обучим классификатор на сгенерированном обучающем множестве clf.fit(X, y) clf.predict(0, 0, 0, 0)
Пример использования на языке Scala
SBT зависимость:
libraryDependencies += "com.github.haifengl" %% "smile-scala" % "1.5.2"
Пример классификации датасета и вычисления F1 меры[1] используя smile.classification.cart[2]:
import smile.classification._ import smile.data._ import smile.plot._ import smile.read import smile.validation.FMeasure
val iris: AttributeDataset = read.table("iris.csv", delimiter = ",", response = Some((new NumericAttribute("class"), 2))) val x: Array[Array[Double]] = iris.x() val y: Array[Int] = iris.y().map(_.toInt) val dt: DecisionTree = cart(x, y, 1000) val predictions: Array[Int] = x.map(dt.predict) val f1Score = new FMeasure().measure(predictions, y) plot(x, y, dt)
Ссылки
- Лекции по логическим алгоритмам классификации — К. В. Воронцов.
- Случайный лес — Medium, Yury Kashnitskiy.
- Деревья решений — scikit-learn.org.
- Ансамбли — scikit-learn.org.