[Artificial Intelligence / Machine Learning] Decision Tree - C5.0 Algorithm

Overview

• Decision Tree 알고리즘 중 가장 알려진 것 중 하나

• 컴퓨터 과학자 J. Ross Quinlan이 개발함

• Iterative Dichotomiser(ID3)에 대한 개선한 C4.5 알고리즘을 개선한 것임

• RuleRequest Research에서 알고리즘을 다운받을 수 있음

강점	약점
대부분의 문제에 적합함 손실 데이터를 포함한 숫자형 또는 명칭형 데이터를 다룰 수 있는 자동화 Learning Process 중요하지 않은 특징 제거 데이터 셋의 규모에 상관없이 사용 가능 수학 배경 없이도 해석할 수 있는 모델 생성 다른 복잡한 모델 보다 효율적	Decision Tree 알고리즘은 많은 수의 레벨을 갖는 Feature에 대한 구분에 있어 치우는 경향이 있음 모델에 대한 과다 적합 또는 미적합 되는 경향이 있음 축에 평행 분할에 대한 의존성으로 인해 어떤 상관성은 모델을 세우기가 쉽지 않음 트레이닝 데이터의 작은 변화가 Decision Logic에 큰 변화를 일으킬 수 있음 Large Tree는 해석되기 어렵고 이를 통한 해석이 실제와는 반대되는 경우가 있을 수 있음

Entropy

• Information Theory로부터 용어를 가져온 것으로 Dataset의 순수성(Purity)에 대한 측정 기준이다.

예를 들어 Class가 하나인 경우(Single Class), 순수(Pure)하다고 정의한다.

Entropy, S는 다음과 같이 정의된다:

\(S=\sum_{i=1}^{n}{p_i}{log_2}{(p_i)}\)

여기서,

n : Dataset의 데이터 개수

p_i : i-번째 데이터의 확률 (0과 1까지의 값)

Class가 2개인 경우, 두 개의 Class의 확률에 따른 Entropy를 살펴보면:

CODE:

library(ggplot2)
p <- seq(from = 0.01, to = 0.99, by = 0.01)
y <- -p * log2(p) - (1 - p) * log2(1 - p)

df <- data.frame(matrix(ncol = 2, nrow = length(p)))
names(df) <- c("Probability", "Entropy")

df$Probability <- p
df$Entropy <- y

ggplot(df) + geom_line(data = df, aes(Probability, Entropy), colour = "red", size = 1)

Information Gain

• Dataset의 분할에 따른 균일성(homogeneity)의 변화량

• 분할하기 전(현재 분할된 상태)의 Entropy, S₁과 분할 후의 Entropy S₂의 차이로 다음과 같이 계산됨:

InfoGain(F) = Entropy(S₁) - Entropy(S₂)

분할이 된 후에는 최소 1개의 Partition이 존재하므로 Entropy(S₂)는 모든 Partition에 걸쳐 총 Entropy를 계산해야 된다.

이는 각 Partition에 속하는 비율에 대하여 가중치를 정하여 계산하도록 한다. 즉,

\(S=\sum_{i=1}^{n}{w_i}{\mathbf{Entropy}{(P_i)}}\)

와 같이 계산된다.

Information Gain이 높을수록 분할 후의 균일한 그룹을 생성하는 경향이 있다. Information Gain이 0이면, 분할에 따른 Entropy의 감소가 없음을 의미한다. 최대 Information Gain은 분할 전의 Entropy와 같다. 이것은, 분할 후의 Entropy가 0임을 의미하며, 분할이 완전히 균일한 그룹을 생성하였음을 의미한다.

Pruning

Pruning이란, Decision Tree의 크기를 적절한 크기로 제한하는 것과 관련이 있다.

즉, Decision Tree는 완벽한 분류에 도달하거나 더 이상 분류를 할 수 있는 특정 기준이 없어질 때까지 무한히 커질 가능성이 있는데, 만약 이와 같이 될 경우 Decision Tree가 불필요하게 커지고 학습 데이터에 대하여 과도하게 구체적이 될 수 있다.

이에 대하여 다음과 같은 해결책이 있다 :

1. Pre-pruning (Early Stopping)

• 특정 개수의 Decision을 정해놓고 그 수에 도달하면 Tree 성장을 멈추도록 한다. 또는,

• Decision Node에 속하는 최소 멤버 수를 정해놓고 그 수보다 못 미치면 Tree 성장을 종료한다.

단점은, Tree가 성장하도록 학습시킨 미묘하지만 중요한 패턴이 있는데 이것을 미리 알 방법이 없다는 것이다.

2. Post-pruning

Post-pruning은 의도적으로 Decision Tree를 크게 성장시킨 후에 적절한 수준으로 가지치기(Branch Removing)하는 방법이다. 이 방법은 Decision Tree를 성장시키지 않고는 최적의 크기를 미리 알 수가 없기 때문에 Pre-pruning 보다는 효율적인 방법이라고 할 수 있다.

C5.0 알고리즘은 "합리적" 기본값을 이용하여 자동으로 Pruning을 해주며, 이 알고리즘의 기본 전략은 Post-pruning이다. 우선적으로 학습 데이터를 과적응(Overfitting) 시킨 후 분류 오차(Classification Error)가 작은, 즉 분류에 큰 영향력이 없는 Branch들을 제거하는 것이다. 어떤 경우에는 전체 Branch들을 상위 레벨로 이동시키는 경우가 있는데 이를 Subtree Raising이라고 하며, 또는 전체 Branch들을 보다 단순한 구조로 대체하는 경우가 있는데 이를 Subtree Replacement라고 한다.

계산과학에는 언제나 Trade-off가 존재하기 마련이다. 결과의 정확성을 올리려면 계산량(또는 계산시간)이 더 투입되어야 하며, 반대로 계산시간을 단축하려면 정확성이 떨어질 수 밖에 없다. 즉, Decision Tree의 Overfitting 또는 Underfitting은 수학적 또는 논리적 기준이 있는 것이 아니라 예술에 가깝다. 무슨 뜻인가 하면, 정확도가 요구하는 모델이라면 테스트 데이터에 대한 성능을 올리려면 다양한 Pruning 옵션을 사용하여 테스트를 수행하는 시간을 투자해야 한다.