[머신러닝] 원핫인코딩이 트리 기반 모델의 성능을 저하시키는 이유

본 포스팅은 범주형 독립변수가 있을 때 원핫인코딩이 트리 기반 모델의 성능에 어떠한 악영향을 미치는지에 대한 칼럼을 번역한 글입니다. 현재 많이 사용하는 Scikit-learn 라이브러리에서 제공하는 트리 기반 모델을 사용할 때는 범주형 변수를 반드시 원핫인코딩 해줘야 합니다. 하지만 원핫인코딩은 트리 기반 모델의 성능을 저하시킵니다. 이에 대한 실험 내용을 잘 정리한 칼럼을 번역하여 소개합니다. 원본 포스팅은 아래 링크를 통해 확인할 수 있습니다.
  

---

 

Are categorical variables getting lost in your random forests?

https://deepnote.com/workspace/first-deepnote-workspace-0bca-0bbbab26-2537-4dc3-adb1-69bd73347824/project/roamresearch-0609a6ac-6ab3-46be-9407-9f21380bcb1f/notebook/BlogPosts%2FCategorical_variables_in_tree_models%2Fcategorical_variables_post-182bb02f3c474c4c89d35d3042d8da49

Deepnote

 
 

의사결정 트리 모델은 원핫 인코딩 없이 범주형 변수를 처리할 수 있습니다. 그러나 많이 사용하는 라이브러리들은 원핫 인코딩 없이는 의사 결정 트리(및 랜덤 포레스트)에서 범주형 변수를 처리할 수 없도록 구현되어 있습니다. 그러나 이번 실험을 통해 우리는 원핫 인코딩이 트리 모델 성능을 심각하게 저하시킬 수 있음을 알게 되었습니다. 본 포스팅에서는 H2O와 Scikit-learn을 비교하여 원핫인코딩 적용 여부에 따른 성능이 어떻게 달라지는지 그 실험결과를 공유하겠습니다.
 
 

---

 

Unnecessary one-hot encoding

많은 실제 데이터셋에는 연속형과 범주형 변수가 혼합되어 있습니다. 의사 결정 트리 모델과 그 앙상블 모델인 랜덤 포레스트의 주요 장점은 연속 변수와 범주형 변수 모두에서 직접 작동할 수 있다는 것입니다. 반면에, 대부분의 다른 인기 모델(예: 일반화된 선형 모델, 신경망)은 범주형 변수를 일부 수치 아날로그로 변환해야 하며, 일반적으로 원핫 인코딩을 통해 원래 변수의 각 범주에 대한 더미 변수를 생성하여 사용합니다.
 
원핫 인코딩은 Feature 수를 크게 증가시킬 수 있습니다 (차원의 저주). 예를 들어, 미국의 주를 원핫 인코딩하면 49개의 차원이 추가될 것입니다 (미국의 주는 총 50개). 또한 원핫 인코딩은 단일 피쳐를 여러 개의 개별 피쳐로 분할함으로써 데이터셋 안에 내재된 중요한 정보를 지울 수 있습니다.
 
또한, 원핫 인코딩은 트리 기반 모델에 아래와 같은 두 가지 문제를 야기합니다.
 
1. Sparsity를 발생시킴으로써 연속형 변수에 더 높은 피쳐 중요도가 할당되도록 합니다.
2. 트리 생성 중 초기에 분할하도록 하려면, 범주형 변수의 각 범주가 매우 높은 기준을 충족해야 합니다. 이로 인해 예측 성능이 저하될 수 있습니다. (무슨 말이지? -> 마저 읽으면 대충 이해가 됨)
 
이 포스팅에서는 원핫 인코딩을 전제로 하는 scikit-learn과 그렇지 않은 H2O 사이의 비교를 통해 이 두 가지 문제점에 대해 입증합니다. 우리는 독립변수(Feature)와 종속변수(Target) 간에 연관성이 있는 가공데이터셋(Artificial Dataset)을 구성하고, 두 라이브러리에서 제공하는 모델의 학습 결과를 바탕으로 이러한 문제가 어떻게 발생하는지 설명할 것입니다. 본 포스팅에 언급하는 모든 코드는 아래 링크에서 모두 사용가능합니다.
https://github.com/roamanalytics/roamresearch/blob/master/BlogPosts/Categorical_variables_in_tree_models/tree_categorical_variables.py

