R언어 의사 결정 트리 및 다양한 개념

분류(Classification)란?

레코드들의 집합이 주어졌을 때 각 레코드는 속성의 집합으로 이루어져있고

특정 레코드가 어느 Class label에 위치하는지 나타내는 것이다.

즉, 여러 물건이 있을 때 레고라면 장난감이라는 Class label을 표기해준다.

이러한 분류를 하기위해 Training set을 두고 분류 학습을 시킨 후 Test set을 통해 분류를 시행함으로써

어떤 레코드가 와도 정확한 분류를 하기위해 트레이닝 시키는 것이 분류 작업의 목표이다.

이러한 분류 작업은 곧 빅데이터의 Class label을 나누기 위한 중요한 요소이다.

결정 나무(Decision Tree)

위와 같은 레코드들이 있을 때 속성을 이용하여 만든 트리가 결정 나무(Decision Tree)이다.

Refund가 YES면 새로운 Class label은 NO라고 표기해야하고 Refund가 NO이면서 Marst가 Single 혹은 Divorced 이고 TaxInc가 >= 80k이면 YES라고 표시해야한다 이런 것들이다.

이러한 결정 나무는 어떻게 조건을 나누냐에따라 결정 나무 모양이 서로 다르게 나타날 수 있다.

이러한 의사 결정나무를 생성하는데 있어 R에서는 tree, rpart, party라는 3가지 패키지(라이브러리)를 제공한다.

rpart를 이용하면 다음과 같다.

install.packages("rpart")
library(rpart)
train<-read.csv("sonar_train.csv",header=FALSE)
y <- as.factor(train[, 61]) 
x <- train[, 1:60]
fit<-rpart(y~., x)  # . : All variables, refer Formula Notations
 

sonar_train.csv :: http://sites.google.com/site/stats202/data/sonar_train.csv

sonar_test.csv :: http://sites.google.com/site/stats202/data/sonar_test.csv

우선 sonar 데이터를 이용하여 해보자

y에는 train의 61번째 열의 값들을 factor로 담아두고 x에는 1~60번째 열들의 값들을 data.frame으로 가지고 있는다

그리고 rpart에서 y에 해당하는 값들을 기준으로 의사 결정 나무를 만들건데 트레이닝 값들을 x로 했다는 의미이다.

Hunt's Algorithm

위의 그림을 보면 바로 파악이 가능하다.

모든 레코드는 루트에서 시작하며 같은 클래스에 속하는 것들끼리 서로 계속해서 나누어준다.

그리고 최종적으로 얻고자하는 것을 말단 노드에 위치시키면 된다.

즉, 노드에 부여되는 record 집합이 동일 class 에 속할 경우 stop하는 것이 Hunt's algorithm이다.

이러한 의사 결정 나무를 최적으로 만들기 위한 방법을 생각해보자.

지니 계수

지니 계수를 이용하여 Impurity를 측정 할 수 있다.

Maximum (1 - 1/n) : 각 class 마다 record 수가 동일하게 분포하는 경우이다.

이때 지니 계수는 0.5를 유지하게 되고 최적의 의사 결정 나무를 만들 수 있게 된다.

Minimum (0) : 모든 record 가 한 개의 class 에 속하는 경우이다.

이대 지니 계수는 0을 유지하게 되고 최악의 의사 결정 나무를 만들수 있게 된다.

2번 테이블의 지니 계수를 구해보자.

1 - (1/6)^2 - (5/6)^2을 하면 0.2777...이 나오게 된다.

위의 테이블중 최적의 지니 계수를 가진 1번 테이블이 최적의 의사 결정 나무를 만들 수 있다.

위의 그림을 보면 알수있듯이 Entropy 및 Gini와 Misclassification error은 0에 가까울수록 최적의 의사결정 트리를 만들 수 있게 된다.

Overfitting

Overfitting은 필요한 만큼보다 더 복잡한 tree를 만드는 경우를 말한다.

