4.4 Decision Tree

6 minute read

의사결정 트리

선형 회귀 분석 및 로지스틱 회귀 모형은 특성과 결과 간의 관계가 비선형이거나 특성이 상호 작용하는 상황에서 좋지않습니다. 의사결정 트리 빛날 시간입니다! 트리 기반 모델은 특성의 특정 기준 값에 따라 데이터를 여러 번 분할합니다. 분할을 통해 각 관측치가 하나의 하위 집합에 속하는 서로 다른 데이터 집합이 생성됩니다. 최종 서브셋을 터미널 또는 리프 노드라고 하고 중간 서브셋을 내부 노드 또는 분할 노드라고 합니다. 각 리프 노드의 결과를 예측하기 위해 이 노드의 학습 데이터의 평균 결과가 사용됩니다. 트리는 분류 및 회귀 분석에 사용할 수 있습니다.

트리를 키울 수 있는 다양한 알고리즘이 있습니다. 트리의 가능한 구조(예: 노드당 분할 수), 분할을 찾는 방법, 분할을 중지하는 시기 및 리프 노드 내의 단순 모델을 추정하는 방법이 서로 다릅니다. 분류 및 회귀 트리(Classficiation And Regression Tree, CART) 알고리즘은 아마도 트리 유도에 가장 많이 사용되는 알고리즘일 것입니다. CART에 초점을 맞출 예정이지만 다른 대부분의 트리 유형에서도 해석이 유사합니다. 저는 ‘The Elements of Statistical Learning’(Friedman, Hastie, Tibshirani 2009)를 추천합니다.1](으)로 CART에 대한 보다 자세한 소개를 할 수 있습니다.


그림 4.16: 인공 데이터가 있는 의사결정 트리입니다. 특성 x1에 대한 값이 3보다 큰 관측치는 노드 5에 포함됩니다. 다른 모든 관측치는 특성 x2 값이 1을 초과하는지 여부에 따라 노드 3 또는 노드 4에 할당됩니다.

다음 공식에서는 결과 y와 특성 x의 관계를 설명합니다.

\[\hat{y}=\hat{f}(x)=\sum_{m=1}^Mc_m{}I\{x\in{}R_m\}\]

각 관측치는 정확히 하나의 리프 노드(=subset \(R_m\))에 속합니다. \(I_{\{x\in{}R_m\}}\)는 \(x\)이(가) 하위 집합 \(R_m\)이고, 그렇지 않으면 0이면 1을 반환하는 항등 함수입니다. 관측치가 리프 노드 \(R_l\)에 포함되는 경우 예상 결과는 \(\hat{y}=c_l\)이며, 여기서 \(c_l\)는 리프 노드 \(R_l\)의 모든 학습 관측치의 평균입니다.

하지만 하위집합은 어디에서 올까요? 이는 매우 간단합니다. CART는 특성을 사용하여 회귀 문제에 대한 y의 분산을 최소화하는 컷오프 포인트 또는 분류 문제에 대한 y의 클래스 분포의 지니 인덱스를 결정합니다. 분산은 노드의 y 값이 평균값 주위에 얼마나 분산되어 있는지 알려줍니다. 지니 지수는 노드가 얼마나 “불순(impure)”한지 알려줍니다. 예를 들어, 모든 클래스의 빈도가 동일하면 노드가 불순하고, 클래스가 하나만 있으면 가장 순수하다고 할 수 있습니다. 노드의 데이터 포인트가 y에 대해 매우 유사한 값을 가질 경우 분산 및 지니 인덱스가 최소화됩니다. 그 결과, 최상의 컷오프 지점은 목표 결과와 관련하여 두 개의 하위 세트를 최대한 다르게 만듭니다. 범주형 특성의 경우 알고리즘은 다른 범주 그룹화를 시도하여 하위 집합을 생성하려고 합니다. 특성당 최상의 컷오프가 결정되면 알고리즘은 분산 또는 지니 인덱스 측면에서 최상의 파티션을 얻을 수 있는 분할 특성을 선택하고 이 분할을 트리에 추가합니다. 알고리즘은 중지 기준에 도달할 때까지 두 새 노드에서 이 검색 및 분할을 반복합니다. 가능한 기준은 다음과 같습니다. 분할하기 전에 노드에 있어야 하는 최소 관측치 수 또는 터미널 노드에 있어야 하는 최소 관측치 수입니다.

해석

해석은 간단합니다. 루트 노드에서 시작하여 다음 노드로 이동하면 연결가지가 보고 있는 하위 집합을 알려줍니다. 리프 노드에 도달하면 노드가 예측 결과를 알려줍니다. 모든 연결가지는 ‘AND’로 연결됩니다.

