#2-(5) 지도학습 알고리즘 : 결정 트리

※ 이 글의 내용은 O'REILLY의 <파이썬 라이브러리를 활용한 머신러닝> 책을 기반으로 한다.

지도 학습 알고리즘 : 결정 트리

• 결정 트리

 - 결정 트리(Decision Tree) : 위키피디아에 따르면, 결정 트리는 의사 결정 규칙과 그에 대한 결과들을 트리 구조로 도식화한 의사 결정 지원 도구의 일종이다. 즉, 의사를 결정하는데 있어서 질문을 던지고 그 질문에 대한 답들이 트리 구조를 이루고 있는 형태이다. 결정 트리는 분류와 회귀 문제에 널리 사용되는 모델이다. 기본적으로 결정 트리는 최종적인 결정에 도달하기 위하여 예/아니오의 이진 분류에 대한 질문을 이어나가면서 학습한다.

 - 트리 구조 : 트리 구조는 그래프 구조의 일종이다. 그래프 구조는 하나의 노드가 여러 노드와 연결될 수 있지만, 트리 구조에서는 하나의 노드는 최대 2개의 노드와 연결될 수 있다. 즉, 회로 없이 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(Root node : 뿌리)라고 하며, 노드 A가 노드 B를 가리킬 때 A노드를 B노드의 부모 노드(Parent node), B를 A의 자식 노드(Child node)라고 한다. 자식 노드가 없는 최하위의 노드를 리프 노드(Leaf node : 잎)라고 하고, 리프 노드가 아닌 자식 노드를 가지고 있는 노드를 내부 노드(Internal node)라고 한다. 리프 노드 중에서도 하나의 타겟 값만을 가지는 노드를 순수 노드(Pure node)라고 한다. 노드 사이를 연결하는 선은 엣지(Edge)라하고, 노드가 분기함으로써 생성되는 층을 깊이(depth)라고 한다.

• 결정트리 만들기

 - 결정 트리를 학습한다는 것은 정답에 가장 빨리 도달하는 질문의 목록을 학습한다는 뜻이다. 머신러닝에서 이런 질문들을 테스트라고 한다. 보통의 데이터는 예/아니오의 형태 특성으로 구성되지 않고, 2차원 데이터 세트와 같이 연속된 특성으로 구성된다. 그렇기 때문에 연속적인 데이터에 적용할 테스트(질문)는 '해당 특성이 특정한 값보다 큰가?'와 같은 형태를 띤다.

 - 트리를 만들 때의 알고리즘은 가능한 모든 테스트에서 타겟 값에 대하여 가장 많은 정보를 가진 것을 고른다. 즉, 거의 모든 테스트(질문)에서 데이터를 가장 잘 나누는 테스트를 찾는 것이다.

 - 데이터를 나누는 과정을 반복하면 각 노드가 테스트(질문) 하나씩을 가진 이진 결정 트리를 만든다. 다르게 말하면 각 테스트는 하나의 축을 따라 데이터를 둘로 나누는 것으로 생각할 수 있다. 이는 계층적으로 영역을 분할해가는 알고리즘이라 할 수 있다. 각 테스트는 하나의 특성에 대하여만 이루어지므로 나누어진 영역은 항상 축과 평행하다.

 - 데이터를 분할하는 것은 각 분할된 영역이 분류에서는 하나의 클래스, 회귀에서는 하나의 분석 결과를 가질 때까지 반복된다. 분할이 완료되어 모델이 만들어진 후에 새로운 데이터가 주어지면, 그 데이터가 특성을 분할한 영역들 중에서 어디에 위치하는지를 확인하면 그 입력 데이터의 출력을 알 수 있다. 도달한 리프 노드의 영역 내에 한 종류의 타겟 값만 존재하면(순수 노드) 그 값이 출력이 되고, 여러 개의 타겟 값이 존재하면 그 중 다수인 것이 출력이 된다.   

 - 분류와 같이, 회귀 문제에서도 트리를 사용할 수 있다. 각 노드의 테스트(질문) 결과에 따라 트리를 탐색해나가고 새로운 데이터에 해당되는 리프 노드를 찾는다. 찾은 리프 노드의 훈련 데이터 평균값이 주어진 입력 데이터에 따른 출력이 된다.

• 복잡도 제어

 - 일반적으로 트리를 만들 때 모든 리프 노드가 순수 노드가 될 때까지 진행하면, 즉 각 리프 노드가 하나의 타겟 값만을 가지면 모델이 매우 복잡해지고 훈련 데이터에 과대적합(Overfitting)된다. 순수 노드로 이루어진 트리에서, 훈련 데이터는 정확한 클래스의 리프 노드에 위치하지만 새로운 데이터가 주어지면 정확도가 떨어질 수 있다는 것이다. 다시 말해 트리의 깊이가 깊어진다는 것은 영역을 더 세밀하게 분할해나가는 것인데, 각 영역 내에 정확하게 하나의 클래스 타겟 값만 위치하도록 영역을 분할하면 모델이 너무 복잡하게 생성된다는 것이다. 결정 경계가 값 하나하나에 너무 민감하기 때문이다.

 - 한계를 주지 않으면 트리는 무한정 깊어지고 복잡해진다. 모델이 너무 복잡해져 과대적합되는 것을 방지하는 방법은 크게 두 가지이다. 하나는 트리 생성을 일찍 중단하는 사전 가지치기(Pre-Pruning) 전략이고, 다른 하나는 트리를 만든 후에 데이터 포인트가 적은 노드를 삭제하거나 병합하는 사후 가지치기(Post-Pruning) 혹은 가지치기(Pruning)라는 전략이다. 사전 가지치기 방법은 트리의 최대 깊이 혹은 리프 노드의 최대 개수를 제한하거나 노드가 분할하기 위한 포인트의 최소 한계를 지정해주는 것이다.