GitHub - roamanalytics/roamresearch

 

from tree_categorical_variables import *

 

---

 

Artificial dataset

가공데이터셋 생성을 위해, 우리는 C+ 또는 C-의 값을 취하는 범주형 변수 c와 정규 분포를 따르는 연속 변수 z를 정의하였다. 이를 수식으로 쓰면 아래와 같다. 범주형 변수 c는 총 200개의 범주를 가지고 있는데, 그중 C+는 y=1인 범주들 100 집합을 의미하고, C-는 y=0인 범주 100개 집합을 의미한다. 변수 c의 범주들에는 'Aau, Abc, Acm, Bcj, Bal, Bdm, .... '이 있습니다. 

 

 
의도적으로 범주 값이 A로 시작하면 1, 그렇지 않으면 0이 되도록 만들었습니다. 즉, 변수 c가 Aau, Abc, Acm 등인 경우에는 반드시 y=1, 반면에 Bcj, Bal, Bdm 등이면 y=0 입니다. 또는 변수c가 C-이더라도, z가 10을 초과하는 경우에는 y가 1이 됩니다. 즉, 가공데이터에서 y를 잘 맞추기 위해서는 사실상 c와 z변수만 있으면 됩니다. 하지만 모델이 헷갈리도록 하기 위해 우리는 y와 약한 상관관계를 가지는 연속형 변수 100개를 더 추가했습니다. 그리고 전체 샘플 수는 10,000개입니다. 최종적으로 생성된 데이터셋은 아래와 같습니다.
 

data_categorical, data_onehot = generate_dataset(
    num_x=100, n_samples=10000, n_levels=200)

 

• y: 타겟변수
• c: 범주형 변수
• z: 정규분포를 따르는 연속형 변수
• x0 ~ x99: y와 약한 상관관계를 가지는 연속형 변수

 

data_categorical.head(10).round(3)

 

앞서 말했듯이, 변수 c가 A로 시작하거나, z > 10인 경우 y=1 입니다. 그러므로 의사 결정 나무는 다음 다이어그램의 왼쪽에 표시된 것처럼 'c'에서 먼저 분할한 다음 'z'에서 분할하여 타겟 변수 y를 완벽하게 예측할 수 있어야 합니다. 왼쪽의 의사결정나무에서 'xi' 변수는 전혀 기여하지 않습니다. 즉, xi들의 노이즈가 전혀 방해되지 않습니다. 그러나 오른쪽 의사결정나무에서는 'xi'가 너무 일찍 선택되었습니다. 개별적으로는 xi feature들이 유용할 수 있지만, 순수도(purity)를 보장하지 않으므로 xi를 너무 일찍 선택하면 순수하지 않은 (impure) 가지가 남게 됩니다. (불필요하게 가지를 더 치게 된다는 뜻) 그러므로 좋은 의사결정나무는 중요한 변수가 초기에 선택되어 가지가 분할될 수 있어야 합니다.
 

from IPython.display import SVG, display

display(SVG("fig/Decision tree visualization.svg"))

 

---

 

Artificial data bake-off

먼저 단순하게 하기 위해 하나의 의사 결정 나무에 초점을 맞춘 다음 결과를 랜덤 포레스트로 확장합니다. 우리는 두 가지 종류의 분석을 수행합니다.
 

1. 범주형 변수 'c'를 포함하지 않는 기준 모형
2. 'c'를 포함하는 모형

이를 통해 예측 문제에 대한 'c'의 영향력을 직관적으로 정량화할 수 있습니다. 각 실험에 대해 트리를 10번 훈련하고 평가하여 결과를 평균화합니다.
 

---

 

Scikit-learn's DecisionTreeClassifier (One-hot Encoding only)

Scikit-learn은 원핫 인코딩 버전만 처리할 수 있습니다. 다음은 'c'가 없는 기준 모델에 대한 평가결과입니다. 

results_no_c = evaluate_sklearn_model(
	data_onehot, 
    feature_names=get_feature_names(data_onehot, include_c=False),
    target_col='y',
    model=DecisionTreeClassifier())