템플릿은 다음과 같습니다. feature x가 임계값 c AND보다 [작거나/크거나]인 경우, 예측 결과는 해당 노드에 있는 관측치의 평균 Y 값입니다.

특성 중요도

의사결정 트리에서 특성의 전반적인 중요도는 다음과 같은 방법으로 계산할 수 있습니다. 특성이 사용된 모든 분할을 살펴보고 상위 노드에 비해 분산 또는 지니 인덱스가 얼마나 감소했는지 측정합니다. 모든 특성의 합계는 100으로 조정됩니다. 즉, 각 중요도를 전체 모델 중요도의 공유로 해석할 수 있습니다.

트리 분해

의사결정 트리의 개별 예측은 의사결정 경로를 특성당 하나의 구성 요소로 분해하여 설명할 수 있습니다. 트리를 통해 결정을 추적하고 각 의사결정 노드에서 추가된 기여에 의한 예측을 설명할 수 있습니다.

의사결정 트리의 루트 노드가 우리의 출발점입니다. 루트 노드를 사용하여 예측하는 경우 학습 데이터의 결과 평균을 예측할 수 있습니다. 다음 분할에서는 경로의 다음 노드에 따라 이 합계에 항을 빼거나 추가합니다. 최종 예측에 도달하기 위해서는 설명하고자 하는 데이터 관측치의 경로를 따르고 공식에 계속 추가해야 합니다.

\[\hat{f}(x)=\bar{y}+\sum_{d=1}^D\text{split.contrib(d,x)}=\bar{y}+\sum_{j=1}^p\text{feat.contrib(j,x)}\]

개별 관측치의 예측은 대상 결과의 평균에 루트 노드와 관측치가 끝나는 터미널 노드 사이에 발생하는 모든 D 분할 기여의 합을 더한 값입니다. 그러나 우리는 분할 기여도에 관심이 없고 특성 기여에 관심이 있습니다. 특성이 두 개 이상의 분할에 사용되거나 전혀 사용되지 않을 수 있습니다. 각 p 특성에 대한 기여도를 추가하고 각 특성이 예측에 얼마나 기여했는지에 대한 해석을 얻을 수 있습니다.

예시

자전거 대여 데이터를 다시 한 번 살펴보겠습니다. 우리는 의사결정 트리를 가지고 특정한 날에 대여된 자전거의 수를 예측하고 싶습니다. 학습된 트리는 다음과 같습니다.


그림 4.17: 자전거 대여 데이터에 적용한 회귀 트리입니다. 트리의 최대 허용 깊이는 2로 설정되었습니다. 분할에 대해 추세 특성(days since 2011)과 온도(temp)가 선택되었습니다. Boxplots은 터미널 노드의 자전거 수 분포를 보여 줍니다.

첫 번째 분할과 두 번째 분할 중 하나는 트렌드 특성으로 수행되었습니다. 이 특성은 데이터 수집이 시작된 이후의 날짜를 계산하고 시간이 지남에 따라 자전거 대여 서비스가 더욱 인기를 끌고 있는 추세를 반영합니다. 105일 전, 예상 자전거의 수는 약 1,800 대이고, 106일에서 430일 사이는 약 3,900 대입니다. 430일 이후 예측은 4,600(온도가 12도 미만인 경우) 또는 6,600(온도가 12도 이상인 경우)입니다.

특성 중요도는 특성이 모든 노드의 순도를 개선하는 데 얼마나 도움이 되었는지 알려줍니다. 여기서는 자전거 대여를 예측하는 것이 회귀 문제이기 때문에 분산이 사용되었습니다.

시각화된 트리는 온도 및 시간 추세가 분할에 사용되었음을 보여주지만 어떤 특성이 더 중요한지는 정량화하지 않습니다. 특성 중요도 측정은 시간 추세가 온도보다 훨씬 더 중요하다는 것을 보여줍니다.


그림 4.18: 노드의 순도가 평균적으로 얼마나 향상되는지 측정된 특성의 중요도입니다.

장점

트리 구조는 데이터의 특성 간 상호 작용을 교려하는데 적합합니다.

데이터는 선형 회귀 분석과 같이 다차원 초평면의 점보다 이해하기 쉬운 개별 그룹으로 나눕니다. 그 해석은 매우 간단합니다.

트리 구조는 또한 노드와 연결가지로 시각화를 할 수 있습니다.

