[머신러닝] 결정트리

🟥결정트리(Decision Tree)

의사결정트리, 의사결정나무라고도 하는 결정트리는 분류(Classification)와 회귀(Regression) 모두 가능한 지도 학습 모델의 한 종류이다. 결정트리는 트리 구조를 활용하여 entropy가 최소화 되는 방향으로 데이터를 예측한다. 쉽게 생각하면 스무고개와 비슷하다고 보면 된다. 이러한 결정트리는 1960년대에 처음 등장 하였음에도 XGBoost, LightBGM과 같이 현재까지 발전되어 많이 쓰이고 있다.

• 발전과정

- Concept Learning System(CLS)(1960년)

결정트리는 처음에는 심리학에서 사용되다가 머신러닝에 사용되기 시작했다. 그 처음인 CLS는 얼 헌트에 의해 고안되었으며 처리 방법이 매우 간단하다. 모두 A의 요소이면 Positive, 모두 A의 요소가 아니면 Negative, 그렇지 않으면 부분집합을 만들어 요소에 해당하는지 확인하는 작업을 반복 수행하면 된다. 

- Iterative Dichotomiser 3(ID3)(1980년대)

이후 얼 헌트의 CLS를 그의 제자인 로스 퀸란이 발전시켜 의사결정트리 알고리즘을 만들게 된다. 이 알고리즘은 엔트로피와 정보 이득을 사용하여 트리를 구축하는 방법을 제안한다. 데이터의 특징을 반복적으로 분할하여 트리를 생성하며, 불순도를 줄이는 방향으로 발전했다.

- Classification and Regression Trees(CART)(1980년대)

CART는 이름 그대로 분류와 회귀 모두 사용 가능한 알고리즘으로 ID3와는 몇가지 차이점이 존재한다. ID3에서는 불순도로 엔트로피를 사용했다면, CART에서는 지니 인덱스를 사용한다. 또 다른 특징으로 CART는 분기할 때 단 두개의 노드로 분기, 즉 자식 노드를 2개만 생성한다는 것이 특징이다.

- C4.5와 C5.0(1990년대)

로스 퀸란은 이후 ID3를 개선하여 C4.5 알고리즘을 개발하였다. C4.5는 연속적인 데이터 처리, 불완전한 데이터 처리, 가지치기 등의 기능을 추가하여 ID3의 단점을 보완했다. 이후 이는 결정 트리 알고리즘의 표준으로 자리잡게 되었고 본격적으로 사용되기 시작했다.

- 앙상블 방법론(2000년대)

이전까지의 결정트리의 가장 큰 단점은 과적합(overfitting)에 취약하다는 것이다. 이러한 단점을 보완하기 위해 앙상블 방법론이 도입되었다. 가장 대표적인 방법으로는 랜덤 포레스트(Random Forest)와 부스팅(Boosting) 이 있다. 랜덤 포레스트는 여러 개의 결정 트리를 훈련시켜 그 결과를 앙상블 하는 방법이다. 부스팅은 약한 학습자 집합을 하나의 강력한 학습자로 결합하여 예측 정확도를 향상시키는 방법으로 AdaBoost와 Gradient Boosting 등이 있다. 이러한 방법들에 대해서는 추후 자세히 다루어 보겠다. 

- 2010년대 이후

XGBoost와 LightBGM 같은 고성능의 부스팅 알고리즘이 개발 되었다. 이들은 속도가 빠를 뿐만 아니라 성능 또한 우수하다. 이들은 몇몇 딥러닝 모델과 결합되어 하이브리도 모델을 형성하기도 한다.

 

모델 원리

결정트리는 이름 그대로 트리 구조의 형태를 띄고 있다. 여기서 하나의 노드는 질문/기준에 해당하는 것으로 이에 따라 데이터를 구분하고 하위 노드를 생성한다. 단순하게 하위 노드를 타고 내려가서 새로운 분기를 거듭해서 최종적인 결정에 도달하는 것이 그 원리이다. 이러한 결정트리는 범주나 연속형 수치 모두 예측할 수 있기 때문에 분류와 회귀 모두 사용한 것이다. 

 

- 불순도(Impurity) / 불확실성(Uncertainty)

결정트리는 한번 분기 때마다 변수 영역(노드에 해당)을 최소 두 개로 구분하는 모델이다. 즉, 해당 노드 안에서 섞여 있는 정도가 높을수록 복잡성이 높고, 덜 섞여 있을수록 복잡성이 낮다. 결정트리는 불순도 혹은 불확실성이 최대한 감소되는 방향으로 학습을 진행한다. 이 Impurity를 측정하는 척도에는 엔트로피, 지니 인덱스, 분산 등 다양한 척도가 있지만 엔트로피(Entropy)에 대해서 간단히 이야기하고 넘어가겠다.

k는 범주, Pi는 영역에 속하는 레코드 가운데 i 범주에 속하는 레코드의 비율이다. 이 엔트로피는 분기를 거듭할 수록 낮아져야 한다. 이는 불확실성이 감소하였다는 의미이고 순도가 증가했다는 의미이다. 이렇게 불확실성이 감소한다면 분기를 진행하는게 낫다고 판단되어 트리의 브랜치를 생성하게 되는 것이다. 이렇게 불순도 측정 -> 데이터 분할 -> 재귀적 분할 -> 종료 조건의 단계를 거쳐 결정트리는 학습을 진행하게 된다.

 

- 가지치기(Pruning)

학습된 결정 트리는 과적합을 방지하기 위해 가지치기 과정을 거친다. 가지치기는 트리의 일부 가지를 제거하여 모델의 복잡성을 줄이고, 일반화 성능을 향상시키는 방법이다. 즉, 최대 깊이나 터미널 노드의 최대 개수, 혹은 한 노드가 분할하기 위한 최소 데이터 수를 제한하는 것이다. 사실 이러한 과정은 가지를 잘라내는 것이 아닌 분기를 합치는 개념이 올바르다고 할 수 있다.

 

 

 

https://post.naver.com/viewer/postView.nhn?volumeNo=28924800&memberNo=50533718
https://tyami.github.io/machine%20learning/decision-tree-4-CART/
https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-4-%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%ACDecision-Tree
https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
https://process-mining.tistory.com/42
https://leedakyeong.tistory.com/entry/Decision-Tree%EB%9E%80-ID3-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98