Классификация
Задача классификации — отнесение объекта к одному из заранее определенных классов на основании его признаков.
Пусть \(x \in \mathbb{R^{p}}\) — объект, описывающийся \(p\) признаками, в задаче классификации рассматриваем \(n\) таких объектов \(X = (x_{1},..,x_{n})\).
Обозначим за \(Y\) множество классов, которым принадлежат \(x_{i}, i = \overline{1:n}\). Предполагается, что существует неизвестная целевая зависимость — отображение \(f: X \rightarrow Y\), значения которой известны только на элементах конечной обучающей выборки \(\{(x_{1}, y_{1}),..,(x_{m}, y_{m})\}, \quad m < n, y_{i} \in Y\). Остальные элементы \(\{x_{m+1},..,x_{n}\}\) назовем тестовой выборкой.
Задачей классификации является аппроксимация \(f\) на всё пространство \(X\). То есть требуется по обучающим данным выявить общие зависимости, закономерности, взаимосвязи, присущие не только этой конкретной подвыборке, а всей генеральной совокупности.
Алгоритм классификации “Случайный лес”
Случайный лес (Random Forest) — один из алгоритмов data mining, который решает как задачи регрессии, так и классификации.
Пусть есть некоторый не самый точный алгоритм, например, дерево принятия решений. Если создать множество деревьев принятия решений и усреднить результат их предсказаний (в случае решения задачи регрессии) или принять решение путём голосования (в случае классификации), то итоговый результат будет существенно информативнее. Таким образом устроено обучение ансамбля. Важным моментом тут является элемент случайности в создании каждого дерева. Очевидно, что если создать много одинаковых деревьев, то результат их усреднения будет обладать точностью одного дерева.
Дерево принятия решений
Каждая вершина дерева представляет собой точку разбиения данных. Вершина определяет некоторый простой критерий, по которому данные делятся на части. Для простоты далее будут рассматриваться только бинарные деревья, где каждая вершина делит данные на две части, именно они используются на практике. Кроме того, разбиение будет происходить по единственному параметру. Таким образом, в каждой вершине дерева разбиваются данные на две части согласно значению одного из параметров.
Приведем абстрактный пример построения дерева принятия решений.
Пусть узлы помечены некоторым предикатом \(\Pi_{i}: X \rightarrow \{True, False\}, i = 1,2..\).
Листья — \(y_{i} \in Y = \{0, 1\}\).
Разбиение данных происходит в каждом узле по единственному признаку.
Допустим, решается задача классификации и нужно разбить некоторое множество людей — X на мужчин и женщин. Тогда присвоим, например, мужчинам — 0, а женщинам — 1. На выходе получим отдельно мужчин, которые удовлетворяют своим критериям разбиения, и отдельно женщин.
Здесь неочевидными остаются только три вещи:
- Как выбирается параметр по которому происходит разбиение
- Как выбирается пороговое значения параметра
- Когда алгоритм должен остановиться
В некоторых реализация параметр, по которому происходит разбиение, и пороговое значение этого параметра находятся методом полного перебора, то есть пробуются все возможные способы разбиения данных по каждому из параметров и оценивается, насколько разбиение было удачным. Например степень удачности разбиения может определяться условиями задачи.
Когда алгоритму остановиться? Есть два варианта: когда дальнейшие разбиения не способны улучшить дерево, например, если в текущей вершине все элементы имеют одинаковое значение. Либо когда мы достигли определенного уровня, например порогового значения элементов в вершине (этот критерий используется по-умолчанию в реализации Random Forest в R).
Голосование деревьев
Как было сказано, выбираются случайные подмножества \(X_{i}\) из обучающей выборки данных \(X\), и для каждого подмножества строится своё дерево принятия решений. Полученный в результате ансамбль деревьев можно использовать для классификации, прогоняя классифицируемый объект через все деревья. Каждое дерево как будто «голосует» за принадлежность объекта к определённому классу. Таким образом, объект относится к тому классу, за который проголосовало большее число деревьев.
Строится \(N\) деревьев принятия решений, где \(N\) — параметр метода.
Пример использования алгоритма классификации “Случайный лес”
library(randomForest)
data(iris)head(iris)## Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1 5.1 3.5 1.4 0.2 setosa
## 2 4.9 3.0 1.4 0.2 setosa
## 3 4.7 3.2 1.3 0.2 setosa
## 4 4.6 3.1 1.5 0.2 setosa
## 5 5.0 3.6 1.4 0.2 setosa
## 6 5.4 3.9 1.7 0.4 setosaРазделим выборку на тренировочную и тестовую, предварительно перемешав её.
N <- nrow(iris)
sample.index <- sample(N)
data.frame <- iris[sample.index,]
iris.training <- data.frame[1:(2*N/3), ]
iris.test <- data.frame[(2*N/3):N, ]library(randomForest)## randomForest 4.6-12
## Type rfNews() to see new features/changes/bug fixes.iris.rf <- randomForest(Species~ ., data = iris.training, ntree = 100, proximity=TRUE)
table(predict(iris.rf), iris.training$Species) ##
## setosa versicolor virginica
## setosa 33 0 0
## versicolor 0 31 2
## virginica 0 1 33print(iris.rf)##
## Call:
## randomForest(formula = Species ~ ., data = iris.training, ntree = 100, proximity = TRUE)
## Type of random forest: classification
## Number of trees: 100
## No. of variables tried at each split: 2
##
## OOB estimate of error rate: 3%
## Confusion matrix:
## setosa versicolor virginica class.error
## setosa 33 0 0 0.00000000
## versicolor 0 31 1 0.03125000
## virginica 0 2 33 0.05714286attributes(iris.rf)## $names
## [1] "call" "type" "predicted"
## [4] "err.rate" "confusion" "votes"
## [7] "oob.times" "classes" "importance"
## [10] "importanceSD" "localImportance" "proximity"
## [13] "ntree" "mtry" "forest"
## [16] "y" "test" "inbag"
## [19] "terms"
##
## $class
## [1] "randomForest.formula" "randomForest"Информативность признаков.
importance(iris.rf) ## MeanDecreaseGini
## Sepal.Length 6.512610
## Sepal.Width 1.093225
## Petal.Length 26.762031
## Petal.Width 31.534133varImpPlot(iris.rf)
Проверка обученной модели на тестовых данных.
risPred <- predict(iris.rf, newdata = iris.test)
Pred <- predict(iris.rf, newdata = iris.test)
table(Pred, iris.test$Species)##
## Pred setosa versicolor virginica
## setosa 17 0 0
## versicolor 0 17 1
## virginica 0 2 14mean(Pred == iris.test$Species)## [1] 0.9411765