트리는 “인간 친화적인 설명”의 장에 정의된 대로 좋은 설명을 만듭니다. 트리 구조는 자동으로 개별 관측치에 대해 예측된 값을 반사실적으로 생각해볼 수 있게 합니다. “만약 특성이 분할점보다 크거나 작았더라면 예측은 y2가 아닌 y1이 되었을 것입니다.” 트리 설명은 항상 관측치의 예측을 트리의 다른 리프 노드인 관련 “what if” 시나리오와 비교할 수 있기 때문에 대조적입니다. 트리가 1-3개의 깊이 분할된 것처럼 짧으면 결과 설명이 선택적입니다. 깊이가 3인 트리는 개별 관측치(instance) 예측에 대한 설명을 생성하기 위해 최대 3개의 특성와 분할점이 필요합니다. 예측의 진실성은 트리의 예측 성능에 달려 있습니다. 짧은 트리에 대한 설명은 매우 간단하고 일반적입니다. 왜냐하면 각각의 분할에 대한 관측치는 한 잎이나 다른 잎으로 떨어지기 때문입니다. 그리고 이항 결정은 이해하기 쉽습니다.

특성를 변환할 필요가 없습니다. 선형 모형에서는 특성의 로그가 필요할 때도 있습니다. 의사결정 트리는 특성의 단조로운 변환과 동일하게 작동합니다.

단점

트리는 선형 관계를 다루는데 실패합니다. 입력 특성와 결과 사이의 선형 관계는 스플릿으로 근사해야 하므로 단계 함수가 생성됩니다. 이것은 효율적이지 않습니다.

이것은 매끄러움 부족과 관련이 있습니다. 입력 특성의 약간의 변경은 예측 결과에 큰 영향을 미칠 수 있으며, 이는 일반적으로 바람직하지 않습니다. 집의 가치를 예측하는 트리를 상상해보세요. 그리고 트리는 집의 크기를 분할된 특성의 하나로 사용해요. 분할은 100.5 평방미터에서 발생합니다. 의사결정 트리 모델을 사용하는 집값 추정기 사용자를 상상해 보세요. 그들은 그들의 집을 측정하고, 99평방미터의 집을 가지고 있다는 결론을 내리고, 가격 계산기에 그것을 입력하고, 20만 유로를 예측합니다. 사용자들은 2평방미터의 작은 저장실을 측정하는 것을 깜빡했습니다. 보관실에는 경사진 벽이 있어 전체 면적을 세는것이 맞을지, 절반만 세는것이 맞을지 확신할 수 없습니다. 그래서 그들은 100.0평방미터와 101.0평방미터 둘 다를 시도하기로 결심합니다. 결과는 다음과 같습니다. 가격 계산기는 20만 유로와 20만5천 유로를 출력하는데, 99평방미터에서 100평방미터로 바뀐 것이 없기 때문에 다소 직관적이지 않습니다.

트리는 또한 안정적이지 않습니다. 학습 데이터 세트를 몇 가지 변경하면 완전히 다른 트리가 만들어질 수 있습니다. 각 분할은 상위 분할에 따라 다르기 때문입니다. 그리고 다른 특성를 첫 번째 분할 특성로 선택하면 전체 트리 구조가 변경됩니다. 구조가 그렇게 쉽게 변경되는 경우에는 모델에 대한 신뢰도가 생성되지 않습니다.

의사결정 트리는 매우 해석할 수 있습니다. 키가 작다면 말이죠. 깊이와 함께 터미널 노드 수가 빠르게 증가합니다. 터미널 노드가 많고 트리가 깊을수록 트리의 의사결정 규칙을 이해하는 것이 더 어려워집니다. 1의 깊이는 2개의 터미널 노드를 가집니다. 깊이 2는 최대 4개의 노드를, 깊이 3은 최대 8개 노드를 가집니다. 트리에서 최대 터미널 노드 수는 깊이 수의 2 제곱에 해당합니다.

소프트웨어

이 장의 예에서는 CART(분류 및 회귀 트리)를 구현하는 rpart R 패키지를 사용했습니다. CART는 Python을 비롯한 여러 프로그래밍 언어로 구현됩니다. 이론적으로, CART는 꽤 오래되고 다소 시대에 뒤떨어진 알고리즘이며, 트리에 맞추기 위한 몇 가지 흥미로운 새로운 알고리즘이 있습니다. Machine Learning and Statistical Learning CRAN Task View의 키워드 “Recursive Partitioning”에서 의사결정 트리에 대한 일부 R 패키지의 개요를 확인할 수 있습니다.

  1. Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. “The elements of statistical learning”. www.web.stanford.edu/~hastie/ElemStatLearn/ (2009).↩ ↩