print_auc_mean_std(results_no_c)

AUC: mean 0.7409, sd 0.0073

 

평가지표는 AUC 최대 값은 1.0(완벽한 분류)입니다. 0.73 점수는 훌륭하지만 완벽과는 거리가 멉니다. 이제 'c'를 다시 추가하겠습니다:

results_with_c = evaluate_sklearn_model(
    data_onehot, 
    feature_names=get_feature_names(data_onehot, include_c=True),
    target_col='y',
    model=DecisionTreeClassifier())

print_auc_mean_std(results_with_c)

AUC: mean 0.7558, sd 0.0104

 
'c'변수 추가를 통해 AUC가 약간 개선되었지만 기대했던 완벽한 성능에는 미치지 못했습니다. 또한 'c' 기반 변수는 지니 피쳐 중요도 순위로 봤을 때 상위에 포함되지도 않았습니다. 오히려 모든 x 기반의 변수들이 모든 c 기반의 변수들보다 더 높은 중요도를 가집니다.

print_sorted_mean_importances(results_with_c)

  z: 0.341
x28: 0.037
 x9: 0.033
x24: 0.027
x71: 0.016

 

---

 

H2O's decision trees

H2O는 기본적인 의사 결정 트리가 아니라 랜덤 포레스트만 가지고 있습니다. scikit-learn과의 직접적인 비교를 용이하게 하기 위해 H2ODeicionTree라는 작은 래퍼 클래스를 작성했습니다. 이는 하나의 의사결정나무와 동일한 기능을 수행합니다. 이전과 마찬가지로 먼저 변수 c 없이 모델을 평가합니다:

h2o_results_no_c = evaluate_h2o_model(
    data_categorical, 
    feature_names=get_feature_names(data_categorical, include_c=False),
    target_col='y', 
    model=H2ODecisionTree())

print_auc_mean_std(h2o_results_no_c)

AUC: mean 0.7326, sd 0.0075

 
범주형 변수 c가 없으면 scikit-learn의 성능과 매우 유사합니다. 그러나 H2O가 c를 활용할 수 있을 때 거의 완벽한 AUC를 달성합니다:

h2o_results_with_c = evaluate_h2o_model(
    data_categorical, 
    feature_names=get_feature_names(data_categorical, include_c=True),
    target_col='y',
    model=H2ODecisionTree())

print_auc_mean_std(h2o_results_with_c)

AUC: mean 0.9990, sd 0.0007

 
scikit-learn 모델과 매우 대조적으로, 변수 c는 피쳐 중요도에서도 가장 높은 위치를 차지합니다. (우리가 데이터 생성 시에 의도했던대로)  

print_sorted_mean_importances(h2o_results_with_c)

  c: 0.701
  z: 0.299
x53: 0.000
x88: 0.000
x36: 0.000

 
마지막으로 H2O에 원핫 인코딩을 한 데이터를 사용하면 어떻게 되는지 살펴보겠습니다:

h2o_results_with_c_onehot = evaluate_h2o_model(
    data_onehot, 
    feature_names=get_feature_names(data_onehot, include_c=True), 
    target_col='y', 
    model=H2ODecisionTree())

print_auc_mean_std(h2o_results_with_c_onehot)

AUC: mean 0.7305, sd 0.0069

 
원핫 인코딩을 한 경우, H2O의 성능은 scikit-learn의 성능과 거의 같습니다.
 

---

What's the difference?

원핫인코딩으로 인한 차이의 원인을 이해하기 위해서는 나무를 만드는 알고리즘의 논리를 이해할 필요가 있습니다. 
 

The tree building algorithm

트리 생성 알고리즘에는 변수와 값을 선택하여 샘플을 두 개의 영역으로 나누는 하위 알고리즘이 있습니다. 이 분할 알고리즘은 각 변수를 차례로 고려하며, 각 변수에 대해 영역의 불순도를 최소화하는 값을 선택합니다. (여기서 우리는 알고리즘이 어떻게 계산하는지에 대해 상세하게 소개하지는 않을 것입니다.)
 
