[ML] 의사결정나무 (Decision Tree)

본 포스팅에서는 기계 학습 (Machine learning)의 대표적인 알고리즘 중 하나인 의사결정 나무 (Decision tree) 알고리즘에 대해서 다뤄보고자 합니다.

Motivation

의사결정나무는 개념 자체는 간단한 알고리즘입니다.
하지만 이를 바탕으로 발전된 다양한 모형들은 Kaggle 등 데이터 분석대회에서 사용되고 있을 뿐 아니라, 실제 업무에서도 베이스라인 코드로 많이 사용되고 있는 편입니다.

2019년 4월, Keras library의 개발자 중 한 명인 François Chollet의 tweet에 올라온 내용입니다.
Kaggle competition 상위권 팀들의 알고리즘을 종합해본 결과, 2, 3위를 딥러닝 기반이 아닌 Gradient Boosting Decision Tree (GBDT) 기반 Ensemble 모델이 차지했습니다.

따라서 본 포스팅으로 시작되는 일련의 포스팅들에서는 Decision Tree의 기초 알고리즘부터 시작해서 XGBoost, LightBoost, CatBoost와 같은 GBDT 기반 모델들까지 정리해보고자 합니다.

---

목차

• 의사결정 나무 (Decision Tree) 기본 설명 (현재 글)
• 의사결정 나무 (Decision Tree) ID3 알고리즘
• 의사결정 나무 (Decision Tree) C4.5 알고리즘
• 의사결정 나무 (Decision Tree) CART 알고리즘
• 앙상블 (Ensemble)의 기본 개념
• 배깅 앙상블 (Bagging Ensemble): Random Forest
• 부스팅 앙상블 (Boosting Ensemble) 1: AdaBoost
• 부스팅 앙상블 (Boosting Ensemble) 2-1: Gradient Boosting for Regression
• 부스팅 앙상블 (Boosting Ensemble) 2-2: Gradient Boosting for Classification
• 부스팅 앙상블 (Boosting Ensemble) 3-1: XGBoost for Regression
• 부스팅 앙상블 (Boosting Ensemble) 3-2: XGBoost for Classification
• 부스팅 앙상블 (Boosting Ensemble) 4: LightGBM
• 부스팅 앙상블 (Boosting Ensemble) 5: CatBoost
• 부스팅 앙상블 (Boosting Ensemble) 6: NGBoost

---

의사결정트리(Decision tree)의 기본 개념

의사결정트리 (Decision Tree)는 주어진 데이터셋을 나누는 일련의 기준을 학습하는 모형입니다.
어릴 때 스무고개 놀이를 해서 정답을 맞히듯, 여러 기준들을 던져가면서 주어진 데이터의 유형을 알아내는 방법이죠.

아래와 같은 데이터가 있다고 생각해봅시다. 날씨, 온도, 습도, 강풍 등의 기상 조건들(Attributes)에 따라 실외 경기가 가능할지 (Play) 결정하는 모델을 만들고자 합니다.

날씨 (Outlook)	온도 (Temperature)	습도 (Humidity)	강풍 (Windy)	경기 진행여부 (Play)
맑음	더움	높음	아니오	No
맑음	더움	높음	예	No
흐림	더움	높음	아니오	Yes
비	따뜻함	높음	아니오	Yes
비	시원함	보통	아니오	Yes
비	시원함	보통	예	No
흐림	시원함	보통	예	Yes
맑음	따뜻함	높음	아니오	No
맑음	시원함	보통	아니오	No
비	따뜻함	보통	아니오	Yes
맑음	따뜻함	보통	예	Yes
흐림	따뜻함	높음	예	Yes
흐림	더움	보통	아니오	Yes
비	따뜻함	높음	예	No

어떤 attribute를 먼저 사용하느냐에 따라 여러 가지 Decision Tree를 만들 수 있을 겁니다. 아래와 같이 말이죠.

그런데 위와 같이 여러 종류의 의사결정트리를 만들 수 있다면, 더 좋은 모델인지 어느 것인지는 어떻게 알 수 있을까요? 답은 "변별력이 좋은 질문부터 먼저 정한다"입니다. 그렇다면, 예시를 통해 변별력이 무엇인지 알아봅시다!

---

빨간색과 주황색으로 표시된, 서로 다른 데이터를 갖는 여러 점들이 있습니다.

어떻게 선을 그어야 이 점들을 잘 구분 지을 수 있을까요? 이 선을 우리는 기준이라고 할 수 있습니다. 다시 말하면, 위의 예시에서 온도(더움/따뜻함,시원함) 또는 강풍(예/아니오)과 같은 것들을 의미하죠.

좌측의 초록색 선으로 주어진 데이터를 나누었더니, 빨강, 주황색 점이 완벽하게 나뉘었습니다. 우리는 이런 것들을 좋은 기준이라고 정의하는 반면, 우측의 보라색 선처럼 데이터를 이상하게 구분 짓는 선들을 나쁜 기준이라고 합니다.

즉, 분류가 잘 안 되던 데이터셋에 특정한 기준을 추가로 적용했더니, 잘 나뉘더라!라는 게 의사결정나무의 기준을 결정짓는 핵심입니다. 의사결정나무에서는 데이터가 잘 나뉘었는지를 정량화하는 개념으로 불순도(Impurity)를 사용합니다.

---

불순도(Impurity)

불순도는 주어진 데이터 내 값들이 얼마나 다양하게 분포되어있는가?입니다.

위 그림 a, c에서는 모든 데이터가 한 가지 색을 갖고 있기 때문에 불순도가 0입니다
반면, 그림 b에서는 여러 색이 뒤섞여있기 때문에, 불순도가 큰 값을 갖습니다.

따라서 의사결정나무에서 여러 가지 기준을 적용했을 때 나뉘는 결과의 불순도를 비교해서, 불순도를 가장 많이 감소시키는 기준을 선택해야 합니다.

불순도의 종류

불순도로 어떤 지표를 사용하냐에 따라 알고리즘의 방향이 갈리게 되는데, 크게는 아래와 같이 엔트로피 (Entropy)와 지니 계수 (Gini index) 기반의 알고리즘으로 나눌 수 있습니다.

• 엔트로피 (Entropy) 기반 알고리즘
  • ID3
  • C4.5
  • C5.0
• 지니 계수 (Gini index) 기반 알고리즘
  • CART (Classification And Regression Tree)

이후 포스팅에서는 ID3, C4.5, CART 알고리즘에 대해서 하나씩 알아보도록 하겠습니다.