• 특성 중요도

 - 특성 중요도(Feature Importance) : 전체 트리를 살펴보는 것은 어려울 수 있으니, 트리가 어떻게 작동하는지 요약하는 속성들을 사용할 수 있다. 특성 중요도도 그 중의 하나로, 트리를 만드는 결정에 각 특성이 얼마나 중요한지를 평가하는 것이다. 이 값은 0과 1사이의 숫자로, 각 특성에 대해 0은 전혀 사용되지 않았다는 뜻이고 1은 완벽하게 타겟 클래스를 예측했다는 뜻이다. 특성 중요도 전체의 합은 1이다. 즉, 특성 중요도가 높으면 트리 구조에서 높은 층에 해당하는 노드의 테스트(질문)라는 것이고 특성 중요도가 낮으면 낮은 층에 해당하는, 세세하게 클래스를 분류하는 노드의 테스트(질문)이거나 혹은 테스트에 사용되지 않는 특성이라는 것이다.

 - 그러나 특성 중요도가 낮다고 하여 그 특성이 유용하지 않다는 것은 아니다. 단지 트리가 그 특성을 선택하지 않았을 뿐이며, 다른 특성이 동일한 정보를 지니고있어서일 수 있다. 음수가 될 수 있고 특성의 중요도를 나타내는 선형 모델의 가중치(계수)와는 달리, 특성 중요도는 항상 양수이며 특성이 어떤 클래스를 지지하는지는 알 수 없다. 

 - 회귀 결정 트리에서도 이런 특성은 동일하게 적용되나 분류와는 달리 회귀를 위한 트리 모델에는 중요한 속성이 하나 있다. 모든 트리 기반 회귀 모델은 외삽(Extrapolation), 훈련 데이터의 범위 밖에 위치하 포인트에 대해서는 예측을 할 수 없다는 것이다. 선형 모델은 전체 데이터의 경향성을 토대로 모델을 만들기 때문에 훈련 데이터의 범위 밖이더라도 예측할 수 있지만, 과는 달리, 훈련 데이터가 위치한 영역을 분할하여 예측하는 결정 트리는 범위 밖에 위치한 데이터에 대해서는 영역이 분할되어 있지 않기 때문에 모델이 예측을 할 수 없는 것이다.

<램(RAM) 가격 동향>

 - 2000년 전까지의 데이터로부터 2000년 후의 가격을 예측한 그래프이다. 선형 회귀 모델의 경우 직선으로 데이터를 근사하였고, 2000년 이후의 테스트 데이터를 거의 정확히 예측한다. 2000년 이전의 가격 동향을 토대로 생성된 모델이기 때문이다. 그러나 결정 트리의 경우 2000년 이전의 훈련 데이터에 대해서는 거의 완벽하게 예측을 하지만, 2000년 이후의 테스트 데이터에 대해서는 아예 예측을 하지 못한다. 그저 마지막 데이터 값을 그대로 출력할 뿐이다. 즉, 트리 모델은 훈련 데이터 밖의 새로운 데이터를 예측할 능력이 없다. 이는 모든 트리 기반 모델의 공통된 단점이다.

• 매개변수 선정

 - 결정 트리에서 모델의 복잡도를 조절하는 매개변수는 트리가 완전히 만들어지기 전에 멈추도록 하는 사전 가지치기 매개변수이다. 보통은 사전 가지치기 방법 중에서 최대 깊이(Max depth), 최대 리프 노드의 개수(Max leaf nodes), 노드가 분할하기 위한 포인트의 최소 한도(Min samples leaf) 중에서 하나만 지정해주어도 과대적합(Overfitting)을 막는 데는 충분하다.

• 결정 트리 평가

 - 장점 : 결정 트리의 장점으로 첫째는 만들어진 모델을 쉽게 시각화할 수 있어서 비전문가도 이해하기 쉽다. 두 번째는 데이터의 스케일에 구애받지 않는다는 것이다. 각 특성이 개별적으로 처리되어 데이터를 분할하기 때문에, 데이터 스케일의 영향을 받지 않으므로 결정 트리에서는 데이터가 특정 범위 안에 들어오도록 하는 정규화(Normalization)나 표준화(Standardization)같은 데이터 전처리 과정이 필요가 없다. 특히나 특성의 스케일이 서로 다르거나 이진 특성과 연속적인 특성이 혼합되어 있을 때에도 잘 작동한다. 셋째로 학습이 끝난 결정 트리의 작업 속도가 매우 빠르다는 것 또한 장점이다. 마지막 장점은 결정 트리는 모델이 어떻게 훈련되었는지 경로의 해석이 가능하다는 것이다.

 - 단점 : 결정 트리의 단점은 사전 가지치기를 사용함에도 과대적합(Overfitting)되는 경향이 있어 모델의 일반화 성능이 좋지 않다는 것이다. 단일 결정 트리의 이러한 단점을 보완한 것이 결정 트리의 앙상블 방법이다.