CatBoost

📖 이번 포스팅에서는 Boosting 계열의 알고리즘 중에서 GBM(Gradient Boosting Machines) 알고리즘에 기반하여 만들어진 CatBoost 알고리즘에 대해 알아보려고 합니다.
CatBoost는 2017년 논문에서 소개되었으며 현재까지 현업에서도 활발하게 사용되고 있다고 합니다. CatBoost에 대한 개념들을 살펴봅시다.

[CatBoost란?]

• GBM의 치명적인 문제점 중 하나로 과적합 문제가 존재합니다. 이 과적합 문제를 해결하면서 동시에 기존 GBM계열의 알고리즘인 XGBoost, LightGBM 알고리즘보다 학습 속도를 개선하는 장점을 앞세워 개발되었습니다.

  • GBM은 최초의 데이터를 학습할 때만 예측값을 기반으로 하고 그 이후의 데이터를 학습할 때는 예측값을 활용해서 계산한 잔차에만 포커스를 맞추어서 학습하게 됩니다.
  • 하지만 이렇게 잔차에만 포커스를 맞추어 학습하는 것이 매우 이상적이라고 보일지도 모르겠지만 모델이 본적 없는 데이터에는 예측을 잘 하지 못하는 과적합(Overfitting) 문제를 유발할 가능성이 매우 높다는 것이 치명적인 단점입니다.

• 범주형 변수의 예측모델에 최적화된 모델입니다.

• 기존의 그래디언트 부스팅 알고리즘을 조작하여 타겟 누수(target leakage)를 개선합니다.

  • target leakage는 예측 시점에서 사용할 수 없는 데이터가 데이터셋에 포함되는 오류를 말합니다.
  • 즉, 모델이 독립변수들인 x만을 활용하여 종속변수인 y를 예측해야 하는데, y에 대한 정보가 x에 포함되어 있는 경우를 말합니다.
  • 기존의 그래디언트 부스팅 방법들은 손실함수를 target value에 대해 편미분한 그래디언트 값을 활용하기에 좋은 아이디어 같지만, target value를 활용하여 생기는 target leakage로 인해 training/test 데이터 셋의 output의 분포에 차이가 생기게 되고 오버피팅을 발생시킵니다.
  • 즉, 다음 스텝의 트리를 만들 때, 이전에 사용했던 데이터를 다시 재사용하여 과적합이 쉽게 되었습니다.

• XGBoost, LightGBM이 Hyper-parameter에 따라 성능이 달라지는 민감한 문제를 해결하는 것에도 초점을 맞추었습니다.

[CatBoost의 특징]

1. Level-wise Tree

• LightGBM은 DFS(깊이 우선 탐색)처럼 트리를 우선적으로 깊게 형성하는 방식을 취하며, XGBoost는 BFS(너비 우선 탐색)처럼 우선적으로 넓게 트리를 형성하게 됩니다. CatBoost도 XGBoost처럼 BFS 방식 즉, level-wise 방식으로 트리를 형성하나 Feature를 모두 동일하게 대칭적인 트리 구조로 형성하게 됩니다. 이런 방식을 통해 예측 시간을 감소시키게 됩니다.

2. Ordered Boosting

• CatBoost는 기존의 부스팅 과정과 전체적인 양상은 비슷하되, 조금 다릅니다.

• 기존의 부스팅 모델이 일괄적으로 모든 훈련 데이터를 대상으로 잔차계산을 했다면, CatBoost는 일부 데이터만을 가지고 잔차계산을 한 뒤, 모델을 만들어 나머지 데이터의 잔차는 이 모델로 예측한 값을 사용합니다.

예시

• 데이터 세트에 10개의 데이터가 있고 아래와 같이 시간 순서가 지정되어 있다고 가정해 보겠습니다.

• 데이터에 시간이 없으면 CatBoost는 각 데이터 포인트에 대해 인공 시간을 무작위로 생성합니다.

1. 먼저 x1의 잔차만 계산하고, 이를 기반으로 모델을 생성합니다. 이 후, x2의 잔차를 이 모델로 예측합니다.
2. x1, x2의 잔차를 가지고 모델을 만듭니다. 이를 기반으로 x3, x4의 잔차를 모델로 예측합니다.
3. x1, x2, x3, x4를 가지고 모델을 만듭니다. 이를 기반으로, x5, x6, x7, x8의 잔차를 모델로 예측합니다.
4. 위 과정을 반복합니다.

