지도학습 > 의사결정나무 : CART, C5.0, C4.5, CHAID - R code

데이터 마이닝 파트 중 지도학습의 한 분야인 의사결정 나무에 대해 CART, C5.0, C4.5, CHAID, 분리기준 (카이 제곱 통계량 p값, 지니 지수, 엔트로피 지수, F통계량, 분산의 감소량), 가지치기(pruning)에 대해 알아보자. 

 

의사결정나무는 분류 및 회귀 문제 모두에 사용되는 기계 학습 알고리즘의 한 유형이다. 의사결정나무는 간단히 말해 가장 중요한 변수를 기반으로 데이터를 더 작은 하위 집합으로 재귀적으로(Recursive하게) 분할하고 결국 클래스 레이블 또는 예측 값을 나타내는 터미널 노드(terminal node, 리프)에 도달하는 방식으로 작동한다. 또한 의사결정나무는 그래픽으로 표현할 수 있어 모델 뒤에 숨겨진 논리를 쉽게 이해할 수 있다.

R에서는 의사결정 트리를 구현하기 위한 여러 패키지를 제공한다:

1) CART(분류 및 회귀 트리):

- 이진 분할을 사용하여 데이터를 분할하는 의사 결정 트리의 일반적인 구현

- CART의 목표는 데이터를 균일한 부분군(또는 "종단 노드")으로 분할하여 목표 변수(또는 "반응")가 예측 변수(또는 "특성")에 대한 값을 기반으로 새로운 관측치에 대해 높은 정확도로 예측할 수 있도록 하는 것이며, 이러한 예측은 터미널 노드의 최소 샘플 크기 또는 최대 트리 깊이와 같은 일부 중지 기준이 충족될 때까지 이진 분할을 사용하여 데이터를 더 작은 하위 집합으로 재귀적으로 분할함으로써 수행됨

- 트리 구축 프로세스의 각 단계에서 CART는 지니 지수 또는 정보 이득(엔트로피)과 같은 기준을 기반으로 데이터를 가장 잘 분리하는 분할을 선택함(이때 지니 지수는 관측치 집합의 불순물을 측정하는데, 0의 값은 완전한 순도(즉, 모든 관측치가 동일한 등급에 속함)를 나타내고 1의 값은 최대 불순물(즉, 관측치의 동일한 비율이 다른 등급에 속함)을 나타냄. 정보 이득은 부모 노드에서 자식 노드로의 엔트로피 감소를 측정하며, 0 값은 엔트로피 감소가 없음을 나타내며(즉, 분할은 대상 변수에 대한 정보를 제공하지 않음) 0보다 큰 값은 엔트로피 감소를 나타냄(즉, 분할은 대상 변수에 대한 정보를 제공함).

- 패키지 "rpart"는 CART 모델을 R에서 구현할 수 있게함 

- 장점: 연속형 변수와 범주형 변수를 모두 처리할 수 있는 빠르고 해석 가능한 알고리즘이며 결측 데이터와 특이치를 처리할 수 있음

- 단점 : 과적합되기 쉬우므로 훈련 데이터에는 매우 적합하지만 새로운 데이터(test data)에는 잘 적용되지 않는 복잡한 트리일 수 있음. (이 문제를 극복하기 위해 가지치기, 교차 검증 또는 앙상블 방법과 같은 다양한 기술 사용)

library(rpart) # CART 관련 패키지
library(caret) # cross-validation 관련 패키지 
data(mtcars) # 데이터 불러오기

fit <- rpart(mpg ~ ., data = mtcars, 
             na.action = na.omit,  #데이터 내 NA가 있는 경우 NA 데이터를 제외하고 모델 피팅 
             cp = 0.01, # complexity parameter(트리의 크기를 제어, 양수로 설정)
             ) 
print(fit)

# 과적합 방지를 위해 cross-validation을 적용 
library(rpart)
library(caret)
data(mtcars)
fitControl <- trainControl(method = "cv", number = 10)
fit <- train(mpg ~ ., data = mtcars, method = "rpart", trControl = fitControl)
print(fit)

# 시각화 
plot(fit)
text(fit, use.n = TRUE, all = TRUE, cex = 0.7)

 

2) C5.0

- 더 복잡한 규칙을 사용하고 누락된 데이터를 처리할 수 있는 CART의 개선된 버전

- C5.0은 트리를 구축하기 위해 그리디 알고리즘을 사용하며, 각 단계에서 엔트로피 또는 지니 지수로 측정된 불순물의 최대 감소를 제공하는 분할을 선택함

- 또한 부스팅을 사용하여 인스턴스의 가중치를 조정하여 오분류율이 높은 샘플이 트리 구성 중에 더 많은 주의를 받도록 함
- 장점 : 변수 선택(feature selection)을 수행하고 대리 분할을 통해 누락된 값을 처리할 수 있기 때문에 많은 기능과 결측값을 가진 대규모 데이터 세트 처리 가능함 / 또한 트리 가지치기를 지원하여 과적합을 극복하고 모델의 복잡성을 줄일 수 있음

- 패키지 "C50"은 R에서 C5.0 모델을 활용하는 데 사용됨 

library(C50)
data(mtcars)
ctrl <- C5.0Control(eval = "CV", classSummary = "weights") #cross-validation하기 
# cC5.0Control을 통해 fold의 갯수, validation 종류, boosting 종류 지정 가능 
# pruning하기 : fit <- C5.0(mtcars[, -1], mtcars[, 1], trials = 10) 
fit <- C5.0(mtcars[, -1], mtcars[, 1], control = ctrl)

# 결과에 대한 시각화 
rules <- rules(fit)

3) C4.5

- 최선의 분할을 결정하기 위해 정보 이득(information gain)을 사용하는 의사결정나무의 한 종류 

- 연속 및 범주형 변수를 모두 처리할 수 있고 결측값도 처리할 수 있는 ID3 알고리즘의 확장

- 정보 이득이 가장 높은 특징을 기반으로 데이터를 더 작은 하위 집합으로 재귀적으로 분할

- 패키지 "RWeka"는 C4.5 모델을 R에서 사용할 수 있도록 함

 

library(rpart)
data(mtcars)
fit <- rpart(mpg ~ ., data = mtcars, minsplit = 10, minbucket = 10)
# control the minimum number of samples required to split a node and 
# the minimum number of samples in a leaf node

# 시각화 하기
plot(fit)
text(fit)

4) CHAID(Chi-square Automatic Interaction Detection)

- 범주형 데이터를 위해 특별히 설계된 의사결정나무 알고리즘

- 카이 제곱 통계량을 사용하여 대상 변수와 예측 변수 간의 종속성을 측정하는 의사 결정 트리 알고리즘

- 범주형 변수에 대한 의사 결정 트리를 만드는 데 사용되며 예측 변수 간의 교호작용 효과를 처리할 수 있음

library(CHAID)
library(caret)
data(mtcars)
# 일반 
fit <- chaid(am ~ ., data = mtcars)

# cross-validation 적용
control<- trainControl(method = "cv", number = 10)
fit_cv <- train(am ~ ., data = mtcars, method = "chaid", trControl = control)

# prunning 적용
fit_pruned <- prune(fit, criterion = "Deviance")

# 시각화
plot(fit)
text(fit)