Impurity Index

분류 문제에서 tree는 impurity index를 줄이는 방향으로 가지(branch)를 성장 시킨다. 선택된 어떤 분할 기준이 impurity 줄인다면(개선) 그 분할은 모형에 필요하다. impurity를 줄이지 못한다면 가지가 더 뻗어갈 이유가 없다. tree는 impurity를 더 줄일 수 없거나 다른 threshold(terminal node의 샘플 수, complexity parameter 등..)를 충족했을 때 성장을 멈춘다. 다음은 tree 기반 모형에서 사용하는 impurity index중 gini에 대한 사례이다.

\(Gini = 1 - \Sigma^{c}_{j=1}p^{2}_{j}, \;\; p_j는 \,\, j번째 \,\, 범주에 \,\, 속할 \,\, 비율\) 


impurity <- function (x, type = c("gini", "deviance")) {
    type <- match.arg(type)
    tab <- table(x)
    p_tab <- prop.table(tab)
    if (type == "deviance") {
        p_tab[p_tab == 0] <- 1
        result <- -2 * sum(p_tab * log(p_tab))
    }
    else if (type == "gini") {
        result <- 1 - sum(p_tab^2)
    }
    return(result)
}
impurity(c(rep('pass', 50), rep('fail', 50)), 'gini')
## [1] 0.5
impurity(c(rep('pass', 10), rep('fail', 40)), 'gini')
## [1] 0.32
impurity(c(rep('pass', 5), rep('fail', 45)), 'gini')
## [1] 0.18


Variable Importance

개별 tree에서 분할에 사용된 변수는 해당 모형에서 중요한 변수라 할 수 있다. 서로 독립인 여러개의 tree의 다수결 투표를 통해 예측을 하는 random forest 모형은 이와 같은 방식으로 변수 중요도를 계산한다. tree 기반 ensemble 방법에서 사용하는 다소 원시적인 variable importance 측정 방법으로 ensemble의 모든 개별 tree에서 각 변수가 선택될 횟수를 집계하는 방법이 있다. 각 변수에 의해 생성된 분할 기준의 개선 정도를 개별 tree에서 수집한 후 평균을 내는 보다 정교한 방법도 있다. random forest에서 쓸 수 있는 가장 진보된 variable importance 측정은 perumtation 정확도 기반 측정이다.


Permutation Importance

n개의 표본과 p개의 예측 변수가 있다고 하자. 개별 tree가 끝까지 성장한 후 oob(out of bagging) 표본으로 예측 정확도를 기록한다. 그런 다음 oob 표본에서 p번째 변수의 값이 랜덤하게 permutation(무작위화) 되고 정학도가 다시 계산된다. 만약 p번째 변수가 정확도에 중요한 영향을 미치는 변수였다면 permutation의 결과로 정확도가 크게 감소하였을 것이다. 반대로 p번째 변수가 정확도에 크게 기여하지 않는 변수였다면 permutation의 결과로 정확도가 크게 변하지 않았을 것이다. 이러한 정확도의 증감을 모든 tree에 걸쳐 기록하여 random forest의 p번째 변수의 중요성을 측정하는 척도로 사용할 수 있다.


R의 randomForest 패키지에서 기본으로 제공하는 importance는 permutation이 아닌 impurity의 개선 정도로 계산한 importance이다. 이는 permutation importance보다 훨씬 빠르게 계산할 수 있지만 permutation importance와 항상 일치하지는 않는다. 경우에 따라 정확도에 전혀 영향을 주지 않는 변수가 높은 importance 값을 가질 수 있다. 이런 경우 반드시 permutation importance도 확인을 하는것이 좋다.

데이터는 여기에서 받을 수 있다.

head(dat)
##    bathrooms bedrooms price longitude latitude interest_level
## 1:       1.5        3  3000  -73.9425  40.7145              2
## 2:       1.0        2  5465  -73.9667  40.7947              1
## 3:       1.0        1  2850  -74.0018  40.7388              3
## 4:       1.0        1  3275  -73.9677  40.7539              1
## 5:       1.0        4  3350  -73.9493  40.8241              1
## 6:       2.0        4  7995  -74.0028  40.7429              2




Impurity Importance Code