즉, sample data에 모델이 너무 딱 맞아 떨어져서 다른 데이터에 대해서는 안 맞게 되는 경우를 의미한다.

따라서 이러한 경우 트리를 새로이 구성할 필요가 있다.

이런 Overfitting을 대처하는 방법은 다음과 같다.

Pre-Pruning

Tree 를 완전히 키우지 않고 도중에 splitting 을 중지.

Hunts 의 기본 알고리즘에서 정지하는 조건

모든 record 가 동일한 class 일 경우

모든 record 의 예측변수 값이 동일할 경우

더 제한 적인 조건

record 의 수가 미리 정해진 수 이하 일 경우

node를 split 해도 impurity measure 를 개선 할 수 없을 경우. 

Post-pruning

먼저 tree 를 완전히 자라게 한 다음 Bottom-up 방식으로 tree 를 가지 치기하는 방식

Reduced Error Pruning:  가지치기를 시도해 보고  만일 generalization error가 개선 된다면 subtree를 단말 node 로 대치 함.

rpart 에서는 error 계산을 위하여 training data set으로 X(cross) validation한다.

단말 node 의 class label은 node에서 다수를 차지하는 record의 class label로 정함. 

이때 rpart 패키지에서는 cp값을 증가시켜가며 tree 크기를 감소시켜 x validation error(xerror)을 계산한다.

이때 xerror이 최소로 하는 cp가 최적이다.

> p_fit <- prune(fit, cp=fit$cptable[which.min(fit$cptable[, "xerror"]), "CP"])

> plot(p_fit)

> text(p_fit)

p_fit에는 prune(가지치기)한 값을 넣을 것이다.

이때 fit에 담긴 정보를 이용할 것이고 cp는 fit의 cptable에 있는것중에서 fit의 cptable에서 "xerror"열에 있는 것중 최소를 가져올 것이다.

트리의 장/단점

이런식으로 트리로 분류하면 장단점이 존재한다.

트리의 장점

이해가 쉽다(모형 및 결과 변수들의 관계를 알기 쉽다)

다양한 변수 종류에 사용할 수 있다. 

계산 속도가 빠르다 -> 큰 dataset 에도 이용가능함. 

트리의 단점

변수들간의 관계가 지나치게 강조될 수 있다. 

초기의  split 이 왜곡된 경우 오류가 확산되어 말단 노드에서 잘못된 결과를 초래한다.

이산형 변수가 다수의 값을 가지는 경우 Binary split 만이 반복되어 신뢰하기 힘든 결과를 보일 수 도있다. 

Overfitting 이 쉽게 일어난다.

정확도 측정

정확도 측정은 아래와 같은 공식으로 이루어진다.

예를들어 2 class에서 record set 분포에서 FALSE 레코드가 9900개 있고 TRUE 레코드가 10개 있었다 가정하고

이 모델이 모든 샘플을 FALSE로 예측했다면 

TP = 0 FN = 10 FP = 0 TN = 9900

(0 + 9900 / 0 + 9900 + 0 + 10) * 100 = 99.0%의 확률로 예측한다.

test <- read.csv('http://sites.google.com/site/stats202/data/sonar_test.csv', header = FALSE)
 
y <- as.factor(test[,61])
x <- test[,1:60]
 
p_fit<-prune(fit, cp=fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"])
 
prediction <- predict(p_fit, x, type="class")
actual <- y
 
conf_matrix <- table(prediction, actual)
conf_matrix

정확도를 측정하기 위해 위의 코드를 작성해보면 conf_matrix에서 확인 할 수 있다.

library("caret")
confusionMatrix(prediction, actual, dnn = c("Prediction", "Actual"))

혹은 위의 라이브러리를 이용하여 정확도 및 다른 내용을 모두 확인해 볼 수 있다.

만약 정확도를 판별하는데 있어 cost까지 부여된다면 아래와 같이 계산하면 된다.