A Step By Step Regression Tree Example
결정 트리(Decision tree)는 문제를 분류하기 위한 강력한 방법이며 회귀문제(regression problem)에도 적용될 수 있다. 목표 컬럼이 실수(real number)가 될 수 있는 데이터셋에 대해 구축된 결정 트리를 회귀 트리(regression trees)라고 한다. 이 경우, ID3의 정보 이익(information gain), C4.5의 이익 비율(gain ratio), CART의 gini index같은 접근은 동작하지 않는다. 여전히 회귀 트리는 CART알고리즘이다. 이 글에서는 설계부터 단계별로 직접 회귀 트리를 구성해 본다.
Pan’s Labyrinth (2006)
Regression trees in Python
이 글에서는 회귀트리 알고리즘을 자세히 설명하고 단계별로 문제를 해결해 본다. 여기에서 회귀 트리를 파이썬으로 구현한 것을 찾을 수 있다.
Objective
표준 편차(standard deviations)로 결정 규칙을 찾는다.
Data set
아래 데이터셋은 다른 결정 트리 관련 글에서 사용한 것과 유사하다. 여기서는 골프 경기를 할지에 대해 결정을 내리는 즉, 참(True)와 거짓(False)값으로 구성되는 범주형 목표(nominal target)이 아닌 목표 컬럼이 골프 플레이어의 수로 실수를 저장한다. 목표가 범주형일 때에는 각 분류에 대한 데이터(instance)의 수를 세었다. 이것은 True 결정과 False 결정에 대한 데이터의 수에 기초하여 분기를 만들 수 있다는 것이다. 여기서는 목표가 연속적이기 때문에 목표 값을 셀 수 없다. 그 대신에 표준편차(standard deviation)로 지표(metric)를 바꿈으로써 회귀 문제를 다룰 수 있다.
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 3 | Overcast | Hot | High | Weak | 46 |
| 4 | Rain | Mild | High | Weak | 45 |
| 5 | Rain | Cool | Normal | Weak | 52 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
| 14 | Rain | Mild | High | Strong | 30 |
표준 편차(Standard Deviation)
$\text{Golf players} = {25, 30, 46, 45, 52, 23, 43, 35, 38, 46, 48, 52, 44, 30}$
$\text{Average of golf players} = (25 + 30 + 46 + 45 + 52 + 23 + 43 + 35 + 38 + 46 + 48 + 52 + 44 + 30) \div 14 = 39.78$
$\text{Standard deviation of golf players}$
$= \sqrt{\frac{\sum(y - y')^2}{n}}$
$= \sqrt{[( (25 – 39.78)^2 + (30 – 39.78)^2 + (46 – 39.78)^2 + … + (30 – 39.78)^2 )/14]} = 9.32$- y : 실제값
- y' : 평균
- n : 데이터 수
전망(Outlook)
전망은 맑음(Sunny), 흐림(Overcast), 비(Rain)이 될 수 있고 이 모든 전망에 대한 골프 플레이어의 표준 편차를 계산해야 한다.
Outlook = Sunny
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
$\text{Golf players for sunny outlook} = {25, 30, 35, 38, 48}$
$\text{Average of golf players for sunny outlook} = (25+30+35+38+48) \div 5 = 35.2$
$\text{Standard deviation of golf players for sunny outlook} = \sqrt{((25 – 35.2)^2 + (30 – 35.2)^2 + … ) \div 5} = 7.78$
Outlook = Overcast
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 3 | Overcast | Hot | High | Weak | 46 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
$\text{Golf players for overcast outlook} = {46, 43, 52, 44}$
$\text{Average of golf players for overcast outlook} = (46 + 43 + 52 + 44) \div 4 = 46.25$
$\text{Standard deviation of golf players for overcast outlook} = \sqrt{((46 – 46.25)^2 + (43 – 46.25)^2 + … ) \div 4} = 3.49$
Outlook = Rain
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 4 | Rain | Mild | High | Weak | 45 |
| 5 | Rain | Cool | Normal | Weak | 52 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 14 | Rain | Mild | High | Strong | 30 |
$\text{Golf players for rain outlook} = {45, 52, 23, 46, 30}$
$\text{Average of golf players for rain outlook} = (45 + 52 + 23 + 46 + 30) \div 5 = 39.2$
$\text{Standard deviation of golf players for rain outlook} = \sqrt{((45 – 39.2)^2 + (52 – 39.2)^2 + … ) \div 5} = 10.87$
전망 특성에 대한 표준편차 정리
| Outlook | Stdev of Golf Players | Instances |
|---|---|---|
| Overcast | 3.49 | 4 |
| Rain | 10.87 | 5 |
| Sunny | 7.78 | 5 |
- $\text{Weighted standard deviation for outlook} = (4 \div 14) \times 3.49 + (5 \div 14) \times 10.87 + (5 \div 14) \times 7.78 = 7.66$
이전 단계에서 골프 플레이어의 전역(global) 표준편차 9.32를 계산했다. 표준편차 감소는 전역 표준편차와 현재 특성에 대한 표준 편차의 차이이다. 이런 방법으로 최대인 표준편차 감소가 결정 노드가 된다.
- $\text{Standard deviation reduction for outlook} = 9.32 – 7.66 = 1.66$
Temperature
온도는 더움(hot), 추움(cool), 포근함(mild)가 될 수 있고 이들 후보에 대한 표준 편차를 계산한다.
Hot temperature
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 3 | Overcast | Hot | High | Weak | 46 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
$\text{Golf players for hot temperature} = {25, 30, 46, 44}$
$\text{Standard deviation of golf players for hot temperature} = 8.95$
Cool temperature
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 5 | Rain | Cool | Normal | Weak | 52 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
$\text{Golf players for cool temperature} = {52, 23, 43, 38}$
$\text{Standard deviation of golf players for cool temperature} = 10.51$
Mild temperature
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 4 | Rain | Mild | High | Weak | 45 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 14 | Rain | Mild | High | Strong | 30 |
$\text{Golf players for mild temperature} = {45, 35, 46, 48, 52, 30}$
$\text{Standard deviation of golf players for mild temperature} = 7.65$
온도 특성에 대한 표준편차 정리
| Outlook | Stdev of Golf Players | Instances |
|---|---|---|
| Hot | 8.95 | 4 |
| Cool | 10.51 | 4 |
| Mild | 7.65 | 6 |
$\text{Weighted standard deviation for temperature} = (4 \div 14) \times 8.95 + (4 \div 14)\times 10.51 + (6 \div 14) \times 7.65 = 8.84$
$\text{Standard deviation reduction for temperature} = 9.32 – 8.84 = 0.47$
Humidity
습도는 이진 분류로 보통(normal) 또는 높음(high)이 될 수 있다.
High humidity
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 3 | Overcast | Hot | High | Weak | 46 |
| 4 | Rain | Mild | High | Weak | 45 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 14 | Rain | Mild | High | Strong | 30 |
$\text{Golf players for high humidity} = {25, 30, 46, 45, 35, 52, 30}$
$\text{tandard deviation for golf players for high humidity} = 9.36$
Normal humidity
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 5 | Rain | Cool | Normal | Weak | 52 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
$\text{Golf players for normal humidity} = {52, 23, 43, 38, 46, 48, 44}$
$\text{Standard deviation for golf players for normal humidity} = 8.73$
습도 특성에 대한 표준편차 정리
| Outlook | Stdev of Golf Players | Instances |
|---|---|---|
| High | 9.36 | 7 |
| Normal | 8.73 | 7 |
$\text{Weighted standard deviation for humidity} = (7 \div 14) \times 9.36 + (7 \div 14) \times 8.73 = 9.04$
$\text{Standard deviation reduction for humidity} = 9.32 – 9.04 = 0.27$
Wind
바람은 이진 분류로 강함(Strong) 또는 약함(Weak)이 될 수 있다.
Strong Wind
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 2 | Sunny | Hot | High | Strong | 30 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 14 | Rain | Mild | High | Strong | 30 |
$\text{Golf players for strong wind} = {30, 23, 43, 48, 52, 30}$
$\text{Standard deviation for golf players for strong wind} = 10.59$
Weak Wind
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 3 | Overcast | Hot | High | Weak | 46 |
| 4 | Rain | Mild | High | Weak | 45 |
| 5 | Rain | Cool | Normal | Weak | 52 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
$\text{Golf players for weakk wind} = {25, 46, 45, 52, 35, 38, 46, 44}$
$\text{Standard deviation for golf players for weak wind} = 7.87$
바람 특성에 대한 표준편차 정리
| Outlook | Stdev of Golf Players | Instances |
|---|---|---|
| Strong | 10.59 | 6 |
| Weak | 7.87 | 9 |
$\text{Weighted standard deviation for wind} = (6 \div 14) \times 10.59 + (8 \div 14) \times 7.87 = 9.03$
$\text{Standard deviation reduction for humidity} = 9.32 – 9.04 = 0.27$
모든 특성에 대한 표준편차 감소를 계산했고 점수가 가장 높은 전망(outlook)이 승자이다.
| Feature | Standard Deviation Reduction |
|---|---|
| Outlook | 1.66 |
| Temperature | 0.47 |
| Humidity | 0.27 |
| Wind | 0.29 |
결정 트리의 맨 위에 전망을 놓는다. 이제 전망 특성의 후보 분기를 위한 새로운 하위 데이터셋을 살펴보자.
트리의 맨위에 전망(Outlook) 넣기
Sunny Outlook
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
$\text{Golf players for sunny outlook} = {25, 30, 35, 38, 48}$
$\text{Standard deviation for sunny outlook} = 7.78$
이 하위 데이터셋에 대해서는 전역 표준 편차로써 이 표준 편차를 사용한다는 것을 기억해 두자.
Sunny outlook and Hot Temperature
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
- $\text{Standard deviation for sunny outlook and hot temperature} = 2.5$
Sunny outlook and Cool Temperature
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 9 | Sunny | Cool | Normal | Weak | 38 |
- $\text{Standard deviation for sunny outlook and cool temperature} = 0$
Sunny outlook and Mild Temperature
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 8 | Sunny | Mild | High | Weak | 35 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
- $\text{Standard deviation for sunny outlook and mild temperature} = 6.5$
맑음 전망일 때 온도 특성에 대한 표준 편차 정리
| Temperature | Stdev for Golf Players | Instances |
|---|---|---|
| Hot | 2.5 | 2 |
| Cool | 0 | 1 |
| Mild | 6.5 | 2 |
$\text{Weighted standard deviation for sunny outlook and temperature} = (2 \div 5) \times 2.5 + (1 \div 5) \times 0 + (2 \div 5) \times 6.5 = 3.6$
$\text{Standard deviation reduction for sunny outlook and temperature} = 7.78 – 3.6 = 4.18$
Sunny outlook and high humidity
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 8 | Sunny | Mild | High | Weak | 35 |
- $\text{Standard deviation for sunny outlook and high humidity} = 4.08$
Sunny outlook and normal humidity
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
- $\text{Standard deviation for sunny outlook and normal humidity} = 5$
맑음 전망일 때 습도 특성에 대한 표준 편차 정리
| Humidity | Stdev for Golf Players | Instances |
|---|---|---|
| High | 4.08 | 3 |
| Normal | 5.00 | 2 |
$\text{Weighted standard deviations for sunny outlook and humidity} = (3 \div 5) \times 4.08 + (2 \div 5) \times 5 = 4.45$
$\text{Standard deviation reduction for sunny outlook and humidity} = 7.78 – 4.45 = 3.33$
Sunny outlook and Strong Wind
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 2 | Sunny | Hot | High | Strong | 30 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
- $\text{Standard deviation for sunny outlook and strong wind} = 9$
Sunny outlook and Weak Wind
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
- $\text{Standard deviation for sunny outlook and weak wind} = 5.56$
맑음 전망일 때 바람 특성에 대한 표준 편차 정리
| Wind | Stdev for Golf Players | Instances |
|---|---|---|
| Strong | 9 | 2 |
| Weak | 5.56 | 3 |
$\text{Weighted standard deviations for sunny outlook and wind} = (2 \div 5) \times 9 + (3 \div 5) \times 5.56 = 6.93$
$\text{Standard deviation reduction for sunny outlook and wind} = 7.78 – 6.93 = 0.85$
맑음 전망에 대한 표준 편차 감소를 계산하였고 온도가 승자이다.
| Feature | Standard Deviation Reduction |
|---|---|
| Temperature | 4.18 |
| Humidity | 3.33 |
| Wind | 0.85 |
맑음(sunny) 전망 아래에 온도 결정 넣기
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
가지치기(Pruning)
추움(Cool) 분기는 하위 데이터셋으로 하나의 인스턴스를 갖는다. 이것은 만약 맑음 전망이면 온도가 춥고 38명의 골프플레이어가 있다고 말할 수 있다. 하지만 더움(hot) 분기는 어떨까? 여전히 2개의 인스턴스가 있다. 바람의 강함과 약함을 위한 또다른 분기를 추가해야 할까? 대답은 그럴 필요 없다이다. 예를 들어 하위 데이터셋에 5개미만의 인스턴스 가 있다면 또는 하위 데이터셋의 표준 편차기 5% 미만일 수 있다면 이것이 오버피팅을 발생시키기 때문에 분기를 만드는 것을 멈춰야 한다. (필자)는 첫번째 방법을 적용하는 것을 좋아하기 때문에 현재 하위 데이터셋에서 5개 미만의 인스턴스만 있다면 분기를 중단한다. 이 종료 조건을 만족한다면 하위 데이터셋의 평균을 계산한다. 이 연산을 결정 트리에서 가지치기(pruning)이라고 한다.
Overcast outlook
흐림(overcast) 전망 분기는 하위 데이터셋에 4개의 인스턴스가 있으므로 이 단계에서 분기를 종료할 수 있다. 흐림 전망에 대한 최종 결정은 아래 테이블의 평균이 된다.
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 3 | Overcast | Hot | High | Weak | 46 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
- $\text{Golf players for overcast outlook} = (46 + 43 + 52 + 44) \div 4 = 46.25$
Rainy outlook
| Day | Outlook | Temp. | Humidity | Wind | Golf Players |
|---|---|---|---|---|---|
| 4 | Rain | Mild | High | Weak | 45 |
| 5 | Rain | Cool | Normal | Weak | 52 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 14 | Rain | Mild | High | Strong | 30 |
이전과 같은 방법으로 위의 하위 데이터셋에 대한 나머지 특성의 표준 편차 감소를 찾아야 한다.
- $\text{Standard deviation for rainy outlook} = 10.87$
감소 단계에서 이 분기에 대한 전역 표준편차로 이 값이 사용된다.
Rainy outlook and temperature
| Temperature | Stdev for Golf Players | Instances |
|---|---|---|
| Cool | 14.50 | 2 |
| Mild | 7.32 | 3 |
$\text{Weighted standard deviation for rainy outlook and temperature} = (2 \div 5) \times 14.50 + (3 \div 5) \times 7.32 = 10.19$
$\text{Standard deviation reduction for rainy outlook and temperature} = 10.87 – 10.19 = 0.67$
Rainy outlook and humidity
| humidity | Stdev for Golf Players | Instances |
|---|---|---|
| High | 7.50 | 2 |
| Normal | 12.50 | 3 |
$\text{Weighted standard deviation for rainy outlook and humidity} = (2 \div 5) \times 7.50 + (3 \div 5) \times 12.50 = 10.50$
$\text{Standard deviation reduction for rainy outlook and humidity} = 10.87 – 10.50 = 0.37$
Rainy outlook and wind
| wind | Stdev for Golf Players | Instances |
|---|---|---|
| Weak | 3.09 | 3 |
| Strong | 3.5 | 2 |
$\text{Weighted standard deviation for rainy outlook and wind} = (3 \div 5) \times 3.09 + (2 \div 5) \times 3.5 = 3.25$
$\text{Standard deviation reduction for rainy outlook and wind} = 10.87 – 3.25 = 7.62$
비 전망 요약
아래 표처럼 바람 특성이 승자이다.
| Feature | Standard Deviation Reduction |
|---|---|
| Temperature | 0.67 |
| Humidity | 0.37 |
| Wind | 7.62 |
비 전망에 대한 하위 데이터셋
보이는 것처럼 양쪽 분기모두 5개 미만으로 종료 규칙에 따라 분기를 종료할 수 있다.
따라서 최종 결정 트리는 아래와 같다.
회귀 트리의 최종 형태