library(randomForest)
library(ggplot2)
# random normal noise
dat$noise <- rnorm(nrow(dat))

# random forest model
rf_fit <- randomForest(interest_level ~ . -noise, dat)
rf_fit_noise <- randomForest(interest_level ~ ., dat)

# barplot
df1 <- data.frame(
  var = rownames(rf_fit$importance), imp = c(rf_fit$importance)
)
df1$data_type <- 'normal'

df2 <- data.frame(
  var = rownames(rf_fit_noise$importance), imp = c(rf_fit_noise$importance)
)
df2$data_type <- 'add random noise'

df <- rbind(df1, df2)
df$col <- df$var == 'noise'

ggplot(df) + 
  geom_bar(aes(x=reorder(var, df$imp), y=imp, fill=col), stat = 'identity') + 
  facet_grid(~ data_type) + guides(fill=F) + 
  scale_fill_manual(values = c('grey45', 'deeppink4')) +
  xlab('variables')

우측 그림은 랜덤 난수를 추가한 모형의 variable importance이고 좌측은 랜덤 난수를 추가하지 않은 importance이다. \(y\)와 전혀 관계가 없고 \(N(0,1)\)의 분포를 따르는 말 그대로 랜덤인 값인데 importance가 높게 나오는것을 볼 수 있다.


Permutation Importance Code

# random forest model
rf_fit_perm <- randomForest(interest_level ~ ., dat, importance = T)

df <- data.frame(
  var = rownames(rf_fit_perm$importance), 
  imp = c(rf_fit_perm$importance[,'MeanDecreaseAccuracy'])
)
df$col <- df$var == 'noise'

rf_fit_perm$importance
##                      1            2            3 MeanDecreaseAccuracy
## bathrooms 0.0150858406  0.007824298  0.002179814         0.0124295270
## bedrooms  0.0896639391  0.047846538 -0.004037131         0.0728591244
## price     0.1232590566  0.071777160  0.100437618         0.1097652385
## longitude 0.0654075797  0.015916629  0.012494954         0.0500300962
## latitude  0.0646234885  0.011398886  0.001811521         0.0476277676
## noise     0.0001272259 -0.000935131 -0.000242909        -0.0001429992
##           MeanDecreaseGini
## bathrooms         349.8986
## bedrooms          990.7359
## price            4519.8326
## longitude        3663.4755
## latitude         3715.8647
## noise            4422.9464
# barplot
ggplot(df) + 
  geom_bar(aes(x=reorder(var, df$imp), y=imp, fill=col), stat = 'identity') + 
  guides(fill=F) + 
  scale_fill_manual(values = c('grey45', 'deeppink4')) +
  xlab('variables')

randomForest 패키지를 사용할 때, importance 옵션을 ’TRUE’로 주면 permutation importance(MeanDecreaseAccuracy)가 같이 계산된다. permutation 과정이 필요하기 때문에 속도가 좀 느릴 수 있다. random noise는 정확도에 전혀 영향을 주지 못하기 때문에 importance 역시 매우 낮은 것을 확인 할 수 있다.


ranger Package

library(ranger)
# random forest model
rf_imp <- ranger(interest_level ~ ., dat, importance = 'impurity')
rf_perm <- ranger(interest_level ~ ., dat, importance = 'permutation')

# barplot
df1 <- data.frame(
  var = names(rf_imp$variable.importance), imp = c(rf_imp$variable.importance)
)
df1$data_type <- 'impurity'

df2 <- data.frame(
  var = names(rf_perm$variable.importance), imp = c(rf_perm$variable.importance)
)
df2$data_type <- 'permutation'
df <- rbind(df1, df2)
df$col <- df$var == 'noise'

ggplot(df) + 
  geom_bar(aes(x=reorder(var, imp), y=imp, fill=col), stat = 'identity') + 
  guides(fill=F) + xlab('variables') +
  scale_fill_manual(values = c('grey45', 'deeppink4')) +
  facet_wrap(~ data_type, scales = 'free')

ranger 패키지는 random forest 모형을 제공하는 패키지인데 randomForest 패키지보다 속도가 빠르다. ’permutation’이라는 옵션으로 permutation importance를 계산할 수 있다.