• 이 방법은 target이 아닌 관측된 기록에만 의존하기에 target leakage를 막을 수 있습니다.

3. Random Permutation

두 번째 데이터의 잔차(r(x5,y5))를 통해서 두 번째 데이터가 포함된 모델 M2로 업데이트하고 이 모델을 이용해서 세번째 데이터(x9)의 분류값을 예측하고 그 잔차를 구하는 과정.

• Ordered Boosting을 할 때, 데이터 순서를 섞어주지 않으면 매 번 같은 순서대로 잔차를 예측하는 모델을 만들 가능성이 있습니다. 이 순서는 사실 임의로 정한 것임으로 순서 역시 매 번 섞어줘야 합니다.

• CatBoost는 이러한 것 역시 감안해서 데이터를 셔플링하여 뽑아냅니다. 뽑아낼 때도 모든 데이터를 뽑는게 아니라, 그 중 일부만 가져오게 할 수 있습니다. 이 모든 기법이 모두 오버피팅 방지를 위해 트리를 다각적으로 만들려는 시도입니다.

• 또한 K-fold Cross Validation처럼 주어진 전체 데이터를 임의적으로 N개의 Fold로 나누어서 각 Fold에 속한 데이터셋들에 Ordered Boosting을 적용할 수 있습니다.

4. Ordered Target Encoding

• Target Encoding, Mean Encoding, Response Encoding 이라고 불리우는 기법 (3개 다 같은 말)을 사용합니다.

예시

• 위 데이터에서 time, feature1으로 class_label을 예측해야한다고 가정해봅시다. feature1의 cloudy는 다음과 같이 인코딩 할 수 있습니다.

cloudy = (15 +14 +20 + 25)/4 = 18.5

• 즉, cloudy를 cloudy에 해당하는 데이터들의 class_label의 값의 평균으로 인코딩 하는 것입니다. 이 때문에 Mean encoding이라고 불리기도 합니다.

• 그런데 위는 우리가 예측해야하는 값이 훈련 셋 피처에 들어가버리는 문제, 즉 target leakage 문제를 일으킵니다. 이는 오버피팅을 일으키는 주 원인이자, Mean encoding 방법 자체의 문제이기도 합니다.

• 그래서, Catboost는 이에 대한 해결책으로, 현재 데이터의 인코딩을 하기 위해 아래처럼 이전 데이터들의 인코딩된 값을 사용합니다.

- Friday 에는, cloudy = (15+14)/2 
## (tues + wed) / 2
- Saturday 에는, cloudy = (15+14+20)/3 = 16.3 로 인코딩 된다.
## (tues + wed + fri) / 3

Tues의 경우 Ordered Target Encoding을 적용하면 어떻게 될까요? 원래대로라면 0을 넣어야 합니다.(과거의 데이터가 0개이기 때문!) 하지만 이 경우 Laplace Smoothing 이라는 방법을 사용합니다.

• 즉, 현재 데이터의 target value를 사용하지 않고, 이전 데이터들의 target value만을 사용하다보니, target leakage가 일어나지 않는 것입니다.

• 범주형 변수를 수로 인코딩하는 할 때, 오버피팅도 막고 수치값의 다양성도 만들어 주는 참 영리한 기법이 아닐 수 없습니다.

5. Categorical Feauture Combinations

• 데이터셋의 클래스를 명확하게 구분할 수 있는 중복되는 범주형 변수가 2개 이상 존재할 때, 이를 하나의 변수로 통합해 처리하는 것을 자동으로 수행합니다.

예시

• country변수만 봐도 hair_color 변수가 결정되기 때문에, class_label을 예측하는데 있어, 두 변수 모두 필요없이 이 중 하나의 변수만 있어도 됩니다. CatBoost는 이렇게 information gain이 동일한 두 변수를 하나의 변수로 묶어버립니다. 이렇게 함으로써 변수가 늘어나는 문제를 예방하여 연산 비용을 줄일 수 있습니다.

6. One-hot Encoding

• 사실 범주형 변수를 항상 Target Encoding하는 것이 아닙니다.

