Decision Tree (1/41) -> (41/41)

Decision Tree (앞으로 DT라 말하겠다.) 는 SVM 에 비해 고안된지 오래되었고 매우 강건한 (Robust) 방법이다.

그리고 DT 또한 SVM 의 kernel trick 과 같은 방법으로 비선형(non-linear)을 선형(linear)으로 나타내어 분류할 수 있다.

자, 알아들을 수 없는 소리는 여기까지하고 쉬운 예들로 DT 에 대해 설명하겠다.

<그림 1> DT Windsurf

<그림 1> 을 살펴보자.

철수가 윈드서핑을 한다고 하자. 윈드서핑을 할 때는 바람도 많이불고 햇빛도 많이 비춰야한다. (그렇다고 태풍에 열사병이 걸릴 정도는 아니다.) 이 경우 빨간색 원은 윈드서핑을 할 수 없는 날씨, 녹색 삼각형은 윈드서핑을 할 수 있는 날씨이다. 이러한 경우 윈드서핑 가능여부를 선으로 나눌 수 있나? (Linearly Separable 한가?) 답은 <안된다.> 이다. 

DT 의 경우 아래 <그림 2> 와 같이 데이터를 분류한다.

<그림 2> DT Windsurf (How to decide)

다음은 Katie 와 DT 에 관한 코딩을 잠시 할 것이다. (실제로 Udacity 에서 코딩을 하지 않는다면 넘어가도 된다.)

아래의 <코드 1> 과 같이 입력하면 된다.

Constructing a Decision Tree 예제 classifyDT.py 파일 내에 작성하면 된다.

from sklearn import tree

clf = tree.DecisionTreeClassifier()
clf.fit(features_train, labels_train)

<코드 1> DT First example in Lesson

첫 번째 예제에서 Fitting 한 데이터를 보면 매끄럽지 않고 조잡하게 되어있다.

이 부분은 학습 데이터의 문제이다. 

DecisionTree Accuracy 예제

from sklearn import tree

clf = tree.DecisionTreeClassifier()
clf.fit(features_train, labels_train)

acc = clf.score(features_test, labels_test)

<코드 2> DT Accuracy

<코드 2> 는 DT Accuracy 에 대한 코드, 그리고 아래 <코드 3> 은 다음으로 설명할 DT Classifier 의 min_samples_split 값에 대한 코드이다.

Decision Tree Accuracy 예제에서 min_samples_split 변경 예제 (기본값 = 2) 2 : 0.908, 50 : 0.912

from sklearn import tree

clf1 = tree.DecisionTreeClassifier(min_samples_split = 2)
clf1.fit(features_train, labels_train)
acc_min_samples_split_2 = clf1.score(features_test, labels_test)
clf2 = tree.DecisionTreeClassifier(min_samples_split = 50)
clf2.fit(features_train, labels_train)
acc_min_samples_split_50 = clf2.score(features_test, labels_test)

<코드 3> DT Classifier min_sample_split Parameter

당장 위의 <코드 3> 의 min_samples_split 을 이해하기 어려울테니 아래 그림을 참고해서 이해하자.

<그림 3> DT_Classifier min_samples_split = 2

<그림 3> 의 맨 위 100 은 (아직 분류하지 않은) 분류할 데이터의 개수이다. 화살표로 한 레이어를 내려올 때마다 특정 기준을 이용하여 분류된 것이다. (<그림 1> 의 Windy ? 와 같은 것)

<그림 3> 맨 아래 원 중 빨간색 원은 더이상 나눌 수 없다는 것인데 이는 min_samples_split 값이 2 이기 때문이다.

만약 min_samples_split 값이 50이라면 어떻게 되었을까? 이는 <그림 4> 에 나와있다.

<그림 4> DT_Classifier min_samples_split = 50

두 경우의 차이를 살펴보자. min_samples_split Parameter 값이 클수록 덜 상세하다. 하지만 매우 상세할 경우 Overfitting 이 되기 때문에 이 값을 적절히 조절해야 한다. 

다음으론 DT 에서 Entropy 에 대해 알아보겠다.