우리가 만든 가공데이터셋의 경우, 알고리즘이 z를 고려할 때는 10에서 분할하기를 희망합니다. 즉, z 값이 10보다 작은 샘플들이 한 영역에 들어가고, 값이 10보다 큰 샘플들이 다른 영역에 들어갑니다. z가 10보다 큰 샘플들은 전부 y=1이지만, z<10인 영역에 포함된 샘플들은 y=0과 y=1이 섞여 있기 때문에 더 세분화할 필요가 있습니다. 
 
이 때, 이진 변수(예. 원핫인코딩된 변수)는 다른 변수들에 비해 불리해집니다. 왜냐하면 표본을 분할하는 방법이 단 한 가지밖에 없기 때문입니다. (해당 변수 값이 0인 영역과 값이 1인 영역으로 분할하는 방법밖에 없음). 또한 범주의 수가 적은 범주형 변수도 동일한 문제를 가집니다. (분할 방법이 적기 때문) 또 다른 방법은 연속 변수가 샘플의 순서를 유도하고 알고리즘이 순서가 지정된 목록을 임의의 위치에서 분할할 수 있다는 것입니다. 이진 변수는 분할 방법이 단 한가지 밖에 없지만, 범주형 변수(범주가 q개)는 2^(q-1) - 1 개의 분할 방법이 존재합니다. 
 
**중요한 참고 사항: 이진 분류와 회귀에 대해 선형 시간 내에 최적의 분할을 찾을 수 있는 효율적인 알고리즘이 있기 때문에 실제로 모든 파티션을 검색할 필요는 없습니다. 다항 분류에는 이러한 보장이 없지만 휴리스팁 접근법이 있습니다. 
(참고 자료: The Elements of Statistical Learning (310페이지))
 

---

 

Why one-hot encoding is bad bad bad for trees

Predictive Performance

범주형 변수를 원핫 인코딩함으로써 많은 이진 변수를 생성하고, 분할 알고리즘의 관점에서 보면 모든 변수들은 모두 독립적입니다. 즉, 범주형 변수가 연속형 변수에 비해 이미 불리합니다. 하지만 또 다른 문제가 있습니다. 이 이진 변수들은 희소합니다. 우리의 범주형 변수가 100개의 범주를 가지고 있고, 각각의 범주가 다른 범주만큼 자주 나타난다고 상상해 보십시오. 알고리즘이 원핫 인코딩 변수 중 하나에서 분할하여 수행할 수 있는 가장 최선의 성능은 불순도를 1% 줄이는 것입니다. 각 더미는 샘플의 약 1%에 대해서만 나타나기 때문입니다.
 
이 결과로, 만약 우리가 범주의 수가 많은 변수를 원핫 인코딩한다면, 트리 알고리즘이 루트 노드 근처의 분할 변수로 연속 변수 대신 원핫인코딩 더미 중 하나를 선택할 가능성은 낮습니다. 우리가 만든 가공데이터와 같은 데이터셋들에는 성능이 저하될 것입니다. 반면에, 변수 c의 모든 범주를 한 번에 고려함으로써, H2O의 알고리즘은 트리의 최상위에서 범주형 변수 c를 선택할 수 있습니다. 
 
 

Interpretability

각 피쳐에 할당된 중요도 점수는 해당 피쳐가 선택된 빈도와 선택되었을 때 불순물 감소에 미치는 영향을 측정한 것입니다. (여기서는 Permutation feature importance는 고려하지 않습니다. 이는 이진 변수보다 연속 변수를 선호하는 것을 방지하는 데 도움이 될 수 있지만 원핫 인코딩으로 파생된 Sparsity 문제에는 도움이 되지 않습니다.)
 
H2O는 중요도의 약 70%를 c에 할당하고, 나머지 30%는 z에 할당합니다. 반대로 Scikit-learn은 데이터를 완벽하게 분류할 필요가 전혀 없는 변수들인 xi들에 거의 60%를 할당하며, z에 30%, 마지막으로 c의 원핫 인코딩에 총 10% 미만을 할당합니다!  
 

Fewer levels, fewer problems

우리가 논의했듯이, 이 문제는 범주의 수가 많은 변수에 특히 심각한 문제가 됩니다. 하지만 범주의 수가 적으면 원핫인코딩을 했을 때 Sparsiry가 심하지 않기 때문에 연속형 변수와 동등하게 경쟁할 가능성이 있습니다.