• CatBoost는 낮은 Cardinality를 가지는 범주형 변수에 한해서, 기본적으로 Onr-hot Encoding을 시행합니다.

• 아무래도 Low Cardinality 를 가지는 범주형 변수의 경우 Target Encoding 보다 One-hot 이 더 효율적이라 그런 듯 합니다.

• Python에서 CatBoost로 모델을 생성할 때, Hyper-parameter로서 one_hot_max_size = N라는 값을 따로 설정해주면 범주형 변수들 중 값의 level 개수가 N개수보다 작다면 해당 범주형 변수를 자동으로 One-Hot Encoding으로 처리해줍니다.

7. 수치형 변수 처리

• 일반 Tree-based 알고리즘 처럼 Information Gain을 활용해서 최적의 Split 기준을 계산하게 됩니다.

8. Optimized Parameter tuning

• Catboost 는 기본 파라미터가 기본적으로 최적화가 잘 되어있어서, 파라미터 튜닝에 크게 신경쓰지 않아도 됩니다. (반면 XGBoost나 LightGBM은 파라미터 튜닝에 매우 민감)

• 사실 대부분 부스팅 모델들이 파라미터 튜닝하는 이유는, 트리의 다형성과 오버피팅 문제를 해결하기 위함인데, CatBoost는 이를 내부적인 알고리즘으로 해결하고 있으니, 굳이 파라미터 튜닝할 필요가 없는 것입니다.

• 굳이 한다면 learning_rate, random_strength, L2_regulariser과 같은 파라미터 튜닝인데, 결과는 큰 차이가 없다고 합니다.

[Catboost의 장단점]

1. 장점

• 다른 GBM에 비해 overfitting이 적다.

• 범주형 변수에 대해 특정 인코딩 방식으로 인하여 모델의 정확도와 속도가 높습니다.

• One-hot Encoding, Label Encoding 등 encoding 작업을 하지 않고도 그대로 모델의 input으로 사용할 수 있습니다.

2. 단점

• missing data를 처리해주지 않습니다.

• Sparse Matrix 즉, 결측치가 매우 많은 데이터셋에는 부적합한 모델입니다.

  • 예를 들어, 추천시스템에 자주 사용되는 사용자-아이템 행렬 데이터를 살펴보면 보통 Sparse한 형태로 이루어져 있습니다. 만약 이러한 데이터를 활용하려면 Sparse한 특성이 없도록 Embedding을 적용한다던지 등 데이터를 변형한 후 CatBoost에 활용하는 것이 적합할 것입니다.

• 데이터 대부분이 수치형 변수인 경우, LightGBM보다 학습 속도가 느립니다. (즉 대부분이 범주형 변수인 경우 사용)

[실습]

> # [사전 작업]
> #install.packages('devtools')
> library(devtools)
> devtools::install_url('https://github.com/catboost/catboost/releases/download/v0.20/catboost-R-Windows-0.20.tgz', INSTALL_opts = c("--no-multiarch", "--no-test-load"))
> library(catboost)
> library(caret)


> credit <- read.csv('D:\\ADP\\credit_final.csv')
> class(credit$credit.rating) 
> credit$credit.rating <- as.factor(credit$credit.rating)
> levels(credit$credit.rating) <- c("pos", "neg")
> class(credit$credit.rating)


> credit$foreign.worker <- as.factor(credit$foreign.worker)
> credit$telephone <- as.factor(credit$telephone)
> credit$other.credits <- as.factor(credit$other.credits)
> credit$bank.credits <- as.factor(credit$bank.credits)
> credit$account.balance <- as.factor(credit$account.balance)

# [데이터 분할]
> idx <- createDataPartition(y = credit$credit.rating,
+                            time = 1, p = 0.7, list = FALSE)
> train <- credit[idx,]
> test <- credit[-idx,]
> table(train$credit.rating)

pos neg 
210 490 


> # [train set 업샘플링]
> train <- upSample(subset(train, select = -credit.rating), train$credit.rating)
> train <- train %>% rename('credit.rating' = 'Class')
> table(train$credit.rating)

pos neg 
490 490 