<그림 5> DT_Purity

엔트로피의 관점에서 <그림 5> 를 살펴보자. 오른쪽이 더 Pure 하다. DT 는 이런식으로 더 Pure 하게 데이터를 분할해 준다. (더 Pure 할 때 분할한다는 말이 맞을 것이다.)

(얼마나 더 Pure 하게 할 것인지와 연산시간 사이를 결정해야한다.)

다음으론 얼마나 더 Pure 한지에 대해 나누는 기준인 Information Gain 에 대해 알아보겠다.

강의에서 사용한 예시를 그대로 사용하여 살펴보자.

<표 1> DT Example

<표 1> 은 4 가지 상황에 대해 적어놓았다.

먼저 Speed 에 대한 엔트로피를 구해보자.

$P_{slow} = \frac{1}{2}, P_{fast} = \frac{1}{2}$ 이고 엔트로피 값은 1 이다.

$Information Gain = entropy(parent) - [weighted average] * entropy(child)$

Information Gain 에 대한 식은 위와 같다. (weighted average 는 보통 1이다. 사실 이 의미는 아직 나도 잘 모른다.)

앞서 구한 Speed 를 Parent 로 설정하고 Grade 를 Child 로 정하고 Information Gain 을 구해보자.

<그림 6> DT Example (Information Gain)

먼저 Speed 에 대해 엔트로피를 구한 후 그의 Child 인 Grade 의 엔트로피를 구해야한다. 

Grade 가 Steep 한 경우에는 $P_{slow} = \frac{2}{3}, P_{fast} = \frac{1}{3}$ 이다. 그리고 오른쪽 Flat 한 경우에는 한 경우밖에 없기 때문에 엔트로피가 0 이다.

이 때 Child 의 엔트로피를 구하면 다음과 같다.$entropy(child) = \frac{3}{4}[-\frac{2}{3}\log_{2}\frac{2}{3} - \frac{1}{3}\log_{2}\frac{1}{3}] + \frac{1}{4} * 0 = 0.9183$

이 때의 Information Gain 은 다음과 같다. $Information Gain = 1 - 0.9183 = 0.0817$

Information Gain 값은 현재 나의 속성 (Speed) 이 다른 속성 (Grade) 을 얼마나 잘 구분하나에 대한 수치이다. (높을수록 더 잘 구분한다.) <그림 6> 에서 사용한 경우는 <잘 구분하지 못한 경우> 이다.

잘 구분한 경우에 대해 알고싶다면 Speed 와 Speed Limit 에 관해 Information Gain 값을 구해보면 될 것이다. 

다음은 Mini Project 이다.

이번에도 저번 분류방법에서의 프로젝트와 같이 이메일 분류를 해보았다.

from sklearn import tree
clf = tree.DecisionTreeClassifier(min_samples_split=40)
clf.fit(features_train,labels_train)

pred = clf.predict(features_train)
print features_train
print features_train[0]
print len(features_train[0])

print clf.score(features_test, labels_test)

<코드 4> DT Mini Project

#    Change Selector Percentile value
selector = SelectPercentile(f_classif, percentile=1)

<코드 5> DT Mini Project

이번 Mini Project 에서는 DT 로 나눌 수 있는 Feature 수에 주목해야 한다. Feature 수가 클수록 더 세세하게 데이터가 나누어진 것이고 이 경우 Overfitting 될 수 있다.

그리고 <코드 5> 에서와 같이 Selector Percentile 를 수정함으로써 Feature 의 개수를 변경하고 Accuracy 에 영향을 줄 수 있다.

이번 글은 여기까지다.

여담으로 기계학습에서 알아야 할 것은 Bias 와 Variance 이다.

Bias 가 너무 크면 <편견> 이 심해 데이터 학습이 잘 안되는 것이고, Variance 가 너무 크면 <배운게 없어> 새로운 상황에서 잘 적응하지 못하는 것이다.

두 값 사이에 어느 곳에 중점을 둘지는 사용자의 선택에 달려있다.

<참고 문헌>

1. Intro to ML in Udacity

<그림>

<코드>