Random Forest in R

Загружаем нужные пакеты:

require(randomForest)

## Loading required package: randomForest
## randomForest 4.6-7
## Type rfNews() to see new features/changes/bug fixes.

require(ggplot2)

## Loading required package: ggplot2

Индекс Джини и энтропия

Предположим, что в выборке \( A \) у нас есть объекты разных типов, скажем, черные муравьи, рыжие муравьи и киты. Доля объектов типа \( i \) в выборке \( A \) равна \( f_i \).

В выборке из ста муравьев и одного кита средняя масса муравья может оказаться больше килограмма.

Индекс Джини определяется как \[ I_G=\sum_i f_i(1-f_i) \] Энтропия определяется как (при соглашении \( 0 \cdot \ln 0=0 \)) \[ I_E= - \sum f_i \ln f_i \]

Индекс Джини и энтропия измеряют неоднородность выборки. Индекс Джини и энтропия будут максимальны, если все типы равновероятны. Если же все объекты принадлежат одному типу, то индекс Джини и энтропия равны нулю.

Классификационное дерево

Каждый мужчина должен посадить дерево!

…

Дерево разбивает всю выборку на несколько непересекающихся частей, \( A_1 \), \( A_2 \), … Индекс Джини или энтропия для дерева определяются как взвешенные по частям:

\[ I_G(Tree)=\sum_j P(A_j) \cdot I_G(A_j) \] \[ I_E(Tree)=\sum_j P(A_j) \cdot I_E(A_j) \]

где \( P(A_j) \) — размер выборки \( A_j \) деленный на общее число наблюдений.

Как посадить одно дерево для качественной переменной?

Существует куча алгоритмов как построить одно дерево. Рассмотрим один под условным названием “Джин жадный до Джини” :)

Алгоритм растит дерево так, чтобы падение индекса Джини было максимальным на каждом шаге.

Проблема с этим алгоритмом состоит в том, что на обучающей выборке он показывает очень хороший результат, но при попытке прогнозирования за пределы обучающей выборки качестве прогнозов становится плохим. Существует несколько подходов, как победить эту проблему. Один из подходов — укорачивание дерева после его построения. Другой подход — случайный лес.

Как посадить одно дерево для количественной переменной?

Дерево можно также строить для непрерывной зависимой переменной. Отличий немного:

• вместо индекса Джини или энтропии считается просто сумма квадратов остатков
• для каждого терминального узла прогнозируется не класс, которому принадлежит \( y \), а само значение \( y \)
• для непрерывной переменной \( y \) ветвление дерева прекращается, если в терминальном узле оказывается 5 наблюдений и меньше

Случайный лес

Допустим в общей выборке всего \( n \) наблюдений. Случайный лес строит ntree=500 деревьев. Для каждого дерева:

• Случайным образом с повторениями выбирается \( n \) наблюдений из \( n \) исходных. Поскольку наблюдения выбираются с повторениями, то при построении каждого конкретного дерева часть наблюдений не будет использоваться, а часть наблюдений будет использоваться несколько раз.
• При делении каждой веточки на две случайным образом выбирается mtry=3 регрессора из множества всех регрессоров, а уже затем из них выбирается переменная, использование которой даёт наибольшее падение индекса Джини.

Есть много вариаций алгоритма, можно менять ntree, mtry, брать для каждого дерева случайную выборку с повторениями или без. В R по умолчанию берется ntree равное 500 и mtry равное корню из количества регрессоров.

R

Загружаем данные:

h <- read.table("~/em301/datasets/flats_moscow.txt", header = TRUE)

Сажаем случайный лес. Тут важно, что есть два алгоритма — случайный лес для качественной переменной и случайный лес для количественной переменной. R сам определит, какой использовать, если правильно указать тип записимой переменной, numeric или factor.

str(h$brick)

##  int [1:2040] 1 0 1 0 1 1 0 1 1 0 ...

h$brick <- as.factor(h$brick)
str(h$brick)

##  Factor w/ 2 levels "0","1": 2 1 2 1 2 2 1 2 2 1 ...

model <- randomForest(brick ~ price + totsp + kitsp + dist, data = h)

Строим прогнозы вероятностей

new.data <- data.frame(price = 100, totsp = 60, kitsp = 10, dist = 13)
predict(model, new.data, type = "prob")

##       0     1
## 1 0.964 0.036
## attr(,"class")
## [1] "matrix" "votes"

Меры важности

Волков бояться — в лес не ходить!

Посмотрим на первое дерево в лесу:

tree1 <- getTree(model, 1, labelVar = TRUE)
head(tree1)

##   left daughter right daughter split var split point status prediction
## 1             2              3     totsp       85.50      1       <NA>
## 2             4              5     price      155.50      1       <NA>
## 3             6              7     totsp       87.50      1       <NA>
## 4             8              9      dist       11.75      1       <NA>
## 5            10             11      dist       10.25      1       <NA>
## 6            12             13      dist        9.75      1       <NA>

Здесь split var — это переменная по которой происходит разделение, split point — значение с которым сравнивается разделяющая переменная. Для нетерминальных (status=1) узлов указываются левый и правый узлы за данным, left daughter и right daughter. Для терминальных (status=-1) узлов указывается прогноз, prediction.

Даже на одном дереве не очень-то понятно, что происходит, а уж на 500 деревьях и подавно!

Чем дальше в лес, тем толще партизаны!

Алгоритм случайного леса хорошо прогнозирует, но не дает какой-то простой наглядной формулы модели. Чтобы как-то описать, что происходит внутри леса придумали меры важности регрессоров.

Переоценим нашу модель заново, теперь попросим R посчитать меры важности регрессоров:

model <- randomForest(brick ~ price + totsp + kitsp + dist, data = h, importance = TRUE)

• Среднее падение индекса Джини. Рассмотрим первое дерево. При каждом ветвлении на дереве падает индекс Джини. Для каждой переменной можно посчитать суммарное падение индекса Джини, вызванное ветвлениями на базе этой переменной. Посчитав среднее падение Джини по всем деревьям получим меру важности.

importance(model)

##           0     1 MeanDecreaseAccuracy MeanDecreaseGini
## price 53.62 21.43                67.78            258.4
## totsp 57.09 15.63                71.05            219.6
## kitsp 60.77 27.65                74.28            126.0
## dist  64.32 60.86                87.07            252.7

Меры близости

Для небольших наборов данных можно посчитать меры близости, т.е. насколько каждые два наблюдения близки между собой.