> # [k-fold 생성 및 랜덤 그리드서치 설정]
> cv_folds <- createMultiFolds(train$credit.rating, k = 3, times = 3)
> fit_ctrl <- trainControl(method = "repeatedcv", 
+                          number = 3,
+                          repeats = 3,
+                          index = cv_folds,
+                          search = 'random',
+                          verboseIter = TRUE)

> # [모델 학습]
> train_x <- subset(train, select = c(-credit.rating))
> train_y <- train$credit.rating
> catboost_model <- train(x = train_x, y = train_y,
+                      method = catboost.caret,
+                      metric = 'Accuracy',
+                      preProcess = c("zv", "center", "scale", "spatialSign"),
+                      #tuneGrid = grid,
+                      trControl = fit_ctrl,
+                      maximize = TRUE,
+                      tuneLength = 10)
...
92:	learn: 0.0003169	total: 430ms	remaining: 32.4ms
93:	learn: 0.0003046	total: 439ms	remaining: 28ms
94:	learn: 0.0002871	total: 449ms	remaining: 23.6ms
95:	learn: 0.0002675	total: 455ms	remaining: 19ms
96:	learn: 0.0002578	total: 461ms	remaining: 14.3ms
97:	learn: 0.0002528	total: 466ms	remaining: 9.51ms
98:	learn: 0.0002379	total: 470ms	remaining: 4.75ms
99:	learn: 0.0002233	total: 476ms	remaining: 0us

> # [최적 모델 확인]
> catboost_model
Catboost 

980 samples
 20 predictor
  2 classes: 'pos', 'neg' 

Pre-processing: centered (15), scaled (15), spatial sign
 transformation (15), ignore (5) 
Resampling: Cross-Validated (3 fold, repeated 3 times) 
Summary of sample sizes: 654, 652, 654, 654, 654, 652, ... 
Resampling results across tuning parameters:

  depth  learning_rate  l2_leaf_reg  rsm  border_count  Accuracy 
  2      0.1158270      1e-06        0.8  168           0.7721021
  2      0.3318660      1e-06        0.8   88           0.7881399
  2      0.7353266      1e-06        0.8  252           0.8054600
  4      0.0971376      1e-06        0.9   79           0.8173620
  5      0.4965535      1e-06        0.7  214           0.8064741
  5      0.6898669      1e-06        0.7  186           0.7969703
  8      0.1959387      1e-01        1.0   39           0.8418541
  8      0.4183411      1e-01        0.8  151           0.8238254
  9      0.5728624      1e-06        0.8   59           0.8139413
  9      0.7598337      1e-06        0.7  143           0.8115949
  Kappa    
  0.5442042
  0.5762798
  0.6109199
  0.6347241
  0.6129483
  0.5939407
  0.6837082
  0.6476508
  0.6278825
  0.6231899

Tuning parameter 'iterations' was held constant at a value of 100
Accuracy was used to select the optimal model using the largest value.
The final values used for the model were depth = 8, learning_rate
 = 0.1959387, iterations = 100, l2_leaf_reg = 0.1, rsm = 1
 and border_count = 39.

> catboost_model$bestTune
  depth learning_rate iterations l2_leaf_reg rsm border_count
7     8     0.1959387        100         0.1   1           39
> ## border_count : 수치형 변수 분할 수
> ## rsm : 변수가 무작위로 다시 선택될 때 각 분할 선택에서 사용할 변수의 백분율


> # [변수 중요도 확인]
> plot(varImp(catboost_model))


> # [예측값에 대한 혼돈행렬]
> confusionMatrix(test$credit.rating, predict(catboost_model, test, type = 'raw'))
Confusion Matrix and Statistics

          Reference
Prediction pos neg
       pos  44  46
       neg  24 186
                                          
               Accuracy : 0.7667          
                 95% CI : (0.7146, 0.8134)
    No Information Rate : 0.7733          
    P-Value [Acc > NIR] : 0.63898         
                                          
                  Kappa : 0.4027          
                                          
 Mcnemar's Test P-Value : 0.01207         
                                          
            Sensitivity : 0.6471          
            Specificity : 0.8017          
         Pos Pred Value : 0.4889          
         Neg Pred Value : 0.8857          
             Prevalence : 0.2267          
         Detection Rate : 0.1467          
   Detection Prevalence : 0.3000          
      Balanced Accuracy : 0.7244          
                                          
       'Positive' Class : pos