D053
Decision Trees
의사결정 나무(Decision Tree) 는 input 이 속한 class 생성하기 위해 feature vector의 attribute 를 사용하는 분기 프로그램입니다.
의사결정 나무에서 nonleaf 노드들은 입력에 대한 test 이고,
leaf 노드는 output 에 대한 클래스를 나타냅니다.
아래 그림은 데이터의 정보를 담고 있습니다.
국가 마다 좋아하는 스포츠가 주어져 있고,
feature vector (Continent, Population)가 있습니다.
여기서 DT 를 사용해서 국가를 입력했을 때 좋아하는 스포츠를 예측하고자 합니다.
국가의 Continent과 Population이 주어졌을 때,
루트부터 test 를 수행합니다.
테스트의 결과가 True 이면 왼쪽, False 이면 오른쪽으로 갑니다.
다음 노드가 nonleaf 인 경우 동일하게, 노드의 test 를 적용해 분기합니다 가게 합니다.
만약 leaf 노드에 도달했을 때, 그 클래스를 출력합니다.
예를 들어 Spain 은 이는 유럽에 속해서 루트에서 왼쪽으로 갑니다.
인구가 60 70 사이인지 묻고, 아니므로 오른쪽 노드로 갑니다.
최종적으로 soccer 클래스가 나오게 됩니다.
위의 트리는 표에 있는 데이터만 사용하여 만들었고,
그 데이터에만 적합하게 생성되었습니다.
그래서 새로운 데이터가 들어올 때 잘 작동이 안되는 경우가 발생합니다.
파키스탄과 같은 경우 Asia이고 182백만의 인구가 있습니다.
이 feature 를 사용하여 트리를 돌리면,
루트 부터 시작해서 오른쪽, 왼쪽으로 가서 하키가 나옵니다.
실제 데이터에서 제대로 동작하지 않은 것 입니다.
이러한 문제 상황을 오버피팅이라고 합니다.
우선 의사결정나무를 어떻게 생성하는지 다루고,
오버피팅 상황을 어떻게 처리하는지 다루겠습니다.
Impurity Measure
의사결정나무를 잘 생성하기 위해선, 좋은 test 를 설정하는 것이 필요합니다.
트리에 레벨은 가능한 적게 만듭니다.
레벨이 적으면 새로운 데이터를 빠르게 분류할 수 있고, 오버피팅을 피할 수 있습니다.
이상적으로, 특정 노드로 가는 모든 입력들이 모두 같은 클래스를 가지길 원합니다.
그 노드를 leaf 로 두어 데이터를 정확하게 분류할 수 있습니다.
이러한 추상적 개념을 impurity 라는 측도로 수치화 할 수 있습니다.
pure 한 것은 위와 같이 동일한 클래스의 노드가 같은 노드로 가는 것을 의미하고
impure 한 것은 여러 클래스가 섞여있는 것을 의미합니다.
때문에 impurity 를 최소화 하도록 (pure 하도록) test를 설정하는 것이
트리를 잘 생성하는 것 입니다.
impurity 은 다양한으로 표현방법이 있고
다음의 것들은 대표적인 impurity 측도입니다.
각각은 n 개의 클래스가 있는 트레이닝 데이터가 들어온 데이터에 해당하며,
pi는 i 번째 클래스에 속하는 트레이닝 데이터의 비율입니다.
- Accuracy : $1 - \max (p_1,p_2,\dots,p_n)$
- GINI Impurity : $1 - \sum_{i=1}^n(p_i)^2$
- Entropy : $\sum_{i=1}^n p_i \log_2 (1/p_i)$
예시를 통해 impurity 를 보자면
위의 예시에서 4개의 클래스가 있습니다.
Soccer 의 p는 5/12 이고, baseball, Hocket 는 둘 다 1/6, Cricket 은 1/4 입니다.
root 노드의 Accuracy 는 1-5/12 = 0.583,
GINI 는 $1-((5/12)^2 + (1/6)^2 +(1/6)^2 + (1/4)^2 ) = 0.715$
entorpy 는 $\frac{5}{12}\log_2(12/5) + \frac{1}{6}\log_2(6)+\frac{1}{6}\log_2(6) +\frac{1}{4}\log_2(4) = 1.875$
root 노드에서 왼쪽 자식 노드에 대해서 봅시다.
SA와 EUR 의 경우 Soccer 가 5/6, Cricket 이 1/6 입니다.
여기서 Accuracy는 1- 5/6 = 0.167
GINI 는 $1 -((5/6)^2+(1/6)^2 ) = 0.278$
entropy 는 $\frac{1}{6}\log_2(6) + \frac{5}{6}\log_2(6/5) =0.643$ 입니다.
위의 측도들은 scale은 다르기 때문에 값 자체가 중요한 것은 아닙니다.
동일한 측도에서 값을 비교하여 최소가되는 것을 찾는게 목적입니다.
Designing a Decision-Tree Node
test 를 만들 때 weighted average impurity 가 가장 작은 자식노드를 만들어야 합니다.
여기서 자식노드의 weight 는 그 노드에 도달하는 트레이닝 데이터의 수에 비례합니다.(많을수록 높다.)
test 는 다음과 둘 중 하나를 사용하여 이진으로 결정하도록 제한해야합니다.
- 입력 벡터의 하나의 feature 와 특정 값과의 크기 비교 (numerical)
- 입력 벡터의 하나의 feature 가 가능한 값들의 집합에 있는지 검사 (categorical)
위 예시에서 루트의 경우 2번에 해당합니다.
Continent 가 SA, EUR 이라는 집합에 포함되는지 검사합니다.
1번과 2번으로 test 를 생성합니다.
impurity 가 가장 많이 줄어드는 쪽으로 test 를 생성합니다.
이렇게 test 를 생성하다가, 만약 남은 트레이닝 데이터가 pure 하게 된다면
그 노드를 해당 클래스를 출력하는 leaf 노드로 만듭니다.
test 를 위한 feature 를 선택할 때,
feature 가 numerical 인지 categorical 에 해당하는지에 따라
처리방식에 차이가 있습니다.
Selecting a Test Using a Numerical Feature
numerical feature A 를 가지고 분할을 한다고 가정해봅시다.
위의 예시에서 A는 population 으로 볼 수 있습니다.
다음과 같은 절차대로 적절한 기준을 선택할 수 있습니다.
- A의 값의 크기 순 트레이닝 데이터를 나열합니다. $a_1,a_,\dots,a_n$
- j =1,2,..n 에 대해,
1부터 j 까지의 클래스 별 트레이닝 데이터의 수를 카운트 합니다.
즉, 각 클래스별 카운트가 n 개씩 있습니다.
계산은 하나씩 늘려가면서 수행할 수 있습니다.
j 였을 때를 계산하였으면 j+1 일 때는 하나의 데이터에 대해서만 보면 됩니다. - 2에서 계산한 카운트로부터,
weighted-average impurity 를 계산합니다.
앞에서 j 까지는 왼쪽, j 부터 n-j 까지는 오른쪽으로 둡니다.
impurity 는 각 클래스 별로 계산하고, Accuracy, GINI, entropy 등을 사용합니다. - weighted-average impurity 가 최소가 되는 j 의 값을 선택합니다.
일반적으로 $A <(a_j +a_{j+1})/2$ 을 비교에 사용합니다.
위 예시에서 root에 해당하는 test 를 만들어 봅시다.
현재는 numerical 인 population 만 feature 로 확인하는데,
실제 작업에서는 continent 와 population 둘 다 확인하여 최소로 나누는 것을 찾아야합니다.
6개의 칼럼은 다음과 같이 계산됩니다.
첫번째 $s_p$ 는 좋아하는 운동입니다.(class)
S - soccer, C - Csricket 입니다.
$n_s$ 와 $n_c$ 는 각 클래스의 누적 카운트입니다.
Ger 의 $n_s$=4 는 Arg 부터 5개의 row 중에 4개가 S 인 것입니다.
C 는 UK 하나이므로 $n_c= 1$ 입니다.
$p_s\leq$ 와 $p_c\leq$ 는 각각 S 와 C 의 클래스의 누적 비율입니다.
$p_s>, p_c> $ 는 아래행에서 부터의 클래스의 누적 비율입니다. (해당 행 포함 안함)
$IM\leq$ 와 $IM>$ 는 각각 왼쪽과 오른쪽 자식의 impurity 입니다.
GINI 를 사용하였으므로
$IM\leq \ = 1- ( (p_s\leq)^2 + (p_c\leq)^2) $ 이고, $IM> \ = 1- ( (p_s>)^2 + (p_c>)^2) $
마지막으로 weighted impurity 를 구합니다.
각 노드에 도달하는 데이터의 수로 weight를 줍니다.
Spain 의 경우 (2/6) 0 + (4/6) (3/8) = 1/4 로 구할 수 있습니다.
위 예시에서는 2/9 가 가장 작은 impurity 로
Italy 의 population 으로 분할할 수 있습니다. (population <60)
Selecting a Test Using Categorical Feature
categorical feature A 를 가지고 트레이닝 데이터를 어떻게 나누는지 확인해봅시다.
두가지 클래스만 있는 경우를 생각해봅시다.
위의 예시에서는 Soccer S 와 soccer 가 아닌 것 N 으로 나눕니다.
두개의 클래스가 있을 때, 트레이닝 데이터가 A의 값을 첫번째 클래스에 속하는 것의 비율로 나열할 수 있습니다.
클래스는 두 개뿐이므로,
첫 번째 클래스의 비율이 일부 임계 값을 초과하는 A 값이 impurity 가 가장 낮은값으로 볼 수 있습니다.
이렇게 되면, 왼쪽으로 가는 데이터들의 대다수는 첫번째 클래스이고
오른쪽으로 가는 데이터는 두번째 클래스 입니다.
weighted impurity 를 최소화하는 값으로 분할하는 과정은 본질적으로 numerical 과 같습니다.
차이는 categorical 은 A의 값(클래스)으로 리스트를 내려간 것이고, numerical 은 트레이닝 데이터의 리스트로 찾아내려가는 것 입니다.
위에서 $n_s , n_n$ 은 S와 N 의 누적 카운트 입니다.
Eur 의 경우 S가 3개, N 이 1개 있고, SA 에서 S 가 2개 였으므로
$n_s = 5 ,n_n=1$ 입니다.
$p_s\leq$ 는 $n_s / (n_s+n_n)$ 이고, $p_s>$ 는 아래의 모든 행에서 S/(S+N) 의 비율입니다.
$Im\leq, Im>$ 는 numerical 과 동일하게
$IM\leq \ = 1- ( (p_s\leq)^2 + (p_c\leq)^2) $ , $IM> \ = 1- ( (p_s>)^2 + (p_c>)^2) $ 으로 계산할 수 있습니다.
여기서 weight 도 이전과 동일하게 데이터의 비율을 사용하여서 계산하였습니다.
NA 와 같은 경우 (9/12)(40/81) + (3/12)(0) = 10/27 을 얻을 수 있습니다.
위 예시에서 5/36가 최소로, Eur 을 기준으로 분할합니다.
Comments