Дерево решений и случайный лес
Дерево решений — логический алгоритм классификации, решающий задачи классификации и регрессии. Представляет собой объединение логических условий в структуру дерева.
Содержание
Дерево решений[править]
Определение: |
Дерево решений (англ. decision tree, DT) — алгоритм классификации
| , задающийся деревом (связным ациклическим графом), где:
Определение: |
Бинарное дерево решений — частный случай дерева решений, для которого | .
function classify(x):if else return
Информативность ветвления[править]
Для того, чтобы оценивать качество разбиения объектов по предикату
Сначала оценим распределение значений классов объектов внутри каждого множества из разбиения, введя понятие меры неопределенности распределения.
Определение: |
Частотная оценка вероятности класса | в вершине :
Определение: |
Мера неопределенности (англ. impurity) распределения
где убывает и , например: , , | :
Примерами мер неопределенности распределения являются:
- Энтропия: , определяется для каждого множества из разбиения, — количество возможных классов, и — вероятность объекта принадлежать -ому классу.
- Критерий Джини:
Теперь определим суммарную неопределенность распределения в разбиении.
Определение: |
Неопределенность распределения | после ветвления вершины по предикату и разбиения :
Информационный выигрыш от разбиения определяется как изменение неопределенности в системе.
Определение: |
Информационный выигрыш от разбиения по предикату |
Рекурсивный алгоритм построения бинарного дерева решений ID3[править]
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм
Проще всего записать этот алгоритм в виде рекурсивной процедуры , которая строит дерево по заданной подвыборке и возвращает его корневую вершину.
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
Редукция решающих деревьев[править]
Суть редукции (англ. pruning) состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.
Предредукция[править]
Предредукция (англ. pre-pruning) или критерий раннего останова досрочно прекращает дальнейшее ветвление в вершине дерева, если информативность
Для этого на шаге 8 алгоритма условие или заменяется условием . Порог является управляющим параметром метода.
Предредукция считается не самым эффективным способом избежать переобучения, так как жадное ветвление по-прежнему остаётся глобально неоптимальным. Более эффективной считается cтратегия постредукции.
Постредукция[править]
Постредукция (англ. post-pruning) просматривает все внутренние вершины дерева и заменяет отдельные вершины либо одной из дочерних вершин (при этом вторая дочерняя удаляется), либо терминальной вершиной. Процесс замен продолжается до тех
пор, пока в дереве остаются вершины, удовлетворяющие критерию замены.
Критерием замены является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов.
Для реализации постредукции контрольная выборка пропускается через
построенное дерево. При этом в каждой внутренней вершине запоминается подмножество попавших в неё контрольных объектов. Если , то вершина считается ненадёжной и заменяется терминальной по мажоритарному правилу:
в качестве берётся тот класс, объектов которого больше всего в обучающей подвыборке , пришедшей в вершину .
Затем для каждой внутренней вершины вычисляется число ошибок, полученных при классификации выборки следующими способами:
- — классификация поддеревом, растущим из вершины ;
- — классификация поддеревом левой дочерней вершины ;
- — классификация поддеревом правой дочерней вершины ;
-
Эти величины сравниваются, и в зависимости от того, какая из них оказалась
минимальной, принимается, соответственно, одно из четырёх решений:
- сохранить поддерево вершины ;
- заменить поддерево вершины поддеревом левой дочерней вершины ;
- заменить поддерево вершины поддеревом правой дочерней вершины ;
- заменить поддерево терминальной вершиной класса .
Алгоритмы построения деревьев решения[править]
Недостатки рассмотренного алгоритма ID3:
- Применим только для дискретных значений признаков;
- Переобучение;
- На каждом шаге решение принимается по одному атрибуту.
Алгоритм CART (англ. Classification And Regression Trees)[править]
- В отличие от ID3 работает и с непрерывными значениями признаков: на каждом шаге построения дерева последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него. Разбивает объекты на две части;
- Использует редукцию для избежания переобучения;
- Обрабатывает пропущенные или аномальные значения признаков.
Алгоритм C4.5[править]
- Также работает и с непрерывными значениями признаков: на каждом шаге построения дерева выбирает правило разбиения по одному из признаков. Разбивает объекты на несколько частей по этому правилу, рекурсивно запускается из полученных подмножеств;
- Использует редукцию для избежания переобучения;
- Обрабатывает пропущенные или аномальные значения признаков.
Случайный лес[править]
Случайный лес — один из примеров объединения классификаторов в ансамбль.
Алгоритм построения случайного леса, состоящего из деревьев на основе обучающей выборки такой:
for (n: 1,...,N): // сгенерировать выборку бутстрэпа = bootstrap( ) // построить решающее дерево по выборке = ID3( )c помощью
Итоговый классификатор —
Таким образом, случайный лес — бэггинг над решающими деревьями, при обучении которых для каждого разбиения признаки выбираются из некоторого случайного подмножества признаков.
Примеры кода[править]
Примеры на языке Python[править]
- Для решения задач классификации и регрессии используют 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_features=2, n_redundant=0, n_informative=2, random_state=1, n_clusters_per_class=1, n_classes=2) // разбиваем выборку на обучающую и тестовую X = StandardScaler().fit_transform(X) X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4, random_state=42) // создадим классификатор на случайном лесе, состоящим из n_estimators деревьев RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1) clf.fit(X_train, y_train) score = clf.score(X_test, y_test)
Результат классификации показан на рисунке.
Пример на языке 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)
Пример на языке Java[править]
Пример классификации с применением weka.classifiers.trees.RandomForest
[3]
Maven
зависимость:
<dependency> <groupId>nz.ac.waikato.cms.weka</groupId> <artifactId>weka-stable</artifactId> <version>3.8.0</version> </dependency>
import weka.classifiers.evaluation.Evaluation; import weka.classifiers.trees.RandomForest;
// read dataset var trainingDataSet = getDataSet(...); var testingDataSet = getDataSet(...); // create random forest classifier var forest = new RandomForest(); forest.setMaxDepth(15); forest.setNumFeatures(2); forest.buildClassifier(trainingDataSet); // evaluate the model on test dataset and print summary var eval = new Evaluation(trainingDataSet); eval.evaluateModel(forest, testingDataSet); System.out.println(eval.toSummaryString());
Пример на языке R[править]
Деревья решений[править]
Для создания деревьев решений используется функция ctree()
из пакета party
.
# importing package install.packages("party") # reading data rdata <- read.csv("input.csv", sep = ',', header = FALSE) # evaluating model output.tree <- ctree(target ~ x + y + z, data = rdata) # plotting results plot(output.tree)
Случайный лес[править]
Для создания случайного леса необходимо импортировать пакет randomForest
# importing packages install.packages("party") install.packages("randomForest") # reading data rdata <- read.csv("input.csv", sep = ',', header = FALSE) # creating the forest output.forest <- randomForest(target ~ x + y + z, data = rdata) # getting results print(output.forest)
См. также[править]
Источники информации[править]
- Логические алгоритмы классификации — Лекция К. В. Воронцова
- Случайный лес — статья на Medium, Yury Kashnitskiy
- Деревья решений — scikit-learn.org
- Ансамбли классификаторов — scikit-learn.org.